疑問

ssh-keygen コマンドで秘密鍵を生成するとき、 ssh-keygen -t ed25519 -a 128 のように -a オプションで rounds を指定できる。デフォルト値は16になっている。 rounds とは何だろうか？どうも秘密鍵ファイルの保護の強度に影響するようだが。

TL;DR: 結論までジャンプ

ドキュメントを読む

man ssh-keygen を引用すると、

When saving a private key, this option specifies the number of KDF (key derivation function, currently bcrypt_pbkdf(3)) rounds used. Higher numbers result in slower passphrase verification and increased resistance to brute-force password cracking (should the keys be stolen). The default is 16 rounds.

とのこと。秘密鍵ファイルを暗号化するための暗号鍵をパスフレーズから導出する bcrypt_pbkdf 関数のパラメータということだ。 bcrypt_pbkdf 関数は鍵導出関数である PBKDF2 を少し改変したものらしい。

PBKDF2 は rounds に似たパラメータとしてストレッチング回数あるいはイテレーションを持つ。入力されたパスワードとソルトにハッシュ関数を繰り返し適用する操作の回数のことで、導出された鍵の解読の困難さに直結し、コンピュータの計算性能が向上するに従って推奨される回数も引き上げられている。

2021年時点で OWASP が推奨¹するストレッチング回数は PBKDF2-HMAC-SHA-256 の場合で31万回。

2000年時点でも推奨回数は1000回だったというから、 rounds がストレッチング回数だとすれば少なすぎるように思える。

実装を読む

実際はどうなのか、 bcrypt_pbkdf 関数の実装を見ていく。

		for (i = 1; i < rounds; i++) {
			/* subsequent rounds, salt is previous output */
			crypto_hash_sha512(sha2salt, tmpout, sizeof(tmpout));
			bcrypt_hash(sha2pass, sha2salt, tmpout);
			for (j = 0; j < sizeof(out); j++)
				out[j] ^= tmpout[j];
		}

出力を固定長のブロックに区切ってブロックごとハッシュ関数を rounds 回適用している。まさにストレッチング回数のことだ。

ただし、ここではハッシュ関数として bcrypt_hash を呼んでいるんでいることに注意しなければならない。

bcrypt_hash 関数はパスワードハッシュ関数の bcrypt を若干改変したもので、鍵拡張のラウンドは64回に固定されている。

n ラウンドの bcrypt 関数を m 回適用すれば n * m ラウンドの bcrypt 関数を1回適用するのに近い解読困難性を得られると仮定するなら、 bcrypt_pbkdf 関数全体の解読困難性はラウンドが ストレッチング回数 * 64 回の bcrypt 関数に近いと言える……のだろうか？（さらにブロックの個数を掛けるべきかどうかは分からない。）だとすると -a オプションのデフォルト値16では 16 * 64 = 1024 ラウンドの bcrypt 関数に近い。

bcrypt 関数のラウンド数は2014年時点でも4000回程度がいいとされている（現代ではもう何倍かすべきだろう）。 -a 128 くらいにしてもいいのかもしれない。当然だが増やしすぎると秘密鍵ファイルのアンロックに時間がかかる。

ベンチマークを取る

試しにいくつか秘密鍵ファイルを作り、アンロックにかかる時間を計測してみる。

まず作る。

for rounds in 16 32 64 128 256 512 1024; do
    ssh-keygen -a "$rounds" -f "key_$rounds" -N pass -C comment
done

hyperfine でベンチマークを取る。テストには秘密鍵ファイルのコメントを書き換えるサブコマンド ssh-keygen -c を使った。コマンドラインから -N でパスフレーズを渡せるサブコマンドはこれくらいなため。

% hyperfine \
    'ssh-keygen -c -f key_16 -N pass -C comment' \
    'ssh-keygen -c -f key_32 -N pass -C comment' \
    'ssh-keygen -c -f key_64 -N pass -C comment' \
    'ssh-keygen -c -f key_128 -N pass -C comment' \
    'ssh-keygen -c -f key_256 -N pass -C comment' \
    'ssh-keygen -c -f key_512 -N pass -C comment' \
    'ssh-keygen -c -f key_1024 -N pass -C comment'

実行結果

Benchmark 1: ssh-keygen -c -f key_16 -N pass -C comment
  Time (mean ± σ):     115.1 ms ±   0.7 ms    [User: 112.2 ms, System: 1.3 ms]
  Range (min … max):   114.5 ms … 117.5 ms    25 runs

Benchmark 2: ssh-keygen -c -f key_32 -N pass -C comment
  Time (mean ± σ):     226.3 ms ±   0.6 ms    [User: 222.8 ms, System: 1.5 ms]
  Range (min … max):   225.7 ms … 228.1 ms    13 runs

Benchmark 3: ssh-keygen -c -f key_64 -N pass -C comment
  Time (mean ± σ):     448.1 ms ±   0.5 ms    [User: 444.0 ms, System: 2.0 ms]
  Range (min … max):   447.6 ms … 449.2 ms    10 runs

Benchmark 4: ssh-keygen -c -f key_128 -N pass -C comment
  Time (mean ± σ):     890.8 ms ±   0.4 ms    [User: 886.2 ms, System: 2.7 ms]
  Range (min … max):   890.1 ms … 891.3 ms    10 runs

Benchmark 5: ssh-keygen -c -f key_256 -N pass -C comment
  Time (mean ± σ):      1.778 s ±  0.002 s    [User: 1.771 s, System: 0.005 s]
  Range (min … max):    1.776 s …  1.783 s    10 runs

Benchmark 6: ssh-keygen -c -f key_512 -N pass -C comment
  Time (mean ± σ):      3.554 s ±  0.008 s    [User: 3.542 s, System: 0.008 s]
  Range (min … max):    3.549 s …  3.568 s    10 runs

Benchmark 7: ssh-keygen -c -f key_1024 -N pass -C comment
  Time (mean ± σ):      7.102 s ±  0.025 s    [User: 7.081 s, System: 0.015 s]
  Range (min … max):    7.085 s …  7.171 s    10 runs

Summary
  'ssh-keygen -c -f key_16 -N pass -C comment' ran
    1.97 ± 0.01 times faster than 'ssh-keygen -c -f key_32 -N pass -C comment'
    3.89 ± 0.03 times faster than 'ssh-keygen -c -f key_64 -N pass -C comment'
    7.74 ± 0.05 times faster than 'ssh-keygen -c -f key_128 -N pass -C comment'
   15.45 ± 0.10 times faster than 'ssh-keygen -c -f key_256 -N pass -C comment'
   30.88 ± 0.21 times faster than 'ssh-keygen -c -f key_512 -N pass -C comment'
   61.70 ± 0.45 times faster than 'ssh-keygen -c -f key_1024 -N pass -C comment'

マシンスペック

% ssh -V
OpenSSH_8.6p1, LibreSSL 3.3.6

% system_profiler SPSoftwareDataType SPHardwareDataType
Software:

    System Software Overview:

      System Version: macOS 12.6 (21G115)
      Kernel Version: Darwin 21.6.0
      Boot Volume: Macintosh HD
      Boot Mode: Normal
      Computer Name: natsu
      User Name: uasi (uasi)
      Secure Virtual Memory: Enabled
      System Integrity Protection: Enabled
      Time since boot: 32 days 17:01

Hardware:

    Hardware Overview:

      Model Name: Mac Studio
      Model Identifier: Mac13,1
      Chip: Apple M1 Max
      Total Number of Cores: 10 (8 performance and 2 efficiency)
      Memory: 32 GB
      System Firmware Version: 7459.141.1
      OS Loader Version: 7459.141.1
      Serial Number (system): DXH63NHWCY
      Hardware UUID: 426393CF-E570-5F8B-96D1-083B7FDC0CC4
      Provisioning UDID: 00006001-000461C03445801E
      Activation Lock Status: Enabled

ベンチマーク結果は折りたたんでおくが、 rounds を倍にすると秘密鍵ファイルのアンロックにかかる時間もおよそ倍になる。 Mac Studio (M1 Max) で

rounds = 16: 115.1 ms
rounds = 128: 890.8 ms
rounds = 256: 1.778 s

程度。現代のハードウェアなら rounds を128にしても実用的な範囲に収まるだろう。

結論

ssh-keygen の -a オプションの値 rounds は秘密鍵ファイル保護用のパスフレーズから暗号鍵を導出する計算量のこと。大きいほど秘密鍵ファイルの解読困難性が上がるが、アンロックにかかる時間も比例して長くなる
rounds のデフォルト値である16は2022年現在では低すぎるように思える（が確信はない）
現在のハードウェアでは50〜100程度でもアンロックが1秒以内で終わるため、高めに設定しても損はないはず

既存の秘密鍵ファイルの rounds を変更するには ssh-keygen -p -a 128 -f /path/to/key でいける。元々パスフレーズ変更用のコマンドなので新しいパスフレーズの入力も促されるが、同じにしてよい。

そもそも可能ならより高性能な他の鍵導出関数を使うべきだという話も書かれている ↩