Более быстрый способ найти правильный порядок фрагментов, чтобы получить известный хэш SHA1?

Question

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

Можно ли ускорить это, вычисляя хеш SHA1 отдельно для каждого чанка, а затем находить порядок чанков, манипулируя только хешами?

Answer 1

Короче, №

Если вы используете SHA-1, из-за Эффект лавины , любое незначительное изменение в открытом тексте (в вашем случае, ваши чанки) значительно изменит соответствующий ему SHA-1.

Скажите, если у вас есть 4 куска: A B C и D , хеш SHA1, равный A + B + C + D (объединенный) равен , предполагается, что не должен быть коррелирован с хешем SHA1 для вычисленных A, B, C и D как отдельно.

Поскольку они не связаны, вы не можете нарисовать какую-либо связь между конкатентным фрагментом (A + B + C + D, B + C + A + D и т. Д.) и каждым отдельным фрагментом (A , B, C или D) .

Если бы вы могли определить какие-либо отношения между ними, алгоритм хэширования SHA1 оказался бы в затруднении.

Answer 2

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

Теоретический ответ: это зависит.Предполагая, для простоты, что у вас есть N порций по 512 битов, тогда вы можете принять меры, чтобы стоимость не превышала N * 2 ¹⁶⁰ элементарных оценок SHA-1, что ниже N! , когда N> = 42 .Идея состоит в том, что рабочее состояние SHA-1 между двумя последовательными блоками ограничено 160 битами.Конечно, эта стоимость смехотворно невозможна в любом случае.В более общем плане, ваша проблема заключается в поиске прообраза для SHA-1 с входными данными в пользовательском наборе S ( N! последовательностей ваших N кусков), поэтомустоимость имеет нижнюю границу размера S и сопротивление прообразу SHA-1, в зависимости от того, что ниже.Размер S равен N! , который очень быстро растет при увеличении N .SHA-1 не имеет известных недостатков в отношении прообразов, поэтому предполагается, что его сопротивление по-прежнему составляет около 2 ¹⁶⁰ (поскольку он имеет 160-битный выход).

Редактировать: Этот тип вопроса будет уместен на предложенном обмене стеками "криптографии" , когда (если) он будет создан.Пожалуйста, помогите создать его!

Answer 3

В зависимости от вашей библиотеки хеширования, что-то вроде этого может работать: допустим, у вас есть блоки A, B, C и D. Вы можете обработать хеш для блока A, а затем клонировать это состояние и вычислить A + B, A + C и A + D без необходимости пересчитывать A каждый раз. И затем вы можете клонировать каждый из них для вычисления A + B + C и A + B + D из A + B, A + C + B и A + C + D из A + C и т. Д.

Answer 4

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