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

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

Простой способ создания 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. Для больших значений размер таблицы перекодировки и необходимое количество кодировок для инициализации таблицы становится слишком большим.

Если есть набор 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 алгоритма основан на использовании сети Фейстеля. Сеть Фейстеля нуждается в источнике псевдослучайных значений для ключей каждого раунда, и выход алгоритма AES может быть использован в качестве этих значений. Результирующая Фейстель конструкция надежна, если использовано достаточное количество раундов.[2]

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

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

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

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

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

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

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

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

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