обратная хэш-функция увеличивает возможности экспоненциально, но количество входных данных конечно. Как?

При попытке обратить хэш-функцию происходит потеря, например.

а+б=с
учитывая c = 5, попробуйте вернуться к a, b (предыдущий шаг)
(а,б)=(5,0),(4,1),(3,2),(2,3),(1,4),(0,5)

но, учитывая любую из пар (a, b), мы получаем c = 5 на следующем шаге, и каждая из этих пар имеет один и тот же экспоненциальный рост, применяемый при их изменении. Таким образом, кажется, что каждый шаг назад увеличивает количество возможных значений, которые приводят к c=5, в геометрической прогрессии.

Кроме того, никакие две ветви не могут рекомбинироваться при реверсировании, поскольку для этого потребуется разбить одну (a, b, c) на две возможные (a, b, c), что является случайным, а не детерминированным и поэтому невозможно при хешировании.

Проблема в том, что существует конечное число входных данных и конечное число возможных значений (a,b,c). Это кажется парадоксом, и единственное решение, которое я могу найти, это то, что некоторые пути являются тупиковыми, например. ((a,b,c)!=можно сделать из любого другого (a,b,c)). Тем не менее, я не думаю, что такие (a, b, c) существуют, так что, может быть, у меня неправильное решение?

Я думаю, что ваше замешательство происходит из-за того, что вы смотрите на одну операцию, а не на хеш-функцию в целом. Это правда, что обращение такой операции, как сложение, вводит новую входную переменную для каждой итерации. Но это игнорирует то, как такая операция используется в хеш-функции. Если вы посмотрите на такую ​​функцию, как SHA-256, такая операция, как сложение, вписывается в четко определенную сеть других операций, которые преобразуют входные данные в выходные. Сеть принимает 512 бит ввода и производит 256 бит вывода, а определение фиксировано, так что на самом деле нет места для разговоров об «экспоненциальном росте». Что верно, так это то, что попытка решить для набора входных данных, который дает желаемый результат, требует экспоненциальных усилий от размера проблемы.

обратная хэш-функция увеличивает возможности экспоненциально, но количество входных данных конечно. Как?

Это именно то, что мы ожидали (рассказ); каждое неизвестное увеличивает вероятность на 2, поэтому вы получите показатель экспоненты - вы можете подумать, что таблица истинности увидит это. В SHA-256 существует ограниченный ввод из-за правил заполнения, то есть $2^{128}-1$. Ваш вклад может быть не таким большим, но все же конечным.

Обращение операции хэширования SHA-256 с помощью решения уравнений (мы называем это алгебраическая атака) почти невозможно, так как вы должны решить символьные вычисления (SAT), а 3SAT является NP-полным. Нет гарантии, что каждый экземпляр SHA-256 неразрешим.. Если учесть, что заявленная AES алгебраическая атака (XSL) не быстрее перебора. Я ожидаю, что 64-раунд SHA-256 будет сложнее для криптоанализа с алгебраическими атаками. Это все еще не означает, что для некоторых значений хеш-функции экземпляр также будет неразрешимым.

Я ожидаю, что даже для 64-битного входного пространства алгебраические вычисления сложнее, чем поиск в 64-битном входном пространстве, чтобы найти прообраз заданного хэш-вывода.

В вашем расчете вы исключаете некоторые возможности переменных, это то, что мы ожидаем, однако 64 раунда внутреннего блочного шифра SHA-256 с именем SHACAL2 не позволит вам его выполнить. Это не способ атака SHA-256.

книга Барда; Алгебраический криптоанализ является отправной точкой для алгебраической атаки. И посмотрите, как их новое уведомление помогает сломать простое шифрование keeloq в то время как SHA-256 гораздо сложнее рассматривать.