В криптографии заполнение — это любой из ряда различных методов, каждый из которых включает добавление данных в начало, середину или конец сообщения перед шифрованием. В классической криптографии заполнение может включать добавление к сообщению бессмысленных фраз, чтобы скрыть тот факт, что многие сообщения заканчиваются предсказуемым образом, например, с искренним уважением .
Официальные сообщения часто начинаются и заканчиваются предсказуемым образом: «Мой дорогой посол», «Сводка погоды», «С уважением» и т. д. Основное использование дополнения классическими шифрами состоит в том, чтобы помешать криптоаналитику использовать эту предсказуемость для поиска известного открытого текста [1] , который помогает взломать шифрование. Случайное заполнение длины также не позволяет злоумышленнику узнать точную длину открытого текстового сообщения.
Известным примером классической набивки, вызвавшей большое недопонимание, является инцидент с « чудесами света », который едва не стал причиной потерь союзников в битве Второй мировой войны у Самара , части более крупной битвы в заливе Лейте . В этом примере адмирал Честер Нимиц , главнокомандующий Тихоокеанским флотом США во Второй мировой войне, отправил следующее сообщение адмиралу Буллу Хэлси , командующему оперативной группой №34 (основной флот союзников) в битве при заливе Лейте, 25 октября 1944 г.: [2]
Где, повторите, где оперативная группа №34? [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]
Радист Хэлси принял некоторые дополнения за сообщение, и в итоге адмирал Хэлси прочитал следующее сообщение:
Где, повторите, где оперативная группа №34? Мировые чудеса [3]
Адмирал Хэлси интерпретировал фразу «чудеса света» как саркастический выговор, из-за которого у него случился эмоциональный всплеск, а затем он заперся на мостике и дулся на час, прежде чем двинуть свои силы для помощи в битве у Самара. [2] Радист Хэлси должен был быть предупрежден буквами RR , которые дополняли слова «чудеса света»; все остальные радисты, получившие сообщение адмирала Нимица, правильно удалили обе дополнительные фразы. [2]
Многие классические шифры упорядочивают открытый текст по определенным шаблонам (например, квадратам, прямоугольникам и т. д.), и если открытый текст не совсем подходит, часто необходимо ввести дополнительные буквы для заполнения шаблона. Использование бессмысленных букв для этой цели имеет побочное преимущество, заключающееся в усложнении некоторых видов криптоанализа.
Большинство современных криптографических хэш-функций обрабатывают сообщения блоками фиксированной длины; все хеш-функции, кроме самых ранних, включают в себя какую-то схему заполнения. Для криптографических хэш-функций крайне важно использовать схемы завершения, которые предотвращают уязвимость хэша к атакам с расширением длины .
Многие схемы заполнения основаны на добавлении прогнозируемых данных в последний блок. Например, площадь может быть получена из общей длины сообщения. Такая схема заполнения обычно применяется к алгоритмам хеширования, использующим конструкцию Меркла-Дамгорда , например, семейства MD-5 , SHA-1 и SHA-2 , например SHA-224, SHA-256, SHA-384, SHA-512. , SHA-512/224 и SHA-512/256 [4]
Режим цепочки блоков шифра (CBC) является примером режима работы блочного шифрования . Некоторые режимы блочного шифрования (по сути, CBC и PCBC) для алгоритмов шифрования с симметричным ключом требуют ввода обычного текста, кратного размеру блока, поэтому сообщения, возможно, придется дополнять, чтобы довести их до этой длины.
В настоящее время [ когда? ] переход на использование потокового режима работы вместо блочного режима работы. [ необходима цитация ] Примером шифрования в потоковом режиме является режим работы счетчика . [5] Потоковые режимы работы позволяют шифровать и дешифровать сообщения любого размера и, следовательно, не требуют заполнения. Более сложные способы завершения сообщения, такие как кража зашифрованного текста или завершение остаточного блока, позволяют избежать необходимости заполнения.
Недостатком заполнения является то, что оно делает простой текст сообщения уязвимым для атак оракула с заполнением . Атаки оракула заполнения позволяют злоумышленнику получить знания об открытом тексте, не атакуя сам примитив блочного шифра. Атак оракула заполнения можно избежать, если убедиться, что злоумышленник не сможет получить информацию об удалении байтов заполнения. Этого можно достичь путем проверки кода аутентификации сообщения (MAC) или цифровой подписи перед удалением заполняющих байтов или путем переключения в потоковый режим работы.
Заполнение битов можно применять к сообщениям любого размера.
К сообщению добавляется один бит «1», а затем добавляется необходимое количество битов «0» (возможно, ни одного). Количество добавляемых нулевых битов будет зависеть от границы блока, до которого необходимо распространить сообщение. В битовом формате это «1000...0000».
Этот метод можно использовать для дополнения сообщений длиной в любое количество битов, не обязательно в целое число байтов. Например, сообщение длиной 23 бита, дополненное 9 битами для заполнения 32-битного блока:
... | 1011 1001 1101 0100 0010 011 1 0000 0000 |
Это заполнение является первым шагом двухэтапной схемы заполнения, используемой во многих хеш-функциях , включая MD5 и SHA . В этом контексте это указано в шаге 3.1 RFC1321.
Эта схема заполнения определена в стандарте ISO/IEC 9797-1 как метод заполнения 2.
Заполнение байтов может применяться к сообщениям, которые можно закодировать как целое число байтов .
В ANSI X9.23 в качестве заполнения всегда добавляется от 1 до 8 байтов. Блок дополняется случайными байтами (хотя во многих реализациях используется 00), а последнему байту блока присваивается количество добавленных байтов. [6]
Пример. В следующем примере размер блока составляет 8 байт, а заполнение требуется для 4 байтов (в шестнадцатеричном формате).
... | ДД ДД ДД ДД ДД ДД ДД ДД | ДД ДД ДД ДД 00 00 00 04 |
ISO 10126 (отменен в 2007 г. [7] [8] ) указывает, что заполнение должно выполняться в конце последнего блока случайными байтами, а граница заполнения должна определяться последним байтом.
Пример: В следующем примере размер блока составляет 8 байт, а для 4 байтов требуется заполнение.
... | ДД ДД ДД ДД ДД ДД ДД ДД | ДД ДД ДД ДД 81 A6 23 04 |
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-байтовый) размер блока. На практике эти два понятия можно использовать взаимозаменяемо.
Максимальный размер блока — 255, поскольку это наибольшее число, которое может содержать байт.
ISO/IEC 7816-4 :2005 [9] идентичен схеме заполнения битами, применяемой к простому тексту из N байтов. На практике это означает, что первый байт представляет собой обязательный байт со значением «80» (шестнадцатеричный), за которым, при необходимости, следуют байты от 0 до N - 1, установленные в «00», пока не будет достигнут конец блока. ISO/IEC 7816-4 сам по себе является стандартом связи для смарт-карт, содержащих файловую систему, и сам по себе не содержит никаких криптографических спецификаций.
Пример: В следующем примере размер блока составляет 8 байт, а для 4 байтов требуется заполнение.
... | ДД ДД ДД ДД ДД ДД ДД ДД | ДД ДД ДД ДД 80 00 00 00 |
В следующем примере показано заполнение всего одного байта.
... | ДД ДД ДД ДД ДД ДД ДД ДД | ДД ДД ДД ДД ДД ДД ДД ДД 80 |
Все байты, которые необходимо дополнить, дополняются нулями. Схема заполнения нулями не стандартизирована для шифрования, хотя она указана для хэшей и MAC как метод заполнения 1 в ISO/IEC 10118-1 [10] и ISO/IEC 9797-1 . [11]
Пример: В следующем примере размер блока составляет 8 байт, а для 4 байтов требуется заполнение.
... | ДД ДД ДД ДД ДД ДД ДД ДД | ДД ДД ДД ДД 00 00 00 00 |
Заполнение нулями может быть необратимым, если исходный файл заканчивается одним или несколькими нулевыми байтами, что делает невозможным различие между байтами данных открытого текста и байтами заполнения. Его можно использовать, когда длину сообщения можно определить внеполосно . Он часто применяется к двоично закодированным строкам [ необходимо пояснение ] ( строка с нулевым завершением ), поскольку нулевой символ обычно можно удалить как пробел .
Заполнение нулями иногда также называют «заполнением нулями» или «заполнением нулевым байтом». Некоторые реализации могут добавлять дополнительный блок из нулевых байтов, если открытый текст уже делится на размер блока. [ нужна цитата ]
В криптографии с открытым ключом заполнение — это процесс подготовки сообщения к шифрованию или подписанию с использованием спецификации или схемы, такой как PKCS#1 v2.2, 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 (log M ) до O (log log M ) . Однако заполнение до степени двойки увеличивает накладные расходы на размер сообщения почти на 100 %, а заполнение до степени большего целого числа еще больше увеличивает максимальные накладные расходы.
Схема PADMÉ, предложенная для дополненных однородных случайных блоков или PURB , детерминированно дополняет сообщения до длин, которые можно представить в виде числа с плавающей запятой , мантисса которого не больше (т. е. не содержит более значащих битов), чем его показатель степени. [16] Это ограничение длины гарантирует, что сообщение пропускает не более O (log log M ) бит информации по своей длине, например, заполнение до степени двойки, но требует гораздо меньших накладных расходов - не более 12% для крошечных сообщений и постепенно уменьшается. с размером сообщения.