словарей мифических животных), спорт (включая названия команд, прозвища и специальные терм и-ны), числа (записанные как цифрами - 2001", так и буквами " twelve), строки символов и чисел ("a", "aa", "aaa", "aaaa" и т.д.), китайские слоги (из Piny in Romanization of Chinese, международного стандарта письма по китайски на англоязычной клавиатуре), Библия короля Джеймса; биологические те р-мины, разговорные и вульгарные выражения (типа "fuckyou", "ibmsux" и "deadhead"), стандарты кл авиатуры (типа "qwerty", "asdf и "zxcvbn"), сокращения (типа "roygbiv" - первые буквы названий цв е-тов радуги по английски - и "ooottafagvah" - мнемоническая схема для запоминания 12 черепных не рвов), имена компьютеров (полученные из /etc/hosts), герои, пьесы и места действия у Шекспира, с а-мые распространенные слова языка Идиш, названия астероидов, совокупность слов из различных те х-нических статей, опубликованных ранее Кляйном. Итого, для пользователя рассматривалось более чем 60000 отдельных слов (с отбрасыванием дубликатов в различных словарях).

3. Вариации слов из пункта 2. Это включало перевод первого символа в верхний регистр или его замену управляющим символом, перевод всего слова в верхний регистр, инверсию регистра слова (с и без вышеупомянутого изменения регистра первой буквы), замену буквы "o" на цифру "0" (так, чтобы сл о-во "scholar" было также проверено как "sch0lar"), замену буквы " 1" на цифру "1" (так, чтобы слово "scholar" было бы также проверено как " scho1ar") и выполнение аналогичных манипуляций с буквой "z" и цифрой "2", а также с буквой " s" и цифрой "5". Другая проверка состояла из перевода слова во множественное число (независимо от того, было ли слово существительным) с учетом необходимых правил, чтобы "dress" заменилось на "dresses", "house" - на "houses", а "daisy" - на "daisies". Хотя Кляйн не жестко придерживался правил преобразования ко множественному числу, поэтому "datum" стала "datums" (а не "data"), "sphynx" - "sphynxs" (а не "sphynges"). Аналогично, для преобразования слов добавлялись суфиксы " -ed", "-er" и "-ing", подобно "phase" в "phased," "phaser" и "phasing". Эти дополнительные проверки добавили еще 1000000 слов к списку возможных паролей, которые пров е-рялись для каждого пользов ателя.

4. Различные варианты преобразования к верхнему регистру слов пункта 2, не рассматривавшихся в пункте 3. Сюда вошло преобразование к верхнему регистру одиночных символов (так, чтобы "michael" б1л также проверен как "m Ichael", "miChael", "micHael", "michAel", и т.д.), преобразование к верхнему регистру пары символов ("MIchael", "MiChael", "MicHael", "m IChael", "mIcHael", и т.д.), преобразование к верхнему регистру трех символов, и т.д. Изменения одиночного символа доб а-вили к проверяемым примерно еще 400000 слов, а изменения пары символов - 1500000 слов. Измен е-ния трех символов добавляли по крайней мере еще 3000000 слов для каждого пользователя, если для завершения тестирования хватало времени. Проверка изменения четырех, пяти и шести символов была признана непрактичной, так как для их проверки не хватало вычислительных мощностей.

5. 5. Иностранные слова для иностранных пользователей. Специфический тест, который был выполнен, проверял пароли из китайского языка для пользователей с китайскими именами. Для китайских сл о-гов использовался стандарт Pinyin Romanization, слоги объединялись вместе в одно-, двух- и тре х-сложные слова. Так как не было выполнено предварительной проверки слов на значимость, использ о-вался исчерпывающий перебор. Так как в системе Pinyin существует 298 китайских слогов, то имеется 158404 слов с двумя слогами, и немного больше 16000000 слов с тремя слогами. Подобный способ вскрытия мог бы быть легко использован и для английского языка, с учетом правил образования пр о-износимых ничего не значащих слов.

6. Пары слов. Объем такого исчерпывающего теста колеблется. Чтобы упростить тест, из /usr/dict/words использовались только слова длиной три или четыре символа. Даже при этом, число пар слов сост а-вило приблизительно десять миллионов.

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

Случайные ключи

Хорошими ключами являются строки случайных битов, созданные некоторым автоматическим процессом. Если длина ключа составляет 64 бита, то все возможные 64-битовые ключи должны быть равновероятны. Ген е-рируйте биты ключей, пользуясь либо надежным источником случайных чисел (см. раздел 17.14), либо крипт о-графически безопасным генератором псевдослучайных битов (см. главы 16 и 17.) Если такие автоматические процессы недоступны, бросайте монетку или кости.

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

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

Некоторые алгоритмы шифрования имеют слабые ключи - специфические ключи, менее безопасные чем другие ключи. Я советую проверять слабость ключа ключей и, обнаружив ее, генерировать новый. У DES тол ь-ко 16 слабых ключей в пространстве 2 56, так что вероятность получить один из этих ключей невероятно мала. Заявлялось, что криптоаналитик не будет знать о том, что используется слабый ключ, и, следовательно, не см о-жет получить никакой выгоды из их случайного использования. Также заявлялось, что информацию криптоан а-литику дает совсем не использование слабых ключей. Однако, проверка немногих слабых ключей настолько проста, что кажется глупым пренебречь ею.

Генерация ключей для систем криптографии с открытыми ключами тяжелее, потому что часто ключи дол ж-ны обладать определенными математическими свойствами (возможно, они должны быть простыми числами, квадратичным остатком, и т.д.). Методы генерации больших случайных простых чисел рассматриваются в ра з-деле 11.5. Важно помнить, что с точки зрения управления ключами случайные стартовые последовательности для таких генераторов должны быть действительно случайны.

Генерация случайного ключа возможна не всегда. Иногда вам нужно помнить ваш ключ. (Интересно, скол ь-ко времени вам понадобится, чтобы запомнить 25e8 56f2 e8ba c820?). Если вам надо генерировать простой для запоминания ключ, замаскируйте его. Идеалом является то, что легко запомнить, но трудно угадать. Вот н е-сколько предложений:

- Пары слов, разделенные символом пунктуации, например, " turtle*moose" или "zorch!splat"

- Строки букв, являющиеся акронимами длинных фраз, например, "Mein Luftkissenfahrzeug ist voller Aale!" служит для запоминания ключа "MLivA!"

Ключевые фразы

Лучшим решением является использование вместо слова целой фразы и преобразование этой фразы в ключ . Такие фразы называются ключевыми фразами. Методика с названием перемалывание ключа преобразует легко запоминающиеся фразы в случайные ключи . Для преобразования текстовой строки произвольной длины в строку псевдослучайных бит используте однонаправленную хэш-функцию . Например, легко запоминающаяся текстовая строка:

My name is Ozymandias, king of kings. Look on my works, ye mighty, and despair. 1

может "перемолоться" в такой 64-битовый ключ:

e6cl 4398 5ae9 0a9b

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

Если фраза достаточно длинна, то полученный ключ будет случаен . Вопрос о точном смысле выражения "достаточно длинна" остается открытым. Теория информации утверждает, что информационная значимость стандартного английского языка составляет около 1.3 бита на символ (см. раздел 11.1). Для 64-битового ключа достаточной будет ключевая фраза, состоящая примерно из 49 символов, или 10 обычных английских слов. В качестве эмпирического правила используйте пять слов для каждых 4 байтов ключа. Это предложение работает с запасом, ведь в нем не учитываются регистр, пробелы и знаки пунктуации .

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

Выбирая ключевую фразу, используйте что-нибудь уникальное и легко запоминающееся. Не выбирайте фразы из книг - пример с "Ozymandias" в этом смысле плох. Легко доступны и могут быть использованы для вскрытия со словарем и собрание сочинений Шекспира, и диалоги из Звездных войн. Выберите что-нибудь туманное и личное. Не забудьте о пунктуации и преобразовании регистра, если возможно включите числа и неа л-фавитные символы. Плохой или искаженный английский, или даже любой иностранный язык, делает ключевую фразу более устойчивой к вскрытию со словарем . Одним из предложений является использование фразы, которая является "потрясающей ерундой", чем-то таким, что вы вряд ли запомните и вряд ли запишете .

Несмотря на все написанное здесь маскировка не заменяет истинную случайность. Лучшими являются сл у-чайные ключи, которые так тяжело запомнить .

1 Я Озимандиас, царь царей. Вы, сильные мира сего, смотрите на мои труды и трепещите.

Стандарт генерации ключей X9.17

Стандарт ANSI X9.17 определяет способ Генерации ключей (см. 7th) [55]. Он не создает легко запоминающиеся ключи, и больше подходит для генерации сеансовых ключей или псевдослучайных чисел в системе . Для генерации ключей используется криптографический алгоритм DES, но он может быть легко заменен любым другим алгоритмом.

Шифровать

Vi-►ф-у Шифровать

•ф-► Шифровать

Рис. 8-1. Генерация ключей ANSI X9.17

Пусть Ek(X) - это X, зашифрованный DES ключом K, специальным ключом, предусмотренным для генер а-ции секретных ключей. Уд - это секретная 64-битовая стартовая последовательность. T- это метка времени. Для генерации случайного ключа Ri вычислим:

R,= Ek(Ek(T,) © V,)

Для генерации Vi+1, вычислим:

Vi+i= Ek(Ek(T) © R,)

Для превращения Ri в ключ DES, просто удалите каждый восьмой бит. Если вам нужен 64-битовый ключ, используйте ключ без изменения. Если вам нужен 128-битовый ключ, создайте пару ключей и объедините их.

Генерация ключей в министерстве обороны США

Министерство обороны США для генерации случайных ключей рекомендует использовать DES в режиме OFB (см. раздел 9.8) [1144]. Создавайте ключи DES, используя системные вектора прерывания, регистры состояния системы и системные счетчики . Создавайте вектор инициализации, используя системные часы, идент и-фикатор системы, с также дату и время. Для открытого текста используйте 64-битовые величины, созданные кем-то другим, например, 8 символов, введенных системным администратором . Используйте в качестве своего ключа результат.

8.2 Нелинейные пространства ключей

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

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

Получившееся пространство ключей называется нелинейным, потому что ключи не являются одинаково сильными. (Противоположным является линейное, или плоское, пространство ключей.) Простым способом д обиться этого можно, создавая ключ, состоящий из двух частей: непосредственно ключа и некоторой фиксир о-ванной строки, шифрованной этим ключом. Модуль расшифровывает строку, используя ключ. Если результ атом оказывается фиксированная строка, то ключ используется как обычно, если нет, то используется другой, слабый алгоритм. Если алгоритм имеет 128-битовый ключ и 64-битовый размер блока, то длина полного ключа - 192 бита. Таким образом, у алгоритма 2 128 эффективных ключа, но вероятность случайно выбрать правильный составляет один шанс из 264.

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

Это работает только, если используется секретный алгоритм, который враг не может перепроектировать, или если различие в силе ключей достаточно тонко, чтобы враг не смог о нем догадаться. NSA проделывало это с секретными алгоритмами в своих модулях Overtake (см. раздел 25.1). Делали ли они то же самое с Skipjack (см. раздел 13.12)? Неизвестно.