Да ли безбедност блоковских шифара зависи од вишеструког комбиновања операција конфузије и дифузије?
Безбедност блоковских шифара је фундаментално утемељена у итеративној примени операција конфузије и дифузије. Овај концепт је први формализовао Клод Шенон у свом капиталном раду о теорији комуникације система тајности, где је артикулисао потребу за конфузијом и дифузијом у криптографским системима како би се спречили статистички и структурни напади. Разумевање зашто су потребни вишеструки кругови ових операција и како су оне међусобно повезане, кључно је за разумевање дизајна и безбедности модерних блоковских шифара као што су Стандард за шифровање података (DES) и Напредни стандард за шифровање (AES).
Збуњеност и дифузија: Дефиниције и улоге
Конфузија тежи да учини везу између шифрованог текста и кључа што је могуће сложенијом. То постиже маскирањем статистичке структуре отвореног текста, често употребом нелинеарних супституција (нпр. S-кутије у DES и AES). Што је ово мапирање нелинеарније и сложеније, то је нападачу теже да изведе информације о кључу, чак и ако има приступ многим паровима отвореног текста и шифрованог текста.
Дифузија, с друге стране, има за циљ да прошири утицај сваког бита отвореног текста на више битова шифрованог текста, тако да промена једног улазног бита резултира променама многих излазних битова. Ово својство осигурава да се статистичка својства отвореног текста расипају кроз шифровани текст, што онемогућава нападачима да искористе обрасце путем фреквентне анализе или сличних техника. Дифузија се обично постиже линеарним операцијама мешања, као што су пермутација, битски XOR операције или множење матрица (као у операцији MixColumns у AES-у).
Структура итеративних блоковских шифара
Већина блоковских шифара је структурирана као итеративне шифре, што значи да примењују једноставну функцију заокруживања више пута како би постигле висок ниво безбедности. Функција заокруживања обично комбинује и конфузију (нпр. кроз S-кутију) и дифузију (нпр. кроз пермутацију или кораке мешања). Разлог за коришћење више рунди је да једна примена конфузије и дифузије није довољна да прикрије све структурне односе између отвореног текста, шифрованог текста и кључа. Свака рунда постепено повећава сложеност ових односа и тек након неколико рунди шифра постиже жељени ниво безбедности од познатих криптоаналитичких напада.
На пример, узимајући у обзир AES шифру, свака рунда шифровања се састоји од следећих кључних корака:
1. Подбајтови (конфузија): Сваки бајт у матрици стања се замењује другим према фиксној нелинеарној S-кутији, уводећи нелинеарност.
2. ShiftRows (Дифузија): Редови матрице стања се циклично померају, померајући бајтове у различите колоне и олакшавајући мешање вредности.
3. Мешање колона (дифузија): Колоне стања се мешају коришћењем множења матрица у коначном пољу, додатно ширећи утицај сваког улазног бајта.
4. ДодајРаундКеј (Забуна): Матрица стања се комбинује са подкључем изведеним из главног кључа, уводећи зависност кључа у свакој рунди.
Ефикасност шифре зависи не само од јачине сваке појединачне операције, већ и од броја пута колико се те операције примењују. Криптоаналитичари су показали да смањење броја рунди у шифри као што су 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-у, постиже сличну безбедност итеративном применом кружне функције која комбинује супституцију и пермутацију, при чему излаз сваке рунде улази у следећу. Безбедност таквих конструкција расте експоненцијално са бројем рунди, под претпоставком да сама кружна функција није тривијално инвертибилна или линеарна.
Закључак: Зависност безбедности од итерације
Снага блоковских шифара је уско повезана са поновљеном применом операција конфузије и дифузије. Модерне шифре су дизајниране са довољним бројем рунди како би се осигурало да се елиминишу сви преостали статистички односи из отвореног текста или кључа и да на сваки бит шифрованог текста утиче сваки бит отвореног текста и кључа. Овај итеративни процес није само детаљ имплементације, већ основни принцип безбедности шифара. Број рунди се бира на основу опсежне криптоанализе како би се обезбедила маргина сигурности и периодично се преиспитује како се појављују нови напади. У свим практичним и теоријским аспектима, безбедност блоковских шифара заиста зависи од комбиновања операција конфузије и дифузије више пута.
Остала недавна питања и одговори у вези Примене блок шифри:
- Шта би блоковска шифра требало да садржи према Шенону?
- Да ли дифузија значи да су појединачни делови шифрованог текста под утицајем многих делова отвореног текста?
- Да ли ЕЦБ режим разбија велики отворени текст у наредне блокове
- Да ли можемо да користимо блок шифру да направимо хеш функцију или МАЦ?
- Да ли се ОФБ режим може користити као генератор тока кључева?
- Може ли енкрипција бити детерминистичка?
- Који су начини рада?
- Шта ЕЦБ режим ради једноставним блок шифрама
- Да ли се ПСРНГ може направити блок шифрама?
- Да ли се МАЦ може изградити блок шифрама?
Погледајте више питања и одговора у Применама блок шифара