Bitcoin Forum

Hello.

  Кому-нить попадался сам полином в математической записи по которому считается SHA?

Ну примерно вот как CRC алгоритм описан, полиномом, а не алгоритмом
http://ru.wikipedia.org/wiki/Циклический_избыточный_код

А то SHA описан в форме алгоритма на псевдокоде(а выковыривать оттуда полином лень ;) )
http://ru.wikipedia.org/wiki/SHA-2

Vladimir

Наверно, такой полином не существует.

должен быть - они же из чего-то писали алгоритм!

Да и для доказательств стойкости нужно иметь математическую запись.

Да, на основе чего-то. Не обязательно полинома.

Вот здесь (http://www.iwar.org.uk/comsec/resources/cipher/sha256-384-512.pdf), например, есть математическая запись. А для доказательства стойкости к чему-либо, в первую очередь нужно знать, что это – что-либо. :)

там же вроде даже аппаратная последовательная схема приведена?..

Такие схемы 1:1 описываются полиномом.


Ладно, спросим по-другому ;) 

Последовательная реализация в виде схемы или логических функций где-нить описана?

на википедии

Э... можно вопрос?
Что значит фраза "полином по которому считается SHA" ?
Вы сами понимаете, чего спрашиваете? Похоже, что нет.
Каким еще полиномом CRC описан? Принято говорить, что CRC "порождается полиномом", но при этом всегда уточняют, что это значит.
Кстати, CRC это обратимая функция в отличие от SHA.
Если же, вдруг, речь идет о какой-нибудь дизъюнктивной нормальной форме записи любой логической функции,  то зачем она вам? Она (даже для одного блока) займет несколько страниц мелкого текста и будет непригодна вообще ни для чего кроме как показывать девочкам...

Зачем ты наступаешь на горло нашему потенциальному великому математику, второму Перельману, можно сказать?

будет пригодна для формальных преобразований при помощи компьютера.

У меня была такая же идея
За счет чего вычисления можно оптимизировать:
1) функция вычисляется не один раз, а два раза подряд;
     (возможна оптимизация места склейки)
2) цель - не вычисление функции, а подбор значения дающего результат с нужным числом лидирующих нулей;
     (т.е. проводить вычисления только тех битов, которые должны стать нулевыми)
3) убедится надо в том, что нужные биты станут нулями (а не скажем единицами).
     (т.е. сократить функцию, зная её требуемое значение)
4) при переборе хешируемое значение меняется не целиком, а только его вариабельная часть
     (т.е. кешировать(вычислять единственный раз) часть промежуточных результатов вычислений)

Всё это ведет к уменьшению числа необходимых логических элементов,
следовательно, к увеличению количества вариантов, перебираемых на одном кристалле за единицу времени (при параллелизации перебора),
т.е. к росту скорости.

Может быть будет даже возможно программирование FPGA на лету для каждого нового блока по-своему
Перепрограммирование FPGA существенно быстрее, чем временнОй интервал между двумя блоками:

Во, уже теплее ;)

п.1 дает конечно не большой рост скорости за счет того что несуществующие коды можно сразу не перебирать, но эти несколько процентов от всего пула дают приличный доход...

остальные дают куда более значительный рост скорости, не исключено что и 386 станет уже достаточно ;)

я так понимаю, тут уже два "потенциально великих математика"?

Написанное в пунктах 1-4 почти полностью бред.
Теоретически, какие-то крохи собрать на этом можно, но, в общем, не удастся поднять быстродействие даже на 10%.


PS. любой лидирующий ноль зависит от ВСЕХ входных бит второго SHA2. Таким образом, для выяснения этого (любого) бита нужно целиком и полностью выполнить первый SHA2. Здесь нет поля для оптимизации. Лучше уж бейтесь над обращением самой функции SHA2. На этом можно заработать значительно больше, чем количество всех нагенеренных биткоинов...

кому-то крохи, кому-то хлеб.

кстати, пункты 2 и 4 давно реализованы в fpga-майнерах. Пункт 4 - благодаря использованию "midstate", а пункт 2 выполняет сам компилятор автоматически - всю логику, которая не влияет на результат (а результатом считаются только лидирующие нули), компилятор выбрасывает из проекта. Разработчику об этом даже думать не нужно.

Дополнительное веселье вызывает (кстати, "на лету" и "налету" это разные слова):
Сколько там по-вашему? 92ms? У меня через 60-70ms уже ответ из устройства выходит...
А еще эту прошивку нужно с диска прочитать, а еще и в fpga передать, как правило по небыстрому каналу. А компилировать, если вдруг придется, то это на часы растянется...

сравнение котлет с устрицами. В вычисление блока Вами за 60-70ms как-то не верю, а одной шарой больше, одной меньше -
может лучше "пол дня тренироваться, а потом за полчаса долететь".


Это если компилятор неспециализированный. Кстати, что он там такое трудоемкое вычисляет?


Если бы Вы написали популяризирующую статью как Советский Ученый - никаких бы претензий к Вам не было.
А так приходится разжигать ненависть к вашей социальной группе буржуазных морд (чё-то у меня перегибы пошли, из-за вас всё)

Кстати, btcsec.com предлагает по 3 BTC за статью.

во, сразу видно как думают не хакеры и не математики ;))

Вот у меня например как тока узнал что там двойной SHA сразу-же первая мысль "а не дырка ли это?.." ;)

К тому-же судя по всему вы еще и с аналитическими преобразованиями совсем не дружите(а я аналитик :) )

Итого:

1  Двойная функция после преобразования превращается в одинарную, хоть она и более высокого порядка, но считать быстрее.

2  Возникают коды, которых быть не может вообще - их можно вычислить и не тратить время на перебор

3  Даже 10% это не мало - если это например будет 10% от всего пула, в карман...


PS  но похоже двойной SHA таки сработал, да ;)

Если вы тут такие крутые матеметики, то скжите свое мнение на счет этого... https://bitcointalk.org/index.php?topic=92423.msg1190132#msg1190132 и ниже... Я тоже заметил странную закономерность когда таблицы делал для брутфорсера...  :-\

Очень жаль, что эта мысль (единственная, похоже), возникнув так и повисла в воздухе. Настоящий математик сам себе бы на этот вопрос смог бы ответить :)



А я криптоаналитик. И че?

Двойная функция хоть и не сильно, но снижает криптостойкость. 

К тому-же это еще от структуры полинома зависит - может и сильно снижать.

а я папа римский ;)

PS  хочешь сказать что обходишься без аналитической формы SHA, или издеваешься просто?
Какие программы знаешь для аналитических преобразований?

Я наверное недопонимаю, но я думал что пошагово SHA256 описан в википедии ?

Слышишь, аналитик-папа римский, я достаточно много ответов дал на твои вопросы. Ты же способен только задавать вопросы. Ни одного ответа или аргументированного "аналитического" утверждения от тебя не прозвучало. Так что тебе нужно доказывать, что ты аналитик, а не окружающим...

Ты даже в терминах не разбираешься.
Ты в своей жизни видел хоть одну "аналитическую форму" хоть какого-нибудь, применяющегося на практике криптоалгоритма? Приведи пример?

да, но там он в форме алгоритма, оптимизированного под 32-битные микропроцессоры.

Точно так-же как и CRC можно описать как полином (там что-то вроде X**16+X**14+...+1) и реализовать
в форме сдвигового регистра с отводами, точно так-же есть форма оптимизированного под 16-битные
микропроцессоры алгоритма, где уже посчитаны 16 или 32 битные константы для алгоритма.
(кстати константы в алгоритме могут быть совершенно разные - например у меня когда пытался
реализовать CRC32 по описанию вообще ничего не получилось, но методом тыка по CRC которые
выдавал архиватор я довольно быстро подобрал другие константы с которыми нормально работало)


Для аппаратной реализации и для аналитического анализа удобнее математическая побитовая форма,
а не алгоритм с константами.

Да уймись уже. Нельзя описать CRC так, как ты хочешь. Твоя писанина безграмотна. CRC можно определить как результат деления одного полинома на другой. При этом первый зависит от входных данных, а второй фиксирован. Ничего общего это описание с твоей ахинеей не имеет.
Но CRC определен так. А ни один криптоалгоритм, в том числе и SHA2 так не определяется.

Если же ты хочешь получить зависимость бит выхода от входных бит в виде уравнений то лопату(компьютер) в руки и пиши программу/считай.
В этом тебе никто не поможет, так как задача изначально глупая, бессмысленная, бесполезная и одурительно трудоемкая.

конечно речь идет о шарах, а не о блоке. Итак, если это не очевидно:
одна шара - это вычисление хэша с 8 лидирующими нулями. Эта задача всегда постоянна и именно за решение этой задачи платят пулы.
А что такое блок? Это хеш с большим и переменным, в зависимости от сложности, количеством нулей. Если вы не умеете аналитически находить 8 нулей, то куда вам соваться в поиск гораздо большего их числа? Кроме того, добавление каждого следующего нуля увеличивает сложность решения поставленной задачи в два раза. Глупо набрасываться на общую задачу, не умея решать ее частный случай. Так что "пол дня тренироваться" лучше на шарах, а не на блоках.
Кстати, "полдня" вместе пишется...

Что значит "неспециализированный"? А какой тогда? Бывают неспециализированные компиляторы? Можете аргументировать свою реплику?


перегибы лучше, чем переломы?

Я не знаю ни одного Советского Ученого, пишущего статьи за 3 BTC.
А ненависть ваша Шариковщиной воняет...

который умеет компилировать схемы любого вида

имеющий специальные оптимизации для схем определенного вида

они как правило все такие.

Это Вы так "культурно" на "слабо" пытаетесь взять?


это легко объяснимо. Их гражданская безответственность привела к развалу Советского Союза,
и случилось это раньше, чем появились биткоины. А теперь они все старые и не могут биткоин освоить.

На "слабо" берут с целью, чтобы человек что-то сделал то, что без "слабо" сделать не может или не хочет.
В данном же случае я пытаюсь вас привести к пониманию того, что вы не сможете аргументировать свою реплику, как со "слабо" так и без него. Просто потому, что не ориентируетесь в том, о чем рассуждаете.
От "слабо" компиляторы, заточенные под (биткоин?)-"схемы определенного вида" не появятся...

в данном случае как раз все наоборот - более общую задачу решить легче, чем частную.
(но там есть нюансы - что-то перебирать возможно придется, но не весь диапазон)

"но мне нравиться ход ваших мыслей"... ;)

Я заявил, что не ориентируюсь как работают HDSL-компиляторы, когда задал вопрос.
Предполагаю, что они там граф на плоскость раскладывают для общего случая.

Вместо ответа на вопрос Вы пересказываете, что этот вопрос отражает мое непонимание.
Нуу, да. Было бы странно задавать вопрос зная на него ответ.

Там обычная оптимизация.  Ничего умного, похожего на аналитику - алгоритмы он не преобразует,
максиум делает оптимальную раскладку по блокам.

Так что смею предположить что ума у него не хватит преобразовать параллельную форму алгоритма в последовательную.

нескучно комуто, задумыватся про алгоритмы.... ::)

Кто знает какая функция или алгоритм рисует вот такой график? http://s004.radikal.ru/i205/1209/cc/6e036f42bdf1.png

Очень похоже на 1-exp(x)

http://ru.wikipedia.org/wiki/%D0%AD%D0%BA%D1%81%D0%BF%D0%BE%D0%BD%D0%B5%D0%BD%D1%86%D0%B8%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B5_%D1%80%D0%B0%D1%81%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5

Доказывай (обосновывай) свои утверждения!
Я математик, доказательство пойму...

Давай и этому утверждению ты приведешь хоть один пример?
Я, к примеру, знаю опровержение этого бреда. Это криптоалгоритмы DES и 3-DES. Первый не рекомендуется к использованию, а второй используется повсеместно и никто до сих пор (публично) и близко не приблизился к его взлому.

А ты знаешь что математикам нобелевку не дают?.. ;)

Чесно говоря не понимаю что тут доказывать - физикам это сразу понятно и так...

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

PS  вот тут че-нить понимаешь? ;)  Особенно где-нить в районе главы 6.1...
web.science.mq.edu.au/~josef/CONTENTS/PHD_THESES/Cameron_McDonald_thesis.pdf
И для тех кто в танке - там и схемка для поиска коллизий есть...
(надеюсь уже никто не думает что биткоин это криптуха? ;)  Ничего общего - задача почти обратная - на поиск коллизий...)

PPS  пусть сначала асики доделают, потом приколимся над ними...

на хабре кто-то уже делал наукообразные потуги...

где-то тут я клал ссылку про многократное примение хэш-функции
http://sites.google.com/site/bitconomika/math

не совсем математически строго - но идея простая - не все множество кодов возможно,
и после повторного вызова функции это множество возможных кодов может тока сокращаться

PS  сильно большое ускорение и не требуется - например 10% от пула где всего 100 клиентов
это в 10 раз больше доход чем от своей фермы.  Как-то так.
(и тока математик может думать что компилятор чипов эти функции сам найдет ;)) )

PPS  кста, если есть интересные ссылки - присылайте - добавлю на сайт.

Прикольно наблюдать как математики ссорятся  ;D
А не потому ли военка США отказались еще в 1997г вроде от SHA, AES и тп лабуды?  8)

продолжаю считать тебя лжематематиком, лжеаналитиком, лжепапойримским.
при чем тут Нобелевская премия? Перельману нашли что дать и без "нобелевки"?
Твои "бытовые рассуждения" не имеют ничего общего с наукой. Лженаука, да и только...

В районе главы 6.1 обсуждается всего-навсего поиск коллизий в алгоритме SHA-1. Коллизии в MD5 и SHA1 обсуждались мировым сообществом лет пять назад. Ничего путевого из этого не вышло. Результата нет, только пшик. Заметь (если сможешь), поиск коллизий - это задача очень отдаленно приближающаяся к взлому алгоритма. Алгоритм хэширования можно считать слабым, если к заданному хэшу можно подобрать какое-нибудь исходное значение. Поиск коллизий же есть поиск ПАРЫ, дающей одинаковый хэш. Вторая задача кроме научного интереса никакой прикладной ценности не имеет.

так что "приколоться над ними" может кто-то и сможет, но это будешь явно не ты, не нужно писать "приколимся" - это не твое.

Кстати, "приколемся" через "е" пишется, а в биткоине SHA2 используется, а не SHA1...

и что из этого следует?
на перебор потребуется не миллион лет, а на 5% меньше? Ты это хотел сказать?

Кстати (для физиков), для выполнения двукратного хэширования требуется в два раза больше времени, так что задача взлома путем перебора не облегчится даже если результирующее пространство в два раза сократится... ;)

ты не поверишь, но мне совершенно пофиг кто там чего обо мне думает...  "я об вас вообще не думаю" ;))

А вот ты явно не сечешь общих принципов, если они не формализованы до уровня готовой статьи, эт я уже понял...



ой ли...

(Может быть эта задача сложнее и не требуется, но коли она уже решена то почему бы не воспользоваться готовым...
Кароч не сечешь фишки, как я и ожидал ;) )


как самокритично ;)


конечно SHA2.  Иначе я бы и не дал эту ссылку ;)

Так-же не дал бы, если бы не был уверен, что ты не сможешь отсюда выудить принцип и перенести на SHA2.
(кстати кто-нить догадался уже?.. )

PS  кто ты по ТИМу, если не секрет?  Че-нить вроде ISTJ?..
http://professionali.ru/Topic/20728708

блин.  Ты вообще замечаешь че-нить, кроме очепяток? ;)

Объясняю второй раз - 5% это тоже не плохо.  Вполне досточно тк их можно положить в карман от всего пула,
а это больше чем доход от своей фермы.



нифига - после преобразования двойная функция превращается в одинарную, что тоже дает ускорение.


биткоин легко ломается и без взлома кодов, но такая задача не стоит (зачем ломать то что приносит доход и так?)

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

(хотя если поймешь принцип синтеза тех алгоритмов, то можно взломать и шифр)

А где второй?

да много способов - самое простое это "51%"

тока ошибка в том что считают что для этого надо много ресурсов - на самом деле все наоборот

то есть чтобы получить 51% не обязательно включать что-то мощное - проще выключить часть того что имеется, это проще...

ломать не строить как говориться ;)

пи...ть - не мешки ворочать! Так говорится.

И сколько ты предполагаешь выключить частей того, что имеется, чтобы получить в руках своих единомышленников 51% ? И как?
А какие еще из "много способов"?

А до второго допрет-таки "где собака порылась" и он уже будет тут всем рулить рано или поздно... И блин это не за горами..  8)

а в чем проблемы-то?  Больше 90% мощности сосредоточено всего на десятке пулов - их вырубить
легко даже без вмешательства провительств элементарной ddos атакой...  
(Оставить только "нужные" пулы которые участвуют в атаке и все)

Через несколько часов мощности с неработащих пулов майнеры сами переключат на работающие,
так что дальше 51% сохраниться даже без блокировки "конкурентов".

PS  издеваешься, или сам до этого не догадался?
Теперь если паламают будешь виноват ;))

PPS  давно пора эти дырки заткнуть.  Есть мысли как?

А те, другие, 50% все сговорились да, кончайте этот бред..

А че другие сделают?..  Согласно алгоритму все кошельки обязаны принять самую длинную цепочку блоков...
(а она будет длиннее там где более 50% мощности, ddos атака легко вырубает более 90%,
к тому-же часть мощности пул через который проводиться атака будет иметь и так)

То есть для взлома даже кошельки трогать не нужно - только слегко перетусовать мощности майнинга, и то на время.

Впихнуть несколько своих блоков - дальше сеть последующие блоки будет сама генерить дальше как обычно.

Но ведь это даст Вам только возможность отменить транзакции, а не "получить контроль" над сетью... Я о том, что ддос когда то закончится ведь... И все встанет на круги своя..

Во-первых - существенная доля мощности находится в соло-майнинге и в неизвестных пулах. До них ддос не доберется.
Во-вторых - владельцы крупных пулов известные и уважаемые люди, обычно, зарабатывающие на этой деятельности. Зачем им твои бредовые "проекты" обрушения сети?
В-третьих - ни один крупный "нужный" пул такую атаку не осилит, им придется кооперироваться.

Тогда зачем чего-то ддосить? Пулы и так могут скооперироваться. Не знаешь, почему они это до сих пор не сделали?

не то, чтобы срач доставлял, но мысли здесь полезные очень были
жаль, что пошел не в ту сферу работать.

зачем отменять?  Наоборот нужно добавить левых...

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



а вот тебя я никак не пойму - толи ты издеваешься надо мной, толи просто элементарных вещей не знаешь...
Ладно, займемся ликбезом ;)

Как тебе ботнетик в миллион компьютеров?..
http://sites.google.com/site/bitconomika/distributedcomputing/virus-nets

Это тока из того что просочилось в печать - реально их может быть гораздо больше...

Так что атаковать хоть 100 хоть 1000 адресов не проблема даже для любого тупого спамера.


Ну и да кстати что скажешь насчет проекта реверсинжиниринга?  (я уже намекал - туго доходит чтоли?)
(пока майнинг жив можно подобных зверушек потрошить и изучать не за свой счет)



ну во-первых не мои, во-вторых с чего ты взял что кто-нить уже давно этим не занимается(ну исчезнут
несколько крупных кошельков вместе с их владельцами - никто и не заметит),
а в третьих вырубить их ddos-ом дешевле и проще чем брать в долю ;)


ты правда читать не умеешь, или всю красоту того что получиться у любого школьника не оценил? ;)

Запустить свой пул не проблема - это любой школьник или спамер может, все готовое есть...

Далее когда пулы вырубаются ддосом что происходит?   Правильно - майнеры САМИ переключают
свои мощности на те пулы которые еще работают!..  Так что помимо "своих" клиентов(их мощностей)
пулы участвующие в атаке АВТОМАТИЧЕСКИ получат дополнительные мощности!  Это произойдет само собой,
даже если атакует полный дурак который этого не понимает...

Красиво? ;)



ну с чего ты взял что еще не сделали - может и сделали...

Это тока школьники пакостят на главной странице сайта ЦРУ, а те кто чуть умнее как видешь
тихо юзают миллионы зараженных маших и делают деньги...




да, кстати - я так понимаю ты этик какой-то(INFJ?) по типу?   Выдумываем всякую удобную чушь,
и свято в это верим?..

Статистику мощностей изучать не пробовал, перед тем как писать чушь в качестве "доказательства"?..
http://blockorigin.pfoe.be/top.php
http://sites.google.com/site/bitconomika/analitic

Тока в первых 4 крупнейших пулах уже 54% мощности сети!..
(причем по личному опыту могу сказать что первые два ТОЧНО находяться под регулярным ddos,
что достало и из-за чего пришлось заморачиваться с поиском других пулов - на них просто работать не возможно,
глючат наверно половину времени.
И хорошо если это просто борьба с конкурентами, а не впихивание левых блоков...)

В первой 10-ке пулов - более 80% мощности сети.

То есть тупая ddos атака всего по 25 адресам полностью вырубает 88% мощности сети,
после чего в течении нескольких часов можно ожидать перехода до 80% мощности на атакующие пулы,
для чего достаточно иметь всего лишь пул в первой десятке(всего 1-2% раскрученности).
(на все остальные и соло значит приходиться всего 12% мощности сети - любой из первых 3 пулов мощнее,
то есть при атаке через пул первой тройки получаем 51% сразу даже без учета переключения мощностей майнерами,
достаточно уже одной только блокировки всего 25 крупнейших пулов, все остальные и соло это мелочи)

The END ;)

Vladimir
PS  ну судя по тому что пришлось разжевывать даже 2*2,
спрашивать как заткнуть эту дырку(особенно в форках где мощностей еще мало) я так понимаю бесполезно?..

PPS  кстати на каких языках пишите?   (пиши-пишите на Ц - спамеры вам спасибо скажут ;) )
http://bugtraq.ru/rsn/archive/2012/06/03.html
(извеняюсь за наглую рекламу Ады ;)) )
Кстати эту ссылку мне чел прислал который запускал свой пул - говорит когда развернул готовый софт
чисто случайно обнаружил что оказывается его выпотрошить весь не проблема совсем...
(Я так понимаю на половине серверов и пулов подобные дырки есть - сколько их еще не описано...)

Использовать p2pool. И создать еще таких пулов  :-\
За ссылочку спасибо

Да, сложно переубеждать человека, если он считает, что 2*2=4. Но вы старайтесь, когда-нибудь получится.

Кстати, представить алгоритм SHA в виде полинома очень легко с помощью интерполяционной формулы Ньютона.

Матан? Делить на ноль нельзя? Хотя как сосчитать время в пути, если скорость равняется нолю?  8)
Делением на ноль вообще можно доказать 2+2=N... ;D

можно.

Но интереснее всего выражения вроде 0/0.

Кстати NaN отлично понимали даже старые компиляторы...

Человеку, который не знает математики, человеком, который её знает. А тут обратный случай.