Padding (криптография) - Padding (cryptography)

Эта статья о криптографии. Чтобы узнать о других значениях этого термина, см. Padding (значения).

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

Классическая криптография

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

Известный пример классической набивки, вызвавший большое недоразумение: "чудеса мира "инцидент, который чуть было не привел к потере союзников во Второй мировой войне Битва у Самара, часть большего Битва при заливе Лейте. В этом примере Адмирал Честер Нимиц, то Главнокомандующий Тихоокеанским флотом США во время Второй мировой войны отправил следующее сообщение Адмирал Булл Хэлси, командующий оперативной группой тридцать четыре (основной флот союзников) в битве при заливе Лейте 25 октября 1944 г .:^[2]

Где, повторяю, где целевая группа тридцать четыре?^[3]

С обивкой (жирным шрифтом) и метаданные добавлено, сообщение стало:

ТРОТКИ НА ВОДУ GG ОТ CINCPAC ACTION COM THIRD FLEET INFO COMINCH CTF SEVENTY-SEVEN X ГДЕ RPT ГДЕ TASK FORCE THIRTY FOUR RR ЧУДЕСА МИРА^[3]

Радист Хэлси принял некоторые дополнения за сообщение, поэтому адмирал Хэлси прочитал следующее сообщение:

Где, повторяю, где целевая группа тридцать четыре? Чудеса мира^[3]

Адмирал Хэлси интерпретировал дополняющую фразу «чудеса света» как саркастический выговор, вызвав у него эмоциональный взрыв, а затем заперся на мостике и надулся на час, прежде чем направить свои силы для помощи в битве у Самара.^[2] Радиста Хэлси следовало предупредить из писем. RR что «чудеса света» были дополнением; все остальные радисты, получившие сообщение адмирала Нимица, правильно удалили обе дополнительные фразы.^[2]

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

Симметричная криптография

Хеш-функции

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

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

Режим работы блочного шифра

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

В настоящее время^{[когда? ]} переход к использованию потокового режима работы вместо блочного режима работы.^{[нужна цитата ]} Примером шифрования в потоковом режиме является счетчик режим работы.^[4] В потоковых режимах работы можно шифровать и расшифровывать сообщения любого размера и, следовательно, не требовать заполнения. Более сложные способы завершения сообщения, например кража зашифрованного текста или же остаточное завершение блока Избегайте необходимости заполнения.

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

Битовое заполнение

Битовое заполнение может применяться к сообщениям любого размера.

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

Этот метод может использоваться для дополнения сообщений длиной в любое количество бит, не обязательно в целое количество байтов. Например, сообщение из 23 бит, дополненное 9 битами, чтобы заполнить 32-битный блок:

... | 1011 1001 1101 0100 0010 0111 0000 0000 |

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

Эта схема заполнения определяется ИСО / МЭК 9797-1 как метод заполнения 2.

Заполнение байтами

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

ANSI X9.23

В ANSI X9.23 от 1 до 8 байтов всегда добавляются в качестве заполнения. Блок заполняется случайными байтами (хотя во многих реализациях используется 00), а последний байт блока устанавливается равным количеству добавленных байтов.^[5]

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

... | ДД ДД ДД ДД ДД ДД ДД | ДД ДД ДД ДД 00 00 00 04 |

ISO 10126

ISO 10126 (отозван, 2007 г.^[6][7]) указывает, что заполнение должно выполняться в конце этого последнего блока случайными байтами, а граница заполнения должна определяться последним байтом.

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

... | ДД ДД ДД ДД ДД ДД ДД | ДД ДД ДД ДД 81 A6 23 04 |

PKCS # 5 и PKCS # 7

PKCS # 7 описывается в RFC 5652.

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

Заполнение будет одним из:

0102 0203 03 0304 04 04 0405 05 05 05 0506 06 06 06 06 06 и т. Д.

Этот метод заполнения (как и два предыдущих) четко определен тогда и только тогда, когда N меньше 256.

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

... | ДД ДД ДД ДД ДД ДД ДД | ДД ДД ДД ДД 04 04 04 04 |

Если длина исходных данных является целым числом, кратным размеру блока B, затем дополнительный блок байтов со значением B добавлен. Это необходимо, чтобы алгоритм дешифрования мог с уверенностью определить, является ли последний байт последнего блока байтом заполнения, указывающим количество добавленных байтов заполнения, или частью сообщения открытого текста. Рассмотрим текстовое сообщение, которое является целым числом, кратным B байтов, причем последний байт открытого текста 01. Без дополнительной информации алгоритм дешифрования не сможет определить, является ли последний байт байтом открытого текста или байтом заполнения. Однако, добавив B байты каждого значения B после 01 байт открытого текста, алгоритм дешифрования всегда может рассматривать последний байт как вспомогательный байт и удалять соответствующее количество вспомогательных байтов из конца зашифрованного текста; указанное количество удаляемых байтов основано на значении последнего байта.

Заполнение PKCS # 5 идентично заполнению PKCS # 7, за исключением того, что оно определено только для блочных шифров, которые используют размер блока 64-бит (8 байт). На практике они могут использоваться как взаимозаменяемые.

ИСО / МЭК 7816-4

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

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

... | ДД ДД ДД ДД ДД ДД ДД | ДД ДД ДД ДД 80 00 00 00 |

В следующем примере показано заполнение всего одного байта.

... | ДД ДД ДД ДД ДД ДД ДД | ДД ДД ДД ДД ДД ДД 80 |

Нулевое заполнение

Все байты, которые необходимо заполнить, заполняются нулями. Схема нулевого заполнения не стандартизирована для шифрования,^{[нужна цитата ]} хотя он указан для хэшей и MAC как метод заполнения 1 в ISO / IEC 10118-1^[9] и ИСО / МЭК 9797-1.^[10]

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

... | ДД ДД ДД ДД ДД ДД ДД | ДД ДД ДД ДД 00 00 00 00 |

Нулевое заполнение может быть необратимым, если исходный файл заканчивается одним или несколькими нулевыми байтами, что делает невозможным различие между байтами данных открытого текста и байтами заполнения. Может использоваться, когда длина сообщения может быть получена из группы. Это часто применяется к двоично-кодированным^{[требуется разъяснение ]} струны (строка с завершающим нулем ) как нулевой символ обычно можно снять как пробел.

Нулевое заполнение иногда также называют "заполнением нулями" или "заполнением нулевым байтом". Некоторые реализации могут добавить дополнительный блок из нулевых байтов, если открытый текст уже делится на размер блока.^{[нужна цитата ]}

Криптография с открытым ключом

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

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

Анализ и защита трафика с помощью отступов

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

Другой пример: при шифровании Голос по IP потоков, которые используют кодирование с переменной скоростью передачи, количество битов в единицу времени не скрывается, и это может быть использовано для угадывания произнесенных фраз.^[11] Точно так же шаблонов пакетов, которые создают обычные видеокодеры, часто бывает достаточно для уникальной идентификации потокового видео, которое пользователь смотрит.^[12] Даже общий размер одного объекта, такого как веб-сайт, файл, загрузка пакета программного обеспечения или онлайн-видео, может однозначно идентифицировать объект, если злоумышленник знает или может угадать известный набор, из которого происходит объект.^[13][14][15] В боковой канал длины зашифрованного содержимого использовалось для извлечения паролей из HTTPS коммуникации в известных ПРЕСТУПЛЕНИЕ и НАРУШЕНИЕ атаки.^[16]

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

Случайное заполнение

В конец сообщения может быть добавлено случайное количество дополнительных битов или байтов заполнения вместе с указанием в конце того, сколько заполнения было добавлено. Если величина заполнения выбрана как равномерное случайное число, например, от 0 до некоторого максимального M, то перехватчик не сможет точно определить длину сообщения в этом диапазоне. Если максимальное заполнение M мало по сравнению с общим размером сообщения, то это заполнение не добавит много накладные расходы, но заполнение будет скрывать только наименее значимые биты общей длины объекта, оставляя приблизительную длину больших объектов легко наблюдаемой и, следовательно, потенциально однозначно идентифицируемой по их длине. Если максимальное заполнение M сравнимо с размером полезной нагрузки, напротив, неуверенность подслушивателя в отношении истинного размера полезной нагрузки сообщения намного больше, за счет того, что заполнение может добавить до 100% накладных расходов (${\displaystyle 2\times }$ взрыв) к сообщению.

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

Детерминированный отступ

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

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

Общие методы детерминированного заполнения включают заполнение до постоянного размера блока и заполнение до ближайшей степени двойки. Как рандомизированное заполнение с небольшим максимальным количествомMоднако детерминированное заполнение до размера блока, намного меньшего, чем полезная нагрузка сообщения, скрывает только наименее значимые биты истинной длины сообщения, оставляя истинную приблизительную длину сообщения в значительной степени незащищенной. Заполнение сообщений до степени двойки (или любой другой фиксированной базы) уменьшает максимальное количество Информация что сообщение может просочиться из-за его длины из ${\displaystyle O(\log M)}$ к ${\textstyle O(\log \log M)}$. Однако заполнение до степени двойки увеличивает накладные расходы на размер сообщения до 100%, а заполнение до степени большего целочисленного основания дополнительно увеличивает накладные расходы.

Схема PADMÉ, предложенная для заполненные однородные случайные капли или PURB, детерминированно дополняет сообщения до длины, представимой как число с плавающей запятой мантисса которого не больше (т.е. содержит не более значащих битов), чем ее показатель степени.^[15] Это ограничение длины гарантирует, что утечка сообщения будет не более ${\displaystyle O(\log \log M)}$ бит информации через его длину, например заполнение до степени двойки, но влечет гораздо меньше накладных расходов - максимум 12% для крошечных сообщений и постепенно уменьшается с размером сообщения.

Смотрите также

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

Рекомендации

1. Гордон Велчман, Хижина Шесть Историй: Разгадывать коды загадок, п. 78.
2. Уиллмотт, Х. П. (19 августа 2005 г.). «Великий день гнева: 25 октября 1944 года». Битва за залив Лейте: последнее действие флота. Издательство Индианского университета. ISBN  9780253003515.
3. Туохи, Уильям (2007). Боевые адмиралы Америки: победа в войне на море во Второй мировой войне. Издательская компания МБИ. ISBN  9780760329856.
4. https://www.cs.columbia.edu/~smb/classes/s09/l05.pdf, стр.17
5. «Цепочка блоков шифрования ANSI X9.23». Центр знаний IBM. IBM. Получено 31 декабря 2018.
6. Каталог ISO, ISO 10126-1: 1991
7. Каталог ISO, ISO 10126-2: 1991
8. Каталог ISO, ИСО / МЭК 7816-4: 2005
9. ИСО / МЭК 10118-1: 2000 Информационные технологии. Методы безопасности. Хеш-функции. Часть 1. Общие.
10. ИСО / МЭК 9797-1: 1999 Информационные технологии. Методы безопасности. Коды аутентификации сообщений (MAC). Часть 1. Механизмы, использующие блочный шифр.
11. Райт, Чарльз V .; Баллард, Лукас; Coull, Scott E .; Монроуз, Фабиан; Массон, Джеральд М. (1 декабря 2010 г.). «Раскрытие произносимых фраз в зашифрованных разговорах по IP». ACM-транзакции по информационной и системной безопасности. 13 (4): 35. CiteSeerX  10.1.1.363.1973. Дои:10.1145/1880022.1880029. S2CID  9622722.
12. Шустер, Рой; Шматиков, Виталий; Тромер, Эран (август 2017 г.). Красота и взрыв: удаленная идентификация зашифрованных видеопотоков. Симпозиум по безопасности USENIX.
13. Хинц, Эндрю (апрель 2002 г.). Снятие отпечатков пальцев с веб-сайтов с использованием анализа трафика. Международный семинар по технологиям повышения конфиденциальности. Дои:10.1007/3-540-36467-6_13.
14. Сунь, Цисян; Саймон, Д.Р .; Ван, И-Мин; Russell, W .; Padmanabhan, V.N .; Цю, Лили (май 2002 г.). Статистическая идентификация зашифрованного веб-трафика. Симпозиум IEEE по безопасности и конфиденциальности. Дои:10.1109 / SECPRI.2002.1004359.
15. Никитин, Кирилл; Бармен, Людовик; Lueks, Wouter; Андервуд, Мэтью; Hubaux, Жан-Пьер; Форд, Брайан (2019). «Снижение утечки метаданных из зашифрованных файлов и обмена данными с PURB» (PDF). Труды по технологиям повышения конфиденциальности (PoPETS). 2019 (4): 6–33. Дои:10.2478 / попец-2019-0056. S2CID  47011059.
16. Sheffer, Y .; Holz, R .; Сен-Андре, П. (февраль 2015 г.). Обобщение известных атак на безопасность транспортного уровня (TLS) и датаграмму TLS (DTLS) (Отчет).

дальнейшее чтение

• XCBC: csrc.nist.gov/groups/ST/toolkit/BCM/documents/workshop2/presentations/xcbc.pdf