Основа идей об алгебраическом криптоанализе возникла более 60 лет назад. Но только лишь за последние 10 лет были разработаны эффективные программные средства (частичного) решения множества NP-полных проблем. Было взломано некоторое число потоковых шифров. Только один блочный шифр был взломан этим методом — сам по себе слабый KeeLoq.
В этой работе автор теоретически обосновывает взлом реально используемый шифр ГОСТ. Он отмечает, что это первый случай в истории, когда алгебраическим криптоанализом был взломан стандартизированный государственный шифр.
Ничто из имеющихся сведений и литературы по поводу ГОСТа не даёт оснований полагать, что шифр может быть небезопасным. Наоборот, большой размер ключа и большое число раундов делают ГОСТ, на первый взгляд, подходящим для десятилетий использования.
ГОСТ был широко исследован ведущими экспертами в области криптографии, известными в области анализа блочных шифров, такими как Шнайнер(Брюс Шнайер
Безопасность — это процесс, а не результат. («Security is a process, not a product»)
Американский криптограф, писатель и специалист по компьютерной безопасности. Президент и основатель криптографической компании Counterpane Systems, член совета директоров Международной ассоциации криптологических исследований и член консультативного совета Информационного центра электронной приватности.
Родился 15 января 1963 года в Нью-Йорке. Закончил Американский университет в Вашингтоне. На данный момент проживает в Миннеаполисе, штат Миннесота.
Работал на министерство обороны США и компанию Bell Labs. Позже стал одним из основателей занимающейся вопросами информационной безопасности компании Counterpane Systems (нынешнее название — Counterpane Internet Security).
Автор нескольких книг по криптографии, в том числе бестселлера «Прикладная криптография». Разработал известные алгоритмы симметричного шифрования Blowfish, Twofish и Threefish,
хэш-функцию Skein и генератор случайных чисел Yarrow)
[Вы должны быть зарегистрированы и подключены, чтобы видеть это изображение]
Бирюков, Данкельман, Вагнер, множеством австралийских, японских и российских учёных, экспертами по криптографии от ISO, и все исследователи высказывались, что всё выглядит так, что он он может быть или должен быть безопасным. Хотя широкого понимания достигло мнение, что сама по себе структура ГОСТа крайне слаба, например, по сравнению с DES, в частности, диффузия не настолько хороша, однако это всегда обуславливалось тем, что это должно компенсироваться большим числом раундов (32), а также дополнительной нелинейностью и диффузией, обеспечиваемой сложением по модулю.
Бирюков и Вагнер писали: "Большое число раундов (32) и хорошо изученная конструкция Фейстеля, сочетаемая с последовательными Шенновскими (Основатель теории информации Клод Элвуд Шеннон
Я могу представить себе такое будущее, в котором мы будем для роботов тем, чем сейчас являются собаки для людей.
Клод Шеннон родился 30 апреля 1916 года в городе Петоцки, штат Мичиган, США. Первые шестнадцать лет своей жизни Клод провел в Гэйлорде, Мичиган, где в 1932 году он закончил общеобразовательную среднюю школу Гэйлорда. В юности он работал курьером службы Western Union. Отец его был адвокатом и в течение некоторого времени судьей. Его мать была преподавателем иностранных языков и впоследствии стала директором Гэйлордской средней школы. Молодой Клод увлекался конструированием механических и автоматических устройств. Он собирал модели самолетов и радиотехнические цепи, создал радиоуправляемую лодку и телеграфную систему между домом друга и своим домом. Временами ему приходилось исправлять радиостанции для местного универмага. Томас Эдисон был его дальним родственником.
В 1932 году Шеннон был зачислен в Мичиганский университет, где выбрал курс, посещая который начинающий ученый познакомился с работами Джорджа Буля. В 1936 г. Клод оканчивает Мичиганский университет, получив степень бакалавра по двум специальностям математика и электротехника, и устраивается в Массачусетский технологический институт, где он работал ассистентом-исследователем на дифференциальном анализаторе Ванневара Буша — аналоговом компьютере. Изучая сложные, узкоспециальные электросхемы дифференциального анализатора, Шэннон увидел, что концепции Буля могут получить достойное применение.
Статья, написанная с его магистерской работы 1937 года «Символический анализ реле и коммутаторов», была опубликована в 1938 году в издании Американского института инженеров-электриков (AIEE). Она также стала причиной вручения Шэннону премии Американского института инженерии имени Альфреда Нобеля в 1940 году. Цифровые цепи — это основа современной вычислительной техники, таким образом результаты его работ являются одними из наиболее важных научных результатов ХХ столетия. Говард Гарднер из Гарвардского университета отозвался о работе Шэннона, как о «возможно, самой важной, а также самой известной магистерской работе столетия».
По совету Буша Шеннон решил работать над докторской диссертацией по математике в MIT. Идея его будущей работы родилась у него летом 1939 года, когда он работал в Cold Spring Harbor в Нью-Йорке. Буш был назначен президентом Carnegie Institution в округе Вашингтон и предложил Шеннону принять участие в работе, которую делала Барбара Беркс по генетике. Именно генетика, по мнению Буша, могла послужить предметом приложения усилий Шеннона. Докторская диссертация Шеннона, получившая название «Алгебра для теоретической генетики», была завершена весной 1940 года. Шеннон получает Докторскую степень по математике и степень магистра по электротехнике.
В период с 1941 по 1956 гг. Шеннон преподает в Мичиганском университете и работает в компании Белл (Bell Labs). В лаборатории Белл Шеннон, исследуя переключающие цепи, обнаруживает новый метод их организации, который позволяет уменьшить количество контактов реле, необходимых для реализации сложных логических функций. Он опубликовал доклад, названный «Организация двухполюсных переключающих цепей». Шеннон занимался проблемами создания схем переключения, развил метод, впервые упоминавшийся фон Нейманом и позволяющий создавать схемы, которые были надежнее, чем реле, из которых они были составлены. В конце 1940 года Шеннон получил Национальную научно-исследовательскую премию. Весной 1941 года он вернулся в компанию Белл. С началом Второй мировой войны Т.Фрай возглавил работу над программой для систем управления огнем для противовоздушной обороны. Шеннон присоединился к группе Фрая и работал над устройствами, засекавшими самолеты противника и нацеливавшими зенитные установки, также он разрабатывал криптографические системы, в том числе и правительственную связь, которая обеспечивала переговоры Черчилля и Рузвельта через океан. Как говорил сам Шеннон, работа в области криптографии подтолкнула его к созданию теории информации.
С 1950 по 1956 Шеннон занимался созданием логических машин, таким образом, продолжая начинания фон Неймана и Тьюринга. Он создал машину, которая могла играть в шахматы, задолго до создания Deep Blue. В 1952 Шеннон создал обучаемую машину поиска выхода из лабиринта.
Шеннон уходит на пенсию в возрасте пятидесяти лет в 1966 году, но он продолжает консультировать компанию Белл (Bell Labs). В 1985 году Клод Шеннон со своей супругой Бетти посещает Международный симпозиум по теории информации в Брайтоне. Шеннон довольно долго не посещал международные конференции, и сначала его даже не узнали. На банкете Клод Шеннон дал короткую речь, пожонглировал всего тремя мячиками, а затем раздал сотни и сотни автографов изумленным его присутствием ученым и инженерам, отстоявшим длиннейшую очередь, испытывая трепетные чувства по отношению к великому ученому, сравнивая его с сэром Исааком Ньютоном.
Он был разработчиком первой промышленной игрушки на радиоуправлении, которая выпускалась в 50-ые годы в Японии (фото). Также он разработал устройство, которое могло складывать Кубик Рубика (фото), мини компьютер для настольной игры Гекс, который всегда побеждал соперника (фото), механическую мышку, которая могла находить выход из лабиринта (фото). Так же он реализовал идею шуточной машины «Ultimate Machine» (фото).
Клод Шеннон ушел из жизни 24 февраля 2001 года.)одстановками-перестановками, обеспечивают солидную основу безопасности ГОСТ". В той же самой работе мы читаем: "после значительных затрат времени и усилий, никакого прогресса в криптоанализе стандарта в открытой литературе достигнуто не было".
Таким образом, не было никаких существенных атак, которые позволяли бы дешифрование или восстановление ключа в реалистичном сценарии, когда ГОСТ используется в шифровании со множеством разных случайных ключей. В противоположность этому, известно очень много работ по атакам на слабые ключи в ГОСТ, атаки со связанными ключами, атаки на восстановление секретных S-блоков. На Crypto-2008 был представлен взлом хэш-функции, основанной на этом шифре. Во всех атаках атакующий имеет значительно больший уровень свободы, чем ему обычно допускается. В традиционных применениях шифрования с использованием случайно выбираемых ключей до настоящего момента никаких серьёзных криптографических атак на ГОСТ найдено не было, что в 2010 году выражалось итоговой фразой: "несмотря на существенные усилия криптоаналитиков за прошедшие 20 лет, ГОСТ всё ещё не взломан" (Axel Poschmann, San Ling, and Huaxiong Wang: 256 Bit Standardized Crypto for 650 GE GOST Revisited, In CHES 2010, LNCS 6225, pp. 219-233, 2010).
Линейный и дифференциальный анализ ГОСТ
В широкоизвестной книге Шнайера мы читаем: "Против дифференциального и линейного криптоанализа ГОСТ вероятно более устойчив, чем DES". Основную оценку безопасности ГОСТа дали в 2000 году Габидулин и др. Их результаты очень впечатляющи: при заложенном уровне безопасности 2^256, достаточно пяти раундов для защиты ГОСТа от линейного криптоанализа. Более того, даже при замене S-блоков на тождественные и единственной нелинейной операции шифра — сложения по модулю 2^32 — шифр всё равно стоек против линейного криптоанализа после 6 раундов из 32. Дифференциальный криптоанализ ГОСТа выглядит сравнительно более лёгким и привлекает больше внимания. Для 2^128 уровня безопасности исследователи (Vitaly V. Shorin, Vadim V. Jelezniakov and Ernst M. Gabidulin: Linear and Differential Cryptanalysis of Russian GOST, Preprint submitted to Elsevier Preprint, 4 April 2001) предполагали достаточную стойкость на уровне 7 раундов. По их утверждению, взлом ГОСТа более чем на пяти раундах "крайне труден". Более того, двое японских исследователей показали, что классическая прямая дифференциальная атака с одной дифференциальной характеристикой имеет крайне малую вероятность для прохождения через большое число раундов.
На основе факта изучения достаточно "хорошей" итеративной дифференциальной характеристики для ограниченного числа раундов (которая сама по себе имеет вероятность прохождения не лучше 2^-11.4 на раунд), получено значения множества подходящих ключей менее половины. Для полнораундового ГОСТа такая атака с единственной характеристикой будет работать лишь с ничтожно малой частью ключей порядка 2^-62 (и даже в этой малой части она будет иметь вероятность прохождения не более 2^-360).
Более сложные атаки включают множества дифференциалов, следующих определённым паттернам, например с использованием отдельных S-блоков, имеющих нулевые дифференциалы, в то время как на других битах имеются ненулевые. Речь об атаках-различителях, основанных на плохих диффузионных свойствах ГОСТа. Лучшая из таких атак работает против 17 раундов ГОСТа, зависит от ключа и имеет сама по себе на выходе крайне слабый различитель от случайных данных, чтобы его как-то можно было использовать для получения информации о ключе.
Атаки скольжения и отражения
Согласно Бирюкову и Вагнеру, структура ГОСТа, включающая обратный порядок подключей в последних раундах, делает его стойким против атак скольжения (т.н. "слайд-атаки"). Однако из-за наличия большой величины самоподобия в шифре, это позволяет проводить атаки инверсии ключей на комбинации неподвижных точек и свойства "отражения" (т.н. "рефлективные атаки") для определённых слабых ключей. Сложность этой атаки 2^192 и 2^32 подобранных открытых текстов.
Последние результаты
Новые атаки также используют отражение и фактически взломали ГОСТ, что и было представлено на конференции FSE 2011. Эти атаки также были открыты независимо автором данной работы. Атака требует 2^132 байтов памяти, что фактически хуже, чем более медленные атаки с меньшим требованием к памяти.
Множество новых атак на основе самоподобия работают против всех ключей ГОСТа и позволяют взламывать полнораундовый ГОСТ с 256-битным ключом, а не только для слабых ключей, как было ранее. Все эти атаки требуют значительно меньше памяти и они значительно быстрее.
Эти новые атаки могут рассматриваться как примеры новой общей парадигмы криптоанализа блочных шифров, называемой "редукция алгебраической сложности", с обобщением этих атак на множество частных случаев атак с известными неподвижными точками, скольжением, инволюциями и циклами. Важно, что среди семейства всех этих атак есть такие, которые позволяют проводить криптоанализ ГОСТ без всяких отражений и без каких-либо симметричных точек, которые проявляются в ходе вычислений. Одним из примеров является простая атака взлома ГОСТа без отражений в данной работе.
Алгебраический криптоанализ и атаки с небольшой сложностью данных на шифры с уменьшенным числом раундов
Алгебраические атаки на блочные и потоковые шифры могут быть представлены в виде проблемы решения большой системы Булевых алгебраических уравнений, которая следует геометрии и структуре частной криптографической схемы. Сама идея восходит к Шеннону. На практике была представлена для DES (впервые представлена автором данной работы) как метод формального кодирования и может взламывать 6 раундов всего на одном известном открытом тексте. Манипуляция с уравнениями происходит на основе алгоритмов XL, базисов Грёбнера, метода ElimLin, SAT-решателей.
На практике алгебраические атаки реализованы против очень малого числа раундов блочных шифров, но уже приводили к взломам потоковых шифров, также есть и успехи во взломе сверхлёгких шифров для микрооборудования. Из-за трудностей в объёмах памяти и оценках затрат на вычисления их комбинируют с другими атаками.
Практический результат пока скромен: 2^64 известных открытых текста и 2^64 памяти для хранения пар "открытый текст/шифртекст" позволяют взломать ГОСТ в 2^8 быстрее, чем простой перебор. Но в плане криптоанализа это делает полностью справедливым утверждение о том, что "ГОСТ взломан"
Комментарий: Ну зачем же переделывать все?! DES, например, сразу после принятия как стандарт FIPS был уязвим. Это ж не помешало его до сих пор использовать во всех ОС:-). Не надо ничего переделывать, можно усовершенствовать, добавить несколько раундов шифрования, усложнить таблицу замен и т.п. - масса вариантов. Самый лучший - сократить время жизни информации, которая закрывается ГОСТом и ключа!
В этой работе автор теоретически обосновывает взлом реально используемый шифр ГОСТ. Он отмечает, что это первый случай в истории, когда алгебраическим криптоанализом был взломан стандартизированный государственный шифр.
Ничто из имеющихся сведений и литературы по поводу ГОСТа не даёт оснований полагать, что шифр может быть небезопасным. Наоборот, большой размер ключа и большое число раундов делают ГОСТ, на первый взгляд, подходящим для десятилетий использования.
ГОСТ был широко исследован ведущими экспертами в области криптографии, известными в области анализа блочных шифров, такими как Шнайнер(Брюс Шнайер
Безопасность — это процесс, а не результат. («Security is a process, not a product»)
Американский криптограф, писатель и специалист по компьютерной безопасности. Президент и основатель криптографической компании Counterpane Systems, член совета директоров Международной ассоциации криптологических исследований и член консультативного совета Информационного центра электронной приватности.
Родился 15 января 1963 года в Нью-Йорке. Закончил Американский университет в Вашингтоне. На данный момент проживает в Миннеаполисе, штат Миннесота.
Работал на министерство обороны США и компанию Bell Labs. Позже стал одним из основателей занимающейся вопросами информационной безопасности компании Counterpane Systems (нынешнее название — Counterpane Internet Security).
Автор нескольких книг по криптографии, в том числе бестселлера «Прикладная криптография». Разработал известные алгоритмы симметричного шифрования Blowfish, Twofish и Threefish,
хэш-функцию Skein и генератор случайных чисел Yarrow)
[Вы должны быть зарегистрированы и подключены, чтобы видеть это изображение]
Бирюков, Данкельман, Вагнер, множеством австралийских, японских и российских учёных, экспертами по криптографии от ISO, и все исследователи высказывались, что всё выглядит так, что он он может быть или должен быть безопасным. Хотя широкого понимания достигло мнение, что сама по себе структура ГОСТа крайне слаба, например, по сравнению с DES, в частности, диффузия не настолько хороша, однако это всегда обуславливалось тем, что это должно компенсироваться большим числом раундов (32), а также дополнительной нелинейностью и диффузией, обеспечиваемой сложением по модулю.
Бирюков и Вагнер писали: "Большое число раундов (32) и хорошо изученная конструкция Фейстеля, сочетаемая с последовательными Шенновскими (Основатель теории информации Клод Элвуд Шеннон
Я могу представить себе такое будущее, в котором мы будем для роботов тем, чем сейчас являются собаки для людей.
Клод Шеннон родился 30 апреля 1916 года в городе Петоцки, штат Мичиган, США. Первые шестнадцать лет своей жизни Клод провел в Гэйлорде, Мичиган, где в 1932 году он закончил общеобразовательную среднюю школу Гэйлорда. В юности он работал курьером службы Western Union. Отец его был адвокатом и в течение некоторого времени судьей. Его мать была преподавателем иностранных языков и впоследствии стала директором Гэйлордской средней школы. Молодой Клод увлекался конструированием механических и автоматических устройств. Он собирал модели самолетов и радиотехнические цепи, создал радиоуправляемую лодку и телеграфную систему между домом друга и своим домом. Временами ему приходилось исправлять радиостанции для местного универмага. Томас Эдисон был его дальним родственником.
В 1932 году Шеннон был зачислен в Мичиганский университет, где выбрал курс, посещая который начинающий ученый познакомился с работами Джорджа Буля. В 1936 г. Клод оканчивает Мичиганский университет, получив степень бакалавра по двум специальностям математика и электротехника, и устраивается в Массачусетский технологический институт, где он работал ассистентом-исследователем на дифференциальном анализаторе Ванневара Буша — аналоговом компьютере. Изучая сложные, узкоспециальные электросхемы дифференциального анализатора, Шэннон увидел, что концепции Буля могут получить достойное применение.
Статья, написанная с его магистерской работы 1937 года «Символический анализ реле и коммутаторов», была опубликована в 1938 году в издании Американского института инженеров-электриков (AIEE). Она также стала причиной вручения Шэннону премии Американского института инженерии имени Альфреда Нобеля в 1940 году. Цифровые цепи — это основа современной вычислительной техники, таким образом результаты его работ являются одними из наиболее важных научных результатов ХХ столетия. Говард Гарднер из Гарвардского университета отозвался о работе Шэннона, как о «возможно, самой важной, а также самой известной магистерской работе столетия».
По совету Буша Шеннон решил работать над докторской диссертацией по математике в MIT. Идея его будущей работы родилась у него летом 1939 года, когда он работал в Cold Spring Harbor в Нью-Йорке. Буш был назначен президентом Carnegie Institution в округе Вашингтон и предложил Шеннону принять участие в работе, которую делала Барбара Беркс по генетике. Именно генетика, по мнению Буша, могла послужить предметом приложения усилий Шеннона. Докторская диссертация Шеннона, получившая название «Алгебра для теоретической генетики», была завершена весной 1940 года. Шеннон получает Докторскую степень по математике и степень магистра по электротехнике.
В период с 1941 по 1956 гг. Шеннон преподает в Мичиганском университете и работает в компании Белл (Bell Labs). В лаборатории Белл Шеннон, исследуя переключающие цепи, обнаруживает новый метод их организации, который позволяет уменьшить количество контактов реле, необходимых для реализации сложных логических функций. Он опубликовал доклад, названный «Организация двухполюсных переключающих цепей». Шеннон занимался проблемами создания схем переключения, развил метод, впервые упоминавшийся фон Нейманом и позволяющий создавать схемы, которые были надежнее, чем реле, из которых они были составлены. В конце 1940 года Шеннон получил Национальную научно-исследовательскую премию. Весной 1941 года он вернулся в компанию Белл. С началом Второй мировой войны Т.Фрай возглавил работу над программой для систем управления огнем для противовоздушной обороны. Шеннон присоединился к группе Фрая и работал над устройствами, засекавшими самолеты противника и нацеливавшими зенитные установки, также он разрабатывал криптографические системы, в том числе и правительственную связь, которая обеспечивала переговоры Черчилля и Рузвельта через океан. Как говорил сам Шеннон, работа в области криптографии подтолкнула его к созданию теории информации.
С 1950 по 1956 Шеннон занимался созданием логических машин, таким образом, продолжая начинания фон Неймана и Тьюринга. Он создал машину, которая могла играть в шахматы, задолго до создания Deep Blue. В 1952 Шеннон создал обучаемую машину поиска выхода из лабиринта.
Шеннон уходит на пенсию в возрасте пятидесяти лет в 1966 году, но он продолжает консультировать компанию Белл (Bell Labs). В 1985 году Клод Шеннон со своей супругой Бетти посещает Международный симпозиум по теории информации в Брайтоне. Шеннон довольно долго не посещал международные конференции, и сначала его даже не узнали. На банкете Клод Шеннон дал короткую речь, пожонглировал всего тремя мячиками, а затем раздал сотни и сотни автографов изумленным его присутствием ученым и инженерам, отстоявшим длиннейшую очередь, испытывая трепетные чувства по отношению к великому ученому, сравнивая его с сэром Исааком Ньютоном.
Он был разработчиком первой промышленной игрушки на радиоуправлении, которая выпускалась в 50-ые годы в Японии (фото). Также он разработал устройство, которое могло складывать Кубик Рубика (фото), мини компьютер для настольной игры Гекс, который всегда побеждал соперника (фото), механическую мышку, которая могла находить выход из лабиринта (фото). Так же он реализовал идею шуточной машины «Ultimate Machine» (фото).
Клод Шеннон ушел из жизни 24 февраля 2001 года.)одстановками-перестановками, обеспечивают солидную основу безопасности ГОСТ". В той же самой работе мы читаем: "после значительных затрат времени и усилий, никакого прогресса в криптоанализе стандарта в открытой литературе достигнуто не было".
Таким образом, не было никаких существенных атак, которые позволяли бы дешифрование или восстановление ключа в реалистичном сценарии, когда ГОСТ используется в шифровании со множеством разных случайных ключей. В противоположность этому, известно очень много работ по атакам на слабые ключи в ГОСТ, атаки со связанными ключами, атаки на восстановление секретных S-блоков. На Crypto-2008 был представлен взлом хэш-функции, основанной на этом шифре. Во всех атаках атакующий имеет значительно больший уровень свободы, чем ему обычно допускается. В традиционных применениях шифрования с использованием случайно выбираемых ключей до настоящего момента никаких серьёзных криптографических атак на ГОСТ найдено не было, что в 2010 году выражалось итоговой фразой: "несмотря на существенные усилия криптоаналитиков за прошедшие 20 лет, ГОСТ всё ещё не взломан" (Axel Poschmann, San Ling, and Huaxiong Wang: 256 Bit Standardized Crypto for 650 GE GOST Revisited, In CHES 2010, LNCS 6225, pp. 219-233, 2010).
Линейный и дифференциальный анализ ГОСТ
В широкоизвестной книге Шнайера мы читаем: "Против дифференциального и линейного криптоанализа ГОСТ вероятно более устойчив, чем DES". Основную оценку безопасности ГОСТа дали в 2000 году Габидулин и др. Их результаты очень впечатляющи: при заложенном уровне безопасности 2^256, достаточно пяти раундов для защиты ГОСТа от линейного криптоанализа. Более того, даже при замене S-блоков на тождественные и единственной нелинейной операции шифра — сложения по модулю 2^32 — шифр всё равно стоек против линейного криптоанализа после 6 раундов из 32. Дифференциальный криптоанализ ГОСТа выглядит сравнительно более лёгким и привлекает больше внимания. Для 2^128 уровня безопасности исследователи (Vitaly V. Shorin, Vadim V. Jelezniakov and Ernst M. Gabidulin: Linear and Differential Cryptanalysis of Russian GOST, Preprint submitted to Elsevier Preprint, 4 April 2001) предполагали достаточную стойкость на уровне 7 раундов. По их утверждению, взлом ГОСТа более чем на пяти раундах "крайне труден". Более того, двое японских исследователей показали, что классическая прямая дифференциальная атака с одной дифференциальной характеристикой имеет крайне малую вероятность для прохождения через большое число раундов.
На основе факта изучения достаточно "хорошей" итеративной дифференциальной характеристики для ограниченного числа раундов (которая сама по себе имеет вероятность прохождения не лучше 2^-11.4 на раунд), получено значения множества подходящих ключей менее половины. Для полнораундового ГОСТа такая атака с единственной характеристикой будет работать лишь с ничтожно малой частью ключей порядка 2^-62 (и даже в этой малой части она будет иметь вероятность прохождения не более 2^-360).
Более сложные атаки включают множества дифференциалов, следующих определённым паттернам, например с использованием отдельных S-блоков, имеющих нулевые дифференциалы, в то время как на других битах имеются ненулевые. Речь об атаках-различителях, основанных на плохих диффузионных свойствах ГОСТа. Лучшая из таких атак работает против 17 раундов ГОСТа, зависит от ключа и имеет сама по себе на выходе крайне слабый различитель от случайных данных, чтобы его как-то можно было использовать для получения информации о ключе.
Атаки скольжения и отражения
Согласно Бирюкову и Вагнеру, структура ГОСТа, включающая обратный порядок подключей в последних раундах, делает его стойким против атак скольжения (т.н. "слайд-атаки"). Однако из-за наличия большой величины самоподобия в шифре, это позволяет проводить атаки инверсии ключей на комбинации неподвижных точек и свойства "отражения" (т.н. "рефлективные атаки") для определённых слабых ключей. Сложность этой атаки 2^192 и 2^32 подобранных открытых текстов.
Последние результаты
Новые атаки также используют отражение и фактически взломали ГОСТ, что и было представлено на конференции FSE 2011. Эти атаки также были открыты независимо автором данной работы. Атака требует 2^132 байтов памяти, что фактически хуже, чем более медленные атаки с меньшим требованием к памяти.
Множество новых атак на основе самоподобия работают против всех ключей ГОСТа и позволяют взламывать полнораундовый ГОСТ с 256-битным ключом, а не только для слабых ключей, как было ранее. Все эти атаки требуют значительно меньше памяти и они значительно быстрее.
Эти новые атаки могут рассматриваться как примеры новой общей парадигмы криптоанализа блочных шифров, называемой "редукция алгебраической сложности", с обобщением этих атак на множество частных случаев атак с известными неподвижными точками, скольжением, инволюциями и циклами. Важно, что среди семейства всех этих атак есть такие, которые позволяют проводить криптоанализ ГОСТ без всяких отражений и без каких-либо симметричных точек, которые проявляются в ходе вычислений. Одним из примеров является простая атака взлома ГОСТа без отражений в данной работе.
Алгебраический криптоанализ и атаки с небольшой сложностью данных на шифры с уменьшенным числом раундов
Алгебраические атаки на блочные и потоковые шифры могут быть представлены в виде проблемы решения большой системы Булевых алгебраических уравнений, которая следует геометрии и структуре частной криптографической схемы. Сама идея восходит к Шеннону. На практике была представлена для DES (впервые представлена автором данной работы) как метод формального кодирования и может взламывать 6 раундов всего на одном известном открытом тексте. Манипуляция с уравнениями происходит на основе алгоритмов XL, базисов Грёбнера, метода ElimLin, SAT-решателей.
На практике алгебраические атаки реализованы против очень малого числа раундов блочных шифров, но уже приводили к взломам потоковых шифров, также есть и успехи во взломе сверхлёгких шифров для микрооборудования. Из-за трудностей в объёмах памяти и оценках затрат на вычисления их комбинируют с другими атаками.
Практический результат пока скромен: 2^64 известных открытых текста и 2^64 памяти для хранения пар "открытый текст/шифртекст" позволяют взломать ГОСТ в 2^8 быстрее, чем простой перебор. Но в плане криптоанализа это делает полностью справедливым утверждение о том, что "ГОСТ взломан"
Комментарий: Ну зачем же переделывать все?! DES, например, сразу после принятия как стандарт FIPS был уязвим. Это ж не помешало его до сих пор использовать во всех ОС:-). Не надо ничего переделывать, можно усовершенствовать, добавить несколько раундов шифрования, усложнить таблицу замен и т.п. - масса вариантов. Самый лучший - сократить время жизни информации, которая закрывается ГОСТом и ключа!
