Зависи ли сигурността на блоковите шифри от многократното комбиниране на операции за объркване и дифузия?
Сигурността на блоковите шифри е фундаментално вкоренена в итеративното приложение на операциите за объркване и дифузия. Тази концепция е формализирана за първи път от Клод Шанън в неговия основополагащ труд върху комуникационната теория на системите за секретност, където той формулира необходимостта както от объркване, така и от дифузия в криптографските системи, за да се предотвратят статистически и структурни атаки. Разбирането защо са необходими множество кръгове от тези операции и как те са взаимосвързани е от решаващо значение за оценяването на дизайна и сигурността на съвременните блокови шифри, като например стандарта за криптиране на данни (DES) и стандарта за усъвършенствано криптиране (AES).
Объркване и дифузия: Дефиниции и роли
Объркването се стреми да направи връзката между шифротекста и ключа възможно най-сложна. То постига това чрез маскиране на статистическата структура на открития текст, често чрез използването на нелинейни замествания (напр. S-кутии в DES и AES). Колкото по-нелинейно и сложно е това съпоставяне, толкова по-трудно става за атакуващия да изведе информация за ключа, дори при достъп до много двойки открит текст-шифротекст.
Дифузията, от друга страна, има за цел да разпредели влиянието на всеки бит от открития текст върху много битове от шифрования текст, така че промяна в един входен бит води до промени в много изходни битове. Това свойство гарантира, че статистическите свойства на открития текст се разсейват в шифрования текст, което прави невъзможно за нападателите да използват модели чрез честотен анализ или подобни техники. Дифузията обикновено се постига чрез линейни операции на смесване, като пермутация, побитови XOR операции или матрични умножения (както в операцията MixColumns на AES).
Структура на итеративните блокови шифри
Повечето блокови шифри са структурирани като итеративни шифри, което означава, че прилагат проста функция за кръгово шифроване многократно, за да постигнат високо ниво на сигурност. Функцията за кръгово шифроване обикновено комбинира както объркване (напр. чрез S-box приложения), така и дифузия (напр. чрез пермутация или стъпки на смесване). Обосновката за използването на множество кръгове е, че еднократното прилагане на объркване и дифузия е недостатъчно, за да прикрие всички структурни връзки между открит текст, шифрован текст и ключ. Всеки кръг постепенно увеличава сложността на тези връзки и едва след няколко кръга шифърът постига желаното ниво на сигурност срещу известни криптоаналитични атаки.
Например, като се има предвид AES шифърът, всеки кръг на криптиране се състои от следните ключови стъпки:
1. Подбайтове (объркване): Всеки байт в матрицата на състоянията се заменя с друг според фиксирана нелинейна S-кутия, въвеждайки нелинейност.
2. ShiftRows (Дифузия): Редовете на матрицата на състоянията се изместват циклично, премествайки байтовете в различни колони и улеснявайки смесването на стойности.
3. MixColumns (Дифузия): Колоните на състоянието се смесват чрез матрично умножение в крайно поле, като по този начин се разпределя допълнително влиянието на всеки входен байт.
4. AddRoundKey (Объркване): Матрицата на състоянията се комбинира с подключ, получен от главния ключ, въвеждайки зависимост между ключа във всеки рунд.
Ефективността на шифъра зависи не само от силата на всяка отделна операция, но и от броя пъти, в които тези операции се прилагат. Криптоаналитиците са демонстрирали, че намаляването на броя на рундовете в шифър като AES или DES може да го направи уязвим за атаки като диференциален и линеен криптоанализ. Например, докато пълният AES-128 използва 10 рунда, версиите само с 6 рунда са податливи на определени криптоаналитични техники.
Необходимост от множество рундове
За да изясним допълнително, помислете какво се случва, ако се приложи само един кръг на объркване и дифузия. Дори ако се използват силни S-кутии и смесителни слоеве, статистическите зависимости и модели могат да се запазят. Атакуващите биха могли да използват тези остатъчни модели, използвайки атаки с избран открит текст или известен открит текст. Множеството кръгове гарантират, че влиянието на всеки ключ и бит от открит текст е напълно разпределено в целия шифрован текст, което прави невъзможно провеждането на такива атаки.
Концепцията за „лавинния ефект“ е централна тук. Силният шифър гарантира, че малка промяна в открития текст (като например обръщане на един бит) води до промяна в приблизително половината битове на шифрования текст и това свойство се постига само след няколко кръга на объркване и дифузия. Итеративната структура на съвременните блокови шифри е специално проектирана да усили този ефект, което прави шифъра устойчив на атаки, които разчитат на проследяване на връзките вход-изход.
Примери: DES и AES
Историческият DES шифър илюстрира добре този принцип. DES използва 16 рунда в своята мрежова структура на Файстел, като всеки рунд се състои от разширяване, S-кутия заместване (объркване) и пермутация (дифузия). Обширният криптоанализ показва, че използването на по-малко от 16 рунда води до слабости; диференциалният криптоанализ е ефективен срещу версии с по-малко рундове. Разработчиците са избрали 16 рунда, за да осигурят марж на сигурност срещу напредъка в криптоанализа, подчертавайки важността на множеството итерации.
AES, проектиран десетилетия по-късно, прилага 10, 12 или 14 рунда в зависимост от размера на ключа (съответно 128, 192 или 256 бита). Всеки рунд включва комбинираните ефекти на объркване и дифузия чрез своите стъпки SubBytes, ShiftRows и MixColumns. Броят на рундовете е внимателно избран въз основа на криптоаналитичните открития, за да се балансират сигурността и производителността.
Режими на работа и тяхната връзка
Докато вътрешната сигурност на блоковите шифри се определя от многократно объркване и разпространение, режимът на работа (напр. ECB, CBC, CFB, OFB, CTR) определя как блоковите шифри се прилагат към данни, по-големи от един блок. Свойствата за сигурност на блоковия шифър в даден режим зависят фундаментално от устойчивостта на блоковия шифър на атаки, което от своя страна е функция на това колко добре се постигат объркване и разпространение в множество рундове. Ако основният блоков шифър е слаб (например с твърде малко рундове), никой режим на работа не може да компенсира този недостатък.
Криптоаналитични атаки и рундове
Няколко криптоаналитични атаки използват недостатъчното объркване и дифузия в блоковите шифри. Диференциалният криптоанализ, например, изучава как разликите в откритите текстове влияят върху получените разлики в шифрования текст. Ако шифърът не е разпръснал адекватно входните разлики, атакуващият може да предвиди как тези разлики се разпространяват и да използва това знание, за да възстанови ключа. По подобен начин, линейният криптоанализ търси линейни приближения между открития текст, шифрования текст и ключовите битове. Ефективността на тези атаки намалява с увеличаване на броя на рундовете, при условие че всеки рунд ефективно реализира объркване и дифузия.
За илюстрация, DES с 8 рунда (половината от стандартния брой) е податлив на диференциален криптоанализ, но с 16 рунда вероятността за разпространение на полезна диференциална следа през всички рундове става незначителна. Това показва, че итеративната структура, и по-специално броят на рундовете, е от основно значение за постигане на практическа сигурност.
Компромиси в дизайна
Проектантите на шифри трябва да балансират броя на рундовете спрямо изискванията за производителност. Повече рундове обикновено означават по-голяма сигурност, но също и по-големи изчислителни разходи. Броят на рундовете обикновено се избира, за да осигури марж на сигурност над най-известните атаки към момента на проектиране, с очакването, че бъдещите постижения в криптоанализата могат да подкопаят този марж. Този консервативен подход гарантира, че шифърът остава сигурен през очаквания си живот.
Математическа обосновка
От теоретична гледна точка, итеративните блокови шифри могат да се разглеждат през призмата на модела на „итериран продуктов шифър“. При определени предположения е показано, че композицията от множество слаби шифъри (всеки от които имплементира слабо объркване и/или дифузия) може да доведе до силен като цяло шифър, при условие че компонентите са достатъчно независими и броят на рундовете е голям. Това оправдава итеративния подход към объркването и дифузията в практическото проектиране на шифри.
Практически примери
Показателен пример е структурата на мрежата за заместване-пермутация (SPN), използвана от AES. В SPN, откритият текст е подложен на редуващи се слоеве на заместване (объркване) и пермутация (дифузия). След няколко кръга, всеки изходен бит зависи от всеки входен бит по силно нелинеен начин. Това свойство не се постига с един кръг; кумулативният ефект от множество кръгове гарантира, че всеки бит от шифротекста е сложна функция на всеки бит от открития текст и ключа, свойство, известно като пълна дифузия.
Мрежата на Файстел, използвана в DES, постига подобна сигурност чрез итеративно прилагане на кръгова функция, която комбинира заместване и пермутация, като изходът от всеки кръг се прехвърля в следващия. Сигурността на такива конструкции се увеличава експоненциално с броя на кръговете, ако приемем, че самата кръгова функция не е тривиално обратима или линейна.
Заключение: Зависимост на сигурността от итерацията
Силата на блоковите шифри е тясно свързана с многократното прилагане на операции за объркване и дифузия. Съвременните шифри са проектирани с достатъчен брой рундове, за да се гарантира, че всички остатъчни статистически връзки от открития текст или ключа са елиминирани и че всеки бит от шифрования текст е повлиян от всеки бит от открития текст и ключа. Този итеративен процес не е просто детайл от имплементацията, а основен принцип на сигурността на шифрите. Броят на рундовете се избира въз основа на обширен криптоанализ, за да се осигури марж на безопасност, и периодично се преоценява при появата на нови атаки. Във всички практически и теоретични аспекти сигурността на блоковите шифри наистина зависи от многократното комбиниране на операции за объркване и дифузия.
Други скорошни въпроси и отговори относно Приложения на блокови шифри:
- Какво трябва да включва един блоков шифър според Шанън?
- Дифузията означава ли, че отделни битове шифрован текст са повлияни от много битове открит текст?
- Режимът ECB разделя ли голям входен обикновен текст на следващи блокове
- Можем ли да използваме блоков шифър за изграждане на хеш функция или MAC?
- Може ли режимът OFB да се използва като генератори на ключови потоци?
- Може ли едно шифроване да бъде детерминистично?
- Какви са режимите на работа?
- Какво прави режимът ECB с простите блокови шифри
- Може ли PSRNG да бъде направен чрез блокови шифри?
- Може ли MAC да бъде изграден чрез блокови шифри?
Вижте още въпроси и отговори в Приложения на блокови шифри