От IKar
К Дмитрий Ховратович
Дата 03.08.2010 12:59:09
Рубрики WWII; Спецслужбы;

Re: Скажу авторитетно

Это не так. DES давно уже вскрыли с помощью дифференциального криптоанализа и по этой причине сначала был сделан 3DES (как временная мера) а далее и совершенно новый AES. Так что криптографы не дремлют. Но справедливости ради, нужно сказать, что ломают чаще всего не криптографическими методами, а используя недостатки среды где эта криптография реализована и работает.
От Дмитрий Ховратович
К IKar (03.08.2010 12:59:09)
Дата 03.08.2010 18:08:16

Это так

>Это не так. DES давно уже вскрыли с помощью дифференциального криптоанализа и по этой причине сначала был сделан 3DES (как временная мера) а далее и совершенно новый AES.

3DES был сделан еще в 80-х:). Я прекрасно в курсе про возможности дифференциального и линейного анализа DESа. Однако на практике 2^42 шифртекстов никто не собирает, все покупают COPACOBANA за 7 тысяч евро и вскрывают ключ за неделю (или сколько там последняя версия требует).

Кстати, 3DES можно использовать и сейчас, только медленно будет.
От IKar
К Дмитрий Ховратович (03.08.2010 18:08:16)
Дата 04.08.2010 12:17:49

Re: Это так

>>Это не так. DES давно уже вскрыли с помощью дифференциального криптоанализа и по этой причине сначала был сделан 3DES (как временная мера) а далее и совершенно новый AES.
>
>3DES был сделан еще в 80-х:). Я прекрасно в курсе про возможности дифференциального и линейного анализа DESа. Однако на практике 2^42 шифртекстов никто не собирает, все покупают COPACOBANA за 7 тысяч евро и вскрывают ключ за неделю (или сколько там последняя версия требует).

Откудо информация про то, что он был сделан еще в 80-х, поделитесь ссылкой? Насколько мне известно, когда в 1990-м Biham и Shamir опубликовали свою статью про дифференциальный криптоанализ DES-подобных систем, никаких публичных данных про 3DES небыло. Насколько я помню публично в разных источниках 3DES, в его ныняшнем виде, появился где-то в середине 90-х, а стандартом стал 1998-ом. У меня был некоторый доступ к первым версиям официальных документов по 3DES и они датировались 90-ми. А упоминаний 80-х мне не попадались.

Относительно реального нахождения ключа я согласен, что теоретико-математические атаки на практике нереализуемы. Но они дают представление о системе. И если кто-то , к примеру, опубликует атаку на AES-128, которая снижает сложность с 2^128 до скажем 2^100 (для 128 битного ключа), то с очень большой долей вероятности версия с 128-битным ключом будет считаться "разбитой" и более не будет рекомендована к использованию не смотря на то, что в реальности даже такая атака нереализуема. Возможно это результат некоторого "невроза" наблюдаемого у людей, которые занимаются защитой информации. Но достаточно математически показать какие-то циферки, которые посеят зерно неуверенности, как человек быстро побежит искать что-то "лучше", "защищенее" и внушающее большее «доверие».
От Дмитрий Ховратович
К IKar (04.08.2010 12:17:49)
Дата 04.08.2010 18:27:18

Re: Это так


>Откудо информация про то, что он был сделан еще в 80-х, поделитесь ссылкой? Насколько мне известно, когда в 1990-м Biham и Shamir опубликовали свою статью про дифференциальный криптоанализ DES-подобных систем, никаких публичных данных про 3DES небыло.

Первая атака на Triple-DES - это Hellman\Merkle в 1981 году. Вот статья http://www.cs.purdue.edu/homes/ninghui/courses/Spring04/homeworks/p465-merkle.pdf

Там рассказано, откуда он взялся. Правда, название Triple-DES появилось позднее.


>Относительно реального нахождения ключа я согласен, что теоретико-математические атаки на практике нереализуемы. Но они дают представление о системе. И если кто-то , к примеру, опубликует атаку на AES-128, которая снижает сложность с 2^128 до скажем 2^100 (для 128 битного ключа), то с очень большой долей вероятности версия с 128-битным ключом будет считаться "разбитой" и более не будет рекомендована к использованию не смотря на то, что в реальности даже такая атака нереализуема. Возможно это результат некоторого "невроза" наблюдаемого у людей, которые занимаются защитой информации. Но достаточно математически показать какие-то циферки, которые посеят зерно неуверенности, как человек быстро побежит искать что-то "лучше", "защищенее" и внушающее большее «доверие».

Да, как-то так. Кроме того, атака за 2^100 показывает, что есть ошибки в дизайне, и могут обнаружиться новые.
От IKar
К Дмитрий Ховратович (04.08.2010 18:27:18)
Дата 05.08.2010 08:27:41

Ре: Это так


>>Откудо информация про то, что он был сделан еще в 80-х, поделитесь ссылкой? Насколько мне известно, когда в 1990-м Бихам и Шамир опубликовали свою статью про дифференциальный криптоанализ ДЕС-подобных систем, никаких публичных данных про 3ДЕС небыло.
>
>Первая атака на Трипле-ДЕС - это Хеллман\Меркле в 1981 году. Вот статья http://www.cs.purdue.edu/homes/ninghui/courses/Spring04/homeworks/p465-merkle.pdf

>Там рассказано, откуда он взялся. Правда, название Трипле-ДЕС появилось позднее.

Спасибо, оказывается история создания 3DES была несколько иной, чем я представлял.
От dap
К IKar (03.08.2010 12:59:09)
Дата 03.08.2010 13:28:24

Re: Скажу авторитетно

>Это не так. DES давно уже вскрыли с помощью дифференциального криптоанализа и по этой причине сначала был сделан 3DES (как временная мера) а далее и совершенно новый AES.
DES стоек к дифференциальному криптоанализу. Т.е. данный тип криптоанализа потребует больше операций чем полный перебор. Кстати в связи с этим возникали вопросы не был ли этот метод известен АНБ во время разработки стандарта DES. Насколько я помню АНБ неоффициально подтвердил, что ему был известен этот метод.
DES не стоек для линейного криптоанализа, но для его применения необходимо огромное число пар открытый текст-шифрованный текст. Поэтому это не практичный метод. Реально DES ломали простым перебором в распределенной вычислительной сети. Последний рекорд 56 часов.

>Так что криптографы не дремлют.
Ну да. Время от времени появляются работы на тему "если у нас будет сто тысяч мильонов пар открытый текст-шифрованный текст то мы сможем уменьшить количество операций для нахождения ключа шифра Дохлая рыба с 2^128 до 2^119" Офигенный результат. Теперь всем суперкомпьютерам земли потребуется не 10000 миллиардов, а всего 10 миллиардов лет. А с учетом роста производительности компьютеров может даже за 10 миллионов лет управятся.
На вопрос нафига через 10 млн. лет нужен будет ключ, где взять сто тысяч мильонов пар открытый текст-шифрованный текст криптографы не отвечают.

>Но справедливости ради, нужно сказать, что ломают чаще всего не криптографическими методами, а используя недостатки среды где эта криптография реализована и работает.
Вот именно. Как говорят люди из компетентных органов - стойкость шифра не превышает стойкости шифровальщицы.
От IKar
К dap (03.08.2010 13:28:24)
Дата 03.08.2010 15:34:23

Ре: Скажу авторитетно

>>Это не так. ДЕС давно уже вскрыли с помощью дифференциального криптоанализа и по этой причине сначала был сделан 3ДЕС (как временная мера) а далее и совершенно новый АЕС.
>ДЕС стоек к дифференциальному криптоанализу. Т.е. данный тип криптоанализа потребует больше операций чем полный перебор. Кстати в связи с этим возникали вопросы не был ли этот метод известен АНБ во время разработки стандарта ДЕС. Насколько я помню АНБ неоффициально подтвердил, что ему был известен этот метод.
На счет же NSA много слухов ходит. Может и знали, идея-то вполне себе не поверхности. NSA никогда официально этого не признавала. Как впрочем, мы никогда не узнаем почему они выбрали Rijndael, который криптографы нещадно критиковали, вместо его сильных соперников.
От U235
К IKar (03.08.2010 15:34:23)
Дата 04.08.2010 07:29:01

Мне другое непонятно

А почему за бортом конкурса осталась такая интересная разработка как SHACAL? Быстрый, унифицированный по преобразованиям с SHA и при этом взломать его никому не удалось. Единственное нарекание было к неудачной процедуре расширения ключа в первой версии алгоритма, но это быстро исправили и SHACAL-2 этим уже не страдает.
От Дмитрий Ховратович
К U235 (04.08.2010 07:29:01)
Дата 04.08.2010 07:35:18

Потому что он медленный

В 2.5 раза медленнее, чем SHA-2, а тот еще в полтора раза медленнее AES-128.

Там же открытый текст запихивается в IV, а message cтановится ключом. Соответственно, то же самое число операций, что в SHA-2 уходило на 512 бит, здесь пойдет на 160.
От U235
К Дмитрий Ховратович (04.08.2010 07:35:18)
Дата 04.08.2010 10:37:04

Откуда информация?

В описаниях перепетий конкурса NESSIE вроде как наоборот указывается, что эксперты отмечали очень высокую скорость шифрования по стандарту SHACAL. И опять же что и как сравниваем? Все таки SHACAL-2 использует 512битный ключ и шифрует 256битными блоками, причем использует те же 64 итерации базового преобразования SHA-2, что и хеш-функция SHA-256. AES-128 же использует 128 битный ключ и шифрует блок размером 128 бит.
От Дмитрий Ховратович
К U235 (04.08.2010 10:37:04)
Дата 04.08.2010 11:02:41

Re: Откуда информация?

>В описаниях перепетий конкурса NESSIE вроде как наоборот указывается, что эксперты отмечали очень высокую скорость шифрования по стандарту SHACAL. И опять же что и как сравниваем? Все таки SHACAL-2 использует 512битный ключ и шифрует 256битными блоками, причем использует те же 64 итерации базового преобразования SHA-2, что и хеш-функция SHA-256. AES-128 же использует 128 битный ключ и шифрует блок размером 128 бит.

Все просто. Сравниваем универсально - в процессорных циклах на байт обработанной информации (сообщения или открытого текста) - это позволяет избавиться от проблем с разной длиной блоков. SHA-2 - это 14 процессорных циклов на байт минимум (в обычных реализациях - больше). Соответственно, SHACAL-2-256 обрабатывает за проход в два (512/256) раза меньше данных, поэтому у него будет около 30 циклов на байт. AES-128 сейчас можно реализовать за 10 циклов на байт, AES-256 - за 14.

Поэтому и не выбрали.

Скажу больше. Если бы SHACAL-2 был сравним по скорости с AES, SHA-2 бы оставили стандартом и конкурс на SHA-3 бы не проводили.
От Дмитрий Ховратович
К IKar (03.08.2010 15:34:23)
Дата 03.08.2010 18:17:16

Признали практически официально


>На счет же NSA много слухов ходит. Может и знали, идея-то вполне себе не поверхности. NSA никогда официально этого не признавала.

Копперсмит делал доклад в конце 90-х (не помню где), где рассказывал, как NSA им в IBM прислала стойкие к дифференциальному криптоанализу S-boxы. Собственно, поэтому первая дифференциальная атака 16 раундов сломать не смогла:).

>Как впрочем, мы никогда не узнаем почему они выбрали Rijndael, который криптографы нещадно критиковали, вместо его сильных соперников.

Они - это NIST? Так голосование же было. Соперники слили по скорости (Serpent) и по дизайну (Twofish). А NSA уже позже подключилось, в 2003 году они официально одобрили AES для TOP SECRET, и то с большим ключом.

Ну и "нещадно критиковали" - это художественное преувеличение. Собственно, там одна претензия была и есть - небольшой security margin (7 раундов из 10 можно сломать в 128-битной версии с одним ключом). Ну и теперь видно, что за 10 лет прогресс в анализе AES с одним ключом - мизерный. И больших надежд на то, что дальше будет лучше - нет.
От Vitaly V. Pinjagin
К Дмитрий Ховратович (03.08.2010 18:17:16)
Дата 04.08.2010 00:19:54

на счёт ДвухРыб есть тонкость

>Они - это NIST? Так голосование же было. Соперники слили по скорости (Serpent) и по дизайну (Twofish)

Рыб забраковали с формулировкой типа "не поддаётся анализу", то есть про нынешний AES есть аналитический анализ его стойкости, а рыбы (и кипящие и две и три) анализу не поддаются. Если сюда прибавить отставание открытых шифров от АНБ-шны примерно в 10 лет, то вот эта аналитичность AES-а как-то ээээ... тревожит что ли :-)

ЗЫ
отставание в 10 лет лично у меня получилось по "реперезентативной" выборке из 4-5 известных случаев когда АНБ признавалась что нынешний "рывок" в шифровании был им известен в таком-то году, в основном конечно происходило это в результате личных амбиций разработчиков и их желания крикнуть "Это я, я придумала!"(c)
От Дмитрий Ховратович
К Vitaly V. Pinjagin (04.08.2010 00:19:54)
Дата 04.08.2010 06:07:47

Re: на счёт...


>
>Рыб забраковали с формулировкой типа "не поддаётся анализу", то есть про нынешний AES есть аналитический анализ его стойкости, а рыбы (и кипящие и две и три) анализу не поддаются.

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

> Если сюда прибавить отставание открытых шифров от АНБ-шны примерно в 10 лет, то вот эта аналитичность AES-а как-то ээээ... тревожит что ли :-)
>отставание в 10 лет лично у меня получилось по "реперезентативной" выборке из 4-5 известных случаев когда АНБ признавалась что нынешний "рывок" в шифровании был им известен в таком-то году, в основном конечно происходило это в результате личных амбиций разработчиков и их желания крикнуть "Это я, я придумала!"(c)

Не знаю, какой у них уровень дизайна шифров, но вот дизайн хэш-функций (а там принципы весьма схожи) у АНБ чуть более чем полностью состоит из накручивания всяких рюшечек на ривестовский MD4. Особенно хорошо это видно на примере SHA-2, которая представляет собой просто кашу из XORов и сложения по модулю.
От IKar
К dap (03.08.2010 13:28:24)
Дата 03.08.2010 15:15:39

Ре: Скажу авторитетно

>>Это не так. ДЕС давно уже вскрыли с помощью дифференциального криптоанализа и по этой причине сначала был сделан 3ДЕС (как временная мера) а далее и совершенно новый АЕС.
>ДЕС стоек к дифференциальному криптоанализу. Т.е. данный тип криптоанализа потребует больше операций чем полный перебор. Кстати в связи с этим возникали вопросы не был ли этот метод известен АНБ во время разработки стандарта ДЕС. Насколько я помню АНБ неоффициально подтвердил, что ему был известен этот метод.
Ну если уж чисто математически, то он нестоек к нему, поскольку дифференциальный криптоанализ дает результат 2^47 супротив полного перебора 2^56.
>ДЕС не стоек для линейного криптоанализа, но для его применения необходимо огромное число пар открытый текст-шифрованный текст. Поэтому это не практичный метод. Реально ДЕС ломали простым перебором в распределенной вычислительной сети. Последний рекорд 56 часов.
Последний раз 1999 году это сделали за чуть более чем 22 часа...

>>Так что криптографы не дремлют.
>Ну да. Время от времени появляются работы на тему "если у нас будет сто тысяч мильонов пар открытый текст-шифрованный текст то мы сможем уменьшить количество операций для нахождения ключа шифра Дохлая рыба с 2^128 до 2^119" Офигенный результат. Теперь всем суперкомпьютерам земли потребуется не 10000 миллиардов, а всего 10 миллиардов лет. А с учетом роста производительности компьютеров может даже за 10 миллионов лет управятся.
>На вопрос нафига через 10 млн. лет нужен будет ключ, где взять сто тысяч мильонов пар открытый текст-шифрованный текст криптографы не отвечают.
Мир не стоит на месте. Никто не может угадать как оно будет завтра.

>>Но справедливости ради, нужно сказать, что ломают чаще всего не криптографическими методами, а используя недостатки среды где эта криптография реализована и работает.
>Вот именно. Как говорят люди из компетентных органов - стойкость шифра не превышает стойкости шифровальщицы.
Это если шифровальщица имеет доступ к реальному ключу. В нормально организованной системе люди реальных ключей не знают. Они могут быть носителями чемоданчика с ключами или теми, кто нажимает нужные кнопки, но не иметь ни малейшей возможности узнать реальное значение ключа.
От dap
К IKar (03.08.2010 15:15:39)
Дата 03.08.2010 16:00:01

Ре: Скажу авторитетно

>>ДЕС стоек к дифференциальному криптоанализу.
>Ну если уж чисто математически, то он нестоек к нему, поскольку дифференциальный криптоанализ дает результат 2^47 супротив полного перебора 2^56.
Сдается мне вы путаете сложность с необходимым количеством пар открытый текст-шифртекст. 2^47 это количество пар, а сложность получается больше чем 2^55 - сложность полного перебора.

>Последний раз 1999 году это сделали за чуть более чем 22 часа...
Может быть. Главное что можно это делать оперативно.

>Мир не стоит на месте. Никто не может угадать как оно будет завтра.
Именно поэтому берут ключ 192 или 256 бит и не парятся с угадыванием.

>Это если шифровальщица имеет доступ к реальному ключу. В нормально организованной системе люди реальных ключей не знают. Они могут быть носителями чемоданчика с ключами или теми, кто нажимает нужные кнопки, но не иметь ни малейшей возможности узнать реальное значение ключа.
Это шутка вообще-то. Имеется ввиду человеческий фактор от которого никуда не денешься.
От Дмитрий Ховратович
К dap (03.08.2010 16:00:01)
Дата 04.08.2010 07:39:15

Сложность тоже 2^47

>Сдается мне вы путаете сложность с необходимым количеством пар открытый текст-шифртекст. 2^47 это количество пар, а сложность получается больше чем 2^55 - сложность полного перебора.

Потому что после получения всех шифртекстов нужные биты ключа будут предложены автоматически.