Криптографический глоссарий

есть оценки снизу

Тривиальные — есть, ага. Не менее одной операции на взлом.

Создать идеальный блочный шифр невозможно, это доказали

Пруффлинк?

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

Почему это? Берется наилучший известный метод криптоанализа и считается криптостойкость алгоритма.

Нет гарантий, что никто не придумает практически эффективный криптоанализ ГОСТа и быстро поломает его.

Конечно. Поэтому и существует ИКСИ, управления различные.

У меня есть оценки снизу, а вы все говно.

Ну так поделитесь.

Пруфлинк.


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


Борьба щита и меча при условии доказанности невозможности создания идеального щита. Многие считают такой путь развития тупиковым. То, что иначе пока нельзя (нет у нас другой практичной криптографии), ещё не означает, что надо преподносить нужду за благодетель.

Есть только набор фактов:

1. Ideal Cipher Model (ICM) зависит от Random Oracle Model (ROM), т.к. блочный шифр — это зависящая от ключа псевдослучайная перестановка (Key depended PRP) всех вариантов блоков открытого текста во все варианты блоков шифртекста, неотличимая от случайной.
2. Никакая реально существующая функция не может заменить RO по причине конечности внутреннего состояния.
3. Для блочных шифров конечность внутреннего состояния функции-эмулятора RO несущественна, т.к. размер блока и ключа — тоже конечны. Т.е. все три параметра (размер внутреннего состояния, размер блока, размер ключа) можно согласовать с запасом.
4. П.3 является недостаточным условием по причине неидеальности раундовой функции, необходимо подбирать ещё ряд параметров, например число раундов. Безотносительно к размеру внутреннего состояния и числу раундов для реальной многораундовой шифрующей функции, даже в идеализированной модели будет зазор безопасности ε, что делает безопасность меньше единицы, но в реальных конструкциях сводиться к долям бита в пересчёте на число операций.

1. Существуют трудности в реальной оценке ε для вычислительно-стойких алгоритмов, в то время как для Information-Theoretic — IT-стойких, это значение м.б. рассчитано точно. Впрочем, не доказано и обратного — что не существует метода создания выч. алгоритма со строго доказуемым ε. Но пока неизвестно ни одного такого метода, ни алгоритма, ни условий их существования.
2. Не доказана возможность существования односторонних функций в вычислительно-стойкой модели, что ставит ещё один вопрос о возможности стойкой эмуляции RO. Обратное тоже не доказано, но как в п.1 и не продемонстрировано существование.

Т.е. строгого доказательства (не)возможности построения стойких алгоритмов в выч. модели не существует, но упорное отсутствие прогресса в появлении положительных живых примеров п.п. 1-2 из предыдущего абзаца вызывает скепсис.

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

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

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

Пруфлинк.

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

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

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

А для его практической эмуляции нужна псевдослучайная функция, которая упирается в RO.

Вы думаете Бабаш одну книжку написал? А вы попробуйте такой купить в магазине: Бабаш, Егоров. Методы криптографического анализа.

Принято. Однако, с этими книжками та же фигня, что и с книгами по радиоэлектронной борьбе: суть ужимается в несколько компактных текстов, поэтому основная информация свободно утекает через неформальные разговоры, рассказы и пересказы, исходя из которых можно составить достаточно детальную картину используемых методов. Если бы за военной криптографией крылось что-то действительно глубокое, был бы другой разговор, но судя по ГОСТу всем всё и так ясно. Понятно, что криптографическая школа ФСБ чисто физически не может конкурировать с открытой мировой криптографией, если даже по поводу АНБ есть скепсис на этот счёт.

Вообще, можно выпустить книжку по обычному матанализу для учащихся ИКСИ и засекретить её. Ну, просто так, по приколу, чтоб было. Для поддержания марки и престижа это тоже сделать можно, а какой в этом смысл — другой вопрос.

строгого доказательства (не)возможности построения стойких алгоритмов в выч. модели не существует

Если вернуться к /comment19007 и повторно его обдумать, то, наверное, можно сказать, что никакой стандартный блочный шифр не может иметь безопасность в 2²⁵⁶ операций или около того. С одной стороны, заранее понятно, что границу можно очень сильно понизить, с другой — что какая-то нетривиальная нижняя граница на сложность брутфорса тоже должна быть. Получается, открытый вопрос — размер окна неопределённости между нетривиальной верхней и нетривиальной нижней границами, поскольку мы не знаем ни ту, ни другую.

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

Добрый вечер. Перевожу статью. В этой статье есть небольшой кусочек о способах атаки.

Two common models of attack are CPA (chosen plaintext attack) and CCA (chosen ciphertext attack).In the first the attacker has access
to an encryption oracle to which it can present plaintexts and receive the
ciphertexts resulting from the encryption of these plaintexts.

Не пойму как переводится слово Oracle, но думаю что это не компания Oracle.
Как его можно перевести?

Что имеется в виду понятно) has access
to an encryption oracle ~ имеет доступ к шифрования типа чёрного ящика. Но как нормально перевести?

Шифрующий оракул — так и есть, русского аналога нет и не предвидится. Дешифрующий оракул тоже бывает. Random Oracle — вы в виде какого ящике себе (и читателям перевода) представлять будете? а Left-Right Oracle? А миры, управляемые оракулами? Как игрушечные вселенные, засунутые в ящики/комнаты?

Погуглите по нашему сайту по слову Oracle и оракул.

Я посмотрю, спасибо. Но могли бы вы ещё сказать вашу интерпретацию этого термина (оракул) в криптографии?

Воображение: автор спросит «как правильно перевести термины "hosen plaintext attack" и "chosen ciphertext attack"?».

Реальность:

Не пойму как переводится слово Oracle, но думаю что это не компания Oracle.

Оракул — blackbox function из теории сложности:

Оракул — не то же, что в классическое криптографии (считается, что там только частный его случай), это что-то типа абстрактной blackbox-функции без каких-либо особых предопределённых свойств.

Оттуда он перекочевал в вычислительно-стойкую криптографию. Как-то так.

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

При попытке перевести, подобрав аналог с ящиком, будет проблема, что термины black box crypto(analysys), whyte box crypto и glass box crypto уже заняты.

Оракул это, короче. Вы ему вопрос (текст, строку) — он вам ответ (шифртекст, хэш-отпечаток и др.). А вы по его ответам пытаетесь раскрыть секрет, который лежит в основе различителя (distinguisher) от идеальной модели.

Примерно так: «Существуют две общей модели атаки: атака с подобранным открытым текстом и атака с подобранным шифртекстом. В первом случае атакующий имеет доступ к шифрующему оракулу и может подавать ему на вход открытый текст, получая ему (открытом тексту) соответствующий шифртекст».

Примерно в этом же было в /comment29611.

Если хочется понять смысл, есть подборка постов.

Я бы сказал, что оракул — это идеализированная функция или идеализированный чёрный ящик. Есть свойства этой идеальной функции (реакция на отклик), а есть свойства реальных функций. Отличие в свойствах даёт различитель реальной функции от идеальной, т.е. от соответствующего оракула.