Format preserving encryption или как правильно шифровать номера кредиток

Привет, %username%! Сегодня у нас немного пятничная криптотема. В марте 2016 года вышла интересная публикация от NIST под номером 800-38G (pdf) и с очень интересным называнием Recommendation for Block Cipher Modes of Operation:Methods for Format-Preserving Encryption, в которой отписываются два алгоритма, позволяющие не менять формат данных при шифровании. То есть, если это будет номер кредитки 1234-3456-4567-6678, то после шифрования он тоже останется номером, просто другим. Например 6243-1132-0738-9906. И это не простой xor, там AES и вообще всё серьезно. Давайте немного поговорим о FPE вообще, и об одной из реализаций в частности.

Да, это не какой-то фокус, действительно можно нормально шифровать и расшифровывать данные из ограниченного набора входных значений. Конечно, тут есть свои подводные камни, но задача в принципе решаема. Главное — чтобы полученная конструкция не была менее стойкой ко взлому, чем тот криптоалгоритм, который лежит в её основе.

Итак, у нас есть предопределенный набор символов, например цифры 0-9 и мы не хотим выходить за его пределы. Чтобы было проще, говорят об основании системы счисления, равным размеру этого исходного набора. Для цифр это, очевидно, 10. Для русского алфавита это будет 33, для английского 26. Сами символы не берутся в расчет, мы работаем лишь с массивом индексов, а потом вместо индексов подставляем символы из исходного множества. Например, для строки «хабр» и русского алфавита в качестве входного множества результатом будет массив [22, 0, 1, 17]. Это была простая часть.

Товарищи Блэк и Рогэвэй придумали несколько способов шифрования с сохранением формата.
Самый простой — это префиксный шифр. Давайте рассмотрим его:

Префиксный шифр

1. Шифруем каждый индекс стойким алгоритмом вроде AES.
2. Сортируем зашифрованные значения.
3. Используем отсортированный список как новый список индексов.

К примеру, мы шифруем множество, состоящее из 4х элементов.

Тут я копипастну википедию, дабы продемонстрировать, как это работает на практике
Зашифруем каждый индекс, например, AES. Получим, к примеру

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.

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

Cycle walking

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

Сети Фейстеля

В описании Блэка и Рогэвэя это примерно то же, что и Cycle walking, только используется сеть Фейстеля с размером равным размеру множества.

Алгоритм BPS, на котором я хочу остановиться подробнее, это дальнейшее развитие идеи шифрования ограниченного множества сетью Фейстеля с тем отличием, что там используется сложение по модулю размера множества. Таким образом не надо ничего брутфорсить, всё получается очень красиво и приятно. Нужно только немного поработать с байтиками.

Все данные тут я буду приводить упрощенно, потому что в оригинальном алгоритме есть несущественные шаги вроде реверса байт BE->LE на каждом этапе, которые будут только замусоривать описание. Поехали!

Входные данные:

• Количество элементов в множестве, оно же основание системы счисления radix
• Ключ для AES. Еще есть tweak, это типа IV, но мы его тут опустим для простоты
• Набор индексов для шифрования, он же наш «plaintext». Должен с учетом radix помещаться в один блок AES

Одна из самых главных и хитрых функций тут — упаковывание массива индексов в массив байт и распаковка обратно. Размер множества не обязательно поместится в 1 байт и наоборот, можно сэкономить место, упаковывая индексы плотнее если размер позволяет.

Называется эта функция num и на самом деле работает очень просто:

BigInteger num(int[] X, int radix) {
		// 1. Let x = 0.
		BigInteger x = BigInteger.ZERO;
		// type conversion for readability
		BigInteger r = BigInteger.valueOf(radix);
		// 2. For i from 1 to LEN(X)
		for (int i = 0; i < X.length; i++) {
			// check the value of X[i]
			if (X[i] < 0 || X[i] >= radix)
				throw ...
			// let x = x * radix + X[i]
			x = x.multiply(r).add(BigInteger.valueOf(X[i]));
		}
		return x;
	}

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

Далее я буду обозначать эту операцию num(x, radix)

Сеть Фейстеля

Поскольку конструкция основана на сети Фейстеля, то мы исходное множество разбиваем на 2 половины и работаем отдельно с каждой из них, меняя местами в конце раунда. Назовем эти половинки A и B.

Шифруем, например, комбинацию [0 1 2 3] c основанием (radix) 4.

A = [0 1]
B = [2 3]

Рассмотрим один упрощенный раунд BPS по шагам:

1) Работаем половиной B. Переводим её в байты. num(B, 4) = [14] ( потому что 2 + 3*4) дополняем до размера блока нулями, получаем [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 14 ]

2) Шифруем блок из п.1 AES. Получаем, например 3B20D6CC035B63C8CFD53C15D477BBF8

3) Переводим 3B20D6CC035B73C8CFD53C15D477BBF8 в число, получаем 78594961850022499408352439646346001400

4) Переводим половину A в число, num(A, 4) 0 + 1*4 = 4

5) Складываем п.4 и п.3, получаем 78594961850022499408352439646346001404

6) Теперь хитрость.

6.1) Чтобы это значение упихать в половинку для следующего раунда, мы сначала вычисляем, сколько в ней разрядов, возведя radix в степень, равную количеству элементов в половинке A
4^2 = 16

6.2) Берем остаток от деления 78594961850022499408352439646346001404 на 16, получаем 12

6.3) Преобразовываем 12 в массив индексов по основанию 4 получаем [0, 3] (0 + 3*4)

7) Меняем половинки местами, получается [2, 3] [0, 3]

И так еще 7 раз, всего 8 раундов

В обратную сторону не сильно сложнее. Только начинаем с A, а не с B

1) Повторяем пункты 1 — 3, получая 78594961850022499408352439646346001400

2) Переводим [0, 3] в цифру, мы уже знаем, что это 12

3) Вычитаем 78594961850022499408352439646346001400 из 12ти, получаем отрицательное число -78594961850022499408352439646346001388, которое по модулю 16 будет равно четырем. Да, отрицательные числа тоже можно брать по модулю, ничего страшного.

4) Переводим 4 в [0, 1]
Меняем половинки местами, получаем [0, 1] [2, 3]

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

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

По поводу кредиток. Не обязательно шифровать таким образом (по основанию 10, естественно) все 16 цифр карты. Как минимум можно не трогать чексумму и честно посчитать её отдельно.
К тому же, в карте есть идентификатор того, кто её выпустил (первые 6 цифр), а собственно номер счета — это предпоследние 9 цифр. Их и есть смысл шифровать таким способом.

На этом у меня всё. Изучить алгоритм мне помог этот код на java, совместимый с новым NIST стандартом