В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 16. Проблемы реализации. Часть II В криптографии наши цели отличаются от тех, что преследуются боль- шинством разработчиков. Мы считаем уровень сбоя в 2 − 64 (примерно один к 18 миллионам триллионов) недопустимым, в то время как другие разра- ботчики вполне бы довольствовались и этим. Многие программисты считают уровень сбоя в 2 − 20 (примерно один к миллиону) вполне приемлемым, а то и вовсе замечательным. Нам же, как криптографам, нужно предъявлять бо- лее строгие требования к системе, поскольку мы работаем в противоборству- ющем окружении. Большинство блочных шифров и функций хэширования достаточно легко поддаются тестированию 1 . Лишь некоторые недочеты реализации приводят к появлению ошибок, которые трудно обнаружить путем тестирования. Ес- ли вы ошибетесь в реализации S-матрицы шифра AES, ошибка всплывет уже после нескольких сеансов шифрования. Простое тестирование с помощью по- следовательности случайных тестов исследует все пути данных в блочном шифре или функции хэширования и быстро обнаружит любые системати- ческие ошибки. Путь кода, который выбирает программа при выполнении шифрования или хэширования, не зависит или практически не зависит от самих данных. Любой приличный набор тестов для симметричной функции шифрования исследует все возможные потоки управления, существующие в реализации. С арифметикой больших чисел все обстоит иначе. Здесь в большинстве реализаций путь кода, который выбирает программа при выполнении опера- ции, зависит от самих данных. Например, код, осуществляющий последний перенос при сложении, используется крайне редко. Функции деления часто содержат фрагмент кода, который применяется только один раз на каждые 2 32 или даже 2 64 операции деления. Ошибка в этой части кода не будет об- наружена с помощью случайного тестирования. Ситуация становится еще хуже при использовании процессоров с б´ольшим количеством разрядов. Для 32-разрядного процессора мы в принципе можем выполнить 2 40 случайных теста и ожидать, что каждое 32-битовое слово встретится в каждой части пути данных, но этот способ тестирования совершенно неприемлем для 64- разрядных процессоров. Из всего изложенного следует, что проводить тестирование арифметиче- ских операций над большими числами следует крайне осторожно. Разработ- чику нужно убедиться в том, что в процессе тестирования программа дей- ствительно пройдет все существующие пути кода. Для этого необходимо тща- тельно подбирать тестовые векторы — занятие, которое требует определенной точности и внимания. Вам понадобится не только использовать все существу- 1 В качестве наиболее примечательных исключений можно назвать шифры IDEA и MARS, в которых используется отдельный код для тестирования частных случаев. 16.1. Арифметика больших чисел 303 ющие пути кода, но и перебрать все граничные условия. Например, если у нас есть тест для a < b , мы должны протестировать этот же фрагмент кода для a = b − 1 , a = b и a = b + 1 (разумеется, если эти условия вообще могут быть достигнуты). И без того нелегкое положение еще более усложняется с появлением опти- мизации. Поскольку упомянутые выше функции создают узкое место в произ- водительности системы, их всячески пытаются оптимизировать. Это, в свою очередь, приводит к появлению множества частных случаев, путей кода и т.п., что еще более затрудняет тестирование. Простая арифметическая ошибка может иметь поистине катастрофиче- ские последствия для безопасности системы. Вот небольшой пример. Пусть в код, вычисляющий значение цифровой подписи RSA, вкралась небольшая ошибка, которая дает неверный результат при возведении в степень по моду- лю p , но верный при возведении в степень по модулю q . (Предположим также, что для ускорения этой процедуры применяются CRT-представления.) Под- писывая свои сообщения, пользователь А вместо верной цифровой подписи σ отсылает подпись σ + kq , где k — некоторое число. (Чтобы результат, полу- ченный пользователем А, был верным по модулю q , но неверным по модулю p , он должен иметь вид σ + kq .) Злоумышленник знает σ 3 mod n — число, из которого пользователь А извлекает корень третьей степени и которое зависит только от сообщения. Но разность ( σ + kq ) 3 − σ 3 кратна q . Найдя наибольший общий делитель этой разности и числа n , злоумышленник узнает q и таким образом сможет разложить число n на простые множители. При одной мысли об этом нас охватывает ужас! Вы спросите, что же в таком случае делать? Во-первых, не пытайтесь реализовать собственную библиотеку для работы с большими числами. Вос- пользуйтесь какой-нибудь существующей библиотекой. Если вам некуда де- вать свое время, лучше потратьте его на то, чтобы разобраться в существу- ющей библиотеке и хорошенько ее протестировать. Во-вторых, разработайте действительно хорошие тесты для своей библиотеки. Убедитесь, что вы про- тестировали все возможные пути кода. В-третьих, вставьте дополнительные тесты в само приложение. Для этого можно воспользоваться несколькими методами. 16.1.1 Вупинг Метод, описанный в этом разделе, имеет довольно непривычное назва- ние — вупинг (wooping) . Во время одного жаркого спора между Дэвидом Шомом (David Chaum) и Юрьеном Босом (Jurjen Bos) срочно понадобилось придумать имя для специальной верификационной переменной. В пылу деба- |