Введення в криптографію: симетричне шифрування

Що таке криптографія?

По суті, криптографія – це практика безпечного спілкування при наявності потенційних сторонніх недоброзичливців. Поняття безпечного спілкування має на увазі дві основні складові:

1. Захист від перехоплення: конфіденційність даних.
2. Захист від маніпуляції даними: цілісність інформації, що означає, що ніхто не може змінити відправляються вами дані, змусивши одержувача прийняти спотворені дані за дійсні.

Конфіденційність даних досягається за допомогою шифрування, яке може приймати дві форми: симетричну і асиметричну.

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

У цій статті ми зосередимося на симетричному шифруванні.

Два типу шифрів

Шифрування забезпечує конфіденційність даних і включає дві важливі складові:

1. Секретний ключ: в контексті симетричного шифрування можна припустити, що у наших учасників Аліси і Боба є загальний секретний ключ.
2. Шифр: алгоритми шифрування і дешифрування.

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

Є два типи симетричних шифрів: потокові і блокові. Для належного розуміння цих шифрів буде корисно знайомство з бітовими операціями, зокрема з «або» (XOR). Якщо коротко, то це складання двох бітів, при якому, якщо вони різні (0 і 1), результат дорівнює 1, а якщо вони однакові (два нуля або дві одиниці), результат дорівнює 0. У подальшому викладі передбачається, що читач знає, що таке XOR і що цю операцію прийнято позначати знаком ⊕.

Потоковий шифр

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

Уважні читачі, напевно, здогадалися, що у ключа і відкритого тексту повинно бути щось спільне, причому дуже важливе. Вірно! Ключ і відкритий текст повинні бути однакової довжини. Це, звичайно, не дуже практично.

Щоб зробити потоковий шифр більш практичним, використовуються генератори псевдовипадкових чисел. Генератор псевдовипадкових чисел – це детермінована процедура , яка на основі входу видає довший псевдовипадковий результат. «Детермінована» означає, що ця процедура при однаковому вході завжди видає один і той же вихід (т. Е. «Abc123» завжди дає «8474f24e0d72e1b949ffd2 …»). Слово «псевдовипадковий» означає, що хоча вихід насправді не випадковий (оскільки він детермінований на основі конкретного входу), він не відрізняється від справжніх випадкових рядків. Іншими словами, якщо мати набір входів і виходів, то неможливо зрозуміти, якого виходу відповідає який був вхід. Якщо використовувати в якості входу загальний секретний ключ, можна отримати більш довгий псевдовипадковий ключ, за допомогою якого буде проведена операція XOR над відкритим текстом такої ж довжини.

Описана реалізація потокового шифру називається «одноразовий блокнот». Дуже важливе її властивість полягає в тому, що ключ можна використовувати тільки ОДИН РАЗ. Якщо він використовується повторно, безпека повідомлень скомпрометована.

Нижче показаний слайд з курсу. PRG (K) позначає псевдовипадкову послідовність, згенерувану з нашого спільного ключа K. Символ ⊕ означає операцію XOR; C – шифротекст; m – повідомлення (відкритий текст).

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

Щоб не повторювати ключ одноразового блокнота, але зберегти один загальний секретний ключ, застосовується концепція Нонсо . Нонсо – це довільне число, яке в криптографічній комунікації може використовуватися тільки один раз. Разом з шіфротекстом можна також відправляти НОНС, який буде складатися з секретним ключем, щоб при кожному шифруванні давати інший псевдовипадковий ключ.

Блоковий шифр

Другий тип шифрів – блокові. Блоковий шифр використовує вхід фіксованої довжини і циклічно знову і знову шифрує вихідний текст, використовуючи кожен раз інший ключ ( «раундовий ключ»), поки не видасть шифротекст тієї ж довжини. 3DES і AES – два приклади блочних шифрів, які відповідно використовують вхід з 48 і 128 бітів.

На слайді вище показана базова архітектура блочного шифру. Як можна бачити, для отримання в кожному раунді нового ключа використовується алгоритм розширення ключа. Оригінальний текст (m) шифрується знову і знову, поки не буде отримано шифротекст (C) такої ж довжини.

Заради стислості в цій статті я буду розглядати AES. Незважаючи на історичну значимість DES / 3DES, AES сьогодні більш широко застосовується.

AES побудований як SP-мережа . AES використовує блоки розміром 128 бітів, що дорівнює 16 байтам. 16 байтів записуються як матриця 4 на 4. Така матриця зручна для операцій з даними. У кожному раунді процес наступний:

1. Проводимо операцію XOR над вихідним повідомленням і першим раундовим ключем (k0) .
2. Виконуємо підстановку, замінюючи блоки даних іншими на основі певної таблиці (процедура ByteSub) .
3. Проводимо перестановку, зрушуючи і перемішуючи біти (процедури ShiftRow і MixColumn) .
4. Процес повторюється 10 раундів.

В останньому раунді опускається процедура MixColumn, проводиться операція XOR з останнім раундовим ключем і отримуємо підсумковий шифротекст. Для розшифровки використовується зворотний процес. Тим, хто бажає заглибитися, можу порадити ознайомитися з мережею Фейстеля, яка використовується в 3DES, щоб порівняти різні блокові шифри.

Після запуску архітектури Westmere компанія Intel стала вбудовувати в свої процесори спеціальні інструкції для оптимізації AES, і незабаром за нею пішла AMD.

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

На відміну від потокових, блокові шифри використовують вхід фіксованої довжини. Очевидно, ми хочемо одночасно обробляти більше 16 байтів даних. Тому далі важливо зрозуміти режими, в яких можна застосовувати блокові шифри до великих обсягів даних. Перший з них – режим електронної кодової книги (ECB). ECB просто розбиває дані на блоки по 16 байтів і виконує AES-шифрування одноманітно. Це можна робити паралельно і дуже швидко. Однак це не дуже безпечно.

Причина в тому, що якщо 16-байтові повідомлення повторюються, шифротекст теж буде повторюватися. Так потенційний зловмисник зможе отримати інформацію про наші дані. Можна показати цю уразливість на прикладі зображення, зашифрованого за допомогою ECB. На зображенні нижче видно, що темне волосся і футболка дозволяють розрізнити обриси, за якими можна зрозуміти, що зашифрований знімок якоїсь особи.

Важливо, щоб схеми шифрування були семантично стійкими . Семантична стійкість означає, що, якщо є шифротекст, що відповідає одному з двох відкритих текстів, злочінець не може знати з вірогідністю більше 1/2, якого саме відкритого тексту він відповідає. Очевидно, що режим ECB семантично нестійкий. Зашифроване зображення видає багато інформації, що дозволяє здогадатися про інформацію.

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

У режимі зчеплення блоків шифротекста (CBC) кожен 16-байтовий блок відкритого тексту складається за допомогою операції XOR з шіфротекста попереднього блоку, а потім робиться блочне шифрування (AES).

Починаємо з випадкової векторної ініціалізації (IV) , тобто початкового значення в циклічному процесі. У разі CBC значення IV має бути випадковим (і, отже, непередбачуваним), а значить, унікальним в кожної транзакції. Перший блок шифротекста – це просто незашифрований випадковий IV. Щоб отримати решту шифротекст, спочатку проводиться операція XOR над випадковим IV і першим блоком відкритого тексту (m [0]). Результат шифрується за допомогою раундового ключа k, і отримуємо перший зашифрований блок шифротекста (c [0]). Далі проводиться операція XOR над цим шіфротекстом і наступним блоком відкритого тексту (m [1]), результат шифрується раундовим ключем k, і отримуємо наступний блок шифротексту (c [1]). Процес триває, поки не будуть зашифровані всі блоки.

Для розшифровки застосовується зворотний процес.

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

Спробую пояснити, як може виглядати така атака. Провести CPA при наявності передбачуваного IV можна через властивості XOR. Результат операції XOR над двома однаковими значеннями (наприклад, 0101 ⊕ 0101) завжди буде дорівнює нулю. Тому, якщо ви підозрюєте, що шифротекст c [0] відповідає певному відкритого тексту m [0], можна перевірити гіпотезу за допомогою передбачуваного IV. Якщо відкритий текст зашифрували за допомогою IV1 (c [0] = E (k, m [0] ⊕ IV1)), то можна зашифрувати новий відкритий текст і подивитися, співпаде чи результат з c [0]. Оскільки можна передбачити, що IV буде IV2, ви робите m [0] ⊕ IV1 ⊕ IV2. CBC виконає операцію XOR над цим входом і наступним IV (IV2): c [1] = E (k, m [0] ⊕ IV1 ⊕ IV2 ⊕ IV2). Отже, два IV2 взаємно знищуються, і ми знову шифруємо E (k, IV1 ⊕ m [0]), що, знову ж таки, дасть c [0],

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

Рандомізований режим лічильника також використовує випадковий IV, але тут він служить іншій меті. Наш ключ складається (наприклад, за допомогою AES) з ітерованих версій нашого IV: наприклад, в кожній ітерації можна збільшувати IV на одиницю, щоб результат не повторювався. Ми робимо це, поки не отримаємо ключ такої ж довжини, як наш відкритий текст. Тепер, як і в випадку потокового шифру з одноразовим ключем, ми проводимо операцію XOR над нашим відкритим текстом і псевдовипадковим ключем, щоб отримати шифротекст. Якщо у вашого комп’ютера є кілька AES-процесор, то це дуже ефективно, так як може виконуватися паралельно. У CBC кожен шифротекст залежить від попереднього блоку, тому обчислювати його паралельно неможливо.

Щоб отримати псевдовипадковий ключ з складання IV і нашого секретного ключа, блоковий шифр не обов’язковий. Блокові шифри повинні бути оборотні. Якщо уважно розглянути механізм рандомізованого режиму лічильника, то можна помітити, що для дешифрування не потрібно виконувати в зворотному порядку F (k, IV). З огляду на властивості XOR, досить взяти той же псевдовипадковий ключ і скласти його за допомогою XOR з нашим шіфротекста. Тобто для дешифрування потрібно повторити операцію, а не провести її в зворотному порядку.

Якщо виражатися абстрактно, це означає, що процедура, яку ми використовуємо для складання нашого секретного ключа і IV (F (k, IV)) повинна бути псевдослучайной функцією (PRF), а не псевдослучайной перестановкою ( PRP). Насправді ми стикалися з цими концепціями в цій статті. І PRF, і PRP – це детерміновані процедури, які при конкретному вході дають псевдовипадковий вихід (AES, XOR). Однак PRP має сувора вимога оборотності. Власне кажучи, поняття PRP і блоковий шифр (наприклад, AES) часто використовуються як синоніми. Але PRF НЕ повинна бути оборотною.

Отже, на цьому закінчується наш огляд симетричного шифрування. Ми розглянули потокові і блокові шифри. Потім, оскільки блокові шифри одночасно здатні обробляти лише 16 байтів, ми поговорили про режими їх застосування до великих відкритих текстів. Нарешті, ми також пояснили різницю між PRP і PRF.

Переклад статті Cryptography 101: Symmetric Encryption