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

[sheknitrtch]

А данный алгоритм обладает свойством изоморфности? Ведь при таком шифровании требуется отсутствие коллизий.

[Scratch]

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

[VaalKIA]

Я не совсем понял проблему: на 1 символ у нас 10 значений вместо 255 и поэтому после шифрования будут символы вне диапазона цифр? Так нет никаких проблем, просто надо брать не отдельные символы а всё число в двоичной форме, потом обратное преобразование шифра.

[Scratch]

А как шифровать, поточно? Размер блока то фиксирован, куда вы денете остаток от зашифрованного блока

[VaalKIA]

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

[Scratch]

Мы именно это и делаем, мы уменьшаем размер блока, Но функцией перестановки остается AES у которого всегда 128 бит. Статья как раз о том как не трогая AES добиться стойкости на блоках меньше 128 бит

[VaalKIA]

Да, я своё предложение снимаю, при дешифровке может получиться больше символов. потому что ограничение сверху разное у двоичного и десятичного чисел.

[hdfan2]

Интересно, спасибо. А можно пример того, где это может реально понадобиться?

[Scratch]

Прежде всего там, где внедрить нормальное шифрование сложно или невозможно из-за проблем совместимости. В каких-нибудь XML или других текстовых протоколах и в других местах где всё завязано на формат данных и который менять будет себе дороже

[Disasm]

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

[Akon32]

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

[Scratch]

del

[Disasm]

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

[Scratch]

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

[Disasm]

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

[Scratch]

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

[Akon32]

Возможно, я не совсем правильно понимаю алгоритм (а алгоритма расшифровки вообще не нашёл, даже в 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 защищены тем же ключом и шифром, что и номер карты, то на деле они не так уж и защищены.

[Disasm]

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

[YourChief]

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

[Scratch]

а еще ему, как и одноразовому блокноту, нужен ключ размером с плеинтекст )