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

  • Tutorial

Привет, %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 стандартом
Virgil Security, Inc.
0,00
Мы превращаем программистов в криптографов.
Поделиться публикацией

Похожие публикации

Комментарии 20

    0
    А данный алгоритм обладает свойством изоморфности? Ведь при таком шифровании требуется отсутствие коллизий.
      +1
      Мы же по сути строим сеть Фейстеля для ограниченного множества значений, так что просто блочный шифр с размером блока равным размеру множества. Так что да, тут всё честно
      0
      Я не совсем понял проблему: на 1 символ у нас 10 значений вместо 255 и поэтому после шифрования будут символы вне диапазона цифр? Так нет никаких проблем, просто надо брать не отдельные символы а всё число в двоичной форме, потом обратное преобразование шифра.
        0
        А как шифровать, поточно? Размер блока то фиксирован, куда вы денете остаток от зашифрованного блока
          0
          Честно, не разбираюсь в шифровании, я думал, что для таких целей можно выбрать подходящий размер блока, но если это ослабит сильно шифр, то видимо об этом и статья, суть которой я не понял.
            +1
            Мы именно это и делаем, мы уменьшаем размер блока, Но функцией перестановки остается AES у которого всегда 128 бит. Статья как раз о том как не трогая AES добиться стойкости на блоках меньше 128 бит
            0
            Да, я своё предложение снимаю, при дешифровке может получиться больше символов. потому что ограничение сверху разное у двоичного и десятичного чисел.
          0
          Интересно, спасибо. А можно пример того, где это может реально понадобиться?
            +1
            Прежде всего там, где внедрить нормальное шифрование сложно или невозможно из-за проблем совместимости. В каких-нибудь XML или других текстовых протоколах и в других местах где всё завязано на формат данных и который менять будет себе дороже
              +1

              На старом Sony Ericsson было очень интересное приложение для хранения pin-кодов, которое (предположительно) как раз FPE и использовало. Для входа в приложение нужно было ввести мастер-код, но если его ввести неправильно, то вам всё равно покажут сохранённые коды, но неправильные, которые выглядят как правильные. Таким образом угадать правильный мастер-код довольно сложно. Более того, так можно использовать несколько разных мастер-кодов, для каждого из которых будет свой набор корректно отображаемых сохранённых кодов, известный только вам.

              +2

              Разве описанный префиксный шифр не сводится к простому подстановочному шифру? Тогда он должен быть уязвим к частотному анализу (на примере карт — в номере карты есть номер банка и номер платёжной системы, которые могут быть известны).

                0
                del
                  0

                  Нет, там перестановка на всех числах, а не для отдельных цифр.

                    0
                    Я сначала согласился, но потом меня смутил ваш комментарий и я удалил свой.
                    Шифруются ведь именно индексы, получается Akon32 прав.
                      0

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

                        0
                        Можно мне кажется и так и так. В вашем случае действительно анализа не получится, но табличка будет огого какой )
                          0

                          Возможно, я не совсем правильно понимаю алгоритм (а алгоритма расшифровки вообще не нашёл, даже в java-коде).


                          немного рассуждений

                          Но, если каждой цифре соответствует другая цифра (судя по строкам F(0) = 3; F(1) = 1; F(2) = 2; F(3) = 0, это так), то, зная платёжную систему (допустим, VISA, код 4) и номер банка (допустим, 12345) и видя шифротекст 9812 9448 1239 7064, мы делаем вывод о соответствии 4=9; 1=8; 3=1;4=2; 5=4, и можем подставить это в шифротекст: 4123 4551 23X4 XXX5, где X — цифра из {0,6,7,8,9}. Зная дополнительно последние 4 цифры карты (допустим, 7895), в данном примере мы можем сузить множество вариантов открытого текста до 4123 4551 23Y4 7895, где Y из {0,6}. Ещё у нас есть контрольная цифра, что добавит немного информации.
                          Это пример вырожденного варианта частотного анализа (с частотой 100% для соответствий 4=9; 1=8 ...).


                          А если вдруг окажется, что PIN, CVC защищены тем же ключом и шифром, что и номер карты, то на деле они не так уж и защищены.

                            +1

                            Приведенный пример — для множества из четырёх элементов. Безусловно, можно взять цифры в качестве элементов и тогда качество шифрования будет на нуле. Но обычно подразумевается, что элементом является само число и тогда количество элементов в примере с картами равно 10^16 (или 10^15, если без контрольной суммы), но в этом случае предложенный метод будет, мягко говоря, неприменим из-за необходимости выполнять 10^16 операций шифрования.

                    0
                    Есть вот такой простой шифр. Сохраняет формат, длину и может быть обобщён на алфавит любого размера ( не обязательно размера 2n )
                      +2
                      а еще ему, как и одноразовому блокноту, нужен ключ размером с плеинтекст )

                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                    Самое читаемое