※本ブログは2024/2に執筆されています。そのため、アップデートによってここに記載されている内容が現状と乖離する可能性があります。記載する内容を参照する場合は自己責任でお願いします。

はじめに

こんにちは! ドワンゴでエンジニアをやっている小林と申します。競技プログラミングを趣味にしています。

今回は業務には関係ありませんが、個人的に興味のあるトピックであるセキュリティーについて執筆します。

対象読者: 以下のどれかを満たす人

• AtCoder で青色〜黄色以上、あるいは意欲のある水色以上
• 暗号理論に興味のある人
• 数学が好きな人

また、簡単な群論の知識を仮定します。(群の定義など)

まとめ

• セキュリティーの強さはセキュリティーレベルと呼ばれる尺度で測ることができます。 \(k\) ビットセキュリティーはおよそ \(2^k\) 回の計算を要するレベルです。
• \(n\) ビットの楕円曲線暗号方式は \(n/2\) ビットのセキュリティーを提供します。 \(n \ge 224\) であれば 112 ビットセキュリティー以上が提供されるので 2024 年現在安全です。特によく見かける Ed25519 や ecdsa-sha2-nistp256 あたりは 128 ビットのセキュリティーを提供するので安全です。

事前知識

セキュリティーレベルとは

https://en.wikipedia.org/wiki/Security_level から引用します。

In cryptography, security level is a measure of the strength that a cryptographic primitive — such as a cipher or hash function — achieves. Security level is usually expressed as a number of “bits of security” (also security strength), where n-bit security means that the attacker would have to perform 2^n operations to break it, but other methods have been proposed that more closely model the costs for an attacker. This allows for convenient comparison between algorithms and is useful when combining multiple primitives in a hybrid cryptosystem, so there is no clear weakest link. For example, AES-128 (key size 128 bits) is designed to offer a 128-bit security level, which is considered roughly equivalent to a RSA using 3072-bit key.

翻訳すると以下のようになります。

暗号学において、セキュリティーレベルとは、暗号やハッシュ関数といった暗号プリミティブが達成する強さの尺度である。セキュリティーレベルは通常「〇〇ビットセキュリティー」(あるいはセキュリティーの強さが〇〇ビット)と表現され、 \(n\) ビットセキュリティーというのは攻撃者がそれを破るために \(2^n\) 回の操作を要するであろうということを意味する。しかし攻撃者にとってのコストをより厳密にモデルするような他の方法も提案されている。このセキュリティーレベルの概念により、複数のアルゴリズムの便利な比較ができ、ハイブリッドな暗号システムで複数の暗号プリミティブを組み合わせるがゆえに明らかな最弱の繋がり (訳注: 一番の弱点) がない際に有用である。例えば、AES-128 (鍵のサイズが 128 ビット) は 128 ビットのセキュリティーを提供するように設計され、このセキュリティーレベルはおよそ 3072 ビットの鍵を使う RSA と等価であるとみなされている。

競プロの人向けに書くと、要するに計算量が \(2^n\) であれば \(n\) ビットセキュリティーが担保されています。2030 年まで使用されているものは 112 ビットセキュリティーが達成されていればよく、言い換えると \(2^{112}\) ステップの計算は 2030 年までは人類には不可能と思われています。

離散対数問題

群 \(G\) および \(G\) の要素 \(g, h\) が与えられた時、 \(g^x = h\) という方程式を解かせる問題を離散対数問題と呼びます。

• 例: \(3^x \equiv 56306 \pmod{65537}\) である。x は何か? (答え: 47 など)
• 例: 以下の ssh-ed25519 公開鍵に対応する指数は何か?

  ssh-ed25519 AAAAC3NzaC1lZDI1NTE5AAAAIJVH04Oyf0Y7FrilmJMVENUBS6SMfyrhQ6L4lGGuBYsj
  

楕円曲線暗号方式

楕円曲線を使う暗号プリミティブを総称して楕円曲線暗号方式と呼びます。

単純化したデータは以下の通りです。

• \(p\): 素数。楕円曲線が定義される有限体の位数。
• \(y^2 \equiv x^3+ax+b \pmod p\): 楕円曲線の方程式。¹これを満たす \(x,y\) の集合を G と呼ぶ。G は群である。
• \(|G|\): \(G\) に含まれる要素の個数であり、\(G\) の位数と呼ばれる。多くの場合、素数であるか、素数を小さな整数倍したものである。

普段使われている Ed25519 は、位数が \(2^{256}\) 程度の群を使用しています。² また、もう一つよく使われる方式である ecdsa-sha2-nistp256 という方式は、NIST P-256 と呼ばれる曲線を使用しています。こちらも位数が \(2^{256}\) 程度の群を使用しています。

基本的に楕円曲線暗号方式は楕円曲線を群とみなしたものの上の離散対数問題の安全性に依存しています。

攻撃手法

基本的に大きさ \(2^{n}\) 程度の群における離散対数問題は \(n/2\) ビットセキュリティーを提供します。これは \(x\) の総当たり (\(O(2^n)\) ステップ) よりも高速に離散対数を求める手法が存在するということです。その説明のために、攻撃手法を見ていきます。AtCoder でのレベル感はおよそ青色〜黄色と思われます。

Baby-Step Giant-step

ABC270 の G 問題 で出題されたのが記憶に新しいです。

1. \(M := 2^{n/2}\) とする。 \(g^{M}, g^{2M}, g^{3M}, \ldots, g^{(M-1)M}\) を計算しておき、マッピング \(S\) を \(g^{M} \mapsto M, g^{2M} \mapsto 2M, \ldots\) という方式で作っておく。
2. \(t := g, g^2, \ldots, g^{M-1}\) に対して \(ht^{-1}\) が \(S\) に含まれるかを調べる。 \(S\) に \(h(g^{i})^{-1}\) が含まれており対応する値が \(v\) であったならば、 \(h(g^{i})^{-1} = g^v\) であるから \(h = g^{v+i}\) であり、求めるべき離散対数は \(v+i\) である。

これは \(O(M) = O(2^{n/2})\) 時間、 \(O(2^{n/2})\) 空間で動作します。 (ただし、マッピングからの値の取得が \(O(1)\) 時間でできることを仮定します。)

ポラードのロー法

Floyd の循環検出法を使います。これは以下のようなアルゴリズムです。

• 入力: 関数 \(f : G \to G, a \in G\)
• 出力: \(f^i(a) = f^j(a)\) となる \(i \neq j\)
• アルゴリズム:
  1. \(x := a, y := a\) とする。
  2. \(x \leftarrow f(x), y \leftarrow f(f(y))\) とする。
  3. \(x = y\) となるまで上を繰り返す。サイクルがあれば必ず \(x = y\) となる時が来るので、それまでに 2. を k 回実行していたら \((k, 2k)\) を返す。

これの空間計算量は O(1) です。 \(f : G \to G\) をランダムな関数とすると、誕生日のパラドックスから \(O(\sqrt{|G|})\) 回程度で \(f^i(a) = f^j(a)\) となる \(i \neq j\) が見つかることが期待できます。

Wikipedia の例では、以下の関数を使っています。

• \(G\) を 3 つの部分集合 \(S_0, S_1, S_2\) の和として分割する。これらの部分集合は共通部分を持たない。(実装するときはハッシュ関数などを使う。)
• \(x \in S_0\) のとき \(f(x) = hx\)
• \(x \in S_1\) のとき \(f(x) = x^2\)
• \(x \in S_2\) のとき \(f(x) = gx\)

これで \(f^i(a) = f^j(a)\) となる \(i, j\) が見つかった際、上のルールから \(f^i(a) = g^sh^t, f^j(a) = g^uh^v\) となる \(s,t,u,v\) が見つかっているはずですが、\(s \neq u, t \neq v\) であることが期待できるのでその差分から離散対数が計算できます。(式変形すると \(h^{v-t} = g^{s-u}\) なので \(x=(s-u) / (v-t) \bmod |G|\) が答えです。)

ループにハマるまでの回数の期待値が \(O(\sqrt{|G|})\) であるため、 これは \(O(2^{n/2})\) 時間、 \(O(1)\) 空間で動作します。

想定質問集

112 ビットセキュリティーで良い根拠は何ですか?

https://www.cryptrec.go.jp/list/cryptrec-ls-0003-2022r1.pdf の 表 5 (p.16) を参照します。 ここで「112 ビットセキュリティ」の行と「2022～2030」の列が交わるところを見ると、「移行完遂期間」とあります。移行完遂期間であれば使用は問題ありませんので、2030 年までは大丈夫です。

楕円曲線暗号方式にはこれより良い攻撃手法はないのですか?

一般のパラメーターにはまだ見つかっていません。特殊な形のパラメーターには見つかっており、以下はそういった例です。

• 位数が \(p\) の場合: additive transfer という手法で \(ax \equiv b \pmod p\) を解くことに帰着できます。これは mod 逆元で簡単に解けるので、こういったパラメーターは全く使い物になりません。
• 位数が \(p-1\) の場合: multiplicative transfer という手法で \(a^x \equiv b \pmod p\) を解くことに帰着されます。これも離散対数問題ですが、有限体上での離散対数問題なので汎用的な攻撃手法より高速に解けます。p が 256 ビットの整数だとおよそ 47 ビットのセキュリティーに相当するレベルとなり、これは普通に人類が解けるレベルです。

Ed25519 などの楕円曲線暗号方式の解読には、総当たりで \(2^{256}\) 回の操作が必要だと聞きました。これは誤りなのですか?

はい。この記事で見たように、もっと高速に解けるので誤りです。 こういった説明は時々見かけますが、よくて勘違い、悪くて優良誤認表示になってしまうでしょうね。

でも \(2^{256}\) と \(2^{128}\) は何が違うのですか? どのみち解けないのだから一緒じゃないですか?

今は一緒かもしれませんが将来差が出てきます。 同じく https://www.cryptrec.go.jp/list/cryptrec-ls-0003-2022r1.pdf の 表 5 (p.16) を参照します。 「128 ビットセキュリティ」の行を見ると、「2041～2050」まで問題ないことがわかるので、2050 年以降に差が出てきます。

RSA 暗号方式はオワコンですか? 今私は SSH の鍵として ssh-rsa の鍵を使っているのですが、新しく作り直した方がいいでしょうか?

いいえ。わざわざ新しく作り直す必要はありません。

しかし個人的には、もし鍵を新規で作るのであれば ssh-rsa ではなく ssh-ed25519 などの鍵を作ることを推奨します。その理由は以下の通りです。

• 鍵の扱いやすさ: 128 ビットセキュリティーを達成するために、RSA だと 3072 ビットの鍵が必要ですが、ssh-ed25519 であれば 256 ビットで済みます。12 倍の差があります。(これは公開鍵の話であり、秘密鍵だとさらに差が広がります。)
• 実装の簡単さ: RSA を安全に実装するのは難しいです。多くの実装は演算のために多倍長整数を使っていますが、これは Go 言語で問題とみなされ修正されました。最近も脆弱な実装が見つかりました。RSA はその単純さから多くの場所で教えられていますが、その有用性が過大評価されていると感じます。