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. Нехай x = 0.
BigInteger x = BigInteger.ZERO;
// type for conversion 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®.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
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.