Topic: Доказательство P=NP: пострадает ли криптоалг& (Read 2902 times)

Ну, собственно, приведенное доказательство только указывает на существование коллизий, но не дает ответа, как, кроме брутфорса, их находить. Нахождение коллизий представляет серьезную сложность даже для устаревших алгоритмов, вышедших (md4) или постепенно выходящих (md5) из употребления.


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

Пример: разработчик программы, которому вы доверяете, выложил архив с пакетом на множество зеркал для разгрузки своего сайта. Одно или несколько из этих зеркал могут быть мошенническими, т.е. их владельцы стремятся добавить внутрь программы свой вредоносный код. Разработчик на своем сайте кроме ссылок на зеркала опубликовал md5-хэш архива (напомню, на сегодняшний день md5 уже считается ненадежным). Вы качаете архив и проверяете соответствие его md5 значению, выложенному на сайте, и если они совпадают - считаете файл надежным.

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

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

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

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

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

Ммм, ясно. Но ведь мало найти коллизию, надо ещё определить какого она рода и насколько опасна?

А если сообщения с одинаковым хэшем вообще никак аналитически не стыкуются, то это будет значить, что коллизия безопасна, так? По идее, именно такое тогда должно быть доказательство соответствия "чёрному ящику". Который может зажевать любое число бит, но выплюнет только n.

Фишка в том, что ограничена длина хэша. Предположим, мы используем keccak - ну или абсолютно любой другой алгоритм с длиной хэша n бит. В этом случае максимально возможное количество значений хэша будет 2ⁿ. Возьмем 2ⁿ+1 сообщений и вычислим хэши для каждого из них. Очевидно, что поскольку количество сообщений больше, чем количество возможных значений хэша, то хотя бы у двух сообщений хэши окажутся одинаковыми - вот вам и коллизия.

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

М? Я читал, что было доказано математически, что Keccak работает точно так же, как искомый "чёрный ящик". Была статья на Хабре. В таком случае коллизий существовать не должно по идее, или их нахождение ничего не даст (я не криптограф, не кидайтесь тапками).

Статейка не одна, их много - разной степени желтизны. Однако из них тоже можно сделать несколько выводов... Я на сегодняшний день ситуацию таковой вижу: некий профессор, доктор физико-математических наук, заведующий кафедрой в достаточно серьезном вузе, обладатель кучи почетных званий и т.п. (http://www.mathnet.ru/php/person.phtml?option_lang=rus&personid=30278, http://www.susu.ac.ru:8001/ru/f/fakultet_vychislitelno_matematiki_i_informatiki/kafedry/emmis/professorsko-prepodavatelski_sostav/panjukov) считает, что решил одну из "задач тысячелетия", над которой работал более 30 лет. Сие решение он готовит к публикации и надеется, что оно окажется верным. Поскольку проблема (как, по всей видимости, и ее доказательство) весьма сложна и ранее было предложено много доказательств (и опровержений), оказавшихся ошибочными, вероятнее всего и на этот раз где-нибудь будет найдена ошибка, однако ввиду серьезности заявления и биографии заявителя это решение должно быть рассмотрено самым серьезным образом.

Что оно гарантированно неверное я ни где не говорил. Я лишь говорю, что статейка несомненно желтая, и именно по этой причине всерьёз воспринимать её не стоит.

Если вы обратите внимание, они по крайней мере ссылаются на NYT, хотя статейке более 10 лет уже. А тут чистейшая желтизна.

Вообще-то я специально сделал оговорку, давая понять, что у меня нет точной и абсолютно достоверной информации на этот счет. Сейчас все-таки загуглил, ситуация действительно весьма неоднозначная... С одной стороны утверждается, что работа не опубликована, с другой - сказано, что "Так, свое доказательство Панюков представил на международной конференции в Черногории, а также в Институте математики и механики УрО РАН и в журнале «Автоматика и механика»". С другой стороны навскидку я не нашел такой журнал, однако существует журнал "Автоматика и телемеханика", в котором этот самый Панюков многократно публиковался, правда, требуемой статьи я там не нашел.


А теперь - вот, получите: http://grani.ru/Society/Science/m.29288.html

Начнем с заголовка: "Российский математик Григорий Перельман утверждает, что доказал гипотезу Пуанкаре" - таки российский? Это же совершенно неважно!

Несколько цитат:


А вот википедия утверждает, что


Уже достаточно желто для вас? Значит, доказательство Перельмана - гарантированный фейк?

Далее по тексту:


Найдите-ка пять отличий от нынешней ситуации! Я не смог.

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

С чего вы взяли?

Вот на таких читателях и держится вся желтая пресса.
Нет ссылки ни на какую научную публикацию, даже на arXiv, только бла-бла-бла и ко-ко-ко

Ну и как аргумент скопипастю коммент с хабра

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

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


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

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

Разве? Вроде это лишь означает, что поиск коллизий нельзя будет вести в полиномиальное время, но не запретит существование коллизий. Тем более в некоторых устаревших алгоритмах коллизии были найдены, вопрос только в том достаточно ли сложно найти коллизии в новых алгоритмах, чтобы пользоваться ими. Пока ответ: да, это сложно (=дорого).

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

Непонятно - каким образом затворничество Перельмана доказывает невозможность доказательства титульной задачи?

Наш дорогой питерец Григорий Перельман восемь лет ломал Пуанкаре головой даже малость поехал, затворником стал, а Вы - "доказательство нашли" - если это правда, то этим самым доказательством подтверждается теория струн!

Вобщем расходимся мужики - новость желтая, битку новых дыр не добавилось пока.

Гм, а какова методика расчета этой вероятности ?


Ммм я же писал - если утверждение P=NP  верное, то это означает потенциальную возможность взлома, но не дает его алгоритмов.


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

Ну, во-первых, с вероятностью семь девяток доказательство очередной фейк, а во-вторых, AFAIR, из утверждения P=NP вовсе не следует автоматически, что вся криптография рухнет, степень полинома будет иметь значение. Так же как из утверждения P≠NP не следует, что существующая криптография абсолютно надёжна - необходимо доказать существование односторонних функций

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

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

Биткойн адрес это не пубкей, он еще хэширован несколько раз