Streebog GOST R 34.11-2012 backdoor

На вашей вероятной базе данных как быстро отрабатывает поиск по 2^512 хешам? Какой объём у БД ?

А то на моём ноутбуке на септилионной секунде транзакция откатывается по таймауту ;)

Зато при наличии двух хешей подобрать ИСХОДНОЕ сообщение - легче.

Оценку можешь привести?

Чего там оценивать-то :)) P(H1) - вероятность подбора исходного сообщения для хеша 1, P(H2) - вероятность подбора исходного сообщения для хеша 1

Значит вероятность подбора исходного сообщения при наличии двух хешей равна максимальной вероятности из P(H1) или P(H2) (ну или минимальной сложности).

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

Т.к. штука эта «очевидная», то дальше уже только в кванторах расписывать исходное условие и доказывать утверждение.

Ну или вот так: если хочешь усложнить поис прообраза по хешу (как в твоём исходном сообщении), то делай так: 1) перед «сообщением» добавляй «соль» - случайный набор бит длиной в 512 штук 2) сохраняй хеш от «солённого» сообщения 3) рядом с хеш-значением сохраняй сгенерированную соль

Если говорить о паролях, то их один хрен перебрать будет быстрее САМИ пароли, чем взламывать этот хеш (ибо по вероятностной оценке поиска исходного сообщения взлом этого хеша потребует полного перебора «пароля из буквцифрспецисимволов» длиной в 128 штук, а мало у кого используется НАСТОЛЬКО длинный пароль).

Исходная задача-то какая? Именно она в первую очередь определяет применимость алгоритмов и подходов.

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

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

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

Ну представьте себе, что «вы 10 лет назад» решили хранить хеши паролей сразу в MD5 и SHA-256. Буду ли «условный я» долго думать, по какому из хешей искать исходное сообщение?

Я буду выбирать тот алгоритм, который на момент старта брутфорса будет проще в подборе и анализе.

Вы переобулись в полёте. Я отвечал на чем два лучше одного, а вы теперь рассказываете, что вы заранее знаете, что будем мучить более простой, совершенно не тратя ресурсы на более сложный. Это другой ответ — не приведение вероятности к одному, а просто отбрасыванию другого.

Ну представьте себе, что «вы 10 лет назад» решили хранить хеши

Разве это чем-то поможет, если этого «пароля» с учётом соли там не будет?

Буду ли «условный я» долго думать, по какому из хешей искать исходное сообщение?

Самое смешное, что чем сильнее алгоритм, тем большая вероятность, что его засунут в криптоускоритель, начиная с унутри в процессор и кончая фермами биткойна. :)

Вы переобулись в полёте. Я отвечал на чем два лучше одного, а вы теперь рассказываете, что вы заранее знаете, что будем мучить более простой, совершенно не тратя ресурсы на более сложный. Это другой ответ — не приведение вероятности к одному, а просто отбрасыванию другого.

Дело в том, что два алгоритма «лучше» только в том случае, если рассматривать наличие коллизий. И в этом они ДЕЙСТВИТЕЛЬНО лучше.

А с точки зрения ДРУГОГО типа атаки - поиск исходного сообщения - «два хеша» ХУЖЕ (В ТЕОРИИ, как вы верно заметили).

Самое смешное, что чем сильнее алгоритм, тем большая вероятность, что его засунут в криптоускоритель, начиная с унутри в процессор и кончая фермами биткойна. :)

Согласен полностью :). Криптостойкость определяется не алгоритмом, а температурой паяльника и утюга. Давным давно самым слабым звеном в защите информации стал человек с паролем 123456.

А с точки зрения ДРУГОГО типа атаки - поиск исходного сообщения

Ну было б странно разговаривать о применении двух алгоритмов, если бы устраивала любая коллизия любого алгоритма.

Ну и всё.

Ты намешал котлеты с мухами

Т.к. штука эта «очевидная», то дальше уже только в кванторах расписывать исходное условие и доказывать утверждение.

Доказывай. Хочется хоть каких-то чисел.

Исходная задача-то какая?

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

Дело в том, что два алгоритма «лучше» только в том случае, если рассматривать наличие коллизий. И в этом они ДЕЙСТВИТЕЛЬНО лучше.

Как бы про другое и не было разговора. Потом пришли теоретики и начали копипастить методички.

Доказывай.

Хренасе. Вы забываетесь.

Хочется хоть каких-то чисел.

3 и 8 подойдут?

Если серьезно - я в первом своём сообщении привел РЕАЛЬНЫЕ цифры по оценке криптостойкости, взятые из статьи «о взломе стрибога».

«подбор исходного сообщения» при наличии двух хешей - я выше описал, почему в таком случае «подбор» «проще».

Хренасе. Вы забываетесь.

Вы заболтались

3 и 8 подойдут?

Откуда вы их взяли?

Если серьезно - я в первом своём сообщении привел РЕАЛЬНЫЕ цифры по оценке криптостойкости, взятые из статьи «о взломе стрибога».

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

«подбор исходного сообщения» при наличии двух хешей - я выше описал, почему в таком случае «подбор» «проще».

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

ты очень бодро рассказываешь про вероятности. но как насчет алгоритма?

Давным давно самым слабым звеном в защите информации стал человек с паролем 123456.

Это понятно, что методы СИ - самые эффективные.

Исходная задача-то какая? Именно она в первую очередь определяет применимость алгоритмов и подходов.

А смысл раскрывать задачу, это облегчит применение СИ.

Вообще, как я вижу задачу, именно добавление соли + использование байт-кода VM вместо ключа при фиксированном алгоритме - самый эффективный способ для стеганографии.

Мы постепенно приходим к децентрализованному обществу, на основе технократии. Плюс, с эффективным восстановлением восполнимых природных ресурсов, http://kvedomosti.ru/news/minselxoz-razrabotal-proekt-gosprogrammy-kompleksno... Как бы, проблема непростая. Работаем с ребятами с разных сторон. Кто-то алгоритмами занят, кто-то продвижением законов, кто-то другими вопросами.

Давайте поставим несколько точек над i и по возможности завершим.
Моим утверждением было то, что для двух хэш-функций найти одновременно коллизию вероятность ниже, чем для каждой по отдельности. Чего-либо другого я не утверждал.
Пусть у нас есть некое сообщение и некое множество входных наборов данных E, предположим с количеством элементов 10^20.
Сообщение для простоты содержится в Е.
Для данного множества Е у первой хэш-функции получается множество коллизий X с сообщением, например 10^5.
У второй функции для множества Е получается множество Y с 10^4 элементов.
Понятно, что это наковыряно из носа в силу произвола, но к конечному выводу это не имеет отношения.
Коллизии у двух функций будут составлять множество Z равное пересечению множеств X и Y. Сверху количество элементов Z ограничено количеством минимального множества из X и Y, то есть 10^4. А снизу, как ни странно это 1.
То есть вероятность ниже и в среднем нужно найти 10 коллизий в X и одну в Y. Что несколько отличается от необходимого одного в случае единственной функции.
Но, это очевидно и видимо уже не вызывает интереса к спору, ведь выиграть в олимпиаде здесь не получится.

Рассмотрим такой реваншистский манёвр, как якобы восстановление исходного сообщения по результатам коллизий в двух функциях.
Во первых не восстановления, а подбора.
Понятно, что по коллизии одной функции в принципе невозможно утверждать, что данное входное сообщение является искомым. Нужно знать что-то ещё для.
По двум и более функциям это возможно, но есть нюансы.
Итак, у нас есть две функции. Обратимся к предыдущему примеру с Y и X. Самым плохим вариантом будет отсутствие коллизий в Y — тогда наверняка, но этот граничный случай и так соответствует варианту полного перебора, поэтому не является интересным, получаем 1 в любом случае. Второй граничный случай это те же самые 10^4 вариантов, из которых опять надо отбирать по какому-либо критерию... Упс... А про вероятность уже написано выше.

но как насчет алгоритма?

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

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

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

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

не думаю что такие алгоритмы, даже если они есть, доступны кому-то кроме спецслужб.

чисто технически, подбор возможен. для GF(256) например можно использовать такой способ:

Используется свойство операций с матрицами в полях GF, и как частный случай F2: все операции которые есть в обычном матане - применимы включая получение ОБРАТНОЙ МАТРИЦЫ. что дает нам возможность разматывать шифр.

(да, если это допилить, хана HTTPS. ибо в HTTPS де-факто шифротекст известен из-за стандартных заголовков HTTP которые в сумме длиннее 16 байт).

пусть каждому байту B=n соответствует жирнобайт длиной ЖB(n) 256 бит = 2^B. Тогда любое нелинейное преобразование описывается матрицей 256х256 бит. Далее, каждому жирнобайту мы сопоставляем жирноматрицу ЖМ(n) такую, что для любого B: B(n)*ЖМ(m)=B(n^m).

В принципе, этого матана достаточно для размотки AES, ГОСТа и любых шифров, которые используют 8битные операнды либо сводимы к таким операциям ибо он покрывает 100% используемых ими операций. Практическая проблема в том, что в полях обратной матрицы получаются невычисленные полиномы, которые съедают всю память. Т.е. когда софт разматывает матрицы обратно, то на каждой итерации происходит получение полиномов вход которых зависит от данных прошлой стадии, а там тоже полиномы.

Но если эту проблему решить, то мы получим систему уравнений, которая даст своим решением биты для инициализации расписания ключей AES например(исходя из того, что в исходных данных где-либо есть известная строка напр из HTTP заголовков

Сколько для этого примерно нужно памяти?

Я даже оценить не могу, то есть наверно могу но обламывась т.к. работа семья херня и т.д.

Я пока не смог пожать потребление, при том, что уже использую 2байта на переменную - ниже не уменьшить, т.к. между стадиями передают 32байта*8бит = 256бит, плюс 1 бит для передачи единички, плюс служебные данные. И надо понимать, что каждые эти 2 байта на каждой итерации превращаются в несколько раз по 2 байта. И так 10 раудов. В лоб оценка вроде (2*256x256)^10 = 128Mb*K где K поправочный коцифиент ~10-16. но то ли из жопы то ли глючу.

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

тьфу. допился.

(2*256x256)^10 = дохера это.

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

ckotinko, ты?

разное может быть. но таки почему вы спрашиваете?

Потому что он рассказывал, что будет aes колоть.

Я это как пример привел. Я не говорю что описаный способ рабочий. нет, это пока теория, причем очень теоретическая. я её привел как пример того, как вроде-бы можно линеаризовать нелинейные S-boxи в AES.

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

К слову, вот одно из последтвий работы Патарана: https://cyberleninka.ru/article/n/analiz-stoykosti-blochnyh-algoritmov-shifro...

«Обычные»-то люди этого не смогут. Поэтому два разных хэша для них - это «всё»,конец игры.

Я бы предложил еще и сперва «подмешивать» рандомные биты причем:

Их надо вставлять в отношении 1 к 1. на каждые 64бита данных надо подсыпать 64 рандома.

Положения рандомных битов в N-ом 64битном слове должны зависеть от какой-нибудь функции F(N, secret_key).

И всё это поверх шифруется с ключом secret_key2. Расшифровать рандом - это задача не решаемая. А проверка делается просто - расшифровываем, удаляем рандомные биты, проверяем что на выходе не мусор.

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

Можно уточнить: «вероятность найти коллизию» ЗНАЯ значения хешей (ну то есть когда мы хотим подобрать первоначальное сообщение каким-то способом, чтобы значения хешей этого сообщения совпали с известными), или же «вероятность того, что нам на наших случайных данных попадутся два разных сообщения, хеши которых будут совпадать» ?

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

Хеши короткие. Вероятно все хеши повторно хешированные уже посчитаны и записаны, и скорость их расшифровки равна скорости поискового запроса к БД.

Так не забывайте солить же. Для каждого юзера разной солью.