AEAD-режим блочного шифрування

AEAD-режими блочного шифрування (англ. Authenticated Encryption with Associated Data, «аутентифіковане шифрування з приєднаними даними») — клас блочних режимів шифрування, при якому частина повідомлення шифрується, частина залишається відкритою, і все повідомлення повністю аутентифікується. Вперше ідея такого класу шифрування була запропонована Charanjit Jutla у 2000 році[1]. В даний час запропоновано декілька AEAD-режимів шифрування: OCB mode^[en] (з версії OCB2), CCM mode^[en], EAX mode^[en], CWC mode^[en], і Galois/Counter Mode. Останній з 2007 року є стандартом NIST[2].

Виникнення проблеми

Існують алгоритми, що дозволяють здійснити аутентифікацію і шифрування — authenticated encryption (далі AE), проте в них не передбачена можливість прикріплювати відкритий текст (associated data), яка виникає, зокрема, при необхідності прикріпити до повідомлення IP-адреси. Взагалі, часто незашифровані дані потрібні для передачі заголовків, адрес, портів, версій протоколу та інших даних, що необхідні для прийняття рішення про те, як повинен оброблятися або пересилатися зашифрований текст. Часто ці дані повинні бути автентифіковано, в той же час залишаючись відкритими, щоб пристрої обробки могли оперувати з даними повідомленнями належним чином. Виникає бажання модифікувати AE-схему, додавши до неї імітовставку (MAC) для аутентифікації відкритих даних, і «задешево» отримати AEAD-схему. Однак, очевидні «наївні» рішення, приклади яких наведено нижче, виявляються неефективними[3].

Нехай, наприклад, потрібно передати повідомлення M, відкритий заголовок H, обраний будь-якого AE-режим шифрування E і функція MAC. Тоді, якщо передавати E (M) і H, то H виявиться не аутентифікованим. Якщо ж передати E (M || H) і H, довжина переданого повідомлення виявиться довшою за вихідний (так як буде виконана непотрібна в даній задачі операція шифрування H), то ж можна сказати й для випадку передачі H, E (M), MAC (H || E (M)) (так як E (M) вже аутентифікується і використання MAC вимагає витрати зайвих ресурсів)[3].

Важливо, що і AE-схеми, і AEAD-схеми вимагають використання nonce. Це необхідно для забезпечення семантичної безпеки (неможливість зловмисника при багаторазовому використанні схеми під одним і тим же ключем отримати відносини між сегментами зашифрованих повідомлень), а також для захисту від атаки повторного відтворення, при якій зловмисник під виглядом легального користувача повторно відправляє повідомлення. Генерація nonce і використання його тільки один раз лягає на відповідальність відправника. Для цього можна використовувати, наприклад, лічильник[3].

Методи реалізації

Encrypt-then-mac (AEAD)

Існують два принципово різних шляхи реалізації AEAD-режиму шифрування. Перший передбачає використання блочного режиму шифрування та імітовставки. У цьому випадком розробник AEAD-схеми може вибирати будь-який блоковий алгоритм шифрування і функцію отримання імітовставки, при цьому так само необхідно використовувати nonce. Другий спосіб — будь-яке перетворення AE-схеми. Вимоги до останнього методу залишаються незмінними: схема не повинна значно сповільнюватися, також в ній не повинно з'являтися нових вразливостей. Безпека й надійність даних підходів була доведена в статті Charanjit S. Jutla «Encryption Modes with Almost Free Message Integrity» за умови, що nonce не використовується повторно і хеш-функція H є криптографічно стійкою[4].

Методи реалізації AEAD-режиму за допомогою блочного шифру та імітовставки

Отримати AEAD-режим за допомогою блочного шифру та імітовставки можливо двома способами: спочатку шифруючи повідомлення, потім аутентифікуючи (encrypt-then-mac), або ж в зворотному порядку (mac-then-encrypt).

Encrypt-then-mac

В даному варіанті спочатку шифрується повідомлення M з використанням nonce N, потім заголовок H і зашифроване повідомлення автентифіковані за допомогою MAC з тим же nonce.

Mac-then-encrypt

Mac-then-encrypt (AEAD)

Аналогічно до попереднього, але в зворотному порядку: спочатку створюється імітовставка MAC від заголовка H, nonce N і відкритого тексту M, а потім шифрується повідомлення M з отриманої імітовставки з використанням того ж nonce N.

Методи реалізації AEAD-режиму за допомогою AE-схеми

Як було показано вище, ефективно прикріпити аутентифікований відкритий текст до збудованого за допомогою AE-схеми повідомленням примітивними способами, неможливо. Однак було запропоновано[1] два наступних методи[4].

Nonce stealing

Нехай є AE-схема, яка використовує nonce розміром n біт, а з додатком, що використовує дану схему, досить використовувати лише n2 бит (n2 < n). Тоді вільні h = n − n2 біт можуть бути використані для зберігання відкритих даних. Дана схема має обмеження на розмір відкритих даних, проте часто цього достатньо. Нехай алгоритм має nonce розміром 128 біт, а додаток використовує лише 16, тоді для відкритих даних залишається 112 біт, яких часто цілком достатньо (наприклад, для адреси в протоколі IPv4 потрібно 32 біта)[4].

Ciphertext translation

Даний метод приведення AE-схеми до AEAD-схемі заснований на операції логічного додавання (XOR) ${\displaystyle \oplus }$, при цьому, якщо проводиться операція над рядками різної довжини, то більш коротка доповнюється не значимими нулями, наприклад: ${\displaystyle 11101001\oplus 101=11101100}$.

Даний метод включає в себе наступні операції: використовується AE-схема для шифрування повідомлення з ключем K і отримання проміжного шифртексту CT, далі застосовується хеш-функція ${\displaystyle F_{K'}}$ для отримання зсуву Δ, і нарешті, фінальний шифротекст виходить в результаті застосування операції логічного складання Δ до останніх бітів CT. Зауважимо, що якщо заголовок є символом нового рядка, отримана AEAD-схема переходить в вихідну AE-схему шифрування. Якщо заголовок залишається незмінним протягом сесії, то зрушення Δ може бути обчислено заздалегідь, що позитивно позначається на часі шифрування — залишилася операція логічного додавання, яку легко можна реалізувати (в тому числі і апаратно)[4].

Визначимо одержувану AEAD-схему більш строго наступним чином: ${\displaystyle {\ddot {E}}_{K,K'}^{N,H}(M)=E_{K}^{N}(M)\oplus F_{K'}(H)}$

${\displaystyle {\ddot {D}}_{K,K'}^{N,H}(C)=D_{K}^{N}(C\oplus F_{K'}(H))}$

Тобто, припускаючи, що ${\displaystyle H\ ne0}$, обчислюємо ${\displaystyle F_{K'}(H)=}$ Δ довжиною в τ біт, зашифровувати M і виробляємо операцію логічного додавання останніх τ біт з Δ.

Даний метод має такі переваги:

• Застосуємо до будь-AE-схемою;
• Якщо не потрібно прикріплювати незашифровані дані H, вихідний AE-метод не ускладнюється;
• Якщо заголовок H не змінюється з плином часу, ${\displaystyle F_{K'}(H)}$ може бути заздалегідь обчислена.

Однак недолік методу полягає в необхідності використання двох ключів K і K'.

AEAD-алгоритми

Для прикладу опишемо деякі AEAD-алгоритми. Два з них засновані на AES GCM, два з них — на AES CCM. Один з алгоритмів в кожній парі використовує 128-бітний ключ, інший — 256 бітний.

AEAD AES 128 GCM

Даний алгоритм використовує AES-128 в якості алгоритму блочного шифрування, використовуючи ключ, nonce, повідомлення і заголовок в якості вхідних даних. Довжина заголовка — 16 байт. Зашифрований текст формується додаванням аутентифікаційного тегу до проміжного зашифрованого тексту, отриманого в якості вихідних даних GCM-шифрування. Вимоги до розмірів вхідних і вихідних даних наступні:

• Розмір nonce — 12 байт;
• Довжина ключа — 16 байт;
• Максимальний розмір повідомлення 2^36 — 31 байт;
• Максимальний розмір заголовка 2^61 — 1 байт;
• Максимальний розмір зашифрованого повідомлення 2^36 — 15 байт[4].

Таким чином, шифртекст на 16 байт довше вихідного відкритого повідомлення.

AEAD AES 256 GCM

Алгоритм повністю аналогічний попередньому, за винятком використання ключа розміром 32 байт і AES-256 GCM.

AEAD AES 128 CCM

Аналогічно до попереднього, за винятком використання CCM режиму замість GCM, при цьому:

• Розмір nonce 12 байт;
• Довжина ключа 16 байт;
• Максимальний розмір повідомлення 2^24 — 1 байт;
• Максимальний розмір заголовка 2^64 — 1 байт;
• Максимальний розмір зашифрованого повідомлення 2^24 + 15 байт[4].

Як і при використанні GCM, розмір шифротексту на 16 байт довший, ніж вихідне повідомлення.

AEAD AES 256 CCM

Алгоритм повністю аналогічний попередньому, за винятком використання ключа розміром 32 байта і AES-256 GCM.

Примітки

1. Jutla, Charanjit S. (2000-08-01) «Encryption Modes with Almost Free Message Integrity» [Архівовано 19 серпня 2012 у Wayback Machine.]. Cryptology ePrint Archive: Report 2000/039. IACR. Retrieved 2013-03-16
2. NIST Special Publication 800 -38D [Архівовано 5 серпня 2011 у Wayback Machine.], November, 2007, Recommendation for BlockCipher Modes of Operation: Galois / Counter Mode (GCM) and GMAC.
3. homepage^[недоступне посилання з червня 2019]
4. NIST homepage. Архів оригіналу за 25 квітня 2012. Процитовано 22 лютого 2022. [Архівовано 2012-04-25 у Wayback Machine.]

Посилання

• homepage^[недоступне посилання з червня 2019]
• NIST homepage [Архівовано 25 квітня 2012 у Wayback Machine.]
• An Interface and Algorithms for Authenticated Encryption Specifies