Вікіпедія

Шифрування, що зберігає формат

У криптографії шифрування, що зберігає формат англ. Format-preserving encryption (FPE), відноситься до шифрування таким чином, що вихід (шифрований текст) має той самий формат як вхідні дані (відкритий текст). Значення терміну «формат» різне. Зазвичай використовуються лише скінченні набори символів; числові, алфавітні або буквено-цифрові. Наприклад:

  • Шифрування 16-значного номера кредитної картки, щоб зашифрований текст був іншим 16-значним номером.
  • Шифрування англійського слова, щоб зашифрований текст був іншим англійським словом.
  • Шифрування n-бітного числа, щоб зашифрований текст був іншим n-бітовим числом (це визначення n-бітного блочного шифру).

Для таких скінченних областей визначення, а також для цілей обговорення нижче, шифр еквівалентний перестановці N цілих чисел {0, ... , N−1}, де N — це розмір області визначення.

Мотивація ред.

Обмеження довжини полів або форматів ред.

Однією з мотивів використання FPE є проблеми, пов'язані з інтеграцією шифрування в існуючі програми з чітко визначеними моделями даних. Типовим прикладом може бути номер кредитної картки[en], наприклад 1234567812345670 (16 байтів, лише цифри).

Додавання шифрування до таких програм може бути складним, якщо потрібно змінити моделі даних, оскільки зазвичай це передбачає зміну обмежень довжини поля або типів даних. Наприклад, вихід із типового блокового шифру перетворить номер кредитної картки на шістнадцяткове значення (наприклад,0x96a45cbcf9c2a9425cde9e274948cb67, 34 байти, шістнадцяткові цифри) або значення Base64 (наприклад, lqRcvPnCqUJc3p4nSUjLZw==, 24 байти, буквено-цифрові та спеціальні символи), що порушить роботу всіх існуючих програм, які очікують, що номер кредитної картки буде 16-значним.

Окрім простих проблем із форматуванням, за допомогою AES-128-CBC цей номер кредитної картки може бути зашифрований до шістнадцяткового значення 0xde015724b081ea7003de4593d792fd8b695b39e095c98f3a220ff43522a2df02. На додаток до проблем, викликаних створенням недійсних символів і збільшенням розміру даних, дані, зашифровані за допомогою режиму алгоритму шифрування CBC, також змінюють своє значення, коли їх розшифровують і знову шифрують. Це відбувається тому, що випадкове початкове значення, який використовується для ініціалізації алгоритму шифрування і включений як частина зашифрованого значення, відрізняється для кожної операції шифрування. Через це неможливо використовувати дані, зашифровані в режимі 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]

  • FF1 є FFX[Radix] «Режим шифрування на основі мережі Фейстеля зі збереженням формату», який також знаходиться в процесі стандартизації у ANSI X9 як X9.119 і X9.124. Він був поданий до NIST Міхіром Белларе з Каліфорнійського університету в Сан-Дієго, Філіпом Рогевеєм з Каліфорнійського університету в Девісі та Теренсом Спайсом з Voltage Security Inc. Постачаються тестові вектори, а частина їх запатентована. DRAFT SP 800-38G Rev 1[18] вимагає, щоб мінімальний розмір області визначення шифруваних даних становив 1 мільйон (раніше 100).
  • FF3 — це BPS, названий на честь авторів. Його було подано до NIST Еріком Браєром, Томасом Пейріном та Жаком Стерном з Індженіко, Франція. Автори заявили NIST, що їхній алгоритм не запатентований.[19] Хоча CyberRes Voltage product [Архівовано 20 березня 2022 у Wayback Machine.] заявляє, що має патенти також на режим BPS.[20][21] 12 квітня 2017 року NIST дійшов висновку, що FF3 «більше не підходить як метод FPE загального призначення», оскільки дослідники виявили вразливість.[22]
  • FF3-1 (DRAFT SP 800-38G Rev 1)[18] замінює FF3 і вимагає, щоб мінімальний розмір домену шифруваних даних становив 1 мільйон (раніше 100).

Інший режим був включений до проекту керівництва NIST, але був вилучений перед остаточною публікацією.

  • FF2 — це схема VAES3 для FFX: додаток «Режим роботи FFX для зберігаючого шифрування»: набір параметрів для рядків шифрування з довільним принципом з операцією підключем для подовження терміну служби ключа шифрування. Він був поданий до NIST Йоахімом Венсом з VeriFone Systems Inc. Тестові вектори не постачаються окремо від FF1, а їх частини запатентовані. Автори подали модифікований алгоритм як DFF[23], який активно розглядається NIST.

Корея також розробила стандарт FPE FEA-1 і FEA-2.

Реалізація ред.

Реалізації FF1 і FF3 з відкритим кодом є загальнодоступними мовами C[24], Go[25], Java[26], Node.js[27], Python[28], C#/.Net[29] та Rust[30]

Примітки ред.

  1. ↑ John Black and Philip Rogaway, Ciphers with Arbitrary Domains, Proceedings RSA-CT, 2002, pp. 114—130. http://citeseer.ist.psu.edu/old/black00ciphers.html [Архівовано 16 грудня 2009 у Wayback Machine.] (http://www.cs.ucdavis.edu/~rogaway/papers/subset.pdf [Архівовано 23 жовтня 2020 у Wayback Machine.])
  2. ↑ 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 [Архівовано 1 лютого 2017 у Wayback Machine.]; 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 [Архівовано 20 жовтня 2016 у Wayback Machine.]
  3. ↑ Morris, Ben; Rogaway, Phillip; Stegers, Till (2009), How to Encipher Messages on a Small Domain (PDF), CRYPTO, архів оригіналу (PDF) за 23 жовтня 2020, процитовано 25 березня 2022
  4. ↑ Bellare, Mihir; Rogaway, Phillip (1999), On the construction of Variable-Input-Length Ciphers (PDF), архів оригіналу (PDF) за 16 липня 2011, процитовано 25 березня 2022
  5. ↑ Terence Spies, Feistel Finite Set Encryption Mode http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/ffsem/ffsem-spec.pdf [Архівовано 12 червня 2009 у Wayback Machine.]
  6. ↑ Mihir Bellare, Phillip Rogaway, Terence Spies: The FFX Mode of Operation for Format-Preserving Encryption (PDF), 2010, архів оригіналу (PDF) за 27 травня 2010, процитовано 25 березня 2022
  7. ↑ Mihir Bellare, Phillip Rogaway, Terence Spies: Addendum to "The FFX Mode of Operation for Format-Preserving Encryption" (PDF), 2010, архів оригіналу (PDF) за 16 травня 2017, процитовано 25 березня 2022
  8. ↑ Hongjun Wu, Di Ma, «Efficient and Secure Encryption Schemes for JPEG2000», International Conference on Acoustics, Speech, and Signal Processing (ICASSP 2004). MSP-L 1.6, Vol. V, pp. 869—872. http://www3.ntu.edu.sg/home/wuhj/research/publications/2004_ICASSP_JPEG2000.pdf [Архівовано 19 лютого 2018 у Wayback Machine.]
  9. ↑ FIPS 74, Federal Information Processing Standards Publication 1981 Guidelines for Implementing and Using the NBS Data Encryption Standard http://www.itl.nist.gov/fipspubs/fip74.htm [Архівовано 2014-01-03 у Wayback Machine.]
  10. ↑ Peter Gutmann, «Encrypting data with a restricted range of values», 23 January 1997, https://groups.google.com/group/sci.crypt/browse_thread/thread/6caf26496782e359/e576d7196b6cdb48 [Архівовано 9 листопада 2012 у Wayback Machine.]
  11. ↑ Michael Brightwell and Harry Smith, "Using Datatype-Preserving Encryption to Enhance Data Warehouse Security, Proceedings of the 1997 National Information Systems Security Conference https://portfolio.du.edu/portfolio/getportfoliofile?uid=135556 [Архівовано 2011-07-19 у Wayback Machine.]
  12. ↑ Mihir Bellare and Thomas Ristenpart, Format-Preserving Encryption http://eprint.iacr.org/2009/251 [Архівовано 4 серпня 2020 у Wayback Machine.]
  13. ↑ Ulf Mattsson, Format Controlling Encryption Using Datatype Preserving Encryption http://eprint.iacr.org/2009/257 [Архівовано 3 лютого 2019 у Wayback Machine.]
  14. ↑ Sashank Dara, Scott Fluhrer. Flexible Naor and Reingold. Cisco Systems Inc. Архів оригіналу за 16 жовтня 2014. Процитовано 26 березня 2022.
  15. ↑ Dworkin, Morris (2016), NIST Special Publication 800-38G, Recommendation for Block Cipher Modes of Operation: Methods for Format-Preserving Encryption, doi:10.6028/NIST.SP.800-38G
  16. ↑ NIST Block Cipher Modes Development, архів оригіналу за 4 вересня 2017, процитовано 25 березня 2022
  17. ↑ NIST Cryptographic Toolkit Example Algorithms, архів оригіналу за 27 березня 2016, процитовано 26 березня 2022
  18. ↑ а б SP 800-38G Rev. 1 (DRAFT) Recommendation for Block Cipher Modes of Operation: Methods for Format-Preserving Encryption. NIST. Feb 2019. Архів оригіналу за 2 квітня 2019. Процитовано 1 квітня 2019.
  19. ↑ BPS Authors Patent Declaration (PDF), архів оригіналу (PDF) за 9 березня 2016, процитовано 26 березня 2022
  20. ↑ HPE Voltage patent claims, архів оригіналу за 15 вересня 2017, процитовано 26 березня 2022
  21. ↑ Revised letter of assurance for essential patent claims FFX Mode of Operation for Format-Preserving Encryption (PDF), архів оригіналу (PDF) за 15 лютого 2017, процитовано 26 березня 2022
  22. ↑ Recent Cryptanalysis of FF3. NIST. 12 квітня 2017. Архів оригіналу за 2 березня 2020. Процитовано 5 травня 2020.
  23. ↑ FF2 Addendum DFF (PDF), архів оригіналу (PDF) за 9 квітня 2016, процитовано 26 березня 2022
  24. ↑ C [Архівовано 14 листопада 2021 у Wayback Machine.]
  25. ↑ Go [Архівовано 26 березня 2022 у Wayback Machine.]
  26. ↑ Java [Архівовано 26 березня 2022 у Wayback Machine.]
  27. ↑ Node.js [Архівовано 26 березня 2022 у Wayback Machine.]
  28. ↑ Python [Архівовано 26 березня 2022 у Wayback Machine.]
  29. ↑ C#/.Net [Архівовано 26 березня 2022 у Wayback Machine.]
  30. ↑ Rust [Архівовано 26 березня 2022 у Wayback Machine.]
Отримано з https://uk.wikipedia.org/w/index.php?title=Шифрування,_що_зберігає_формат&oldid=42194635