id0-rsa.pubのメモ【ECDSA Nonce Recovery】

ctf crypto

ECDSA Nonce Recovery

same k attackの話。以下問題文。

As part of signing something using DSA (digital signature algorithm) one must select a secret, cryptographically secure random number k to be used as a nonce. k must never be reused. Why you ask? Well you could ask Sony, or I could just tell you that you can recover k given two signature / message pairs that used the same k and signing key, which can lead to the signing key being compromised. I've signed two messages (z1,z2) with the same k (using the NIST curve P-192), resulting in the signatures (s1,r1) and (s2,r2). Your job is to recover k

(submit your answer in hex). Some reading to get started (of most relevance is section 2.3).

z1 = 78963682628359021178354263774457319969002651313568557216154777320971976772376
s1 = 5416854926380100427833180746305766840425542218870878667299
r1 = 5568285309948811794296918647045908208072077338037998537885

z2 = 62159883521253885305257821420764054581335542629545274203255594975380151338879
s2 = 1063435989394679868923901244364688588218477569545628548100
r2 = 5568285309948811794296918647045908208072077338037998537885

n = 6277101735386680763835789423176059013767194773182842284081

same k attackとは、ECDSA、DSA、ElGamal署名あたりの署名アルゴリズムで、二つの別々のメッセージに同じ乱数kで署名を行った場合、kを復元可能という攻撃手法？のこと。割とCTFでは頻出っぽい。（SECCON Beginners2018やVolga CTF 2017でも同様の問題が出題されていた）
とりあえず過去のsolverにブチ込む。以下のような感じで解いてみた。

z1 = 78963682628359021178354263774457319969002651313568557216154777320971976772376
s1 = 5416854926380100427833180746305766840425542218870878667299
r1 = 5568285309948811794296918647045908208072077338037998537885
z2 = 62159883521253885305257821420764054581335542629545274203255594975380151338879
s2 = 1063435989394679868923901244364688588218477569545628548100
r2 = 5568285309948811794296918647045908208072077338037998537885
n = 6277101735386680763835789423176059013767194773182842284081

def inv(x):
  return pow(x, n-2, n)

k = (z1-z2)*inv(s1-s2) % n
print(hex(k))

最初全然Acceptにならなくて困っていたけど、どうやらnを法として計算しないとダメらしい。（ここで初めてnの利用用途に気づく...）
なぜ上記の方程式で復元できるのかはあまりわかっていないので時間があるときにまた調べたい。あと、以前PS3でこの攻撃手法が使えたっぽいことに驚いた。（cryptoも物によっては意外と身近なんだなあ）

参考