Дополнение (криптография)

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Дополнение (англ. padding) в криптографии — добавление ничего не значащих данных к зашифровываемой информации, нацеленное на повышение криптостойкости. Различные техники дополнения применялись в классической криптографии [⇨], обширное применение техники дополнений нашли в компьютерных системах шифрования.

Классическая криптография[править | править код]

Официальные сообщения часто начинаются и заканчиваются предсказуемо, например, «С уважением, …». Основная цель применения дополнения к классическими шифрами — лишить криптоаналитика возможности использовать такую предсказуемость при криптоанализе известного текста[1]. Случайная длина дополнения также не позволяет криптоаналитику узнать точную длину сообщения.

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

Симметричная криптография[править | править код]

Хеш-функции[править | править код]

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

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

Режим шифрования[править | править код]

Electronic codebook (ECB) и cipher-block-chaining (CBC) — примеры режимов шифрования. Режимы шифрования для алгоритмов с симметричным ключом требуют, чтобы длина сообщения была кратна размеру блока, поэтому сообщение, возможно, необходимо дополнить, чтобы привести его к подходящей длине.

Недостатком дополнения является то, что оно делает текст уязвимым для атакам Оракула[en]. Данная атака позволяет злоумышленнику получить знания о передаваемом сообщении, не атакуя блочный шифр примитивно; этой атаки можно избежать, если убедиться, что атакующий не может получить никаких знаний об удалении добавленных байтов. Это может быть достигнуто путём проверки кода аутентификации сообщений (MAC) или цифровой подписи перед удалением байтов заполнения.

Дополнение битами[править | править код]

Дополнение битами может быть применено к сообщению любой длины. Сообщение дополняется одним единичным битом ('1') и некоторым количеством нулевых битов ('0'). Количество добавленных нулевых битов зависит от границы блока, до которой необходимо дополнить сообщение. В битных терминах это «1000 … 0000». Этот метод может быть использован для дополнения сообщений с любым числом битов, абсолютно не обязательно, чтобы они составляли целое число байт. Например, сообщение, состоящее из 23 бит, дополняется 9 битами, чтобы заполнить 32-битовый блок:

… | 1011 1001 1101 0100 0010 0111 0000 0000 |

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

Дополнение байтами[править | править код]

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

ANSI X.923[править | править код]

В ANSI X.923 байты дополняются нулями и последний байт определяет границу дополнения или количество добавленных байтов.

Пример: В следующем примере блок имеет размер 8 байтов, и требуется дополнение 4 байтами.

... | DD DD DD DD DD DD DD DD | DD DD DD DD 00 00 00 04 |
ISO 10126[править | править код]

В ISO 10126[2][3] дополнение должно быть заполнено случайными байтами, а последний байт должен показывать количество добавленных байтов.

Пример: В следующем примере блок имеет размер 8 байтов, и требуется дополнение 4 байтами.

... | DD DD DD DD DD DD DD DD | DD DD DD DD 81 A6 23 04 |
PKCS7[править | править код]

PKCS#7 описано в RFC 5652.

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

01
02 02
03 03 03
04 04 04 04
05 05 05 05 05
etc.

Данный метод дополнения (также как и два предыдущих) хорошо определён, только если N меньше, чем 256.

Пример: В следующем примере блок имеет размер 8 байтов, и требуется дополнение 4 байтами

... | DD DD DD DD DD DD DD DD | DD DD DD DD 04 04 04 04 |
ISO/IEC 7816-4[править | править код]

ISO/IEC 7816-4:2005[4] идентичен схеме дополнения битами, примененной к тексту, состоящему из N байтов. На практике это значит, что первый дополнительный байт обязательно имеет значение '80', а за ним следует, если это необходимо, от 0 до N-1 байтов '00' до тех пор, пока не будет достигнута граница блока. ISO/IEC 7816-4 является стандартом связи для смарт-карт и сам по себе не содержит каких-либо криптографических спецификаций.

Пример: В следующем примере блок имеет размер 8 байтов, и требуется дополнение 4 байтами

... | DD DD DD DD DD DD DD DD | DD DD DD DD 80 00 00 00 |

Следующий пример показывает дополнение только одним байтом:

... | DD DD DD DD DD DD DD DD | DD DD DD DD DD DD DD 80 |

Дополнение нулями[править | править код]

Все байты, которыми необходимо дополнить, заполняются нулями. Схема дополнения нулями не признана стандартом, хотя она описана как метод дополнения 1 для хеш-функций и MAC в ISO/IEC 10118-1[5] и ISO/IEC 9797-1.[6]

Пример: В следующем примере блок имеет размер 8 байтов, и требуется дополнение 4 байтами

... | DD DD DD DD DD DD DD DD | DD DD DD DD 00 00 00 00 |

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

Криптография с открытым ключом[править | править код]

В криптографии с открытым ключом дополнение это способ приготовления сообщения для шифрования или подписи следующими схемами: PKCS#1, OAEP, PSS, PSSR, IEEE P1363 EMSA2 и EMSA5. Современная форма дополнения для асимметричных примитивов применяется с алгоритму RSA, когда он используется для шифрования ограниченного количества байт.

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

Анализ трафика[править | править код]

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

В качестве другого примера, при шифровании потоков Voice Over IP, которые используют кодирование с попеременной битовой скоростью, число битов в единицу времени не скрыто, и это может служить для предположения голосовой фразы.[7]

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

См. также[править | править код]

Примечания[править | править код]

  1. Гордон Уэлчман, The Hut Six Story: Breaking the Enigma Codes, p. 78.
  2. ISO catalog, ISO 10126-1:1991. Дата обращения: 8 декабря 2015. Архивировано 9 апреля 2016 года.
  3. ISO catalog, ISO 10126-2:1991. Дата обращения: 8 декабря 2015. Архивировано 9 апреля 2016 года.
  4. ISO catalog, ISO/IEC 7816-4:2005. Дата обращения: 8 декабря 2015. Архивировано 4 марта 2016 года.
  5. ISO/IEC 10118-1:2000 Information technology — Security techniques — Hash-functions — Part 1: General. Дата обращения: 8 декабря 2015. Архивировано 18 апреля 2016 года.
  6. ISO/IEC 9797-1:1999 Information technology — Security techniques — Message Authentication Codes (MACs) — Part 1: Mechanisms using a block cipher. Дата обращения: 8 декабря 2015. Архивировано 9 апреля 2016 года.
  7. Uncovering Spoken Phrases in Encrypted Voice over IP Conversations