Отправитель и получатель. Сообщения и шифрование 20 глава

k₂ = c'₂ Å p', затем p₂ = c₂ Å k₂
k₃ = c'₃ Å p₂, затем p₃ = c₃ Å k₃
k₄ = c'₄ Å p₃, затем p₄ = c₄ Å k₄

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

9.8 Режим выходной обратной связи

Режим выходной обратной связи (Output-feedback, OFB) представляет собой метод использования блочного шифра в качестве синхронного потокового шифра. Этот режим похож на CFB за исключением того, что nбитов предыдущего выходного блока сдвигаются в крайние правые позиции очереди (см. Рис. -11). Дешифрирование является обратным процессом. Такой режим называется n-битовым OFB. И при шифровании, и при дешифрировании блочный алгоритм работает в режиме шифрования. Это иногда называют внутренней обратной связью, потому что механизм обратной связи не зависит ни от потоков открытого текста, ни от потоков шифротекста [291]. Если размер блока алгоритма n, то n-битовый алгоритм OFB выглядит, как показано на :

C_i = P_i Å S_i, S_i = E_k(S_i-1)

P_i = C_i Å S_i, S_i = E_k(S_i-1)

S_i - состояние, независящее ни от открытого текста, ни от шифротекста.

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

Рис. -11. 8-битовый режим с выходной обратной связью

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

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

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

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

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

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

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

Анализ режима OFB [588, 430, 431, 789] показывает, что OFB стоит использовать только, когда размер обратной связи совпадает с размером блока. Например, 64-битовый алгоритм нужно использовать только в 64-битовом режиме OFB. Несмотря на то, что правительство США разрешает для DES и другие размеры обратных связей DES [1143], избегайте их.

Режим OFB выполняет XOR над потоком ключей и текстом. Этот поток ключей со временем повторяется. Важно, чтобы он не повторялся для того же ключа, в противном случае нарушается безопасность. Когда размер обратной связи равен размеру блока, блочный шифр переставляет m-битовые значения (где m - это размер блока), и средняя длина цикла составляет 2^m -1. При длине блока 64 бита это очень большое число. Когда размер обратной связи nменьше длины блока, средняя длина цикла падает до приблизительно 2^m/2. Для 64-битного шифра это только 2³² - что явно недостаточно.

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

Потоковые шифры также могут работать в режиме OFB. В этом случае ключ влияет на функцию следующего состояния (см. Рис. -13). Функция выхода не зависит от ключа, очень часто она является чем-то простым, например, одним битом внутреннего состояния или результатом XOR нескольких битов внутреннего состояния. Криптографически сложной является функция следующего состояния, которая зависит от ключа. Этот метод также называется внутренней обратной связью [291], потому что механизм обратной связи является вложенным по отношению к алгоритму генерации ключей.

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

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

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

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

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

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

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

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

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

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

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

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

C_i = E_k(P_i Å F_i), F_i+1 = F_i Å C_i

P_i = F_i Å D_k(C_i), F_i+1 = F_i Å C_i

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

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

Режим распространяющегося сцепления блоков шифра (propagating cipher block chaining, PCBC)[1080] похож на режим CBC за исключением того, что и предыдущий блок открытого текста, и предыдущий блок шифротекста подвергаются операции XOR с текущим блоком открытого текста перед шифрованием (или после шифрования) (см. Рис. -15).

C_i = E_k(P_i Å C_i-1 Å P_i-1)

P_i = C_i-1 Å P_i-1 Å D_k(C_i)

PCBC используется в Kerberos версии 4 (см. раздел 24.5) для выполнения за один проход и шифрования, и проверки целостности. В режиме PCBC ошибка шифротекста приводит к неправильному дешифрированию всех последующих блоков. Это означает, что проверка стандартного блока в конце сообщения обеспечивает целостность всего сообщения.

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

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

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

Сцепление блоков шифра с контрольной суммой (cipher block chaining with checksum, CBCC)представляет собой вариант CBC [1618]. Сохраняйте значение XOR всех уже зашифрованных блоков открытого текста, выполняя для каждого текущего блока открытого текста перед его шифрованием XOR с сохраняемым значением. CBCC обеспечивает, что любое изменение любого блока шифротекста изменит результат дешифровки последнего блока. Если последний блок содержит какую-нибудь константу или служит для проверки целостности, то целостность расшифрованного открытого текста может быть проверена с минимальными дополнительными накладными расходами.

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

Выходная обратная связь с нелинейной функцией (output feedback with a nonlinear function, OFBNLF)[777] представляет собой вариант и OFB,и ECB, где ключ изменяется с каждым блоком:

C_i = E_k(P_i), K_i = E_k(K_i-1)

P_i = D_k(C_i), K_i = E_k(K_i-1)

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

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

Возможны и другие режимы, хотя они используются нечасто. Сцепление блоков открытого текста (plaintext block chaining, PBC) похоже на CBC за исключением того, что операция XOR выполняется для с блока открытого текста и для предыдущего блока открытого текста, а не блока шифротекста. Обратная связь по открытому тексту (plaintext feedback, PFB) похожа на CFB за исключением того, что для обратной связи используется не шифротекст, а открытый текст. Существует также сцепление блоков шифротекста по различиям открытого текста (cipher block chaining of plaintext difference, CBCPD). Я уверен, что можно найти еще таинственнее.

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

9.11 Выбор режима шифра

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

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

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

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

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

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

OFB является хорошим выбором для систем с ошибками, так как в нем отсутствует распространение ошибки.

Берегитесь заумных режимов. Один из четырех основных - ECB, CBC, OFB и CFB - подойдет почти для любого приложения. Эти режимы не слишком сложны и, возможно, не уменьшат безопасности системы. Хотя возможно, что сложный режим повысит безопасность системы, более вероятно, что он только повысит ее сложность. Ни у одного из этих хитрых режимов не лучше в отношении распространения ошибки или устранения ее последствий.

9.12 Чередование

В большинстве режимов шифрование бита (или блока) зависит от шифрования предыдущих битов (или блоков). Часто это делает невозможным распараллелить шифрование. Например, рассмотрим аппаратное устройство, выполняющее шифрование в режиме CBC. Даже если блок содержит четыре микросхемы шифрования, работать может только одна. Следующей микросхеме для начала работы нужны результаты работы предыдущей.

Решением является чередование нескольких потоков шифрования. (Это не множественное шифрование, оно рассматривается в разделах 15.1 и 15.2). Вместо одной цепочки CBC используются четыре. Первый, пятый и, далее, каждый четвертый блок шифруются в режиме CBC с одним IV. Второй, шестой и, далее, каждый четвертый блок шифруются в режиме CBC с другим IV, так далее. Полный IV намного длиннее, чем без чередования.

Представьте себе шифрование четырех различных сообщений одним ключом с четырьмя различными IV. Все эти сообщения чередуются.

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

На Figure 9.16 показаны три параллельных потока, чередующихся в режиме CFB. Эта идея применима также к режимам CBC и OFBдля любого числа параллельных потоков. Только не забывайте, что для каждого потока нужен свой собственный IV. Не экономьте.

Рис. -16. Чередование трех шифрований CFB.

9.13 Блочные шифры против потоковых

Хотя блочные и потоковые шифры сильно отличаются, блочные шифры можно реализовать как потоковые, а потоковые шифры - как блочные. Лучшее определение различия я нашел у Рэньеры Рюппела (Ranier Rueppel) [1362.]:

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

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

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

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

10 Использование алгоритмов

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

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

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

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

Криптография в большинстве приложений использовалась вшивая, но успешные вскрытия не имели ничего общего с криптоанализом. Они были вызваны нечестными служащими, умными обманными действиями, тупыми реализациями, грубыми ошибками интеграции и случайными глупостями. (Я настоятельно рекомендую работу Росса Андерсона "Почему отказывают криптосистемы" (Ross Anderson, "Why Cryptosytems Fail") [44], ее должен прочитать каждый, работающий в этой области.) Даже NSA признало, что большинство сбоев систем безопасности в соответствующей области интересов обусловлены недостатками реализации, а не недостатками алгоритмов или протоколов [1119]. В таких случаях неважно, насколько хороша используемая криптография, успешные вскрытия полностью ее обходят.

10.1 Выбор алгоритма '

Когда приходит время оценивать и выбирать алгоритм, возможны различные варианты:

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

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

— Можно доверять личному консультанту, основываясь на вере в то, что беспристрастный консультант способен правильно оценить различные алгоритмы.

— Можно доверять правительству, основываясь на вере в то, что правительство не обманет своих граждан.

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

Проблематичен любой из этих вариантов, но первый кажется наиболее разумным. Доверчивость по отношению к производителю, правительству или консультанту опасна. Большинство тех, кто называет себя консультантами по безопасности (даже сотрудники фирм с громкими именами), обычно ничего не знают о шифровании. Большинство производителей продуктов, обеспечивающих безопасность, ничем не лучше. Самые лучшие криптографы мира работают в NSA, но они не скажут вам, что они знают. У них свои интересы, не совпадающие с интересами простых граждан. Каким бы вы ни были гением, создание своего алгоритма и его использование без объективного анализа откровенно глупо.

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

Уязвимой место этих рассуждений - это то, что нам неизвестны возможности различных военных криптоаналитических организаций.

Какие алгоритмы может вскрыть NSA? Большинству из нас узнать это все равно не удастся. Если в момент ареста у вас будет компьютерный жесткий диск, шифрованный с помощью DES, вряд ли ФБР предъявит расшифрованный открытый текст на суд - то, что они вскрыли алгоритм, скорее всего является большим секретом, чем любая раскрытая информация. В ходе Второй мировой войны союзники не использовали расшифрованные немецкие сообщения, пока им не удавалось добыть эту информацию и из других источников. Единственный способ заставить NSA признать возможность взломать конкретный алгоритм - это зашифровать что-то настолько значительное, что опубликование секрета будет стоить признания возможности вскрывать алгоритм. Или, еще лучше, придумайте что-то действительно смешное и пошлите эту шутку шифрованной электронной почтой таинственными символами в подозрительные страны. Сотрудники NSA тоже люди, я сомневаюсь, что даже им удастся сохранить в тайне хорошую шутку.

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

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

Алгоритмы на экспорт

Алгоритмы для экспорта из Соединенных Штатов должно одобрить правительство США (а в действительности NSA - см. раздел 2.5.1). Широко распространено мнение, что к экспорту разрешены только те алгоритмы, которые может взломать NSA. Хотя этого никто не признал письменно, есть ряд требований, которые по слухам NSA предъявляет компаниям, желающим экспортировать свои криптографические продукты:

— Вставлять по одному биты ключа в шифротекст.

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

— Использовать фиксированный IV или шифровать в начале каждого сообщения фиксированный заголовок. Это облегчает вскрытие с известным открытым текстом.

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

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

10.2 Криптография с открытыми ключами против симметричной криптографии

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