Следует ли из теории информации невозможность создания
1. Идеального шифра?
2. Идеального хэша?

The crucial property of pseudorandom generators is that when the input seed is completely random, the output of the pseudorandom generator is computationally indistinguishable from a truly random string of the same length. Intuitively, a pseudorandom generator stretches a small random string into a much longer one which appears random to and “fools” any computationally-bounded adversary. Such a generator which creates randomness out of nowhere provably cannot exist in the information-theoretic setting, but exists in the computational setting (assuming the existence of one-way functions,for example). We refer the reader to [Gol99, Chap. 3] for further definitions and background on pseudorandom generators.

"List Decoding of Error-Correcting Codes" © Venkatesan Guruswami.

a generator which creates randomness out of nowhere provably cannot exist in the information-theoretic setting

The security of the overall block cipher generally improves with the number of rounds, but a larger number of rounds also means larger keys and less efficient enciphering algorithms. For some block ciphers, the round function can be described by a low-degree polynomial for a non-negligible fraction of its input values.

Nevertheless, intuitively such ciphers do appear to be weak, since the existence of a nontrivial algebraic relation between the plaintext and the ciphertext would make the round function appear quite non-random, and it is not clear this will be alleviated by taking several rounds of such functions. But there was no formal attack which corroborated this intuition.

Jakobsen [Jak98] exposed the weakness of such block ciphers using techniques from coding theory, and in particular list decoding. Specifically, he used the Reed-Solomon list decoding algorithms to break several rounds of block ciphers whose round functions have even a small agreement with low-degree polynomials. In particular, he was able to break up to 10 rounds of a construction by Nyberg and Knudsen that was provably secure against differential and linear cryptanalysis. This represents an interesting use of list decoding in cryptanalysis, and on the flip side provides useful new design criteria for block ciphers. In particular, it indicates that good properties against differential or linear attacks alone is not enough, and that one must avoid using round functions which are algebraically very simple. For further details on the details of the cryptanalysis, we refer the reader to the original article [Jak98].

"List Decoding of Error-Correcting Codes" © Venkatesan Guruswami.

Т.е. специфические атаки (в т.ч. не "алгебраические", а на основе теории кодов), пробивающие много раундов для шифров с раундовой функцией со слабым уровнем алгебраической сложности (к которым принадлежит в т.ч. Keccak), теоретически были давно предсказаны.

that one must avoid using round functions which are algebraically very simple

Codes have also been used in less direct ways for traitor tracing.

The nice feature of their scheme is that it traces all traitors in coalitions of up to a certain size, and once again never accuses innocent subscribers.

"List Decoding of Error-Correcting Codes" © Venkatesan Guruswami.

Как говорил академик И.М.Гельфанд, "чем больше человек знает, тем сложнее от него получить ответ на конкретный вопрос". :)
А вопрос такой: какие конкретно шифры (и как) лучше использовать в каскаде?

Гость (26/04/2013 20:41), не разводите оффтопик. Здесь тема про кеччак. Каскады per se обсуждаются в районе /comment37486, /comment57634, /comment30210 и /faq/kriptografijapraktika#h1792-6 — там и задавайте вопросы.

Тема, конечно, про кеччак, однако для построения каскадов тут есть полезная информация:

"KeccaK имеет преимущество в том, что атаки, рассчитанные против SHA-2 не действуют против него, поскольку эти два алгоритма устроены на совершенно разных принципах".

Спрошу тогда так: каскад кеччак+sha2 хуже, чем только кеччак в плане криптостойкости?

Каскады хэшей это вообще возможно? Как вы это себе представляете?

Видимо так: H = H₃ (H₂ (H₃ (M)))

:)

Что произойдёт при взломе H₃ вопрошавшему предлагается подумать самостоятельно. Также как и о том, что противник видит не только выход каждого хэша, но и состояние каждого раунда. В отличие от шифров, в хэшах от противника секретов вообще нет ни в какой разумной модели. Потому их так сложно создавать.

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

Не то что бы именно разнохэшевый HMAC или каскад мне именно сейчас нужен, мне хочется понять, как можно использовать новое гарантировано не ухудшая прежнего, пусть за счёт дополнительных ресурсов. Удивлён, что эта задача нестандартна и непопулярна.

Unknown, спасибо за развёрнутое объяснение, сейчас стало намного понятнее. Тем не менее, я всё-таки поворчу относительно одного места:

Вот концовка предложения мне совсем непонятна, не могу распарсить. Можно придумать 2ⁿ разных вариантов прочтения и попыток сопоставить. Например, кусок «которые неуязвимы, а только имеют допуски на неидеальность» может быть отнесён как к «идеальным моделям» или «идеализированным», так и к «неидеальным». Нагоромождение отрицаний с пояснениями часто приводит к невозможности однозначного толкования. Я именно поэтому так обильно употребляю дополнительные слова — без них краткость становится сестрой многозначности. Если не хочется заморачиваться с длинными предложениями, есть простой способ изложения:

1. Есть три типа: идеальные, неидеальные и идеализированные.
2. По определению: идеальные — те-то, неидальные — вон те, а идеализированные — вот эти.
3. Свойство выполнено для вот этих, а для тех не выполнено.

Вот и всё.

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

Сейчас ваше изложение совершенно прозрачно, понятно и, более того, вполне соответствует картинке в голове, которая у меня была. В криптографии это называют ε-безопасностью или ε-идеальностью — совершенно естественные понятия, возникающие много где в математике. Абсолютно идеальная вещь — это случай ε → 0. Для некоторых криптопримитивов действительно показано, что их не существует при ε = 0. Эти определения/понятия возникают в условиях абстрактной теории информации, тут никакой технически нагруженной криптографии не требуется.

Ещё подумалось: если проводить параллели с абстрактной CS, то тут же возникает вопрос:

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

Я считаю, что в FAQ криптография очень хорошо описана, а копать глубже и глубже можно всегда. FAQ на то и FAQ, чтобы дать общее понимание ключевых слов/понятий/терминов, но не более того. Иногда для упрощения изложения даже приходится явно произносить неверные вещи и тут же оговаривать, что они неверные, но «здесь упрощено чисто для иллюстрации».

Вот невозможность сделать идеальный ГПСЧ интуитивно кажется совершенно естественным фактом теории, в отличие от невозможности создать идеальный хэш/ICM и т.п. конструкции.

---

Наткнулся на февральское интервью с Жилем:

Although Keccak, as the SHA-3 standard, will coexist with the current standard SHA-2 hash function family, we hope to convince that it is much more than just another “SHAxSUM” algorithm. Keccak relies at its core on a new construction, called the sponge construction, which allows for simpler and more flexible modes of use. The talk will illustrate this by giving various examples on how current software designs can benefit from this greater flexibility, e.g., for all the flavors of hashing, stream encryption, authentication, authenticated encryption and pseudo-random bit generation.

One of us (Gilles) attended FOSDEM last year and he really enjoyed it! Note that we make our presentations using XeLaTeX and are in general happy Linux users. :-)

Несколько дней назад пришёл бумажный спам — какой-то Magazine местной политехнической школы. Внутри было обнаружено вот это. :)

---

P.S. Раз тема про хэши, задам ещё один вопрос. Здесь пишут, что

the basic security of cryptographic hash functions can be seen from three different angles: pre-image resistance, second pre-image resistance and collision resistance.

Т.е. имеем 3 типа уязвимости. Есть ли иерархия между ними? Т.е. следует ли одна уязвимость из другой, или в общем случае все они совершенно независимы?^* Какая из них намного проще всего ищется, и какая сложнее всего? Или это почти всегда зависит от типа хэша?

> А вдруг они раздают персонализированные копии файлов в целях traitor tracing?
Пароль один для всех, причём он был разослан через полупубличную рассылку, что несколько затрудняет traitor tracing. :)

^*Существуют ли примеры того, когда нахождение одного типа уязвимости ничуть не упрощает нахождение другого?

Если не хочется заморачиваться с длинными предложениями, есть простой способ изложения:

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

Вот концовка предложения мне совсем непонятна, не могу распарсить.

Не знаю точно строгой терминологии потому что. Подозреваю, что не только я лично в ней плаваю, но она у разных авторов и школ разная и необщепринятая. Из ε-идеальных раундовых функций можно строить сколь-угодно близкое экспоненциальное приближение к ε → 0, но не достигая при этом "абсолютного" нуля, это тривиальный вывод. На более глубоком уровне окажется, что ε-безопасности не существует. Она сама хоть и ε-неидеальна, но лишь идеализирована. Никакого строго доказуемого ε для вычислительных конструкций не существует.

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

Есть пересчёты ICM-ROM, есть сравнительно тривиальная PRP/PRF switcing lemma. Во многих случаях считается, что если доказана стойкость в одной идеальной модели, то это означает и стойкость в другой идеальной модели. Но строго этот вопрос вроде не решён, поэтому для одного и того же, бывает, публикуют дублирующие доказательства в разных моделях. Страховка ли это от ошибки? От неидеальности? От фундаментальной теоретической непроработанности некоторых вопросов? Не знаю. Не знаю и полной теории "всего" на основе идеализированных моделей. Доказуемая безопасность пытается это сделать, сводя всё к случайному оракулу, но есть всё ещё достаточно места для неполноты, оговорок, недоговорок.


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


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

Какая из них намного проще всего ищется, и какая сложнее всего?

Сложнее всего доказать коллизионную стойкость и соответственно, легче всего её найти (атаку на это свойство конструкции хэша).

Понятно. Спасибо, не знал.

P.S.: Вообще, получилось глубокое и интересное обсуждение (спасибо unknown'у за разъяснение основ ещё раз), которое, по-видимому, можно подытожить так:

> приходится ... запихивать всё в конструкцию со скобками
Могу обучить использованию сносок. Когда-то мне SATtva устроил мастеркласс показал пример их использования в собственных комментариях.

Шнайер в блоге пишет, что на этапе стандартизации NIST ослабил Keccak для повышения производительности его программных реализаций, а теперь, после всех сливов от Сноудена, боится публиковать стандарт в таком виде, поскольку из-за недоверия никто не станет использовать SHA-3.

Они офигели? У меня к сожалению эти гуглослайды не отображаются, где пэдээфку можно скачать? Пэдээфка здесь.

На последнем раунде конкурса наоборот число самих раундов в Keccak было увеличено из-за гипотетических атак нахождения различителя с нулевой суммой. Когда это успели откатить назад или что ещё сделали у Шнайера подробностей нет.

Положил пока pdf-ку сюда.
https://mega.co.nz/#!p4hinB6T!.....XOrt2p-FvIeda4ssB6Mc

Та пэдээфка, которую я добавил в своё сообщение — это она?