Уважаемые, какие есть методы для оценки стойкости криптоалгоритмов?
Возможно ли например сказать, что стойкость IDEA — XXXX попугаев, а стойкость ГОСТ — XXXY? Или стойкость RSA с ключём 512 бит XXX попугаев, а 1024 бита — XXXXXX?
А как насчёт алгоритмов хеширования — как их стойкость оценивают?
Что можно почитать по этому вопросу?

Zampolit wrote:
> Уважаемые, какие есть методы для оценки стойкости криптоалгоритмов?
> Возможно ли например сказать, что стойкость IDEA — XXXX попугаев, а
> стойкость ГОСТ — XXXY? Или стойкость RSA с ключём 512 бит XXX попугаев,
> а 1024 бита — XXXXXX?
> А как насчёт алгоритмов хеширования — как их стойкость оценивают?
> Что можно почитать по этому вопросу?
Печальная правда включает такое утверждение:

Ещё не доказано полностью про криптостойкость ничего положительного,
включая невозможность взломать любой текст, зашифрованный по ГОСТ/по RSA
с ключом 1536 бит за 15с на AMD K6 — 200MHz.

Точнее, всё доказанное опирается на возможно неверные предположения.

Соответственно, 1 попугай = 1 год возраста * 1 с рекордного взлома/1Флоп
производительности лучшего суперкомпьютера в том году. Ничего намного
лучше, кажется, нет. Можно поискать в интернете про то, как ломали RSA
(правда, относительно грубой силой, т.е увеличение ключа в 10 раз эту
атаку обламывает (пока)). Сломан hash MD5 (в слабом смысле: можно найти
такую пару файлов, что сумма совпадёт). Что именно ещё сломано и в каких
условиях — точно не знаю.

Здравствуйте, raskin, Вы писали:

R>Соответственно, 1 попугай = 1 год возраста * 1 с рекордного взлома/1Флоп
R>производительности лучшего суперкомпьютера в том году.

Странная формула. Взять хотябы вот этот множитель: "1 с рекордного взлома".
Вы думаете, "1 с рекордного взлома" чем-нибудь отличается от обыкновенной 1 секунды? Или я чего-то не понял?

Хелп.

Zampolit wrote:
Ой, я опечатался..
> R>Соответственно, 1 попугай = 1 год возраста * 1 с рекордного взлома*1Флоп
> R>производительности лучшего суперкомпьютера в том году.
>
> Странная формула. Взять хотябы вот этот множитель: "1 с рекордного взлома".
> Вы думаете, "1 с рекордного взлома" чем-нибудь отличается от
> обыкновенной 1 секунды? Или я чего-то не понял?
Я имел в виду следующее: за 20 лет взлом этого шифра с ключом этой длины
был произведён один раз за 1000000 секунд при том, что самый мощный
суперкомпьютер в том году имел производительность 10ГФлоп. Считаем —
получаем 20*10^6*10^9=2*10^16 попугая. Ну, можно формулу
отмасштабировать, чтоб попугаев было у всех больше/меньше.. Я просто
перечислил причины, подтверждающие надёжность: возраст, отсутствие за
эти годы быстрого взлома, и наличие при имевшемся взломе достаточных
вычислительных мощностей.

Здравствуйте, Zampolit, Вы писали:

Z>Уважаемые, какие есть методы для оценки стойкости криптоалгоритмов?
Z>Возможно ли например сказать, что стойкость IDEA — XXXX попугаев, а стойкость ГОСТ — XXXY? Или стойкость RSA с ключём 512 бит XXX попугаев, а 1024 бита — XXXXXX?
Z>А как насчёт алгоритмов хеширования — как их стойкость оценивают?
Z>Что можно почитать по этому вопросу?

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

Здравствуйте, y3sky, Вы писали:

Y>Практически все криптоалгоритмы, являются теоретически стойкими. Вообще есть классика жанра Брюс Шнайер (книга вроде "Ведение в Криптографию", хотя может и ошибаюсь)

Applied Cryptography.

Вот, что там написано про RSA

Утверждение, что безопасность RSA от проблемы разложения на множители больших чисел, является гипотетической. Никто и никогда не доказал математически, что для восстановления m по c и e нужно разложить n на множители.

Так что с теорией не всё хорошо.

Здравствуйте, gear nuke, Вы писали:

GN>

Утверждение, что безопасность RSA от проблемы разложения на множители больших чисел, является гипотетической. Никто и никогда не доказал математически, что для восстановления m по c и e нужно разложить n на множители.

Так что с теорией не всё хорошо.
Скорее, с полной теорией ничего не хорошо. Если P=NP, то криптографии не муществует (в современном определении).

Здравствуйте, Аноним, Вы писали:
А>Скорее, с полной теорией ничего не хорошо. Если P=NP, то криптографии не муществует (в современном определении).

Я бы сказал что появляются проблемы у криптографии с открытым ключом. Классическим системам фактически наплевать на NP=P, это ведь не повлияет на перебор ключа при одноразовой гамме, например...

Если кому нитересно — вот что я разузнал:
Оценить стойкость алгоритма можно временной сложностью вычислений, необходимых для его вскрытия.
Временная сложность — функция, различная для каждого алгоритма и каждого типа атаки на него.
Криптостойкость алгоритма — временная сложность той атаки на него, которая в данный момент считается самой эффективной.
Для RSA это сложность разложения на множители, для блочного шифра ГОСТ — перебор всех возможных вариантов ключа и т.д.
Временная сложность полного перебова ключей — простая функция: O=2^n, n — длина ключа.
Измеряется временная сложность в попугаях, но зная сколько процессорных операций уходит на один попугай и сколько таких операций может выполнить компьютер в единицу времени можно перейти ко времени, которое потребуется на взлом. Это как раз и есть те тысячи и миллионы лет вычислений, которые публикуют в книжках.

Для алгоритмов хеширования стойкость измеряют следующей формулой: sqrt(2^n), n — длина хэш-значения. Для хэш-функции ГОСТ сложность равна 2^128. Для SHA-1: 2^80, недавние события снизили её до 2^69. (http://www.cryptopro.ru/CryptoPro/doc/SHA-1_collision.pdf) Как получили такую новую цифру — пока не понял.

andrey.def wrote:
> Здравствуйте, Аноним, Вы писали:
> А>Скорее, с полной теорией ничего не хорошо. Если P=NP, то криптографии
> не муществует (в современном определении).
>
> Я бы сказал что появляются проблемы у криптографии с открытым ключом.
> Классическим системам фактически наплевать на NP=P, это ведь не повлияет
> на перебор ключа при одноразовой гамме, например...

Одноразовой гамме всё по барабану. Полноценной. Но она очень дорога. А
ГОСТ поможет вряд ли — пишем decrypt + spell-checker + grep "ключевое
слово" . Проверить, что ключ похож на правильный (расшифровывается
что-топочти читаемое с ключевым словом) можно за P-время — тогда можно
подобрать ключ, подходящий лучше всех (P=NP, L(key)<<L(message) ). И
даже десять лучших. Это даёт немаленькую вероятность раскрытия. А по
определениям (формальным) эффективной криптосистемы с закрытым коротким
ключом всё ещё веселее. Скорее есть шанс, что NP=P, но алгоритмы имеют
степень 1000 — но всё равно все определения в науке будут переписаны.

PS. Тот Аноним — это я.

Здравствуйте, Zampolit, Вы писали:

Все оценки делаются исходя из того, что ломать будут brute-force-ом.
Если же (как писалось выше в ветке) P=NP то о криптографии можно забыть вообще.
До тех пор пока это не опровергнуто самая лучший критерий криптостойкости — время.

Здравствуйте, raskin, Вы писали:

R>Проверить, что ключ похож на правильный (расшифровывается что-топочти читаемое с ключевым словом)
R>можно за P-время — тогда можно подобрать ключ, подходящий лучше всех (P=NP, L(key)<<L(message) ).
Вообще-то, у тебя линейная задача — перебрать все ключи в пространстве 2**x бит (где x >= 64) и ты в дамках. Это при условии что ты знаешь открытый текст... И не надо даже заморачиваться на расшифроку всего сообщения. Достаточно расшифровать блок... тоде в пределах 2**х бит (где x <= длина ключа)...

ЗЫ. Почитайте "Прикладная криптография" Шнайера. Главы о попытках а взлома DES — в особенности.
ЗЗЫ. А DES вообще-то до сих пор не взломан... за приемлемое для обычного человека время. Кстати, я пробовал его брут-форснуть на 16 машинах методом монте-карло. За выходные не получилось.

Здравствуйте, raskin, Вы писали:

R>ГОСТ поможет вряд ли — пишем decrypt + spell-checker + grep "ключевое
R>слово" .
не понял, что это значит

0xDEADBEEF wrote:
> Здравствуйте, raskin, Вы писали:
>
> R>Проверить, что ключ похож на правильный (расшифровывается что-топочти

> Вообще-то, у тебя линейная задача — перебрать все ключи в пространстве
> 2**x бит (где x >= 64) и ты в дамках. Это при условии что ты знаешь
> открытый текст... И не надо даже заморачиваться на расшифроку всего
Это при известном тексте, я просто грубо прикинул, что надо делать при
неизвестном открытом тексте. Мне тоже очевидно, что при P=NP
криптографии нет.
> ЗЫ. Почитайте "Прикладная криптография" Шнайера. Главы о попытках а
> взлома DES — в особенности.
Речь шла о теории — поэтому лучше читать Foundations of cryptography
Голдрайха. Это я читал.
> ЗЗЫ. А DES вообще-то до сих пор не взломан... за приемлемое для обычного
> человека время. Кстати, я пробовал его брут-форснуть на 16 машинах
> методом монте-карло. За выходные не получилось.
А какая длина ключа? Впрочем, исходно вопрос был о том, что новый
алгоритмический прорыв может всё изменить.

andrey.def wrote:
> R>ГОСТ поможет вряд ли — пишем decrypt + spell-checker + grep "ключевое
> R>слово" .
> не понял, что это значит

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