IP ядрото на алгоритъма за криптиране GOST 28147 89 за компютри на платформата Intel x86

Известен изследовател, основателят на алгебричния криптоанализ, Никола Куртоа, твърди, че блоковият шифър GOST, който скоро трябваше да стане международен стандарт, всъщност е бил кракнат и очаква много публикации в бъдеще, които да развият идеите му за нестабилността на този алгоритъм.

Следват кратки извадки от тази работа, която може да се разглежда като алармистка атака в разгара на международната стандартизация (авторът е известен с подобни преувеличения по отношение на AES, но тогава работата му има голямо теоретично въздействие върху криптоанализа, но не е довела до практически атаки срещу самата AES). Но може би това е истинско предупреждение за началото на етапа на „въртящ се самолет“, който може да завърши с колапса на националния стандарт за криптиране, какъвто беше случаят с алгоритъма за хеширане SHA-1 и „де факто“ MD5 алгоритъм за хеширане.

GOST 28147-89 беше стандартизиран през 1989 г. и стана първият официален стандарт за защита на поверителна информация, но спецификацията на шифъра остана затворена. През 1994 г. стандартът е разсекретен, публикуван и преведен на английски език. По аналогия с AES (и за разлика от DES), GOST има право да защитава класифицирана информация без ограничения, в съответствие с начина, по който е посочено в руския стандарт. Че. GOST не е аналог на DES, а конкурент на 3-DES с три независими ключа или AES-256. Очевидно е, че GOST е доста сериозен шифър, който отговаря на военни критерии, създаден с мисъл за най-сериозните приложения. Най-малко два комплекта GOST S-кутии са идентифицирани въз основа на приложения, използвани от руски банки. Тези банки трябва да провеждат тайна комуникация със стотици клонове и да защитават милиарди долари от измамни кражби.

GOST е блоков шифър с проста структура на Feistel, с размер на блока от 64 бита, 256-битов ключ и 32 кръга. Всеки кръг съдържа добавяне на ключ по модул 2^32, набор от осем 4-битови S-кутия и просто 11-битово кръгово изместване. Характеристика на GOST е възможността за тайно съхраняване на S-блокове, което може да се разглежда като втори ключ, увеличавайки ефективния ключов материал до 610 бита. Един набор от S-блокове е публикуван през 1994 г. като част от спецификацията на хеш функцията GOST-R 34.11-94 и, както пише Шнайер, е използван от Централната банка Руска федерация. Той също беше включен в стандарта RFC4357 в частта "id-GostR3411-94-CryptoProParamSet". IN изходни кодовеимаше грешка в края на книгата на Schneier (в реда на S-кутиите). Най-точната референтна реализация с оригинален руски произход вече може да бъде намерена в библиотеката OpenSSL. Ако някъде се използват тайни S-кутии, те могат да бъдат извлечени от софтуерни реализации и от микросхеми, за които са публикувани съответните работи.

GOST е сериозен конкурент

В допълнение към много големия размер на ключа, GOST има значително по-ниски разходи за изпълнение в сравнение с AES и други подобни системи за криптиране. Всъщност струва много по-малко от AES, който изисква четири пъти повече хардуерни логически портове за значително по-ниско заявено ниво на сигурност.

Не е изненадващо, че GOST се превърна в интернет стандарт, по-специално той е включен в много крипто библиотеки като OpenSSL и Crypto++ и става все по-популярен извън страната си на произход. През 2010 г. GOST беше подложен на стандартизацията на ISO като световен стандарт за криптиране. Изключително малък брой алгоритми са успели да се превърнат в международни стандарти. ISO/IEC 18033-3:2010 описва следните алгоритми: четири 64-битови шифъра - TDEA, MISTY1, CAST-128, HIGHT - и три 128-битови шифъра - AES, Camellia, SEED. Предлага се GOST да бъде добавен към същия стандарт ISO/IEC 18033-3.

За първи път в историята на индустриалната стандартизация имаме работа с такъв конкурентен алгоритъм по отношение на оптималност между цена и ниво на сигурност. GOST има 20 години опити за криптоанализ зад гърба си и доскоро сигурността му от военен клас не беше поставена под въпрос.

Както авторът наскоро научи чрез частна кореспонденция, мнозинството от страните гласуваха против GOST на гласуването на ISO в Сингапур, но резултатите от това гласуване все пак ще бъдат разгледани на пленарната среща на ISO SC27, така че GOST все още е в процес на стандартизация в времето на публикуване на това произведение.

Експертни мнения по GOST

Никоя от наличната информация и литература относно GOST не дава причина да се смята, че шифърът може да е опасен. Обратно, голям размерключ и голям брой кръгове правят GOST, на пръв поглед, подходящ за десетилетия употреба.

Всеки запознат със закона на Мур разбира, че на теория 256-битовите ключове ще останат сигурни поне 200 години. GOST е широко проучен от водещи експерти по криптография, известни в областта на анализа на блоковия шифър, като Шнайер, Бирюков, Дункелман, Вагнер, много австралийски, японски и руски учени, експерти по криптография на ISO и всички изследователи изразиха, че изглежда така че може да бъде или трябва да бъде безопасно. Въпреки че е широко разбрано, че самата структура на GOST е изключително слаба, например в сравнение с DES, по-специално дифузията не е толкова добра, но това винаги се е дължало на факта, че това трябва да бъде компенсирано от голям брой кръгове (32), както и допълнителна нелинейност и дифузия, осигурени чрез добавяне по модул.

Бирюков и Вагнер пишат: „Големият брой патрони (32) и добре проучената конструкция на Feistel, съчетани с последователни пермутации на Шанън, осигуряват солидна основа за сигурността на GOST.“ В същия документ четем: "след значителна инвестиция на време и усилия, не е постигнат напредък в стандарта за криптоанализ в отворената литература." По този начин не е имало значителни атаки, които биха позволили декриптиране или възстановяване на ключа в реалистичен сценарий, при който GOST се използва при криптиране с много различни произволни ключове. За разлика от тях има много работи за атаки срещу слаби ключове в GOST, атаки със свързани ключове, атаки за възстановяване на тайни S-кутии. На Crypto 2008 беше представен хак на хеш функция, базирана на този шифър. При всички атаки нападателят има значително по-високо нивосвобода, отколкото обикновено му се позволява. В традиционните приложения за криптиране, използващи произволно избрани ключове, досега не са открити сериозни криптографски атаки срещу GOST, което през 2010 г. беше изразено с обобщената фраза: „въпреки значителните усилия на криптоаналитиците през последните 20 години, GOST все още не е разкрит кракнат“ (Аксел Пошман, Сан Линг и Хуаксионг Уанг: 256-битово стандартизирано крипто за 650 GE GOST Revisited, в CHES 2010, LNCS 6225, стр. 219-233, 2010).

Линеен и диференциален анализ GOST

В известната книга на Шнайер четем: „Срещу диференциалния и линейния криптоанализ GOST вероятно е по-стабилен от DES.“ Основната оценка на сигурността на GOST е дадена през 2000 г. от Gabidulin и др.. Резултатите им са много впечатляващи: с предвиденото ниво на сигурност от 2^256, пет кръга са достатъчни, за да защитят GOST от линеен криптоанализ. Освен това, дори при замяна на S-блокове с идентични и единствената нелинейна операция на шифъра - добавяне по модул 2^32 - шифърът все още е устойчив на линеен криптоанализ след 6 кръга от 32. GOST диференциалният криптоанализ изглежда сравнително по-лесен и привлича повече внимание. За нивото на сигурност 2^128 изследователите (Виталий В. Шорин, Вадим В. Железняков и Ернст М. Габидулин: Линеен и диференциален криптоанализ на руския GOST, препринт, представен на Elsevier Preprint, 4 април 2001 г.) приемат достатъчна устойчивост на ниво от 7 кръга. Според тях хакването на GOST в повече от пет кръга е „изключително трудно“. Нещо повече, двама японски изследователи показаха, че класическата диференциална атака напред с една диференциална характеристика има изключително ниска вероятност да оцелее през голям брой рундове. Въз основа на факта на изучаване на доста „добра“ итеративна диференциална характеристика за ограничен брой рундове (което само по себе си има вероятност да премине не по-добре от 2-11,4 на рунд), стойностите на набора от подходящи ключове са по-малко от половината. За GOST с пълен кръг такава атака с една характеристика ще работи само с незначителна част от ключовете от порядъка на 2-62 (и дори в тази малка част ще има вероятност да премине не повече от 2- 360).

По-сложните атаки включват множество диференциали, следващи специфични модели, като например използване на отделни S-кутии, които имат нулеви диференциали, докато други битове имат ненулеви. Говорим за дискриминационни атаки въз основа на лошите дифузионни свойства на GOST. Най-добрата от тези атаки работи срещу 17 кръга на GOST, зависи от ключа и има изключително слаб дискриминатор от произволни данни на изхода, така че по някакъв начин да може да се използва за получаване на информация за ключа.

Плъзгащи и отразяващи атаки

Според Бирюков и Вагнер структурата на GOST, която включва обръщане на реда на подключовете във финалните кръгове, го прави устойчив на плъзгащи се атаки (известни още като "слайд атаки"). Въпреки това, поради наличието на голямо количество самоподобие в шифъра, той позволява атаки с инверсия на ключове върху комбинации от фиксирани точки и свойства на „отражение“ (известни още като „отражателни атаки“) за определени слаби ключове. Сложността на тази атака е 2^192 и 2^32 съвпадащи обикновени текстове.

Последни резултати

Новите атаки също използват отражение и всъщност разбиха GOST, който беше представен на конференцията FSE 2011. Тези атаки също бяха открити независимо от автора на тази работа. Атаката изисква 2^132 байта памет, което всъщност е по-лошо от по-бавните атаки с по-ниски изисквания към паметта.

Много нови атаки, базирани на самоподобие, работят срещу всички GOST ключове и ви позволяват да разбиете пълен GOST с 256-битов ключ, а не само за слаби ключове, както беше преди. Всички тези атаки изискват значително по-малко памет и са значително по-бързи.

Тези нови атаки могат да се разглеждат като примери за нова обща парадигма за криптоанализа на блокови шифри, наречена "намаляване на алгебричната сложност", обобщаваща тези атаки до много специални случаи на атаки с известни фиксирани точки, пропуски, инволюции и цикли. Важно е, че сред семейството на всички тези атаки има такива, които позволяват GOST криптоанализ без никакви отражения и без никакви симетрични точки, които се появяват по време на изчисленията. Един пример е проста хакерска атака на GOST без отражение в тази работа.

Алгебричен криптоанализ и атаки с ниска сложност срещу шифри с намален кръг

Алгебрични атаки срещу блокови и поточни шифри могат да бъдат представени като проблем за решаване на голяма система от булеви алгебрични уравнения, която следва геометрията и структурата на патентована криптографска схема. Самата идея се връща към Шанън. На практика той е въведен за DES (въведен за първи път от автора на тази работа) като формален метод за кодиране и може да разбие 6 кръга само на един познат обикновен текст. Манипулирането с уравнения се извършва на базата на XL алгоритми, бази на Gröbner, метода ElimLin и SAT решаващи програми.

На практика алгебричните атаки са били прилагани срещу много малък брой кръгове от блокови шифри, но вече са довели до разбиването на поточни шифри, а също така е имало успехи при разбиването на ултра-леки шифри за микрохардуер. Поради трудностите в паметта и оценките на изчислителните разходи, те се комбинират с други атаки.

Как да хакна GOST?

Алгебричната атака на пълния GOST е представена по-подробно в разглежданата публикация. IN предишна работаАвторът вече е очертал 20 алгебрични атаки срещу GOST и очаква голям брой от тях в близко бъдеще. Атаката, предложена в тази работа, не е най-добрата от тях, но отваря прост (поне за разбиране от криптографите) път за последващи разработки за създаване на специфична методология за разбиване на GOST.

Практическият резултат все още е скромен: 2^64 известни обикновени текстове и 2^64 памет за съхраняване на двойки обикновен текст/шифрован текст правят възможно кракването на GOST 2^8 по-бързо от обикновената груба сила. Но по отношение на криптоанализа това прави твърдението, че „GOST е хакнат“ напълно вярно.

заключения

GOST е предназначен да осигури военно ниво на безопасност за 200 години напред. Повечето от водещите експерти, изучавали GOST, се съгласиха, че „въпреки значителните криптоаналитични усилия в продължение на 20 години, GOST все още не е кракнат“. През 2010 г. GOST беше повишен до ISO 18033 като глобален стандарт за криптиране.

Основата на идеите за алгебричен криптоанализ възниква преди повече от 60 години. Но едва през последните 10 години бяха разработени ефективни софтуерни инструменти за (частично) решаване на различни NP-пълни проблеми. Редица шифри на потока са били разбити. Само един блоков шифър е разбит с този метод - самият слаб KeeLoq. В тази работа авторът разбива важен, действително използван GOST шифър. Той отбелязва, че това е първият път в историята, когато стандартизиран правителствен шифър е бил разбит чрез алгебричен криптоанализ.

Една проста атака „MITM с отражение“ срещу GOST вече беше представена на конференцията FSE 2011. В работата, обсъждана в тази статия, друга атака е представена само за да илюстрира факта колко атаки срещу GOST вече са се появили сега, много от които са по-бързи, а алгебричната атака изисква много по-малко памет и отваря практически неизчерпаемо пространство от възможности за противник, който атакува шифъра различни начини. Тази работа също така показва, че няма нужда да се използва свойството отражение за хакване.

Авторът заявява: очевидно е, че GOST има сериозни недостатъци и вече не осигурява нивото на устойчивост, изисквано от ISO. Много атаки срещу GOST са представени като част от потвърждението на парадигмата за намаляване на алгебричната сложност.

И накрая, изследователят специално отбелязва някои факти, които все още не са достъпни за читателя, но са известни на изследователя, които са важни по време на процеса на стандартизация по ISO. Тази атака не е просто „сертификационна“ атака срещу GOST, която е по-бърза от грубата сила. Всъщност стандартизирането на GOST сега би било изключително опасно и безотговорно. Това е така, защото някои от атаките са осъществими на практика. Някои GOST ключове дори могат да бъдат декриптирани на практика, независимо дали са слаби ключове или ключове от определени реални приложения на GOST. В предишна работа авторът предоставя подробно разглеждане на случаите на възможност практически атаки. Това, което също е важно е, че „това е първият път в историята, че сериозен, стандартизиран блоков шифър, предназначен да защитава военни тайни и предназначен да защитава правителствени тайни за правителства, големи банки и други организации, е бил разбит от математическа атака ."

Кратко описание на шифъра

GOST 28147-89 е съветски и руски стандарт за симетрично криптиране, въведен през 1990 г., също стандарт на CIS. Пълно име - „ГОСТ 28147-89 Системи за обработка на информация. Криптографска защита. Алгоритъм за криптографско преобразуване." Алгоритъм за блоково шифиране. Когато се използва методът на гама криптиране, той може да изпълнява функциите на алгоритъм за поточен шифър.

GOST 28147-89 е блоков шифър с 256-битов ключ и 32 цикъла на преобразуване, работещ върху 64-битови блокове. Основата на алгоритъма за шифиране е мрежата Feistel. Основният режим на криптиране съгласно GOST 28147-89 е прост режим на замяна (дефинират се и по-сложни режими: гама, гама с обратна връзкаи симулиран режим на вмъкване).

Как работи алгоритъмът

Алгоритъмът не е фундаментално различен от DES. Той също така съдържа цикли на криптиране (32 от тях) по схемата на Feistel (фиг. 2.9.).

Ориз. 2.9. Криптиращи кръгове на алгоритъма GOST 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 се събират по модул 2 32 , след което резултатът се разделя на осем 4-битови подпоследователности, всяка от които се въвежда в своя собствена възел на таблицата за заместване(във възходящ ред на приоритет на битове), наречен по-долу S-блок. Общият брой на GOST S-блоковете е осем, т.е. същият брой като подпоследователностите. Всеки S-блоке пермутация на числа от 0 до 15. Първата 4-битова подпоследователност отива на входа на първата S-кутия, втората - на входа на втората и т.н. Изходите на всичките осем S-кутии се комбинират в 32-битова дума, тогава цялата дума се измества циклично наляво (към най-значимите битове) с 11 бита. Всичките осем S-кутии могат да бъдат различни. Всъщност те могат да бъдат допълнителен ключов материал, но по-често те са параметър на схема, общ за определена група потребители. Текстът на стандарта показва, че доставката на резервни модули за пълнене (S-блокове) се извършва по предписания начин, т.е. разработчик на алгоритъм. Общността на руските разработчици на CIPF се споразумя за заместващите възли, използвани в Интернет.

Дешифрирането се извършва по същия начин като криптирането, но редът на подключовете k i е обърнат.

Режими на работа на алгоритъма GOST 28147-89

Алгоритъмът GOST 28147-89 има четири режима на работа.

1. Режимлесна подмянаприема като вход данни, чийто размер е кратен на 64 бита. Резултатът от криптирането е входният текст, преобразуван в блокове от 64 бита в случай на криптиране с цикъл „32-Z“, а в случай на декриптиране с цикъл „32-R“.

2. Режимхазартни игриприема данни от всякакъв размер като вход, както и допълнителен 64-битов параметър - съобщение за синхронизиране. По време на работа съобщението за синхронизиране се преобразува в цикъла „32-Z“, резултатът се разделя на две части. Първата част се добавя по модул 2 32 с постоянна стойност 1010101 16. Ако втората част е равна на 2 32 -1, тогава нейната стойност не се променя, в противен случай тя се добавя по модул 2 32 -1 с постоянна стойност 1010104 16. Стойността, получена чрез комбиниране на двете трансформирани части, наречена шифър гама, влиза в цикъла „32-3“, резултатът от него се добавя бит по бит модул 2 с 64-битовия блок от входни данни. Ако последното е по-малко от 64 бита, тогава допълнителните битове от получената стойност се отхвърлят. Получената стойност се изпраща на изхода. Ако все още има входящи данни, действието се повтаря: блокът, съставен от 32-битови части, се преобразува в части и т.н.

3. Режимигри с обратна връзкасъщо така приема данни от всякакъв размер и съобщение за синхронизация като вход. Блокът от входни данни се добавя бит по бит модул 2 с резултата от трансформацията в цикъла “32-3” на съобщението за синхронизация. Получената стойност се изпраща на изхода. Стойността на синхронизиращото съобщение се заменя при криптиране от изходния блок, а при декриптиране - от входния блок, т.е. криптирания. Ако последният блок от входящи данни е по-малък от 64 бита, тогава допълнителните битове на гама (изход от цикъла "32-3") се отхвърлят. Ако все още има входящи данни, тогава действието се повтаря: от резултата от криптирането на заменената стойност се формира шифър гама и т.н.

4. Производствен режимимитации на вложкиприема като входни данни, които са с размер на поне два пълни 64-битови блока, и връща 64-битов блок от данни, наречен симулирано вмъкване. Временната 64-битова стойност е зададена на 0, след което, докато има входни данни, те се добавят бит по бит модул 2 с резултата от цикъла „16-3“, чийто вход е блок от вход данни. След края на входните данни, временната стойност се връща като резултат.

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

Шифърът GOST 28147-89 използва 256-битов ключ и обемът на ключовото пространство е 2256. На нито един от съществуващите в момента компютри с общо предназначение не може да бъде намерен ключ за по-малко от много стотици години. Руският стандарт GOST 28147-89 е проектиран с голям резерв и е много порядъци по-силен от американския стандарт DES с действителния си размер на ключа от 56 бита и обем на ключовото пространство от само 2 56 .

Има и атаки срещу пълния GOST 28147-89 без никакви модификации. Една от първите обществени работи, които анализират алгоритъма, използва слабостите в процедурата за разширяване на ключа на редица добре известни алгоритми за криптиране. По-специално, пълният алгоритъм на GOST 28147-89 може да бъде разбит с помощта на диференциален криптоанализ на свързани ключове, но само ако се използват слаби заместващи таблици. 24-кръговата версия на алгоритъма (в която липсват първите 8 кръга) се отваря по подобен начин с всички заместващи таблици, но силните заместващи таблици правят такава атака напълно непрактична.

Домашни учени A.G. Ростовцев и Е.Б. Маховенко през 2001 г. предложи фундаментално нов метод за криптоанализ чрез формиране на целева функция от известен открит текст, съответния шифрован текст и желаната стойност на ключа и намиране на нейния екстремум, съответстващ на истинската стойност на ключа. Те също така откриха голям клас слаби ключове на алгоритъма GOST 28147-89, които правят възможно отварянето на алгоритъма, като се използват само 4 избрани открити текста и съответните шифровани текстове с доста ниска сложност.

През 2004 г. група специалисти от Корея предложи атака, с която, използвайки диференциален криптоанализ на свързани ключове, е възможно да се получат 12 бита с вероятност от 91,7% таен ключ. Атаката изисква 2 35 избрани открити текстове и 2 36 операции за криптиране. Както можете да видите, тази атака е практически безполезна за действително нарушаване на алгоритъма.

Таблицата за замяна е дългосрочен ключов елемент, тоест тя е валидна за много по-дълъг период от един ключ. Предполага се, че е общ за всички криптиращи възли в една и съща система за криптографска защита. Качеството на шифъра зависи от качеството на тази таблица. При „силна“ таблица за заместване силата на шифъра не пада под определена приемлива граница, дори ако е компрометирана. Обратно, използването на "слаба" таблица може да намали силата на шифъра до неприемливо ниска граница. В откритата преса на Русия не е публикувана информация за качеството на таблицата за замяна, но съществуването на „слаби“ таблици е извън съмнение - пример е „тривиална“ таблица за замяна, в която всяка стойност се заменя сама. Редица произведения погрешно заключават, че секретните таблици за заместване на алгоритъма GOST 28147-89 могат да бъдат част от ключа и да увеличат неговата ефективна дължина (което не е важно, тъй като алгоритъмът има много голям 256-битов ключ).

GOST 28147-89 предвижда следните режими на криптиране на данни: проста замяна, гама, гама с обратна връзка и един допълнителен режимразработване на имитационни вложки.

Във всеки от тези режими данните се обработват в блокове от 64 бита, на които е разделен криптираният масив, поради което GOST 28147-89 се отнася до блокови шифри. В гама режимите е възможно да се обработи непълен блок от данни с размер под 8 байта, което е от съществено значение при криптиране на масиви от данни с произволен размер, който може да не е кратен на 8 байта.

Лесен режим на смяна. Този режим на използване на блоков шифър е подобен на режима ECB, обсъден в Лекция 4. В този режим всеки блок от изходни данни се криптира независимо от други блокове, като се използва един и същ ключ за криптиране. Характеристика на този режим е, че идентични блокове от оригиналния текст се преобразуват в един и същ шифрован текст. Следователно GOST 28147-89 препоръчва използването на режим на проста подмяна само за криптиране на ключове.

Гама и гама режимите със затворен цикъл могат да се използват за криптиране на данни с произволен размер.

IN гама режимБитовете на изходния текст се добавят по модул 2 с гамата, която се генерира с помощта на алгоритъма за криптиране в съответствие с GOST 28147-89. Тоест, алгоритъмът за криптиране в съответствие с GOST 28147-89 в този режим се използва като генератори на 64-битови гама блокове. Когато шифровате всеки нов блок от данни, гамата, използвана в предишната стъпка, се криптира и използва като „нова“ гама. Тъй като първоначалният масив от данни, криптиран за получаване на най-първата гама, т.нар съобщение за синхронизиране– 64-битов първоначален блок от данни, който трябва да е еднакъв откъм страни за криптиране и декриптиране. Поради факта, че прилагането и премахването на гама се извършва с помощта на една и съща операция за добавяне по модул 2, алгоритмите за криптиране и декриптиране в гама режим са еднакви.

Тъй като всички гама елементи са различни за реални криптирани масиви, резултатът от криптирането дори на два идентични блока в един масив от данни ще бъде различен. В допълнение, въпреки че гама елементите се генерират на равни части от 64 бита, може да се използва част от такъв блок с размер, равен на размера на криптирания блок. Това е, което прави възможно криптирането на непълни блокове от данни.

Режим игри с обратна връзкае подобен на режима gamut и се различава от него само по начина, по който се генерират елементите на gamut. При игра с обратна връзка следващият 64-битов гама елемент се генерира в резултат на трансформация съгласно основния цикъл на алгоритъма GOST 28147-89 на предишния блок от криптирани данни. За шифроване на първия блок от масива от данни гама елементът се генерира в резултат на трансформацията, използвайки същия цикъл на синхронизация. Това постига блокова верига - всеки блок с шифрован текст в този режим зависи от съответния и всички предишни блокове с обикновен текст. Следователно този режим понякога се нарича игри с блокиращи блокове. Фактът, че блоковете са свързани, няма ефект върху силата на шифъра.

За решаване на проблема с откриването на изкривявания в криптиран масив от данни, GOST 28147-89 предоставя допълнителен режим на криптографска трансформация - генериране на имитативно вмъкване. Имитовстаке контролна комбинация, която зависи от отворени данни и информация от таен ключ. Целта на използването на имитативно вмъкване е да се открият всички случайни или умишлени промени в информационния масив. В режим на генериране на вмъкване на симулация входният текст се обработва на блокове, както следва:

където f е основният цикъл съгласно GOST 28147-89; X i – 64-битов блок от изходен текст; K – ключ.

Част от блока Y n, получен на изхода, се приема като симулирано вмъкване, обикновено неговите 32 най-малко значими бита.

По този начин атакуващият, без да притежава ключа за криптиране, не може да изчисли имитативната стойност за даден отворен масив от информация, както и да избере отворени данни за даден имитативен вход.

Разлики между алгоритмите за криптиране съгласно GOST 28147-89 и DES

Въпреки факта, че алгоритъмът, изложен в GOST 28147-89, е проектиран доста отдавна, той съдържа достатъчна граница на надеждност. Това се дължи главно на голямата дължина на ключа за криптиране.

Както е известно, разработчиците на съвременни криптосистеми се придържат към принципа, че секретността на криптираните съобщения трябва да се определя от тайната на ключа. Това означава, че дори ако самият алгоритъм за криптиране е известен на криптоаналитика, той все пак не би трябвало да може да дешифрира съобщението, ако не разполага с подходящия ключ. Всички класически блокови шифри, включително DES и GOST 28147-89, отговарят на този принцип и са проектирани по такъв начин, че няма начин да бъдат разбити повече ефективен начин, а не пълно търсене в цялото ключово пространство, т.е. над всички възможни ключови стойности. Ясно е, че силата на такива шифри се определя от размера на използвания в тях ключ.

Шифърът, внедрен в GOST 28147-89, използва 256-битов ключ, а обемът на ключовото пространство е 2256. Дори ако, както в „DES и AES криптиращи алгоритми“, приемем, че всички сили на компютърен комплекс с възможност за търсене на 10 12 (това е приблизително равно на 2 40) ключа за една секунда се използват за разбиване на шифъра, след това пълното търсене на всичките 2256 ключа ще отнеме 2216 секунди (това е над милиард години).

Към вече отбелязаните разлики между алгоритмите DES и GOST 28147 може да се добави и следното. Основният DES кръг използва неправилни пермутации на оригиналното съобщение, докато GOST 28147 използва 11-битово циклично ляво изместване. Последната операция е много по-удобна за софтуерна реализация. Пренареждането на DES обаче увеличава ефекта на лавината. В GOST 28147 промяната на един входен бит засяга един 4-битов блок, когато се замени в един кръг, който след това засяга два 4-битови блока в следващия кръг, три блока в следващия и т.н. GOST 28147 изисква 8 кръга, преди промяната на един входен бит да засегне всеки бит от резултата; DES се нуждае само от 5 рунда за това.

Трябва също да се отбележи, че за разлика от DES, в GOST 28147-89 заместващата таблица за извършване на операцията по заместване може да бъде произволно променена, т.е. заместващата таблица е допълнителен 512-битов ключ.

Ключови термини

ГОСТ 28147-89– Руски стандарт за блок симетричен алгоритъм за криптиране.

Кратко обобщение

В Русия е приет GOST 28147-89, препоръчан за използване за криптографска защитаданни. GOST 28147-89 е блоков шифър с частен ключ. Основните параметри на алгоритъма GOST 28147-89 са следните: размер на блока – 64 бита, размер на ключа – 256 бита, брой кръгове – 32. Алгоритъмът е класическа мрежа на Feishtel.

Комплект за упражнения

Въпроси за самопроверка

1. За какви цели може да се използва алгоритъмът за преобразуване на криптографски данни съгласно GOST 28147-89?
2. Избройте основните параметри на алгоритъма за симетрично криптиране съгласно GOST 28147-89.
3. Какви операции се използват в алгоритъма за блоково криптиране съгласно GOST 28147-89?
4. Какви са основните разлики между алгоритъма за криптиране съгласно GOST 28147-89 и алгоритъма DES?
5. Каква информация, в допълнение към секретния ключ, предоставя този стандарт алгоритми GOST 28147Необходим ли е -89 за дешифриране на съобщението?
6. В какви режими данните могат да бъдат криптирани с помощта на алгоритъма за криптографска трансформация в съответствие с GOST 28147-89?
7. Какво е имитация на вложка? За какви цели може да се използва имитираща вложка?

Упражнения за самопроверка

1. Нека всеки три бита от входното съобщение да бъдат заменени съгласно следната таблица за заместване:

За разлика от американския DES, вътрешният стандарт използва по-дълъг ключ - 256 бита. В допълнение, руският стандарт предлага използването на 32 кръга криптиране, докато DES изисква само 16.

По този начин основните параметри на алгоритъма за криптографска трансформация на данни GOST 28147-89 са следните: размерът на блока е 64 бита, размерът на ключа е 256 бита, броят на кръговете е 32.

Алгоритъмът е класическа мрежа на Feishtel. Криптираният блок от данни е разделен на две еднакви части, дясно R и ляво L. Дясната част се добавя към кръглия подключ и с помощта на някакъв алгоритъм криптира лявата част. Преди следващия кръг лявата и дясната част се разменят. Тази структура позволява един и същи алгоритъм да се използва както за криптиране, така и за декриптиране на блок.

Алгоритъмът за криптиране използва следните операции:

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

На различни стъпки на GOST алгоритмите, данните, с които работят, се интерпретират и използват по различни начини. В някои случаи елементите от данни се третират като масиви от независими битове, в други случаи като цяло число без знак, в трети като структуриран сложен елемент, състоящ се от няколко по-прости елемента.

Кръгла структура GOST 28147-89

Структурата на един кръг от GOST 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.

Получената стойност на конвертирания блок се счита за резултат от един кръг на алгоритъма за криптиране.

Процедури за криптиране и декриптиране

Следователно GOST 28147-89 е блоков шифър преобразуване на данниизвършва се на блокове в т.нар основни цикли. Основните цикли се състоят от повтарящо се изпълнение на основния кръг, който обсъдихме по-рано за блок от данни, като се използват различни ключови елементи и се различават един от друг по реда, в който се използват ключовите елементи. Всеки кръг използва един от осем възможни 32-битови подключа.

Нека да разгледаме процеса на създаване на кръгли подключове. В GOST тази процедура е много проста, особено в сравнение с DES. 256-битовият ключ K е разделен на осем 32-битови подключа, означени с K0, K1, K2, K3, K4, K5, K6, K7. Алгоритъмът включва 32 кръга, така че всеки подключ по време на криптиране се използва в четири кръга в последователността, представена в таблица 5.1.

Процесът на декриптиране се извършва по същия алгоритъм като криптирането. Единствената разлика е редът, в който се използват подключовете K i. При дешифриране подключовете трябва да се използват в обратен ред, а именно както е посочено в

Алгоритъм GOST 28147-89

GOST 28147-89 е съветски и руски стандарт за симетрично криптиране, въведен през 1990 г., също стандарт на CIS. Пълно име - „ГОСТ 28147-89 Системи за обработка на информация. Криптографска защита. Алгоритъм за криптографско преобразуване."

Ориз. 4.

Алгоритъм за блоково шифиране. Когато се използва методът на гама криптиране, той може да изпълнява функциите на алгоритъм за поточен шифър. GOST 28147-89 - блоков шифър с 256-битов ключ и 32 цикъла на преобразуване, работещ с 64-битови блокове. Основата на алгоритъма за шифиране е мрежата на Feistel. Съществуват четири режима на работа съгласно GOST 28147-89: проста замяна, игра, игра с обратна връзка и режим на генериране на симулация.

Предимствата на алгоритъма: безполезността на силовата атака, ефективността на внедряване и съответно високата производителност на съвременните компютри, наличието на защита срещу налагане на фалшиви данни (генериране на имитативно вмъкване) и един и същ цикъл на криптиране във всички четири GOST алгоритъма, по-голям ключ в сравнение с алгоритъма DESX.

Недостатъци на алгоритъма: Основните проблеми на GOST са свързани с непълнотата на стандарта по отношение на генерирането на ключове и таблици за заместване. Смята се, че GOST има „слаби“ ключове и таблици за подмяна, но стандартът не описва критериите за избор и елиминиране на „слаби“. Също така стандартът не определя алгоритъм за генериране на таблица за заместване (S-кутии). От една страна, това може да е допълнителна секретна информация (в допълнение към ключа), а от друга страна, това поражда редица проблеми: невъзможно е да се определи криптографската сила на алгоритъма, без да се знае предварително таблицата за заместване ; реализациите на алгоритъма от различни производители могат да използват различни заместващи таблици и може да са несъвместими една с друга; възможността за умишлено предоставяне на слаби резервни таблици от лицензиращите органи на Руската федерация.

Предимства на IDEA пред аналозите

При софтуерна реализация на Intel486SX е два пъти по-бърз от DES IDEA, което е значително увеличение на скоростта; дължината на ключа на IDEA е 128 бита, срещу 56 бита за DES, което е добро подобрение спрямо ключовете с груба сила. Вероятността за използване на слаби ключове е много малка и възлиза на 1/2 64 . IDEA е по-бърз от алгоритъма GOST 28147-89 (при софтуерна реализация на Intel486SX). Използването на IDEA в паралелни режими на криптиране на процесори Pentium III и Pentium MMX ви позволява да получите високи скорости. В сравнение с финалистите на AES, 4-way IDEA е само малко по-бавен от RC6 и Rijndael на Pentium II, но по-бърз от Twofish и MARS. На Pentium III 4-way IDEA е дори по-бърз от RC6 и Rijndael. Друго предимство е, че е добре проучен и устойчив на добре познати инструменти за криптоанализ.