Вопросы по криптоанализу

Отечественные ученые А. Г. Ростовцев и Е. Б. Маховенко в 2001 г. предложили принципиально новый метод криптоанализа (по мнению авторов, существенно более эффективный, чем линейный и дифференциальный криптоанализ) путем формирования целевой функции от известного открытого текста, соответствующего ему шифртекста и искомого значения ключа и нахождения ее экстремума, соответствующего истинному значению ключа.

прокомментируйте, пожалуйста, это текст из википедии про гост 28147.

если это так, почему они неизвестны на западе?

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

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

что такое дифференциальный криптоанализ на связанных ключах? Это если известны дифференциалы между ключами?

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

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

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

Ни о чём не говорит, нужно читать сами работы.

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

можно ли в атаке на связанных ключах выбирать разность между ключами dk?

можно ли комбинировать атаки, к примеру, атака на основе выбранного открытого текста и выбранной разности связанных ключей?

Противнику известна разность — атака на связанных ключах с известным соотношением — known related key attack. Противник может сам задавать разность — атака на связанных ключах с подобранным соотношением — chosen related key attack.
Да, выше было приведено описание RKDC. Есть и более изощрённые варианты, наподобие бумеранг-атак — просят зашифровать пару на одних ключах, затем меняют местами и расшифровывают обратно и смотрят на то, сохранились ли какие-то взаимосвязи, при этом можно что-то ещё и с ключами делать. Фантазия криптографов-теоретиков не знает границ!

Понятно. А что представляет собой скользящая атака? В интернете много англоязычного материала на эту тему. Развивает некий Бюриков.

Собственно в исходной работе всё описано, что тут пересказывать.
"Slide Attacks" Alex Biryukov, David Wagner.

Шифр представляется как набор функций PRP:
X₀ → F₁ → F₂ → … → F_r → X_r

Каждая функция зависит от подключа: F(x₁, k).

Если найдены F(x₁, k) = y₁ и F(x₂, k) = y₂, то ключ k легко извлекается.

Для этого нужно найти например такую пару X₀, X'₀, которая даёт одинаковые значения на раунде n и n+1 соответственно. Это и есть "скользящая пара". Для её поиска используется парадокс дней рождения.

Краткие выводы: чем больше размер блока, тем сложнее найти пару. Для SP-шифров поиск пары требует 2^n/2 известных открытых текстов от размера блока, для сетей Файстеля 2^n/4 подобранных открытых текстов. Атака независит от числа раундов. Эффективна против шифров со слабым ключевым расписанием. Потенциально эффективна против шифров с S-блоками, зависящими от ключа и преобразованиями, зависящими от шифруемых данных.

Самые фатальные последствия атака вызывает при неправильном использовании какого-либо шифра, когда он используется с одним ключом, но с разным числом раундов.

Понятно. Что такое одноразовая аутентификация?

Про одноразовый блокнот, совершенный шифр слышал, а об этом упоминаний нигде не слышал.

Unconditionally secure authentication, метод Вегмана-Картера и его разновидности.

Кажется, unknown'а или DoSят или брутфорсят. Скоро найдут отличие от random oracle идеального сферического криптографа в вакууме и опубликуют различитель, что не позволит ему баллотироваться на конкурс стандартов в НИСТ. :)

Гость (18/02/2010 18:54), LOL. Значит, не мне одному пришла в голову такая мысль. :)

Значит, не мне одному пришла в голову такая мысль.

Честно признаюсь – это я тут иногда оффтоплю в перерывах между работой. Просьба сильно не казнить :-)

а победителя положат под вакуумный колпак в палату мер и весов в Париже.

Лишь бы не взяли под колпак и не положили на полтора метра в землю.

На днях заимел исходник программы, реализующей последовательное шифрование стандартными криптографическими алгоритмами с открытыми исходными кодами (Blowfish, Twofish, Rijndael, TEA, CAST). Можно выбирать разную последовательность используемых алгоритмов. В исходниках предусмотрена возможность как стабилизации по Base64, так и без нее. Возник вопрос к участникам топика, усложняет ли последовательное шифрование разными алгоритмами криптоанализ сообщения или же последовательное шифрование наоборот вредит стойкости?