Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С
 Скачать 3.25 Mb.
|
|
Манфилд Рихтер (Manfield Richter) разработал генератор случайных чисел на базе температурного шума полу- проводникового диода [1309]. Предположительно случайны временные интервалы между последовательными 2e4 излучениями света рас- падающегося атома ртути. Используйте. А лучше найдите полупроводниковую фирму, которая изготавливает микросхемы генераторов случайных чисел, их достаточно много . Существует также генератор случайных чисел, использующий диск компьютера [439]. Он измеряет время, нужное для чтения блока диска, и использует изменения этого времени в качестве источника случайных чисел . Данные фильтруются, чтобы удалить структуру, вызванную квантованием, затем к векторам чисел применяется быстрое преобразование Фурье. Это устраняет смещение и корреляцию. Наконец, в качестве случайных битов используются спектральные углы для частот в диапазоне (0, ?), нормализованные на единичный интервал . Большая часть изменений скорости вращения диска вызвана турбулентностью воздуха, которая и является и с- точником случайности в системе. Хотя надо учесть следующее. Если вы выдаете на выход слишком много б и- тов, то вы используете в качестве генератора случайных чисел быстрое преобразование Фурье и рискуете пол у- чить определенную предсказуемость. И лучше снова и снова читать один и тот же дисковый блок, чтобы вам не пришлось фильтровать структуру, источником которой является планировщик диска . Реализация такой системы позволяла получать около 100 битов в минуту [439]. Использование таймера компьютера Если вам нужен один случайный бит (или даже несколько), воспользуйтесь младшим значащим битом л ю- бого регистра таймера. В системе UNIX он может быть не слишком случайным из-за различной возможной синхронизации, но на некоторых персональных компьютерах это работает . Не стоит извлекать таким образом слишком много битов . Выполнение много раз одной и той же процедуры последовательно может легко сместить биты, генерированные этим способом . Например, если выполнение каж- дой процедуры генерации бита занимает четное число тиков таймера, на выходе вашего генератора будет бе с- конечная последовательность одинаковых битов . Если выполнение каждой процедуры генерации бита занимает нечетное число тиков таймера, на выходе вашего генератора будет бесконечная последовательность череду ю- щихся битов. Даже если зависимость не так очевидна, получающийся битовый поток будет далек от случайного . Один генератор случайных чисел работает следующим образом [918]: Наш генератор действительно случайных чисел . . . работает, устанавливая будильник и затем быстро инкрементируя р е- гистр счетчика процессора до тех пор, пока не произойдет прерывание . Далее выполняется XOR содержимого регистра и со- держимого байта выходного буфера (данные регистра усекаются до 8 битов). После того, как будет заполнен каждый байт выходного буфера, буфер подвергается дальнейшей обработке циклическим сдвигом каждого символа вправо на два бита . Это приводит к эффекту перемещения наиболее активных (и случайных) младших значащих битов в старшие значащие п о- зиции. Затем весь процесс повторяется три раза . Наконец после прерываний два самых случайных бита регистра счетчика п о- влияют на каждый символ буфера. То есть происходит 4n прерываний, где n - число нужных случайных битов. Этот метод очень чувствителен к случайности системных прерываний и квантованности таймера . При тести- ровании на реальных UNIX-машинах результат был очень неплох. Измерение скрытого состояния клавиатуры Процесс печатания и случаен, и неслучаен . Он достаточно неслучаен, чтобы его можно было использовать для идентификации печатающего человека, но он достаточно случаен, чтобы его можно было использовать для генерации случайных битов. Измерьте время между последовательными нажатиями клавиш, затем воспользу й- тесь младшими значащими битами этих измерений . Эти биты оказываются достаточно случайными . Этот метод не работает на UNIX-терминалах, так как нажатия клавиш прежде, чем они будут переданы вашей программе, проходят через фильтры и другие механизмы, но это будет работать на большинстве персональных компьют е- ров. В идеале вы должны по каждому нажатию клавиши генерировать только один бит . Использование большего количества битов может сместить результаты в зависимости от навыков машинистки . Однако этот метод имеет ряд ограничений. Хотя нетрудно посадить за клавиатуру человека, печатающего со скоростью 100 слов в минуту или около того, если есть время для генерации ключа, глупо просить машинистку печатать текст из 100000 слов, чтобы использовать результат работы генератора в качестве одноразового блокнота . Смещения и корреляции Главной проблемой подобных систем являются возможные закономерности в генерируемой последовател ь- ности. Используемые физические процессы могут быть случайны, но между физическим процессом и компь ю- тером находятся различные измерительные инструменты . Эти инструменты могут легко привести к появлению проблем. Способом устранить смещение, или отклонение, является XOR нескольких битов друг с другом. Если слу- чайный бит смещен к 0 на величину e, то вероятность 0 можно записать как: P(0) = 0.5 + e XOR двух из таких битов дает: P(0) = (0.5 + e) 2 + (0.5 - e) 2 = 0.5 + 2e 2 Те же вычисления для XOR 4 битов дают: P(0) = 0.5 + 8e 4 XOR m битов экспоненциально сходится к равной вероятности 0 и 1 . Если известно максимальное смещение, которое допустимо в вашем приложении, вы можете вычислить, сколько битов вам нужно объединить с пом о- щью XOR, чтобы уменьшить смещение до этого значения . Еще лучше рассматривать биты попарно . Если 2 бита одинаковы отбросьте их и взгляните на следующую пару. Если 2 бита различны, используйте первый бит в качестве выхода генератора . Это полностью устраняет смещение. Другие методы уменьшения смещения используют распределение переходов сжатие и быстрое пр е- образование Фурье [511]. Потенциальной проблемой обоих методов является то, что при наличии корреляции между соседними би- тами эти методы увеличивают смещение . Одним из способов исправить это является использование нескольких случайных источников. Возьмите четыре случайных источника и выполните XOR битов друг с другом или возьмите два случайных источника и взгляните на их биты попарно . Например, возьмите радиоактивный источник и присоедините счетчик Гейгера к вашему компьютеру . Возь- мите пару шумящих диодов и записывайте в качестве события каждое превышение определенного значения . Измерьте атмосферный шум. Извлеките из каждого источника случайный бит и выполните их XOR друг с дру- гом, получая случайный бит. Возможности бесконечны. Одно то, что генератор случайных чисел смещен не обязательно означает его бесполезность . Это только оз- начает, что он менее безопасен. Например, рассмотрим проблему Алисы, генерирующей 168-битовый ключ для тройного DES. A все, что у нее есть, - это генератор случайных битов со смещением к 0 : с вероятностью 55 про- центов он выдает нули и с вероятностью 45 процентов - единицы . Это означает, что энтропия на бит ключа с о- ставит только 0.99277 (для идеального генератора она равна 1). Мэллори, пытаясь раскрыть ключ, может опти- мизировать выполняемое вскрытие грубой силой, проверяя сначала наиболее вероятные ключи (000 . . . 0) и двигаясь к наименее вероятному ключу (111 . . . 1). Из-за смещения Мэллори может ожидать, что ему удастся обнаружить ключ за 2 109 попыток. При отсутствии смещения Мэллори потребуется 2 111 попыток. Полученный ключ менее безопасен, но это практически неощутимо . Извлеченная случайность В общем случае лучший способ генерировать случайные числа - найти большое количество кажущихся сл у- чайными событий и извлечь случайность из них . Эта случайность может храниться в накопителе и извлекаться при необходимости. .Однонаправленные хэш-функции прекрасно подходят для этого. Они быстры, поэтому вы можете пропускать биты через них, не слишком заботясь о производительности или действительной случайн о- сти каждого наблюдения. Попробуйте хэшировать почти все, что вам кажется хоть чуть-чуть случайным. Н а- пример: — Копия каждого нажатия на клавиши — Команды мыши — Номер сектора, время дня и задержка поиска для каждой дисковой операции — Действительное положение мыши — Номер текущей строки развертки монитора — Содержание действительно выводимого на экран изображения — Содержание FAT-таблиц, таблиц ядра, и т.д. — Времена доступа/изменения /dev/tty — Загрузка процессора — Времена поступления сетевых пакетов — Выход микрофона — /dev/audio без присоединенного микрофона Если ваша система использует различные кристаллы-осцилляторы для своего процессора и часов , попытай- тесь считывать время дня в плотном цикле . В некоторых (но не всех) системах это приведет к случайным коле- баниям фазы между двумя осцилляторами . Так как случайность в этих событиях определяется синхронизацией осцилляторов, используйте часы с как можно меньшим квантом времени. В стандартном PC используется микросхема таймера Intel 8254 (или эквива- лентная), работающая на тактовой частоте 1.1931818 МГц, поэтому непосредственное считывание регистра счетчика даст разрешение в 838 наносекунд. Чтобы избежать смещения результатов, не используйте в качестве источника событий прерывание таймера . Вот как выглядит этот процесс на языке C с MD5 (см. раздел 18.5) в качестве хэш-функции: char Randpool[16]; /* Часто вызывается для широкого множества случайных или полуслучайных системных событий для to churn the randomness pool . Точный формат и длина randevent не имеет значения, пока его содержание является в некоторой мере чем-то непредсказуемым. */ void churnrand(char *randevent,unsigned lnt randlen) { MD5_CTX md5; MD5Init(&md5); MD5Update(&md5, Randpool , sizeof(Randpool)); MD5Update(&md5 , randevent , randlen ); MD5Final(Randpool,&md5); } После достаточных вызовов churnrand() накопления достаточной случайности в Randpool, можно генериро- вать из этого случайные биты. MD5 снова становится полезной, в этот раз в качестве генератора псевдослуча й- ного байтового потока, работающего в режиме счетчика . long Randcnt; void genrand(char *buf,unsigned int buflen) { MD5_CTX md5; char tmp[16]; unsigned int n; while(buflen != 0) { /* Пул хэшируется счетчиком */ MD5Init(&md5); MD5Update(&md5, Randpool, sizeof(Randpool)); MD5Update(&md5,(unsigned char *)&Randcnt,sizeof(Randcnt)); MD5Final(tmp,&md5); Randcnt++; /* Инкрементируем счетчик */ /*Копируем 16 или запрошенное число байтов, если оно меньше 16, в буфер пользователя*/ n = (buflen < 16) ? buflen : 16; memcpy(buf, tmp, n); buf += n ; buflen -= n; } } По многим причинам хэш-функция имеет ключевое значение . Во первых она обеспечивает простой способ генерировать произвольное количество псевдослучайных данных , не вызывая всякий раз churnrand(). На деле, когда запас в накопителе подходит к концу, система постепенно переходит от совершенной случайности к пра к- тической. В этом случае становится теоретически возможным использовать результат вызова genrand() для определения предыдущего или последующего результата . Но для этого потребуется инвертировать MD5, что вычислительно невозможно. Это важно, так как процедуре неизвестно, что делается потом со случайными данными, которые она возвр а- щает. Один вызов процедуры может генерировать случайное число для протокола, которое посылается в явном виде, возможно в ответ на прямой запрос взломщика . А следующий вызов может генерировать секретный ключ для совсем другого сеанса связи, в суть которого и хочет проникнуть взломщик . Очевидна важность того, чтобы взломщик не смог получить секретный ключ, используя подобную схему действий . Но остается одна проблема. Прежде, чем в первый раз будет вызвана genrand() в массиве Randpool[] должно быть накоплено достаточно случайных данных . Если система какое-то время работала с локальным пользовате- лем, что-то печатающим на клавиатуре, то проблем нет . Но как насчет независимой системы, которая перегр у- жается автоматически, не обращая внимания ни на какие данные клавиатуры или мыши ? Но есть одна трудность. В качестве частичного решения можно потребовать, чтобы после самой первой з а- грузки оператор какое-то время поработал на клавиатуре и создал на диске стартовый файл перед выгрузкой операционной системы, чтобы в ходе перезагрузок использовались случайные данные, переданные в Randseed[]. Но не сохраняйте непосредственно сам Randseed[]. Взломщик, которому удастся заполучить этот файл, сможет определить все результаты genrand() после последнего обращения к churnrand() прежде, чем этот файл будет создан. Решением этой проблемы является хэширование массива Randseed[] перед его сохранением, может даже вы- зовом genrandO. При перезагрузке системы вы считываете данные из стартового файла, передаете их churnrand(), а затем немедленно стираете их. К сожалению это не устраняет угрозы того, что злоумышленник добудет файл между перезагрузками и использует его для предсказания будущих значений функции genrand(). Я не вижу иного решения этой проблемы кроме, как подождать накопления достаточного количества случайных событий, случившихся после перезагрузки, прежде, чем позволить genrand() выдавать результаты. Глава 18 Однонаправленные хэш-функции 18.1 Основы Однонаправленная функция H(M) применяется к сообщению произвольной длины M и возвращает значение фиксированной длины h. h = H(M), где h имеет длину m Многие функции позволяют вычислять значение фиксированной длины по входным данным произвольной длины, но у однонаправленных хэш-функций есть дополнительные свойства, делающие их однонаправленными [1065]: Зная M, легко вычислить h. Зная H, трудно определить M, для которого H(M)=h. Зная M, трудно определить другое сообщение, M', для которого H(M)= H(M'). Если бы Мэллори умел делать трудные вещи, он смог бы разрушить безопасность любого протокола, и с- пользующего однонаправленную хэш-функцию . Смысл однонаправленных хэш-функций и состоит в обеспеч е- нии для M уникального идентификатора ("отпечатка пальца") . Если Алиса подписала M с помощью алгоритма цифровой подписи на базе H(M), а Боб может создать M', другое сообщение, отличное от M, для которого H(M)= H(M'), то Боб сможет утверждать, что Алиса подписала M'. В некоторых приложениях однонаправленности недостаточно, необходимо выполнение другого требования, называемого устойчивостью к столкновениям. Должно быть трудно найти два случайных сообщения, M и M', для которых H(M)= H(M'). Помните вскрытие методом дня рождения из раздела 7.4? Оно основано не на поиске другого сообщения M', для которого H(M)= H(M'), а на поиске двух случайных сообщений, M и M', для которых H(M)= H(M'). Следующий протокол, впервые описанный Гидеоном Ювалом ( Gideon Yuval) [1635], показывает, как, если предыдущее требование не выполняется, Алиса может использовать вскрытие методом дня рождения для обм а- на Боба. (1) Алиса готовит две версии контракта: одну, выгодную для Боба, и другую, приводящую его к банкротству (2) Алиса вносит несколько незначительных изменений в каждый документ и вычисляет хэш-функции . (Этими изменениями могут быть действия, подобные следующим : замена ПРОБЕЛА комбинацией ПРО- БЕЛ-ЗАБОЙ-ПРОБЕЛ, вставка одного-двух пробелов перед возвратом каретки, и т.д. Делая или не делая по одному изменению в каждой из 32 строк, Алиса может легко получить 2 32 различных документов.) (3) Алиса сравнивает хэш-значения для каждого изменения в каждом из двух документов , разыскивая пару, для которой эти значения совпадают. (Если выходом хэш-функции является всего лишь 64-разрядное зн а- чение, Алиса, как правило, сможет найти совпадающую пару сравнив 2 32 версий каждого документа.) Она восстанавливает два документа, дающих одинаковое хэш-значение . (4) Алиса получает подписанную Бобом выгодную для него версию контракта, используя протокол, в котором он подписывает только хэш-значение. (5) Спустя некоторое время Алиса подменяет контракт, подписанный Бобом, другим, который он не подпис ы- вал. Теперь она может убедить арбитра в том, что Боб подписал другой контракт . Это заметная проблема. (Одним из советов является внесение косметических исправлений в подписываемый документ.) При возможности успешного вскрытия методом дня рождения, могут применяться и другие способы вскр ы- тия. Например, противник может посылать системе автоматического контроля (может быть спутниковой) слу- чайные строки сообщений со случайными строками подписей . В конце концов подпись под одним из этих сл у- чайных сообщений окажется правильной . Враг не сможет узнать, к чему приведет эта команда, но, если его единственной целью является вмешательство в работу спутника, он своего добьется . Длины однонаправленных хэш-функций 64-битовые хэш-функции слишком малы, чтобы противостоять вскрытию методом дня рождения . Более практичны однонаправленные хэш-функции, выдающие 128-битовые хэш-значения . При этом, чтобы найти два документа с одинаковыми хэш-значениями, для вскрытия методом дня рождения придется хэшировать 2 64 слу- чайных документов, что, впрочем, недостаточно, если нужна длительная безопасность . NIST в своем Стандарте безопасного хэширования (Secure Hash Standard, SHS), использует 160-битовое хэш-значение. Это еще сильнее усложняет вскрытие методом дня рождения, для которого понадобится 2 80 хэширований. Для удлинения хэн-значений, выдаваемых конкретной хэш-функцией, был предложен следующий метод . (1) Для сообщения с помощью одной из упомянутых в этой книге однонаправленных хэш-функций генерир у- ется хэш-значение. (2) Хэш значение добавляется к сообщению. (3) Генерируется хэш-значение объединения сообщения и хэш-значения этапа (1) . (4) Создается большее хэш-значение, состоящее из объединения хэш-значения этапа (1) и хэш-значения этапа (3). (5) Этапы (1)-(4) повторяются нужное количество раз для обеспечения требуемой длины хэш-значения . Хотя никогда не была доказана безопасность или небезопасность этого метода, уряд людей этот метод выз ы- вает определенные сомнения [1262,859]. Обзор однонаправленных хэш-функций |