id: Гость   вход   регистрация
текущее время 23:58 28/03/2024
Владелец: unknown (создано 14/04/2010 17:06), редакция от 16/04/2010 11:38 (автор: unknown) Печать
Категории: криптография, хэширование, симметричное шифрование
https://www.pgpru.com/Новости/2010/АтакаРикошетомИРазличителиНаОсновеПодпространствДляАнализаХэш-функцииWhirlpool
создать
просмотр
редакции
ссылки

14.04 // Атака рикошетом и различители на основе подпространств для анализа хэш-функции Whirlpool


Mario Lamberger, Florian Mendel, Christian Rechberger, Vincent Rijmen и Martin SchlЁffer опубликовали подробную работу по использованию ряда техник в криптоанализе хэш-функции Whirlpool. В настоящее время идёт конкурс NIST на хэш-функцию SHA-3, на который авторы Whirlpool даже не подавали заявку, так как эта функция не соответствует ряду формальных критериев конкурса. Чем же актуальна эта работа?


Во-первых, полученный результат интересен с точки зрения общих критериев проектирования хэш-функций и может дать стимул к новым работам. Во-вторых, авторы подтверждают полезность новых критериев стойкости хэш-функций, в том чиле специально рекомендованных NIST для конкурса SHA-3 (См. подробности: здесь, здесь и здесь). В третьих, Whirlpool основана на байт-ориентированном шифре W, который является почти точной копией шифра AES-Rijndael, но с изменением размера блока до 512 бит. При этом авторы утверждают, что их работа показывает уязвимость в дизайне AES, так как на него распространяются аналогичные методы криптоанализа, что должно послужить в будущем более пристальному изучению структуры AES для создания новых блочных шифров (один из авторов этой работы — Vincent Rijmen является создателем AES). Наконец, функция Whirlpool успела получить некоторое распространение, как наиболее обоснованная альтернатива взломанным MD5 и SHA-1 и была единственной хэш-функцией, стандартизированной ISO/IEC с 2000 года, не опирающейся на дизайн MD4.


Криптографическая хэш-функция H отображает сообщение m, имеющее произвольную длину, в фиксированное по длине хэш-значение h. Избегая излишней формализации можно сказать, что криптографическая хэш-функция должна удовлетворять трём классическим требованиям стойкости: нахождению прообраза, нахождению второго прообраза и нахождению коллизий. Если длина хэш-значения на выходе функции равна N, то противник всегда сможет найти первый и второй прообразы методом перебора 2N различных сообщений, а нахождение коллизий потребует 2N/2 попыток за счёт парадокса дней рождения. Ранее считалось, что этих свойств достаточно для достижения идеальной стойкости.


Последующие исследования показали, что это не так. В ходе конкурса NIST на SHA-3 исследователи обратили внимание на (полу-) начальные коллизии, предколлизии и др. Любое проявление "поведения, отличного от ожидаемого для случайного оракула" стало рассматриваться как подозрительное, даже если уязвимость была показана в отношении функции сжатия, а не для полной хэш-функции.


Интересным результатом данной работы явилось успешное применение рикошет-атаки — разновидности дифференциального криптоанализа, значительным образом оптимизированного для взлома хэш-функций и в тоже время ставшего высокоуровневой моделью в их проектировании. Рикошет-атака может быть использована для получения разного типа коллизий и в тоже время она особенно успешна против простых байт-ориентированных структур на основе AES.


Вторым важным результатом работы стало введение и определение проблемы подпространств, как естественного расширения и формализации требований в вопросах предколлизий. Наконец, в этой работе показан различитель для полной функции сжатия Whirlpool и таким образом продемонстрировано первое отличие этой функции от идеальной модели.


Рикошет-атака была предложена Менделем и др. ранее для анализа хэш-функций, основанных на AES. Эта атака основана на дифференциальном криптоанализе. Дифференциальный криптоанализ — это один из основных инструментов в анализе симметричных криптопримитивов. Первоначально разработанный для DES, затем он был применён к блочным, потоковым шифрам, хэш-функциям. Дифференциальная атака использует предсказуемое прохождение разности между парой на входе криптопримитива к соответствующему выходу. То, что определяет различные паттерны входа, промежуточные значения и выход криптопримитива, называется характеристикой или иначе дифференциальным путём. Пара, которая соответствует характеристике, называется правильной парой. Отношение количества всех правильных пар ко всем возможным входным парам, в некоторых случаях усреднённое по отношению ко всем ключам (если примитив управляется ключом), называется вероятностью пути.


Сокращённые дифференциалы были предложены Кнудсеном для анализа блочных шифров. Если в стандартной дифференциальной атаке необходимо знание полной разности между двумя входными/выходными значениями, то в случае сокращённых дифференциалов достаточно только частично определенной разности, например для каждого байта можно проверить только соответствует он заявленной разности или нет.


При применении дифференциального криптоанализа к хэш-функциям, коллизия для хэш-функции будет возникать тогда, когда есть правильная пара в пути через эту хэш-функцию с нулевой выходной разностью. Аналогично, предколлизия возникает тогда, когда правильная пара в пути имеет хотя и ненулевую разность, но с близким расстоянием Хэмминга. Отсюда следует, что дифференциальный криптоанализ хэш-функций интуитивно очень близок к криптоанализу блочных шифров. Однако есть важная разность в этих двух случаях, которая возникает при рассмотрении рикошет-атаки.


В случае блочных шифров противник, пытающийся найти правильную пару, не может сделать ничего лучше, чем осуществлять перебор пар. Усилия на такой перебор обратно пропорциональны вероятности дифференциального пути. Но поскольку у хэш-функций нет никаких секретных от противника ключей, он может предпринять кое-что более эффективное. В принципе, противник может просто составить уравнения, описывающие правильную пару и решить их. Но на практике такие уравнения носят крайне нелинейный характер и труднорешаемы. Однако часто возможно определить некоторые правильные биты сообщения, увеличивая вероятность случайно угадать часть решения. Используя такого рода технику модификации сообщений можно получить значительно упрощённые уравнения, описывающие хэш-функции, независящие от всех входных частей сообщения.


Таким образом, для нахождения (пред) коллизий используется трёхшаговый алгоритм:


  1. Нахождение высоковероятностного пути.
  2. Использование техники модификации сообщений для определения некоторых значимых битов.
  3. Нахождение оставшихся битов сообщения путём угадывания с последующей проверкой.

В атаке предколлизий используются две фазы, называемые фазой приближения и фазой отскока. В соответствии с этими фазами функция сжатия, внутренний блочный шифр или перестановка делятся на три части. Часть фазы приближения помещается в центральную часть шифра, а две части исходящий фазы — в начало шифра вслед за входящей фазой. Для исходящей фазы конструируются два высоковероятностных (сокращённых) дифференциальных пути и соединяются с входящей фазой.
Помещая наиболее ресурсоёмкую часть атаки в центр шифра и используя такого рода техники перегруппировок можно значительно сократить ресурсы на технику модификации сообщений. Эти методы уже использовались в криптоанализе MD5 и в атаках Вагнера по типу бумеранг и дифференциалов второго порядка.


Авторы улучшили эти техники для криптоанализа Whirlpool и ещё раз доказали слабость ключевой функции AES-подобных структур, которая упрощает перегруппировку.


Новые критерии NIST требуют, чтобы любые подмножества функции сохраняли свойства стойкости самой функции в пересчёте на мощность множества. Это имеет большой практический смысл, так как позволяет произвольным образом урезать выход хэш-функции до нужного минимального значения. Но на практике некоторые программисты используют например для уменьшения величины выхода хэш-функции xor двух половин выхода, что является почти таким же простым и малозатратным как и отбрасывание лишней половины битов. (Прим. перев.: этот вопрос долгое время оставался без аргументированного ответа: что лучше — простое отбрасывание или xor (в ряде случаев — не половин, а нецелого числа частей с дополнением остатка нулями)? С другой стороны в случае идеальной стойкости самой хэш-функции оба варианта сокращения размера её выхода должны быть равностойкими).


В случае xor должно быть сложно подобрать пару сообщений m, m' такую, что H (m) xor H (m' ) = z, иначе говоря для любого типа линейного преобразования L должно быть сложно найти пару входов m, m' такую, что L(H (m) xor H (m' )) = 0. С одной стороны противник не должен выбирать L поскольку для любых m, m' можно тривиально найти L, удовлетворяющее последнему условию. С другой стороны, если мы требуем, чтобы противник мог найти подходящие m, m' для произвольно выбранного L или для большого подмножества, то интутивно может казаться, что противнику будет крайне сложно подобрать соответствующие этим случаям плохо спроектированные хэш-функции.


Авторам удалось предложить вариант формализации проблемы подпространств, проанализировать сложность разных вариантов проблем подпространств, доказать их неэквивалентность для Whirlpool и использовать это в качестве предпосылки доказательства неидеальности хэш-функции. С подробными выкладками можно ознакомиться в работе.


Используя технику различителя на подпространствах, исследователи смогли построить различитель хэш-функции Whirlpool и найти различитель внутреннего шифра W в модели открытого ключа. Ранее такая работа была известна для AES, но теперь есть больше оснований говорить об особенностях криптоанализа всех AES-подобных структур. Также им удалось получить восьмираундовый различитель для W в модели известного ключа. В такой модели противнику известен ключ блочного шифра и он пытается доказать, что перестановка шифртекстов по отношению к открытым текстам не является идеально псевдослучайной (шифр не соотвествует идеальной модели PRP). Для всех 10 раундов была проведена аналогичная атака только с использованием подобранного ключа.


Источник: Cryptology ePrint Archive


 
— Гость (14/04/2010 21:05)   <#>
В принципе, противник может просто составить уравнения, описывающие правильную пару и решить их. Но на практике такие уравнения носят крайне нелинейный характер и труднорешаемы. Однако часто возможно определить некоторые правильные биты сообщения, увеличивая вероятность случайно угадать часть решения. Используя такого рода технику модификации сообщений можно получить значительно упрощённые уравнения, описывающие хэш-функции, независящие от всех входных частей сообщения.
Именно так зачастую и решают сложные задачи. Это называется "упрощением матмодели [физического/экономического/ещё какого-то] являения".

PS: мысленно представил себе, что будет если Rijndael сломают окончательно. В частности, это будет означать возможность прочитать все PGP-шифрованные сообщения :-(
— unknown (15/04/2010 09:27, исправлен 15/04/2010 10:47)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

С одной стороны, "Атаки никогда не становятся слабее. Они могут становится только сильнее" © Б. Шнайер.
С другой стороны, старичка DES за последние 15-20 лет атаковали всеми возможными способами и множеством новых методов криптоанализа и атаки быстрее грубой силы против него есть, но практичность их мала для того, чтобы можно было просто читать зашифрованные тексты. При утраивании длины ключа путём 3-DES, атаки хоть и остаются более быстрыми, чем простой перебор, но стабильно далеко за пределами вычислительных возможностей, хотя формально шифр взломан.


...и перехваченные образцы трафика SSL, SSH, VPN, Tor. Все серверы взломают, все межбанковские переводы выкачают, из всех банкоматов деньги заберут, под шумок опустошат государственную казну, пенсионный фонд и разграбят золотой запас.


На самом деле доказана нестойкость AES-структур в атаках с известным и подобранным ключом, а даже не текстом. Конечно, это плохо, так как теперь окончательно можно говорить, что AES не соответствует модели идеального шифра и по крайней мере хэши из него и его аналогов строить нельзя, но насколько практичны будут дальнейшие результаты исследований — неизвестно. Если будет найдена уязвимость в раундовой функции AES, то такая слабость ключевого расписания облегчит атаку при совместном применении.


Если кого-то это беспокоит, то по крайней мере в GnuPG в свойствах своего ключа (для получаемых сообщений) и в конфиге (для отправляемых) можно переместить AES с первого места в списке предпочтений.


Но неидеальность альтернативных шифров, того же Twofish в моделях хэш-структур была частично показана ещё на конкурсе NESSIE (а предсказана на конкурсе AES), но исследования не доведены до конца. А поскольку Twofish не стал финалистом никаких конкурсов, в стандарты не вошёл, для анализа труден, хэши из него на практике не делают, то и работ по нему просто ничтожно мало. Для других шифров отсутствие таких глубоких работ, как по AES, ещё актуальнее.

— Гость (16/04/2010 08:12)   <#>
[offtop]
Есть ли в GnuPG опция каскадного шифрования? Или предлагается делать это "вручную"?
[/offtop]
— unknown (16/04/2010 09:24, исправлен 16/04/2010 09:33)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

[offtop]


FAQ. Криптография: практика. Как отражается на криптографической стойкости многократное зашифрование сообщений?


С учётом того, что "вручную" вы получите не полноценный каскад, а помещение лишнего известного открытого текста в каждый уровень вложенного сообщеня (заголовки, определённый формат пакетов, номера открытых ключей, подпись), то это IMHO бесполезное занятие.


Во-вторых, стоит ли городить безопасность не "через неясность" (этот термин уж закрепился за другим понятием), а через "запутанность" и "труднодоказуемость"?


[/offtop]


А никто раньше при проектировании шифров и не думал, что ключевое расписание обязано быть таким же идеальным, как и функция раунда. Всегда был компромисс в сторону облегчённости расписания, поскольку подразумевалось, что ключ будет использоваться только рэндомизированный, а уж никак не известный противнику или подбираемый им, чтобы он мог искать различитель ещё и в этой модели. Только когда из шифров стали делать хэши и по-серьёзному их исследовать, только тогда и спохватились.


— Гость (16/04/2010 17:44)   <#>
[offtop]
это IMHO бесполезное занятие.
По вашей же ссылке:
стойкость повышается с каждым дополнительным уровнем "вложенности", поскольку взломщику, чтобы добраться до открытого текста, потребуется последовательно вскрыть все шифртексты, или вычислить все ключи расшифрования, или подобрать все ключевые фразы.

многократно зашифрованное сообщение по самым скромным оценкам должно быть столь же стойко, сколь и самый нижний уровень шифртекста, но, наверняка, каждое последующее зашифрование повышает надёжность предыдущего при условии, что для каждого зашифрования используются различные ключи / ключевые фразы.

А по-моему, каскад (даже в таком случае) целесообразен в качестве защиты от взлома алгоритма. Другой вопрос состоит в обоснованности расматривать серьёзно такой риск, но это уже иной вопрос.
[/offtop]
— Гость (17/04/2010 15:47)   <#>
Разве TOR по сути не является тем-же каскадом?
— Гость (17/04/2010 21:42)   <#>
Криптографически – является, но трафик тора анализируется не только предмет расшифрования, но и на предмет анонимности в сетевых реалиях, и как раз анонимность понижается с ростом длины каскада выше некоторого [по кр. мере, в рамках ряда атак на корреляции трафика между узлами сети].
— unknown (17/04/2010 22:16)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Блочный шифр — это некоторая функция, зависящая при шифровании от открытого текста и ключа:
C = F ( P, k )

Как было описано здесь ( FAQ/КриптографияОбщиеВопросы:Что такое модель идеального шифра? )
каждый ключ задаёт таблицу псевдослучайной перестановки (Pseudo Random Permutation — PRP) всех возможных вариантов открытого текста во все возможные варианты шифртекста (размер каждого "варианта" равен размеру блока, т.е. b)


Тогда двойной каскад — это:

C = F2 ( F1 (P,k1), k2)

Тройной каскад:

C = F3 (F2 (F1 (P,k1), k2), k3)

И т.д., т.е. использование разных шифров и ключей в пределах одного блока.
3-DES можно считать частным случаем каскада, когда F1 = F2 = F3 .

Главное, чтобы каскад сохранял свойство модели идеального шифра. Для этого все составляющие его F должны иметь одинаковый размер блока, а в процессе шифрования между F в открытый текст не вносилось дополнительных данных (операция шифрования каскада должна проводиться на блоке). Тогда, если хотя бы один шифр в каскаде остаётся идеальным, то и весь каскад будет работать, как идеальный шифр (по крайне мере в рамках этой модели).

Если текст шифруется несколько раз (в GnuPG, Tor, SSL, etc) с разными заголовками, беря на вход результаты работы режимов шифрования с предыдущего уровня, то это — не каскад. Модель идеального шифра для совместной операции не работает, поскольку это не PRP над блоком. Каждый шифр по отдельности может остаться идеальным, но не вся операция.
— Гость (18/04/2010 05:43)   <#>
то это — не каскад
Это вопрос определний.
Каждый шифр по отдельности может остаться идеальным, но не вся операция.
В чём неидеальность такой операции? Чем вам помогут для вскрытия служебные заголовки?
— unknown (18/04/2010 15:45, исправлен 18/04/2010 15:57)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Когда изобретали алгебраические атаки опасались (или надеялись), что они будут суперпрактичными, т.к. для взлома может быть достаточно одного блока известного открытого текста. Но они оказались сугубо теоретическими, потому что алгебраическая сложность существующих шифров не позволяет упростить эти атаки так, чтобы они были быстрее перебора грубой силой. И надежды в этом направлении заметно поубавилось.


Но допустим, что такая атака существует и для её проведения достаточно 40 бит работы. Пусть все шифры каскада подвержены этой атаке. Тогда тройной каскад можно рассматривать как многораундовый шифр, для взлома каждой третьей части которого требуется 240 работы, а для всего каскада — 240 • 240 • 240 = 2120. А если на вход третьего шифра F3 попадает известный открытый текст, тогда сначала можно взломать этот шифр отдельно за 240 операций, получить ключ k3 и превратить каскад в двойной. Всего на взлом такого псевдокаскада потребуется 240 + 240 • 240 = 281.


А используя обсуждавшийся ранее Meet in the Middle, двойной каскад также можно сократить до 241 (правда для 128-битных блоков это неактуально).


Пример конечно надуманный, на практике всё равно считают, что надеятся в такой ситуации не на что и что стойкость каскада по крайней мере должна быть не слабее самого сильного его шифра, а на большее рассчитывать не стоит. Так что вроде бы два варианта равнозначны. Но если даже для правильного каскада в идеальном случае доказан такой скептический вывод, может для "неправильного" могут быть какие-то более серьёзные доказательства нестойкости? Взаимодествие различителей тогда имеет больше шансов снизить стойкость. Например если предположить атаки, в которых можно подобрать половину ключа, а вторую половину каким-то образом угадать быстрее, чем перебор и т.д.

— Гость (18/04/2010 19:23)   <#>
Но если даже для правильного каскада в идеальном случае доказан такой скептический вывод, может для "неправильного" могут быть какие-то более серьёзные доказательства нестойкости?
Вы сравниваете теоретическую максимальную идеальную стойкость каскада с тем, что дали исследования, и видите что стойкость хуже. Разумнее же сранивать её со стойкостью каждого из шифра по отдельности. Если взломать каскад по крайней мере сложнее, чем каждый из шифров по отдельности, то его применение целесообразно в качестве защиты от.
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3