Режими блокового шифрування

У криптографії, режими дії (англ. modes of operation) — це математичні операції для уможливлення повторюваного і убезпеченого використання блокового шифру з одним ключем. Блоковий шифр дозволяє шифрування тільки одного блоку даних встановленої довжини. Для роботи з блоками різних довжин, дані спочатку потрібно розбити на окремі блоки встановленої даним шифром довжини. Зазвичай, останній блок треба доповнити до відповідної довжини підхожим доповненням. Режими дій описують процес шифрування кожного з цих блоків і звичайно використовують рандомізацію засновану на додатковому значені на вході, відомим як ініціалізаційний вектор, з ціллю зробити це безпечно.

Режими дії первісно були розроблені для шифрування й автентифікації. Історично, режими шифрування широко вивчались зважаючи на їх властивості поширення помилок при різних сценаріях зміни даних. Подальший розвиток поставив цілісність інформації як цілком окрему від шифрування ціль криптографії. Деякі сучасні режими дії поєднують шифрування і автентифікацію ефективним чином, і відомі як режими автентифікованого шифрування.

Хоча режими дії звичайно пов'язують з симетричним шифруванням, в принципі, їх також можна застосувати до примітивів шифрування з відкритим ключем таких як RSA (хоча на практиці шифрування довгих повідомлень з відкритим ключем найчастіше здійснюють із використанням гібридного шифрування).

Ініціалізаційний вектор (IV)

Ініціалізаційний вектор (англ. initialization vector) — це блок біт, який використовують декілька режимів для увипадковлення шифрування і, таким чином, видають різні шифротексти навіть на одному відкритому тексті зашифрованому декілька разів, без потреби в повільнішому процесі отримання нового ключа.

Ініціалізаційний вектор має інші вимоги до безпеки ніж ключ, отже він не повинен бути секретним. Однак, здебільшого, важливо щоб IV не використовувався двічі з одним і тим самим ключем. Для CBC і CFB, повторне використання IV призводить до витоку інформації про перший блок відкритого тексту. Для OFB і CTR, повторне використання IV повністю руйнує безпеку. В режимі CBC, IV повинен бути непрогнозовним під час шифрування; зокрема, звична раніше практика використання останнього блоку шифротексту як IV для наступного повідомлення небезпечна (цей метод, наприклад, використовувався в SSL 2.0). Якщо нападник знає IV (або попередній блок шифротексту) до того як він визначив наступний відкритий текст, він може перевірити свій здогад щодо відкритого тексту для якогось блоку зашифрованого раніше (це відомо як атака TLS CBC IV).

Як особливий випадок, якщо відкриті тексти завжди достатньо малі для одного блоку (без доповнення), тоді для деяких режимів (ECB, CBC, PCBC), перевикористання IV призведе до витоку лише якщо два шифротексти однакові. Це може бути корисним у випадках коли треба перевіряти на рівність без дешифрування.

Доповнення

Блоковий шифр опрацьовує інформацію блоками встановленої довжини (відомої як розмір блока), але повідомлення мають різну довжину. Отже деякі режими (а саме ECB і CBC) вимагають доповнення завершального блоку перед шифруванням. Існує декілька схем доповнення. Найпростіша полягає в додаванні нульових байтів до відкритого тексту для доведення його довжини до кратної до розміру блоку, але треба потурбуватись, щоб можна було відновити початкову довжину тексту; наприклад, якщо відкритий текст є рядком у стилі C, що не містить нульових байтів окрім як останній байт. Первісний метод DES трошки складніший, який додає один одиничний біт за яким слідують нульові біти; якщо повідомлення завершується врівно з блоком, додається цілий блок доповнення. Найускладненіший варіант схем специфічних для CBC таких як викрадення шифротексту або завершення залишкового блоку, які не призводять до збільшення шифротексту, натомість трошки ускладнюють алгоритм. Брюс Шнайдер і Нілс Ферґюсон запропонували дві можливості, обидві прості: додати байт зі значенням 128 (шістнадцяткове 80), з наступними нульовими байтами до повного блоку або доповнити n байтами зі значенням n.

CFB, OFB і CTR режими не потребують якихось особливих заходів для опрацювання повідомлень не кратних розміру блоку, бо режими працюють через XOR відкритого тексту з виходом блокового шифру. Останній неповний блок відкритого тексту XOR-иться з першими кількома байтами потоку ключа, на виході отримуємо завершальний блок шифротексту однакової довжини з завершальним блоком відкритого тексту. Така властивість потокових шифрів робить їх придатними для використання в ситуаціях коли необхідна однакова довжина шифро і відкритого тексту, і в застосунках де дані передаються в потоковому вигляді і незручно доповнювати блоки.

Електронна книга кодів (ECB)

Найпростішим з режимів шифрування є режим електронної книги кодів (англ. electronic codebook, ECB), він же режим простої заміни. Повідомлення розбивається на блоки і кожен блок шифрується окремо.

Вадою цього методу є те, що однакові блоки відкритого тексту шифруються в однакові блоки шифротексту; отже шаблон погано приховується. Цей режим не забезпечує серйозну безпеку повідомленням, і його взагалі не радять використовувати в криптографічних протоколах.

Типовий приклад ступеня збереження шаблонів ECB відкритого тексту в шифротексті можна побачити, коли ECB використовують для шифрування bitmap зображень, які використовують великі площі однорідних кольорів. Хоча колір кожного окремого пікселя зашифровано, загальну картинку можна розрізнити як маску однокольорових пікселів картинки на вході.

Первісне зображення

зашифроване в режимі ECB

Псевдовипадковий вислід режимів відмінних від ECB

Зображення праворуч показує як зображення може виглядати шифрованим урежимі CBC, CTR або будь-яким іншим безпечнішим режимом, і яке важко розрізнити з випадковим шумом. Зауважте, що псевдовипадковий вигляд зображення праворуч не гарантує, що зображення безпечно зашифроване; розроблено багато типів небезпечних шифрувань вихід яких виглядає випадковим.

Ланцюгування шифроблоків (CBC)

IBM винайшла режим ланцюгування шифроблоків (англ. cipher-block chaining, CBC) у 1976. В CBC режимі, кожен блок відкритого тексту XOR-ять з попереднім шифроблоком перед шифруванням. Так, кожен шифроблок, залежить від усіх блоків оброблених до нього. Для отримання унікальних повідомлень потрібно використовувати ініціалізаційний вектор у першому блоці.

Якщо перший блок має індекс 1, математична формула для CBC шифрування така

$C_{i}=E_{K}(P_{i}\oplus C_{i-1}),C_{0}=IV,$

тоді як математична формула для CBC розшифрування така

$P_{i}=D_{K}(C_{i})\oplus C_{i-1},C_{0}=IV.$

CBC найчастіше використовний режим. Основна його вада це властива послідовність (тобто не можливість упаралелення), і необхідність доповнення повідомлення до розміру кратного розміру блоку. Один зі способів уникнути доповнення полягає в використанні методу викрадення шифротексту. Зауважте, що зміна одного біта в відкритому тексті або IV впливає на всі наступні шифроблоки.

Розшифрування з неправильним IV спричиняє пошкодження першого блоку відкритого тексту, але наступні блоки будуть правильними. Це відбувається через можливість відновити відкритий текст з двох суміжних блоків шифротексту. Як наслідок, розшифрування можна упаралелити. Зауважте, що зміна одного біту в шифротексті спричиняє повне пошкодження відповідного блоку відкритого тексту, але інші блоки залишаються незачепленими.

Режим CBC не стійкий до атаки на основі підібраного шифротексту. Отримавши в CPA-запиті $(IV,c)$, в ССА-запиті передаємо $(IV\oplus 1,c).$

CBC теорема (непередбачуваність CBC)

Для будь-якого $L>0$, якщо $E$ є безпечною PRP над $(K,X)$, тоді $E_{CBC}$ — значеннєво безпечна щодо CPA над $(K,X^{L},X^{L+1})$.

Зокрема, для супротивника $A$ з q-запитами, що атакує $E_{CBC}$ існує PRP супротивник $B$ такий що:

$Adv_{CPA}[A,E_{CBC}]\leq 2Adv_{PRP}[B,E]+2q^{2}L^{2}/|X|.$

Отже CBC залишається безпечним доки $q^{2}L^{2}\ll |X|.$

Ланцюгування шифроблоків із поширенням (PCBC)

Режим ланцюгування шифроблоків із поширенням (англ. propagating cipher-block chaining, PCBC) або (англ. plaintext cipher-block chaining) спроектували для введення маленьких змін в шифротексті для нескінченного поширення при розшифруванні як і при шифруванні.

Шифрування і розшифрування такі:

$C_{i}=E_{K}(P_{i}\oplus P_{i-1}\oplus C_{i-1}),P_{0}\oplus C_{0}=IV$

$P_{i}=D_{K}(C_{i})\oplus P_{i-1}\oplus C_{i-1},P_{0}\oplus C_{0}=IV$

Кербер v4 і WASTE використовують PCBC. Якщо повідомлення зашифроване у PCBC режимі, тоді переставка двох сусідніх блоків не впливає на розшифрування наступних блоків. Через це, Кербер v5 не використовує PCBC.

Зворотний зв'язок по шифротексту (CFB)

Режим зворотного зв'язку по шифротексту (англ. cipher feedback, CFB), близький родич для CBC, перетворює блоковий шифр на потоковий, що самосинхронізується. Дія дуже схожа; зокрема, розшифрування CFB майже тотожне до шифрування CBC виконаного навпаки:

$C_{i}=E_{K}(C_{i-1})\oplus P_{i}$

$P_{i}=E_{K}(C_{i-1})\oplus C_{i}$

$C_{0}=\ {\mbox{IV}}$

Описаний вище найпростіший спосіб використання CFB ані трохи не більш самосинхронізовний ніж інші режими на кшталт CBC. Якщо губиться цілий блок шифротекту, то обидва CBC і CFB синхронізуються, тоді як втрата одного байту або біту остаточно відкине розшифрування. Для уможливлення синхронізації після втрати одного байту або біту, за раз треба шифрувати один байт або біт. CFB можна так використовувати разом з зсувним регістром на вході до блокового шифру.

На початку зсувний регістр заповнений ініціалізаційним вектором, і алгоритм шифрування запускається для утворення 64 біт виходу. Найлівіші 8 біт з бітів на виході XOR-ять з байтом до передачі. Вислід цієї операції посилають мережею, а також заштовхують в зсувний регістр, виштовхуючи найлівіші 8 бітів. Тоді алгоритм шифрування запускається знову і наступний символ шифрується так само.

Для використання CFB як самосинхронізовного потокового шифру, який синхронізуватиметься для будь-якої втрати кратної x бітам, починають з встановлення зсувного регістра розміром в один блок ініціалізаційним вектором. Це шифрується блоковим шифром, і старші x біт висліду XOR-рять з x бітами відкритого тексту для отримання x біт шифротексту. Ці x біт на виході заштовхуються в зсувний регістр, і процес повторюється з наступними x бітами відкритого тексту. Розшифрування схоже, починається з ініціалізаційним вектором, шифрується і XOR-иться x старших бітів висліду з x бітами шифротексту для отримання x бітів відкритого тексту. Заводимо x біт шифротексту в зсувний регістр. Цей спосіб обробки відомий як CFB-8 або CFB-1 (відповідно до розміру зсуву).

В записі, де $S_{i}$ — i-й стан зсувного регістра, $<<x$ це $a$ зсунуте на $x$ біт, ${\mbox{head}}(a,x)$ це $x$ старших бітів $a$ і $n$ це кількість біт в IV:

$C_{i}={\mbox{head}}(E_{K}(S_{i-1}),x)\oplus P_{i}$

$P_{i}={\mbox{head}}(E_{K}(S_{i-1}),x)\oplus C_{i}$

$S_{i}=\ ((S_{i-1}<<x)+C_{i}){\mbox{ mod }}2^{n}$

$S_{0}=\ {\mbox{IV}}$

Якщо x біт шифротексту втрачено, шифр видаватиме неправильний відкритий текст доки зсувний регістр не набуде стану, який він мав під час шифрування, тут шифр ресинхронізується. Це призводить до того, що підтасується вихід розміром в один блок.

Подібно до режиму CBC, зміни в відкритому тексту поширюються на весь шифротекст, і шифрування не можна упаралелити. Також подібно до CBC, розшифрування упаралельнюване. При розшифруванні, зміна одного біту в шифротексті впливає на два блоки відкритого тексту: однобітова зміна в відповідному блоці відкритого тексту і повне пошкодження наступного блоку. Подальші блоки розшифровуються нормально. Через це, якщо зловмисник знає відкритий текст, він може змінити біти в блоці шифротексту як він захоче і призвести до отримання потрібного йому блоку відкритого тексту, наступний блок буде перетасовано, але на той час вже може бути заподіяна шкода.

CFB разом з режимами потокових шифрів OFB і CTR поділяє дві переваги над CBC режимом: блок шифр використовується лише в напрямку шифрування, і повідомлення не потребує доповнення до розміру кратного розміру блоку (хоча також можна використати викрадення шифротексту і таким чином зробити доповнення необов'язковим).

Зворотний зв'язок по виходу (OFB)

Режим зворотного зв'язку по виходу (англ. output feedback, OFB) утворює з блокового шифру синхронний потоковий шифр. Він утворює потік ключа, який потім XOR-иться з блоками відкритого тексту для утворення шифротескту. Як і передбачає ім'я, OFB використовує попередній вихід блокового шифру, а не попередній шифротекст як CFB, що робить шифротекст незалежним від відкритого тексту і шифротексту, саме через це OFB є синхронним потоковим шифром. Так само як і з іншими потоковими шифрами, обернення біту в відкритому тексті призводить до обернення відповідного біту в шифротексті. Ця властивість дозволяє багатьом кодам виправлення помилок виконуватись нормально навіть при застосуванні до шифрування.

Через симетричність операції XOR, шифрування і розшифрування однакові:

$C_{j}=P_{j}\oplus O_{j}$

$P_{j}=C_{j}\oplus O_{j}$

$O_{j}=\ E_{K}(I_{j})$

$I_{j}=\ O_{j-1}$

$I_{0}=\ {\mbox{IV}}$

Для кожного нового повідомлення треба використовувати новий IV, інакше повідомлення будуть шифруватись з тим самим потоком ключа. IV можна відправляти у відкритому вигляді, однак, якщо зловмисник підмінив IV, тоді на відміну від CFB режиму, отримати відкритий текст з шифротексту неможливо.

Кожен блок на виході залежить від усіх попередніх, отже неможливе паралельне виконання. Однак, через те, що відкритий текст і шифр використовуються лише в фінальному XOR, операції блокового шифру можна виконати наперед, що дозволить виконання фінального кроку паралельно щойно відкритий або шифротекст стане доступним.

Можна отримати потік ключа для режиму OFB із рядком нулів на вході. Це може бути корисним, бо уможливлює використання швидкого апаратного забезпечення, що втілює CBC для шифрування в режимі OFB.

На відміну від CFB, помилка в одному біті відкритого тексту зачіпає лише відповідний біт в шифротексті, наступні блоки залишаються неушкодженими. Ця властивість разом із можливістю високої швидкодії OFB робить його підхожим для шифрування потоків даних на кшталт голосу і відео, особливо на каналах с завадами де поширення помилок може легко перетворити зашифроване передавання в майже неможливе. З іншого боку OFB вимагає від двох учасників бути синхронізованими. Як варіант розв'язання цієї проблеми пропонується відправляння синхронізаційних сигналів в узгоджені проміжки часу.

Середня тривалість циклу для s-бітового-OFB

Якщо OFB використовують зі зворотнім зв'язком обмеженим s < n біт (де n розмір блоку блокового шифру), найправішими n − s біт нехтують, і біти що залишились, стають наступними бітами потоку ключа, і також їх заштовхуються в зсувний регістр, який слугує входом для блокового шифру в s-бітовому-OFB. Досліди підтвердили, що OFB з s відмінним від 64 значно знижує рівень безпеки. Через це, підтримка урізаного зворотного зв'язку видалена зі специфікації OFB.

Безпечність потокових шифрів залежить від непередбачуваності потоку ключа. У випадку з OFB з DES (який діє на блоках по 64 біти) породжувач потоку ключа є скінченним автоматом з 2⁶⁴ отже він повторюється після 2⁶⁴ станів або менше. Davies і Parkin проаналізували умови за яких можна досягти найбільшу довжину циклу. В OFB з повним зворотнім зв'язком, потік ключа утворюється повторним застосуванням шифрування блоковим шифром, який є ефективно випадковим над усіма 2⁶⁴! переставок. Дійсна випадковість потоку ключа менш важлива ніж розмір циклу; і через те, що функція шифрування має однозначну обернену функцію розшифрування, для кожного ключа всі стани з 2⁶⁴ повинні бути членами одного циклу. Автори вважають середню тривалість циклу в 2⁶³ «достатньою для всіх практичних цілей», бо вона дуже близька до досяжного максимуму. Менші цикли можливі, але малоймовірні; наприклад імовірність циклу в 10⁶ або менше станів становить 2^-44.

Якщо OFB використовується зі зворотнім зв'язком s < n біт, найправішими n − s бітами нехтують, а ті що залишились стають продовженням потоку ключа і також заштовхуються в зсувний регістр, який слугує вхідним блоком для s-бітового-OFB. В цьому разі, для оцінки середньої тривалості циклу необхідна математична модель породжувача потоку ключа, але необхідні припущення було б важко довести. Отже Дейвіс і Паркін провели дослід, в якому використали зменшений до випадково обраної переставки з 256 станів на 8-бітовому регістрі DES. Для кожного значення s вони виконали тест з 10000 переставок і обрахували розподіл довжини циклу.

Дослід підтвердив їх теоретичні висліди, показав, що OFB з s відмінним від 64 значно знижує безпеку, бо середня довжина циклу зменшується у 2³² рази або більше. Дейвіс і Паркін запропонували, що s = n повинен бути єдиним визнаним OFB режимом. Немає переваг від використання OFB з іншими значеннями; більше того s-бітовий-OFB зменшує пропускну здатність у режимі CFB.

Лічильник (CTR)

Заувага: режим CTR також знають як режим цілочисельного лічильника (англ. integer counter mode, ICM) або режим сегментованого цілочисельного лічильника (англ. segmented integer counter, SIC)

Подібно до OFB, режим лічильника перетворює блоковий шифр в потоковий шифр. Він породжує наступний блок потоку ключа шифруванням послідовних значень «лічильника». Лічильник може бути будь-якою функцією, що видає послідовність, яка гарантовано не повторюється впродовж тривалого часу, насправді найпростішими і найпоширенішими є прості лічильники, що на кожному кроці збільшуються на одиницю. Використання простої детерміністичної функції викликає суперечки; критики кажуть, що «навмисне використання відомого систематичного входу в криптосистемі становить непотрібний ризик.» Наразі, режим CTR широко прийнятий, і проблеми похідні від входової функції розпізнаються як слабкість використовного блокового шифру, а не режиму CTR. Проте, існують пристосовані атаки подібні до атаки помилки устаткування (англ. Hardware Fault Attack), які покладаються на використання простого функції лічильника.

Режим CTR має подібні до OFB характеристики, але також має можливість довільного доступу під час розшифрування. Режим CTR добре підходить для використання на багатопроцесорній машині, де блоки можна шифрувати паралельно. Більше того, він не потерпає від проблеми короткого циклу, яка може вплинути на OFB.

Зауважте, що нонс на зображенні це те саме, що й ініціалізаційний вектор на інших зображеннях. IV/нонс і лічильник можна сполучати із використанням будь-якої операції без втрат (конкатенації, додавання або XOR) для отримання унікального блоку лічильника для шифрування.

У випадку використання режиму CTR з одним нонсом для шифрування цілого диску, повторне використання відтинку потоку ключа уможливлює нескладну атаку. Отже, кожного разу за зміни навіть малої ділянки даних, необхідно буде перешифрувати весь диск із використанням іншого нонса для підтримки безпеки, що не практично.

Galois/Counter Mode

Розширення режиму лічильника, яке крім шифрування дозволяє виробити код автентифікації повідомлення.

(XTS)

Режим XTS порівняно новий; NIST його стандартизував у січні 2010, після стандартизації IEEE в 2007. XTS призначений для специфічного застосування: шифрування одиниць даних сталої довжини (наприклад, дата секторів) на накопичувачах, насправді не схвалено жодного іншого застосування.