Привет, Хабр! Сегодня я расскажу, как пытался найти уязвимости в AES-128-CBC.
Вступление. Почему я это сделал
Полгода назад я знал только шифр Цезаря. Серьёзно. Мой криптографический опыт ограничивался сдвигом букв в алфавите.
А потом мне стало интересно: а что там внутри у AES? Все говорят "это безопасно", "стойкий алгоритм". Но как это проверить? Не на веру же принимать?
Я полез в документацию, начитался статей, и понял: теория теорией, но я хочу сам увидеть, как выглядит "криптостойкость" в цифрах.
Так родился этот эксперимент.
Что я хотел выяснить
Главный вопрос был простым: насколько шифротексты AES похожи на случайные данные?
Потому что если шифр выдаёт последовательности, которые можно отличить от шума — это уже повод задуматься.
Я не надеялся "взломать" AES. Это было бы глупо. Но я хотел найти границу, где теория расходится с практикой.
Как я строил эксперимент
Мне пришла в голову мысль, что на большой выборке ( как я позже узнал сэмплах ) при условии, что шифр детерменирован ( хоть и нелинеен ) появятся какие-то корреляции. Какое-то статистическое отклонение от нормы. Проще говоря - шум станет "просвечивать"
Что взял за основу
AES-128 с фиксированным ключом
Три режима шифрования: CBC, CTR
Контрольная группа: идеальная случайность (crypto.getRandomValues)
Конкретно этот подход вырос из моего подхода, где я изначально просто искал аномальное поведение байтов на выборках в 10 000, 50 000, 100 000, 500 000, 1 000 000, 50 000 000 сэмплов. Каждый шифротекст — случайная длина от 16 до 48 байт.
Следующий шаг позволяет сравнить поведение на дистанции шифробайтов с истинной случайностью. И найти корреляции, если они есть
Почему именно так
Фиксированный ключ — чтобы исключить лишние переменные. Потому что изначально я пытался "проявить" ключ по вероятностям, как пленку. Но средняя вероятность на символ была около 0,4%. Однако не смотря на то, что "проявка" не сработала - я обнаружил, что на выборках до 5 000 000 сэмлов прослеживаются аномалии.
Что анализировал
Распределение отдельных байтов
Распределение пар соседних байтов
XOR соседних байтов
Последовательности битов (runs test)
-
Статистические тесты хи-квадрат, энтропию, корреляцию
Что я ожидал увидеть
Честно? Я думал, что всё будет идеально. AES же — стандарт шифрования, его проверяли лучшие криптографы мира.
Ожидал: RANDOM ≈ CTR ≈ CBC. Все три должны быть неотличимы.
Результат на 500 000 сэмплов
Показатель
CBC
CTR
Случайные
Хи-квадрат (байты)
560
523
258
P-value
0.000
0.000
0.86
Runs Z
3.04
0.37
-0.36
Макс. отклонение
0.87%
1.07%
0.83%
Некоторые термины:
ХИ-КВАДРАТ (χ²) - Мера того, насколько распределение отличается от "идеально равномерного"
Как понять число:
χ² = 255 → идеальное совпадение с теориейχ² < 255 → распределение даже более равномерное, чем ожидалосьχ² > 255 → есть отклонения от равномерности"Представь, что ты бросаешь кубик 600 раз. В идеале каждая грань выпадет 100 раз. Хи-квадрат показывает, насколько реальные броски отличаются от идеала. Чем больше число — тем сильнее отличие."
P-Value - вероятность ошибки. Вероятность того, что наблюдаемое отклонение — просто случайность
p > 0.05 → "всё ок, это нормальный шум"
p = 0.01 → "есть что-то подозрительное"
p < 0.001 → "почти наверняка есть закономерность"
Runs-Z - Проверяет, есть ли "паттерны" в последовательности битов
Случайная последовательность: 0 1 0 1 0 1 0 1 (много смен)
Неслучайная: 0 0 0 0 1 1 1 1 (длинные серии)
Z-значение (нормальная статистика):
|Z| < 1.96 → норма (95% доверие)|Z| > 2.58 → аномалия (99% доверие)|Z| > 3.29 → сильная аномалия (99.9% доверие)
Что наши цифры означают?
Хи-квадрат 560 против 258 — это в 2.2 раза хуже, чем у случайных данных. P-value = 0.000 значит, что вероятность случайного возникновения такой аномалии — практически ноль.
Но самый интересный результат — Runs Z = 3.04 для CBC
Это статистическая величина, которая показывает, есть ли в последовательности битов "паттерны". В идеале она должна быть около 0. У меня получилось 3.04.
Вероятность случайного получения такого результата — 0.24%. Или 1 шанс из 400.
Что это значит на человеческом языке
Давайте на примерах.
Представьте, что вы бросаете монетку.
В идеале — 500 орлов, 500 решек.
У CBC получилось не 500/500, а 560/440. Причём 560 — это не ошибка округления. Это устойчивое отклонение, которое растёт с объёмом данных. Мне подсказали, что CBC выдает слишком длинные очереди случайных битов.
Почему это происходит? Моя гипотеза
Я не криптограф, поэтому могу ошибаться. Но вот как я это понял
В режиме CBC каждый следующий блок шифруется с учётом предыдущего.
Кажется безобидным. Но если предыдущий зашифрованный блок зависит от предыдущих данных, то возникает цепная реакция. Маленькие неравномерности в исходных данных накапливаются.
В режиме CTR другой принцип - здесь счётчик уникален для каждого блока. Нет зависимости от предыдущих результатов.
Поэтому CTR оказался "чище" CBC, хотя тоже не идеальным (хи-квадрат 523 против 258 у случайности).
Почему CTR тоже не идеален? Потому что исходные данные (plaintext) не идеально случайны. Даже когда я генерировал их через крипто-стойкий RNG, в распределении длин и значений оставались микро-неравномерности. Они и проявились при 500к сэмплов.
ВАЖНОЕ ОТСТУПЛЕНИЕ. Чего это НЕ значит
Я НЕ взломал AES.
Я НЕ могу восстановить ключ.
Я НЕ могу расшифровать чужие сообщения.
Что я могу? В теории - отличить CBC шифротекст от случайных данных с достаточно большой вероятностью при наличии 500к сэмплов.
Это называется "статистический различитель" (distinguisher). В криптографии это считается допустимым результатом, но не уязвимостью.
Если вы хотите повторить эксперимент
Весь код на GitHub: [https://github.com/koolkid90/aes-128-analytics]
Что нужно:
Любой современный браузер (я использовал Chrome)
Терпение на генерацию 500к сэмплов (~2 минуты)
Желание разобраться
Запускаете, жмёте кнопку, получаете три тепловые карты и таблицы.
Что я вынес из этого эксперимента
Теория и практика — разные вещи. В учебниках пишут "AES случаен". На практике при 500к сэмплов видно отличия.
Режим шифрования важен. CBC и CTR ведут себя по-разному с точки зрения статистики.
500к сэмплов — не так много. Я думал, это огромная цифра. Оказалось, для серьёзного криптоанализа нужны миллионы и миллиарды.
Самое ценное — не результат, а понимание. Я теперь гораздо лучше понимаю, что означают "хи-квадрат", "p-value". И могу объяснить это другим.
Про строгость математического доказательства
Важный момент. Я должен быть честен.
P.S. Моё исследование НЕ ЯВЛЯЕТСЯ строгим математическим доказательством. Вот почему:
Я не проверял все возможные условия. Фиксированный ключ, фиксированный RNG, конкретная реализация Web Crypto API.
Статистические тесты имеют допущения. Некоторые тесты предполагают нормальное распределение, которое при конечных выборках может немного отличаться.
Я мог ошибиться в интерпретации p-value. P-value = 0.000 не означает “абсолютная истина”. Это означает “при моих допущениях вероятность очень мала”.
Нет peer review. Ни один профессиональный криптограф не проверял мои результаты.
Что это значит для вашего восприятия:
Относитесь к результатам как к наблюдению, а не как к доказательству
Если вы учёный — вам нужно повторить эксперимент в контролируемых условиях
Если вы практик — имейте в виду, что аномалия существует, но её практическое значение не доказано
Почему я всё равно публикую: Потому что даже наблюдение энтузиаста может быть полезным. Кто-то захочет повторить, кто-то укажет на ошибки, кто-то предложит улучшения. Это нормальный процесс.
Спасибо!