Привет, all Известно, что добавив определенные 4 байта к любому файлу, можно получить нужную crc32 (имею ввиду "стандартный" crc32), независимо от crc32 исходного файла. Для crc16 нужно добавить всего 2 байта. Внимание, вопрос: можно ли такое проделать с другими криптографическими хэшами (не crc*), я смотрел в гугле, ничего не нашел. Меня больше волнует теоретическая сторона - можно или нет, т.к. возможно, что найти эти корректирующие байты будет очень сложно.
зависит от алгоритма.. иногда можно обойтись несложными вычислениями, иногда нужен брутфорс, иногда вообще очень сложно подделоть (например вооброзом crc advance, который будет состоять из crc файла и crc размера файла, которые считаются отдельно и сравниваюцо отдельно)
Freeman меня практическая сторорона не волнует, понятно, что для хэшей сложнее стандартного crc реверсировать алгоритм будет практически невозможно, а брутофорс бесполезен, т.к. подозреваю, что для полного брутофорса, например, 128-битного хэша потребуется время сравнимое с возрастом вселенной. all Пока ехал в маршрутке из универа, пришел к мысли, что для корректировки _любого_ хэша длиной n байт нужно к сообщению добавить/изменить не более n определенных байт. Я совсем мало знаю в криптографии, поэтому я могу ошибаться, может я где-то допустил ошибку, поправьте пожалуйста, если это так. Все следует из простенького доказательства (возможно неверного): пусть хэш длиной n бит, тогда возможно 2^n его возможных значений. В идеальном случае, при каждом изменении/добавлении бита хэш будет меняться, а т.к. число всевозможных его значений конечно, то в крайнем случае надо добавить/изменить n бит, чтобы хэш совпал с нужным. Т.е. чтобы установить нужный, к примеру, md5 для сообщения, нужно добавить/изменить не более 128 бит этого сообщения. Я прав? Если нет, то где ошибка.
Мне кажется ты вопрос не совсем корректно поставил. С криптографическими — нельзя. Т.е. такой блок данных сущетсвует, но найти его вычислительно невозможно. Поэтому — нельзя. В своих рассуждениях ты прав.
flankerx Вопрос был такой: есть сообщение, есть какой-либо хэш длины n бит, возможно ли (теоретически) добиться нужного значения этого хэша дописав/изменив не более n бит в сообщение. Хотя на вопрос ты уже ответил ("В своих рассуждениях ты прав), спасибо. Я не понял, что за "блок данных" ты имеешь в ввиду. Я полный ламер, мне надо объяснить очень ясно, а то я не пойму.
Ты неправ. Менятся будет, но может получиться что один хэш будет получаться одинаковым, от разных наборов данных. Поэтому тебе нужно как минимум n бит и более. Пример Хэш функция And 00 0 01 0 10 0 11 1 010101010100011 0 Если на каком-то участке получается хэш 0 то он так и будет 0 и никуда отэтого не уйти. Пример 2 x2x1f' f 000 1 001 0 010 1 011 0 100 0 101 1 110 0 111 1 Что бы изменить функцию нужно два бита.
Ra!N В идеальном случае, при каждом изменении/добавлении бита хэш будет меняться, а т.к. число всевозможных его значений конечно, то в крайнем случае надо добавить/изменить n бит, чтобы хэш совпал с нужным. К сожалению рассуждение неверно. Даже если мы примем, что значение меняется при изменении любого бита, то нигде не сказано, что оно будет меняться все время по-разному. Изменение и добавление битов эквивалентны, поэтому можем ограничиться рассмотрением изменений. Пример: для числа a_{1}a_{2}a_{3}.. (где a_{i} биты) вычисляем двухбитовый хеш S = ((a_{1}+a_{2}+a_{3}+...) & 1100b) >> 2 Дано число 1111b. Попробуй получить для него S=10b, изменив два бита. То есть ответ на твой вопрос: для корректировки _любого_ хэша длиной n байт нужно к сообщению добавить/изменить не более n определенных байт. нет, в общем случае это неправильно. P.S. Когда писал, предыдущего сообщения еще не было
Pavia Stiver Спасибо большое. Все разъяснили, я был не прав Насчет md5: а для этого хэша существует некоторый нижний предел кол-ва бит, которые нужно добавить/изменить для получения нужного хэша. Теоретически.
Да прав ты, тыщщу раз прав!!! Теоретически для подгонки хеша в N бит достаточно перепатчить каких-нить N бит, потому что у них одинаковое число состояний, 2^N. Но практически ничего сложнее CRC ты реверснуть не сможешь, так что тема эта бредовая.
Freeman Pavia и Stiver совершенно верно отметили неточности в рассуждениях, но общая идея от этого не меняется. Пространство значений хеш-функции ограничено, поэтому рано или поздно найдется такая последовательность из K битов, что хеш от сообщения и этой последовательности будет равен заданному. Да, для используемых хешей не существует эффективных алгоримов поиска таких последовательностей. Да, утверждать что K <= N нельзя. Но общая идея правильная и, в общем то, очевидная.
flankerx Пространство значений хеш-функции ограничено, поэтому рано или поздно найдется такая последовательность из K битов, что хеш от сообщения и этой последовательности будет равен заданному. И это рассуждение тоже неверно Даже если предположить, что для каждого значения хеша существует бесконечно много последовательностей, отображающихся на него (что далеко не очевидно и в общем случае не выполняется) - из этого не следует, что среди них найдется хотя бы одна с заданным префиксом (здесь: сообщением).
Stiver вот, тут, пожалуйста, поподробней - из какого леса сии чудеса(???): хэш - отображения большего множества в меньшее, если какие-то значения не будут на других цепочках повторяться - для других значений хэша произойдёт уплотнение, т.е. 2^N - длинна хэшируемых файлов 2^T - длинна хэшей ====>> колво файлов на каждое значение хэша в среднем == 2^(N-T)
Вот хэш, к которому можно добавлять что угодно, но значение для массива состоящего из 1 еденицы подделать нельзя. Хотя я не знаю "правильного" определения слова хэш и м.б. моя процедура им не является ULONG GetHash(PBYTE Array, ULONG Size) { ULONG Hash = 0; ULONG i; if (Size == 1 && Array[0] == 1) { Hash = 1; } else { for (i = 0; i < Size; i++) Hash += Array*2; } return Hash; }
Stiver А если мы скажем что хеш — это (псевдо)случайное отображение из (0,1)^m в (0,1)^n, где m — произвольное натуральное, а n — не более 128, например?
flankerx А если мы скажем что хеш — это (псевдо)случайное отображение Смотря что понимать под случайным отображением.. приведи пожалуйста определение, которое ты используешь.
Stiver Скажем, отображение, каждому элементу из пространства сообщений ставящее в соответствие случайную последовательность длиной n бит.
flankerx Скажем, отображение, каждому элементу из пространства сообщений ставящее в соответствие случайную последовательность длиной n бит. Все равно не до конца ясно Нужно различать между отображением и алгоритмом отображения. Если речь идет о свойствах отображения, то для хэшей обычно требуют равномерное распределение вероятности, то есть: для случайно выбранного сообщения m вероятность, что его хэш S(m) равен определенному значению n, должна быть равна 1/|S| (где |S| количество возможных значений) Существования нужной последовательности это свойство не гарантирует, пример: функция, отображающая строку на ее первый знак. Но если под "ставящее в соответствие случайную последовательность" подразумевается свойство самого алгоритма - т.е. каким образом функция обеспечивает равномерное распределение ("бросанием кубика") - тогда да. Для этого частного случая действительно всегда можно построить искомую последовательность.
