02.07 // Нові бумеранг-атаки за методом зв'язаних ключів на AES
Нова криптоаналітичних атака на AES, яка швидше простого перебору:
Ці результати можуть пролити нове світло на розробки ключового розкладу до блокових шифрів, але не представляють ніякої реальної загрози для реально існуючих додатків, що використовують AES.
В. Це перший результат в криптоанализе повного AES?
О так. Раніше найуспішніші атаки працювали тільки проти скорочених версій: 10 раундів (з 12) для AES-192, 10 раундів (з 14 для AES-256).
В. Ця атака практична?
О ні. Навіть після поліпшень нам все ще потрібно більше 2 100 шифрування, що знаходиться за межами обчислювальних потужностей людства. Більш того, ця атака працює в моделі атак зі зв'язаними ключами, які мають на увазі більш потужного атакуючого, ніж в моделі з незалежними ключами.
В. Що з себе являє модель атаки зі зв'язаними ключами?
О. В цій моделі атакуючий може спостерігати результати процесу зашифрування / розшифрування на різних секретних ключах. Атакуючий знає (або навіть сам здатний вибирати) співвідношення між різними ключами, але не знає самих ключів. Наприклад, співвідношення може бути просто значенням XOR з відомою константою: K B = K A xor C або складніша зв'язок виду K B = F (K A). де F - довільна функція, вибрана атакуючим. В реальному житті такі залежності можуть виникнути при збоях в апаратному забезпеченні або погано спроектованих протоколах безпеки.
В. У вашій роботі для конференції CRYPTO ви показали практичну атаку на AES в моделі з відкритим ключем - що це значить?
O. Це означає, що AES-256 практично зламаний як хеш-функція і тому не може використовуватися як готовий елемент ( "plug-and-play") в різних конструкціях, заснованих на доказовою безпеки.
В. Чи варто мені продовжувати використовувати AES-192 і AES-256?
О так. Наші атаки не представляють ніякої суттєвої загрози у використанні AES, але стежте уважно за прогресом в криптоанализе.
В. Чи означає це, що AES-256 слабкіше, ніж AES-128?
O. Теоретично - так. Практично - вони обидва все ще забезпечують комфортний рівень безпеки.
В. Як це зачіпає AES-128?
О. Ми не знаємо як атакувати повний AES-128 на підставі цієї ідеї. Однак, ми очікуємо прогрес в криптоанализе скорочених версій AES-128.
Питання: Чи можна виправити цю уразливість?
О. Ця вразливість може бути виправлена, тільки це зажадає дуже серйозних змін в дизайні. Зокрема та частина шифру, яка називається ключовим розкладом, повинна бути перероблена. Це також можна виправити збільшенням числа раундів для всіх версій, але це зробить шифр набагато більш повільним.
В. Який ефект це матиме на конкурс SHA-3 і на заявки на нього, в яких містяться хеш-функції, засновані на AES?
O. Трохи заявок містять використання AES в явному вигляді, так що ми не очікуємо, що багато функцій постраждають від атаки. Однак, основні ідеї можуть бути використані в криптоанализе деяких кандидатів, що містять елементи схожі на AES.
В. Як була відкрита ця вразливість? Чому вона не була відкрита під час конкурсу AES і не була відкрита протягом наступних десяти років?
О. Уразливість була відкрита, коли ми стали розглядати AES як хеш-функцію і стали намагатися шукати уразливості, характерні для хеш-функцій. Ми думаємо, що більшість криптографов використовували тільки техніки, орієнтовані на блокові шифри, проти яких AES був добре захищений розробниками. Інша причина в тому, що AES-256 ймовірно отримав менше уваги з боку криптоаналітиків, ніж AES-128, хоча за іронією саме AES-256 призначений для захисту більш чутливою інформації, ніж AES-128.
В. Чи можете ви коротко описати які властивості шифру привели до такої вразливості?
O. Ключ AES багаторазово використовується в ході шифрування після того як він розгорнутий в ході процесу, званого ключовим розкладом. Ми встановили, що малі зміни ключа викликають малі зміни в процесі шифрування і можуть бути нейтралізовані з високою ймовірністю, що дає атакуючому контроль над поширенням диференціальних змін. Ми називаємо таку нейтралізацію локальної колізією (поняття з криптоанализа хеш-функцій). Деякі послідовні локальні колізії можуть склеюватися один з одним разом в довгі 7-раундові різниці зразків проходження (також звані диференціальними характеристиками або диференціальними шляхами), які мають дуже високі ймовірності - такі про які жоден криптоаналитик не міг раніше і мріяти. Ми називаємо їх чарівними шляхами AES-256.
Цю атаку можна розвинути і до 10 раундів (2 172 кроків), але тільки при неповній моделі пов'язаних ключів (так званих пов'язаних подключей).
RC-5-72 поки не зламаний, правда після припинення спонсорства RSA (правда теж чисто символічного) і інтерес до конкурсу впав. Про успішний брутфорс за 2 72 операцій поки не чути.
2 64 - це точно практично.
Атаки ж на пов'язаних ключах (частина з яких навіть не на полнораундовую версію або не на «чисті" пов'язані ключі) в більшості простих протоколів самі по собі дійсно ніяк не допоможуть зламати зашифрований текст або повідомлення.
Cледовательно, неможливо провести і 2 128 обчислювальних операцій на чомусь би там не було з відомого.
Дозволю собі переклад, може хтось знайде неточність в розрахунках або передумови:
Існує фізичний аргумент щодо того, що 128-бітний симетричний ключ безпечний проти атаки простого перебору. Так звану межу Фон-Неймана-Ландау встановлює нижній фізичний межа споживання енергії, необхідної для проведення обчислень у вигляді ln (2) kT на кожен біт, що використовується в обчисленні, де T - температура обчислювального пристрою в кельвінах, k - константа Больцмана і натуральний логарифм 2 приблизно рівний 0.693. Ніяке пристрій односторонніх обчислень не може використовувати менше цієї енергії, навіть впринципі.
Таким чином, в порядку спрощення проходженням пристроєм всіх можливих значень 128-бітного симетричного ключа (виключаючи проведення всіх необхідних обчислень для його перевірки) буде потрібно 2 128 - 1 бітових перемикань. Якщо ми маємо на увазі, що обчислення проводяться при кімнатній температурі (300 K) ми можемо шляхом накладення меж Фон-Неймана-Ландау оцінити кількість споживаної енергії як
10 18 джоулів, що еквівалентно споживанню 30 гігават енергії в рік (30 x 10 9 W x 365 x 24 x 3600s = 9.46 x 10 17 Дж). Загальна кількість обчислень і перевірок кожного ключа очевидно буде у багато разів більше і зажадає набагато більшого споживання енергії.
Цей аргумент правда має на увазі, що значення регістрів змінюються з використанням традиційних операцій, неминуче генеруючих ентропію. Було показано, що теоретично можна створити обчислювальний обладнання на оборотних обчисленнях, не схильне до таким теоретичним обмеженням, але нічого не відомо про конструювання комп'ютерів такого роду.
Час злому 128-бітного ключа також страхітливо. Необхідно перевірити 2 128 (340,282,366,920,938,463,463,374,607,431,768,211,456) можливих значень. Пристрою, яке могло б перевіряти мільярд мільярдів ключів (10 18) у секунду, все ще треба було б близько 10 13 років для перевірки значень з простору ключів. Це в тисячу разів більше віку всесвіту, який оцінюється в 13,000,000,000 (1.3 x 10 10 років).
AES допускає використання 256-бітних ключів. Злом простим перебором симетричного 256-бітного ключа потребують в 2 128 разів більше обчислювальних ресурсів, ніж 128-бітного. Пристрій, який могло б перевіряти мільярд мільярдів (10 18) ключів в хвилину зажадало б 3 x 10 51 років для повного перебору 256-бітного ключового простору
Пристрій, який могло б перевіряти мільярд мільярдів (10 18) ключів в хвилину зажадало б 3 x 10 51 років для повного перебору 256-бітного ключового простору
Джерела енергії у Всесвіті закінчаться значно раніше, так що, мабуть, можна зробити висновок, що брутфорс такого ключа принципово неможливий.
А це нічого, що КК ефективно знижує довжину криптостійкого ключа в 2 рази? Тобто 128-мібітний ключ, наприклад, буде зламати настільки ж важко як зараз на звичайному комп'ютері 64хбітний. 64бітние AES ще не зламується брутфорсом? 2 ^ 64 - це точно практично.
Що-небудь відомо про КК більш ніж з трьома вентилями?
256-бітовий AES створювався саме в розрахунку на таку загрозу. Але ситуація складається так, що до її появи він в нинішньому бачачи навряд чи доживе.
Що-небудь відомо про КК більш ніж з трьома вентилями? Ну все ж таки КК це трохи більше реально ніж абстрактна фраза типу Було показано, що теоретично можна створити обчислювальний обладнання на оборотних обчисленнях, не схильне до таким теоретичним обмеженням, але нічого не відомо про конструювання комп'ютерів такого роду. Звучить начебто є одна робота яка, де, нібито показала "можливість", але ніхто не впевнений, хоча насправді КК - розвинена тема, над якою зараз працюють тисячі людей по всьому світу.