Введение
Дифференциальный криптоанализ — метод криптоанализа симметричных блочных шифров (и других криптографических примитивов, в частности, хэш-функций). Предложен в 1990 году израильскими специалистами Эли Бихамом и Ади Шамиром.
Дифференциальный криптоанализ основан на изучении преобразования разностей между шифруемыми значениями на различных раундах шифрования. В качестве разности, как правило, применяется операция побитового суммирования по модулю 2, хотя существуют атаки и с вычислением разности по модулю 232. Является статистической атакой, в результате работы предлагает список наиболее вероятных ключей шифрования блочного симметричного шифра.
Дифференциальный криптоанализ применим для взлома DES, FEAL и некоторые других шифров, как правило, разработанных ранее начала 90-х. Количество раундов современных шифров (AES, Camellia и др.) рассчитывалось с учетом обеспечения стойкости в том числе и к дифференциальному криптоанализу.
1. Дифференциальный криптоанализ DES
В 1990 году Эли Бихам и Ади Шамир используя метод дифференциального криптоанализа нашли способ вскрытия DES, более эффективный, чем вскрытие методом грубой силы. Работая с парами шифротекстов, открытые тексты которых имеют определенные отличия[1], ученые анализировали эволюцию этих отличий при прохождении открытых текстов через этапы DES.
1.1. Схема взлома
Рис.1 Схема взлома
На схеме представлено прохождение одного из этапов DES. Пусть X и X' - пара входов, различающихся на ΔX. Соответствующие им выходы известны и равны Y и Y', разница между ними - ΔY. Также известны перестановка с расширением и P-блок, поэтому известны ΔA и ΔC. B и B' неизвестны, но мы знаем, что их разность равна ΔA, т.к. различия XOR Ki c A и A' нейтрализуются. Вскрытие ключа основано на том факте, что для заданного ΔA не все значения ΔC равновероятны, а комбинация ΔA и ΔC позволяет предположить значения A XOR Ki и A' XOR Ki. При известных A и A' это дает нам информацию о Ki.
Таким образом, определенные отличия пар открытых текстов с высокой вероятностью вызывают определенные отличия получаемых шифротекстов. Такие различия называют характеристиками. Для нахождения характеристик составляется таблица, в которой строкам соответствуют возможные ΔX, столбцам - возможные ΔY, а на пересечении строки и столбца пишется, сколько раз заданное ΔY встречается для заданного ΔX. Различные характеристики можно объединять, и, при условии, что рассматриваемые этапы независимы, перемножать их вероятности.
Пара открытых текстов, которая соответствует характеристике называется правильной парой, а пара, не соответствующая характеристике - неправильной парой. Правильная пара указывает на правильный ключ рассматриваемого этапа, неправильная - на случайный ключ. Для нахождения правильного ключа этапа нужно собрать достаточное количество предположений - один из ключей будет встречаться среди правильных чаще, чем остальные. Зная вероятное значение Ki мы получаем 48 битов ключа шифрования K. Остальные 8 битов можно определить с помощью перебора.
1.2. Эффективность взлома
В простейшем виде дифференциальное вскрытие обладает рядом проблем. Для успешного определения ключа необходимо набрать некоторое пороговое количество предположений, иначе вероятность успеха пренебрежимо мала (невозможно выделить правильный ключ из шума). При этом хранение вероятностей 248 возможных ключей (т.е. хранение счетчика для каждого ключа) требует большого объема памяти.
Бихам и Шамир предложили вместо 15-этапной характеристики 16-этапного DES использовать 13-этапную характеристику и с помощью ряда приемов получать данные для последних этапов. Кроме того, они использовали специальные оптимизации для получения вероятных 56-битовых ключей, что позволяло проверять их немедленно. Это решало проблему с пороговым характером взлома и устраняло необходимость в хранении счетчиков.
Наилучший разработанный алгоритм дифференциального вскрытия полного 16-этапного DES требует 247 выбранных открытых текстов. При этом временнная сложность составляет 237 операций DES.
Дифференциальный криптоанализ применим для взлома алгоритмов с постоянными S-блоками, таких как DES. При этом его эффективность сильно зависит от структуры S-блоков. Оказалось, что S-блоки DES оптимизированы против дифференциального криптоанализа. Предполагается, что создатели DES знали об этом методе. По словам Дона Копперсмита из IBM:
При проектировании использовались преимущества определенных криптоаналитических методов, особенно метода "дифференциального криптоанализа", который не был опубликован в открытой литературе. После дискуссий с NSA было решено, что раскрытие процесса проектирования раскроет и метод дифференциального криптоанализа, мощь которого может быть использована против многих шифров. Это, в свою очередь, сократило бы преимущество США перед другими странами в области криптографии.
1.3. Повышение устойчивости к взлому
Устойчивость DES к дифференциальному криптоанализу может быть повышена путем увеличения количества этапов. Дифференциальный криптоанализ для DES с 17 или 18 этапами потребует столько же времени, сколько и полный перебор, а при 19 или более этапах дифференциальный криптоанализ невозможен (т.к. для него потребуется более чем 264 открытых текстов, что невозможно при длине блока 64 бита).
1.4. Недостатки метода
Отмечается, что метод дифференциального криптоанализа в большей степени является теоретическим достижением. Его применение на практике ограничено высокими требованиями к времени и объему данных. Кроме того, этот метод в первую очередь применим для вскрытия с выбранным открытым текстом. Он может быть использован для вскрытия с известным открытым текстом, но в случае полного 16-этапного DES это делает его даже менее эффективным, чем вскрытие грубой силой.
Таким образом, правильно реализованный алгоритм DES сохраняет устойчивость к дифференциальному криптоанализу.
1.5. Сравнение с другими методами
См. Известные атаки на DES
2. Сноски
Для алгоритма DES термин "отличие" определяется как результат применения операции XOR
Дифференциальный криптоанализ — метод криптоанализа симметричных блочных шифров (и других криптографических примитивов, в частности, хэш-функций). Предложен в 1990 году израильскими специалистами Эли Бихамом и Ади Шамиром.
Дифференциальный криптоанализ основан на изучении преобразования разностей между шифруемыми значениями на различных раундах шифрования. В качестве разности, как правило, применяется операция побитового суммирования по модулю 2, хотя существуют атаки и с вычислением разности по модулю 232. Является статистической атакой, в результате работы предлагает список наиболее вероятных ключей шифрования блочного симметричного шифра.
Дифференциальный криптоанализ применим для взлома DES, FEAL и некоторые других шифров, как правило, разработанных ранее начала 90-х. Количество раундов современных шифров (AES, Camellia и др.) рассчитывалось с учетом обеспечения стойкости в том числе и к дифференциальному криптоанализу.
1. Дифференциальный криптоанализ DES
В 1990 году Эли Бихам и Ади Шамир используя метод дифференциального криптоанализа нашли способ вскрытия DES, более эффективный, чем вскрытие методом грубой силы. Работая с парами шифротекстов, открытые тексты которых имеют определенные отличия[1], ученые анализировали эволюцию этих отличий при прохождении открытых текстов через этапы DES.
1.1. Схема взлома
Рис.1 Схема взлома
На схеме представлено прохождение одного из этапов DES. Пусть X и X' - пара входов, различающихся на ΔX. Соответствующие им выходы известны и равны Y и Y', разница между ними - ΔY. Также известны перестановка с расширением и P-блок, поэтому известны ΔA и ΔC. B и B' неизвестны, но мы знаем, что их разность равна ΔA, т.к. различия XOR Ki c A и A' нейтрализуются. Вскрытие ключа основано на том факте, что для заданного ΔA не все значения ΔC равновероятны, а комбинация ΔA и ΔC позволяет предположить значения A XOR Ki и A' XOR Ki. При известных A и A' это дает нам информацию о Ki.
Таким образом, определенные отличия пар открытых текстов с высокой вероятностью вызывают определенные отличия получаемых шифротекстов. Такие различия называют характеристиками. Для нахождения характеристик составляется таблица, в которой строкам соответствуют возможные ΔX, столбцам - возможные ΔY, а на пересечении строки и столбца пишется, сколько раз заданное ΔY встречается для заданного ΔX. Различные характеристики можно объединять, и, при условии, что рассматриваемые этапы независимы, перемножать их вероятности.
Пара открытых текстов, которая соответствует характеристике называется правильной парой, а пара, не соответствующая характеристике - неправильной парой. Правильная пара указывает на правильный ключ рассматриваемого этапа, неправильная - на случайный ключ. Для нахождения правильного ключа этапа нужно собрать достаточное количество предположений - один из ключей будет встречаться среди правильных чаще, чем остальные. Зная вероятное значение Ki мы получаем 48 битов ключа шифрования K. Остальные 8 битов можно определить с помощью перебора.
1.2. Эффективность взлома
В простейшем виде дифференциальное вскрытие обладает рядом проблем. Для успешного определения ключа необходимо набрать некоторое пороговое количество предположений, иначе вероятность успеха пренебрежимо мала (невозможно выделить правильный ключ из шума). При этом хранение вероятностей 248 возможных ключей (т.е. хранение счетчика для каждого ключа) требует большого объема памяти.
Бихам и Шамир предложили вместо 15-этапной характеристики 16-этапного DES использовать 13-этапную характеристику и с помощью ряда приемов получать данные для последних этапов. Кроме того, они использовали специальные оптимизации для получения вероятных 56-битовых ключей, что позволяло проверять их немедленно. Это решало проблему с пороговым характером взлома и устраняло необходимость в хранении счетчиков.
Наилучший разработанный алгоритм дифференциального вскрытия полного 16-этапного DES требует 247 выбранных открытых текстов. При этом временнная сложность составляет 237 операций DES.
Дифференциальный криптоанализ применим для взлома алгоритмов с постоянными S-блоками, таких как DES. При этом его эффективность сильно зависит от структуры S-блоков. Оказалось, что S-блоки DES оптимизированы против дифференциального криптоанализа. Предполагается, что создатели DES знали об этом методе. По словам Дона Копперсмита из IBM:
При проектировании использовались преимущества определенных криптоаналитических методов, особенно метода "дифференциального криптоанализа", который не был опубликован в открытой литературе. После дискуссий с NSA было решено, что раскрытие процесса проектирования раскроет и метод дифференциального криптоанализа, мощь которого может быть использована против многих шифров. Это, в свою очередь, сократило бы преимущество США перед другими странами в области криптографии.
1.3. Повышение устойчивости к взлому
Устойчивость DES к дифференциальному криптоанализу может быть повышена путем увеличения количества этапов. Дифференциальный криптоанализ для DES с 17 или 18 этапами потребует столько же времени, сколько и полный перебор, а при 19 или более этапах дифференциальный криптоанализ невозможен (т.к. для него потребуется более чем 264 открытых текстов, что невозможно при длине блока 64 бита).
1.4. Недостатки метода
Отмечается, что метод дифференциального криптоанализа в большей степени является теоретическим достижением. Его применение на практике ограничено высокими требованиями к времени и объему данных. Кроме того, этот метод в первую очередь применим для вскрытия с выбранным открытым текстом. Он может быть использован для вскрытия с известным открытым текстом, но в случае полного 16-этапного DES это делает его даже менее эффективным, чем вскрытие грубой силой.
Таким образом, правильно реализованный алгоритм DES сохраняет устойчивость к дифференциальному криптоанализу.
1.5. Сравнение с другими методами
См. Известные атаки на DES
2. Сноски
Для алгоритма DES термин "отличие" определяется как результат применения операции XOR
