Сегодня мы поговорим про недостаток подписи ECDSA, который может стать проблемой для подписывающей стороны.
В статье, посвящённой ECDSA, мы уже упоминали, что она строится на базе эллиптических кривых над конечным полем. Если точнее, используется группа точек эллиптической кривой с заданной операцией сложения точек. Для простоты, мы не будем вдаваться в подробности теории групп и эллиптических кривых. Но важно запомнить, что любая точка R в группе точек эллиптической кривой, кроме нейтральной(бесконечно удалённой точки 𝒪), имеет противоположную точку -R, такую, что:
R+(-R)=𝒪
Точки R и -R отличаются только знаком y-координаты. То есть, если R=(x,y), то -R=(x,-y)
Из-за этого в подписи ECDSA есть небольшой изъян - податливость подписи(malleability).
Свойство податливости заключается в том, что если (r,s) - действительная подпись сообщения M, то подпись (r,-s mod n) тоже будет приниматься как действительная подпись для сообщения M, при этом таковой не являясь. Чтобы показать это, мы используем пару (r,-s mod n) в качестве входных данных для алгоритма проверки подписи ECDSA.
- Вычисляем z₁=(1/-s)·H(M) mod n=-(1/s)·H(M) mod n
- Вычисляем z₂=(1/-s)·r mod n=-(1/s)·r mod n
- Вычисляем z₁·P+z₂·A=(z₁+z₂a)·P=(-(1/s)·H(M)-(1/s)·r·a)·P=
=-(1/s)·(H(M)+r·a)·P=(x₁,-y₁)
Так как s=(1/k)·(H(M)+r·a) mod n, то умножив левую и правую часть этого равенства на (1/s)·k, мы получаем k=(1/s)·(H(M)+r·a) mod n. Поэтому:
(x₁,-y₁)=z₁·P+z₂·A=-(1/s)·(H(M)+r·a)·P=-k·P=-R=(xᵣ,-yᵣ)
- Так как x₁=xᵣ, то x₁ mod n =r. Следовательно, подпись (r,-s mod n) будет принята.
Теперь поговорим, к чему может привести податливость подписи ECDSA в контексте Биткоина. Подписи в Биткоине нужны для доказательства владения монетами. Точнее, если вы владеет парой секретный/открытый ключ от конкретного адреса, то вы владеет всеми монетами на нём. Поэтому вы можете перевести эти биткоины другому пользователю сети, доказав право владения монетами посредством подписания транзакции своим приватным ключом.
В Биткоине подпись - это часть данных транзакции. В самом простом сценарии, чтобы потратить монеты вам нужно сгенерировать подпись и включить её вместе с соответствующим открытым ключом в данные транзакции.
Более подробно о структуре транзакций мы поговорим в одной из следующих статей. Сейчас же просто представьте, что транзакция состоит из множество кирпичиков, каждый из которых несёт в себя определённую информацию о транзакции. Один(или больше) из таких кирпичиков содержит в себе подпись (r,s).
Для того, чтобы получить идентификатор транзакции - txid, который поможет вам найти вашу транзакцию и который в том числе используется для связи между транзакциями, нужно дважды хэшировать эти данные.
Таким образом, мы получим 32-х байтный идентификатор транзакции.
Однако мы знаем, что помимо реальной подписи (r,s) может быть также принята и подпись (r,-s mod n). Тогда транзакция, состоящая из тех же данных, но с подписью (r,-s mod n), фактически останется той же самой. Информация об отправителе, получателе, сумме перевода не поменялась. Изменилась только подпись.
Но как это небольшое изменение в данных повлияет на txid транзакции.
Он будет абсолютно другим. Это связано с так называемым лавинным эффектом криптографической хэш-функции: изменение даже в один бит повлечёт за собой полное изменение хэш-значения.
К чему же это может привести? Представим, что у нас есть пользователь Алиса, которая взяла в долг 1 биткоин у пользователя Боба. Настал день возврата средств, и Алиса собирает транзакцию для перевода Бобу одного биткоина. В том числе Алиса генерирует подпись для этой транзакции. Собрав транзакцию, она дважды хэширует данные и получает идентификатор транзакции txid₁. Его она передаст Бобу для отслеживания появления транзакции с txid₁ в списке подтвержденных. Дальше Алиса должна отправить транзакцию в p2p сеть нод Биткоина, где помимо обычных нод пользователей есть и ноды майнеров. Транзакция Алисы будет передаваться по этой сети от одной ноды к другой. Затем в какой-то момент майнеры, получив транзакцию Алисы, решат включить её в новый блок. Это начнёт гонку по решению задачи поиска подходящего хэш-значения в рамках Proof-of-Work алгоритма. После включения транзакции в новый блок, она считается подтвержденной, а платёж - осуществленным.
Но что, если Боб - нечестный пользователь и обладает необходимыми техническими возможностями, чтобы окружить ноду Алисы своими нодами и перехватывать её транзакции до их передачи на другие ноды. В этом случае у Боба появится шанс подменить в транзакции Алисы подпись (r,s) на (r,-s mod n). Затем он, используя двойное хэширование, вычислит новый идентификатор транзакции - txid₂. После этого он передаст соседним нодам ту же транзакцию Алисы, но с идентификатором txid₂. Именно с этим идентификатором транзакция Алисы распространиться по сети и будет включена майнером в один из новых блоков, тем самым пополнив кошелек Боба на один биткоин.
Однако теперь Боб может потребовать от Алисы повторить платёж, так как в блокчейне нет транзакции с txid₁, тем самым попытавшись убедить её в том, что он не получил один биткоин. Если Алиса - наивный пользователь, который не пойдёт проверять отправленные транзакции в своём кошельке или не откроет адрес Боба в каком-либо Биткоин эксплорере(например https://www.blockchain.com/), чтобы проверить приходил ли ему один биткоин с её адреса, то она может повторить платёж. Таким образом, Алиса будет обманута Бобом и перешлёт ему не один биткоин, а два.
Способы решения проблемы податливости транзакции:
- Low s-value. Предложен в BIP-062. Согласно этому предложению принимались только подписи, у которых s значение находилось в промежутке
от 0x1
до 0x7FFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF 5D576E73 57A4501D DFE92F46 681B20A0 - Segwit(Segregate Witness). Предложен в BIP141. Фактически подписи выносятся за пределы данных транзакции, которые используются для получения идентификатора транзакции посредством хэширования.
- Подпись Шнорра. Предложена в BIP340. Реализация подписи Шнорра не подвержена проблеме податливости подписи.
Если говорить о реальных примерах эксплуатации этого недостатка ECDSA в рамках Биткоина, то самый известный на сегодняшний день случай - атака на биржу Mt.Gox в 2014 году. Согласно отчётам, биржей было потеряно около 849600 биткоинов, и по крайне мере 386 биткоинов были украдены с помощью эксплуатации податливости подписи ECDSA.
Однако стоит заметить, что на сегодняшний день такая атака практически невозможна. Во-первых были введены три механизма, которые разными способами предотвращают эту атаку(low s-value,segwit,подпись Шнорра). Во-вторых, сама атака подразумевает некоторый элемент социальной инженерии и была более вероятна в первые годы существования Биткоина, когда лишь горсть людей понимала что такое Биткоин и как он работает. Сейчас ситуация кардинально меняется: люди всё лучше и лучше разбираются в криптовалютах, появились криптовалютные эксплореры и другие механизмы проверки транзакций. Это не значит, что людей нельзя обмануть, всегда найдутся наивные или не желающие учится люди, но хочется верить, что с каждым годом процент хорошо осведомленных, не наивных пользователей будет расти.