Криптография, 03 лекция (от 15 октября)

Материал из eSyr's wiki.

[править] Симметричные шифры

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

Если у нас блок размером 128 бит, сколько способов существует получить выходной блок такого же размера? Всего блоков 2^128. Всего взаимно однозначных отображений столько сколько число перестановок, это меньше чем 2^128!

У нас есть фиксированный блок на входе и такой же на выходе.

128 бит это довольно немного. Если нам надо зашифровать 10 Тб, как мы будем это делать?

По кускам независимо. Возьмем текст, разобъем на куски по 7 байт и каждый блок зашифруем независимо. Кто возражает? один человек.

Такая схема называется ECB -- electronic code book.

На что это будет похоже на практике? Картинка зашифрованная в режиме ECB -- изображение отчасти восстаналивается. Размер блока в 128 бит маленький, много повторений, которые будут шифроваться одинаково.

Что сделать чтобы этого не происходило. Отдельные ключи? Слишком много ключа.

Брать вместо ключа зашифрованный текст?

Самый первый способ -- CBC(cipher block changing).

Генерируем инициализационный вектор. Он генерирует случайность. Складываем его с открытым текстом и результат шифруем. Складываем со вторым блоком, шифруем, и так далее.

Этим мы добиваемся зависимости вида зашифрованного блока от того, как выглядел текст до него.

Инициализационный вектор несекретный. Почему?

Инициализационный вектор передается вместе с сообщением в качестве первого.

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

Как ломать CBC? Какие существуют проблемы?

1. Фиксированный инициализационный вектор. Если у нас есть сообщения с одинаковыми инициализационными векторами то для первого блока мы переходим фактически к простой замене.
1. Совпадение блоков шифротекста. Дает информацию об открытом тексте. Какую?
c_i = c_j c_i= E(c_{i-1} + t_i)
          c_j= E(c_{j-1} + t_j)
          c_{i-1} + t_i = c_{j-1} + t_j
          c_{i-1} + c_{j-1} = t_i + t_j

Если у нас есть такой идеальный шифр, то его выходные блоки неотличимы от белого шума. Считая, что вероятность появления любого блока в выходном блоке одинакова, какова вероятность, что два блока совпадут? Положим длину блока 64 бит. Сколько нам необходимо блоков чтобы они совпали с вероятностью 90 процентов?

Какова вероятность того, что первый блок не совпадет ни с одним из n?

Есть оценка. Для того, чтобы два блока совпали с вероятностью 1/2 при размере в 64 бита блока нам надо 2^32 блока (размером 64 бита).

Сколько это байт? 32Гб.

При скорости 1 Гбит в секунду. 256 секунд. Чуть блоьше 4 минут. 4.27.

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

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

Поэтому des и гост-89 этого не выдерживают. Строго говоря, гост не предусматривает cbc. В других стандартах и в частности в госте используется cfb.

Точно так же есть открытый вектор, который мы шифруем и складываем с открытым текстом. Защищен ли cfb от коллизий блоков?

c_i = c_j c_i = E(c_{i-1}) + t_i c_j = E(c_{j-1}) + t_j

E(c_{i-1}) + t_i = E(c_{j-1}) + t_j

c_{i+1} = E(c_i) + t_{i+1} c_{j+1} = E(c_j) + t_{j+1} E(c_i) = E(c_j) E(c_j) = c_{j+1} + t_{j+1} c_{i+1} + t_{i+1} = c_{j+1} + t_{j+1}

Теперь ещё проблемы -- нельзя накопить трафика впрок если нам надо зашифровать внезапно всплеск трафика.

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

Последовательно шифруем гамму, складывая ею с блоками шифратекста.

Поток гаммы для шифрования генерируется вне зависимости от поступающих данных. Можно запасти впрок.

Что плохо?

Перекрытие гаммы. Если мы получим совпадающие гаммы.

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

Главная проблема OFB. Представьте, что у нас поток данных, зашифрованный OFB.

Представим, что передаем финансовые транзакции фиксирвоанного вида. Где начиная с 25 байта всегда идет сумма. И злоумышленник поменяет ноль на единицу. Независимо от гаммы у нас сменится бит расшифрованного текста.

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

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

Чего хорошего?

Непредсказуемость. Да, хоть и меньше, чем у всех предыдущих.

Можно ли готовить заранее гаммы? Можно.

Какие ещё свойства по сравнению с OFB? Гарантированно разные гаммы. Зато первый блок от второго отличается всего на один бит и если нам не повезет мы наблдюдаем попытку дифференциальногоо криптоанализа организованную самим шифрующим.

Большое достоинство -- поскольку мы знаем значение счетчика наперед, то мы можем распараллелить генерирование гаммы. У OFB генерирование гаммы сугубо последовательно и однопоточно.

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

Это что касается режимов шифрования.

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

А что же делать, если данные меньше блока?

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

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

Итак что сделать, чтобы представить данные так, чтобы было понятно сколько их было?

Всё это называется паддингом.

Существует несколько способов его обеспечить.

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

Второй механизм широко применяется, но имеет несколько проблем.

В частности делает реализуемой padding oracle atack. В данном случае оракул это черный ящик, который может давать детерминированный набор ответов.

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

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

Такое невинное свойство позволяет реализовывать весьма неприятные атаки.

В частности уязвимость microsoft 01210 в asp.net оказалась возможна именно потому что в механизме сессионности была обнаружена уязвимость такого типа.

Как работает пэддинг оракл?

Представим себе что у нас есть оракул.

У нас может быть строчка из 8 8восьмерок, 7 семерок, и так далее. Не очень много строчек. Чего мы можем делать? Самая простая атака состоит в следующем -- мы можем попытаться передать все варианты последнего блока, передаваемого пэддинг ораклу, в попытке высянить какова длина блока с открытым текстом.

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

Если в какой-то момент это значение сработало, это значит что мы послали блок, который был успешно расшифрован нашим оракулом.

Давайте еще раз.

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

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

если мы говорим про блочный шифр в режиме не ctr или ofb, не каждая строка будет правильно расшифрована с паддингом, потому что правильно расшированная строка обязательно должна заканчиваться на один и 8 вариантов. Чего мы можем сделать.

Давайте манипулировать последним байтом последнего блока. Возьмем последний байт последнего блока и перберем все вохможные варианты этого последнего байта.

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

Если мы знаем, что последний блок имеет 7 байт осмысленного текста, то мы знаем что последний байт всегда 1. Тем не менее если мы взглянем на cbc, то у нас не все байты шифруются независимо.

Внутри у нас xor. Если мы манипулирвем последним байтом шифротекста, мы манипулируем последним байтом открытого текста. Перебрав все варианты последнего байта шифротекста, то мы прееберем все байты открытого текста.

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

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

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

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

Итак, есть две задачи, которые надо свести в одну.