В этой статье я хочу рассказать об одной небольшой, но интересной вещи — доказательстве незнания. Говоря точнее, мы будем генерировать хэши SHA-256 так, чтобы можно было доказать, что их прообразы почти наверняка никому не известны.
Разумеется, мы можем просто взять случайную последовательность байт, и полученное хэш-значение уже будет таким, у которого нет известного прообраза. Однако нам также нужно уметь доказывать, что эта последовательность байт действительно случайна, а не выбрана специальным образом.
Словосочетание “почти наверняка” часто встречается в данной статье из-за того, что вероятность подбора прообраза SHA-256 за разумное время ненулевая, хоть и ничтожно мала.
Решать данную задачу можно следующим образом:
import hashlib, random
s = random.getrandbits(256)
s_hash = hashlib.sha256(s.to_bytes(32, "big")).digest()
s_hash_int = int.from_bytes(s_hash, "big")
h = s_hash_int ^ 1
print(f"h={h:064x}")
print(f"s={s}")
Эта программа выдаёт значение h такое, что (почти наверняка) не существует числа x, для которого SHA256(x) = h, которое было бы кому-либо известно или могло бы быть кем-либо подобрано за разумное время. Значение s впоследствии можно использовать, чтобы доказать, что прообраз с подавляющей вероятностью никому не известен.
Теперь обсудим принцип работы. Мы берём некоторое случайное число s, которое будет служить зерном (seed) для дальнейших вычислений. Если нам нужен всего один хэш, s может быть даже любой константой: ему не обязательно быть по-настоящему случайным. Затем s хэшируется, чтобы получить исходную последовательность байт.
После этого мы слегка модифицируем байты SHA256(s) так, чтобы в этой модификации не было никаких скрытых секретов. В данном подходе мы просто инвертируем последний бит, выполняя XOR хэша с 1. Альтернативно можно взять любое другое «число без карт в рукаве», например, несколько первых цифр pi, e, sqrt(2) и т.д., и/или другую операцию «без карт в рукаве». К примеру, XOR с таким числом, как
k = 34127829386043893497825798180264754903547262366162207969901803965141107382164,
будет подтасованным, потому что k = SHA256(0x2) ^ SHA256(0x3): если s = 2, то мы получим
h = SHA256(s) ^ k = SHA256(0x2) ^ SHA256(0x2) ^ SHA256(0x3) = SHA256(0x3)
с известным прообразом 0x3.
Мы не можем просто взять произвольную последовательность байт и слегка её изменить, потому что она может быть заранее подогнана. Использование здесь SHA256(s) для генерации исходной последовательности байт делает такую «подгонку» не проще, чем поиск прообраза для хэша: чтобы добиться того, что h = SHA256(s) ^ 1 совпадает с SHA256(x) для некоторого выбранного x, нужно найти такое s, что SHA256(s) = SHA256(x) ^ 1, а это как раз задача поиска прообраза.
Чтобы доказать, что прообраз неизвестен, доказывающий может взять число s, вычислить его хэш и модифицировать его тем же способом, что и сторона, сгенерировавшая данный хэш. Таким образом, проверяющий убеждается в корректности конструкции и видимой «случайности» последовательности байт.
Я не знаю конкретных практических применений этой штуки, но она, например, может быть использована для генерации Bitcoin-адресов, которые доказуемо (почти наверняка) не имеют и никогда не будут иметь владельца.
Вместо SHA-256 можно использовать и другие криптографические хэш-функции.