openPGP в России / Библиотека / Статьи / Анализ надежности PGP / Алгоритмы PGP / Симметричные блочные шифры

==Симметричные блочные шифры==

==={{a name="p1"}}Bass-o-Matic===

Этот блочный шифр приведен первым как первый, который был представлен в PGP. Он больше не является частью программы. Он ненадежен. Фил Циммерман сам разработал этот шифр, а спустя два месяца после выхода PGP 1.0 он и ##Бихам## выявили слабости Bass-o-Matic. Найти этот шифр в литературе непросто: библия блочных шифров, "Прикладная криптография" ((../Библиография#b18 [18])), не содержит даже упоминания о нем. К счастью, исходные коды PGP 1.0 все еще доступны в качестве описания этого алгоритма. Его название произошло от постановки в воскресном телешоу с рыбой, приготовленной в блендере.

==={{a name="p2"}}IDEA===

##IDEA## появился на свет в 1991 году под названием ##IPES## (Improved Proposed Encryption Standard). В 1992 году название изменилось на International Data Encryption Algorithm. Его авторы – Суэджа ##Лай## и Джеймс ##Мэсси##. Это 64-битовый блочный шифр со 128-битовым ключом. Его дизайн основан на смешении побитового исключающего ИЛИ (&#8853;), сложения по модулю ##2^^16^^## и умножения по модулю ##2^^16^^+1## (известное простое число 65537). Он быстр в программной реализации (процессоры персональных компьютеров могут умножать одной инструкцией), но менее эффективен в аппаратной реализации (маленькие процессоры смарт-карт не имеют таких инструкций). IDEA запатентован, патент принадлежит швейцарской Ascom-Tech AG.

Практических атак, направленных на полный алгоритм IDEA, неизвестно. Если вы планируете взломать PGP, можете забыть об атаке на его блочные шифры. Это __не__ его слабое место.

====Кровавые подробности====
++//В этом параграфе специально для тех, кому интересно, как работают блочные шифры, приведено детальное описание алгоритма IDEA. Можете его пропустить; это не отразится на вашем понимании дальнейшего материала.//++

Ключ расширяется, чтобы получить множество 16-битовых подключей. Для каждого из 8 раундов используется шесть подключей ""S""vv1vv, ""S""vv2vv, ""S""vv3vv, ""S""vv4vv, ""S""vv5vv и ""S""vv6vv, а для заключительного выходного преобразования – четыре других подключа ""S""vv1vv, ""S""vv2vv, ""S""vv3vv, ""S""vv4vv. Затем, на каждом из восьми раундов выполняются следующие шаги:

1. 64-битовый вход данного раунда делится на четыре 16-битовых подблока: ""X""vv1vv, ""X""vv2vv, ""X""vv3vv и ""X""vv4vv.
  2. ##A = ""X""vv1vv &#8727; ""S""vv1vv##. Это умножение по модулю 65537. 0 умножается как -1.
  3. ##B = ""X""vv2vv + ""S""vv2vv##. Это сложение по модулю 2^^16^^.
  4. ##C = ""X""vv3vv + ""S""vv3vv##
  5. ##D = ""X""vv4vv &#8727; ""S""vv4vv##
  6. ##E = A &#8853; C##
  7. ##F = B &#8853; D##
  8. ##G = E &#8727; ""S""vv5vv##
  9. ##H = F + G##
  10. ##I = H &#8727; ""S""vv6vv##
  11. ##J = G + I##
  12. ##K = A &#8853; I##
  13. ##L = C &#8853; I##
  14. ##M = B &#8853; J##
  15. ##N = D &#8853; J##

Выход каждого раунда – это ##(K L M N)##. После каждого раунда, за исключением последнего, два внутренних подблока меняются местами, и следующий раунд начинается с ##(""X""vv1vv ""X""vv2vv ""X""vv3vv ""X""vv4vv) vvi+1vv = (K M L N)vvivv##.

После восьмого раунда происходит заключительное преобразование (с новыми подключами ""S""vv1vv, ""S""vv2vv, ""S""vv3vv и ""S""vv4vv):

* ##W = ""X""vv1vv &#8727; ""S""vv1vv##
  * ##X = ""X""vv2vv + ""S""vv2vv##
  * ##Y = ""X""vv3vv + ""S""vv3vv##
  * ##Z = ""X""vv4vv &#8727; ""S""vv4vv##

Сами подключи зависят от того, зашифровываете вы или расшифровываете. Если вы зашифровываете, то для первых 8 подключей просто берете биты ключа ##K##, разделенного на 16-битовые группы, затем циклически сдвигаете ключ на 25 бит влево, снова берете 8 подключей, сдвигаете еще на 25 бит, ... пока не получите все подключи. Процесс суммирован в ((#t1 таблице 1)), где ""K""vv0-16vv означает, что берутся биты ключа от 0 до 16.

Если вы расшифровываете, то подключи представляют собой инвертированные подключи зашифрования с обратными значениями операций. Суть в том, что вы выполняете те же операции, что и при зашифровании, но наоборот. Пусть ##E(1,2)##, или, сокращенно, ##E12##, будет вторым подключом зашифрования из раунда 1, ##-X## – инверсией прибавления ##X##, а ##X'## – инверсией умножения ##X##. Тогда подключи расшифрования можно получить из ((#t2 таблицы 2)).

IDEA похож на другие блочные шифры во всем, кроме одного: он не содержит S-блоков. ##S-блок## – это таблица подстановочных значений, действующая как очень случайная функция: она не должна быть линейной или иным образом систематизированной. Дело в том, что XOR и сложение рассеивают информацию, тогда как S-блоки действительно перемешивают ее. Часто именно S-блоки определяют устойчивость шифра против криптоаналитических атак. IDEA использует умножение по модулю 65537 в качестве своего "S-блока". Это крайне хаотичная функция, за счет чего получается очень большой S-блок, который не нужно хранить.

++{{a name="t1"}}Таблица 1. Подключи зашифрования IDEA++
#|
||**Раунд 1**|""K""vv0-16vv |""K""vv16-32vv |""K""vv32-48vv |""K""vv48-64vv |""K""vv64-80vv |""K""vv80-96vv||
||**Раунд 2**|""K""vv96-112vv |""K""vv112-128vv |""K""vv25-41vv |""K""vv41-57vv |""K""vv57-73vv |""K""vv73-89vv||
||**Раунд 3**|""K""vv89-105vv |""K""vv105-121vv |""K""vv121-128vv, ""K""vv0-9vv |""K""vv9-25vv |""K""vv50-66vv |""K""vv66-82vv||
||**Раунд 4** |""K""vv82-98vv |""K""vv98-114vv |""K""vv114-128vv, ""K""vv0-2vv |""K""vv2-18vv |""K""vv18-34vv |""K""vv34-50vv||
||**Раунд 5**|""K""vv75-91vv |""K""vv91-107vv |""K""vv107-123vv |""K""vv123-128vv, ""K""vv0-11vv |""K""vv11-27vv |""K""vv27-43vv||
||**Раунд 6**|""K""vv43-59vv |""K""vv59-75vv |""K""vv100-116vv |""K""vv116-128vv, ""K""vv0-4vv |""K""vv4-20vv |""K""vv20-36vv||
||**Раунд 7**|""K""vv36-52vv |""K""vv52-68vv |""K""vv68-84vv |""K""vv84-100vv |""K""vv125-128vv, ""K""vv0-13vv |""K""vv13-29vv||
||**Раунд 8**|""K""vv29-45vv |""K""vv45-61vv |""K""vv61-77vv |""K""vv77-93vv |""K""vv93-109vv |""K""vv109-125vv||
||**Закл. преобр.**|""K""vv22-38vv |""K""vv38-54vv |""K""vv54-70vv |""K""vv70-86vv||
|#

++{{a name="t2"}}Таблица 2. Подключи расшифрования IDEA++
#|
||**Раунд 1**|E91'|-E92|-E93|E94'|E85|E86||
||**Раунд 2**|E81'|-E83|-E82|E84'|E75|E76||
||**Раунд 3**|E71'|-E73|-E72|E74'|E65|E66||
||**Раунд 4**|E61'|-E63|-E62|E64'|E55|E56||
||**Раунд 5**|E51'|-E53|-E52|E54'|E45|E46||
||**Раунд 6**|E41'|-E43|-E42|E44'|E35|E36||
||**Раунд 7**|E31'|-E33|-E32|E34'|E25|E26||
||**Раунд 8**|E21'|-E23|-E22|E24'|E15|E16||
||**Закл. преобр.**|E11'|-E12|-E13|E14'||
|#

==={{a name="p3"}}CAST===

Карлайсл ##Адамс## и Стаффорд ##Таварес## создали блочный шифр ##CAST##. Они утверждали что его название описывает процесс разработки, ((*1)) но более вероятно, что они намеренно подобрали название по собственным инициалам. Точный вариант CAST, реализованный в PGP, – CAST5-128, специфицированный в RFC 2144 ((../Библиография#b1 [1])). Это 16-раундовый шифр Файстеля со 128-битовым ключом, оперирующий на 64-битовых блоках.

Исходное описание CAST не оговаривало порядок выбора S-блоков. RFC же содержит их описание. Документ определяет CAST-128 – 128-битовый вариант алгоритма, который также может работать с ключом меньшего размера. Чтобы отличить все эти варианты, CAST-128 еще именуют CAST5, а длину ключа дописывают после названия. PGP использует наибольшую длину ключей: 128 бит. Отсюда, CAST5-128.

==={{a name="p4"}}3DES===

DES означает Data Encryption Standard, Стандарт шифрования данных. Этот алгоритм был создан в 1977 году американским правительством (NIST и ##АНБ##) на основе разработки IBM. DES – это 64-битовый блочный шифр с 64-битовым ключом. К несчастью, последний бит каждого байта в ключе является битом четности, так что эффективная длина ключа составляет только 56 бит. Это слишком мало, атака грубой силой на специализированной машине займет менее суток. Тройной DES (Triple DES) или ##3DES## – это DES, выполняемый трижды с разными ключами. Таким образом, тройной DES – это 64-битовый блочный шифр со 168-битовым ключом (плюс 24 бита четности). Оригинальный DES исследовался многие годы, вследствие этого эксперты считают 3DES очень надежным. Недостатком является то, что он значительно медленнее всех остальных алгоритмов: DES сам по себе довольно медлителен из-за применения битовых перестановок, эффективно производимых на специальных микросхемах, но гораздо хуже на универсальных компьютерах, а с 3DES вам нужно выполнить три операции, чтобы получить защищенность двух. Единственная причина, по которой стоит применять тройной DES – это то, что он хорошо изучен. Это шифр для консерваторов.

3DES – наиболее интересный блочный шифр PGP. Многократное зашифрование делает шифр сильнее, но не обходится без проблем. Атака на двойное шифрование описана ниже. Кроме того, DES сам по себе не так хорош, как другие шифры. Существуют атаки на 16-раундное шифрование DES, что, в теории, делает 3DES самым сомнительным шифром PGP.

=====Дифференциальный криптоанализ=====
С помощью ##дифференциального криптоанализа## и атаки на основе подобранного открытого текста можно найти ключ DES, используя 2^^47^^ открытых текстов. ##Атака на основе подобранного открытого текста## заключается в том, что оппонент может предоставить любой по своему выбору открытый текст на шифрование и получить шифртекст. Это исключительно теоретическая атака, поскольку нереально собрать столько открытых текстов. Особым образом сконструированные S-блоки DES надежно противостоят дифференциальному криптоанализу, из чего можно сделать вывод, что АНБ знало об этой технике криптоанализа еще в 1977 году. Остальной мир услышал о ней от Эли ##Бихама## и Ади ##Шамира## лишь в 1990-м.

=====Линейный криптоанализ=====
##Линейный криптоанализ## еще более эффективен против DES. Это схожая техника, однако другая, открытая Мицуру ##Мациу## в 1993 году, с помощью которой можно провести против DES атаку на основе 2^^43^^ известных открытых текстов. При ##атаке на основе известного открытого текста## взломщик имеет доступ к некоторому количеству открытых текстов и соответствующих шифртекстов, но не может выбирать открытый текст для шифрования. Эта атака уже ближе к практике, хотя 2^^43^^ – все же слишком много. Атаку нельзя применить к случаю тройного DES, так что она не имеет практической ценности против PGP, однако демонстрирует, что блочный шифр не обязан храниться в секрете, даже если создан лучшими криптографами времени. ((*2))

S-блоки DES не выбирались с учетом повышенной устойчивости к линейному криптоанализу, так что можно допустить, что АНБ не знало этой техники в 1977 году.

Обе эти методики описаны в ((../Библиография#b18 [18])), страницы 285-293.

=====Атаки на многократное шифрование=====
Эффективная стойкость 3DES – 112 бит, не 168. Логично предположить, что достичь такой стойкости можно было бы за два шифрования. Но это не так из-за ##атаки "встреча посередине"## ( ((../Библиография#b18 [18])), стр. 358). Для атаки грубой силой на DES по известному открытому тексту нужно провести 2^^56^^ шифрований. Если используется двойное шифрование, для атаки потребуется только 2^^57^^ пробных шифрований и еще память под 2^^56^^ блоков.

Для атаки с известным открытым текстом атакующий располагает шифртекстом ""C""vv1vv и открытым текстом ""P""vv1vv, так что

#||
||
  ##""C""vv1vv = ""E""vvk2vv ( ""E""vvk1vv ( ""P""vv1vv ))## |>>>(3.1)>>>||
||#

Для всех возможных ключей //k//, он шифрует и сохраняет результат ##""E""vvkvv (""P""vv1vv)##. Сделав это, он пытается вычислить для всех ключей выражение ##""D""vvlvv (""C""vv1vv)## и ищет результат вычислений в памяти: если он находит соответствие ##""E""vvkvv (""P""vv1vv) = ""D""vvlvv (""C""vv1vv)##, то //kl// – вероятно, его искомый ключ. Мы допускаем, что у взломщика есть в наличии несколько известных открытых текстов, на которых он может проверить, правильный ли найден ключ, и попробовать другие //l//, если неправильный.

Хотя дополнительные требования к памяти под 2^^56^^ блоков не тривиальны, все же ясно, что двойное шифрование не сильно увеличивает безопасность. Для тройного шифрования есть похожая атака со встречей посередине, трубущая ##2^^2n^^## вычислений и память под ##2^^n^^## блоков. Ранние реализации тройного шифрования должны были быть обратно совместимы с одиночным зашифрованием, поэтому в них использовался метод зашифрования-расшифрования-зашифрования (EDE): ##C = ""E""vvk3vv ( ""D""vvk2vv ( ""E""vvk1vv ( P )))##. Это не влияло на стойкость, но если вы выбирали ##k1 = k2 = k3##, это было равносильно однократному зашифрованию.

Чтобы еще более все усложнить, есть также схема тройного шифрования, требующая только два ключа: ##C = ""E""vvk1vv ( ""D""vvk2vv ( ""E""vvk1vv ( P )))##. Это весьма неплохой подход, если вы ограничены в объеме памяти для размещения ключа, но она не столь устойчива, как тройное шифрование. Смотрите ((../Библиография#b18 [18])), стр. 359.

PGP использует 3DES со 168-битовым ключом (действительная длина) в режиме EDE, что дает эффективную стойкость 112 бит.

==={{a name="p5"}}Rijndael/AES===

В 2000 году блочный шифр ##Rijndael## был выбран на звание нового Улучшенного стандарта шифрования (##Advanced Encryption Standard##), заменив тем самым стандарт DES. PGP 6.5.8 не имеет поддержки AES, но в версиях от 7.0 и выше она есть. ##AES## это очень новый шифр, и атаки на него неизвестны.

Rijndael разработан Джоан ##Даймен## и Винсентом ##Рижменом##. У него необычный дизайн: он использует операции над полиномами, и расшифрование проходит не так быстро, как зашифрование. Размер блока составляет 128 бит (вдвое больше, чем у других шифров), а длина ключа – 128, 192 или 256 бит. Для дополнительной информации смотрите http://csrc.nist.gov/encryption/aes/rijndael/

==={{a name="p6"}}Режимы шифрования===

Блочные шифры можно применять несколькими способами, называемыми ##режимами шифрования##. Самый недальновидный способ, называемый режимом простой замены (##Electronic Codebook Mode, ECB##), состоит в том, чтобы разбить входные данные на блоки и по отдельности зашифровать каждый блок. У этого режима есть недостатки: если на вход подаются повторяющиеся структуры (множество одинаковых символов, например), они будут видны и на выходе. Другая проблема заключается в том, что одинаковый открытый текст будет всякий раз давать одинаковый шифртекст. И последнее, но не менее важное: взломщик может предсказуемо изменять данные, переставляя или повторяя зашифрованные блоки.

Для преодоления этих проблем существуют еще три режима: ((*3)) CBC, CFB и OFB. PGP использует режим ##CFB##, поэтому он будет описан подробней. CFB означает ##Cipher Feedback Mode## (гаммирование с обратной связью). Режим CFB, реализованный в PGP, был разработан PRZ и имеет некоторые отличия от классического варианта. Более подробно они описаны в ((../Библиография#b3 [3])).

====CFB====

CFB-алгоритм использует некоторый объем памяти, называемый //регистром сдвига//, размер которого равен размеру блока используемого шифра (т.е. блока данных; обычно это 8 байт). Чтобы зашифровать блок, он просто объединяется операцией XOR с содержимым регистра. Если шифруемый блок не полный, но короче, чем длина регистра сдвига, вы берете первые байты регистра. После использования (части) регистра, он сдвигается и заполняется последним зашифрованным блоком. Если была использована только часть регистра, а вход еще не завершен, этот процесс называется //синхронизацией//. Пусть ##""C""vvivv## будет //i//-ным блоком шифртекста, ##R## – регистром, а ##""P""vvivv## – //i//-ным блоком открытого текста, тогда

#||
||
  ##""C""vvivv = ""P""vvivv &#8853; R ;## |##R = E ( ""C""vvi-1vv )##|>>>(3.2)>>>||
||#

Чтобы начать шифрование, алгоритм шифрует один состоящий из нулей блок, и шифртекст заполняет регистр. Затем //вектор инициализации// (ВИ), представляющий собой один блок случайных байтов, шифруется в режиме CFB: результат отбрасывается, но задает начальное состояние регистра. Первые два байта ВИ шифруются вновь, что запускает синхронизацию. Теперь можно зашифровывать данные.

Нестандартная часть реализации CFB в PGP заключается в том, что начальное состояние регистра не просто устанавливается, а определяется путем обработки случайных данных, а также в том, что он в любой момент позволяет обрабатывать сокращенные неполные блоки: когда шифруется множество больших чисел, синхронизация происходит после каждого числа. Эти небольшие нюансы не влияют на безопасность. Повторение первых двух случайных байт становится чем-то вроде контрольное суммы и позволяет вам обнаружить, что вы используете неправильный ключ. ((*4)) Хорошим свойством этого режима является то, что вам не нужно заполнять последние байты неполного блока.

====Проблемы CFB====

Серьезной уязвимостью CFB представляется возможность вносить предсказуемые изменения в байты последнего блока: если вы измените биты в последней части зашифрованных данных, соответствующие биты расшифрованного текста также будут изменены. PGP обнаружит такие модификации, если зашифрованные данные были подписаны. Но иногда данные не подписывают: если вы использовали PGP, чтобы зашифровать файл паролем, он не будет полностью защищен от изменений. Секретные ключи тоже зашифрованы, но не подписаны. Это большая проблема, ведь все режимы шифрования разработывают с защитой от изменений, однако она не срабатывает для последнего блока. Атака Климы-Росы из параграфа ((../БагиАтаки/ЧешскаяАтака "Чешская атака на закрытый ключ")) использует эту брешь.

Более теоретический недостаток CFB в том, что он уязвим для атаки с подобранным шифртекстом, описанной в ((../Библиография#b11 [11])). В этой атаке взломщик может получить расшифрование любого блока данных, кроме того который он атакует. Это довольно сильное допущение, но при некоторых обстоятельствах оно осуществимо. Оппонент может послать оригинальное сообщение со случайными байтами вместо последнего блока, а из расшифровки этого сообщения сможет определить, с каким блоком нужно выполнить XOR. Эта атака не представляет серьезной угрозы для PGP, но может быть интересна в других применениях CFB. ((*5))

====CBC====

Другой распространенный режим – это ##CBC##, или ##Cipher Block Chaining## (сцепление блоков шифртекста). PGP не использует этот режим непосредственно для шифрования, но он применяется внутри генератора случайных чисел (смотрите параграф [[../АнализИсходногоКода/СлучайныеЧисла "Случайные числа"]]). В этом режиме также есть регистр ##R##, всегда содержащий последний выход. Блок открытого текста объединяется операцией XOR с ##R## и затем шифруется.

#||
||
  ##""C""vvivv = E ( ""P""vvivv &#8853; R ) ;## |##R = ""C""vvi-1vv## |>>>(3.3)>>>||
||#

Этот режим не позволяет использовать неполные блоки в конце сообщения. Любые изменение, внесенные в шифртекст, повреждают весь данный блок.

++((ВидыАлгоритмов Назад)) | ((АсимметричныеАлгоритмы Дальше))++

----
++**((#1))** От англ. "cast" – "догадка", – //прим. пер.//++

++**((#2))** Возможно, а некоторые скажут, что и весьма вероятно, что разработчики намеренно старались сделать DES настолько слабым, какой он и есть.++

++**((#3))** В действительности, режимов значительно больше, но эти применимы ко всем блочным шифрам, и в реализациях они наиболее распространены, – //прим. пер.//++

++**((#4))** Этой особенностью режима CFB в PGP ((/FAQ/Криптография#q9 воспользовались)) в феврале 2005 года исследователи Мистер и Цуккерато, чтобы с помощью тайминг-атаки или дешифрующего оракула раскрыть часть зашифрованного текста. После публикации их работы стандарт OpenPGP был изменен с тем, чтобы отбрасывать синхронизирующие байты ВИ, а не помещать их в тэг "быстрой проверки" (Quick Check), – //прим. пер.//++

++**((#5))** Такая атака с участием дешифрующего оракула была ((/FAQ/Криптография#q6 проведена)) в 2002 году Шнайером, Джелладом и Катцем. Вставив произвольные данные между блоками шифртекста, каким-то образом убедив пользователя расшифровать такое сообщение, а потом получив в распоряжение "мусор", произведенный при расшифровании, взломщик может дешифровать это единичное послание. Мера безопасности, реализованная с тех пор в OpenPGP (MDC), обнаруживает подобные манипуляции с шифртекстом, – //прим. пер.//++

Ваше имя:
	Запомнить псевдоним (сохранить в cookie)
	OpenPGP-подписанный текст в кодировке Помощь
	Сохранить параметры OpenPGP в cookie

Для корректной работы разрешите в своем браузере показ изображений.

Пожалуйста, напишите, кого/что вы видите
на изображенной слева картинке. Если
там несколько персонажей/предметов,
перечислите их в именительном падеже
через пробел (одинаковых приводите во
множественном числе).

(осталось попыток на решение теста: 3)

Поддержка BBCode включена