Часть 2 Криптографические методы

Часть 2 Криптографические методы

Глава 7 Длина ключа

7.1 Длина симметричного ключа

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

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

Для выполнения такого вскрытия криптоаналитику требуется кусочек шифротекста и соответствующего о т-крытого текста, вскрытие грубой силой представляет собой вскрытие с известным открытым текстом . Для блоч­ного шифра криптоаналитику понадобится блок шифротекста и соответствующий открытый текст : обычно 64 бита. Заполучить такие кусочки открытого текста и шифротекста легче, чем можно себе представить . Криптоа-налитик может получить каким-то образом копию открытого текста сообщения и перехватить соответствующий шифротекст. Он может знать что-то о формате шифротекста: например, что это файл в формате WordPerfect, или у него есть стандартный заголовок сообщения электронной почты , или файл каталога UNIX, или изображе­ние в формате TIFF, или стандартная запись в базе данных клиентов. Все эти форматы содержат некоторые предопределенные байты. Криптоаналитику для такого вскрытия не нужно много открытого текста .

Рассчитать сложность вскрытия грубой силой нетрудно. Если используется 8-битовый ключ, то существует 2 или 256, возможных ключей. Следовательно, для обнаружения правильного ключа потребуется, самое боль­шее, 256 попыток, с 50-процентной вероятностью найти нужный ключ после половины попыток . Если длина ключа равна 56 битам, то существует 2⁵⁶ возможных ключей. Если компьютер может проверить миллион клю­чей в секунду, поиск нужного ключа займет в среднем 2285 лет. Если используется 64-битовый ключ, то тому же суперкомпьютеру понадобится около 585000 лет, чтобы найти правильный ключ среди 2^м возможных клю­чей. Если длина ключа равна 128 битам поиск ключа займет 10²⁵ лет. Возраст вселенной составляет всего 10¹⁰ лет, поэтому 10²⁵ лет - это большое время. При 2048-битовом ключе миллион компьютеров, работая параллел ь-но и проверяя миллион ключей в секунду, потратят 10⁵⁸⁷ лет в поисках ключа. К этому времени вселенная давно расширится, превратившись в ничто или сожмется.

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

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

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

Оценки времени и стоимости вскрытия грубой силой

Скорость вскрытия грубой силой определяется двумя параметрами : количеством проверяемых ключей и скоростью проверки одного ключа. Большинство… Скорость, с которой может быть проверен каждый ключ, имеет менее важное… В криптологической среде большинство споров по поводу вскрытия грубой силой сконцентрированы вокруг алгоритма DES. В…

Табл. 7-1. Оценки среднего времени для аппаратного вскрытия грубой силой в 1995 году.

Длина ключей в битах

 

Стоимость
$100 К	2 секунды	35 часов	1год	70000 лет	1014лет	1019лет
$1М	0.2 секунды	3.5 часа	37 дней	7000 лет	10" лет	1018лет
$10М	0.02 секунды	21 минута	4 дня	700 лет	1012лет	1017лет
$100 М	2 миллисекунды	2 минуты	9 часов	70 лет	10" лет	1016лет
$1Г	0.2 миллисекунды		1час	7 лет	1010лет	1015лет
$10 Г	0.02. миллисекунды	1 секунда	5.4 минуты	245 дней	10'лет	1014лет
$100 Г	2 микросекунды	0.1 секунды	32 секунд	24 дня	108лет	10" лет
$1 Т	0.2 микросекунды	0.01 секунды	3 секунды	2.4 дня	Ю'лет	1012лет
$10Т	0.02 микросекунды	1 миллисекунда	0.3 секунды	6 часов	106лет	10" лет

Если взломщик очень сильно хочет взломать ключ, все, что ему нужно, это потратить деньги . Следовательно, стоит попытаться определить минимальную "цену" ключа: в пределах какой стоимости сведе­ний можно пользоваться одним ключом прежде, чем его вскрытие станет экономически выгодным ? Крайний случай: если шифрованное сообщение стоит $1.39, то нет финансового смысла устанавливать аппаратуру стои­мостью 10 миллионов долларов для взлома этого ключа. С другой стороны, если стоимость открытого текста -100 миллионов долларов, то дешифрирование этого одиночного сообщения вполне окупит стоимость аппарату­ры взлома. Кроме того, стоимость многих сообщений со временем очень быстро падает.

Программное вскрытие

Реальная угроза программного вскрытия грубой силой страшна не своей неизбежностью, а тем, что такое вскрытие "свободно". Ничего не стоит… Основной угрозой программного вскрытия является слепое везение . Представьте… Использование алгоритма с 64-битовым ключом вместо 56-битового ключа делает это вскрытие в 256 раз сложнее. А…

Нейронные сети

Вирусы

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

Эта особенно коварная идея впервые появилась в [1593]. Взломщик пишет и выпускает на волю компьюте р-ный вирус. Этот вирус не переформатирует жесткий диск, не удаляет файлы, но во время простоя компьютера он работает на криптоаналитической проблемой грубого взлома. Различные исследования показали, что комп ь-

ютер простаивает от 70 до 90 процентов времени, так что у вируса не будет проблем с временем для решения этой задачи. Если он нетребователен и в других отношениях, то его работа даже не будет заметна.

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

Другим, трусливым подходом бал бы вывод на экран следующего сообщения :

В этом компьютере есть серьезная ошибка. Пожалуйста позвоните 1-8001234567 и продиктуйте оператору следующее 64-битовое число:

хххх хххх хххх хххх

Первому, кто сообщит об этой ошибке будет выплачено вознаграждение 100 долларов.

Насколько эффективно такое вскрытие? Пусть типичный зараженный компьютер проверяет тысячу ключей в секунду. Эта скорость намного меньше потенциальных возможностей компьютера, ведь мы полагаем, что он иногда будет делать и другие вещи. Предположим также, что типичный вирус инфицирует 10 миллионов машин. Этот вирус может вскрыть 56-битовый ключ за 83 дня, а 64 битовый - за 58 лет. Вам возможно при­шлось бы подкупить разработчиков антивирусного программного обеспечения, но это уже ваши проблемы . Лю­бое увеличение скорости компьютеров или распространения вируса, конечно, сделало бы это нападение более эффективным.

Китайская лотерея

Если у каждого человека в Китае, будь то мужчина, женщина или ребенок, есть радиоприемник или телев и-зор, то правильное значение 56-битового ключа… Чтобы сделать такое вскрытие возможным на практике, необходимо сделать ряд… Эффективность Китайской лотереи для различных стран и различных длин ключа показана в 5-й. Ясно, что Китай оказался бы…

Табл. 7-2. Оценки среднего времени вскрытия грубой силой при китайской лотерее

(Все данные взяты из World Almanac and Book of Facts за 1995 год.)

 

 

 

Страна	Население	Количество телевизо­ров/радиоприемников	Время взлома
	56 бит	64 бита
Китай			280 секунд	20 часов
США			97 секунд	6.9 часа
Ирак			4.2 часа	44 дня
Израиль			5.5 часа	58 дней
Вайоминг			15 часов	160 дней
Виннемукка, Невада			48 дней	34 года

Биотехнология

Типичный динозавр состоит из 1014 клеток (без бактерий). Если каждая из них выполняет миллион шифро­ваний в секунду (неплохой результат), вскрытие… Другой биологический подход состоит в использовании генетически проектируемых… Предположим, что типичная клетка морской водоросли - это кубик со стороной 10 микрон (возможно, это оценка сверху,…

Термодинамические ограничения

Приняв, что к= 1.38*10-16 эрг/К, и что температура окружающей вселенной 3.2К, идеальный компьютер, ра­ботая при 3.2К, потреблял бы 4.4* 10"16… Далее, энергия, излучаемая нашим Солнцем за год, составляет около 1.21*1041… останется.

Табл. 7-4.

Разложение на множители с помощью решета общего

Поля чисел

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

Табл. 7-5. Разложение на множители с помощью решета специаль-ного поля чисел

Количество бит Сколько mips-лет нужно для разложе-

 

	ния
	<200
	3*107
	3*109
	2*10п
	4*1014

В 1991 году участники семинара Европейского института безопасности систем ( European Institute for System Security) согласились, что 1024-битовых модулей будет достаточно для длительного хранения секретов до 2002 года [150]. Однако, они предупреждали: "Хотя участники этого семинара являются лучшими специалистами в соответствующих областях, это заявление (по поводу срока безопасности) должно быть воспринято с осторож­ностью." Это хороший совет.

Умный криптограф сверхконсервативен при выборе длин открытых ключей . Чтобы понять, насколько длин­ный ключ вам нужен, вам придется оценить нужную безопасность и время жизни ключа, не забывая о текущем состоянии искусства разлагать на множители. Чтобы получить тот же уровень безопасности, который давало 512-битовое число в начале восьмидесятых, сегодня вам понадобится 1024-битовое число. Если же вы хотите, чтобы ваши ключи оставались безопасными в ближайшие 20 лет, 1024-битовое число, по видимому, слишком коротко.

Даже если ваши конкретные секреты не стоят усилий, нужных для разложения вашего модуля, вы можете оказаться в опасности. Представьте себе автоматическую банковскую систему, использующую для безопасности RSA. Мэллори может предстать перед судом и заявить: "Читали ли вы в газете за 1994 год, что RSA-129 был взломан, и что 512-битовые числа могут быть разложены на множители любой организацией, которая может потратить несколько миллионов долларов и подождать несколько месяцев ? Мой банк использует для безопасн о-сти 512-битовые числа и, между прочим, эти семь изъятий сделаны не мной." Даже если Мэллори лжет, судья, вероятно, может потребовать, чтобы банк это доказал.

Почему не использовать 10000-битовые ключи? Конечно, можно, но чем длиннее ваши ключи, тем больше стоимость вычислений. Вам нужен ключ, который был бы достаточно длинным для обеспечения безопасности, но достаточно коротким, чтобы его можно было использовать .

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

Вот некоторые соображения из [66]:

Мы считаем, что сможем получить доступ к 100 тысячам компьютеров без сверхчеловеческих усилий и неэтичных де й-ствий. То есть, мы не собираемся выпускать в Internet "червя" или разрабатывать вирус, который бы предоставил бы нам в ы-числительные ресурсы. Во многих организациях многие тысячи машин подключены к сети . Доступ к их возможностям по­требует искусной дипломатии, но не является невозможным. Приняв среднюю производительность машины равной 5 mips и время работы 1 год, вполне возможно осуществить проект, который требует полмиллиона mips-лет.

Проект разложения на множители 129-разрядного числа без значительных усилий смог задействовать 0.03 процента оценочной полной вычислительной мощности Internet [1190]. Разумно предположить, что хорошо раз­рекламированный проект получит на год 2 процента всемирной вычислительной мощности .

Предположим, что увлеченный криптоаналитик сможет получить в свое распоряжение 10000 mips-лет, большая корпорация - 10⁷ mips-лет, а правительство большой страны - 10⁹ mips-лет. Предположим также, что вычислительная мощь будет возрастать на порядок каждые пять лет. И , наконец, предположим также, что ус-

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

Табл. 7-6. Рекомендованные длины открытых ключей в (битах)

 

Год	Частное лицо	Корпорация	Правительство

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

Предсказывать более далекое будущее еще глупее. Кто может знать, каких успехов к 2020 году достигнет вычислительная техника, сетевые вычисления и математика? Однако, если окинуть взглядом всю картину, можно заметить, что в каждом следующем десятилетии мы получаем возможность разлагать на множители вдвое более длинные числа, чем в предыдущем. Это позволяет построить 0-й.

С другой стороны, техника разложения на множители может достичь предела своих возможностей задолго до 2045. Хотя я думаю, что это маловероятно.

Не все согласятся с моими рекомендациями. NSA установило для своего Стандарта цифровой подписи (Digital Signature Standard, см. раздел 20.1) длину ключей от 512 до 1024 бит - намного меньше, чем я рекомен­дую для длительной безопасности. У Pretty Good Privacy ("Вполне надежный секрет", см. раздел 24.12) макси­мальная длина ключа RSA составляет 2047 бит. Аржан Ленстра, лучший в мире раскладыватель на множители, в течение последних 10 лет отказывается делать предсказания [949]. В -1-й приведены рекомендации Рона Ри-веста для длины ключей, которые сделаны в 1990 году и кажутся мне слишком оптимистичными [1323]. Хотя его анализ на бумаге выглядит хорошо, в недавней истории можно найти примеры регулярно происходящих сюрпризов. Чтобы предохранить себя от последствия этих сюрпризов, есть смысл выбирать ключи с запасом .

Табл. 7-7.

Долгосрочный прогноз разложения

На множители

Минимальные оценки предполагают бюджет $25000, алгоритм "квадратичное решето " и скорость техниче­ского прогресса 20 процентов в год.… решета специального поля чисел и скорость технического прогресса 45 процентов… Всегда есть вероятность того, что успехи в разложении на множители будут поразительны и для меня, но я попытался…

Квантовые вычисления

В [1443] Питер Шор (Peter Shor) очертил принципы построения машины для разложения на множители, о с-нованной на законах квантовой механики. В… Общепризнанно, что квантовый компьютер не противоречит фундаментальным законам… Поэтому, хотя квантовое разложение на множители вызывает восхищение в академических кругах, малов е-роятно, что оно…

Табл. 7-9.

Длины симметричных и открытых ключей с аналогичной jc-

Тойчивостью к вскрытию грубой силой

ключа (в битах) ключа (в битах) 56 384 64 512

Табл. 7-10. Требования к безопасности различной информации

Типы трафика

Тактическая военная информация

Объявления о продуктах, слиянии компаний, процент­ных ставках

Долговременны бизнес-планы

Торговые секреты (например, рецепт кока-колы)

Секреты водородной бомбы

Личности шпионов

Личные дела

Дипломатические конфликты

Данные переписи США

 

	Минимальная дли-
Время жизни	на ключа (в битах)
минуты/часы	56-64
дни/недели
годы
десятилетия
>40 лет
>50 лет
>50 лет
>65 лет
100 лет	по меньшей мере

7.6 Caveat emptor¹

Вся эта глава - просто много чепухи. This entire chapter is a whole lot of nonsense. Смешно говорить даже о самом понятии предсказания вычислительной мощи на 10, а тем более на 50 лет вперед . Эти расчеты приведе­ны только для ориентировки, ни для чего больше. Экстраполируя прошлое, мы получаем будущее, которое, возможно, будет иметь мало общего с грядущей реальностью.

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

 

¹ Да будет осмотрителен покупатель (латин.)

Глава 8 Управление ключами

У Алисы и Боба есть безопасная система связи. Они играют в мысленный покер, одновременно подписью а-ют контракты и даже меняют цифровые наличные. Их протоколы безопасны. Их алгоритмы -самые лучшие. К несчастью, они покупают свои ключи от "Keys-R-Us" Евы, чей лозунг - "Вы можете доверять нам: Безопасность - среднее имя человека, которого туристический агент нашей бывшей тещи встретил в "Kwik-E-Mart".

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

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

Криптоаналитики часто вскрывают и симметричные криптосистемы, и криптосистемы с открытыми ключ а-ми через распределение ключей. Зачем Еве беспокоиться об проблеме вскрытия криптографического алгоритма целиком, если она может восстановить ключ из-за неаккуратного хранения ключа? Зачем ей тратить 10 ми л-лионов долларов на создание машина для криптоанализа, если она может подкупить клерка за 1000 долларов? Миллион долларов за клерка связи на хорошем месте в дипломатическом посольстве может быть выгодной сделкой. Уолкеры годами продавали Советам ключи шифрования ВМС США. Руководитель контрразведки ЦРУ стоил меньше 2 миллионов долларов, включая жену. Это намного дешевле, чем строить огромные маш и-ны вскрытия и нанимать блестящих криптоаналитиков. Ева может выкрасть ключи. Она может арестовать или похищать кого-то, кто знает ключи. Она может совращать кого-то и получать ключи таким образом. (Морские пехотинцы, охранявшие посольство США в Москве не устояли перед подобной атакой.) Намного проще нах о-дить дефекты в людях, чем в криптосистемах.

Алиса и Боб должны защищать и свой ключ, и в той степени шифруемые им данные. Если ключ не изменять регулярно, то количество данных может быть огромно. К сожалению, многие коммерческие продукты просто объявляют "Мы используем DES" и забывают обо всем остальном. Результаты не слишком впечатляют.

Например, программа DiskLock для Macintosh (версия 2.1), продававшаяся в большинстве магазинов пр о-граммного обеспечения, претендует на безопасное шифрование DES. Она шифрует файлы, используя DES. Ре а-лизация DES алгоритма правильна. Однако, DiskLock сохраняет ключ DES вместе с зашифрованным файлом. Если вы знаете, где искать ключ, и хотеть прочитать файл, шифрованный DiskLock с помощью DES, восстан о-вите ключ из шифрованного файла и затем расшифровывать файл. Не имеет значение, что программа использ у-ет шифрование DES - реализация абсолютно небезопасна.

Дальнейшую информацию относительно управления ключами можно найти в [457, 98, 1273, 1225, 775, 357]. В следующих разделах обсуждаются некоторые из вопросов и решений.

8.1 Генерация ключей

The security of an algorithm rests in the key. If you're using a cryptographically weak process to generate keys, then your whole system is weak. Eve need not cryptanalyze your encryption algorithm; she can cryptanalyze your key generation algorithm.

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

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

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

Табл. 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!"

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

My name is Ozymandias, king of kings. Look on my works, ye mighty, and despair. 1 может "перемолоться" в такой 64-битовый ключ: e6cl 4398 5ae9 0a9b

Стандарт генерации ключей Х9.17

Tt -------- ^Шифровать! ' ' ► Vi+1 нф Шифровать

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

Пусть Е_К(Х) - это X, зашифрованный DES ключом К, специальным ключом, предусмотренным для генер а-ции секретных ключей. V₀ - это секретная 64-битовая стартовая последовательность. Г- это метка времени. Для генерации случайного ключа R_t вычислим:

Ri= Е_К(Е_К(Т,) © V.)

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

V_l+1= E_K(E_K(T,) ® R,)

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

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

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

Ki

Кг

Кз

к₄

к₅

 

к2

к5

Рис. 8-2. Распределение ключей по параллельным каналам.

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

Распределение ключей в больших сетях

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

обменяться ключами, общее число обменов ключами в сети из п человек равно п(п -1)/2.

В сети с шестью пользователями потребуется 15 обменов ключами. В сети из 1000 пользователей понадо­бится уже около 500000 обменов ключами. В этих случаях работа сети гораздо более эффективна при использ о-вании центрального сервера (или серверов) ключей.

Кроме того, любой из протоколов симметричной криптографии или криптографии с открытыми ключами, приведенных в разделе 3.1, подходит для безопасного распределения ключей.

8.4 Проверка ключей

Как Боб узнает, получив ключ, что ключ передан Алисой, а не кем-то другим, кто выдает себя за Алису? Все просто, если Алиса передает ему ключ при личной встрече. Если Алиса посылает свой ключ через доверенного курьера, то курьеру должен доверять и Боб. Если ключ зашифрован ключом шифрования ключей, то Боб должен доверять тому, что этот ключ шифрования ключей есть только у Алисы. Если для подписи ключа Алиса испол ь-зует протокол электронной подписи, Боб при проверке подписи должен доверять базе данных открытых кл ю-чей,. (Ему также придется считать, что Алиса сохранила свой ключ в безопасности.) Если Центр распределения ключей (Key Distribution Center, KDC) подписывает открытый ключ Алисы, Боб должен считать, что его копия открытого ключа KDC не была подменена.

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

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

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

Боб мог бы также проверять ключ Алисы по телефону, получив возможность услышать ее голос. Распозн а-вание голоса действительно является хорошей схемой идентификации личности. Если речь идет об открытом ключе, он может безопасно его повторить его даже при угрозе подслушивания. Если это секретный ключ, он может использовать для проверки ключа одностороннюю хэш-функцию. Оба TSD PGP (см. раздел 24.12.) и АТ$Т (см. Раздел 24.18) используют этот способ пр оверки ключей.

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

Обнаружение ошибок при передаче ключей

Одним из наиболее широко используемых методов является шифрование ключом некоторой постоянной в е-личины и передача первых 2-4 байт этого…

Обнаружение ошибок при дешифрировании

Наивным подходом явилось бы присоединение к открытому тексту до шифрования проверочного блока-известного заголовка. Получатель Боб расшифровывает… легчает вскрытие шифров с коротким ключом, таких как DES и все экспортируемые… Вот для этого способ получше [821]:

Контроль использования ключей

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

Заверенные открытые ключи

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

Распределенное управление ключами

Распределенное управление ключами, используемое в PGP (см. раздел 24.12), решает эту проблему с помо­щью поручителей. Поручители - это пользователи… Спустя какое-то время Боб соберет подписи большего числа поручителей . Если… Выгода этого механизма - в отсутствии СА, которому каждый должен доверять. А отрицательной стороной является…

Глава 9

Типы алгоритмов и криптографические режимы

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

Набивка

Последний блок дополняется (набивается) некоторым регулярным шаблоном - нулями, единицами, чер е-дующимися нулями и единицами - для получения… На 8-й показан другой вариант, называемый похищением шифротекста[402]. Рп., -… Шифрование

С

 

Ек

Ек

Dk

Dk

1

'

*

'

1

'

'

•

Сп

С

Сп-1

Рп

С

Рп-1

Рис. 9-1. Похищение шифротекста.

9.2 Повтор блока

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

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

 

Банк 1: Передача	1.5 блока
Банк 2: Прием	1.5 блока
Имя вкладчика	6 блоков
Счет вкладчика	2 блока
Сумма вклада	1 блок

Блок соответствует 8-байтному блоку шифрования. Сообщения шифруются с помощью некоторого блочного алгоритма в режиме ЕСВ.

Мэллори, который подслушивает линию связи между банками, банком Алисы и банком Боба, может испол ь-зовать эту информацию для обогащения. Сначала, он программирует свой компьютер для записи всех шифр о-ванных сообщений из банка Алисы в банк Боба. Затем, он переводит $100 из банка Алисы на свой счет в банк

Боба. Позже, он повторяет эту операцию еще раз. С помощью своего компьютера он проверяет записанные с о-общения, разыскивая пару идентичных сообщений. Этими сообщениями являются те сообщения, которыми он переводит $100 на свой счет. Если он находит несколько пар одинаковых сообщений (что больше похоже на реальную жизнь), он делает еще один денежный перевод и записывает результат. В конце концов он сможет выделить сообщение, которым был проведен именно его перевод.

Теперь он может отправить это сообщение по каналу связи, когда захочет . Каждое сообщение приведет к за­числению на его счет в банке Боба еще $100. Когда оба банка сверят свои переводы (возможно в конце дня), они обнаружат переводы-призраки, но если Мэллори достаточно умен, он уже сбежит в какую-нибудь банан о-вую республику без договора об экстрадиции, прихватив с собой деньги . И скорее всего он использует суммы несколько больше $100 и провернет операцию сразу для нескольких банков .

На первый взгляд банки могут легко пресечь это, добавляя метки времени к своим сообщениям .

Метка даты/времени 1 блок

Банк 1: Передача 1.5 блока

Банк 2: Прием 1.5 блока

Имя вкладчика 6 блоков

Счет вкладчика 2 блока

Сумма вклада 1 блок

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

Номер блока

 

Метка времени

Банк отправитель

Банк получатель

Имя вкладчика

Счет вкладчика

Сумма

Поле

Рис. 9-2. Блоки шифрования в записи приведенного примера.

Он перехватывает сообщения из банка Алисы в банк Боба и заменяет блоки с 5 по 12 сообщения байтами , соответствующими его имени и номеру счета. Затем он посылает измененные сообщения в банк Боба. Ему не нужно знать, кто был отправителем денег, ему даже не нужно знать переводимую сумму (хотя он может связать подправленное сообщение с соответствующим увеличением своего счета и определить блоки, соответствующие определенным денежным суммам). Он просто изменяет имя и номер счета на свои собственные и следит за ро с-том своих доходов. (Я помню, что Мэллори надо быть осторожным, чтобы не модифицировать сообщение о снятии денег, но предположим на минутку, что у этих сообщений другая длина или иной отличительный пр и-знак.)

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

Банки могут минимизировать эту проблему, часто меняя свои ключи, но это означает только, что Мэллори придется действовать побыстрее. Однако, добавление MAC также решит проблему. Несмотря на это рассматри­ваемая проблема фундаментальна для режима ЕСВ. Мэллори удалять, повторять или заменять блоки по своему усмотрению. Решением является способ, называемый сцеплением.

9.3 Режим сцепления блоков шифра

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

В режиме сцепления блоков шифра(cipher block chaining, CBC) перед шифрованием над открытым тек­стом и предыдущим блоком шифротекста выполняется операция XOR. На 6-й (а) показано шифрование СВС в действии. ,Когда блок открытого текста зашифрован, полученный шифротекст сохраняется в регистре обратной связи. Прежде чем будет зашифрован следующий блок открытого текста, он подвергается операции XOR вместе

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

Дешифрирование является обратной операцией (см. Figure 9.3 (б) ). Блок шифротекста расшифровывается как обычно, но сохраняется в регистре обратной связи. Затем следующий блок дешифрируется и подвергается операции XOR вместе с содержимым регистра обратной связи. Теперь следующий блок шифротекста сохраня­ется в регистре обратной связи, и так далее, до конца сообщения .

Математически это выглядит следующим о бразом: С, = Е_К(Р, © С,.])

Pi = С,-; © D_K(Q)

Pi-l

P_i

Рм

Си

C_i

ci+_I

 

О

О

О

 

E_k

E_k

E_k

D_k

D_k

D_k

 

О

O

O

 

Си

C_i

Ci+_I

Pt-i

P_i

Рм

 

(а) Шифрование СВС

(б) Дешифрирование СВС

Рис. 9-3. Режим сцепления блоков шифра.

Вектор инициализации

У ряда сообщений может быть одинаковый заголовок - тема письма, строка "From" или еще что-нибудь. Хо­тя повтор блока будет невозможен,… Избежать этого можно, шифруя в качестве первого блока какие-то случайные… С использованием IV сообщения с идентичным открытым текстом при шифровании переходят в сообщения с различным…

О

Е_к

Рп-1

Gt;в

Е_к

Р_п (/' битов длиной)

 

Сп-2

Сп-1

С„ (j битов длиной)

Рис. 9-4. Шифрование короткого последнего блока в режимеСВС.

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

Лучшим способом является похищение щифротекста (см. 4th) [402]. Р„_₇ - последний полный блок открытого текста, Р„ - заключительный, короткий блок открытого текста. С„., - последний полный блок шифротекста, С„ -заключительный, короткий блок шифротекста. С - это просто промежуточный результат, не являющийся ча­стью переданного шифротекста. Преимуществом этого метода является то, что все биты открытого текста соо б-щения проходят через алгоритм шифрования.

 

Рис. 9-5. Похищение шифротекста в режимеСВС.

Распространение ошибки

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

ленный открытый текст будет содержать ту же единственную ошибку.

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

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

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

Вопросы безопасности

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

Рис. 9-6. Потоковый шифр

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

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

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

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

Генератор потока ключей состоит из трех основных частей (см. 2nd). Внутреннее состояние описывает теку­щее состояние генератора потока ключей. Два генератора потока ключей, с одинаковым ключом и одинаковым внутренним состоянием, выдают одинаковые потоки ключей. Функция выхода по внутреннему состоянию гене­рирует бит потока ключей. Функция следующего состояния по внутреннему состоянию генерирует новое вну т-реннее состояние.

КЛЮЧ K

 

Рис. 9-7. Устройство генератора потока ключей.

9.5 Самосинхронизирующиеся потоковые шифры

В самосинхронизирующихся потоковых шифрахкаждый бит потока ключей является функцией фиксиро­ванного числа предыдущих битов шифротекста [1378]. Военные называют этот шифр автоключом шифротек-ста(ciphertext auto key, CTAK). Основная идея была запатентована в 1946 [667].

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

Рис. 9-8. Самосинхронизирующийся генератор потока ключей.

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

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

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

Вопросы безопасности

9.6 Режим обратной связи по шифру Блочный шифр также может быть реализованы как самосинхронизирующийся потоковый… В режиме CFB единица зашифрованных данных может быть меньше размера блока . В следующем примере каждый раз шифруется…

Ф

С/

С/

Е

p_i

 

(а) Шифрование

(б) Дешифрирование

Рис. 9-9. Режим 8-битовой обратной связи по шифру.

Рп-1 Рп Рп+1

О

Е_к

О г-

Е_к

О

 

Сп-1

с_п

С_п+1

Рис. 9-10. n-битовый CBF с n-битовым алгоритмом.

Как и режим СВС, режим CFB связывает вместе символы открытого текста так, что шифротекст зависит от всего предшествующего открытого текста.

Вектор инициализации

Однако IV должен быть уникальным. (В отличие от режима СВС, где IV не обязан быть уникальным, хотя это и желательно.) Если IV в режиме CFB не…

Распространение ошибки

Более тонкой проблемой, связанной с такого рода распространением ошибки, является то, что если Мэллори знает открытый текст сообщения, он может… CFB самовосстанавливается и после ошибок синхронизации . Ошибка попадает в… 9.7 Синхронные потоковые шифры

Вскрытие вставкой

текста. Оригинальный открытый текст: pip! рЗ Pi Оригинальный поток клю­чей: U к! kj Id… Мэллори вставляет один известный ему бит, w', в открытый текст после pi и затем пытается получить моди­фицированный…

Рис. 9-11. 8-битовый режим

Вектор инициализации

В сдвиговый регистр OFB также сначала должен быть загружен IV. Он должен быть уникальным, но сохра­нять его в секрете не обязательно.

Распространение ошибки

С другой стороны, потеря синхронизации смертельна. Если сдвиговые регистры при шифровании и при д е-шифрировании отличаются, то восстановленный…

Рис. 9-12. n-битовый OFB с n-битовым алгоритмом.

OFB и проблемы безопасности

связей DES [1143], избегайте их. Режим OFB выполняет XOR над потоком ключей и текстом. Этот поток ключей со…

Потоковые шифры в режиме OFB

Рис. 9-13. Генератор потока ключей в режиме с выходной обратной связью.

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

9.9 Режим счетчика

Блочные шифры в режиме счетчикаиспользуют в качестве входов алгоритма последовательные номера [824, 498, 715]. Для заполнения регистра используется счетчик, а не выход алгоритма шифрования . После шиф­рования каждого блока счетчик инкрементируется на определенную константу, обычно единицу . Для этого ре­жима свойства синхронизации и распространения ошибки такие же, как и для OFB. Режим счетчика решает проблему й-битового выхода режима OFB, где п меньше длины блока.

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

Потоковые шифры в режиме счетчика

У потоковых шифров в режиме счетчика простые функции следующего состояния и сложные функции вых о-да, зависящие от ключа. Этот метод, показанный на -5-й, был предложен в [498, 715]. Функция следующего состояния может быть чем-то простым, например, счетчиком, добавляющим единицу к предыдущему состо я-нию.

Рис. 9-14. Генератор потока ключей в режиме счетчика.

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

9.10 Другие режимы блочных шифров

Режим сцепления блоков

Для использования блочного алгоритма в режиме сцепления блоков(block chaining, ВС), просто выполните XOR входа блочного шифра и результата XOR всех предыдущих блоков шифротекста. Как и для СВС исполь­зуется IV. Математически это выглядит как:

С, = Ek(P, Q F*; F, I = F, © С, Р, = F, © *(С,); Fi* I = F,

А

Как и СВС, обратная связь процесса ВС приводит к распространению ошибки в открытом тексте. Главная

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

Режим распространяющегося сцепления блоков шифра

Ci = Е*Р, ©СИ© Р, I) P* = Cjl© Pi I © а*,) PCBC используется в Kerberos версии 4 (см. раздел 24.5) для выполнения за один…

Рис. 9-15. Режим распространяющегося сцепления блоков шифра.

К несчастью в этом режиме существует одна проблема [875]. Перестановка двух блоков шифротекста приво­дит к неправильной расшифровке двух соответствующих блоков открытого текста , но из-за природы операции XOR над открытым текстом и шифротекстом, дальнейшие ошибки компенсируются. Поэтому, если при провер­ке целостности проверяются только несколько последних блоков расшифрованного открытого текста, можно получить частично испорченное сообщение. Хотя никто до сих пор не додумался, как воспользоваться этой сла­бостью, Kerberos версии 5 после обнаружения ошибки переключается в режим СВС.

Сцепление блоков шифра с контрольной суммой

Выходная обратная связь с нелинейной функцией

С, = Ek*P* К* = Edit, ,P, = a*,); Ki = Е*К, I) Ошибка одного бита шифротекста распространяется только на один блок открытого…

Прочиережимы

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

Табл. 9-1. Краткий обзор режимов работы блочных шифров

ЕСВ: Security:

-Plaintext patterns are not concealed.

- Input to the block cipher Is not randomized; It Is the same as the plaintext. + More than one message can be encrypted with the same

- plaintext Is easy to manipulate; blocks can be removed, repeated, or Interchanged.

Efficiency: + Speed is the same as the block cipher.

- Clphertext Is up to one block longer than the plaintext, due to padding.

- No preprocessing is possible. *Processing is paraUelizable. Fault-tolerance:

-A ciphertext error affects one full block of plaintext.

- Synchronization error is unrecoverable.
CFB:

Security:

+ Plaintext patterns are concealed. + Input to the block cipher is randomized. + More than one message can be encrypted with the same key, provided that a different IV is used. +/- Plaintext is somewhat difficult to manipulate; blocks call be removed from the beginning and end of the message, bits of the first block can be changed, and repetition allows some controlled changes.

Efficiency: + Speed is the same as the block cipher.

- Ciphertext is the same size as the plaintext, not counting the IV.

+/- Encryption is not paraUelizable; decryption is paral- Idizable and has a random-access property.

- Some preprocessing is possible before a block is seen; the Previous ciphertext block can be encrypted. +/- Encryption is not paraUelizable; decry p-
tion is paral- felizable and has a random-access property.

F'auh-toterance:

-A ciphertext error affects the corresponding bit of plaintext and the next full block.

+ Synchronization errors of full block sizes are recoverable. I. -bit CFB can recover from the addition or loss of single bits.

cbc:

Security:

+ Plaintext patterns are concealed by XORing with previous ciphertext block.

+ Input to the block cipher is randomized by XORing with the previous ciphertext block.

+ More than one message can be encrypted with the same key.

+/- Plaintext is somewhat difficult to manipulate; blocks can be removed from the beginning and end of the message, bits of the first block can be changed, and repetition allows some controlled changes.

Efficiency: + Speed is the same as the block cipher.

- Ciphertext is up to one block longer than the plaintext, not counting the IV.

- No preprocessing is possible.

+/- Encryption is not paraUelizable; decryption is paral- lelizable and has a random-access property. Wau*-toterance:

- A ciphertext error affects one full block of plaintext and the corresponding bit in the next block.

- Synchronization error is unrecoverable. OFB/Counter: Security;

+ Plaintext patterns are concealed. + Input to the block cipher is randomized. + More than one message can be encrypted with the same key, provided that a different IV is used. - Plaintext is very easy to manipulate; any change in ciphertext directly affects the plaintext.

C*lclency: + Speed is the same as the block cipher.

- Ciphertext is the same size as the plaintext, not counting the IV. + Processing is possible before the message is seen.

-/+ OFB processing is not paraUelizable; counter processing is paraUelizable.

Fau*t-tolerance:

+ A ciphertext error affects only the corresponding bit of plaintext. - Synchronization error is unrecoverable.

CFB-specifically 8-bit CFB-is generally the mode ol choice for encrypting streams of characters when each cha r-acter has to be treated individually, as in a link between a terminal and a host. OFB is most often used in high-speed synchronous systems where error propagation is intolerable. OFB is also the mode of choice if preprocessing is r e-quired.

OFB is the mode of choice in a error-prone environment, because it has no error extension.

Stay away from the weird modes. One of the four basic modes-ECB, CBC, OFB, and CFB-is suitable for almost any application. These modes are not overly complex and probably do not reduce the security of the system. While it is possible that a complicated mode might increase the security of a system, most likely it just increases the complexity. None of the weird modes has any better error propagation or error recovery characteristics.

9.12 INTERLEAVING

With most modes, encryption of a bit (or block) depends on the encryption of the previous bits (or blocks). This can often make it impossible to parallelize encryption. For example, consider a hardware box that does encryption in CBC mode. Even if the box contains four encryption chips, only one can work at any time. The next chip needs the results of the previous chip before it starts working.

The solution is to interleave multiple encryption streams. (This is not multiple encryption; that's covered in Se c-tions 15.1 and 15.2). Instead of a single CBC chain, use four. The first, fifth, and every fourth block thereafter are e n-crypted in CBC mode with one IV. The second, sixth, and every fourth block thereafter are encrypted in CBC mode with another IV, and so on. The total IV is much longer than it would have been without interleaving.

Think of it as encrypting four different messages with the same key and four different IVs. These messages are all i nterleaved.

This trick can also be used to increase the overall speed of hardware encryption. If you have three encryption chips, each c a-pable of encrypting data at 33 megabits/second, you can interleave them to encrypt a single 100 megabit/second data channel.

Figure 9.16 shows three parallel streams interleaved in CFB mode. The idea can also work in CBC and OFB modes, and with any number of parallel streams. Just remember that each stream needs its own IV. Don't share.

9.13 BLOCK CIPHERS VERSUS STREAM CIPHERS

Although block and stream ciphers are very different, block ciphers can be implemented as stream ciphers and stream ciphers can be implemented as block ciphers. The best definition of the difference I've found is from Ranier Rueppel [1362.]:

Block ciphers operate on data with a fixed transformation on large blocks of plaintext data; stream ciphers ope r­ate with a time-varying transformation on individual plaintext digits.

Figure 9.16 Interleavingthtee CFB encryptions.

In the real world, block ciphers seem to be more general (i.e., they can be used in any of the four modes) and stream ciphers seem to be easier to analyze mathematically. There is a large body of theoretical work on the analysis and design of stream c i-phers-most of it done in Europe, for some reason. They have been used by the world's militaries since the invention of electronics. This seems to be changing; recently a whole slew of theoretical papers have been written on block cipher design. Maybe soon there will be a theory of block cipher design as rich as our current theory of stream cipher d esign.

Otherwise, the differences between stream ciphers and block ciphers are in the implementation. Stream ciphers that only e n-crypt and decrypt data one bit at a time are not really suitable for software implementation. Block ciphers can be easier to impl e-ment in software, because they often avoid time-consuming bit manipulations and they operate on data in computer-sized blocks. On the other hand, stream ciphers can be more suitable for hardware implementation because they can be implemented very eff i-ciently in silicon.

These are important considerations. It makes sense for a hardware encryption device on a digital communications channel to encrypt the individual bits as they go by. This is what the device sees. On the other hand, it makes no sense for a software encry p-tion device to encrypt each individual bit separately. There are some specific instances where bit- and byte-wise encryption might be necessary in a computer system-encrypting the link between the keyboard and the CPU, for example-but generally the encry p-tion block should be at least the width of the data bus.

Глава 10 Using Algorithms

Think of security - data security, communications security, information security, whatever - as a chain. The security of the entire system is only as strong as the weakest link. Everything has to be secure: cryptographic algorithms, protocols, key manag e-ment, and more. If your algorithms are great but your random-number generator stinks, any smart cryptanalyst is going to attack your system through the random-number generation. If you patch that hole but forget to securely erase a memory location that contains the key, a cryptanalyst will break your system via that route. If you do everything right and accidentally e-mail a copy of your secure files to The Wall Street Journal, you might as well not have bothered.

It's not fair. As the designer of a secure system, you have to think of every possible means of attack and protect against them all, but a cryptanalyst only has to find one hole in your security and exploit it.

Cryptography is only a part of security, and often a very small part. It is the mathematics of making a system secure, which is different from actually making a system secure. Cryptography has its "size queens": people who spend so much time arguing about how long a key should be that they forget about everything else. If the secret police want to know what is on your computer, it is far easier for them to break into your house and install a camera that can record what is on your computer screen than it is for them to cryptanalyze your hard drive.

Additionally, the traditional view of computer cryptography as "spy versus spy" technology is becoming increasingly ina p-propriate. Over 99 percent of the cryptography used in the world is not protecting military secrets; it's in applications such as bank cards, pay-TV, road tolls, office building and computer access tokens, lottery terminals, and prepayment electricity meters [43,44]. In these applications, the role of cryptography is to make petty crime slightly more difficult; the paradigm of the well-funded a d-versary with a rabbit warren of cryptanalysts and roomsful of computers just doesn't apply.

Most of those applications have used lousy cryptography, but successful attacks against them had nothing to do with cry p-tanalysts. They involved crooked employees, clever sting operations, stupid implementations, integration blunders, and random idiocies. (I strongly recommend Ross Anderson's paper, "Why Cryptosytems Fail" [44]; it should be required reading for anyone involved in this field.) Even the NSA has admitted that most security failures in its area of interest are due to failures in impl e-mentation, and not failures in algorithms or protocols [1119]. In these instances it didn't matter how good the cryptography was; the successful attacks bypassed it completely.

CHOOSING AN ALGORITHM

- They can choose a published algorithm, based on the belief that a published algorithm has been scrutinized by many cry p-tographers; if no one has… - They can trust a manufacturer, based on the belief that a well-known… - They can trust a private consultant, based on the belief that an impartial consultant is best equipped to make a…