Алгоритм криптографічного перетворення згідно з держстандартом 28147 89. Вітчизняний стандарт шифрування даних. Вироблення імітівставки до масиву даних

). Одночасно з цим у російських ЗМІ і блогах російських користувачів зростає кількість нотаток про даний алгоритм: як результати атак на російський стандарт, що висвітлюють різного ступеня достовірності, так і містять думки про його експлуатаційні характеристики. У авторів (а, отже, і читачів) даних нотаток найчастіше складається враження, що вітчизняний алгоритм шифрування є морально застарілим, повільним і володіючим уразливістю, що роблять його схильним до атак значною мірою більше, ніж зарубіжні алгоритми шифрування з аналогічною довжиною ключа. Даною серією нотаток ми хотіли б у доступній формі розповісти про справжній стан справ із російським стандартом. У першій частині буде висвітлено всі відомі міжнародної криптографічної громадськості атаки на ГОСТ 28147-89, поточні оцінки його стійкості. У майбутніх публікаціях ми також докладно розглянемо властивості стандарту з погляду можливості побудови ефективних реалізацій.

Ніколя Куртуа - «великий та жахливий»

Почнемо з розповіді про діяльність Ніколя Куртуа, яка є автором цілого циклу робіт, присвячених російському стандарту блокового шифрування ().

У жовтні 2010 року розпочато процес розгляду питання про включення алгоритму ГОСТ 28147-89 до міжнародного стандарту ISO/IEC 18033-3. Вже у травні 2011 року на електронному архіві ePrint з'явилася стаття відомого криптографа Ніколя Куртуа, відзначеного вельми неоднозначним ставленням до нього світової криптографічної спільноти. Публікації Куртуа являють собою сумний приклад маніпулювання поняттями, яке не відкриває жодних нових властивостей об'єкта, що розглядається, але з претензією на сенсацію провокує поширення в некомпетентному середовищі помилкових думок про його дійсні властивості.

Алгебраїчний метод

Міркування Куртуа будуються навколо двох класів методів криптоаналізу: методів алгебри і диференціальних. Розглянемо перший клас методів.

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

Алгебраїчний метод, який експлуатується Куртуа, коротко можна описати так. На першому етапі використовуються такі властивості ГОСТ 28147-89 як існування нерухомої точки для частини шифруючого перетворення, а також так званої точки відображення (reflection point). Завдяки цим властивостям із досить великої кількості пар відкритих-шифрованих текстів вибирається кілька пар, які дозволяють розглядати перетворення не так на 32, а лише на 8 раундах. Другий етап полягає в тому, що за отриманими на першому етапі результатами 8 раундових перетворень будується система нелінійних рівнянь, невідомими в якій є біти ключа. Далі ця система вирішується (це звучить просто, але насправді є трудомісткою частиною методу, тому що система складається з нелінійних рівнянь).

Як уже зазначалося вище, ніде в роботі немає детального опису та аналізу трудомісткості другого та головного етапу визначення ключа. Саме трудомісткість другого етапу визначає трудомісткість всього методу загалом. Натомість автор наводить горезвісні «факти», на основі яких робить оцінки трудомісткості. Стверджується, що це «факти» засновані на результатах експериментів. Аналіз «фактів» із роботи Куртуа загалом наведено у роботі вітчизняних авторів. Авторами цієї роботи зазначається, що багато хто з представлених без будь-яких доказів «фактів» Куртуа під час експериментальної перевірки виявився хибним. Автори статті пішли далі та за Куртуа провели аналіз трудомісткості другого етапу за допомогою добре обґрунтованих алгоритмів та оцінок. Отримані в результаті оцінки трудомісткості показують повну нездатність представленої атаки. Крім вітчизняних авторів, великі проблеми, які виникають у Куртуа з оцінками та обґрунтуванням своїх методів, відзначалися також, наприклад, у роботі.

Диференціальний метод

Розглянемо другий метод Куртуа, який ґрунтується на диференціальному криптоаналізі.

Загальний метод диференціального криптоаналізу базується на експлуатації властивостей використовуваних криптографічних примітивах нелінійних відображень, пов'язаних з впливом значення ключа на залежності між різницями пар вхідних і пар вихідних значень даних відображень. Наведемо основну ідею диференціального методу криптографічного аналізу блокового шифру. Зазвичай блокові шифри перетворюють вхідні дані поетапно за допомогою деякої кількості про раундових перетворень, причому кожне раундове перетворення використовує не весь ключ, а лише деяку його частину. Розглянемо трохи "усічений" шифр, який відрізняється від вихідного тим, що в ньому немає останнього раунду. Припустимо, що вдалося встановити, що в результаті зашифрування за допомогою такого «усіченого» шифру двох відкритих текстів, які відрізняються в деяких фіксованих позиціях, з великою ймовірністю виходять шифртексти, які також відрізняються в деяких фіксованих позиціях. Ця властивість показує, що «усічений» шифр з великою ймовірністю залишає залежність між деякими відкритими текстами та результатами їхнього зашифрування. Щоб за допомогою цього явного недоліку відновити частину ключа, необхідно мати можливість зашифрувати заздалегідь вибрані відкриті тексти на тому ключі, який ми хочемо відновити (так звана атака з вибраним відкритим текстом). На початку процедури «розкриття ключа» випадково генерується кілька пар відкритих текстів, які у тих самих фіксованих позиціях. Усі тексти зашифровуються за допомогою повного шифру. Отримані пари шифртекстів використовуються для відновлення тих біт ключа, які використовуються в останньому раундовому перетворенні, наступним чином. За допомогою деякого вибраного навмання значення бітів ключа, що шукаються, до всіх шифртекстів застосовується перетворення, зворотне останньому раундовому перетворення. По суті, якщо ми вгадали потрібне значення бітів ключа, ми отримаємо результат роботи «усіченого» шифру, а якщо не вгадали – ми фактично «ще більше зашифруємо дані», що тільки зменшить помічену вище залежність між блоками (відмінність у деяких фіксованих позиціях). Іншими словами, якщо серед результатів такої «дообробки» шифртекстів знайшлося досить багато пар, що відрізняються у відомих нам фіксованих позиціях, це означає, що ми вгадали шукані біти ключа. Інакше таких пар знайдеться значно менше. Оскільки в кожному раунді використовується тільки частина ключа, шуканих бітів (тобто бітів ключа, що використовуються в останньому раунді) не так багато, як бітів у повному ключі і їх можна просто перебрати, повторюючи наведені вище дії. У такому разі ми обов'язково колись натрапимо на правильне значення.

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

Куртуа використовує дещо модифікований варіант диференціального методу. Відразу зазначимо, що свій аналіз Куртуа проводить для S-блоків, відмінних від діючих і запропонованих ISO. У роботі наводяться диференціальні характеристики (ті самі номери, у яких мають відрізнятися блоки) для малого числа раундів. Обґрунтування продовження характеристик на більшу кількість раундів, як водиться, ґрунтується на «фактах». Куртуа висловлює, знову ж таки, нічим, крім його авторитету, не підкріплене припущення, що зміна S-блоків не вплине на стійкість ГОСТ 28147-89 проти його атаки (при цьому з незрозумілих причин S-блоки з 1-го робочого проекту доповнення до стандарту ISO/IEC 18033-3 не розглядалися). Аналіз, проведений авторами статті, показує, що навіть якщо прийняти на віру необґрунтовані «факти» Куртуа та провести аналіз ГОСТ 28147-89 з іншими S-блоками, то атака знову ж таки виявляється не кращою за повний перебір.

Детальний аналіз робіт Куртуа з докладним обгрунтуванням безпідставності всіх тверджень про зниження стійкості російського стандарту було проведено на роботах [ , ].

При цьому абсолютну відсутність акуратності викладок визнає навіть сам Куртуа! Наступний слайд взятий із презентації Куртуа на секції коротких оголошень FSE 2012.

Необхідно відзначити, що роботи Куртуа неодноразово критикувалися також зарубіжними дослідниками. Наприклад, його роботи з побудови атак на алгоритм блокового шифрування AES за допомогою XSL-методу містили ті ж принципові недоробки, що і роботи з аналізу російського стандарту: більшість оцінок трудомісткості з'являється в тексті абсолютно безпідставно і бездоказово - докладну критику можна знайти, наприклад, роботі. Крім того, сам Куртуа визнає повсюдні відмови в публікації його робіт на великих криптографічних конференціях і в визнаних журналах, що рецензуються, залишали йому часто лише можливість виступити на секції коротких оголошень. Про це, наприклад, можна прочитати у розділі 3 роботи. Ось деякі цитати, що наводяться самим Куртуа і пов'язані з його роботами:

• "Я думаю, що аудиторії з Asiacrypt не будуть зайняти ним інтерес". Рецензент Asiacrypt 2011
• «… there is a big, big, big problem: this attack, which is the main contribution of the paper has already been published at FSE'11 (it was even the best paper), …». Рецензент Crypto 2011

Таким чином, професійна частина міжнародної криптографічної громадськості відноситься до якості робіт Куртуа з не меншим сумнівом, ніж, скажімо, до не підтверджених жодними послідовними викладками заяв деяких російських фахівців про їхнє вміння зламувати AES за 2 100 або до чергових "доказів" на дві сторінки про нерівність складних класів P і NP.

Атаки Ісобі та Дінура-Данкельмана-Шаміра

Загальна ідея атак Ісобі () і Дінура-Данкельмана-Шаміра (далі: атака ДДШ) () полягає в побудові для певної (залежної від ключа) вузької множини відкритих текстів еквівалентного на цій множині перетворення, що має більш просту, ніж саме шифруюче перетворення, . У випадку методу Ісобі це безліч таких 64-бітових блоків x, що F 8 -1 (Swap(F 8 (z))) = z де z = F 16 (x), через F 8 (x) і F 16 ( x) позначені перші 8 та перші 16 раундів шифрування ГОСТ 28147-89 відповідно, через Swap - операція обміну місцями половинок 64-байтового слова. При попаданні відкритого тексту в це безліч результату повного 32-раундового перетворення ГОСТ 28147-89 збігається з результатом 16-раундового, що й експлуатується автором атаки. У разі методу ДДШ це безліч таких x, що F 8 (x) = x (нерухлива точка перетворення F 8). Для будь-якого відкритого тексту з цієї множини перетворення ГОСТ 28147-89 працює точно так само, як останні його 8 раундів, що і спрощує аналіз.

Трудомісткість атаки Ісобі становить 2224 операцій зашифрування, атаки ДДШ - 2192 . Однак всі питання про те, чи атаки Ісобі та ДДШ вносять нові обмеження на умови застосування нашого алгоритму, знімає оцінка вимог до обсягу матеріалу, необхідного для проведення кожної з атак: для методу Ісобі потрібно 2 32 пар відкритих і шифрованих текстів, а для методу ДДШ - 2 64 . Обробка таких обсягів матеріалу без зміни ключа апріорно неприйнятна для будь-якого блокового шифру з довжиною блоку 64: на матеріалі об'ємом 2 32 з урахуванням завдання про дні народження (див., наприклад, ), близька до 1/2 ймовірність появи блоків, що повторюються, що надасть порушнику можливість робити за шифрованими текстами деякі висновки про відкриті тексти без визначення ключа. Наявність же 264 пар відкритих і шифрованих текстів, отриманих на одному ключі, фактично дозволяє противнику здійснювати операції зашифрування і розшифрування взагалі без знання цього ключа. Це зумовлено суто комбінаторним властивістю: противник у разі має всієї таблицею шифруючого перетворення. Така ситуація абсолютно неприпустима за жодних розумних експлуатаційних вимог. Наприклад, у КриптоПро CSP є технічне обмеження на обсяг шифрованого (без перетворення ключа) матеріалу в 4 Мб (див. ). Таким чином, сувора заборона на використання ключа на матеріалі такого обсягу властивий будь-якому блоковому шифру з довжиною блоку 64 біта, а отже, атаки Ісобі і ДДШ жодним чином не звужують область використання алгоритму ГОСТ 28147-89 при збереженні максимально можливої ​​стійкості 2256 .

Безумовно, не можна не відзначити, що дослідниками (Ісобі та Динуром-Данкельманом-Шаміром) було показано, що деякі властивості алгоритму ГОСТ 28147-89 дозволяють знаходити шляхи аналізу, не враховані творцями алгоритму. Простий вигляд ключового розкладу, що суттєво спрощує завдання побудови ефективних реалізацій, також дозволяє для деяких рідкісних випадків ключів та відкритих текстів будувати простіші описи перетворень, що виробляються алгоритмом.

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

Зазначимо, що певні недбалості в оцінках середньої трудомісткості присутні й у роботі Дінура, Данкельмана та Шаміра. Так, при побудові атаки не приділяється належної уваги наступному моменту: для істотної частки ключів безліч відкритих текстів x, таких, що F 8 (x) = x є порожнім: нерухомих точок у 8 раундів перетворення може просто не бути. Існування нерухомих точок залежить також від вибору вузлів заміни. Таким чином, атака застосовується тільки при певних вузлах заміни та ключах.

Варто згадати також ще одну роботу з атакою на ГОСТ 28147-89. У лютому 2012 року на електронному архіві ePrint міжнародної криптографічної асоціації з'явилася оновлена ​​версія статті (від листопада 2011 року), яка містила нову атаку на ГОСТ 28147-89. Характеристики представленої атаки такі: обсяг матеріалу - 232 (як у Ісобі), а трудомісткість - 2192 (як у ДДШ). Таким чином, ця атака покращувала рекордну за часом атаку ДДШ за обсягом матеріалу з 264 до 232 . Зазначимо окремо, що автори чесно навели усі викладки з обґрунтуванням трудомісткості та обсягу матеріалу. Через 9 місяців у наведених викладках було знайдено принципову помилку, і з листопада 2012 року оновлена ​​версія статті в електронному архіві вже не містить жодних результатів щодо вітчизняного алгоритму.

Атаки у припущенні, що порушник знає «щось» про ключі

Зауважимо насамкінець, що у літературі також є кілька робіт (див., наприклад, і ), присвячених атакам на ГОСТ 28147-89 у так званої моделі зі зв'язаними ключами. Дана модель у своїй основі містить припущення про можливість порушника отримувати доступ для аналізу не просто до пар відкритих і шифрованих за допомогою шуканого ключа текстів, але також до пар відкритих і шифрованих текстів, отриманих за допомогою (також невідомих) ключів, що відрізняються від відомим регулярним (наприклад, у фіксованих бітових позиціях). У даній моделі дійсно вдається отримати цікаві результати про ГОСТ 28147-89, проте в цій моделі не менш сильні результати вдається отримувати і про, наприклад, стандарті AES, що отримав найбільш широке поширення в сучасних мережах загального користування (див., наприклад, ). Зауважимо, що умови для проведення таких атак виникають при використанні шифру в деякому протоколі. Не можна не відзначити, що результати такого роду, хоч і становлять безперечний академічний інтерес з погляду вивчення властивостей криптографічних перетворень, але фактично не належать до практики. Наприклад, всі сертифіковані ФСБ Росії засоби криптографічного захисту інформації виконують найсуворіші вимоги щодо схем вироблення ключів шифрування (див., наприклад, ). Як зазначено в результатах проведеного аналізу, за наявності 18 пов'язаних ключів і 2 10 пар блоків відкритого і шифрованого тексту трудомісткість повного розкриття закритого ключа, при ймовірності успіху 1-10 -4 , дійсно становить 2 26 . Однак при дотриманні згаданих вище вимог з вироблення ключового матеріалу ймовірність виявлення таких ключів дорівнює 2 -4352, тобто в 24096 разів менше, ніж якщо просто спробувати вгадати секретний ключ з першої спроби.

До робіт, що належать до моделі зі зв'язаними ключами, відноситься також і робота, що наробила в 2010 році багато шуму в російських електронних виданнях, які не страждають від звички уважно перевіряти матеріал у процесі гонки за сенсаціями. Результати, представлені в ній, не були підкріплені якимось суворим обґрунтуванням, зате містили гучні заяви про можливість зламувати державний стандарт Російської Федерації на слабкому ноутбуці за лічені секунди - загалом, стаття була написана в кращих традиціях Ніколя Куртуа. Але, незважаючи на цілком очевидну хоч трохи знайомому з основними принципами науковості публікацій читачеві безпідставність статті, саме для заспокоєння російської громадськості після роботи Рудським був написаний докладний і докладний текст, що містить всебічний аналіз цієї недостатності. У статті з назвою "Про нульову практичну значущість роботи "Key recovery attack on full GOST block cipher with zero time and memory"" наводиться обґрунтування того, що середня трудомісткість наведеного в методу не менше, ніж трудомісткість повного перебору.

Сухий залишок: яка стійкість практично?

На закінчення наведемо таблицю, що містить дані про всі відомі міжнародному криптографічного співтовариства результати строго описаних та обґрунтованих атак на ГОСТ 28147-89. Зазначимо, що складність наводиться в операціях зашифрування алгоритму ГОСТ 28147-89, а пам'ять та матеріал вказані в блоках алгоритму (64 біти = 8 байт).

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

У нашій країні встановлено єдиний алгоритм криптографічного подання даних для систем обробки інформації в мережах ЕОМ, окремих обчислювальних комплексів та ЕОМ, що визначається ГОСТ 28147-89.

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

При описі алгоритму використовуються такі позначення:

L та R - послідовності бітів;
LR - конкатенація послідовностей L і R, в якій біти послідовності R йдуть за бітами послідовності L;
(+) - порозрядне додавання за модулем 2 (операція "що виключає АБО");
[+] - додавання 32-розрядних чисел за модулем 2 32;
(+) - додавання 32-розрядних чисел за модулем 2 32 -1.

Числа підсумовуються за таким правилом:

A [+] B = A + B, якщо A + B< 2 32 ,
A [+] B = A + B - 2 32 якщо A + B >= 2 32 . A (+) B = A + B якщо A + B< 2^32 - 1, A {+} B = A + B - (2^32 - 1), если A + B >= 2^32 - 1.

Алгоритм передбачає чотири режими роботи:

У будь-якому випадку для шифрування даних використовується 256-бітовий ключ K, який представляється у вигляді восьми 32-бітових підключів K i:

K = K 7 K 6 K 5 K 4 K 3 K 2 K 1 K 0 .

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

Режим простої заміни

Перший і найпростіший режим - заміна. Дані, що підлягають шифруванню, розбивають на 64-бітові блоки. Процедура шифрування блоку відкритих даних T0 включає 32 цикли (j=1...32).

Блок T 0 поділяється на дві послідовності по 32 біти: В(0)A(0), де В(0) - ліві або старші біти, A(0) - праві або молодші біти.

Ці послідовності вводять накопичувачі N 1 і N 2 перед початком першого циклу шифрування.

Перший цикл (j=1) процедури шифрування 64-бітового блоку даних описується такими формулами:

Тут i означає номер ітерації (i = 1, 2,..., 32).

Функція f називається функцією шифрування. Її аргументом є сума за модулем 2 32 числа A(i), отриманого на попередньому кроці ітерації, та числа X(j) ключа (розмірність кожного з цих чисел дорівнює 32 знакам).

Функція шифрування включає дві операції над отриманою 32-розрядною сумою. Перша операція називається підстановкою До. Блок підстановки До складається з 8 вузлів заміни К(1) ... До(8) з пам'яттю 64 біт кожен. 32-розрядний вектор, що надходить на блок підстановки, розбивається на 8 послідовно йдуть 4-х розрядних векторів, кожен з яких перетворюється в 4-х розрядний вектор відповідним вузлом заміни, що представляє собою таблицю з 16 цілих чисел в діапазоні 0...15.

Вхідний вектор визначає адресу рядка в таблиці, число якої є вихідним вектором. Потім 4-розрядні вихідні вектори послідовно об'єднуються в 32-розрядний вектор. Таблиці блоку підстановки містить ключові елементи, загальні для мережі ЕОМ і рідко змінювані.

Друга операція - циклічне зрушення вліво 32-розрядного вектора, отриманого в результаті підстановки К. 64-розрядний блок зашифрованих даних Т ш представляється у вигляді Т ш =A(32)B(32).

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

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

Режим гамування

Відкриті дані, розбиті на 64-розрядні блоки Т(i) (i=1, 2,..., m, де m визначається об'ємом даних, що шифруються), зашифровуються в режимі гамування шляхом порозрядного складання по модулю 2 з гамою шифру Г ш, яка виробляється блоками по 64 біт, тобто Г ш = (Г (1), Г (2), ..., Г (i), ..., Г (m)).

Рівняння зашифрування даних у режимі гамування може бути представлене у такому вигляді:

Ш(i) = A(Y(i-1) [+] C2, Z(i-1) (+) C1) (+) T(i) = Г(i) (+) T(i) .
Тут Ш(i) - 64-розрядний блок зашифрованого тексту,
A - функція шифрування в режимі простої заміни (аргументами цієї функції є два 32-розрядні числа),
С1 та С2 - константи, задані в ГОСТ 28147-89,
Y(i) та Z(i) - величини, які визначаються ітераційно у міру формування гами наступним чином:
(Y(0), Z(0)) = A(S), де S - 64-розрядна двійкова послідовність (синхропосилання);
(Y(i), Z(i)) = (Y(i-1) [+] C2, Z(i-1) (+) C1) для i = 1, 2,...,m.

Розшифрування даних можливе лише за наявності синхропосилання, яка не є секретним елементом шифру і може зберігатися в пам'яті ЕОМ або передаватися каналами зв'язку разом із зашированими даними.

Режим гамування із зворотним зв'язком

Режим гамуванняіз зворотним зв'язком дуже схожий на режим гамування. Як і режимі гамування відкриті дані, розбиті на 64-розрядні блоки Т(i) (i=1, 2,..., m , де m визначається об'ємом даних, що шифруються), зашифровуються шляхом порозрядного складання по модулю 2 з гамою шифру Г ш, яка виробляється блоками по 64 біт:

Г ш = (Г (1), Г (2), ..., Г (i), ..., Г (m)).

Число двійкових розрядів у блоці Т(m) може бути менше 64, при цьому невикористана частина шифрування гами шифру з блоку Г(m) відкидається.

Рівняння зашифрування даних у режимі гамування зі зворотним зв'язком може бути представлене в наступному вигляді:

Процес вироблення імітівстакиоднаковий для будь-якого з режимів шифрування даних.

Імітівставка - це блок з р біт (імітівставка Ір), який виробляється або перед шифруванням всього повідомлення, або паралельно з шифруванням по блоках. Перші блоки відкритих даних, які беруть участь у виробленні імітівставки, можуть містити службову інформацію (наприклад, адресну частину, час, синхропосилання) і не зашифровуватися. Значення параметра р (кількість двійкових розрядів в імітовставці) визначається криптографічними вимогами з урахуванням того, що ймовірність нав'язування хибних перешкод дорівнює 1/2^р.

Для отримання імітівставки відкриті дані подаються у вигляді 64-розрядних блоків Т(i) (i = 1, 2,..., m , де m визначається обсягом даних, що шифруються). Перший блок відкритих даних Т(1) піддається перетворенню, що відповідає першим 16 циклів алгоритму зашифрування в режимі простої заміни. Причому як ключ для вироблення імітівставки використовується ключ, яким шифруються дані.

Отримане після 16 циклів роботи 64-розрядне число підсумовується модулем 2 з другим блоком відкритих даних Т(2). Результат підсумовування знову перетворюється, що відповідає першим 16 циклам алгоритму зашифрування в режимі простої заміни. Отримане 64-розрядне число підсумовується модулем 2 з третім блоком відкритих даних Т(3) і т.д. Останній блок Т(m) при необхідності доповнений до повного 64-розрядного блоку нулями, підсумовується по модулю 2 з результатом роботи на кроці m-1, після чого зашифровується в режимі простої заміни перших 16 циклів роботи алгоритму. З отриманого 64-розрядного числа вибирається відрізок Ір довжиною рбіт.

Імітовставка Ір передається каналом зв'язку чи пам'ять ЕОМ після зашифрованих даних. Зашифровані дані, що надійшли, розшифровуються, і з отриманих блоків відкритих даних T(i) виробляється імітівставка Ір", яка потім порівнюється з імітівставкою Ір, отриманої з каналу зв'язку або з пам'яті ЕОМ. У разі розбіжності імітівставок всі розшифровані дані вважають помилковими.

На відміну від американського DES у вітчизняному стандарті застосовується довший ключ - 256 біт. Крім того, російський стандарт пропонує використовувати 32 раунди шифрування, тоді як DES – лише 16.

Таким чином, основні параметри алгоритму криптографічного перетворення даних ГОСТ 28147-89 такі: розмір блоку становить 64 біти, розмір ключа - 256 біт, кількість раундів - 32.

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

В алгоритмі шифрування використовуються такі операції:

• додавання слів за модулем 2 32;
• циклічний зсув слова вліво на вказане число біт;
• побітове додавання за модулем 2;
• заміна за таблицею.

На різних кроках алгоритмів ГОСТу дані, якими вони оперують, інтерпретуються та використовуються по-різному. У деяких випадках елементи даних обробляються як масиви незалежних бітів, в інших випадках – як ціле число без знака, у третіх – як складний елемент, що має структуру, що складається з декількох більш простих елементів.

Структура раунду ГОСТ 28147-89

Структура одного раунду ГОСТ 28147-89 наведено на рис. 5.1.

Блок даних, що шифрується, розбивається на дві частини, які потім обробляються як окремі 32-бітові цілі числа без знака. Спочатку права половина блоку та підключ раунду складаються за модулем 2 32 . Потім проводиться поблочна підстановка. 32-бітове значення отримане на попередньому кроці (позначимо його S ), інтерпретується як масив з восьми 4-бітових блоків коду: S=(S 0 ,S 1 ,S 2 ,S 3 ,S 4 ,S 5 ,S 6 ,S 7). Далі значення кожного з восьми блоків замінюється на нове, яке вибирається по таблиці замін наступним чином: значення блоку S i замінюється на S i -тий по порядку елемент (нумерація з нуля) i-го вузла замін (тобто i-того рядка таблиці замін, нумерація також із нуля). Іншими словами, як заміна для значення блоку вибирається елемент з номером рядка, рівним номеру блоку, що замінюється, і номером стовпця, рівним значенню блоку, що замінюється як 4-бітового цілого неотрицательного числа. У кожному рядку таблиці замін записано числа від 0 до 15 у довільному порядку без повторень. Значення елементів таблиці замін взяті від 0 до 15, так як у чотирьох бітах, які піддаються підстановці, може бути записано ціле число без знака в діапазоні від 0 до 15. Наприклад, перший рядок S-блоку може містити такі значення: 5, 8, 1, 13, 10, 3, 4, 2, 14, 15, 12, 7, 6, 0, 9, 11 . У цьому випадку значення блоку S 0 (чотири молодших біта 32-розрядного числа S) заміниться на число, що стоїть на позиції, номер якої дорівнює значенню блоку, що замінюється. Якщо S 0 = 0 , воно заміниться на 5 , якщо S 0 = 1 , воно заміниться на 8 тощо.

Мал. 5.1.

Після виконання підстановки всі 4-бітові блоки знову об'єднуються в єдине 32-бітове слово, яке потім циклічно зсувається на 11 бітів вліво. Нарешті, за допомогою побітової операції "сума за модулем 2"результат поєднується з лівою половиною, внаслідок чого виходить нова права половина R i . Нова ліва частина L i береться рівною молодшій частині блоку, що перетворюється: L i = R i-1 .

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

Процедури шифрування та розшифрування

ГОСТ 28147-89 є блоковим шифром, тому перетворення данихздійснюється блоками в так званих базових циклах. Базові цикли полягають у багаторазовому виконанні блоку даних основного раунду, розглянутого нами раніше, з використанням різних елементів ключа і відрізняються один від одного порядком використання ключових елементів. У кожному раунді використовується одна з восьми можливих 32-розрядних з'єднань.

Розглянемо процес створення підключів раундів. У ГОСТ ця процедура дуже проста, особливо в порівнянні з DES. 256-бітний ключ K розбивається на вісім 32-бітових підключів, що позначаються K 0 , K 1 , K 2 ,K 3 , K 4 , K 5 , K 6 , K 7 . Алгоритм включає 32 раунди, тому кожен підключ при шифруванні використовується в чотирьох раундах у послідовності, представленій на таблиці 5.1.

Процес розшифрування проводиться у тому алгоритму, як і шифрування . Єдина відмінність полягає в порядку використання підключів K i. При розшифруванні підключи повинні бути використані у зворотному порядку, а саме, як зазначено на

Короткий опис шифру

ГОСТ 28147-89 - радянський та російський стандарт симетричного шифрування, введений у 1990 році, також є стандартом СНД. Повна назва – «ГОСТ 28147-89 Системи обробки інформації. Захист криптографічний. Алгоритм криптографічного перетворення». Блоковий шифроалгоритм. При використанні методу шифрування з гамуванням може виконувати функції потокового шифроалгоритму.

ГОСТ 28147-89 - блоковий шифр з 256-бітним ключем та 32 циклами перетворення, що оперує 64-бітними блоками. Основа алгоритму шифру – Мережа Фейстеля. Базовим режимом шифрування за ГОСТ 28147-89 є режим простої заміни (визначено також складніші режими гамування, гамування зі зворотним зв'язком та режим імітівставки).

Принцип роботи алгоритму

Алгоритм принципово не відрізняється від DES. У ньому також відбуваються цикли шифрування (їх 32) за схемою Фейстеля (Рис. 2.9).

Мал. 2.9. Раунди шифрування алгоритму ГОСТ 28147-89.

Для генерації підключів вихідний 256-бітний ключ розбивається на вісім 32-бітових блоків: k 1 … k 8 . Ключі k 9 … k 24 є циклічним повторенням ключів k 1 … k 8 (нумеруються від молодших біт до старших). Ключі k 25 … k 32 є ключами k 1 … k 8 , що у зворотному порядку.

Після виконання всіх 32 раундів алгоритму, блоки A 33 і B 33 склеюються (слід звернути увагу на те, що старшим бітом стає A 33 а молодшим - B 33) - результат є результат роботи алгоритму.

Функція f(A i ,K i) обчислюється наступним чином: A i і K i складаються за модулем 2 32 потім результат розбивається на вісім 4-бітових підпослідовностей, кожна з яких надходить на вхід свого вузла таблиці замін(у порядку зростання старшинства бітів), званого нижче S-блоком. Загальна кількість S-блоків ГОСТу – вісім, тобто стільки ж, скільки і підпослідовностей. Кожен S-блокявляє собою перестановку чисел від 0 до 15. Перша 4-бітна підпослідовність потрапляє на вхід першого S-блоку, друга - на вхід другого і т.д. ліворуч (до старших розрядів) на 11 бітів. Усі вісім S-блоків можуть бути різними. Фактично вони можуть бути додатковим ключовим матеріалом, але частіше є параметром схеми, загальним для певної групи користувачів. У тексті стандарту вказується, що постачання заповнення вузлів заміни (S-блоків) виробляється у порядку, тобто. розробником алгоритму. Спільнота російських розробників СКЗІ погодила вузли заміни, що використовуються в Інтернет.

Розшифрування виконується як і, як і зашифрування, але інвертується порядок підключень k i .

Режими роботи алгоритму ГОСТ 28147-89

Алгоритм ГОСТ 28147-89 має чотири режими роботи.

1. Режимпростий заміниприймає на вхід дані, розмір яких кратний 64-м бітам. Результатом шифрування є вхідний текст, перетворений блоками по 64 біта у разі зашифрування циклом "32-З", а у разі розшифрування - циклом "32-Р".

2. Режимгамуванняприймає на вхід дані будь-якого розміру, а також додатковий 64-бітовий параметр - синхропосилку. У ході роботи синхропосилання перетворюється в циклі «32-З», результат ділиться на дві частини. Перша частина складається за модулем 2 32 з постійним значенням 1010101 16 . Якщо друга частина дорівнює 232-1, то її значення не змінюється, інакше вона складається за модулем 232-1 з постійним значенням 1010104 16 . Отримане об'єднанням обох перетворених частин значення, зване гамою шифру, надходить цикл «32-З», його результат порязрядно складається за модулем 2 з 64-розрядним блоком вхідних даних. Якщо останній менше 64 розрядів, то зайві розряди отриманого значення відкидаються. Отримане значення подається на вихід. Якщо ще є вхідні дані, то дія повторюється: складений з 32-розрядних частин блок перетворюється частинами і так далі.

3. Режимгамування зі зворотним зв'язкомтакож приймає на вхід дані будь-якого розміру та синхропосилання. Блок вхідних даних порозрядно складається за модулем 2 з результатом перетворення в циклі «32-З» синхропосилання. Отримане значення подається на вихід. Значення синхропосилання замінюється у разі зашифрування вихідним блоком, а у разі розшифрування - вхідним, тобто зашифрованим. Якщо останній блок вхідних даних менше 64 розрядів, зайві розряди гами (виходу циклу «32-З») відкидаються. Якщо є вхідні дані, то дія повторюється: з результату зашифрування заміненого значення утворюється гамма шифру тощо.

4. Режим виробіткуімітівставкиприймає на вхід дані, розмір яких не менше двох повних 64-розрядних блоків, а повертає 64-розрядний блок даних, званий імітівставкою. Тимчасове 64-бітове значення встановлюється в 0, далі, поки є вхідні дані, воно складається по модулю 2 з результатом виконання циклу «16-З», на вхід якого подається блок вхідних даних. Після закінчення вхідних даних тимчасове значення повертається як наслідок.

Криптоаналіз шифру

У шифрі ГОСТ 28147-89 використовується 256-бітовий ключ і обсяг ключового простору становить 2256 . На жодному з існуючих в даний час комп'ютері загального застосування не можна підібрати ключ за час, менший за багато сотень років. Російський стандарт ГОСТ 28147-89 проектувався з великим запасом і за стійкістю на багато порядків перевершує американський стандарт DES з його реальним розміром ключа 56 біт і обсягом ключового простору всього 2 56 .

Існують атаки і на повнораундовий ГОСТ 28147-89 без будь-яких модифікацій. Одна з перших відкритих робіт, в яких було проведено аналіз алгоритму, використовує слабкість процедури розширення ключа ряду відомих алгоритмів шифрування. Зокрема, повнораундовий алгоритм ДЕРЖСТАНДАРТ 28147-89 може бути розкритий за допомогою диференціального криптоаналізу на зв'язаних ключах, але тільки у разі використання слабких таблиць замін. 24-раундовий варіант алгоритму (у якому відсутні перші 8 раундів) розкривається аналогічним чином при будь-яких таблицях замін, однак сильні таблиці замін роблять таку атаку абсолютно непрактичною.

Вітчизняні вчені О.Г. Ростовцев та Є.Б. Маховенко в 2001 р. запропонували принципово новий метод криптоаналізу шляхом формування цільової функції від відомого відкритого тексту, відповідного йому шифртексту та шуканого значення ключа та знаходження її екстремуму, що відповідає справжньому значенню ключа. Вони ж знайшли великий клас слабких ключів алгоритму ГОСТ 28147-89, які дозволяють розкрити алгоритм за допомогою всього 4-х вибраних відкритих текстів і відповідних шифротекстів з досить низькою складністю.

У 2004 році група фахівців із Кореї запропонувала атаку, за допомогою якої, використовуючи диференціальний криптоаналіз на зв'язаних ключах, можна отримати з ймовірністю 91,7% 12 біт секретного ключа. Для атаки потрібно 2 35 вибраних відкритих текстів та 2 36 операцій шифрування. Як видно, дана атака практично марна для реального розтину алгоритму.

Таблиця замін є довготривалим ключовим елементом, тобто діє протягом більш тривалого терміну, ніж окремий ключ. Передбачається, що вона є спільною всім вузлів шифрування у межах однієї системи криптографічного захисту. Від якості таблиці залежить якість шифру. При "сильній" таблиці замін стійкість шифру не опускається нижче деякої допустимої межі навіть у разі її розголошення. І навпаки, використання "слабкої" таблиці може зменшити стійкість шифру до неприпустимо низької межі. Ніякої інформації з якості таблиці замін у відкритій пресі Росії не публікувалося, проте існування " слабких " таблиць викликає сумніви - прикладом може бути " тривіальна " таблиця замін, якою кожне значення замінюється нею самого. У ряді робіт помилково робиться висновок про те, що секретні таблиці замін алгоритму ГОСТ 28147-89 можуть бути частиною ключа і збільшувати його ефективну довжину (що несуттєво, оскільки алгоритм має дуже великий 256-бітний ключ).

Алгоритм, який визначається ГОСТ 28147-89, має довжину ключа шифрування 256 біт. Він шифрує інформацію блоками по 64 біт (такі алгоритми називаються блоковими), які потім розбиваються на два субблоки по 32 біти (N1 і N2) (рисунок 1). Субблок N1 обробляється певним чином, після чого його значення складається зі значенням субблока N2 (складання виконується за модулем 2, тобто застосовується логічна операція XOR - «виключає або»), а потім субблоки змінюються місцями. Дане перетворення виконується кілька разів («раундів»): 16 чи 32 залежно від режиму роботи алгоритму. У кожному раунді виконуються дві операції.

Малюнок 1. Схема алгоритму ГОСТ 28147-89.

Перша – накладення ключа. Вміст субблоку N1 складається за модулем 2 з 32-біт частиною ключа Kx. Повний ключ шифрування представляється як конкатенації 32-біт подключей: K0, K1, K2, K3, K4, K5, K6, K7. У процесі шифрування використовується один із цих підключів - залежно від номера раунду та режиму роботи алгоритму.

Друга операція – таблична заміна. Після накладання ключа субблок N1 розбивається на 8 частин по 4 біти, значення кожної з яких замінюється відповідно до таблиці заміни для цієї частини субблоку. Потім виконується побітовий циклічний зсув субблоку вліво на 11 біт.

Табличні заміни (Substitution box - S-box) часто використовуються у сучасних алгоритмах шифрування, тому варто пояснити, як організується така операція. У таблицю записуються вихідні значення блоків. Блок даних певної розмірності (у разі - 4-бит) має своє числове уявлення, яке визначає номер вихідного значення. Наприклад, якщо S-box має вигляд 4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1 і на вхід прийшов 4-біт блок «0100» (значення 4), то, згідно з таблицею, вихідне значення дорівнюватиме 15, тобто «1111» (0 а 4, 1 а 11, 2 а 2 ...).

Алгоритм, що визначається ГОСТ 28147-89, передбачає чотири режими роботи: простий заміни, гамування, гамування зі зворотним зв'язком та генерації імітоприставок. Вони використовують одне й те описане вище шифруюче перетворення, але, оскільки призначення режимів по-різному, здійснюється це перетворення у кожному їх по-різному.

У режимі простої заміни для зашифрування кожного 64-біт блоку інформації виконуються 32 описані вище раунди. При цьому 32-біт підключи використовуються в наступній послідовності:

K0, K1, K2, K3, K4, K5, K6, K7, K0, K1 і т.д. - у раундах з 1-го по 24-й;

K7, K6, K5, K4, K3, K2, K1, K0 - у раундах з 25-го до 32-го.

Розшифрування в даному режимі проводиться так само, але з дещо іншою послідовністю застосування підключень:

K0, K1, K2, K3, K4, K5, K6, K7 – у раундах з 1-го по 8-й;

K7, K6, K5, K4, K3, K2, K1, K0, K7, K6 тощо - у раундах з 9-го по 32-й.

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

У режимі гамування кожен блок відкритого тексту побітно складається по модулю 2 блоком гами шифру розміром 64 біт. Гамма шифру - це спеціальна послідовність, яка у результаті певних операцій із регістрами N1 і N2.

• 1. У регістри N1 і N2 записується їхнє початкове заповнення - 64-біт величина, звана синхропосилкою.
• 2. Виконується зашифрування вмісту регістрів N1 і N2 (в даному випадку - синхропосилання) в режимі простої заміни.
• 3. Вміст регістру N1 складається за модулем (232 - 1) з константою C1 = 224 + 216 + 28 + 24, а результат додавання записується в регістр N1.
• 4. Вміст регістру N2 складається за модулем 232 з константою C2 = 224 + 216 + 28 + 1, а результат додавання записується в регістр N2.
• 5. Вміст регістрів N1 і N2 подається на вихід як 64-біт блоку гами шифру (в даному випадку N1 і N2 утворюють перший блок гами).

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

Для розшифрування гамма виробляється аналогічним чином, а потім до біт зашифрованого тексту та гами знову застосовується операція XOR. Оскільки ця операція оборотна, у разі правильно виробленої гами виходить вихідний текст (таблиця 1).

Таблиця 1.Зашифрування та розшифрування в режимі гамування

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

У більшості реалізацій алгоритму ГОСТ 28147-89 синхропосилання не секретна, проте є системи, де синхропосилання - такий же секретний елемент, як і ключ шифрування. Для таких систем ефективна довжина ключа алгоритму (256 біт) збільшується ще на 64 біт секретної синхропосилання, яку також можна розглядати як ключовий елемент.

У режимі гамування із зворотним зв'язком для заповнення регістрів N1 і N2, починаючи з 2-го блоку, використовується не попередній блок гами, а результат зашифрування попереднього блоку відкритого тексту (рисунок 2). Перший блок у цьому режимі генерується повністю аналогічно попередньому.

Рисунок 2. Вироблення гами шифру як гамування зі зворотним зв'язком.

Розглядаючи режим генерації імітаторів, слід визначити поняття предмета генерації. Імітоприставка - це криптографічна контрольна сума, що обчислюється з використанням ключа шифрування та призначена для перевірки цілісності повідомлень. При генерації імітоприставки виконуються такі операції: перший 64-біт блок масиву інформації, для якого обчислюється імітоприставка, записується в регістри N1 і N2 і зашифровується в скороченому режимі простої заміни (виконуються перші 16 з 32 раундів). Отриманий результат підсумовується по модулю 2 з наступним блоком інформації зі збереженням результату N1 і N2.

Цикл повторюється до блоку інформації. В результаті цих перетворень 64-біт вміст регістрів N1 і N2 або його частина і називається імітоприставкою. Розмір імітоприставки вибирається, виходячи з необхідної достовірності повідомлень: при довжині імітоприставки r біт ймовірність, що зміна повідомлення залишиться непоміченим, дорівнює 2-r. Найчастіше використовується 32-біт імітоприставка, тобто половина вмісту регістрів. Цього достатньо, оскільки, як і будь-яка контрольна сума, імітоприставка призначена насамперед для захисту від випадкових спотворень інформації. Для захисту ж від навмисної модифікації даних застосовуються інші криптографічні методи - насамперед електронний цифровий підпис.

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

Алгоритм ДЕРЖСТАНДАРТ 28147-89 вважається дуже сильним алгоритмом - в даний час для його розкриття не запропоновано більш ефективних методів, ніж згаданий вище метод «грубою сили». Його висока стійкість досягається насамперед за рахунок великої довжини ключа – 256 біт. При використанні секретної синхропосилання ефективна довжина ключа збільшується до 320 біт, а засекречування таблиці замін додає додаткові біти. Крім того, криптостійкість залежить від кількості раундів перетворень, яких за ГОСТ 28147-89 має бути 32 (повний ефект розсіювання вхідних даних досягається після 8 раундів).

Достоїнствами ГОСТ 28147-89 є наявність захисту від нав'язування хибних даних (вироблення імітівставки) та однаковий цикл шифрування у всіх чотирьох алгоритмах ГОСТ.