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

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


>2. Однако криптографы всё равно взламывают шифры. Что находится в противоречии с п.1.

Прежде всего, шифрблокнот (one-time pad) должен быть равен по длине шифруемому тексту. Соответственно, два пользователя, желающие передавать информацию таким способом, должны предварительно обменяться шифрблокнотами такого же размера. Для повседневного использования это не подходит.

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

Иногда шифры используются с неправильными параметрами или допускают неправильный выбор этих параметров. В этом случае взлом возможен, хотя сам по себе шифр останется стойким. Примерно так был сломан один из первых протоколов защищенного WiFi - WEP, который базируется на шифре RC4.
От IKar
К Дмитрий Ховратович (03.08.2010 09:43:30)
Дата 03.08.2010 12:59:09

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 - сложность полного перебора.

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