Заполнение (криптография)
В криптографии — это любой из ряда различных методов , заполнение каждый из которых включает добавление данных в начало, середину или конец сообщения перед шифрованием. В классической криптографии заполнение может включать добавление к сообщению бессмысленных фраз, чтобы скрыть тот факт, что многие сообщения заканчиваются предсказуемым образом, например, с искренним уважением .
Классическая криптография [ править ]
Официальные сообщения часто начинаются и заканчиваются предсказуемым образом: «Мой дорогой посол», «Сводка погоды», «С уважением» и т. д. Основное использование дополнения классическими шифрами состоит в том, чтобы помешать криптоаналитику использовать эту предсказуемость для поиска известного открытого текста. [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) для алгоритмов шифрования с симметричным ключом требуют ввода обычного текста, кратного размеру блока, поэтому сообщения, возможно, придется дополнять, чтобы довести их до этой длины.
 | этого раздела Фактическая точность оспаривается . ( январь 2016 г. ) |
В настоящее время существует [ когда? ] переход на использование потокового режима работы вместо блочного режима работы. [ нужна ссылка ] Примером шифрования потокового режима является режим работы счетчика . [5] Потоковые режимы работы позволяют шифровать и дешифровать сообщения любого размера и, следовательно, не требуют заполнения. Более сложные способы завершения сообщения, такие как кража зашифрованного текста или завершение остаточного блока, позволяют избежать необходимости заполнения.
Недостатком заполнения является то, что оно делает простой текст сообщения уязвимым для атак оракула с заполнением . Атаки оракула заполнения позволяют злоумышленнику получить знания об открытом тексте, не атакуя сам примитив блочного шифра. Атак с оракулом заполнения можно избежать, если убедиться, что злоумышленник не сможет получить информацию об удалении байтов заполнения. Это может быть достигнуто путем проверки кода аутентификации сообщения (MAC) или цифровой подписи перед удалением заполняющих байтов или путем переключения в потоковый режим работы.
Заполнение битов [ править ]
Заполнение битов можно применять к сообщениям любого размера.
К сообщению добавляется один бит «1», а затем добавляется необходимое количество битов «0» (возможно, ни одного). Количество добавляемых нулевых битов будет зависеть от границы блока, до которого необходимо распространить сообщение. В битовом формате это «1000...0000».
Этот метод можно использовать для дополнения сообщений длиной в любое количество битов, не обязательно в целое число байтов. Например, сообщение длиной 23 бита, дополненное 9 битами для заполнения 32-битного блока:
... | 1011 1001 1101 0100 0010 0111 0000 0000 |
Это заполнение является первым шагом двухэтапной схемы заполнения, используемой во многих хеш-функциях, включая MD5 и SHA . В этом контексте это указано в шаге 3.1 RFC1321 .
Эта схема заполнения определена в стандарте ISO/IEC 9797-1 как метод заполнения 2.
Заполнение байтов [ править ]
Заполнение байтов может применяться к сообщениям, которые можно закодировать как целое число байтов .
ANSI X9.23 [ править ]
В ANSI X9.23 в качестве заполнения всегда добавляется от 1 до 8 байтов. Блок дополняется случайными байтами (хотя во многих реализациях используется 00), а последнему байту блока присваивается количество добавленных байтов. [6]
Пример: В следующем примере размер блока составляет 8 байт, а заполнение требуется для 4 байтов (в шестнадцатеричном формате).
... | DD DD DD DD DD DD DD DD | DD DD DD DD 00 00 00 04 |
ИСО 10126 [ править ]
ISO 10126 (отменен, 2007 г.) [7] [8] ) указывает, что заполнение должно выполняться в конце последнего блока случайными байтами, а граница заполнения должна определяться последним байтом.
Пример: В следующем примере размер блока составляет 8 байт, а для 4 байтов требуется заполнение.
... | DD DD DD DD DD DD DD DD | DD DD DD DD 81 A6 23 04 |
PKCS#5 и PKCS#7 [ править ]
Заполнение осуществляется целыми байтами. Значение каждого добавленного байта представляет собой количество добавляемых байтов, т.е. N байтов, каждый из которых значение N. имеет Количество добавляемых байтов будет зависеть от границы блока, до которого необходимо расширить сообщение.
Заполнение будет одним из:
01 02 02 03 03 03 04 04 04 04 05 05 05 05 05 06 06 06 06 06 06 etc.
Этот метод заполнения (как и два предыдущих) является корректным тогда и только тогда, когда N меньше 256.
Пример: В следующем примере размер блока составляет 8 байт, а для 4 байтов требуется заполнение.
... | DD DD DD DD DD DD DD DD | DD DD DD DD 04 04 04 04 |
Если длина исходных данных кратна размеру блока B дополнительный блок байтов со значением B. , то добавляется Это необходимо для того, чтобы алгоритм дешифрования мог с уверенностью определить, является ли последний байт последнего блока байтом заполнения, указывающим количество добавленных байтов заполнения, или частью открытого текстового сообщения. Рассмотрим сообщение открытого текста, которое представляет собой целое число, кратное B байтам, причем последний байт открытого текста равен 01 . Без дополнительной информации алгоритм дешифрования не сможет определить, является ли последний байт байтом открытого текста или байтом заполнения. Однако, добавляя B байтов со значением B каждый после байта открытого текста 01 , алгоритм дешифрования всегда может рассматривать последний байт как заполняющий байт и удалять соответствующее количество заполняющих байтов с конца зашифрованного текста; указанное количество байтов, подлежащих удалению, основано на значении последнего байта.
Заполнение PKCS#5 идентично заполнению PKCS#7, за исключением того, что оно было определено только для блочных шифров, использующих 64-битный (8-байтовый) размер блока. На практике эти два понятия могут использоваться как взаимозаменяемые.
Максимальный размер блока — 255, поскольку это наибольшее число, которое может содержать байт.
ИСО/МЭК 7816-4 [ править ]
ИСО/МЭК 7816-4 :2005 [9] идентично схеме заполнения битов, применяемой к простому тексту размером 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 |
Заполнение нулями [ править ]
Все байты, которые необходимо дополнить, дополняются нулями. Схема заполнения нулями не стандартизирована для шифрования. [ нужна ссылка ] хотя для хэшей и MAC-адресов он указан как метод заполнения 1 в ISO/IEC 10118-1. [10] и ИСО/МЭК 9797-1 . [11]
Пример: В следующем примере размер блока составляет 8 байт, а для 4 байтов требуется заполнение.
... | DD DD DD DD DD DD DD DD | DD DD DD DD 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% для крошечных сообщений и постепенно уменьшается с размером сообщения. .
См. также [ править ]
- Подтасовывание и отсеивание , подмешивание большого количества ерунды перед отправкой
- Кража зашифрованного текста — еще один подход к работе с сообщениями, длина которых не кратна длине блока.
- Вектор инициализации , соль (криптография) , которые иногда путают с заполнением
- Инкапсуляция ключей , альтернатива заполнению для систем открытых ключей, используемых для обмена симметричными ключами.
- PURB или дополненный однородный случайный двоичный объект — дисциплина шифрования, которая сводит к минимуму утечку метаданных или длины.
- Русское совокупление , еще один прием предотвращения шпаргалки
Ссылки [ править ]
- ^ Гордон Уэлчман , История «Хижины шесть»: Взлом кодов загадки , с. 78.
- ^ Jump up to: Перейти обратно: а б с Уиллмотт, HP (19 августа 2005 г.). «Великий день гнева: 25 октября 1944 года». Битва при заливе Лейте: последнее действие флота . Издательство Университета Индианы. ISBN 9780253003515 .
- ^ Jump up to: Перейти обратно: а б с Туохи, Уильям (2007). Боевые адмиралы Америки: победа в войне на море во Второй мировой войне . Издательская компания МБИ. ISBN 9780760329856 .
- ^ НИСТ. «Стандарт безопасного хеширования FIPS 180-4 (SHS)» (PDF) . НИСТ. .
- ^ https://www.cs.columbia.edu/~smb/classes/s09/l05.pdf , стр. 17.
- ^ «Цепочка блоков шифрования ANSI X9.23» . Центр знаний IBM . ИБМ . Проверено 31 декабря 2018 г.
- ^ Каталог ISO, ISO 10126-1: 1991.
- ^ Каталог ISO, ISO 10126-2: 1991.
- ^ Каталог ISO, ISO / IEC 7816-4: 2005.
- ^ ISO / IEC 10118-1: 2016 Информационные технологии. Методы безопасности. Хэш-функции. Часть 1: Общие сведения.
- ^ ISO / IEC 9797-1: 2011 Информационные технологии. Методы безопасности. Коды аутентификации сообщений (MAC). Часть 1. Механизмы, использующие блочный шифр.
- ^ Райт, Чарльз В.; Баллард, Лукас; Коулл, Скотт Э.; Монроуз, Фабиан; Массон, Джеральд М. (1 декабря 2010 г.). «Раскрытие разговорных фраз в зашифрованной передаче голоса по IP». Транзакции ACM по информационной и системной безопасности . 13 (4): 35. CiteSeerX 10.1.1.363.1973 . дои : 10.1145/1880022.1880029 . S2CID 9622722 .
- ^ Шустер, Рой; Шматиков, Виталий; Тромер, Эран (август 2017 г.). Красота и взрыв: удаленная идентификация зашифрованных видеопотоков . Симпозиум USENIX по безопасности .
- ^ Хинц, Эндрю (апрель 2002 г.). «Отпечатки пальцев на веб-сайтах с использованием анализа трафика». Технологии повышения конфиденциальности . Международный семинар по технологиям повышения конфиденциальности. Конспекты лекций по информатике. Том. 2482. стр. 171–178. дои : 10.1007/3-540-36467-6_13 . ISBN 978-3-540-00565-0 .
- ^ Сунь, Цисян; Саймон, доктор медицинских наук; Ван, И-Мин; Рассел, В.; Падманабхан, ВН; Цю, Лили (май 2002 г.). «Статистическая идентификация зашифрованного трафика веб-браузера». Материалы симпозиума IEEE 2002 г. по безопасности и конфиденциальности . Симпозиум IEEE по безопасности и конфиденциальности. стр. 19–30. дои : 10.1109/SECPRI.2002.1004359 . ISBN 0-7695-1543-6 .
- ^ Jump up to: Перейти обратно: а б Никитин Кирилл; Барман, Людовик; Люкс, Воутер; Андервуд, Мэтью; Юбо, Жан-Пьер; Форд, Брайан (2019). «Уменьшение утечки метаданных из зашифрованных файлов и связь с PURB» (PDF) . Труды по технологиям повышения конфиденциальности (PoPETS) . 2019 (4): 6–33. arXiv : 1806.03160 . дои : 10.2478/popets-2019-0056 . S2CID 47011059 .
- ^ Шеффер, Ю.; Хольц, Р.; Сен-Андре, П. (февраль 2015 г.). Обзор известных атак на безопасность транспортного уровня (TLS) и дейтаграммный TLS (DTLS) (отчет).
