Криптография
Атаки на симметричные шифры
IBM знала о дифференциальном криптоанализе в 1974 году - но засекретила. S-boxes DES уже были защищены от него. В 1990 году Biham и Shamir независимо открыли атаку и опубликовали. С тех пор все шифры проектируются с публичным криптоанализом. AES выбран после 3 лет публичного конкурса.
- **DES криптоанализ**: Matsui (1993-1994) - линейный криптоанализ за 2^43. Практически реализован. Доказал что 56-битный ключ DES небезопасен уже тогда.
- **WPA-TKIP взлом**: related-key атака на RC4 через слабый IV. Aircrack-ng (open source) взламывал за минуты. Поэтому WPA2 перешёл на AES-CCMP.
- **AES Square attack**: авторы AES сами нашли integral атаку на 4-раундовый предшественник Square. Это укрепило доверие к 10-раундовому AES.
- **NIST конкурс AES**: 15 кандидатов, 3 года публичного анализа (1997-2000). Rijndael выбран частично за чистоту математической структуры и устойчивость к известным атакам.
Дифференциальный криптоанализ
Дифференциальный криптоанализ (Biham & Shamir, 1990): изучает как разность двух открытых текстов распространяется через раунды шифра. Если ΔP = P XOR P' предсказуемо влияет на ΔC = C XOR C' - это утечка информации о ключе.
IBM знала о дифференциальном криптоанализе при разработке DES (1970-е), но засекретила. S-boxes DES уже были оптимизированы против этой атаки - именно поэтому DES был сильнее чем казался. Biham и Shamir независимо открыли атаку в 1990 и опубликовали. NIST учёл дифференциальный криптоанализ в критериях отбора AES.
Что изучает дифференциальный криптоанализ?
Линейный криптоанализ
Линейный криптоанализ (Matsui, 1993): находит линейные приближения между битами открытого текста, ключа и шифртекста. Линейное выражение: P[bit positions] XOR C[bit positions] = K[bit positions] выполняется с вероятностью 1/2 + epsilon (epsilon - линейный потенциал).
Matsui в 1994 реализовал атаку и взломал DES-56 за 10 дней на 12 workstations с 2^43 известными парами. Это было первым теоретически обоснованным и практически выполненным взломом DES. Triple-DES и AES разработаны с учётом линейного криптоанализа.
Почему для линейного криптоанализа нужно O(1/epsilon^2) пар открытый/шифрованный текст?
Related-Key атаки
Related-Key атака: атакующий знает или контролирует отношение между несколькими ключами (XOR, сдвиг). Если шифр не обеспечивает независимости выходов при related keys - это уязвимость. AES-256 имеет теоретическую related-key атаку за 2^99.
WPA (Wi-Fi Protected Access) с TKIP использовал RC4 с related keys: IV в первых 3 байтах ключа. Инструмент Aircrack-ng взламывал WPA-TKIP за минуты через related-key атаку. WPA2 с AES-CCMP заменил TKIP. WPA3 полностью устраняет уязвимость через SAE.
В каком реальном сценарии related-key атака на AES-256 реалистична?
Integral атаки и Square атака
Integral attacks (Square attack): если шифровать все 256 значений одного байта при остальных константных, XOR всех шифртекстов = 0 (balanced set). Это следствие линейности операций ShiftRows и MixColumns в AES.
Integral атака на AES разработана самими авторами AES (Daemen & Rijmen) при создании алгоритма Square - предшественника AES. Они анализировали и объясняли почему 4 раунда недостаточно. 10 раундов AES-128 дают огромный запас безопасности против известных integral атак.
Теоретические атаки на AES (related-key за 2^99, integral за 2^32) означают что AES небезопасен
Теоретические атаки показывают запас безопасности AES по сравнению с полным перебором. AES-128 (2^128 перебор) с лучшей атакой 2^126 всё ещё практически непробиваем
2^99 или 2^126 операций недостижимо. Все эти атаки академические - для оценки безопасности шифра. Реальная угроза AES - неправильное использование (ECB, повтор nonce в GCM), а не криптоанализ.
Почему integral атака работает на 4 раунда AES, но не на 10?
Итоги
- **Дифференциальный криптоанализ**: XOR-разности распространяются предсказуемо через плохо спроектированные S-boxes. AES S-box специально оптимизирован против этого.
- **Линейный криптоанализ**: статистические линейные приближения накапливаются. Нужно 1/epsilon^2 пар. DES взломан за 2^43, AES требует 2^96+.
- **Related-key атаки**: при контроле отношения между ключами. WPA-TKIP (RC4) - реальная жертва. AES-256 в правильных протоколах не уязвим.
- **Integral/Square**: balanced sets через линейные операции. 4 раунда AES уязвимы. 10 раундов - огромный запас безопасности.
Связанные темы
Атаки на симметричные шифры определяют дизайн всех современных алгоритмов:
- Модели безопасности — Chosen Plaintext Attack (CPA) - база для дифференциального и линейного криптоанализа. Формальная модель описывает что может атакующий.
- Side-channel атаки — DPA (Differential Power Analysis) - аналог дифференциального криптоанализа но через измерение энергопотребления, а не разности текстов.
- Атаки на асимметричные системы — Принципы криптоанализа аналогичны: найти математическую структуру, которую можно эксплуатировать статистически или алгебраически.
Вопросы для размышления
- IBM засекретила дифференциальный криптоанализ в 1974 и защитила DES от него. Это правильное решение или нет с позиции безопасности?
- Integral атака на 4-раундовый AES требует только 256 открытых текстов. Почему это chosen plaintext, а не known plaintext атака?
- AES-256 имеет related-key атаку за 2^99. Что это говорит о совете 'чем длиннее ключ, тем безопаснее'?