md5 -- чо опять не так?

Любые обсуждения, не нарушающие правил форума.

Модератор: Модераторы

Re: md5 -- чо опять не так?

Сообщение olegy123 » 07.03.2018 08:09:13

azsx писал(а):Правда мои слова отвергает биткоин и торрент, но в теории я прав. Верно?

у биткойна и торрента цель другая - глобальная унификация и защита информации от подбора.

я бы эту задачу решил бы так: id (integer в 4 байта) crc32 + дополнительная точность (размер или md5 или sha256/sha512..sha2048).
что это даст - скорость выборки, даже среди миллиарда поиск будет быстрым на слабых компьютерах, вся информация может быть хранится в памяти.. в других случаях, каждый поиск уже потребует дополнительных вычислений (в два или более прохода) - загрузки/выгрузки и т.п., Есть таблицы с какими видами данных шустро работает CPU - так вот более приемлемо тип integer/int64, single/double - за единицу времени они больше вычислений сделают чем с другими видами данных. У них электронная схема под это заточена.
olegy123
энтузиаст
 
Сообщения: 934
Зарегистрирован: 25.02.2016 12:10:20

Re: md5 -- чо опять не так?

Сообщение vitaly_l » 07.03.2018 10:36:03

Mirage писал(а):Интересно, что тут может дать длина в байтах? Вероятности не умеем сравнивать вообще? Ну помножишь ты вероятность совпадения длины в байтах на 2 в минус 128-ой. Получишь значение малоотличимое от 2 в минус 128-ой.
А нулевую вероятность совпадения и побайтовое сравнение не даст. Задание - подумать почему.

Вы меня немножечко неправильно интерпретировали. Я ничего не умножаю и не перемножаю. Я лишь дополнил md5 дополнительным индексом sha, но при этом прекрасно понимаю, что даже при таком индексе возможны совпадения при каких-то очень громадных вариациях. Например если для md5 взять 256 битное число, то одинаковых md5 у цикла итераций этого числа (от 0 до max) - будет очень много. Если взять 512 битное число и прогнать его (от 0 до max) через sha 256, то тоже будет много одинаковых sha при разных числах в итерациях, но при этом числа будут отличаться по длине, которую в том числе можно взять в байтах, но не все будут отличаться по длине. Соответственно, именно индекс из трёх значений - является уникальным, т.к. разные алгоритмы хэширования дадут разные ответы в тех случаях где раньше были совпадения.

Как пример берём два слова: "умный" и "дурак". Слова совершенно разные. У них совершенно разные md5 и sha. Но при совмещении - означают они одно и тоже: "дурак умный" и "умный дурак". Теперь попытаемся сделать из умного дурака, а из дурака умного. Как это сделать? Я бы мог дать софистическое задание: "подумай почему"... Но я лучше дам другое задание, позволяющее сделать дурака умным, а умного дураком. Выполнять это задание на PC "нельзя" т.к. скорее всего не хватит памяти и вылетит БСОДА, но в уме Вы можете посчитать.

Код: Выделить всё
var
durak:string;
umniy:string;
sd,su :string;
begin
sd := 'дурак';
su := 'умный';
durak := md5(sd);
umniy := md5(su);

while durak <> umniy do begin
   sd := sd +' '; // добавляется пробел
   durak := md5(sd);
end;

sd := 'дурак';
su := 'умный';
durak := md5(sd);
umniy := md5(su);
while umniy <> durak  do begin
   su := su +' '; // добавляется пробел
   umniy := md5(su);
end;

end;


Суть вышеприведённого кода в том что, рано или поздно (при каких-то очень громадных итерациях через несколько дней или лет или тысячелетий) хэши: durak и umniy - совпадут и циклы остановятся, несмотря на, то, что я всего-лишь прибавлял пробелы, в каждой итерации. Так вот, когда хешируются тексты, то предугадать 100% отсутствие совпадений при md5 - нельзя. У sha больше устойчивость, но тоже будут совпадения, при хэше текстов. Например пароли, хэшированные md5 - довольно часто бывают одинаковые и поэтому требуют УНИКАЛЬНЫЙ логин. Посмотрите в поиске, есть примеры.

Соответственно, только тройной индекс можно считать уникальным индексом (и предполагаю что он устойчивее чем sha2048):
    1) md5
    2) sha
    3) указываете длину в байтах (или в символах).
При этом я не перемножаю индексы, а сохраняю sha и md5 и длину, как получено из функции. Я просто сильно повысил устойчивость индекса. Программистам - этот индекс лучше не использовать, т.к. я не математик и не даю 100% гарантию, что индекс устойчивее чем sha2048 (но мне кажется, что он получается устойчивее чем sha2048). Проверить может только математик. :cry:

PS: Между прочим (раз про балалайку нельзя "ныть"), то сообщаю, что и гитару тоже нельзя настраивать камертоном, т.к. это может нарушить права соседей (согласно решению суда, точнее согласно мошеннической экспертизе целого Департамента...). При этом гибель этой планеты неизбежна и ни у кого (на сегодняшний день) - нет шансов на выживание. И это основные проблемы всего цивилизованного Мира. Теперь меня попросят забанить с моей гитарой :wink:

Для тех кто не знает как выглядит Гитара (а это международный музыкальный инструмент), на картинке виден кусок гитары, с которой я, кстати, вполне успешно выступал в ДК МАИ и не только. А перед ней лежит, тот самый ужасный и коварный камертон, который по решению суда, основанного на Заведомо ложной экспертизе ст.307.УКРФ (которую отказались признать заведомо ложной экспертизой), так вот камертон, оказывается может нарушить права соседей. И благодаря этой мошеннической экспертизе - нечестно распределяют Гос. бюджет. И нет сомнения, что действия Департамента были преднамеренными, т.к. был суд и даже в суде, они настаивали, что камертон может нарушить права соседей. И я пишу всё это, и понимаю, что показывая всё это беззаконие в открытом доступе, я сильно рискую своей жизнью. Потому что: МВД и прокуратура, по какой-то непонятной причине, не захотели расследовать Заведомо ложную экспертизу. Это реальный квест, второй уровень: Камертон и Гитара... И гибель этой планеты неизбежна...

.
У вас нет необходимых прав для просмотра вложений в этом сообщении.
Последний раз редактировалось vitaly_l 07.03.2018 15:36:29, всего редактировалось 1 раз.
Аватара пользователя
vitaly_l
долгожитель
 
Сообщения: 3333
Зарегистрирован: 31.01.2012 16:41:41

Re: md5 -- чо опять не так?

Сообщение runewalsh » 07.03.2018 15:36:04

vitaly_l, ты не понимаешь следующих вещей:

1) масштаб вероятностей
>при каких-то очень громадных итерациях через несколько дней или лет или тысячелетий
Даже если взять более слабую версию — совпадение двух любых хэшей (парадокс дней рождения), ≈1% вероятность совпадения 128-битного хэша при миллионе итераций в секунду ты получишь через √(2^128) × 0.01 ÷ 1000000 ÷ 86400 ÷ 365 = 5000 лет. Каждые 2 бита умножают эту оценку ещё на 2.
(В твоём случае с поиском совпадений конкретного хэша из формулы убирается квадратный корень и оценка удваивается каждым битом.)

2) Сцепив два хэша, один M-битный, другой N-битный, ты по сути строишь такой же, только (M+N)-битный. Скажем, MD5 (128 бит) + SHA-256 (256 бит) эквивалентно SHA-384. Сцепив это с K-битной длиной, ты типа как получаешь (M+N+K)-битный, если не учитывать того, что длина плохо распределена, т. е. неравномерно, т. е. её энтропия, т. е. «реальная битность» для целей хэширования, будет сильно меньше K (условно K÷2).
Аватара пользователя
runewalsh
постоялец
 
Сообщения: 403
Зарегистрирован: 27.04.2010 00:15:25

Re: md5 -- чо опять не так?

Сообщение vitaly_l » 07.03.2018 15:43:47

runewalsh писал(а):1) масштаб вероятностей
>при каких-то очень громадных итерациях через несколько дней или лет или тысячелетий
Даже если взять более слабую версию — совпадение двух любых хэшей (парадокс дней рождения), ≈0,1% вероятность совпадения 128-битного хэша при миллиарде итераций в секунду ты получишь через √(2^128) × 0.001 ÷ 86400 ÷ 365 = полмиллиарда лет. Каждые 2 бита умножают эту оценку ещё на 2.
(В твоём случае с поиском совпадений конкретного хэша из формулы убирается квадратный корень и оценка удваивается каждым битом.)

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

runewalsh писал(а):Сцепив два хэша, один M-битный, другой N-битный, ты по сути строишь такой же, только (M+N)-битный. Скажем, MD5 (128 бит) + SHA-256 (256 бит) эквивалентно SHA-384.

Нет. Я беру два разных алгоритма хэширования. И здесь секрет другой. Например, если для теста НЕЧТО:
if sha(testA) = sha(testB) then ... сработает и будет true. То точно такие же при if ((md5(testA) = md5(testB)) AND (sha(testA) = sha(testB) ))then ... вернут false. В этом секрет такого теста, т.к. разные алгоритмы и разные коды. Плюс добавляется длинна измеряемого текста, как третий параметр ограничивающий совпадения. Нельзя считать вероятность в прямом виде, т.к. когда вводишь текст то уже начинаешь не с 0 позиции вероятности, а с xxx-итой,
Аватара пользователя
vitaly_l
долгожитель
 
Сообщения: 3333
Зарегистрирован: 31.01.2012 16:41:41

Re: md5 -- чо опять не так?

Сообщение zub » 07.03.2018 15:56:39

>>Я просто сильно повысил устойчивость индекса.
Я просто думаю что я сильно повысил устойчивость индекса. Fixed

Добавлено спустя 2 минуты 19 секунд:
Также как думаешь что ничего не перемножал)))
zub
долгожитель
 
Сообщения: 2411
Зарегистрирован: 14.11.2005 23:51:26

Re: md5 -- чо опять не так?

Сообщение runewalsh » 07.03.2018 15:59:30

Я там исправил, со 128 битами не полмиллиарда всё-таки.
>Нет. Я беру два разных алгоритма хэширования.
Ты построил свой 384-битный хэш, и для него найдётся такое «нечто» с той же трудоёмкостью, что для любого другого «хорошего» 384-битного хэша.

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

С учётом того, что ты потенциально введёшь пользователя в заблуждение, что раз у тебя хэш длины 128 (MD5) + 32 (длина uint32) = 160, то для оценки коллизий можно брать 2^160 (вместо реальных 2^(128+чуть-чуть)), это хуже, чем просто не добавлять длину.
Аватара пользователя
runewalsh
постоялец
 
Сообщения: 403
Зарегистрирован: 27.04.2010 00:15:25

Re: md5 -- чо опять не так?

Сообщение vitaly_l » 07.03.2018 16:05:25

zub писал(а):Я просто думаю что я сильно повысил устойчивость индекса

Я этого и не отрицаю, я лишь говорю, проверить может только очень крутой математик с очень большим PC, т.к. runewalsh привёл очень большое время пересчёта NNN возможных вариантов, которые не являются конечным числом возможных, т.к. вариантов бесконечно много.
runewalsh писал(а):Ты построил свой 384-битный хэш, и для него найдётся такое «нечто» с той же трудоёмкостью, что для любого другого «хорошего» 384-битного хэша.

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

Добавлено спустя 21 минуту:
Вот например, можно так показать наглядно:
хэш md5(xxxxxxxxxxxxxxxxx) совпадёт с хэшем md5(xxxxxxxxxxxxxxxxxyyyyyyyyyyyyyyyyyyyyy) и таких итераций совпадения бесконечно много md5(xxxxxxxxxxxxxxxxxyyyyyyyyyyyyyyyyyyyyyzzzzzzzzzzzzzzzzzzzzzzzzz) и т.д. Но при этом, ограничение по длине, сразу отметёт такие совпадения и индекс получается 100% более уникальным. Но при этом, есть такие md5, которые совпадают по длине и возвращают одинаковый хэш. И вот тут, как раз срабатывает проверка на sha... Соответственно индекс получается 100% более устойчивым чем sha2048 (практически уверен, но всё ещё предполагаю, т.к. доказательство этого - задача для математика с уровнем Перельмана).

Добавлено спустя 55 минут 55 секунд:
В общем глубоко задумался и пришёл к выводу, что это получился именно уникальный и БЕСКОНЕЧНЫЙ индекс, т.к. L = длинна хэшируемого string слова и она стремиться в бесконечность, т.к. не имеет ограничений как у sha и md5. А совпадение md5(somestring) и sha(somestring), возможны только при одинаковой L, которая стремиться в бесконечность. Соответственно, это действительно получился уникальный индекс, который вместе с L тоже стремиться в бесконечность. Соответственно имеет бесконечное число уникальных значений, в которых поочерёдно будут повторяться хэши для md5(somestring) и sha(somestring) и вероятность их единовременного совпадения возможно где-то при супер громадных значениях, которые пока ещё не имеют математических названий, т.к. это потребуется слишком громадная длинна слова L, при длине L, которого совпадут хэши md5(somestring) и sha(somestring). И эти числа намного больше чем sha2048 или sha4096, sha8192 итд (с)
Аватара пользователя
vitaly_l
долгожитель
 
Сообщения: 3333
Зарегистрирован: 31.01.2012 16:41:41

Re: md5 -- чо опять не так?

Сообщение runewalsh » 07.03.2018 17:52:16

Ко всем возможным 128-битовым сообщениям невозможно добавить ещё одно так, чтобы его MD5 не совпало с MD5 одного из этих сообщений (т. к. всех возможных значений MD5 столько же, сколько сообщений).
Ко всем возможным 384-битовым сообщениям невозможно добавить ещё одно так, чтобы не получить коллизию одновременно MD5 и SHA-256.
Среди всех 385-битовых сообщений будет минимум 2^384 пар, у которых совпадают одновременно MD5 и SHA-256.
Аватара пользователя
runewalsh
постоялец
 
Сообщения: 403
Зарегистрирован: 27.04.2010 00:15:25

Re: md5 -- чо опять не так?

Сообщение vitaly_l » 07.03.2018 17:58:02

runewalsh писал(а):Ко всем возможным 128-битовым сообщениям невозможно добавить ещё одно так, чтобы его MD5 не совпало с MD5 одного из этих сообщений (т. к. всех возможных значений MD5 столько же, сколько сообщений).
Ко всем возможным 384-битовым сообщениям невозможно добавить ещё одно так, чтобы не получить коллизию одновременно MD5 и SHA-256.
Среди всех 385-битовых сообщений будет минимум 2^384 пар, у которых совпадают одновременно MD5 и SHA-256.

Это всё именно так, но сюда добавляется длина слова L, которая стремиться в бесконечность. Соответственно получается бесконечное число итераций и нет совпадений, т.к. для каждой 2^384 пар существует только одна длина L, которая бесконечно увеличивается. Это бесконечная спираль чисел. Это всё равно что задать бесконечно inc(i); где длина i не ограничена. Но при этом, это именно хэш!!! Хэш который может быть уникальным индексом!
Последний раз редактировалось vitaly_l 07.03.2018 18:00:53, всего редактировалось 1 раз.
Аватара пользователя
vitaly_l
долгожитель
 
Сообщения: 3333
Зарегистрирован: 31.01.2012 16:41:41

Re: md5 -- чо опять не так?

Сообщение runewalsh » 07.03.2018 18:00:29

Каждое из этих сообщений длины 385, не?
Аватара пользователя
runewalsh
постоялец
 
Сообщения: 403
Зарегистрирован: 27.04.2010 00:15:25

Re: md5 -- чо опять не так?

Сообщение vitaly_l » 07.03.2018 18:02:30

runewalsh писал(а):Каждое из этих сообщений длины 385, не?

Это как десятичная система, только "десятка" получается длинной 2^384 пар. И каждый раз она увеличивается за счёт L.
Аватара пользователя
vitaly_l
долгожитель
 
Сообщения: 3333
Зарегистрирован: 31.01.2012 16:41:41

Re: md5 -- чо опять не так?

Сообщение runewalsh » 07.03.2018 18:09:25

Я перестал тебя понимать. Ну смотри, если ты будешь отсчитывать L по принципу
aaaa
aaab
aaac
...
aaba
...
zzzz
aaaaa
и так досчитать до своего сообщения, то тогда сам номер, т. е. L, и будет сообщением (иметь длину порядка длины сообщения и крякать как сообщение).
Аватара пользователя
runewalsh
постоялец
 
Сообщения: 403
Зарегистрирован: 27.04.2010 00:15:25

Re: md5 -- чо опять не так?

Сообщение vitaly_l » 07.03.2018 18:14:13

runewalsh писал(а):Я перестал тебя понимать.

Вот, первая колонка это L = длинна слова.
первая колонка L | вторая sha * md5 вариантов, это равно 2^384 пар.
1 | 2^384 пар
2 | 2^384 пар
3 | 2^384 пар
4 | 2^384 пар
6 | 2^384 пар
7 | 2^384 пар
итд. inc(L)| 2^384 пар
итд. 2^384 | 2^384 пар
итд. 2^512 | 2^384 пар
итд. 2^1024| 2^384 пар
И везде индекс 100% не совпадает, т.к. на каждом витке меняется длина L. И эта спираль бесконечна, т.к. бесконечна длина L.
Последний раз редактировалось vitaly_l 07.03.2018 18:19:45, всего редактировалось 1 раз.
Аватара пользователя
vitaly_l
долгожитель
 
Сообщения: 3333
Зарегистрирован: 31.01.2012 16:41:41

Re: md5 -- чо опять не так?

Сообщение runewalsh » 07.03.2018 18:19:40

Для хранения L понадобится (в лучшем случае) столько же бит, на сколько длина сообщения превышает 384.
Аватара пользователя
runewalsh
постоялец
 
Сообщения: 403
Зарегистрирован: 27.04.2010 00:15:25

Re: md5 -- чо опять не так?

Сообщение vitaly_l » 07.03.2018 18:21:25

runewalsh писал(а):Для хранения L понадобится (в лучшем случае) столько же бит, на сколько длина сообщения превышает 384.

Да, именно, это ещё и более выгодно при хранении больших хэшей, т.к. требует намного меньше памяти нежели sha2048... sha4096...
Аватара пользователя
vitaly_l
долгожитель
 
Сообщения: 3333
Зарегистрирован: 31.01.2012 16:41:41

Пред.След.

Вернуться в Потрепаться

Кто сейчас на конференции

Сейчас этот форум просматривают: MailRu[bot] и гости: 3

Рейтинг@Mail.ru