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

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

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

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

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

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

С заполнением (полужирным шрифтом) и добавленными метаданными сообщение стало:

TURKEY TROTS TO WATER GG FROM CINCPAC ACTION COM THIRD FLEET INFO COMINCH CTF SEVENTY-SEVEN X WHERE IS RPT WHERE IS TASK FORCE THIRTY FOUR RR THE WORLD WONDERS[3]

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

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

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

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


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

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

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

Многие схемы заполнения основаны на добавлении предсказуемых данных в последний блок. Например, блокнот может быть получен из общей длины сообщения. Такая схема заполнения обычно применяется к алгоритмам хеширования, которые используют конструкцию Меркла – Дамгарда, например к семейству MD-5 , SHA-1 и SHA-2, например SHA-224, SHA-256, SHA-384, SHA-512. , SHA512 / 224 и SHA-512/256 [4]

Режим работы блочного шифра [ править ]

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

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

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

Битовое заполнение [ править ]

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

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

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

... | 1011 1001 1101 0100 0010 011 1 0000 0000 |

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

Эта схема заполнения определяется ISO / IEC 9797-1 как метод заполнения 2.

Заполнение байтами [ править ]

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

ANSI X9.23 [ править ]

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

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

... | ДД ДД ДД ДД ДД ДД ДД | ДД ДД ДД ДД 00 00 00 04 |
ISO 10126 [ править ]

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

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

... | ДД ДД ДД ДД ДД ДД ДД | DD DD DD DD 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 [ править ]

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

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

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

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

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

Нулевое заполнение [ править ]

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

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

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

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

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

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

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

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

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

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

В качестве другого примера, при шифровании потоков Voice Over IP, которые используют кодирование с переменной скоростью передачи данных, количество битов в единицу времени не скрывается, и это можно использовать для угадывания произносимых фраз. [12] Точно так же шаблонов пакетов, которые создают обычные видеокодеры, часто бывает достаточно для уникальной идентификации потокового видео, которое пользователь смотрит. [13] Даже общий размер одного объекта, такого как веб-сайт, файл, загрузка пакета программного обеспечения или онлайн-видео, может однозначно идентифицировать объект, если злоумышленник знает или может угадать известный набор, из которого происходит объект. [14] [15] [16] боковой канал зашифрованного контента длина был использован для извлечения паролей изСвязь HTTPS в хорошо известных атаках CRIME и BREACH . [17]

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

Случайное заполнение [ править ]

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

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

Детерминированное заполнение [ править ]

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

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

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

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

См. Также [ править ]

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

Ссылки [ править ]

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

Дальнейшее чтение [ править ]

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