Текстовый файл содержащий свой хеш — возможно ли такое?

Question

[Андрей Вершинин]

Читая один известный ресурс, посвященный 'неординарному' коду, и увидев один экземпляр оного возник вопрос - возможно ли такое, чтобы строка содержала подстроку, которая является её хешем?

Comments

[Андрей Вершинин]

Если да, то возможно ли вычисление такой строки за полиномиальное время?

[Андрей Вершинин]

К примеру, MD5.

Answer 1

[sheknitrtch]

Если в двух словах, то это можно сделать следующим "тупым" алгоритмом:
# Придумываете значение хэш функции. Например: final_hash = '4817504d069b4c5082161b02a22116ad75f822b1'
# Начинаете перебор, дописывая к исходной строке с хешем произвольные строки:
txt = final_hash + 'a'
txt = final_hash + 'b'
txt = final_hash + 'c'
...
txt = final_hash + 'z'
txt = final_hash + 'aa'
txt = final_hash + 'ab'
...
# Для каждого варианта вычисляете значение хеша и сравниваете с final_hash. Как только calc_hash(txt) == final_hash - значит вы нашли искомую строку, которая содержит собственный хеш.

Проблема в том, что такой перебор может занимать от 5 минут до 5`000 лет.
Возможно существует какой-нибудь умный перебор с использованием радужных таблиц.
Многое зависит от вида хеш функции.

Answer 2

[Павел Волынцев]

Первое: если ты увидел алгоритм - попробуй и убедись.

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

Третье: файл может содержать хэш не самого себя, а какой нибудь части своей файла.
Например, первые N байт могли бы быть хэшем всего файла за исключением этих N байт.
В какой-то мере контрольные суммы файлов в ZIP являются хэшами от файлов, а хранится-то всё это в одном зипе.
Всё это может пригодиться если нужно проверить целостность документа (идентичное значение повторно вычисленного хэша по тому же файлу означает отсутствие потерь при передаче) или удостовериться в подлинности источника данных (хэш вычислен известным отправителем).

Comments

[Андрей Вершинин]

Я увидел кусок пхп кода, который проверял целостность/правильность файла, в котором этот кусок находился. Я понимаю о чем вы, но я не это имел ввиду.