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

[runewalsh]

Нет, это то же самое, что хранить само сообщение.

[vitaly_l]

Нет, это то же самое, что хранить само сообщение.

Почему?

Когда указывается хэш 999999999999999999999999999999999999999999999999999999999999999999 + md5 + sha для Большой Ленинской энциклопедии, где 999999999999999999999999999999999999999999999999999999999999999999 - это количество букв в одной книге, то явно этот хэш короче чем хранить всё сообщение (книгу).

[runewalsh]

Так ты всё ещё про просто длину? Я же сказал: среди всех сообщений длины 385 бит (можно добить нулями до 49 байт) будет минимум 30000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 (2^384) коллизий одновременно md5 и sha-256. А в книге можно, не меняя длину, поменять любые 49 байт так, чтобы (с вероятностью >50%) оба хэша получившейся книги совпали с хэшами исходной.

[vitaly_l]

Так ты всё ещё про просто длину? Я же сказал: среди всех сообщений длины 385 бит (можно добить нулями до 49 байт) будет минимум 30000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 (2^384) коллизий одновременно md5 и sha-256. А в книге можно, не меняя длину, поменять любые 49 байт так, чтобы (с вероятностью >50%) оба хэша получившейся книги совпали с хэшами исходной.

Не понимаю про байты. Я беру длину слова в символах. Если длина слова меньше или равна 2^384, то 100% совпадения невозможны. При этом, 2^384 * 256 - значений 100% уже не совпали.

Если длина слова 2^384 + 1, то появляется маловероятная едва отличная от ноля вероятность что в строке длинной 2^384+1 из (2^384+1)*256 букв ВОЗМОЖНО с вероятностью 0.00000000000000000000000000000000000000000000000000000001 найдётся хотя-бы один ЕДИНОВРЕМЕННО совпадающий для md5 и sha, т.к. зависимость не линейная и зависит от алгоритма md5 и sha, которые возвращают разные значения и возвращаемые значения явно не линейны, соответственно нет прямой зависимости от количества букв. То что у md5 128 бит значений, ещё не значит что они совпадут с 256 возвращаемых для sha, т.к. это не цифры которые идут подряд. И они не имеют повторяющуюся последовательность, позволяющую вычислить единовременное совпадение md5 и sha. Соответственно, когда длина слова 2^384 + 2, то тогде всего лишь увеличивается вероятность что в (2^384 + 2) * 256 букв, возможно произойдёт единовременное совпадение md5 и sha, т.к. возможно все только 512 повторов sha и 1024 для md5, но вероятность их единовременного совпадения - настолько сильно маловероятна, насколько велика вероятность совпадения параметров двух волн в океане, т.к. зависимость не линейная и эти 512 и 1024 повтора md5 и sha, мало того что разбросаны по шкале 2^384 + 2, так ещё и не факт что они будут на одно и тоже слово.

(с вероятностью >50%)

Соответственно в такую громадную вероятность я точно никогда не поверю. Если вероятность > 50% то попробуйте найти хотя-бы ОДНО совпадение.

[runewalsh]

Если длина слова меньше или равна 2^384

Если длина слова 384 бита (здесь нет никаких 2^), есть 2^384 (300...00 — то число из 116 цифр) вариантов этого слова. Это столько же, сколько всех возможных сочетаний MD5 и SHA-256. Если среди всех этих слов не было одновременных коллизий MD5 и SHA-256, то каждое слово длины 385 и больше будет иметь таковую с одним из них.

Ещё раз, сочетание MD5 и SHA-256 можно рассматривать как один 384-битный хэш. Представь себе

Код: Выделить всё

TCombinedHash = record
    md5: array[0 .. 15] of byte;
    sha256: array[0 .. 31] of byte;
end;

как

Код: Выделить всё

TCombinedHash = record
    md5_and_sha256: array[0 .. 47] of byte;
end;

[vitaly_l]

TCombinedHash = record
    md5_and_sha256: array[0 .. 47] of byte;
end;

Это не верно (в смысле ложно), т.к. это не последовательные числа от 0 до max. sha и md5 - это не линейная зависимость.

[runewalsh]

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

[vitaly_l]

А даже если бы была линейная как у 0,1,2,3,4,5,6,7,8,9,10, то всё равно такая последовательность индексов бесконечна. Это все равно что вместо десятичной системы взять 16-ти-ричную, где цикл спирали равен 16-ти цифрам. Только цикл спирали, будет из 116 цифр.

Добавлено спустя 25 секунд:

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

Мы обсуждаем что-то разное, т.к. оба правы.

Добавлено спустя 4 минуты 44 секунды:
В смысле Вы мне доказываете одно, а я Вам доказываю совершенно другое. Истина, как обычно где-то в Балагое.

[runewalsh]

Тебе наглядно показали, что сочетание SHA-256, MD5 и длины сообщения (пусть она хранится в longword или qword, неважно) можно рассматривать как хэш длины 384 или, с длиной, 384+чуть-чуть. А у любого хэша длины N гарантированно есть коллизии среди сообщений длины N+1.

[vitaly_l]

У любого хэша длины N гарантированно будут коллизии среди сообщений длины N+1.

Да, всё верно! Но это уже длина N+1 соответственно все хэши длинной N - уже вылетают из сравнения. И у хэшей для слова длинной N+1 не получается совпадений.

[runewalsh]

У хэша длина фиксированная (для MD5 — 128 бит), сообщение, хэш которого рассчитывается, может быть любой длины, хоть мегабайт.

[vitaly_l]

У хэша длина фиксированная (для MD5 — 128 бит), сообщение, хэш которого рассчитывается, может быть любой длины.

Так в том-то и секрет, что у хэшей длинна-то фиксированная, а мы добавили к этим хэшам уникальный индекс 1,2,3,4,5,6,7,8, итд до бесконечности. Соответственно и совпадений нет и не может быть.

Добавлено спустя 1 минуту 56 секунд:
Индекс состоит не только из двух хэшей но и из третьего значения, которое равно длине слова и это значение РАСТЁТ как уникальный индекс и никогда не повторяется.

Добавлено спустя 5 минут 55 секунд:
То есть даже если оно ВДРУГ совпадёт по хэшам то будет разным по длине слова:

Код: Выделить всё

1 | 608333adc72f545078ede3aad71bfe74  |  e58f1e8c55fa105bdd3f40e5037eb0b039b5998d52c05e6cd98878dd2da5cab2
2 | 608333adc72f545078ede3aad71bfe74  |  e58f1e8c55fa105bdd3f40e5037eb0b039b5998d52c05e6cd98878dd2da5cab2
3 | 608333adc72f545078ede3aad71bfe74  |  e58f1e8c55fa105bdd3f40e5037eb0b039b5998d52c05e6cd98878dd2da5cab2
4 | 608333adc72f545078ede3aad71bfe74  |  e58f1e8c55fa105bdd3f40e5037eb0b039b5998d52c05e6cd98878dd2da5cab2
5 | 608333adc72f545078ede3aad71bfe74  |  e58f1e8c55fa105bdd3f40e5037eb0b039b5998d52c05e6cd98878dd2da5cab2
6 | 608333adc72f545078ede3aad71bfe74  |  e58f1e8c55fa105bdd3f40e5037eb0b039b5998d52c05e6cd98878dd2da5cab2
7 | 608333adc72f545078ede3aad71bfe74  |  e58f1e8c55fa105bdd3f40e5037eb0b039b5998d52c05e6cd98878dd2da5cab2
8 | 608333adc72f545078ede3aad71bfe74  |  e58f1e8c55fa105bdd3f40e5037eb0b039b5998d52c05e6cd98878dd2da5cab2
и так до бесконечности, левая колонка может расти


[runewalsh]

Сообщения длины 128 могут не иметь коллизий своих 128-битных хэшей.
Для сообщений длины 129 понадобится индекс 0 или 1 (1-битный).
Для сообщений длины 130 понадобится снова индекс 0 или 1 уже для под-сообщения длины 129, т. о. оба индекса составляют 2-битовое число.
Для сообщений длины 131 понадобится 3-битный индекс к 128-битному хэшу.
В общем случае этот индекс будет занимать столько, на сколько длина сообщения больше длины хэша (ещё больше с учётом коллизий, никогда не меньше), т. е. это не лучше, чем просто хранить сообщение.

[vitaly_l]

это не лучше, чем просто хранить сообщение.

А пример слабо придумать?

[runewalsh]

Упростим до 4-битного хэша, пусть это первые 4 бита MD5. Слабо дополнить его индексом, который позволит хэшировать файлы без коллизий и при этом будет меньше размера файла? С любым хэшем принципиально то же самое.