Потоковый шифр на основе хеш-функции и Counter Mode Encryption CTR

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

However since they are not permutations, the security proofs that apply to block ciphers may not apply to hash functions when used in these modes.
<...>
For completeness' sake: most block cipher mode proofs assume the cipher is PRP and thus PRF up to the birthday bound. Hash functions are not PRP and not required to be PRF either though the ones we use seem to be.

Насколько помню, подобный вопрос ранее обсуждался и на нашем сайте, и unknown приводил такие же аргументы: использование хэш-функций в подобных конструкциях может делать их уязвимыми к таким классам атак, которые неприменимы к шифрам.

Доброе утро!

Любовь к велосипедам расширяет познания если к этому подходить с умом и очень аккуратно, в особенности в крипте.

Вообще чем проще тем меньше ошибок, в криптографии многое отталкивается от сложности, простой пример:

35 + 87 + 91 + 17 + 63 + 72 = 365

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

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

Пример:

Берем хеш md5 от слова secret
Далее данный хеш ксорим с текстом my secret messag

Получаем следующее:
5ebe2294ecd0e0f08eab7690d2a6ee69 – наша гамма из хеша
33c702e789b39295fa8b1bf5a1d58f0e – наш зашифрованный текст хеш xor открытый текст.

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

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

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

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

К примеру в том же AES зная закрытый текст и открытый невозможно вычислить ключ, в этом и фишка.

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

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

1. Это сжать выходной хеш, и для каждого байта генерировать свой независимый хеш с секретом. Например:

5ebe2294ecd0e0f08eab7690d2a6ee69 – хеш md5 от secret
6c – сжали наш выходной хеш

Сжимаем так: 5e + be + 22 + ... = 6c

При этом принимаем каждое значение за unsigned char, таким образом мы получаем переполнение, например unsigned char 254 + unsigned char 186 = 184

Зачем мы это делаем? Ну первое, наша гамма же должна иметь равномерное распределение, второе, хеш функция устойчива к коллизиям, мы же намеренно сделали коллизию, при этом сохранив хорошее равномерное распределение, я гонял гигабайты сжатых таким методом sha512 в diehardere и нист тестах и все отлично (хотя это не говорит о стойкости вообще никак). Теперь вспомним, о том, о чем я говорил в начале про 35 + 87 + 91 + 17 + 63 + 72 = 365 именно этого мы и добились.

Второе как нам получать ключ? А вот ключ маленький у нас не получится, потому, что для каждого хеша нам нужно отдавать по 16+ случайных байт (128 бит ключ), а лучше истинно случайных.

Теперь подсчитаем, наше секретное сообщение my secret messag 16 байт, 16 * 16 = 256 длина нашего ключа для данного сообщения, разбитая на 16 хешей. Сюда же можно добавить nonce + 16 байт, и для каждой итерации хеширования просто дописываем наш nonce.

Таким образом мы получаем, что каждый байт не зависит от другого байта (кроме nonce), единственная проблема которая у нас осталась, это то, что противник может знать, какие байты и где потому, что мы не используем рассеивание и перемешивание, но за счет того, что каждый байт у нас не зависит от предыдущего, противнику это не дает ровным счетом ничего, получив даже первые несколько байт гаммы он не сможет её дополнить, так как мы не используем сырой хеш, вместо этого мы сделали сжатие, которое восстановить обратно не представляется возможности, потому, что сколько хешей и с какими значениями при сжатии нам дадут 6с? Примерно 256 хешей простого инкремента i, точно даст 6с. Еще один нюанс все эти 16 ключей должны быть уникальными, иначе на выходе мы получим ту же гамму, хотя мы её и так будем получать за счет коллизии, но это немного другое. Вероятность конечно мала при 128 битах, но всеж.

В любом случае данная схема имеет простейшие минусы, такие как скорость работы, это очень медленно. Еще не ясно насколько надежна схема сжатия при получении равномерного распределения, хотя она и проходит тесты на ура, но я более чем уверен, что при ручной проверке методами которых я не знаю, можно найти закономерности, можно выстроить теорию, когда мы сжимаем хеш в один байт и изучаем гигабайты выхода, можно выявить некоторую корреляцию равномерности распределения, в виде отпечатка, а когда мы наложим гамму на открытый текст, корреляция изменится от нормальной, и это может служить утечкой гаммы. Это же справедливо и для обычного хеша который мы ксорим с открытым текстом, нормальное распределение изменится, кстати вот почему нельзя ксорить хеши между собой, это уменьшает их общую стойкость. Так, что схема 35 + 87 + 91 + 17 + 63 + 72 = 365 теоретически может быть взломана, хотя и кажется, что да как такое может быть возможно?

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

У пользователя stargrave проблемы с добавлением комментария. Копирую его сообщение.

Хотел заметить что использование хэша как PRF для создания потока с которым можно было бы XORить данные шифруя их не нова.
Например в описании одного из финалистов SHA3, хэш-функции Skein (http://www.skein-hash.info/sit.....t/files/skein1.3.pdf) подобный use-case описан в самой PDF-ке хэша. Учитывая что этот же хэш можно использовать ещё и для аутентификации сообщений, мы можем получить полноценный AEAD используя только один криптографический примитив: хэш.
Это полезно там, где нужно экономить ресурсы. Однако в общем случае так не делают из-за скорости.