Shogo's Blog

Mar 27, 2024 - 2 minute read -

鍵生成には暗号論的に安全な乱数を使おう

SSHの鍵生成には暗号論的に安全な疑似乱数を使おうという話。 暗号論的に安全ではない疑似乱数がどれだけ危険かというのを、簡単なCTFを解くことで検証してみました。

背景

SSH公開鍵に自分の好きな文字列を入れる、という記事を読みました。

例えばこのSSH公開鍵、末尾に私の名前(akiym)が入っています。

ssh-ed25519 AAAAC3NzaC1lZDI1NTE5AAAAIFC90x6FIu8iKzJzvGOYOn2WIrCPTbUYOE+eGi/akiym

そんなかっこいいssh鍵が欲しいと思いませんか？

かっこいい！真似してみたい！

そこまではいいんですが、問題は実装です。

秘密鍵を生成する際の乱数生成には高速化のために Goのmath/randを使っていますが、乱数が用いられるのは公開しない秘密鍵自体であり、このアルゴリズム自体はLagged Fibonacci generatorのようなので変に乱数に偏りがない限りは大丈夫だろうと思います(追記: これは乱数予測を主とした話)。 (強調 は筆者によるもの)

おっとそれはまずい。 Goの math/rand パッケージは暗号論的に安全な疑似乱数 ではありません 。 SSH秘密鍵のようなセキュリティーが重要な場面では使用してはいけません。

Capture the Flag Challenge

ブログ記事の筆者も math/rand を使ったらまずいことは認識したようで、 かっこいいSSH鍵生成プログラムのREADMEに以下のような追記がありました。

This is a joke software, but there was a serious bug in commit 7db96da05684a86bdbea18319ecc39097d0320d4.

Can you recover the private key generated by the following command? Of course, it can be recovered in about an hour.

% git rev-parse HEAD
7db96da05684a86bdbea18319ecc39097d0320d4
% go run ./main.go -authorized-key-suffix a
2024/03/25 23:51:08 start
2024/03/25 23:51:08 found
% cat out.pub
ssh-ed25519 AAAAC3NzaC1lZDI1NTE5AAAAIBVji5kBXa8PbDP1nk+nysVA89VMg27z98D4aVT/j4Fa

CTF(Capture the Flag)とは一般的には旗取りゲームのことをいいます。 コンピューターセキュリティーの文脈では、情報セキュリティーの知識を用いて、課題の中に隠された秘密の文字列を見つける競技を意味します。

ようするに、以下の公開鍵に対応する秘密鍵を見つけられるものなら見つけてみろ、というわけです。

ssh-ed25519 AAAAC3NzaC1lZDI1NTE5AAAAIBVji5kBXa8PbDP1nk+nysVA89VMg27z98D4aVT/j4Fa

面白そうなので解いてみましょう。

脆弱性を探す

さすがに公開鍵だけから秘密鍵を見つけるのは困難です。 しかし、秘密鍵生成に使われたソースコードが手元にあります。 バグが埋め込まれたというコミットを見てみましょう。

脆弱性があるのはここです。

// https://github.com/akiym/ed25519brute/blob/7db96da05684a86bdbea18319ecc39097d0320d4/main.go#L52
fastRandReader := &fastRandReaderImpl{rand.New(rand.NewSource(rand.Int63()))}

math/rand.NewSource を呼び出しています。 この実装を追って、Goの標準ライブラリのコードを読んでみましょう。

すると math/rand.rngSource 構造体の Seed メソッドにたどり着きます。

// https://github.com/golang/go/blob/50dcffb384cf1693fb113de01c8a36debc6086d1/src/math/rand/rng.go#L203-L214
func (rng *rngSource) Seed(seed int64) {
	rng.tap = 0
	rng.feed = rngLen - rngTap

	seed = seed % int32max
	if seed < 0 {
		seed += int32max
	}
	if seed == 0 {
		seed = 89482311
	}

seed = seed % int32max !!!

int32max は 2³¹-1 です。今どきのコンピューターなら全数探索もそう難しいことではありません。

ブルートフォースアタックを仕掛ける

大まかに以下ようなコードを書きます。

func bruteAuthorizedKey(idx, total int) ed25519.PrivateKey {
    for i := 0; i < 1<<32; i++ {
        fastRandReader := &fastRandReaderImpl{rand.New(rand.NewSource(int64(i)))}

        for {
            // SSH鍵を生成する。
            priv := generateKey(fastRandReader)

            // 公開鍵の末尾が a で終わっているか調べる。
            if hasSuffix(priv) {

                // フラグ（問題の答え）を見つけたら終了。
                if isFlag(priv) {
                    return priv
                }

                // かっこいいSSH鍵生成プログラムは、
                // 最初に見つけたかっこいいSSH鍵を返すことがわかっているので、
                // ここで検索を打ち切る。
                break
            }
        }
    }
    return nil
}

完全なコードはGitHubにコミットしておきました。

結果

手元の MacBook Pro (14-inch, 2021) Apple M1 Pro で実行してみました。

(snip)
2024/03/27 21:45:50 21b80800 Fq/+3V2o1CSI7qUuAzSzhc1otbnBjIqXiu+ybt2Zs82a
2024/03/27 21:45:50 21b1c807 IhlcF4+LUicBBOxQR7SjzUfq3PiddX/ulJde5iWoVnza
2024/03/27 21:45:51 21c07809 WTy/1TdGMGNQ3WAoMVD+BlOYW0HvvyvBAPKRNyhmOwba
2024/03/27 21:45:51 21afc004 ywYeAfpZxkGz+7py0ybhpsHNnk1UyDsRtCUtHQreg/xa
2024/03/27 21:45:51 21bee806 2kgEG+xcZyclfnmpdP9UuK5qKTNsaoHmDOQ3jKiIJVha
2024/03/27 21:45:51 21bad802 cUKSbvAl1on3L0GktTysP1or73hDdad5+5xqFnPCBCKa
2024/03/27 21:45:51 21b92001 1vz9ZFEIsUvg8G8GTcdK8X3sEkHDhyZK05yTHYM9pTHa
2024/03/27 21:45:51 21b74003 3dNasnfkkFUaHjk4ezn5bG+5H0UraPIAwf4/j4ax0gpa
2024/03/27 21:45:51 21bb0005 spI7VNXs8mPBVNKq8S6mS85Lpj583Bdp3HZJ3tKcGQ6a
2024/03/27 21:45:51 found
go run main.go  748204.48s user 2866.83s system 966% cpu 21:35:21.69 total

21時間かかったよ・・・ An hour とは行きませんでしたが、まあ現実的な時間で解けました。

得られた秘密鍵は以下の通りです。

-----BEGIN OPENSSH PRIVATE KEY-----
b3BlbnNzaC1rZXktdjEAAAAABG5vbmUAAAAEbm9uZQAAAAAAAAABAAAAMwAAAAtz
c2gtZWQyNTUxOQAAACAVY4uZAV2vD2wz9Z5Pp8rFQPPVTINu8/fA+GlU/4+BWgAA
AIhLwY9OS8GPTgAAAAtzc2gtZWQyNTUxOQAAACAVY4uZAV2vD2wz9Z5Pp8rFQPPV
TINu8/fA+GlU/4+BWgAAAEB7Gf+HiN78cWBrNra2Y712ZZz0Gcev7WqY2NMN0feG
5xVji5kBXa8PbDP1nk+nysVA89VMg27z98D4aVT/j4FaAAAAAAECAwQF
-----END OPENSSH PRIVATE KEY-----

ssh-keygen を使えばこれが答えであることを確認できます。

$ ssh-keygen -y -f out
ssh-ed25519 AAAAC3NzaC1lZDI1NTE5AAAAIBVji5kBXa8PbDP1nk+nysVA89VMg27z98D4aVT/j4Fa

余談

同じ手法で冒頭のSSH鍵も秘密鍵を計算できるはずです。 ただし、単純計算で今回解いたCTFの1700万倍の計算量が必要です。 無限にコンピューターリソースが使えるなら計算できそうですが・・・予算の都合から諦めました。

math/rand の代わりに crypto/rand を使うプルリクエストをマージしてもらいました。

初版よりは強力なSSH鍵を生成できるようになっているはずです。

まとめ

秘密鍵の生成には、おとなしく ssh-keygen を使いましょう。

暗号論的に安全ではない疑似乱数を使って作成されたSSH鍵は非常に危険です。 そのようなSSH鍵では、公開鍵から秘密鍵を計算できることを実際に確かめてみました。

🐰✨
セキュリティのためには、
強固な鍵が必要、
crypto/randの光に導かれ、
安全な道を歩もう。
🌟🔑
by CodeRabbit

参考文献