Существует ли универсальная функция F, которая F (sha (a), sha (b)) = sha (ab)

Question

Я столкнулся с необходимостью отправлять свои данные по частям, и в то же время я должен предоставить sha256 для своих ВСЕХ данных.

Что-то вроде этого cat large file | chunker | receiver, где получатель - это приложение, котороеожидается получение данных, возможно, порциями, имеющими в заголовке sha256 полезной нагрузки и затем следующей полезной нагрузки.После сбора всех фрагментов предполагается сохранить все переданные данные, и sha256 всех данных (конкретный sha256 будет использоваться только для перефразирования и подтверждения целостности данных.)

Конечно, самая простая вещьбыло бы, если бы получатель генерировал sha256 из всех потоковых данных, но мне было интересно, есть ли более простой способ, собирая все хеши всех кусков, и объединяя их для генерации одного окончательного хеша, который будет таким же, как хеш, вычисленный извсе данные.

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

И снова, другими словами, имея эту формулу: F (sha256 (данные [0]), sha256 (данные [1]), ... sha256 (data [N])) = sha256 (data [0..N])

Какой будет функция F?Будет ли это универсальная функция или нет такой вещи для вычисления хэширования?

Я подозреваю, что такой функции нет или это слишком сложный вопрос, чтобы на него ответить.

Answer 1

AFAIK, для SHA-256 до сих пор нет известных коллизий, но я держу пари, что как только некоторые найдены, то есть кто-то найдет два сообщения m1 и m2, таких что SHA-256(m1) = SHA-256(m2), тогда почти для любого префикса a хэшейSHA-256(a || m1) и SHA-256(a || m2) будут разными, т.е. запрашиваемая вами функция на самом деле не является функцией (имеет разные выходы для одних и тех же входов).Или, иначе говоря, SHA-2 восприимчив к атакам с удлинением, но AFAIK не к атакам с префиксами.Тем не менее, даже если это на самом деле функция, вам не достаточно, чтобы такая функция существовала, вы также хотите, чтобы она была быстрой.И я считаю, что нет такой быстрой для вычисления функции.

С другой стороны, SHA-256 работает, разбивая исходное сообщение на 512-битные порции и обрабатывая их, используя четко определенный процесс (основанный на состоянии всех предыдущих порций), поэтому теоретически вы можете изменитьнекоторая реализация SHA-256 для вычисления двух хэшей одновременно (путем применения одной и той же логики к разным начальным состояниям):

1. Хеш вашего блока приложения (с использованием стандартного начального состояния)
2. Хеш всех кусков до этой точки (используя состояние, переданное из предыдущего выхода того же шага, что и начальное состояние).

Это, вероятно, будет немного быстрее, чем выполнение этих вещейнезависимо, но я не знаю, будет ли это намного быстрее оправдывать такую ​​пользовательскую реализацию.