md5 -- чо опять не так?
Модератор: Модераторы
Нет, это то же самое, что хранить само сообщение.
runewalsh писал(а):Нет, это то же самое, что хранить само сообщение.
Почему?
Когда указывается хэш 999999999999999999999999999999999999999999999999999999999999999999 + md5 + sha для Большой Ленинской энциклопедии, где 999999999999999999999999999999999999999999999999999999999999999999 - это количество букв в одной книге, то явно этот хэш короче чем хранить всё сообщение (книгу).
Так ты всё ещё про просто длину? Я же сказал: среди всех сообщений длины 385 бит (можно добить нулями до 49 байт) будет минимум 30000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 (2^384) коллизий одновременно md5 и sha-256. А в книге можно, не меняя длину, поменять любые 49 байт так, чтобы (с вероятностью >50%) оба хэша получившейся книги совпали с хэшами исходной.
runewalsh писал(а):Так ты всё ещё про просто длину? Я же сказал: среди всех сообщений длины 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, так ещё и не факт что они будут на одно и тоже слово.
runewalsh писал(а):(с вероятностью >50%)
Соответственно в такую громадную вероятность я точно никогда не поверю. Если вероятность > 50% то попробуйте найти хотя-бы ОДНО совпадение.
Последний раз редактировалось vitaly_l 07.03.2018 19:14:44, всего редактировалось 1 раз.
vitaly_l писал(а):Если длина слова меньше или равна 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;
Последний раз редактировалось runewalsh 07.03.2018 19:16:56, всего редактировалось 1 раз.
runewalsh писал(а):TCombinedHash = record
md5_and_sha256: array[0 .. 47] of byte;
end;
Это не верно (в смысле ложно), т.к. это не последовательные числа от 0 до max. sha и md5 - это не линейная зависимость.
Это не может быть неверным, т. к. их байты именно так лежат в памяти в первом варианте, одну форму можно взаимно однозначно преобразовать в другую.
А даже если бы была линейная как у 0,1,2,3,4,5,6,7,8,9,10, то всё равно такая последовательность индексов бесконечна. Это все равно что вместо десятичной системы взять 16-ти-ричную, где цикл спирали равен 16-ти цифрам. Только цикл спирали, будет из 116 цифр.
Добавлено спустя 25 секунд:
Мы обсуждаем что-то разное, т.к. оба правы.
Добавлено спустя 4 минуты 44 секунды:
В смысле Вы мне доказываете одно, а я Вам доказываю совершенно другое. Истина, как обычно где-то в Балагое.
Добавлено спустя 25 секунд:
runewalsh писал(а):Это не может быть неверным, т. к. их байты именно так лежат в памяти в первом варианте, одну форму можно взаимно однозначно преобразовать в другую.
Мы обсуждаем что-то разное, т.к. оба правы.
Добавлено спустя 4 минуты 44 секунды:
В смысле Вы мне доказываете одно, а я Вам доказываю совершенно другое. Истина, как обычно где-то в Балагое.
Тебе наглядно показали, что сочетание SHA-256, MD5 и длины сообщения (пусть она хранится в longword или qword, неважно) можно рассматривать как хэш длины 384 или, с длиной, 384+чуть-чуть. А у любого хэша длины N гарантированно есть коллизии среди сообщений длины N+1.
runewalsh писал(а):У любого хэша длины N гарантированно будут коллизии среди сообщений длины N+1.
Да, всё верно! Но это уже длина N+1 соответственно все хэши длинной N - уже вылетают из сравнения. И у хэшей для слова длинной N+1 не получается совпадений.
Последний раз редактировалось vitaly_l 07.03.2018 19:46:48, всего редактировалось 1 раз.
У хэша длина фиксированная (для MD5 — 128 бит), сообщение, хэш которого рассчитывается, может быть любой длины, хоть мегабайт.
runewalsh писал(а):У хэша длина фиксированная (для 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
и так до бесконечности, левая колонка может расти
Сообщения длины 128 могут не иметь коллизий своих 128-битных хэшей.
Для сообщений длины 129 понадобится индекс 0 или 1 (1-битный).
Для сообщений длины 130 понадобится снова индекс 0 или 1 уже для под-сообщения длины 129, т. о. оба индекса составляют 2-битовое число.
Для сообщений длины 131 понадобится 3-битный индекс к 128-битному хэшу.
В общем случае этот индекс будет занимать столько, на сколько длина сообщения больше длины хэша (ещё больше с учётом коллизий, никогда не меньше), т. е. это не лучше, чем просто хранить сообщение.
Для сообщений длины 129 понадобится индекс 0 или 1 (1-битный).
Для сообщений длины 130 понадобится снова индекс 0 или 1 уже для под-сообщения длины 129, т. о. оба индекса составляют 2-битовое число.
Для сообщений длины 131 понадобится 3-битный индекс к 128-битному хэшу.
В общем случае этот индекс будет занимать столько, на сколько длина сообщения больше длины хэша (ещё больше с учётом коллизий, никогда не меньше), т. е. это не лучше, чем просто хранить сообщение.
runewalsh писал(а):это не лучше, чем просто хранить сообщение.
А пример слабо придумать?
Упростим до 4-битного хэша, пусть это первые 4 бита MD5. Слабо дополнить его индексом, который позволит хэшировать файлы без коллизий и при этом будет меньше размера файла? С любым хэшем принципиально то же самое.