Уменьшенные пространства ключей

DES использует 56-битовый ключ с битами. Любая правильно заданная 56-битовая строка может быть кл ю-чом, существует 2⁵⁶ (10¹⁶) возможных ключей. Norton Discreet for MS-DOS (версии 8.0 и более ранние) разре­шает пользоваться только ключам ASCII, делая старший бит каждого байта нолем. Программа также преобр а-зует символы нижнего регистра в верхний регистр (так что пятый бит каждого байта всегда противоположен шестому бита) и игнорирует бит младшего разряда каждого байта, что приводит к пространству в 2 ⁴⁰ возмож­ных ключей. Эти ущербные процедуры генерации ключей сделали свою реализацию DES в десять тысяч раз проще для вскрытия.

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

Могут быть использованы для вскрытия грубой силой любые специализированные аппаратные и параллел ь-

ные реализации. При проверке миллиона ключей в секунду (одной машиной или несколькими параллельно) физически возможно расколоть ключи из символов нижнего регистра и ключи из цифр и символов нижнего регистра длиной до 8 байтов, алфавитно-цифровые ключи - длиной до 7 байтов, ключи из печатаемых символов и ASCII-символов - длиной до 6 байтов, в ключи из 8-битовых ASCII-символов - длиной до 5 байтов.

Табл. 8-1. Количество возможных ключей в различных пространствах ключей

	4 байта	5 байтов	6 байтов	7 байтов	8 байтов
Строчные буквы (26)		1.2*107	3.1*108	8.0*109	2.1*10"
Строчные буквы и цифры (36)		6.0П07	2.2*109	7.8*1010	2.8*1012
Алфавитные и цифровые символы	1.5*107	9.2*108	5.7*1010	3.5*1012	2.2*1014
(62)
Печатаемые символы (95)	8.1П07	7.7*109	7.4*10п	7.0*1013	6.6*1015
СИМВОЛЫ ASCII (128)	2.7*108	3.4*1010	4.4*1012	5.6*1014	7.2*1016
8-битовые ascii символы (256)	4.3П09	1.1*1012	2.8*1014	7.2*1016	1.8*1019

Табл. 8-2. Время исчерпывающего поиска различных пространства ключей (при одном миллионе проверок в е-

кунду)

	4 байта	5 байтов	6 байтов	7 байтов	8 байтов
Строчные буквы (26)	0.5 секунды	12 секунд	5 минут	2.2 часа	2.4 дня
Строчные буквы и цифры (36)	1.7 секунды	1 минута	36 минут	22 часа	33 дня
Алфавитные и цифровые символы	15 секунд	15 минут	16 часов	41 день	6.9 года
(62)
Печатаемые символы (95)	1.4 минуты	2.1 часа	8.5 дня	2.2 года	210 лет
СИМВОЛЫ ASCII (128)	4.5 минуты	9.5 часа	51 день	18 лет	2300 лет
8-битовые ascii символы (256)	1.2 часа	13 дней	8.9 года	2300 лет	580000 лет

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

Обедненный выбор ключей

Когда люди сами выбирают ключи, они выбирают ущербные ключи. Они с большей вероятностью выберут "Barney", чем "*9 (hH/A". Это не всегда происходит из-за плохой практики, просто "Barney" легче запомнить чем "*9 (hH/A". Самый безопасный алгоритм в мире не сильно поможет, если пользователи по привычке выб и-рают имена своих жен (мужей) для ключей или пишут свои ключи на небольших листочках в бумажниках. И н-теллектуальное вскрытие грубой силой не перебирает все возможные ключи в числовом порядке, но пробует сначала очевидные ключи.

Это называется вскрытием со словарем, потому что нападющий использует словарь общих ключей. Дэн и-ел Кляйн (Daniel Klein) смог расколоть 40 процентов паролей на среднем компьютере, используя этот способ вскрытия [847, 848]. Нет, он не перебирал один пароль за другим, пытаясь войти в систему. Он скопировал з а-шифрованный файл паролей и предпринял вскрытие автономно. Вот, что он пробовал:

1. В качестве возможного пароля имя пользователя, инициалы, имя бюджета и другую связанную с ч е-ловеком информацию. В целом, на основе такой информации пробовалось до 130 различных паролей. Вот некоторые из паролей, проверявшихся для имени бюджета klone и пользователя "Daniel V. Klein": klone, kloneO, klonel, klonel23, dvk, dvkdvk, dklein, Dklein, leinad, nielk, dvklein, danielk, DvkkvD, DANIEL-KLEIN, (klone), KleinD, и так далее.

2. Слова из различных баз данных. Использовались списки мужских и женских имен (всего около 16000), названия мест (включая изменения, поэтому рассматривались и "spain", " Spanish", и "Spaniard"), имена известных людей, мультфильмы и мультипликационные герои, заголовки, герои и места из фильмов и научной фантастики, мифические существа (добытые из Bullfinch's Mythology и

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

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

4. Различные варианты преобразования к верхнему регистру слов пункта 2, не рассматривавшихся в пункте 3. Сюда вошло преобразование к верхнему регистру одиночных символов (так, чтобы "michael" был также проверен как "mIchael", "miChael", "micHael", "michAel", и т.д.), преобразование к верхнему регистру пары символов ("Michael", "MiChael", "MicHael",..., "mIChael", "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⁵⁶, так что вероятность получить один из этих ключей невероятно мала. Заявлялось, что криптоаналитик не будет знать о том, что используется слабый ключ, и, следовательно, не см о-жет получить никакой выгоды из их случайного использования. Также заявлялось, что информацию криптоан а-литику дает совсем не использование слабых ключей. Однако, проверка немногих слабых ключей настолько проста, что кажется глупым пренебречь ею.

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

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

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

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