Comments 30
Код выглядит просто ужасно — нельзя было использовать массив, вместо переменных с индексом в имени?
В какой именно функции? Какие именно переменные?
Если это в sha256 — так это типовые реализации взятые на просторах интернета. Они все похожи, как близнецы братья.
Если это в sha256 — так это типовые реализации взятые на просторах интернета. Они все похожи, как близнецы братья.
Просто воспринял вывод консоли, который ошибочно сделан цветным, как код на ++ при беглом просмотре. А так я бы такого не писал + взял бы готовое решение например — github.com/openssl/openssl/blob/master/crypto/sha/sha256.c, а все номера парсил как hex-строки ну или base64 хотя бы — просто из-за кучи магических чисел — код выглядит мерзко ИМХО.
Я как-то раз подумал о чем-то подобном, но немного в другом ключе. Все алгоритмы (в т.ч. криптографические) так или иначе сводятся к битам и базовым операциям над ними — AND, OR, NOT, а можно свести все к одной операции "штрих шеффера" или "стрелка пирса". То есть любой алгоритм может быть представлен как логическая схема с M входов и N выходов. Для такой схемы может быть составлена таблица истинности. А дальше я задумался — можно ли "развернуть" схему? Т.е. "подавая" на выходы какие-то значения, протрассировать логику обратно и получить что-то на входах?
Тут как раз требуется некая вероятностная логика. Но, как оказалось, не просто вероятностная: входы как правило оказываются весьма сложным образом взаимозависимы. Даже для простейшего элемента — скажем "логического И" с двумя входами и одним выходом получается, что если на выход "подать" 1, то на входах однозначно будут единицы; если же на выход "подать" 0, то на входах будут неопределенные значения ("0.5" ?), но они не должны быть равны "1" одновременно. Как это отразить, я так и не понял, поэтому дальше рассуждений дело не пошло.
У меня есть на с++ готовый алгоритм, который делает «синтез схемы» для каждого выходного бита хэша. Думал про это вторую статью написать, но судя по посыпавшимся минусам, делать этого не стоит. Такие дела.
Как я понимаю, это в каком-то смысле эмуляция квантовых вычислений. Если найти способ оценивать вероятность того или иного входного бита для заданного набора выходных бит, то можно не только стать биткоиновым триллионером, но и взломать всю сильную криптогрфию:) Но подозреваю, что там не все так просто, т.е. нет линейной зависимости…
То есть, допустим мы подали "правильную" последовательность (например для bitcoin) на выход, и хотим посмотреть что же нужно подавать на вход. Получаем некую мешанину бит, все будут в районе около 0.5 (можно даже игнорировать взаимозависимости). Смотрим бит который сильнее всего отличается от 0.5 и приводим его к 0 или 1, после чего смоторим что получилось на остальных входах. Я подозреваю что картинка моментально поменяется, т.е. никакой схожести с предыдущими вероятностями не будет (это и есть нелинейность!).
И рано или поздно мы доберемся до "невозможной" комбинации. Т.е. все равно все сведется к полному перебору.
А алгоритм публикуйте, интересно. И плюсы уже посыпались:)
Теоретически можно построить логическую функцию в конъюнктивной или дизъюнктивной форме. Число слагаемых (если обозначать логическое или сложением) для одного выходного бита всего лишь лишь два в степени числа бит на входе (кратно 512 битам). Таблица истинности будет иметь столько же строк.
Логическое И (как и логическое ИЛИ) необратимо. Если число выходных бит меньше числа входных, то нельзя будет определить, что именно было подано на вход. Но, тем не менее, какие-то варианты можно отбросить.
Один выход логического И порождает два варианта. Если число элементов И велико и выход одного подаётся на вход другого, то число вариантов будет расти как степень двойки, и в итоге может оказаться что проще построить таблицу всех вариантов.
Логическое И (как и логическое ИЛИ) необратимо. Если число выходных бит меньше числа входных, то нельзя будет определить, что именно было подано на вход. Но, тем не менее, какие-то варианты можно отбросить.
Один выход логического И порождает два варианта. Если число элементов И велико и выход одного подаётся на вход другого, то число вариантов будет расти как степень двойки, и в итоге может оказаться что проще построить таблицу всех вариантов.
а можно переориентировать этот «бред» на поиск коллизий?
По хорошему, надо проверять, но навскидку ваш подход работать не должен — в силу принципов построения криптостойких хэшей. Если на пальцах — каждый бит входа «размазывается» по всем битам выхода (каким-то неочевидным образом влияя на них) — т.е. почти независимо от вероятностей битов nonce на входе (ну, если только вы не зададите точные значения) вы должны получать вероятности 0.5 на выходе. 64 раунда перемешивания, Карл!
Ну а поскольку операции с вероятностями «дороже» точного вычисления (особенно если вы будете использовать floating-point) — проиграете стандартным алгоритмам.
В общем, подход неплохой, но шифры, на которых он сработал бы, afaik давно ушли в прошлое.
Ну а поскольку операции с вероятностями «дороже» точного вычисления (особенно если вы будете использовать floating-point) — проиграете стандартным алгоритмам.
В общем, подход неплохой, но шифры, на которых он сработал бы, afaik давно ушли в прошлое.
Я в общем согласен с вами. Я так же был абсолютно уверен, что выходные вероятности будут у каждого бита очень близко к 0.5. Я когда начинал это исследование это и ожидал увидеть.
Однако, посмотрите на последнгий вывод в консоли, вероятности битов:
0.44525679540883948 0.44525679540840074
0.55268174813167364 0.5526817481315932
0.57758654725359399 0.57758654725360606
0.49595026978928474 0.49595026978930477
0.57118578561406703 0.57118578561407746
0.53237003739057907 0.5323700373905661
0.57269859374138096 0.57269859374138162
0.57631236396381141 0.5763123639638157
тут и 0.44 и 0.57 — дисперсия значительная.
Есть еще один фактор, о котором я думаю — на мой взгляд автор биткоина не очень удачно подобрал размер заголовка блока — 80 байт.
Второй sha256_transform получает слишком много паддинг нулей, и третий sha256_transform так же получает слишком много паддинг нулей. Нонсе конечно размазывается по всем выходным битам, но входные данные из за паддингов в значительной степени предопределены. По моим подсчетам до 1/5 вычислений просто излишни, так как обращаются в константы.
Однако, посмотрите на последнгий вывод в консоли, вероятности битов:
0.44525679540883948 0.44525679540840074
0.55268174813167364 0.5526817481315932
0.57758654725359399 0.57758654725360606
0.49595026978928474 0.49595026978930477
0.57118578561406703 0.57118578561407746
0.53237003739057907 0.5323700373905661
0.57269859374138096 0.57269859374138162
0.57631236396381141 0.5763123639638157
тут и 0.44 и 0.57 — дисперсия значительная.
Есть еще один фактор, о котором я думаю — на мой взгляд автор биткоина не очень удачно подобрал размер заголовка блока — 80 байт.
Второй sha256_transform получает слишком много паддинг нулей, и третий sha256_transform так же получает слишком много паддинг нулей. Нонсе конечно размазывается по всем выходным битам, но входные данные из за паддингов в значительной степени предопределены. По моим подсчетам до 1/5 вычислений просто излишни, так как обращаются в константы.
зачем float на битовом массиве? вероятность в процентах отлично считается ;)
Напоминает статистический криптоанализ. Там тоже исходят из предположения, что есть некоторая взаимосвязь распределений входных и выходных данных. В случае шифра — зависящая только от ключа и не зависящая от сообщения. В вашем случае — зависящая от nonce и не зависящая от остального заголовка блока.
Правда обычно криптосистему рассматривают как черный ящик, а вы вычисляете статистику не только для входа и выхода, но и для всех внутренних состояний. Кстати, а почему бы не использовать и эти данные тоже? Например, сравнивать не только вход и выход, но и выходы каждого раунда хеширования.
Вы придумали (предположительно) хороший метод криптоанализа, но пока не получили значимых результатов. Как проверить пригодность метода вообще? Попробуйте провести атаку на ослабленный алгоритм. Например, хеш-функцию с уменьшенным числом раундов, или меньшей разрядности. Или вместо SHA256 возьмите MD5, MD4, что-нибудь заведомо не криптостойкое, типа CRC, наконец.
Правда обычно криптосистему рассматривают как черный ящик, а вы вычисляете статистику не только для входа и выхода, но и для всех внутренних состояний. Кстати, а почему бы не использовать и эти данные тоже? Например, сравнивать не только вход и выход, но и выходы каждого раунда хеширования.
Вы придумали (предположительно) хороший метод криптоанализа, но пока не получили значимых результатов. Как проверить пригодность метода вообще? Попробуйте провести атаку на ослабленный алгоритм. Например, хеш-функцию с уменьшенным числом раундов, или меньшей разрядности. Или вместо SHA256 возьмите MD5, MD4, что-нибудь заведомо не криптостойкое, типа CRC, наконец.
Этот набор байтов довольно ценный материал, так как зачастую по исходникам майнеров не просто понять в каком порядке должны следовать байты при формировании заголовка, часто применяется разворот местами младших и старших байт (endians).
Но есть же классика для определения endians:
include <stdio.h>
unsigned short x = 1; /* 0x0001 */
int main(void)
{
printf("%s\n", *((unsigned char *) &x) == 0 ? "big-endian" : "little-endian");
return 0;
}Я собственно не совсем об этом… Вот к примеру смотрим статью «майним с помошью ручки и бумаги» habr.com/post/258181
типа там хорошо все объяснено и там есть вот такая картинка:
Предположим Вы хотите по этим данным сами пересчитать хэш и проверить, действительно ли там правильный нонсе.
Какие Ваши действия будут в этом случае?
Вы должны из этой картинки сформировать массив байтов для передачи в функцию sha256.
Тут видно что 32х битные слова. Но как в тестовый массив их занести — в прямом порядке или в развернутом? Особенно обескураживает подпись на merkle root — «reversed».
Вот все примеры которые я видел они какие-то бестолковые — не понятно как располагать данные в каком порядке следуют байты. Получается из картинки merkle — reversed, а остальные поля нет? И начинаешь гадать на кофейной гуще.
Собственно по этому я назвал свои примеры ценными. Это готовые заголовки блоков в котором байты стоят в правильном порядке.
Еще ньюанс. Если информацию о конкретном блоке смотреть из blockchain explorer глазами — там может оказаться вообще мрак — например, таймстамп может показывается не в шестнадцатеричном виде, а в виде строки даты: 2018-08-14 16:18:01 и кстати не понятно по какой временной зоне. И человек глядя на страницу blockchain explorera вообще ничего проверить почти не может — скопление бессмысленных данных, нуждающихся в дополнительной обработке.
А в моих «ценных» примерах уже все данные в виде байтов какие нужно.
типа там хорошо все объяснено и там есть вот такая картинка:
Предположим Вы хотите по этим данным сами пересчитать хэш и проверить, действительно ли там правильный нонсе.
Какие Ваши действия будут в этом случае?
Вы должны из этой картинки сформировать массив байтов для передачи в функцию sha256.
Тут видно что 32х битные слова. Но как в тестовый массив их занести — в прямом порядке или в развернутом? Особенно обескураживает подпись на merkle root — «reversed».
Вот все примеры которые я видел они какие-то бестолковые — не понятно как располагать данные в каком порядке следуют байты. Получается из картинки merkle — reversed, а остальные поля нет? И начинаешь гадать на кофейной гуще.
Собственно по этому я назвал свои примеры ценными. Это готовые заголовки блоков в котором байты стоят в правильном порядке.
Еще ньюанс. Если информацию о конкретном блоке смотреть из blockchain explorer глазами — там может оказаться вообще мрак — например, таймстамп может показывается не в шестнадцатеричном виде, а в виде строки даты: 2018-08-14 16:18:01 и кстати не понятно по какой временной зоне. И человек глядя на страницу blockchain explorera вообще ничего проверить почти не может — скопление бессмысленных данных, нуждающихся в дополнительной обработке.
А в моих «ценных» примерах уже все данные в виде байтов какие нужно.
Вот все примеры которые я видел они какие-то бестолковые — не понятно как располагать данные в каком порядке следуют байты. Получается из картинки merkle — reversed, а остальные поля нет?
Ваши "мучения" (хотите изыскания) мне напоминают рекомендации TK-26 по структуре сертификатов и CMS, где также что-то перевернуто, что-то переставлено, что-то little, что-то big. Спасибо за развернутый ответ.
А я все время считал, что все эти хеш суммы можно побитово расписать в систему уравнений и ее решить подставив известные нули (и еще предварительно сократить ага). Но что-то мне подсказывает, что такое решение будет дороже чем полный перебор
У меня есть программа, которая расписывает уравнение для каждого выходного бита.
Она составляет дерево логических функций для каждого бита.
Есть процедура, она оказывается рекурсивной, которая печатает логическую функцию для каждого бита в консоль. Еще не разу не дождался окончания работы этой процедуры — хотя честно пол дня ждал.
Но да, я теоретически у меня есть все уравнения.
Она составляет дерево логических функций для каждого бита.
Есть процедура, она оказывается рекурсивной, которая печатает логическую функцию для каждого бита в консоль. Еще не разу не дождался окончания работы этой процедуры — хотя честно пол дня ждал.
Но да, я теоретически у меня есть все уравнения.
запускаю код. пробую
и разница всё равно в 8-13 знаке. При этом она (почти) такая же, как если запускать с 1E-50.
for (int i = 0; i < 32; i++)
nonce_bits[i] = 1E-45;
nonce_x32_b.init(nonce_bits);и разница всё равно в 8-13 знаке. При этом она (почти) такая же, как если запускать с 1E-50.
Более того, даже если четко инициализировать все биты кроме первого,
всё равно выходит разница в 8-13 знаках. Переломный момент наступает, если
nonce_bits[0] = 1E-50;
for (int i = 1; i < 32; i++)
nonce_bits[i] = 1.0;всё равно выходит разница в 8-13 знаках. Переломный момент наступает, если
nonce_bits[0] = 1E-74;Я еще попробовал менять один бит правильного nonce. Допустим, третий бит равен 0. Я пробую в одном случае, к примеру 1E-60, в другом 1E-73. Было бы здорово, если бы разница во всех битах конца была одного знака — это означало бы, что нам точно нужно сделать бит окончательно 0. Но к сожалению, разница в каждом бите результата еще тысячу раз поменяет знак…
Информационно для понятия проблематики:
Посмотрим например на случайно выбранный майнинг блок 388368 на сайте blockchain.info.
hash для этого блока выглядит так:
0000000000000000021ff110a589e44f56979254a204557311204f803910fdfa
Требуется приблизительно 10 минут для всех компьютеров в майнинг сети (совместная производительность 700,000,000 гига хэш/секунда) для того чтобы найти этот хэш. Нетрудно увидеть что hash имеет достаточно начальных нулей (17), чтобы удовлетворять критериям сложности для биткоина в момент создания блока. Исходя из того, что все цифры после первых 17 могут быть любыми, получаем 16^47 (то есть 16^(64-17)) возможных вариантов, которые могут быть найдены при условии критериев сложности (3.92 * 10^56). Еще раз требуется вся вычислительная мощность майнинг сети в течении 10 минут чтобы найти один hash удовлетворяющий условиям.
Чтобы взломать hash с учетом первых 17 нулей, экстраполируя вышесказанное получаем, что потребуется 10 * 3.92 * 10^56 минут для взлома SHA256 при существующей мощности глобальной сети майнеров. А это скорее всего долгое время )
Посмотрим например на случайно выбранный майнинг блок 388368 на сайте blockchain.info.
hash для этого блока выглядит так:
0000000000000000021ff110a589e44f56979254a204557311204f803910fdfa
Требуется приблизительно 10 минут для всех компьютеров в майнинг сети (совместная производительность 700,000,000 гига хэш/секунда) для того чтобы найти этот хэш. Нетрудно увидеть что hash имеет достаточно начальных нулей (17), чтобы удовлетворять критериям сложности для биткоина в момент создания блока. Исходя из того, что все цифры после первых 17 могут быть любыми, получаем 16^47 (то есть 16^(64-17)) возможных вариантов, которые могут быть найдены при условии критериев сложности (3.92 * 10^56). Еще раз требуется вся вычислительная мощность майнинг сети в течении 10 минут чтобы найти один hash удовлетворяющий условиям.
Чтобы взломать hash с учетом первых 17 нулей, экстраполируя вышесказанное получаем, что потребуется 10 * 3.92 * 10^56 минут для взлома SHA256 при существующей мощности глобальной сети майнеров. А это скорее всего долгое время )
если взять нейросеть, скормить ей алгоритм шифрования, прогнав большой массив с известными входными и выходными данными и пусть следит за отклонениями вероятностей. то есть поискать зависимости на всем известном. возможно будет понятно, работает метод или нет.
я сам ни разу не программист, но вдруг я что-то умное сказал?
я сам ни разу не программист, но вдруг я что-то умное сказал?
Отличная работа! Тоже брался взломать sha256 (или оптимизировать алгоритм перебора nonce хотя бы кратно). Начало статьи — как собственные действия. Классная идея и пища для анализа изменения единичных битов. Текст знаком духом :)
Однако я пришел к выводу, в конце концов, что, и за это необходимо сказать спасибо дальновидности Сатоши, любой анализ nonce бессмыслен в силу двойного sha; все было во много раз легче (хуже для биткоина), если бы заголовок хешировался однократно.
Ваш вероятностный подход прекрасен, но скорее всего только как попытка. Поскольку смешение битовых и арифметических действий в раундах дают то свойство функции, когда выявленное свойство работает на одних входных, но не работает на других.
Однако я пришел к выводу, в конце концов, что, и за это необходимо сказать спасибо дальновидности Сатоши, любой анализ nonce бессмыслен в силу двойного sha; все было во много раз легче (хуже для биткоина), если бы заголовок хешировался однократно.
Ваш вероятностный подход прекрасен, но скорее всего только как попытка. Поскольку смешение битовых и арифметических действий в раундах дают то свойство функции, когда выявленное свойство работает на одних входных, но не работает на других.
Гениально, пока читал получил море удовольствия, на минусяторов не обращайте внимание — как минимум такие алгоритмы отличная разминка для ума, прошу — пишите еще!
dblokhin: & Ztare: вероятно смогу найти своё решение этой задачи с помощью нейросети в начале 2010х. Эксперимент был прекращен при достижении сетью размера 4Тб. =)
может быть коллективный разум справится? И да там был 1 проход но тоже очень прибыльно… теоретически ;)
может быть коллективный разум справится? И да там был 1 проход но тоже очень прибыльно… теоретически ;)
Sign up to leave a comment.
Вероятностный метод майнинга Bitcoin