В криптографии , padding — это любая из ряда отдельных практик, которые все включают добавление данных в начало, середину или конец сообщения перед шифрованием. В классической криптографии padding может включать добавление бессмысленных фраз в сообщение, чтобы скрыть тот факт, что многие сообщения заканчиваются предсказуемым образом, например, Sincerally Yours .
Официальные сообщения часто начинаются и заканчиваются предсказуемыми способами: Мой дорогой посол, Прогноз погоды, Искренне ваш и т. д. Основное применение дополнения с классическими шифрами — помешать криптоаналитику использовать эту предсказуемость для поиска известного открытого текста [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, SHA-512/224 и SHA-512/256 [4]
Режим цепочки блоков шифра (CBC) является примером режима работы блочного шифра . Некоторые режимы блочного шифра (по сути CBC и PCBC) для алгоритмов шифрования с симметричным ключом требуют ввода обычного текста, кратного размеру блока, поэтому сообщения, возможно, придется дополнять, чтобы довести их до этой длины.
В настоящее время [ когда? ] происходит переход на использование потокового режима работы вместо блочного режима работы. [ необходима цитата ] Примером потокового режима шифрования является режим работы счетчика . [5] Потоковые режимы работы могут шифровать и расшифровывать сообщения любого размера и, следовательно, не требуют заполнения. Более сложные способы завершения сообщения, такие как кража шифротекста или остаточное завершение блока, позволяют избежать необходимости в заполнении.
Недостатком заполнения является то, что оно делает открытый текст сообщения уязвимым для атак оракула заполнения . Атаки оракула заполнения позволяют злоумышленнику получить знания об открытом тексте, не атакуя сам примитив блочного шифра. Атаки оракула заполнения можно избежать, убедившись, что злоумышленник не сможет получить знания об удалении байтов заполнения. Этого можно добиться, проверив код аутентификации сообщения (MAC) или цифровую подпись перед удалением байтов заполнения или переключившись в потоковый режим работы.
Дополнение битами можно применять к сообщениям любого размера.
К сообщению добавляется один бит '1', а затем добавляется столько бит '0', сколько требуется (возможно, ни одного). Количество добавляемых бит '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 |
Заполнение нулями может быть необратимым, если исходный файл заканчивается одним или несколькими нулевыми байтами, что делает невозможным различение байтов данных открытого текста и байтов заполнения. Его можно использовать, когда длину сообщения можно вывести из полосы пропускания . Его часто применяют к двоично-кодированным [ требуется разъяснение ] строкам ( строкам с завершающим нулем ), поскольку нулевой символ обычно можно удалить как пробел .
Zero padding иногда также называют "null padding" или "zero byte padding". Некоторые реализации могут добавлять дополнительный блок нулевых байтов, если открытый текст уже делится на размер блока. [ необходима цитата ]
В криптографии с открытым ключом заполнение — это процесс подготовки сообщения к шифрованию или подписанию с использованием спецификации или схемы, такой как 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% для маленьких сообщений и постепенно уменьшается с размером сообщения.