Атака «дней рождения» (Birthday attack)

Один из популярных способов атаки на Биткойн который может быть использован при достаточном количестве ядер или новым поколением квантовых компьютеров это атака «дней рождения» (Birthday attack)

Метод основывается на вычислении коллизий хеш-функций на основе т.н. "парадокса дней рождения".

Используется математика, стоящая за проблемой "дня рождения" из теории вероятностей. Успех атаки во многом зависит от более высокой вероятности коллизий между случайными попытками атаки и фиксированным числом определяющим степень перестановок, как и описано в проблеме парадокса "дня рождения". Это готовая математическая модель для поиска частичных столкновений, через обнаружение коллизий между двумя Биткоин Адресами, которые создают один и тот же HASH160( для поиска коллизии HASH160).

Принцип аналогичен известной теории "Случайных блужданий"

Пять случайных блужданий по восемь шагов с началом в центральной точке.

Некоторые пути будут короче, чем 8 шагов: в этом случае наш путь продублирует шаги в обратном направлении. Материал из Википедии: «Случайное блуждание»

Используя простой принцип, согласно которому любая функция с конечным числом возможных выходов, помещенных в петлю обратной связи, может циклически повторяться, можно использовать небольшой объем памяти для хранения результатов с определенной структурой и использовать их в качестве эталонных, чтобы лучше определять, когда маркер имеет место ( это будет сигнал что нужное нам значение уже было «пройдено» раньше). Эти маркеры называются выделенными точками , а точка в которой два входа дают один и тот же результат, называется точкой столкновения.

Перейдем к самому процессу:
Откроем
[TerminalGoogleColab].
Воспользуемся репозиторием «11QianshiBTC».
Установим пакеты:

git clone https://github.com/demining/CryptoDeepTools.git
cd CryptoDeepTools/11QianshiBTC/
ls



sudo apt-get install g++ -y
sudo apt-get install libgmp3-dev libmpfr-dev -y





Сборка:
make




Запустим команду ls и увидим что qianshiBTC — наш инструмент для поиска коллизии Биткоин Адресов успешно создан!


Запуск:

Для запуска укажем в нем первые 40 bits для поиска столкновения:
./qianshiBTC 40



Как видим мы успешно получили частичную коллизию Биткоин адресов используя «Birthday Attack»

Откроем bitaddress и проверим:

--RESULT-(SECRET)---------------------------------------------------------------

priv_key[1] = 277C6CA6F6BD18E09BE149D02B73219E959F1F196EA053DA064F8AE87D937060
priv_key[2] = 9E233E554BBBCA4E0E487DBB108E8207F5E29C2203007A6C671F769C6EB56463

WIF[1] = KxYU1nx59KfPngSvDWU9B2hinhprnTT5pXiVZUEmjqdo41DuafPc
WIF[2] = L2X7Kn854vGj87rNQd1Kgz9p9powZ3iHebp8GdkK8tHuRMDjufJv

--RESULT-(SIGNATURES)-----------------------------------------------------------

message = "This is a real Bitcoin address."
sig[1] = H3RIf+MXNTt68hBxo6jNLMYFZVdGJYKucuE07P2EEcYnCT3MmeC7IZ7bib4GphG3oKph2Cg/t1KIoJShT1uLOfo=
sig[2] = ILWm8qSAacbS+ShcUohp5Nyw4/yFLMPRydPLLy8HNy3IVHRvRt58Rtr3511euQGT9tVIcv0QhetqydrB0txUxu8=

--RESULT-(PUBLIC)---------------------------------------------------------------

pub_key[1] = 023A7ABE886BF8A5E629C71449FA7B45F1A540A88C1321B32153002EE5DB6FCD
pub_key[2] = 024EE1DFCE7498EA0729EADFDC3428FF3D966509800A4C786A317B9E0CAABB44

bonus = 0bits
shared = 10chars
hash160[1] = 06df0a6506d559796b4e4bf11e5d37140151f631
hash160[2] = 06df0a6506264eae5f2727343b09f9b6b114d5ad

shared = 6chars
addr[1] = 1dLFHTpXawMMcFGd81ky7pjEcKDa9z3M8
addr[2] = 1dLFHToyYKVanuxG6XcC1BW9BLHuRugGt

warning: verify the keys/addresses before use!


В настоящее время этот код использует только CPU, переход на GPU сделал бы возможными поиск даже 100 битных коллизий.
Это чем-то похоже на добычу разделенных ключей "Vanitygen".

В случае с квантовыми компьютерами хэш функция RIPEMD160 полностью обречена.

Вдохновлено: «Параллельный поиск столкновений с помощью криптоаналитических приложений»
[«Parallel Collision Search with Cryptanalytic Applications»] Paul C. van Oorschot & Michael J. Wiener