У криптографії шифрування, що зберігає формат (FPE), відноситься до шифрування таким чином, що вихід (шифрований текст) має той самий формат як вхідні дані (відкритий текст). Значення терміну «формат» різне. Зазвичай використовуються лише скінченні набори символів; числові, алфавітні або буквено-цифрові. Наприклад:
Шифрування 16-значного номера кредитної картки, щоб зашифрований текст був іншим 16-значним номером. Шифрування англійського слова, щоб зашифрований текст був іншим англійським словом. Шифрування n-бітного числа, щоб зашифрований текст був іншим n-бітовим числом (це визначення n-бітного блочного шифру).
Для таких скінченних областей визначення, а також для цілей обговорення нижче, шифр еквівалентний перестановці N цілих чисел }, де N — це розмір області визначення.
Мотивація
Обмеження довжини полів або форматів Однією з мотивів використання FPE є проблеми, пов'язані з інтеграцією шифрування в існуючі програми з чітко визначеними моделями даних. Типовим прикладом може бути , наприклад 1234567812345670 (16 байтів, лише цифри).
Додавання шифрування до таких програм може бути складним, якщо потрібно змінити моделі даних, оскільки зазвичай це передбачає зміну обмежень довжини поля або типів даних. Наприклад, вихід із типового блокового шифру перетворить номер кредитної картки на шістнадцяткове значення (наприклад,0x96a45cbcf9c2a9425cde9e274948cb67, 34 байти, шістнадцяткові цифри) або значення Base64 (наприклад, lqRcvPnCqUJc3p4nSUjLZw==, 24 байти, буквено-цифрові та спеціальні символи), що порушить роботу всіх існуючих програм, які очікують, що номер кредитної картки буде 16-значним.
Окрім простих проблем із форматуванням, за допомогою AES-128-CBC цей номер кредитної картки може бути зашифрований до шістнадцяткового значення 0xde015724b081ea7003de4593d792fd8b695b39e095c98f3a220ff43522a2df02. На додаток до проблем, викликаних створенням недійсних символів і збільшенням розміру даних, дані, зашифровані за допомогою режиму алгоритму шифрування CBC, також змінюють своє значення, коли їх розшифровують і знову шифрують. Це відбувається тому, що випадкове початкове значення, який використовується для ініціалізації алгоритму шифрування і включений як частина зашифрованого значення, відрізняється для кожної операції шифрування. Через це неможливо використовувати дані, зашифровані в режимі CBC, як унікальний ключ для ідентифікації рядка в базі даних.
FPE намагається спростити процес переходу, зберігаючи форматування та довжину вихідних даних, дозволяючи замінити значення відкритого тексту їх шифротекстом у застарілих програмах.
Порівняння з дійсно випадковими перестановками Хоча справді випадкова перестановка є ідеальним шифром FPE, для великих областей визначення неможливо попередньо створити та запам'ятати справді випадкову перестановку. Отже, проблема FPE полягає в тому, щоб створити псевдовипадкову перестановку з секретного ключа, таким чином, щоб час обчислення для окремого значення був малим (в ідеалі постійним, але, що найважливіше, меншим, ніж O(N)).
Порівняння з блочними шифрами n-бітовий блочний шифр технічно є FPE на наборі }. Якщо FPE потрібен для одного з цих наборів стандартного розміру (наприклад, n = 64 для DES і n = 128 для AES) можна використовувати блочний шифр потрібного розміру.
Однак у типовому використанні блочний шифр використовується в режимі роботи, що дозволяє йому шифрувати довільно довгі повідомлення, і з вектором ініціалізації, як обговорювалося вище. У цьому режимі блочний шифр не є FPE.
Визначення безпеки У криптографічній літературі (див. більшість посилань нижче) міра «хорошого» FPE полягає в тому, чи може зловмисник відрізнити FPE від дійсно випадкової перестановки. Постулюються різні типи зловмисників залежно від того, чи мають вони доступ до оракулів або відомих пар шифртекст/відкритий текст.
Алгоритми У більшості перерахованих тут підходів добре зрозумілий блочний шифр (наприклад, AES) використовується як примітив, який замінює ідеальну випадкову функцію. Це має перевагу в тому, що включення секретного ключа в алгоритм є простим. Там, де AES згадується в наступному обговоренні, будь-який інший хороший блочний шифр також буде працювати.
Конструкції FPE від Блека та Рогевея Впровадження FPE із стійкістю, доказово пов'язаною з базовим блочним шифром, було вперше здійснено у статті криптографами та ,John Black and Philip Rogaway, Ciphers with Arbitrary Domains, Proceedings RSA-CT, 2002, pp. 114—130. http://citeseer.ist.psu.edu/old/black00ciphers.html (http://www.cs.ucdavis.edu/~rogaway/papers/subset.pdf ) де описано три способи зробити це. Вони довели, що кожен із цих методів настільки ж безпечний, як і блочний шифр, який використовується для його створення. Це означає, що якщо алгоритм AES використовується для створення алгоритму FPE, то отриманий алгоритм FPE такий же безпечний, як і AES, оскільки супротивник, здатний зламати алгоритм FPE, також може зламати алгоритм AES. Отже, якщо AES безпечний, то і алгоритми FPE, побудовані на його основі, також безпечні. У нижче викладеному «E» позначає операцію шифрування AES, яка використовується для побудови алгоритму FPE, а «F» позначає операцію шифрування FPE.
FPE з префіксного шифру Один простий спосіб створити алгоритм FPE на — призначити псевдовипадкову вагу кожному цілому, а потім відсортувати за вагою. Ваги визначаються шляхом застосування існуючого блочного шифру до кожного цілого числа. Блек і Рогавей назвали цю техніку «префіксним шифром» і показали, що вона, ймовірно, настільки ж гарна, як використовуваний блоковий шифр.
Таким чином, щоб створити FPE на множині {0,1,2,3}, за допомогою ключа K застосувати AES(K) до кожного цілого числа, даючи, наприклад,
вага(0) = 0x56c644080098fc5570f2b329323dbf62 вага(1) = 0x08ee98c0d05e3dad3eb3d6236f23e7b7 вага(2) = 0x47d2e1bf72264fa01fb274465e56ba20 вага(3) = 0x077de40941c93774857961a8a772650d
Сортування [0,1,2,3] за вагою дає [3,1,2,0], тому шифр
F(0) = 3 F(1) = 1 F(2) = 2 F(3) = 0
Цей метод корисний лише для малих значень N. Для більших значень розмір таблиці пошук та необхідна кількість шифрувань для ініціалізації таблиці стають занадто великими для практичного застосування.
FPE з обходу циклу Якщо в областівизначення псевдовипадкової перестановки P існує набір M дозволених значень (наприклад, P може бути блочним шифром, таким як AES), алгоритм FPE можна створити з блочного шифру шляхом багаторазового застосування блочного шифру, поки результат не стане одним із дозволених значень (в межах M).
CycleWalkingFPE(x) { if P(x) is an element of M then return P(x) else return CycleWalkingFPE(P(x))
Рекурсія гарантовано завершиться. (Оскільки P є відображення один-в-один, а область визначення є скінченною, повторне застосування P утворює цикл, тому починаючи з точки M, цикл в кінцевому підсумку закінчиться на М.)
Це має перевагу в тому, що елементи M не потрібно відображати в послідовність {0,…,N-1} цілих чисел. Цей алгоритм має той недолік, коли M набагато менше за область визначення P, що для кожної операції може знадобитися занадто багато ітерацій. Якщо P є блоковим шифром фіксованого розміру, наприклад AES, є суворе обмеження на розміри M, для яких цей метод ефективний.
Наприклад, програма може захотіти зашифрувати 100-бітові значення за допомогою AES таким чином, щоб створити інше 100-бітове значення. За допомогою цього методу шифрування AES-128-ECB можна застосовувати, доки воно не досягне значення, для якого всі 28 найвищих бітів встановлені на 0, для чого знадобиться в середньому 228 ітерацій.
FPE з мережі Фейстеля Також можна створити алгоритм FPE, використовуючи мережу Фейстеля. Мережа Фейстеля потребує джерела псевдовипадкових значень для підключів для кожного раунду, а вихідні дані алгоритму AES можна використовувати як ці псевдовипадкові значення. Коли це буде зроблено, отримана конструкція Фейстеля буде гарною, якщо використовується достатня кількість раундів.Jacques Patarin, Luby-Rackoff: 7 Rounds Are Enough for 2n(1-epsilon) Security, Proceedings of CRYPTO 2003, Lecture Notes in Computer Science, Volume 2729, Oct 2003, pp. 513—529. https://www.iacr.org/archive/crypto2003/27290510/27290510.pdf ; also Jaques Patrin: Security of Random Feistel Schemes with 5 or more Rounds. https://www.iacr.org/archive/crypto2004/31520105/Version%20courte%20Format%20Springer.pdf
Один із способів реалізації алгоритму FPE з використанням AES і мережі Файстеля полягає в тому, щоб використовувати стільки бітів виводу AES, скільки необхідно, щоб дорівнювати довжині лівої або правої половини мережі Фейстеля. Наприклад, якщо підключем потрібне 24-розрядне значення, для цього значення можна використовувати найнижчі 24 біти виводу AES.
Це може призвести до того, що вихідні дані мережі Фейстеля не збережуть формат вхідних даних, але можна повторити мережу Фейстеля так само, як і техніку обходу циклу, щоб забезпечити збереження формату. Оскільки можна налаштувати розмір входів для мережі Фейстеля, можна зробити дуже ймовірним, що ця ітерація в середньому закінчиться дуже швидко. У випадку номерів кредитних карток, наприклад, існує 1015 можливих 16-значних номерів кредитних карток (з урахуванням надлишкової контрольної цифри), а оскільки 1015 ≈ 249.8, використовуючи 50-бітну мережу Фейстеля разом із циклічним обходом, буде створено алгоритм FPE, який в середньому шифрує досить швидко.
Перетасування Торпа Перетасування Торпа схоже на ідеалізоване перемішування карт або, що еквівалентно, на максимально незбалансований шифр Фейстеля, де одна сторона є одним бітом. Для незбалансованих шифрів Фейстеля легше довести безпеку, ніж для збалансованих.
Режим зі змінним розміром входу Для розмірів домену, які мають ступінь двійки, і існуючого блочного шифру з меншим розміром блоку, новий шифр може бути створений за допомогою режиму змінним розміром входу, як описано , Рогевеєм.
Шифр Hasty Pudding використовує спеціальні конструкції (не залежать від існуючих блочних шифрів як примітивів) для шифрування довільних скінченних малих областей визначення.
Режим FFSEM/FFX AES Режим FFSEM AES (специфікаціяTerence Spies, Feistel Finite Set Encryption Mode http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/ffsem/ffsem-spec.pdf ) який був прийнятий до розгляду NIST, використовує конструкцію мережі Фейстеля описану вище Блеком та Рогевеєм, з функцією раунду AES з однією невеликою модифікацією: використовується один ключ, який трохи змінюється для кожного раунду.
Станом на лютий 2010 року FFSEM був замінений режимом FFX, написаним , Філіпом Рогевеєм та Теренсом Спайсом. (специфікація,Mihir Bellare, Phillip Rogaway, Terence Spies: Mihir Bellare, Phillip Rogaway, Terence Spies: ).
FPE для шифрування JPEG 2000 У стандарті JPEG 2000 коди маркерів (у діапазоні від 0xFF90 до 0xFFFF) не повинні відображатися в відкритому тексті та зашифрованому тексті. Просту техніку модульного складання 0xFF90 неможливо застосувати для вирішення проблеми шифрування JPEG 2000. Наприклад, слова зашифрованого тексту 0x23FF і 0x9832 є дійсними, але їх комбінація 0x23FF9832 стає недійсною, оскільки вводить код маркера 0xFF98. Аналогічно, проста техніка обходу циклів не може бути застосована для вирішення проблеми шифрування JPEG2000, оскільки два дійсних блоки шифротексту можуть дати недійсний шифртекст, коли вони об'єднуються. Наприклад, якщо перший блок зашифрованого тексту закінчується байтами «…30FF», а другий блок шифротексту починається байтами «9832…», то в зашифрованому тексті з'явиться код маркера «0xFF98».