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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

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

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

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

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

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

Доповнення[ред.ред. код]

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

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

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

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

Ecb encryption.png

Ecb decryption.png

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

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

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

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

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

Cbc encryption.png

Cbc decryption.png

Якщо перший блок має індекс 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}] \le 2 Adv_{PRP}[B, E] + 2 q^2 L^2 / |X|.

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

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

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

Pcbc encryption.png

Pcbc decryption.png

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

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 режимі, тоді переставка двох сусідніх блоків не впливає на розшифрування наступних блоків.[8] Через це, Кербер 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 encryption.png

Cfb decryption.png

Описаний вище найпростіший спосіб використання 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 (відповідно до розміру зсуву).[9]

В записі, де 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}

Ofb encryption.png

Ofb decryption.png

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

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

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

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

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

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

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

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

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

Лічильник (CTR)[ред.ред. код]

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

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

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

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

Ctr encryption.png

Ctr decryption.png

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

(XTS)[ред.ред. код]

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

Примітки[ред.ред. код]

  1. а б в г Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone (1996). Handbook of Applied Cryptography. CRC Press. ISBN 0-8493-8523-7. 
  2. а б в «Block Cipher Modes». NIST Computer Security Resource Center. Архів оригіналу за 2012-11-20. 
  3. «FIPS 81: DES Modes of Operation». NIST Computer Security Resource Center. Архів оригіналу за 2013-07-22. 
  4. B. Moeller (May 20, 2004), Security of CBC Ciphersuites in SSL/TLS: Problems and Countermeasures, http://www.openssl.org/~bodo/tls-cbc.txt 
  5. William F. Ehrsam, Carl H. W. Meyer, John L. Smith, Walter L. Tuchman, "Message verification and transmission error detection by block chaining", US Patent 4074066, 1976
  6. Propagating cipher-block chaining
  7. Kaufman, C., Perlman, R., & Speciner, M (2002). Network Security. Upper Saddle River, NJ: Prentice Hall. Page 319 (2nd Ed.)
  8. Kohl, J. "The Use of Encryption in Kerberos for Network Authentication", Proceedings, Crypto '89, 1989; published by Springer-Verlag; http://dsns.csie.nctu.edu.tw/research/crypto/HTML/PDF/C89/35.PDF
  9. NIST: Recommendation for Block Cipher Modes of Operation
  10. Building Stream Ciphers from Block Ciphers and their Security, page 12
  11. D. W. Davies and G. I. P. Parkin. The average cycle size of the key stream in output feedback encipherment. In Advances in Cryptology, Proceedings of CRYPTO 82, pages 263–282, 1982.Б.
  12. Robert R. Jueneman. Analysis of certain aspects of output feedback mode. In Advances in Cryptology, Proceedings of CRYPTO 82, pages 99–127, 1982.
  13. Helger Lipmaa, Phillip Rogaway, and David Wagner. Comments to NIST concerning AES modes of operation: CTR-mode encryption. 2000
  14. R. Tirtea and G. Deconinck. Specifications overview for counter mode of operation. security aspects in case of faults. In Electrotechnical Conference, 2004. MELECON 2004. Proceedings of the 12th IEEE Mediterranean, pages 769–773 Vol.2, 2004.
  15. http://www.quadibloc.com/crypto/co040601.htm
  16. Performing File or Disk Encryption на etutorials.org
  17. Рекомендації для Режиму блочного шифрування: Режим XTS-AES для конфіденційності на накопичувачах, NIST. (англ.)
  18. IEEE Std. 1619-2007, IEEE стандарт для криптографічного захисту даних на блоково-орієнтованих накопичувачах. IEEE Press, квітень 2008.