Режимы шифрования данных, или, когда сильный шифр не спасает

программирование

Режимы шифрования: почему простая замена небезопасна.

Почему-то каждый третий мнит себя экспертом по безопасности, пишет «безопасные» программы для шифрования данных, но даже не подозревает, что существуют и другие режимы шифрования, кроме известного как ECB. И этим грешат не только студенты в своих дипломных работах (головы бы поотрывал их научрукам за такое), но и «серьёзные» разработчики.

Например, программист на сайте uk-swingers.com шифровал номера кредитных карточек (!), используя простой алгоритм RC4 и постоянный ключ. Ломалось очень просто. К счастью, уже исправлено.  Другие товарищи использовали сложение по модулю два для шифрования важных данных. Третий товарищ защитил диплом по безопасности, и шифрование секретной базы данных опять-таки выполнялось по модулю два. Четвертый шифровал AES’ом тонны информации (в режиме ECB, разумеется), при этом не потрудившись даже ее сжать. Этот печальный список можно продолжать и продолжать…

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

Начнем с теории.

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

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

Режим простой замены

Режим простой замены (Electronic Codebook, ECB) является простейшим режимом шифрования. Сообщение разбивается на блоки, каждый из которых шифруется (раздельно). Таким образом, из идентичных блоков открытого текста получаются идентичные блоки шифротекста. Данный режим шифрования не обеспечивает достаточной конфиденциальности сообщения, вследствие чего его использование в криптографических протоколах не рекомендуется.

Уравнение шифрования: Ci=Ekey(Pi).
Уравнение расшифрования: Pi=Dkey(Ei).
В вышеприведенных формулах (и далее): C — шифротекст; P — открытый текст; EKEY — операция шифрования данных с ключом KEY; DKEY — операция расшифрования данных с ключом KEY.

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

Режим гаммирования

Поточное гаммирование

В режиме гаммирования (также известном как Stream Mode, SM, поточный режим) открытый текст складывается по модулю два с гаммой шифра (вместо операции сложения по модулю два можно использовать любую обратимую операцию). Гамма шифра получается следующим образом: при помощи псевдослучайного генератора формируется начальная (предварительная) гамма, которая шифруется в режиме простой замены (таким образом получается основная гамма). Начальное значение псевдослучайного генератора (называемое инициализационным вектором (Initialization Vector, IV) или синхропосылкой) не является секретным и передается по каналу в открытом виде. Если последний блок неполный (его длина меньше стандартного для данного алгоритма размера блока), берется только необходимое количество бит гаммы.

В режиме гаммирования операции зашифрования и расшифрования являются симметричными.

Гаммирование с обратной связью

Режим гаммирования с обратной связью (Cipher Feedback, CFB) — «близкий родственник» режима сцепления блоков — превращает блочный шифр в самосинхронизирующийся поточный шифр.

Уравнение зашифрования: Ci=Ekey(Ci-1)⊕Pi.
Уравнение расшифрования: Pi=Ekey(Ci-1)⊕Ci.
В приведенных выше формулах C0 — синхропосылка.

Обычно размер блока обратной связи совпадает с размером буфера (рас)шифрования; в общем случае, это может быть не так. Если размеры не совпадают, то на вход следующего цикла криптографического преобразования поступает (bs) младших бит шифротекста (при шифровании) или открытого текста (при расшифровании), дополненные s битами полученного на предыдущем шаге шифротекста или открытого текста соответственно. При получении очередных s бит шифротекста (открытого текста), открытый текст (шифротекст) складывается по модулю два с s старшими битами результата шифрования. В приведенных выше формулах b — размер буфера (рас)шифрования, s — размер буфера обратной связи.

В режиме гаммирования с обратной связью шифрование не может выполняться параллельно, расшифрование — может (но с некоторыми ограничениями).

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

Гаммирование с обратной связью по выходу

Режим гаммирования с обратной связью по выходу (Output Feedback, OFB) преобразует блочный шифр в синхронный поточный шифр: генерируемые ключевые блоки складываются по модулю два с блоками открытого текста.

Вследствие того, что операция сложения по модулю два является симметричной, процесс шифрования и расшифрования выглядит одинаково.

Уравнение зашифрования: Ci=Ekey(Oi-1)⊕Pi.
Уравнение расшифрования: Pi=Ekey(Oi-1)⊕Ci.
В приведенных выше формулах O0синхропосылка.

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

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

Изменение одного бита открытого текста (шифротекста) приводит к изменению соответствующего бита шифротекста (открытого текста); данное свойство позволяет использовать многие корректирующие коды даже до операции шифрования.

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

Простое сцепление

В режиме сцепления блоков (Cipher-block Chaining, CBC) каждый блок открытого текста складывается по модулю два с предыдущим блоком шифротекста, а затем шифруется. Таким образом, каждый блок шифротекста зависит от всех обработанных блоков открытого текста. Чтобы каждое сообщение было уникальным, при обработке первого блока открытого текста должна использоваться синхропосылка. Режим сцепления блоков является наиболее часто используемым.

Уравнение шифрования: Ci=Ekey(PiCi-1).
Уравнение расшифрования: Pi=Dkey(Ci)⊕Ci-1.
В приведенных выше формулах C0 — синхропосылка.

Очевидно, что шифрование блоков не может выполняться параллельно, а для расшифрования достаточно двух соседних блоков шифротекста (вследствие чего расшифрование может выполняться параллельно).

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

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

Режим распространяющегося сцепления блоков (Propagating CBC, PCBC) является модификацией предыдущего метода. Основным отличием данного режима от предыдущего является то, что изменения в шифротексте распространяются на все блоки как при расшифровании, так и при шифровании, вследствие чего (рас)шифрование блоков не может выполняться параллельно.

Уравнение шифрования: Ci=Ekey(PiPi-1Ci-1).
Уравнение расшифрования: Pi=Dkey(Ci)⊕Pi-1Ci-1.

В приведенных выше формулах P0C0 — синхропосылка.

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

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

Режим счетчика (Counter, CTR) преобразует блочный шифр в поточный. Его можно рассматривать как гибрид режимов простой замены и гаммирования с обратной связью по выходу. Ключевой блок генерируется путем зашифрования последовательных значений счетчика и затем складывается по модулю два с открытым текстом или шифротекстом. Операции (рас)шифрования могут выполняться параллельно, так как для (рас)шифрования очередного блока необходимо знать только значение счетчика.

Вследствие того, что операция сложения по модулю два является симметричной, процесс шифрования и расшифрования выглядит одинаково.

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

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

Изменение одного бита открытого текста (шифротекста) приводит к изменению соответствующего бита шифротекста (открытого текста).

Синхропосылка

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

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

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

Рекомендация NIST SP 800-38A рекомендует один из следующих подходов для генерации непредсказуемых синхропосылок:

  1. Применение функции шифрования с тем же ключом, что и для шифрования открытого текста, к одноразовому значению;
  2. Использование генератора случайных чисел, одобренного FIPS (Federal Information Processing Standard, федеральный стандарт обработки информации).

Эксперимент

Методика эксперимента: в качестве исходных данных брался этот файл и переводился в формат RGB. Затем на полученный файл натравливалась тестовая программа, которая выполняла шифрование в различных режимах; результат помещался в новый файл. Ключ шифрования — слово password, инициализационный вектор получался путем хеширования по ГОСТ 34.311-95. Шифрованные файлы переводились в из формата RGB в PNG и просматривались на экране  Помимо всего прочего считалась энтропия полученных файлов (сим преследовалась цель убедиться, что «сильный» шифр может использоваться в качестве хорошего источника случайных чисел). Энтропия исходного файла составляет 3.37144 бит.

Результаты сведены в таблицу.

Энтропия зашифрованного сообщения для различных шифров и режимов шифрования
ECB CBC CFB CTS OFB CTR PCBC
NULL 3.37144 7.92382 7.92382 3.53878 3.37197 3.65126 3.37197
XOR 5.42685 7.93968 7.94004 2.19935 5.27889 5.66991 5.27889
TEA 6.30925 7.99976 7.99973 7.99975 7.99974 7.99971 7.99977
XTEA 6.33340 7.99974 7.99979 7.99978 7.99975 7.99975 7.99975
XXTEA 7.90143 7.99974 7.99977 7.99973 7.99972 7.99974 7.99975
Q128 6.85842 7.99977 7.99974 7.99975 7.99976 7.99978 7.99976
FROG 7.77603 7.99977 7.99977 7.99972 7.99975 7.99972 7.99975
CAST-128 6.32833 7.99979 7.99973 7.99976 7.99973 7.99978 7.99974
CAST-256 6.81389 7.99971 7.99976 7.99977 7.99975 7.99974 7.99973
IDEA 6.30512 7.99976 7.99977 7.99976 7.99976 7.99975 7.99975
Blowfish 6.28322 7.99974 7.99975 7.99978 7.99977 7.99972 7.99976
Rijndael 6.74933 7.99977 7.99978 7.99974 7.99976 7.99977 7.99977
DES 6.33022 7.99982 7.99970 7.99975 7.99977 7.99973 7.99975
GOST 6.33646 7.99974 7.99975 7.99977 7.99971 7.99976 7.99972
GOST-X 6.20684 7.99975 7.99976 7.99977 7.99977 7.99975 7.99974
TripleDES EDE 6.33022 7.99982 7.9997 7.99975 7.99977 7.99973 7.99975
TGOST 6.33556 7.99977 7.99976 7.99978 7.99976 7.99977 7.99973
TripleDES3 6.95098 7.99975 7.99980 7.99976 7.99973 7.99970 7.99974
TGOST3 7.01890 7.99977 7.99977 7.99978 7.99977 7.99977 7.99972
TGOSTX3 6.98361 7.99977 7.99968 7.99977 7.99976 7.99973 7.99976

Примечание: размерность приведённых в таблице данных — биты.

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

По результатам тестирования мы видим, что режим простой замены для шифрования данных лучше не использовать. Кстати, в стандарте шифрования ГОСТ 28147-89 отмечено, что режим простой замены может быть использован только для шифрования ключевых данных. Из таблицы видно, что каким бы ни был шифр, в режиме простой замены он не может обеспечить достаточной конфиденциальности сообщения.

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

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

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

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

  • представленное выше изображение;
  • файл в формате MS Word 2003;
  • фотография в формате JPEG;
  • файл из 1024 символов с кодом FF16;

Результаты эксперимента представлены в таблице

NULL XOR ГОСТ 28147-89
Простая замена 3.37144
4.48239
7.95642
0
5.42685
5.85078
7.98966
2.75
6.33646
7.76984
7.99839
3
Сокрытие шифротекста 3.53878
5.17479
7.99782
0
2.19935
4.71443
7.99633
0.0873988
7.99977
7.99921
7.99844
7.78699
Гаммирование с обратной связью по выходу 3.37197
4.48239
7.95641
0
5.27889
5.80711
7.98579
2.375
7.99971
7.99930
7.99845
7.80087
Гаммирование с обратной связью 7.92382
7.97188
7.99839
1
7.94004
7.95779
7.99848
2.375
7.99975
7.99917
7.99829
7.80648
Сцепление блоков шифротекста 7.92382
7.97188
7.99839
1
7.93968
7.95869
7.99827
2.375
7.99974
7.99921
7.99864
7.82002
Распространяющееся сцепление блоков шифротекста 3.37197
4.48239
7.95641
0
5.27889
5.80711
7.98579
2.375
7.99972
7.99931
7.99840
7.83605
Счетчик 3.65126
4.63377
7.95941
0.233209
5.66991
6.05639
7.98633
2.89398
7.99976
7.99930
7.99840
7.80864

Примечание: размерность данных в таблице — биты.

Делать выводы возлагаем на читателя…

Related posts

Комментарии к статье “Режимы шифрования данных, или, когда сильный шифр не спасает”

  1. Михаил

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

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

Оставить комментарий