RFC 6979を使った結果がライブラリによって違った→私の間違いだった

2017/04/05更新：mbedTLSに問題がなかったので更新

突然のRFCだ。
ESP8266のこともやりたいのだけど、仕事の調査もあるのでね。。。
せっかくなので、書いても問題なさそうなところは使おう。

---

RFC 6979という、楕円曲線を使った署名についてのRFCがある。

RFC 6979 - Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA)

私の把握では、

• 楕円曲線暗号の署名の乱数って、面倒よね
• そもそも、乱数が乱数かどうかなんてあやしいし
• 別の署名で同じ乱数が使われたりすると、目も当てられないわ
• じゃあ、いっそのこと、データによって乱数の値が変わるような計算式を作ってしまわない？
• さんせいさんせい！！

というところだ。
RFC 6979に基づいた署名計算を行うと、乱数要素がなくなるので、毎回同じ署名結果が得られる。

---

それはよいのだが、この決定性署名(Deterministic Signature)を持つ暗号化ライブラリを使ったのだが、結果は乱数を使っていないので同じ結果になるものの、ライブラリによって得られる署名が異なることがあった。

やむなくRFC 6979を見てみたが、うん、全然わからん。。。
ただ、3.2章が「Generation of k」で、3.3章が「Alternate Description of the Generation of k」となっている。

Alternate Description ?
別の説明、ってなんだ？
3.2章で使った用語とは別の言葉(X9.62の用語か)で説明しているだけだとは思う。

たぶん、kは、ここの手順3の整数kだと思う。
「セキュリティ」のところにもそう書かれていた。
https://ja.wikipedia.org/wiki/%E6%A5%95%E5%86%86%E6%9B%B2%E7%B7%9ADSA#.E7.BD.B2.E5.90.8D.E7.94.9F.E6.88.90

 

一致しているライブラリは、先にnonceを求めてから署名を行っている。
nonceは、たぶんkのことだろう。乱数っぽいし。
困ったことに、一致していないライブラリは違う計算方法で、直接比較ができない。

mbedTLSなのだが、うーん、どうしたものか。。。
https://github.com/ARMmbed/mbedtls/blob/development/library/ecdsa.c#L72
nonceを作らず、f_rngでうまいことやるようなのだが、乱数っぽい値はtに入るようだし、kはkeypairとかから設定されているし、なんだかよくわからんのだ。

---

2017/04/05

この問題はけっこう大きいので、引き続き調査を行う。
まあ、違う実装を使えばよいと言えばよいのだけど、それでは負けた気がしてしまう。。。
mbedTLSは負けないのだ！

間違われないように書いておくが、署名が間違っているわけではないのだ。
verifyは成功する。
単に、署名が一致しないだけなのだが、それがあり得るのかどうかだけが気になっているのだ。

 

mbedTLSの実装でDeterministicっぽいことをしているのはここだと思う。
https://github.com/ARMmbed/mbedtls/blob/development/library/ecdsa.c#L178-L182

よくわかってないが、HMAC_DRBGという言葉が出てくるので、RFC6979の3.3章のような実装なのだろうか。
この辺で設定したrng_ctxを使ってECDSAの署名に使う乱数を作っているのだろうと思う。
呼び出すのは、mbedtls_hmac_drbg_random()。
これを使っているのが、L97のgen_keyapir()と、L121のfill_random()。
RFCと実装が一致しているのかを確認するのは、私にはちょっと難しい。。

でも、mbedTLSもちゃんとtestsuitesでRFC 6979に載っているデータのパターンはOKなのだよ。。。
だから、間違えているとは考えにくい。
例えば、RFCのA.2.3は、この辺がテストデータになっている。

 

全部正しいのに結果が違うということがあり得るとしたら、エンディアンじゃなかろうか？
RFC 6979にはbig-endianと書かれているけど、与えているハッシュ値がlittle-endianになっているからとか。
しかし、いろいろひっくり返したものの、署名は一致しなかった。

なんでだ？？
そんなことあり得るのか？？？

 

わからなくなって、変更したところを元に戻し、自分のmbedTLSを使った処理を見直してみた。
あれ・・・署名計算だけしか見てなかったから気付かなかったけど、そもそもの署名計算に与えている値を間違えている・・・？
pythonで作ったのと同じパラメータになるように修正して・・・

あーーー、一致したーーーー
疑ってごめん、mbedTLS。
やっぱり私が間違っていたよ。。。