More than 3 years have passed since last update.

秘密鍵を10億個作れば、高確率で自分の名前を含む公開鍵が作れる件

Last updated at 2020-08-08Posted at 2020-07-26

エンジニアなら誰もがgithubで晒される公開鍵。
https://github.com/ユーザー名.keys
で全世界に公開されます。

それでは、稚拙ながら私@umihicoの公開鍵をご覧ください。

ssh-ed25519 AAAAC3NzaC1lZDI1NTE5AAAAIFUMIHICoCb3Sy2n1qPXOxc2mFBqW9Hg0dRigxl2F3nW

そうです。自身のユーザー名を挿入することに成功しました。正規表現で指定の文字列が見つかるまで、とにかく鍵を生成し続けるワンライナーを作り、それを1週間くらい回しました。ワンライナーはこちらです。

@Ress さんよりcd $(mktemp -d)を使用しディスクIOの時間を減らすアドバイスを頂きました。ありがとうございます！

cd $(mktemp -d); while true; do seq 1000 | xargs -P 1000 -I NUM sh -c 'ssh-keygen -t ed25519 -f NUM.pem -N "" -C "" > /dev/null && if grep -vi umihico NUM.pem.pub > /dev/null; then rm NUM.pem NUM.pem.pub;fi' ; if find . -mindepth 1 | read; then  for f in *.pem.pub; do echo $f >> files.txt; done; test -f files.txt && head -n1 files.txt | xargs -I F echo found;  break; fi ; date ; done

鍵生成から正規表現判定と削除までの処理を、xargsでマルチプロセスを使って1000個の並列処理をしています。見つかり次第、whileから抜けています。RSAよりed25519を使うことで短時間で大量に作成できます。しかも鍵の安全性が高まり、文字長も短いです。

@AKKYM さんより、xargsよりfilterを使ってマルチプロセスを高速化させる提案を頂きました。1.2倍ほどパフォーマンスが改善します。ありがとうございます。Macbookのsplitは引数がLinuxと異なるので、brew install coreutilsでインストールできるgsplitを使う必要があります。

cd $(mktemp -d); while true; do seq 1000 | gsplit -u -n r/32 --filter 'while read i; do ssh-keygen -t ed25519 -f $i.pem -N "" -C "" > /dev/null && if grep -vi umihico $i.pem.pub > /dev/null; then rm $i.pem $i.pem.pub;fi; done' ; if find . -mindepth 1 | read; then  for f in *.pem.pub; do echo $f >> files.txt; done; test -f files.txt && head -n1 files.txt | xargs -I F echo found;  break; fi ; date ; done

r/32が分割数＝プロセス数になりますが、増やしたり少なくしたりしてベスト値から外れると、パフォーマンスが低下しxargsと同程度になります。それに対しxargsはプロセス数は32〜1000で変化させてみても、明らかな差はあまりないです。

サーバーでtmuxなどを使ってバックグラウンドで処理させる場合は通知がほしいので、echo foundを例えばSlackのWebhook Incoming APIなどに置換しましょう。以下のようになります。（xargsバージョン）

cd $(mktemp -d); while true; do seq 1000 | xargs -P 1000 -I NUM sh -c 'ssh-keygen -t ed25519 -f NUM.pem -N "" -C "" > /dev/null && if grep -vi umihico NUM.pem.pub > /dev/null; then rm NUM.pem NUM.pem.pub;fi' ; if find . -mindepth 1 | read; then  for f in *.pem.pub; do echo $f >> files.txt; done; test -f files.txt && head -n1 files.txt | xargs -I F curl -s -X POST -d '{"text":"F"}' https://hooks.slack.com/services/XXXXXXXXX/YYYYYYYYYYY/zzzZZZzZzzZzzZZzz;  break; fi ; date ; done

ちなみに遊休サーバーなら使ってもいいかというと、EC2はCPUバーストの設定によっては+αの課金をされるので注意しましょう。
CPUバーストUnlimitedのEC2さんに乱暴したら課金された

それでは希望の文字列が発生する確率と待ち時間について考察します。
7文字のbase64からなるランダムな文字列が、偶然umihico（case-insensitive）になる可能性は、2^7/64^7です。そしてed25519は変化する文字列長が43文字なので、7文字の場合はこの試行を37回同時に行えると解釈できます。つまり１回でヒットする確率は 0.0000001076841726899147%です。

>>> 2**7/64**7*37
1.076841726899147e-09

10億回試行するまでに見つかる確率は10億回連続で見つからない確率を1から引けばよいです。65.9%です。

>>> 1-(1-2**7/64**7*37)**(10**9)
0.6593302436744479

X文字をYの確率で出現させるにはZ回試行すればよい、というのは以下の式で得られます。（python3.6以降のターミナル）

>>> import math
>>> X=8
>>> Y=0.6
>>> Z=int(math.log(1-Y,1-2**X/64**X*(43-X+1)))
>>> f"{X}文字の場合{ '{:,}'.format(Z)}回で{Y*100}%"
'8文字の場合27,985,342,058回で60.0%'

ワンライナーは1000件生成が完了する毎にdateが実行されるので、少し眺めていれば１日に何件試行できるか見当がつきます。１秒に1000件できても、8文字で60%を叩き出す270億回のためには324日かかるので、8文字以上の名前の方々は現実的ではないと言えそうです。ごめんなさい。

そして注意点があります、公開鍵は当然、ランダムな文字列ではありません。しかし名前という任意な文字列を含む確率という命題に対しては、ランダムとして扱えると仮定しています。色々試し、体感的には正しそうですが、**無根拠です。**つまり、永遠に試行しても発生しない文字列や、ランダムより歪んだ確率を持つ文字列の存在が十分ありえます。この辺をもっと調べたいですが、~~これ以上業務時間を使うべきではありません。~~

@angel_p_57 さんよりコメントで補足を頂きました。
ランダムとして扱ってよいが、最初のIの次は大文字A～Pに限られるとのことです。ありがとうございます。

ご一読ありがとうございました。

Gist

参考

378

192

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up