Шифрование, сохраняющее формат

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

• Зашифровать 16-значный номер кредитной карты так, чтобы шифротекст был также 16-цифирным номером.
• Зашифровать английское слово так, чтобы шифротекст был тоже английским словом.
• Зашифровать n-битовый номер так, чтобы шифротекст был n-битовым номером. (Это определение n-битового блочного шифрования)

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

Зачем нужно FPE

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

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

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

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

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

Генерация псевдослучайных чисел

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

Например, если создана последовательность чисел от 11111 до 88888, тогда FPE берёт первое значение 11111 и зашифровывает его в другой 5-цифирный номер. Этот процесс продолжается до тех по, пока не будет считано последнее значение 88888. Все зашифрованные значения уникальны и случайны. Эти номера используются в качестве серийного ключа для продукта.

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

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

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

N-битовое блочное шифрование (например, AES) технически является FPE на множестве {0, ..., 2ⁿ-1}. Если необходим FPE на одном из стандартных множеств (где n=128, 192, 256), то можно использовать блочное шифрование необходимого размера.

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

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

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

Алгоритмы FPE

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

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

FPE конструкции Блэка и Рогавэя

Реализация FPE, лежащего в основе блочного шифра, была впервые использована в работе криптографов Джона Блэка и Филлипа Рогавэя, которая описывала 3 способа сделать это. Они доказали, что каждый из этих методов обладает такой же надёжностью, как и блочный шифр, который используется для их построения. Значит, противник, способный расшифровать FPE-алгоритм, может расшифровать и AES-алгоритм. Поэтому для надёжных AES-алгоритмов построенные на них FPE-алгоритмы также надёжны. Далее E обозначает операцию шифрования AES, который используется для построения FPE-алгоритма, а P — FPE.

FPE на основе prefix-шифра

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

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

weight(0) = 0x56c644080098fc5570f2b329323dbf62
weight(1) = 0x08ee98c0d05e3dad3eb3d6236f23e7b7
weight(2) = 0x47d2e1bf72264fa01fb274465e56ba20
weight(3) = 0x077de40941c93774857961a8a772650d

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

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

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

FPE из cycle walking

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

  CycleWalkingFPE(x)
  {
    if ''P''(x) is an element of ''M''
      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 на основе сети Фейстеля

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

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

Этот метод может и не сохранять формат, но можно повторно использовать сеть Фейстеля так же, как и cycle-walking метод до тех пор, пока формат не будет сохранён. Регулируя размер входных данных для сети Фейстеля, можно добиться быстрого завершения цикла. Например, есть 10¹⁶ (10¹⁶ = 2^53.1) возможных 16-цифирных номеров кредитной карты. Используя 54-битную широкую сеть Фейстеля и cycle-walking, возможно создать FPE-алгоритм, который шифрует достаточно быстро.

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

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

8 секция FIPS 74, Federal Information Processing Standards Publication 1981 Guidelines for Implementing and Using the NBS Data Encryption Standard, описывает способ использования DES-алгоритма шифрования, который сохраняет формат данных путём сложения по модулю n. Этот стандарт был удалён 19 мая 2005, так что метод считается устаревшим в терминах стандарта.

Другим методом шифрования, сохраняющего формат, была работа Питера Гутмана «Encrypting data with a restricted range of values», в которой был рассмотрен алгоритм, который также выполнял сложение по модулю n с некоторыми корректировками.

Работа «Using Datatype-Preserving Encryption to Enhance Data Warehouse Security» Майкла Брайтвелла и Гарри Смита описывает способ использования DES-алгоритма шифрования, который сохраняет формат данных открытого текста. Этот метод не использует сложение по модулю n.

Работа «Format-Preserving Encryption» Михира Беллара и Томаса Ристенпарта описывает использование «почти сбалансированной» сети Фейстеля для создания безопасного FPE-алгоритма.

Работа «Format Controlling Encryption Using Datatype Preserving Encryption» Ульфа Мэттссона описывает другие методы реализации FPE-алгоритма.

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

Принятие FPE-алгоритмов государственными стандартами

NIST опубликовал Special Publication 800-38G, DRAFT Recommendation for Block Cipher Modes of Operation: Methods for Format-Preserving Encryption. Эта публикация определяет три метода FF1, FF2 и FF3. Подробная информация о них, а также патент и информация о тестовом наборе, может быть найдена на сайте NIST Block Cipher Modes Development.

• FF1 — это FFX «Format-preserving Feistel-based Encryption Mode». Он был представлен на NIST Михиром Бэлларом из Калифорнийского университета в Сан-Диего, Филипом Рогэвэем из Калифорнийского университета, Дейвис, и Теренсом Спайсом из Voltage Security Inc. Тестовый набор предоставлен, и его части запатентованы.
• FF2 — это VAES3-схема для FFX: Дополнение к "The FFX Mode of Operation for Preserving Encryption. Он был представлен на NIST Йоахимом Вэнсом из VeriFone Systems Inc. Тестовый набор не предоставлен, в отличие от FF1, и его части запатентованы.
• FF3 — это BPS, названный по именам его авторов. Он был представлен на NIST Эриком Браером, Томасом Пайрином и Жаком Стерном из Ingenico, Франция. Тестовый набор не предоставлен и не запатентован.