Рейтинг:1

Подвержен ли этот простой алгоритм Proof of Work, основанный на SHA256, атаке с увеличением длины?

флаг us

Содержимое каждого блока хэшируется в 32 байта с использованием $\имя_оператора{SHA-256}$ (назовите эту строку $а$). Чтобы блок был принят, должен быть 256-битный одноразовый номер (назовем эту строку $b$) при условии, что $\operatorname{SHA-256}(a\mathbin\|b)$ ($а$ в сочетании с $b$) имеет $N$ или более начальных нулевых битов, где $N$ является параметром сложности.

Является ли этот простой алгоритм Proof of Work основанным на $\имя_оператора{SHA-256}$ восприимчивы к атаке с увеличением длины?

Рейтинг:1
флаг in
  1. Атака с расширением длины изменяет результат хеширования поэтому с большой вероятностью параметры сложности уже недействительны. Из этого $$ h = \operatorname{SHA-256}(a\mathbin\|b\mathbin\|pad1)$$ в этом*. $$ h'= \operatorname{SHA-256}(a\mathbin\|b\mathbin\| \text{pad1}\mathbin\|\text{appended_data} \mathbin\| \text{pad2})$$ Мы не ожидаем, что они будут равными, равенство является незначительным событием.

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

  2. Проверяющие получат $а$ и $b$ и результат хеша $ч'$ (ограниченный размер является ключевым здесь). Когда они вычисляют значение хеш-функции, они будут вычислять $h = \operatorname{SHA-256}(a\mathbin\|b)$ и они это увидят $ч \neq ч'$ и равенство является незначительным событием.

    Даже если они имеют одинаковое хеш-значение или допустимый параметр сложности, правильно реализованный клиент увидит атаку.

Следовательно, при правильной реализации атака с увеличением длины не является проблемой. Однако не полагайтесь на реализации, поскольку они могут быть неверными, используйте двойной SHA-256, как это делал Биткойн. В качестве альтернативы используйте устойчивые к расширению длины хеш-функции, такие как SHA-512/256, BLAKE2/3, SHA3-256.

Имейте в виду, что POW требует много работы, поэтому выбор двойной SHA-256 был неплохой идеей когда началось проектирование биткойнов.


*Прокладки
$pad1$ это дополнение SHA-256, где кулак 1 добавляется как можно меньше 0s так, чтобы при добавлении кодировки длины сообщение было кратно 512. Злоумышленник с расширением длины должен использовать это заполнение, а затем добавить расширенное сообщение, тогда для этого потребуется дополнительное заполнение, поскольку $pad2$, тоже.

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.