Шифрование с сохранением формата

В криптографии открытый шифрование с сохранением формата ( FPE ) относится к шифрованию таким образом, что выходные данные ( зашифрованный текст ) имеют тот же формат, что и входные данные ( текст ). Значение слова «формат» варьируется. Обычно используются только конечные наборы символов; числовой, буквенный или буквенно-цифровой. Например:

• Шифрование 16-значного номера кредитной карты так, чтобы зашифрованный текст представлял собой еще одно 16-значное число.
• Шифрование английского слова так, чтобы зашифрованный текст представлял собой другое английское слово.
• Шифрование n -битного числа так, чтобы зашифрованный текст представлял собой другое n -битное число (это определение n -битного блочного шифра).

Для таких конечных областей и для целей обсуждения ниже шифр эквивалентен перестановке N целых чисел {0, ..., N −1 }, где N — размер области.

Мотивация

Ограниченная длина или формат полей

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

Добавление шифрования в такие приложения может оказаться затруднительным, если необходимо изменить модели данных, поскольку обычно это связано с изменением ограничений длины полей или типов данных. Например, выходные данные типичного блочного шифра преобразуют номер кредитной карты в шестнадцатеричный формат (например, 0x96a45cbcf9c2a9425cde9e274948cb67, 34 байта, шестнадцатеричные цифры) или Base64 (например, значение lqRcvPnCqUJc3p4nSUjLZw==, 24 байта, буквенно-цифровые и специальные символы), что нарушит работу всех существующих приложений, ожидающих, что номер кредитной карты будет состоять из 16 цифр.

Помимо простых проблем с форматированием, при использовании AES-128-CBC номер кредитной карты может быть зашифрован до шестнадцатеричного значения. 0xde015724b081ea7003de4593d792fd8b695b39e095c98f3a220ff43522a2df02. Помимо проблем, вызванных созданием недопустимых символов и увеличением размера данных, данные, зашифрованные с использованием режима CBC алгоритма шифрования, также меняют свое значение при повторном расшифровке и зашифровании. Это происходит потому, что случайное начальное значение , которое используется для инициализации алгоритма шифрования и включается как часть зашифрованного значения, различно для каждой операции шифрования. По этой причине невозможно использовать данные, зашифрованные в режиме CBC, в качестве уникального ключа для идентификации строки в базе данных.

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

Сравнение с действительно случайными перестановками

Хотя действительно случайная перестановка является идеальным шифром FPE, для больших доменов невозможно заранее сгенерировать и запомнить действительно случайную перестановку. Таким образом, проблема FPE состоит в том, чтобы сгенерировать псевдослучайную перестановку из секретного ключа таким образом, чтобы время вычисления одного значения было небольшим (в идеале постоянным, но, что наиболее важно, меньшим, чем O(N) ).

Сравнение с блочными шифрами

представляет Технически n- битный блочный шифр собой FPE на множестве {0,...,2. ^н -1 }. Если FPE необходим для одного из этих наборов стандартного размера (например, n = 64 для DES и n = 128 для AES), можно использовать блочный шифр нужного размера.

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

Определение безопасности

В криптографической литературе (см. большинство ссылок ниже) мерой «хорошего» FPE является то, может ли злоумышленник отличить FPE от действительно случайной перестановки. Предполагаются различные типы злоумышленников в зависимости от того, имеют ли они доступ к оракулам или известным парам зашифрованный/открытый текст.

Алгоритмы

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

Конструкции FPE Black и Rogaway

Реализация FPE с безопасностью, доказуемо связанной с безопасностью базового блочного шифра, была впервые предпринята в статье криптографов Джона Блэка и Филиппа Рогауэя . в котором описаны три способа сделать это. Они доказали, что каждый из этих методов так же безопасен, как и блочный шифр, который используется для его создания. Это означает, что если алгоритм AES используется для создания алгоритма FPE, то полученный алгоритм FPE так же безопасен, как и AES, поскольку злоумышленник, способный победить алгоритм FPE, также может победить алгоритм AES. Следовательно, если AES безопасен, то построенные на его основе алгоритмы FPE также безопасны. Во всем нижеследующем E обозначает операцию шифрования AES, которая используется для построения алгоритма FPE, а F обозначает операцию шифрования FPE.

FPE из префиксного шифра

Один простой способ создать алгоритм FPE для {0,..., N -1} — это присвоить псевдослучайный вес каждому целому числу, а затем отсортировать по весу. Веса определяются путем применения существующего блочного шифра к каждому целому числу. Блэк и Рогауэй назвали этот метод «префиксным шифром» и показали, что он, вероятно, не уступает используемому блочному шифру.

Таким образом, чтобы создать FPE в домене {0,1,2,3}, учитывая ключ K, примените AES( K ) к каждому целому числу, дав, например,

weight(0) = 0x56c644080098fc5570f2b329323dbf62weight(1) = 0x08ee98c0d05e3dad3eb3d6236f23e7b7weight(2) = 0x47d2e1bf72264fa01fb274465e56ba20weight(3) = 0x077de40941c93774857961a8a772650d

Сортировка [0,1,2,3] по весу дает [3,1,2,0], поэтому шифр имеет вид

F(0) = 3F(1) = 1F(2) = 2F(3) = 0

Этот метод полезен только для небольших N. значений Для больших значений размер таблицы поиска и необходимое количество шифрований для инициализации таблицы становятся слишком большими, чтобы их можно было использовать на практике.

СПО от велосипедной ходьбы

существует набор M Если в области псевдослучайной перестановки P разрешенных значений (например, P может быть блочным шифром, например AES), алгоритм FPE может быть создан из блочного шифра путем многократного применения блочного шифра до тех пор, пока результат не будет одно из разрешенных значений (в пределах M ).

CycleWalkingFPE(x) {    if P(x) is an element of M then        return P(x)    else        return CycleWalkingFPE(P(x))}

Рекурсия гарантированно завершится. (Поскольку P взаимно однозначен, а область определения конечна, повторное применение P образует цикл, поэтому, начиная с точки в M, цикл в конечном итоге завершится в M .)

Это имеет то преимущество, что элементы M не нужно отображать в последовательную последовательность {0,..., N -1} целых чисел. Недостаток этого подхода заключается в том, что когда M намного меньше домена P , для каждой операции может потребоваться слишком много итераций. Если P — блочный шифр фиксированного размера, такой как AES, это серьезное ограничение на размеры M , для которых этот метод эффективен.

Например, приложению может потребоваться зашифровать 100-битные значения с помощью AES таким образом, чтобы создать еще одно 100-битное значение. С помощью этого метода шифрование AES-128-ECB может применяться до тех пор, пока оно не достигнет значения, в котором все его 28 старших бит установлены в 0, что в среднем займет 2 ²⁸ итерации, которые должны произойти.

FPE из сети Feistel

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

Один из способов реализации алгоритма FPE с использованием AES и сети Фейстеля — использовать столько бит вывода AES, сколько необходимо, чтобы равняться длине левой или правой половины сети Фейстеля. Например, если в качестве дополнительного ключа требуется 24-битное значение, для этого значения можно использовать младшие 24 бита вывода AES.

Это может не привести к тому, что выходные данные сети Фейстеля сохранят формат входных данных, но можно итерировать сеть Фейстеля таким же образом, как это делает метод велосипедной ходьбы, чтобы гарантировать сохранение формата. Поскольку можно настроить размер входных данных сети Фейстеля, можно сделать очень вероятным, что эта итерация в среднем завершится очень быстро. Например, в случае номеров кредитных карт их 10. ¹⁵ возможные 16-значные номера кредитных карт (с учетом избыточной контрольной цифры ), а поскольку 10 ¹⁵ ≈ 2 ^49.8 Использование 50-битной сети Фейстеля вместе с велосипедной прогулкой позволит создать алгоритм FPE, который в среднем шифрует довольно быстро.

Перетасовка Торпа

Тасование Торпа похоже на идеализированное тасование карт или, что эквивалентно, максимально несбалансированный шифр Фейстеля, где одна сторона представляет собой один бит. Легче доказать безопасность несбалансированных шифров Фейстеля, чем сбалансированных.

ХОЧУ моду

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

Поспешный пудинговый шифр

Шифр Hasty Pudding Cipher использует специальные конструкции (не зависящие от существующих блочных шифров в качестве примитивов) для шифрования произвольных конечных небольших доменов.

Режим FFSEM/FFX AES

Режим FFSEM AES (спецификация ), который был принят к рассмотрению NIST, использует описанную выше структуру сети Фейстеля Блэка и Рогавея с AES для функции раунда, с одной небольшой модификацией: используется один ключ, который слегка настраивается для каждого раунда.

По состоянию на февраль 2010 года FFSEM был заменен режимом FFX, написанным Михиром Белларе , Филиппом Рогауэем и Теренсом Спайсом. (спецификация, Разработка режимов блочного шифрования NIST , 2010 ).

FPE для шифрования JPEG 2000

В стандарте JPEG 2000 коды маркеров (в диапазоне от 0xFF90 до 0xFFFF) не должны появляться в открытом тексте и зашифрованном тексте. Простой метод модульного 0xFF90 не может быть применен для решения проблемы шифрования JPEG 2000. Например, слова зашифрованного текста 0x23FF и 0x9832 действительны, но их комбинация 0x23FF9832 становится недействительной, поскольку она вводит код маркера 0xFF98. Аналогичным образом, простой метод обхода цикла не может быть применен для решения проблемы шифрования JPEG2000, поскольку два действительных блока зашифрованного текста могут дать неверный зашифрованный текст при их объединении. Например, если первый блок зашифрованного текста заканчивается байтами «...30FF», а второй блок зашифрованного текста начинается с байтов «9832...», то в зашифрованном тексте появится код маркера «0xFF98».

Два механизма шифрования JPEG 2000 с сохранением формата были описаны в статье «Эффективные и безопасные схемы шифрования для JPEG2000». Хунцзюнь Ву и Ди Ма. Чтобы выполнить шифрование JPEG 2000 с сохранением формата, необходимо исключить байт «0xFF» из шифрования и дешифрования. Затем механизм шифрования JPEG 2000 выполняет сложение по модулю n с потоковым шифрованием; другой механизм шифрования JPEG 2000 реализует метод циклического обхода с блочным шифром.

Другие конструкции FPE

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

Раздел 8 FIPS 74, Публикация федеральных стандартов обработки информации 1981 г., Рекомендации по внедрению и использованию стандарта шифрования данных NBS , описывает способ использования алгоритма шифрования DES таким образом, чтобы сохранить формат данных посредством сложения по модулю n с последующей операцией несмещения. Этот стандарт был отменен 19 мая 2005 г., поэтому эту методику следует считать устаревшей с точки зрения формального стандарта.

Еще одним ранним механизмом шифрования с сохранением формата была работа Питера Гутмана «Шифрование данных с ограниченным диапазоном значений». который снова выполняет сложение по модулю n для любого шифра с некоторыми корректировками, чтобы сделать результат однородным, при этом полученное шифрование будет таким же надежным, как и базовый алгоритм шифрования, на котором оно основано.

Статья «Использование шифрования с сохранением типа данных для повышения безопасности хранилищ данных» Майкл Брайтвелл и Гарри Смит описывают способ использования алгоритма шифрования DES таким образом, чтобы сохранить формат открытого текста. Этот метод, похоже, не применяет несмещенный шаг, как другие методы по модулю n, упомянутые здесь.

Статья «Шифрование с сохранением формата». Михир Белларе и Томас Ристенпарт описывают использование «почти сбалансированных» сетей Фейстеля для создания безопасных алгоритмов FPE.

Статья «Управление шифрованием формата с использованием шифрования с сохранением типа данных» Ульф Маттссон описывает другие способы создания алгоритмов FPE.

Примером алгоритма FPE является FNR ( Flexible Naor and Reingold ).

Принятие алгоритмов FPE органами стандартизации

Специальная публикация NIST 800-38G, «Рекомендации по режимам работы блочного шифрования: методы шифрования с сохранением формата» определяет два метода: FF1 и FF3. Подробную информацию о предложениях, представленных для каждого из них, можно найти на сайте NIST по разработке режимов блочного шифрования. включая информацию о патентах и ​​тестовых векторах. Примеры значений доступны как для FF1, так и для FF3.

• FF1 — это FFX[Radix] «Режим шифрования на основе Фейстеля с сохранением формата», который также присутствует в стандартных процессах ANSI X9 как X9.119 и X9.124. Его представили в NIST Михир Белларе из Калифорнийского университета в Сан-Диего, Филип Рогавей из Калифорнийского университета в Дэвисе и Теренс Спайс из компании Voltage Security Inc. Поставляются тестовые векторы, и некоторые их части запатентованы. (ПРОЕКТ СП 800-38Г Ред. 1) требует, чтобы минимальный размер домена шифруемых данных составлял 1 миллион (ранее 100).

• FF3 — это BPS, названный в честь авторов. Его представили в NIST Эрик Брайер, Томас Пейрен и Жак Стерн из Ingenico, Франция. Авторы заявили NIST, что их алгоритм не запатентован. Продукт CyberRes Volt , хотя и претендует на собственные патенты и на режим BPS. 12 апреля 2017 года NIST пришел к выводу, что FF3 «больше не подходит в качестве метода FPE общего назначения», поскольку исследователи обнаружили уязвимость.
• FF3-1 (ПРОЕКТ SP 800-38G Ред. 1) заменяет FF3 и требует, чтобы минимальный размер домена шифруемых данных составлял 1 миллион (ранее 100).

Другой режим был включен в проект руководства NIST, но был удален до окончательной публикации.

• FF2 — это схема VAES3 для FFX: дополнение к «Режиму работы FFX для сохранения шифрования»: набор параметров для зашифрованных строк произвольного основания с операцией подключа для продления срока службы ключа шифрования. Он был представлен в NIST Йоахимом Вэнсом из VeriFone Systems Inc. Тестовые векторы не поставляются отдельно от FF1, и некоторые их части запатентованы. Авторы представили модифицированный алгоритм как DFF. который находится на активном рассмотрении NIST.

Корея также разработала стандарт FPE: FEA-1 и FEA-2.

Реализации

Реализации FF1 и FF3 с открытым исходным кодом общедоступны в язык Си , Иди язык , Ява , Node.js , Питон , С#/.Net и Ржавчина