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

SSHの鍵生成には暗号論的に安全な疑似乱数を使おうという話。 暗号論的に安全ではない疑似乱数がどれだけ危険かというのを、簡単なCTFを解くことで検証してみました。 背景 SSH公開鍵に自分の好きな文字列を入れる、という記事を読みました。 かっこいいSSH鍵が欲しい 例えばこのSSH公開鍵、末尾に私の名前(akiym)が入っています。 ssh-ed25519 AAAAC3NzaC1lZDI1NTE5AAAAIFC90x6FIu8iKzJzvGOYOn2WIrCPTbUYOE+eGi/akiym そんなかっこいいssh鍵が欲しいと思いませんか？ かっこいい！真似してみたい！ そこまではいいんですが、問題は実装です。 秘密鍵を生成する際の乱数生成には高速化のために Goのmath/randを使っていますが、乱数が用いられるのは公開しない秘密鍵自体であり、このアルゴリズム自体はLagged Fib

[yarumato]

“秘密鍵の生成には、おとなしく ssh-keygen を使いましょう。暗号論的に安全ではない疑似乱数を使って作成されたSSH鍵は危険です。 ”

[yhoriz]

種空間の大きさだけでなく数学的構造に基づく攻撃等々も問題で、CSPRNGはこれらについて最善の努力が専門家によりなされている 問題を軽視しているブコメが散見されるが「暗号はメチャ難しい」という無知の知が大事

[mano-junki]

リスペクトがありつつなやり取り、素敵

[tattyu]

seedが小さいから現実的な時間で解けちゃうのか。

[m10i]

やはり乱数シードと実装がわかると秘密鍵ばれるんだな　勉強になりました

[ad2217]

seed空間が小さい問題のように読める

[tmatsuu]

生成方法には気をつけてね

[mas-higa]

元ネタにはナンバープレート 11-11 みたいな恥しさがあったよなぁ

[belgianbeer]

参考になるな

[deep_one]

予想していたよりもさらに問題があった。

[shoh8]

“まあ現実的な時間で解けました。”

[altar]

世の中が512bit以上の鍵のセキュリティで回っている中で、この例では形式上大きいビット長でも実質32bitの鍵を生成してしまってるわけか。

[natu3kan]

乱数の傾向性がある程度読めたら、いくら桁数が大きくても、可能性が絞れちゃうから実現可能な計算量で殴れちゃうもんな。ゲームで状況再現するのと同じで。

[mockmock9876]

私の乱数は爆発します

[RySa]

待って待って。鍵が分かっていれば同定出来るけどそれが最初に見つかる鍵か分かっていなければ力づくで計算しても徒労じゃない？脆弱性ではあるけどここに書いてあるほどではない。

[tettekete37564]

「暗号論的に安全な疑似乱数」自体がどういう特性のものなのかは以前から気にはなっている。この記事でブルートフォースを使ってるあたりから十分に大きな桁数(ビット数)や周期が十分に長いとかは含まれるのだろうな

[spark7]

64^4か。『ただし、単純計算で今回解いたCTFの1700万倍の計算量が必要です』

[onesplat]

まずそのかっこいいSSH鍵が欲しいってとこからしてナメてんのかなと思ってしまう

[wata88]

ナイス

[buzztaiki]

すてき。

[mojimojikun]

よき

[Windymelt]

良い

[m4fg]

イマドキのcpuには32ビットは短すぎる

[a-know]

良い

[misomico]

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

[iww]

かっこいい

[mizdra]

良い

[daiksy]

めっちゃおもしろい

[Songmu]

こういうエンジニア同士のやり取りめっちゃ良いですね。