AES (конкурс)
Advanced Encryption Standard, AES — конкурс, організований NIST в 1997 році для вибору нового криптографічного стандарту, який повинен був стати наступником DES. В результаті конкурсу 2000 року переможцем був оголошений шифр Rijndael (який тепер часто називають за іменем конкурсу — AES).
Необхідність у прийнятті нового стандарту була викликана невеликою довжиною ключа DES (56 біт), що теоретично дозволяло застосувати метод грубої сили (повний перебір ключів) проти цього алгоритму. Крім того, архітектура DES була орієнтована на апаратну реалізацію, і програмна реалізація алгоритму на платформах з обмеженими ресурсами не давала достатнього швидкодії. Модифікація 3-DES володіла достатньою довжиною ключа, але при цьому була втричі повільніша.
Початок конкурсу
2 січня 1997 року NIST оголосив про намір вибрати наступника для DES, що був американським стандартом із 1977 року. Однак, замість опублікування алгоритму, NIST прийняв різні пропозиції від зацікавлених сторін про те, яким чином слід вибирати алгоритм. Бурхливий відгук зі сторони відкритої криптографічної спільноти привів до оголошення конкурсу (12 вересня 1997 року). Свій алгоритм могла запропонувати будь-яка організація або група дослідників. Вимоги до нового стандарту були наступними:
- Блочний шифр
- Довжина блоку 128 біт
- Ключі довжиною 128, 192 і 256 біт
Подібні шифри були досить рідкісні під час оголошення конкурсу; можливо, кращим був SQUARE. Додатково кандидатам рекомендувалося:
- Використовувати операції, легко реалізовані як апаратно (в мікрочипах), так і програмно (на персональних комп'ютерах і серверах)
- Орієнтуватися на 32-розрядні процесори
- Не ускладнювати без необхідності структуру шифру для того, щоб всі зацікавлені сторони були в змозі самостійно провести незалежний криптоаналіз алгоритму й переконатися, що в ньому не закладено жодних недокументованих можливостей.
Крім того, алгоритм, який претендує на те, щоб стати стандартом, повинен поширюватися по всьому світу за неексклюзивними умовами й без плати за користування патентом.
Конкурс AES
20 серпня 1998 року на 1-й конференції AES був оголошений список з 15 кандидатів: CAST-256, CRYPTON, DEAL, DFC, E2, FROG, HPC, LOKI97, MAGENTA, MARS, RC6, Rijndael, SAFER +, Serpent, Twofish.
У наступних обговореннях ці алгоритми піддавалися всебічному аналізу, причому досліджувалися не тільки криптографічні властивості, такі як стійкість до відомих атак, відсутність слабких ключів, хороші статистичні властивості, але й практичні аспекти реалізації: оптимізацію швидкості виконання коду на різних архітектурах (від ПК до смарт-карт і апаратних реалізацій), можливість оптимізації розміру коду, можливість розпаралелювання. Перевірка кандидатів на предмет формування випадкових двійкових послідовностей здійснювалася за допомогою набору статистичних тестів NIST.
Перший раунд AES
Протягом першого раунду тестування проводилося з 128-бітними ключами. Лише 9 алгоритмів з 15 змогли пройти статистичні тести, а саме: CAST-256, DFC, E2, LOKI-97, MAGENTA, MARS, Rijndael, SAFER + і Serpent. Решта алгоритмів показали деякі відхилення в тестах на випадковий характер формованих ними довічних послідовностей [1].
У березні 1999 року пройшла 2-га конференція AES, а в серпні 1999 року були оголошені 5 фіналістів: MARS, RC6, Rijndael, Serpent і Twofish. Всі ці алгоритми були розроблені авторитетними криптографами зі світовими іменами. На 3-й конференції AES в квітні 2000 року автори виступили з доповідями про свої алгоритмах.
Другий раунд AES
У другому раунді оцінка придатності фіналістів першого раунду в якості генераторів випадкових чисел проводилося на основі 192-бітних і 256-бітних ключів. Тривалість статистичних тестів NIST склала кілька місяців, причому обчислення проводилися на численних робочих станціях Sun Ultra. Всі дані формувалися і оброблялися в режимі онлайн. В результаті другого раунду було показано, що кожен з п'яти вищевказаних алгоритмів формує абсолютно випадкову бінарну послідовність і тому може бути використаний в якості генератора псевдовипадкових чисел, причому є можливість використання ключів розмірами: 128, 192 і 256 біт [2].
Голосування
Голоси на конференції AES2 розподілилися наступним чином:
- Rijndael: 86 за, 10 проти
- Serpent: 59 за, 7 проти
- Twofish: 31 за, 21 проти
- RC6: 23 за, 37 проти
- MARS: 13 за, 83 проти
Третя конференція AES
Третя конференція AES пройшла в Нью-Йорку 13 і 14 квітня 2000 року, незадовго до завершення другого етапу. На ній були присутні 250 учасників, багато з яких приїхали з-за кордону. Дводенна конференція була розділена на вісім сесій, по чотири в день, плюс до того відбулася неформальна додаткова сесія, підводила підсумки першого дня. На сесіях першого дня обговорювалися питання, пов'язані з програмованими матрицями (FPGA), проводилася оцінка реалізації алгоритмів на різних платформах, в тому числі PA-RISC, IA-64, DEC Alpha, високорівневих смарт-картах і сигнальних процесорах, порівнювалася продуктивність претендентів на стандарт, аналізувалося число раундів в алгоритмах-кандидатах. На сесіях другого дня був проаналізований Rijndael зі скороченим числом раундів і показана його слабкість в цьому випадку, обговорювалося питання про інтегрування в остаточний стандарт всіх п'яти алгоритмів-претендентів, ще раз тестувалися всі алгоритми. В кінці другого дня була проведена презентація, на якій претенденти розповідали про свої алгоритми, їх достоїнства і недоліки. Про Rijndael розповів Вінсент Реймен, який заявив про надійність захисту, високу загальну продуктивність і простоту архітектури свого кандидата.
Вибір переможця
2 жовтня 2000 було оголошено, що переможцем конкурсу став алгоритм Rijndael [3], і почалася процедура стандартизації.
28 лютого 2001 року було опубліковано проект, а 26 листопада 2001 року AES був прийнятий як FIPS 197. Історичну ретроспективу конкурсу можна простежити на вебсайті NIST[4].
Примітки
- NIST IR 6390 Randomness Testing of the Advanced Encryption Standard Candidate Algorithms (англ.)
- NIST IR 6483 Randomness Testing of the Advanced Encryption Standard Finalist Candidates
- NIST Error Page Архівовано 2010-09-28 у Wayback Machine.
- Bounce to index.html Архівовано 2014-07-17 у Wayback Machine.