EdDSA. Исследуем криптоподпись и учимся с ней бороться

Каж­дый ува­жающий себя хакер прос­то обя­зан знать вра­га в лицо и раз­бирать­ся в основных крип­тоал­горит­мах, популяр­ных и не очень. Так, крип­топод­пись EdDSA, нес­мотря на доволь­но широкое исполь­зование (I2P, OpenBSD, OpenSSH и так далее), в отли­чие от сво­ей эллипти­чес­кой сес­тры EcDSA силь­но обде­лена реали­заци­ями в стан­дар­тных крип­тобиб­лиоте­ках. Ее мож­но най­ти раз­ве что в узкоспе­цифи­чес­ких про­ектах типа NaCl, SUPERCOP, python-ed25519 и про­чей экзо­тике.

Слож­ностей добав­ляет и то, что по упо­мяну­той при­чине каж­дый автор реали­зует хеширо­вание, а так­же генера­цию клю­чей и сиг­натур по‑сво­ему. Поэто­му я и решил попод­робнее рас­ска­зать об алго­рит­ме EdDSA, при­чем имен­но с прак­тичес­кой точ­ки зре­ния. Мы раз­берем реали­зацию и работу этой под­писи на кон­крет­ном при­мере.

Предмет исследования

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

Ка­жет­ся, что все в ней прек­расно: в понят­ном тек­сто­вом виде хра­нит­ся и вер­сия, и ID обо­рудо­вания, а так­же вре­мя начала и кон­ца сро­ка дей­ствия в мил­лисекун­дах. Мож­но сме­ло пра­вить и поль­зовать­ся! Но нет, в кон­це мы обна­ружи­ваем поле с нед­вусмыс­ленным име­нем signature, где в шес­тнад­цатерич­ном виде закоди­рован некий 64-бай­товый (512-бит­ный) блок дан­ных.

Дей­стви­тель­но ли это сиг­натура или под­пись тек­сто­вых дан­ных лицен­зии, про­верить эле­мен­тарно: замена любого бай­та в тек­сто­вой час­ти или в самой сиг­натуре дела­ет лицен­зию невалид­ной, и прог­рамма немед­ленно кида­ется пов­торно ска­чивать ее с уда­лен­ного сер­вера. Пер­вый 512-бит­ный хеш, который при­ходит в голову, — это SHA-512, его наличие под­твержда­ет и прог­рамма Krypto Analyzer, если скор­мить ей наш исполня­емый модуль.

То, что это не слу­чай­ный набор бай­тов, а реаль­ная ини­циали­зация под­сче­та хеша SHA-512, нам под­твержда­ет и IDA, в которой мы откры­ваем код при­ложе­ния по любез­но пре­дос­тавлен­ному нам ана­лиза­тором адре­су.

Од­нако счастье ока­зыва­ется не так близ­ко, как кажет­ся: пос­читан­ная кон­троль­ная сум­ма SHA-512 совер­шенно не похожа на зна­чение signature, а зна­чит, для под­писи не годит­ся. Под­пись счи­тает­ся каким‑то иным спо­собом.

Поп­робу­ем коп­нуть с дру­гой сто­роны: най­ти про­вер­ку под­писи в отладчи­ке. Заг­ружа­ем нашу прог­рамму в x64dbg и ищем про­вер­ку под­писи. Прог­рамма написа­на на чис­том C++, ничем не защище­на и сво­бод­на от анти­отладчи­ков, поэто­му иско­мое мес­то находит­ся эле­мен­тарно, в псев­докоде IDA оно выг­лядит так.

Будь мы чуть более ленивы­ми, то закоро­тили бы эту фун­кцию на return 0 (да, при успешной верифи­кации она воз­вра­щает имен­но 0) и успо­коились бы, но тог­да смыс­ла писать эту статью не было бы никако­го. Поп­робу­ем все‑таки разоб­рать­ся, как устро­ена сиг­натура и как она верифи­циру­ется.

Оче­вид­но, что финаль­ную про­вер­ку выпол­няет фун­кция sub_14000517D, которая слож­ным и неп­рямым спо­собом срав­нива­ет на тож­дес­твен­ное равенс­тво две 32-бай­товые пос­ледова­тель­нос­ти. Пер­вую из них IDA-шный деком­пилятор условно обзы­вает a1 + 8. Она пред­став­ляет собой пер­вые 32 бай­та сиг­натуры, то есть в нашем слу­чае выг­лядит так:

Вто­рая пос­ледова­тель­ность вычис­ляет­ся фун­кци­ей sub_1401155E0 и условно называ­ется a1 + 104. Оста­вим пока без вни­мания тре­вож­ный зво­ночек «почему про­веря­ется толь­ко пер­вая полови­на сиг­натуры, зачем тог­да вто­рая?» и тупо поп­робу­ем перепод­писать лицен­зию зна­чени­ем a1 + 104. То есть меня­ем в тек­сто­вой час­ти лицен­зии любой байт, ста­вим точ­ку оста­нова на про­вер­ку, берем новое зна­чение a1 + 104 и под­став­ляем его вмес­то пер­вых 32 байт сиг­натуры.

План кажет­ся надеж­ным, как швей­цар­ские часы, но он не работа­ет: пос­ле замены пер­вой полови­ны сиг­натуры зна­чение a1 + 104 сно­ва меня­ется. Это озна­чает, что пер­вая полови­на сиг­натуры вхо­дит в обе час­ти это­го крип­тоурав­нения. Вто­рая полови­на сиг­натуры тоже находит­ся доволь­но быс­тро — она под условным име­нем a1 + 40 явля­ется аргу­мен­том фун­кций sub_1401162C0 и sub_140114D30 в цепоч­ке весь­ма голово­лом­ного рас­чета про­вероч­ного зна­чения a1 + 104.

Поп­робу­ем все‑таки опоз­нать крип­тоал­горитм. Потыкав­шись по фун­кци­ям, ничего харак­терно­го не обна­ружи­ваем, лишь какие‑то дол­гие, лома­ющие мозг вычис­ления, напоми­нающие опе­рации с BigInteger, коими они, оче­вид­но, и явля­ются. Самой пер­спек­тивной в этом пла­не пред­став­ляет­ся фун­кция sub_1401161B0.