книги / Практическая криптография

Глава 16

Проблемы реализации. Часть II

Протокол согласования ключей, описанный в предыдущей главе, приво­ дит к появлению еще нескольких проблем реализации.

16.1Арифметика больших чисел

Все вычисления с открытым ключом подразумевают применение ариф­ метики больших чисел. Как уже отмечалось, правильно реализовать ариф­ метику больших чисел крайне сложно.

Реализация арифметических операций над большими числами практиче­ ски всегда в той или иной мере зависит от платформы. Эффективность, кото­ рой можно добиться, учитывая специфические свойства платформы, слиш­ ком высока, чтобы ею пренебрегать. Например, большинство процессоров поддерживают инструкцию “сложение с переносом" (Add With Carry — ADC) для реализации операций сложения многократной точности. Но в С и боль­ шинстве других языков высокого уровня эта инструкция недоступна. Выпол­ нение арифметических операций над большими числами в языке высокого уровня обычно происходит в несколько раз медленнее, чем в реализации, оп­ тимизированной для конкретной платформы. Кроме того, вычисления с ис­ пользованием больших чисел образуют “узкое место" в производительности криптосистемы с открытым ключом, поэтому применение кода, специфично­ го для конкретной платформы, просто необходимо для повышения эффек­ тивности.

Обсуждать вопросы реализации арифметических операций над больши­ ми числами мы не будем. Для этого существуют другие книги. В качестве хорошей отправной точки можно порекомендовать книгу Кнута [54]. Нас же, скорее, будет интересовать то, как тестировать арифметические операции над большими числами.

304	Глава 16. Проблемы реализации. Часть II

В криптографии наши цели отличаются от тех, что преследуются боль­ шинством разработчиков. Мы считаем уровень сбоя в 2-64 (примерно один к 18 миллионам триллионов) недопустимым, в то время как другие разра­ ботчики вполне бы довольствовались и этим. Многие программисты считают уровень сбоя в 2-20 (примерно один к миллиону) вполне приемлемым, а то и вовсе замечательным. Нам же, как криптографам, нужно предъявлять бо­ лее строгие требования к системе, поскольку мы работаем в противоборству­ ющем окружении.

Большинство блочных шифров и функций хэширования достаточно легко поддаются тестированию1. Лишь некоторые недочеты реализации приводят к появлению ошибок, которые трудно обнаружить путем тестирования. Ес­ ли вы ошибетесь в реализации S-матрицы шифра AES, ошибка всплывет уже после нескольких сеансов шифрования. Простое тестирование с помощью по­ следовательности случайных тестов исследует все пути данных в блочном шифре или функции хэширования и быстро обнаружит любые системати­ ческие ошибки. Путь кода, который выбирает программа при выполнении шифрования или хэширования, не зависит или практически не зависит от самих данных. Любой приличный набор тестов для симметричной функции шифрования исследует все возможные потоки управления, существующие

вреализации.

Сарифметикой больших чисел все обстоит иначе. Здесь в большинстве реализаций путь кода, который выбирает программа при выполнении опера­ ции, зависит от самих данных. Например, код, осуществляющий последний перенос при сложении, используется крайне редко. Функции деления часто содержат фрагмент кода, который применяется только один раз на каждые 232 или даже 264 операции деления. Ошибка в этой части кода не будет об­ наружена с помощью случайного тестирования. Ситуация становится еще хуже при использовании процессоров с ббльшим количеством разрядов. Для 32-разрядного процессора мы в принципе можем выполнить 240 случайных теста и ожидать, что каждое 32-битовое слово встретится в каждой части пути данных, но этот способ тестирования совершенно неприемлем для 64разрядных процессоров.

Из всего изложенного следует, что проводить тестирование арифметиче­ ских операций над большими числами следует крайне осторожно. Разработ­ чику нужно убедиться в том, что в процессе тестирования программа дей­ ствительно пройдет все существующие пути кода. Для этого необходимо тща­ тельно подбирать тестовые векторы —занятие, которое требует определенной точности и внимания. Вам понадобится не только использовать все существу-

*В качестве наиболее примечательных исключений можно назвать шифры IDEA и MARS, в которых используется отдельный код для тестирования частных случаев.

16.1 Арифметика больших чисел

305

ющие пути кода, но и перебрать все граничные условия. Например, если у нас есть тест для о < 6, мы должны протестировать этот же фрагмент кода для а = 6— 1,а = 6 и а = 6+ 1 (разумеется, если эти условия вообще могут быть достигнуты).

И без того нелегкое положение еще более усложняется с появлением опти­ мизации. Поскольку упомянутые выше функции создают узкое место в произ­ водительности системы, их всячески пытаются оптимизировать. Это, в свою очередь, приводит к появлению множества частных случаев, путей кода и т.п., что еще более затрудняет тестирование.

Простая арифметическая ошибка может иметь поистине катастрофиче­ ские последствия для безопасности системы. Вот небольшой пример. Пусть в код, вычисляющий значение цифровой подписи RSA, вкралась небольшая ошибка, которая дает неверный результат при возведении в степень по моду­ лю р, но верный при возведении в степень по модулю q. (Предположим также, что для ускорения этой процедуры применяются CRT-представления.) Под­ писывая свои сообщения, пользователь А вместо верной цифровой подписи а отсылает подпись а + kq, где к — некоторое число. (Чтобы результат, полу­ ченный пользователем А, был верным по модулю q, но неверным по модулю р, он должен иметь вид cr-j- kq.) Злоумышленник знает a3 mod п — число, из которого пользователь А извлекает корень третьей степени и которое зависит только от сообщения. Но разность (a + kq)3 — а3 кратна q. Найдя наибольший общий делитель этой разности и числа п, злоумышленник узнает q и таким образом сможет разложить число п на простые множители. При одной мысли об этом нас охватывает ужас!

Вы спросите, что же в таком случае делать? Во-первых, не пытайтесь реализовать собственную библиотеку для работы с большими числами. Вос­ пользуйтесь какой-нибудь существующей библиотекой. Если вам некуда де­ вать свое время, лучше потратьте его на то, чтобы разобраться в существу­ ющей библиотеке и хорошенько ее протестировать. Во-вторых, разработайте действительно хорошие тесты для своей библиотеки. Убедитесь, что вы про­ тестировали все возможные пути кода. В-третьих, вставьте дополнительные тесты в само приложение. Для этого можно воспользоваться несколькими методами.

16.1.1Вупинг

Метод, описанный в этом разделе, имеет довольно непривычное назва­ ние — вупинг (wooping). Во время одного жаркого спора между Дэвидом Шомом (David Chaum) и Юрьеном Босом (Jurjen Bos) срочно понадобилось придумать имя для специальной верификационной переменной. В пылу деба­

306 Глава 16. Проблемы реализации. Часть II

тов кто-то предложил назвать ее словом “woop”2. Впоследствии это название закрепилось и за самим методом. Через некоторое время Бос описал дета­ ли вупинга в своей докторской диссертации [10, глава 6], но опустил слово “wooping”, чтобы не шокировать почтенное академическое общество.

Основная идея вупинга заключается в том, чтобы проверять правиль­ ность вычислений по модулю с помощью случайно выбранных малых про­ стых чисел. Для большей наглядности это можно представить себе в виде криптографической проблемы. У нас есть библиотека арифметических опе­ раций над большими числами, которая пытается “обмануть” нас и предо­ ставить неверные результаты. Наша задача состоит в том, чтобы проверить правильность этих результатов. Простая проверка результатов с помощью все той же библиотеки не принесет никакой пользы, так как ошибка может последовательно повторяться по всему коду библиотеки. Используя вупинг, мы можем проверить правильность библиотечных вычислений, если предпо­ ложим, что библиотека не пытается “нарочно” навредить нам (в том смысле, что она не портит преднамеренно наши вычисления, выполняемые в рамках верификации).

Вначале мы случайным образом генерируем относительно малое простое число t длиной около 64-128 бит. Значение t не должно быть фиксированным или предсказуемым, но именно для этого и предназначен генератор псевдо­ случайных чисел. Полученное значение t сохраняется в секрете от остальных участников общения. Затем для каждого большого числа х, которое фигу­ рирует в вычислениях, мы подсчитываем х := (х mod t). Число х — это и есть функция WOOP(x). Значения функции WOOP(x) имеют фиксиро­ ванный размер. Обычно они намного меньше соответствующих больших чи­ сел. Поэтому вычисление WOOP(x) не требует больших расходов системных ресурсов.

Итак, для каждого целого числа х мы сохраняем значение WOOP(x). Для каждого значения, которое подается на вход нашего алгоритма, мы сра­ зу же вычисляем х как х mod t. Во всех внутренних вычислениях нашей библиотеки выражения над большими числами будут дублироваться анало­ гичными выражениями над значениями WOOP. Следовательно, мы сможем подсчитать WOOP результата выражения, подставив в него значения WOOP входных чисел, а не применяя функцию WOOP к конечному результату вы­ ражения, как при выполнении операции взятия по модулю.

Обычная операция сложения выполняется как с := а + Ь. Мы, в свою очередь, можем вычислить с, используя равенство с = а + b(modt). Анало­

2На русский язык слово “wooping” (или “whooping”) можно перевести как “вопль”, “улю­ люканье” или “приступ кашля”. Действительно, такое название могло родиться только в пы­ лу жарких споров. — Прим, перев.

16,1 Арифметика больших чисел

307

гичным образом можно продублировать и операцию умножения. Мы можем проверять правильность с после каждого сложения или умножения, опреде­ ляя, выполняется ли соотношение с mod t = с. Впрочем, гораздо эффектив­ нее проводить все эти проверки в самом конце.

Выполнять операцию сложения по модулю п лишь немного труднее, чем обычную операцию сложения. Вместо того чтобы просто записать с = (а + b) mod п, мы представляем это как с = а + 6 + Jfc •п, где число к вы­ брано таким образом, что результат с находится в диапазоне 0, . .. , п — 1. Это всего лишь другой способ записи взятия числа по модулю. В данном случае к равно 0 или —1 при условии, что числа а и Ълежат в диапазоне 0,... ,п — 1. Соответствующее выражение с использованием вупинга выгля­ дит как с = (a+b+ k-n) mod t. Отметим, что внутренняя реализация операции сложения по модулю “знает” к. Нам необходимо лишь получить от библиоте­ ки значение /г, чтобы можно было вычислить к.

Умножение по модулю выполнить гораздо сложнее. В этом случае нужно снова записать с = а •Ъ+ к •п. Чтобы вычислить с = а -Ь + к *n(mod £), мы должны знать а, 6, п и к. Первые три числа у нас уже есть, а вот значение к нужно каким-то образом извлечь из функции умножения по модулю. Это можно сделать при создании библиотеки “с нуля”, однако модифицировать существующую библиотеку будет весьма сложно. В качестве универсально­ го решения можно предложить следующее: вычислить о •6, а затем поде­ лить полученный результат на п, используя деление “в столбик”. Полученное частное и будет тем самым значением А:, которое необходимо для вычисления WOOP (/с). Остаток от деления — это результат с. Единственным недостатком универсального метода является крайне медленная скорость его выполнения.

Применив вупинг к операции умножения по модулю, это несложно сде­ лать и для операции возведения в степень по модулю. Большинство функ­ ций возведения в степень по модулю вычисляют результат посредством ряда обычных умножений по модулю. (Некоторые из них используют отдельную функцию возведения в квадрат по модулю, но и ее можно продублировать с помощью вупинга как обычную операцию умножения по модулю.) Доста­ точно лишь сохранять для каждого большого числа х значение WOOP(x) и вычислять WOOP каждого произведения как произведение значений WOOP входных чисел.

Как видите, алгоритмы, использующие вупинг, вычисляют WOOP резуль­ тата выражения на основе значений WOOP входных чисел. Если значение WOOP одного или нескольких входных чисел окажется неверным, WOOP результата выражения практически наверняка также окажется неверным. Другими словами, ошибка хотя бы в одном значении WOOP распространится и на конечный результат.

308 Глава 16. Проблемы реализации. Часть II

По окончании вычислений мы проверяем правильность значений WOOP. Если результат операции над большими числами равен х, нам нужно про­ верить, что (х mod £) = х. Если в реализации библиотеки была допущена ошибка, значения х mod £ и х не совпадут. Мы исходим из предположения, что ошибки библиотеки не были специально подобраны таким образом, чтобы давать нужные результаты в зависимости от того, какое значение £ мы вы­ берем. В конце концов, библиотека разрабатывалась задолго до того, как мы выбрали £, а код готовой библиотеки уже не находится под контролем зло­ умышленника. Легко показать, что любая ошибка библиотеки может быть обнаружена с помощью практически любого значения £. Таким образом, до­ бавление к существующей библиотеке верификации на основе вупинга — пре­ красный способ проверки правильности вычислений.

После этого остается лишь найти библиотеку арифметических операций над большими числами со встроенной системой верификации на основе ву­ пинга. Но нам такая библиотека еще не попадалась.

Какой величины должны быть значения WOOP(x)? Это зависит от мно­ гих факторов. Для случайных ошибок вероятность того, что применение ву­ пинга не обнаружит ошибку, составляет около 1/£. К сожалению, в нашем ми­ ре не бывает случайностей. Пусть в коде библиотеки содержится программ­ ная ошибка, и, к нашему огорчению, злоумышленник знает о ее существо­ вании. Он может выбирать входные данные наших вычислений и не только инициировать ошибку, но и выбирать отклонение этой ошибки от правиль­ ного значения. Вот почему значение £ должно быть случайным секретным числом; не зная £, злоумышленник не сможет выбрать такую разницу, кото­ рая точно была бы пропущена нами в ходе вупинга.

Как бы мы поступили в подобной ситуации на месте злоумышленника? Мы бы, конечно же, инициировали ошибку. Кроме того, мы бы попытались свести отклонение от правильного результата к нулю для наибольшего коли­ чества модулей £. Самая простая защита от атак подобного рода — выбрать £ так, чтобы оно было простым числом. Если злоумышленник хочет обмануть нас, скрыв ошибку вычислений для шестнадцати 64-битовых простых £, ему придется тщательно выбрать минимум 16 •64 = 1024 бит входных данных. Поскольку большинство вычислений ограничивают количество входных би­ тов, которые могут быть выбраны злоумышленником, применение простого £ снижает вероятность того, что атака пройдет успешно.

Чем больше значение £, тем лучше. Существует так много простых чисел большого размера, что вероятность успеха атаки быстро снижается с увели­ чением размера £. Если бы мы, как обычно, стремились придерживаться 128битового уровня безопасности, длина числа £ должна была бы составлять 128 бит или около того.

16.1 Арифметика больших чисел

309

Отметим, что вупинг ни в коей мере не является основным средством обеспечения безопасности системы; скорее, это вспомогательная мера. Если верификация на основе вупинга окончится неудачей, мы поймем, что в про­ граммном обеспечении содержится ошибка, которая должна быть устранена. Такая программа должна аварийно завершить свое выполнение и выдать со­ общение о неисправимой ошибке (fatal error). Подобное поведение еще более усложняет проведение повторных атак на систему. На практике мы пред­ лагаем использовать в качестве t 64-битовое случайное простое число. Это значительно сократит расходы по сравнению с использованием 128-битово­ го простого числа и обеспечит достаточный уровень безопасности. Если вы не можете позволить себе 64-битовое £, используйте 32-битовое — это всегда лучше, чем ничего. Особенно хорошо 32-битовые значения t подходят для использования в системах с 32-разрядными процессорами, поскольку к ним могут быть применены прямые инструкции умножения и деления.

Если функции библиотеки будут включать в себя вычисления, позволя­ ющие злоумышленнику выбирать большой объем данных, вам понадобится

проверять и промежуточные значения WOOP(z). Эти проверки имеют чрез-

7

вычайно простой вид: (х mod t) = х. Проверяя промежуточные значения, ко­ торые зависят лишь от ограниченного числа битов, выбранных злоумышлен­ ником, мы значительно затрудняем атаку последнего на систему вупинга.

Мы всячески поддерживаем использование библиотеки арифметических операций над большими числами со встроенной системой верификации на основе вупинга. Этот, казалось бы, сравнительно простой метод позволяет избежать многих потенциальных проблем безопасности. Кроме того, нам ка­ жется, что гораздо проще один раз добавить к библиотеке поддержку ву­ пинга, нежели реализовать отдельные специфические системы верификации

вкаждом из приложений, которые будут использовать эту библиотеку.

16.1.2Проверка вычислений алгоритма DH

Если у вас нет библиотеки с поддержкой вупинга, вам придется работать без нее. Протокол DH, описанный в одной из предыдущих глав, сам по себе содержит целый ряд проверок. В частности, проверку того, что результат не должен быть равен единице и что порядок результата должен быть ра­ вен q. К сожалению, эти проверки осуществляются не тем участником, кото­ рый выполняет вычисления, а тем, кто получает результат этих вычислений. В общем случае мы не хотим отсылать какие-либо ошибочные результаты, так как они могут оказаться полезными для злоумышленника, но в данной ситуации особого вреда это не нанесет. Если результат ошибочен, протокол так или иначе перестанет работать, поэтому ошибку в любом случае заметят. Безопасность протокола нарушается только тогда, когда библиотека арифме­

310	Глава 16. Проблемы реализации. Часть II

тических операций вместо дх возвращает х, но ошибку такого типа без труда обнаружит любое нормальное тестирование.

При необходимости можно использовать алгоритм DH с библиотекой, ко­ торая не поддерживает вупинг. Тот тип весьма редких арифметических оши­ бок, который нас беспокоит, вряд ли позволит злоумышленнику узнать значе­ ние х при вычислении дх. Любая другая ошибка выглядит вполне безобидной, особенно вследствие того, что в алгоритме DH нет долгосрочных секретных данных. Тем не менее там, где это возможно, мы все-таки предпочитаем ис­ пользовать библиотеку с поддержкой вупинга — просто чтобы чувствовать себя в безопасности.

16.1.3Проверка шифрования RSA

Алгоритм шифрования RSA более уязвим для нападения злоумышленни­ ков, а потому требует дополнительных проверок. Если что-нибудь пойдет не так, злоумышленник может узнать секретные данные, которые вы пытались зашифровать, или даже ваш секретный ключ.

Если реализовать верификацию на основе вупинга невозможно, мы можем порекомендовать вам еще два метода проверки правильности шифрования RSA. Предположим, что реальный алгоритм шифрования RSA вычисляет с = ш5mod п, где т — это сообщение, а с — шифрованный текст. Чтобы проверить правильность этой операции, мы могли бы подсчитать с1/5 mod п и сравнить его с т. Недостаток этого подхода состоит в крайне медленной скорости верификации (что особенно неудобно для такого быстрого алгорит­ ма, как этот). Кроме того, данный метод требует знания закрытого ключа, который при шифровании с помощью RSA обычно недоступен.

Пожалуй, более удачное решение — выбор случайного значения z и про­ верка того, что с •z5 = ( т •z)5 mod п. Здесь нам придется выполнить три операции возведения в пятую степень: вычислить с = т5 и z5, а также убе­ диться, что (mz)5 совпадает с с •z5. Такая верификация с высокой степе­ нью вероятности позволит перехватить случайные арифметические ошибки. Выбирая случайное значение z, мы лишаем злоумышленника возможности инициировать ошибки с нужным отклонением. В наших системах алгоритм шифрования RSA применяется только для шифрования случайных значе­ ний, поэтому злоумышленнику вообще не удастся никоим образом повлиять на результат верификации.

16.1.4 Проверка цифровых подписей R SA

Проверять цифровые подписи RSA очень просто. Пользователю, подпи­ савшему сообщение, достаточно лишь запустить стандартный алгоритм вери­

16.2 Быстрое умножение

311

фикации подписи. Последний выполняется относительно быстро и с большой долей вероятности позволяет перехватить арифметические ошибки. Каждая процедура вычисления подписи RSA должна верифицировать результат, про­ веряя только что сгенерированную подпись. Исключений из этого прави­ ла нет.

16.1.5Заключение

Попытаемся немного прояснить ситуацию. Проверки, о которых шла речь в предыдущих разделах, должны выполняться в дополнение к обычному те­ стированию библиотек арифметических операций над большими числами. Они ни в коей мере не заменяют обычного тестирования, которому должен подвергнуться любой элемент программного обеспечения, особенно если речь идет о системе обеспечения безопасности.

Если хотя бы одна из перечисленных выше проверок окончится неудачей, это означает, что программное обеспечение содержит ошибку. Возможных вариантов действия здесь немного. Продолжать работу небезопасно; мы ведь не знаем, что именно привело к возникновению ошибки. Пожалуй, единствен­ ное, что стоит сделать в подобной ситуации, —это записать ошибку в журнал

иаварийно завершить работу программы.

16.2Быстрое умножение

Существует множество способов ускорить умножение по модулю таким образом, чтобы системе не приходилось выполнять полное умножение и по­ следующее деление “в столбик”. В протоколах с большим количеством умно­ жений широко используется метод Монтгомери [67]. К сожалению, статья самого Монтгомери слишком трудна для понимания. Более понятное описа­ ние этого метода содержится в [25].

В основе метода Монтгомери лежит способ вычисления (х mod п), где число х намного больше п. Классический метод деления “в столбик” подра­ зумевает вычитание из числа х подходящих чисел, кратных п. Идея Монтго­ мери гораздо проще: многократное деление х на 2. Если число х четное, мы делим х на 2, сдвигая его двоичное представление на один бит вправо. Если же х нечетное, мы вначале прибавляем к нему п (что, разумеется, не изме­ няет значения х по модулю п), а затем делим полученный четный результат на 2. (Данный метод работает только для нечетных п. Напомним, что в на­ ших системах всегда применяются нечетные п. Впрочем, данный метод легко обобщить и на четные значения п.) Если длина п равна к бит, а значение х не превышает (n — I)2, мы выполним к делений на 2. Полученный резуль­

312	Глава 16. Проблемы реализации. Часть II

тат всегда будет находиться в диапазоне 0, . .. , 2п — 1, что уже совсем близко

кискомому значению по модулю п.

Ивсе же что-то здесь не так! Ведь мы все время делили на 2, поэтому ответ неверен. В действительности метод Монтгомери дает нам не (х mod п),

ах/2к mod п для некоторого к. Данная операция выполняется намного быст­ рее, но “в нагрузку” мы получаем дополнительный множитель 2~к. Существу­ ет несколько соображений относительно того, как убрать этот дополнитель­ ный множитель.

Одна из самых неудачных идей — просто переопределить протокол, что­ бы включить в вычисления дополнительный множитель 2~к. Данный при­ ем никуда не годится, так как приводит к смешению уровней. Он изменяет спецификацию криптографического протокола, адаптируя ее к конкретному методу реализации. Возможно, в будущем вам захочется реализовать этот же протокол на другой платформе без применения метода Монтгомери. (На­ пример, это может быть медленная платформа, имеющая сопроцессор для работы с большими числами, который выполняет умножение по модулю на­ прямую.) В этом случае наличие в спецификации протокола множителей 2-fc будет только мешать.

Стандартный прием, к которому прибегают в данной ситуации, — изме­ нить представление чисел. Число х будет внутренне представлено как х ■2к. Если требуется перемножить х и у, мы применим умножение Монтгомери к соответствующим внутренним представлениям. Перемножив эти числа, мы получим х •2к ■у •2к, но вследствие взятия числа х •2к•у •2к по модулю п у нас появится множитель 2~к. Конечный результат операции умножения будет выглядеть как х •у •2fc, а это и есть внутреннее представление произведения ху. Таким образом, дополнительные расходы, связанные с применением ме­ тода Монтгомери, включают в себя стоимость преобразования входных дан­ ных во внутреннее представление (умножение на 2к) и стоимость обратного преобразования выходных данных для получения фактического результата (деление на 2к). Первое преобразование может быть выполнено путем умно­ жения Монтгомери числа х на (22к mod п). Второе преобразование, в свою очередь, можно выполнить, сдвинув число х •у •2к еще на к бит вправо, по­ скольку это будет эквивалентно делению на 2к. Конечный результат метода Монтгомери не обязательно будет меньше п, однако в большинстве случаев можно показать, что он будет меньше 2п —1. В подобных случаях для полу­ чения корректного результата достаточно лишь небольшой проверки и (при необходимости) одного вычитания числа п.

На практике взятие числа по модулю методом Монтгомери выполняет­ ся не по битам, а по словам. Предположим, что процессор оперирует w- битовыми словами. Для заданного числа х необходимо найти такое малое z, чтобы наименее значимое слово числа х + zn равнялось нулю. Можно пока­