ある種のEdDSAの実装に対するDouble-PubKey Oracle Attack

話題はこれ↓

www.reddit.com

詳しい話はこれ↓

blog.safeheron.com

興味があるところだけ書くと、EdDSAの署名は秘密鍵 $x$ 、公開鍵 $A = xG$ として、平文 $m$ を受け取って次のように計算した $(R, S)$ の組*1。詳しくはwikipediaとかを見てください。

$r = h(h_{\{b \dots 2b-1\}}(k) || m), R = rG$
$e = h(R || A || m)$
$S \equiv r + ex \mod q$

ここで署名のロジックが入力として $(k, m, A)$ を受け取っているとき、 $(R, S) = sign(k, m, A), (R, S') = sign(k, m, A')$ のように不正な公開鍵 $A'$ を渡して、これが計算されてしまうとECDSAにおけるnonce reuse attackのような感じで $x$ が計算できる。

具体的には $S \equiv r + ex \mod q, S' \equiv r + e'x \mod q$ で、 $r, x$ が未知なので2式で引き算をして $r$ を消すと $S - S' \equiv (e - e')x \mod q$ になって、 $x = \frac{S - S'}{e - e'} \mod q$ とやって $x$ が得られる。

上述のポストなどでは署名するロジックは $A$ は受け取らずに自前で計算するか、受け取ってもそれが $k$ に対応したものであることを確かめましょうといってる（まあこれは計算して一致するか見ることになる）。

個人的には引数に誤った値を渡したらロジックが思わぬ挙動になって結果的に困るみたいなのはそうですねと思うんだけど、特にredditの記事では割と深刻っぽい雰囲気で書いてある。誤用しうる状態すらも許せないってことなんだろうか。実際これが攻撃やバグにつながるかと言われると、それこそCTFでくらいしかそういうシチュエーションにならないような気がするし、これで問題を作れって言われても自然な形にするのにはだいぶ苦心することになるだろうな、と思う。暗号界隈的にはどういう受け止め方をされているんだろう。気になる。

redditのスレちゃんと読んでなかったけどCTFでは既出らしいです ctf/2018-12-08-hxp/crypto_uff at master · p4-team/ctf · GitHub

*1:ここで $R$ は曲線状の点だけど $S$ は整数なので注意。あと $k$ は $x = h_{0 \dots b-1}(k)$ であるシード