Шифрування, що зберігає форматУ криптографії шифрування, що зберігає формат англ. Format-preserving encryption (FPE), відноситься до шифрування таким чином, що вихід (шифрований текст) має той самий формат як вхідні дані (відкритий текст). Значення терміну «формат» різне. Зазвичай використовуються лише скінченні набори символів; числові, алфавітні або буквено-цифрові. Наприклад:
Для таких скінченних областей визначення, а також для цілей обговорення нижче, шифр еквівалентний перестановці N цілих чисел {0, ... , N−1}, де N — це розмір області визначення. МотиваціяОбмеження довжини полів або форматівОднією з мотивів використання FPE є проблеми, пов'язані з інтеграцією шифрування в існуючі програми з чітко визначеними моделями даних. Типовим прикладом може бути номер кредитної картки[en], наприклад Додавання шифрування до таких програм може бути складним, якщо потрібно змінити моделі даних, оскільки зазвичай це передбачає зміну обмежень довжини поля або типів даних. Наприклад, вихід із типового блокового шифру перетворить номер кредитної картки на шістнадцяткове значення (наприклад, Окрім простих проблем із форматуванням, за допомогою AES-128-CBC цей номер кредитної картки може бути зашифрований до шістнадцяткового значення FPE намагається спростити процес переходу, зберігаючи форматування та довжину вихідних даних, дозволяючи замінити значення відкритого тексту їх шифротекстом у застарілих програмах. Порівняння з дійсно випадковими перестановкамиХоча справді випадкова перестановка є ідеальним шифром FPE, для великих областей визначення неможливо попередньо створити та запам'ятати справді випадкову перестановку. Отже, проблема FPE полягає в тому, щоб створити псевдовипадкову перестановку з секретного ключа, таким чином, щоб час обчислення для окремого значення був малим (в ідеалі постійним, але, що найважливіше, меншим, ніж O(N)). Порівняння з блочними шифрамиn-бітовий блочний шифр технічно є FPE на наборі {0, ..., 2n-1}. Якщо FPE потрібен для одного з цих наборів стандартного розміру (наприклад, n = 64 для DES і n = 128 для AES) можна використовувати блочний шифр потрібного розміру. Однак у типовому використанні блочний шифр використовується в режимі роботи, що дозволяє йому шифрувати довільно довгі повідомлення, і з вектором ініціалізації, як обговорювалося вище. У цьому режимі блочний шифр не є FPE. Визначення безпекиУ криптографічній літературі (див. більшість посилань нижче) міра «хорошого» FPE полягає в тому, чи може зловмисник відрізнити FPE від дійсно випадкової перестановки. Постулюються різні типи зловмисників залежно від того, чи мають вони доступ до оракулів або відомих пар шифртекст/відкритий текст. АлгоритмиУ більшості перерахованих тут підходів добре зрозумілий блочний шифр (наприклад, AES) використовується як примітив, який замінює ідеальну випадкову функцію. Це має перевагу в тому, що включення секретного ключа в алгоритм є простим. Там, де AES згадується в наступному обговоренні, будь-який інший хороший блочний шифр також буде працювати. Конструкції FPE від Блека та РогевеяВпровадження FPE із стійкістю, доказово пов'язаною з базовим блочним шифром, було вперше здійснено у статті криптографами Джоном Блеком[en] та Філіпом Рогевеєм[en],[1] де описано три способи зробити це. Вони довели, що кожен із цих методів настільки ж безпечний, як і блочний шифр, який використовується для його створення. Це означає, що якщо алгоритм AES використовується для створення алгоритму FPE, то отриманий алгоритм FPE такий же безпечний, як і AES, оскільки супротивник, здатний зламати алгоритм FPE, також може зламати алгоритм AES. Отже, якщо AES безпечний, то і алгоритми FPE, побудовані на його основі, також безпечні. У нижче викладеному «E» позначає операцію шифрування AES, яка використовується для побудови алгоритму FPE, а «F» позначає операцію шифрування FPE. FPE з префіксного шифруОдин простий спосіб створити алгоритм FPE на {0, ..., N-1} — призначити псевдовипадкову вагу кожному цілому, а потім відсортувати за вагою. Ваги визначаються шляхом застосування існуючого блочного шифру до кожного цілого числа. Блек і Рогавей назвали цю техніку «префіксним шифром» і показали, що вона, ймовірно, настільки ж гарна, як використовуваний блоковий шифр. Таким чином, щоб створити 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 можна використовувати як ці псевдовипадкові значення. Коли це буде зроблено, отримана конструкція Фейстеля буде гарною, якщо використовується достатня кількість раундів.[2] Один із способів реалізації алгоритму FPE з використанням AES і мережі Файстеля полягає в тому, щоб використовувати стільки бітів виводу AES, скільки необхідно, щоб дорівнювати довжині лівої або правої половини мережі Фейстеля. Наприклад, якщо підключем потрібне 24-розрядне значення, для цього значення можна використовувати найнижчі 24 біти виводу AES. Це може призвести до того, що вихідні дані мережі Фейстеля не збережуть формат вхідних даних, але можна повторити мережу Фейстеля так само, як і техніку обходу циклу, щоб забезпечити збереження формату. Оскільки можна налаштувати розмір входів для мережі Фейстеля, можна зробити дуже ймовірним, що ця ітерація в середньому закінчиться дуже швидко. У випадку номерів кредитних карток, наприклад, існує 1015 можливих 16-значних номерів кредитних карток (з урахуванням надлишкової контрольної цифри), а оскільки 1015 ≈ 249.8, використовуючи 50-бітну мережу Фейстеля разом із циклічним обходом, буде створено алгоритм FPE, який в середньому шифрує досить швидко. Перетасування ТорпаПеретасування Торпа схоже на ідеалізоване перемішування карт або, що еквівалентно, на максимально незбалансований шифр Фейстеля, де одна сторона є одним бітом. Для незбалансованих шифрів Фейстеля легше довести безпеку, ніж для збалансованих.[3] Режим зі змінним розміром входуДля розмірів домену, які мають ступінь двійки, і існуючого блочного шифру з меншим розміром блоку, новий шифр може бути створений за допомогою режиму змінним розміром входу, як описано Белларе[en], Рогевеєм.[4] Шифр Hasty PuddingШифр Hasty Pudding[en] використовує спеціальні конструкції (не залежать від існуючих блочних шифрів як примітивів) для шифрування довільних скінченних малих областей визначення. Режим FFSEM/FFX AESРежим FFSEM AES (специфікація[5]) який був прийнятий до розгляду NIST, використовує конструкцію мережі Фейстеля описану вище Блеком та Рогевеєм, з функцією раунду AES з однією невеликою модифікацією: використовується один ключ, який трохи змінюється для кожного раунду. Станом на лютий 2010 року FFSEM був замінений режимом FFX, написаним Міхіром Белларе[en], Філіпом Рогевеєм та Теренсом Спайсом. (специфікація,[6][7] NIST Block Cipher Modes Development, 2010, архів оригіналу за 4 вересня 2017, процитовано 25 березня 2022). FPE для шифрування JPEG 2000У стандарті JPEG 2000 коди маркерів (у діапазоні від 0xFF90 до 0xFFFF) не повинні відображатися в відкритому тексті та зашифрованому тексті. Просту техніку модульного складання 0xFF90 неможливо застосувати для вирішення проблеми шифрування JPEG 2000. Наприклад, слова зашифрованого тексту 0x23FF і 0x9832 є дійсними, але їх комбінація 0x23FF9832 стає недійсною, оскільки вводить код маркера 0xFF98. Аналогічно, проста техніка обходу циклів не може бути застосована для вирішення проблеми шифрування JPEG2000, оскільки два дійсних блоки шифротексту можуть дати недійсний шифртекст, коли вони об'єднуються. Наприклад, якщо перший блок зашифрованого тексту закінчується байтами «…30FF», а другий блок шифротексту починається байтами «9832…», то в зашифрованому тексті з'явиться код маркера «0xFF98». У статті Хунджуна Ву і Ді Ма «Efficient and Secure Encryption Schemes for JPEG2000»[8] наведено два механізми шифрування JPEG 2000, що зберігає формат. Метод шифрування JPEG 2000 із збереженням формату полягає у виключенні байта «0xFF» у шифруванні та дешифруванні. Потім механізм шифрування JPEG 2000 виконує додавання за модулем n з потоковим шифром; інший механізм шифрування JPEG 2000 виконує техніку обходу циклів з блоковим шифром. Інші конструкції FPEКілька конструкцій FPE засновані на додаванні вихідних даних стандартного шифру за модулем n до даних, які підлягають шифруванню, з різними методами протидії зміщенню результату. Додавання за модулем n, яке поділяється багатьма конструкціями, є відразу очевидним рішенням проблеми FPE (тому воно використовується в ряді випадків), причому основні відмінності полягають у використаних механізмах протидії зміщенню. Розділ 8 FIPS 74, Federal Information Processing Standards Publication 1981 Guidelines for Implementing and Using the NBS Data Encryption Standard,[9] описує спосіб використання алгоритму шифрування DES у спосіб, який зберігає формат даних за допомогою додавання за модулем n з подальшою операцією протидії зміщенню. Цей стандарт було скасовано 19 травня 2005 року, тому методику слід вважати застарілою з точки зору формального стандарту. Іншим раннім механізмом шифрування, що зберігає формат, було"Шифрування даних з обмеженим діапазоном значень"[10] авторства Пітера Гутмана[en], який знову виконує додавання за модулем n для будь-якого шифру з деякими налаштуваннями, щоб зробити результат однорідним, при цьому отримане шифрування буде таким же стійким, як і основний алгоритм шифрування, на якому воно засноване. У статті «Using Datatype-Preserving Encryption to Enhance Data Warehouse Security»[11] Майкла Брайтвелла та Гаррі Сміта описується спосіб використання алгоритму шифрування DES таким чином, щоб зберегти формат відкритого тексту. Здається, ця методика не застосовує крок протидії зміщенню, як інші методи за модулем n, на які тут є посилання. У статті «Format-Preserving Encryption»[12] автор Міхір Белларе і Томас Рістенпарт описують використання «майже збалансованих» мереж Фейстеля для створення безпечних алгоритмів FPE. У статті «Format Controlling Encryption Using Datatype Preserving Encryption»[13] Ульф Маттссон описує інші способи створення алгоритмів FPE. Прикладом алгоритму FPE є FNR (Flexible Naor and Reingold).[14] Прийняття алгоритмів FPE органами стандартизаціїСпеціальна публікація NIST 800-38G «Recommendation for Block Cipher Modes of Operation: Methods for Format-Preserving Encryption»[15] визначає два методи: FF1 і FF3. Детальну інформацію про пропозиції, подані для кожного, можна знайти на сайті NIST Block Cipher Modes Development,[16] включаючи інформацію про патенти та тестові вектори. Зразки значень доступні як для FF1, так і для FF3.[17]
Інший режим був включений до проекту керівництва NIST, але був вилучений перед остаточною публікацією.
Корея також розробила стандарт FPE FEA-1 і FEA-2. РеалізаціяРеалізації FF1 і FF3 з відкритим кодом є загальнодоступними мовами C[24], Go[25], Java[26], Node.js[27], Python[28], C#/.Net[29] та Rust[30] Примітки
|
Portal di Ensiklopedia Dunia
