OpenSSH ED25519 の Vanity Adress を探してみる

以前何種類かのVanity Adress を掘ってみました．

Nostr の Vanity address を掘る – matoken’s meme

torのhidden serviceで使うアドレスを計算する(Vanity Addresses) – matoken’s meme

ふとSSH鍵のVanity Adress はどうだろうと試してみました．

鍵はEd25519 ．鍵ペアの公開鍵がいい感じだと良さそうな気がします．

OpenSSH ssh-keygen

まずはOpenSSH の ssh-keysign で作ってみます．大文字小文字いずれかの mat0 が見つかるまで作成しています．

$ umask 277; no=0; tmp=`mktemp -d -p ~/tmp/`; chmod 700 ${tmp}; while true;do no=$(($no + 1)); ssh-keygen -t ed25519 -f ${tmp}/${no} -N '' -C '' > /dev/null; grep -i -E m[a@]t[o0] ${tmp}/${no}.pub && echo ${tmp}/${no} && break; done
ssh-ed25519 AAAAC3NzaC1lZDI1NTE5AAAAIOt6L8+9eF3T8o/M4BnDVZ5F7SVdPmat0hlM8s/8zV/r
/home/matoken/tmp/tmp.rGb5eSpEaJ/26016

26016鍵ペアを生成したところで186秒ほど，大体140.6keys/sec くらい．遅い感じ?vmstat やtop を見てもcpu はあまり使えていない感じです．
-a 1 (default:16) にすると160.8/keys/sec と少し早くなりましたが鍵を盗まれた場合の強度が下がると思うのでやめたほうが良さそうです．

ssh-keygen-ed25519-vanity

tool を探してみます．

GitHub – ionathanch/ssh-keygen-ed25519-vanity: Generate a vanity EdDSA SSH key for fun.

clone&build

$ git clone https://github.com/ionathanch/ssh-keygen-ed25519-vanity
$ cd ssh-keygen-ed25519-vanity
$ make

run

$ ./vanity mato
ssh-ed25519 AAAAC3NzaC1lZDI1NTE5AAAAIEHmibZNyKuT/GO9rloS8qmatoFOZ4N7fJcRSOPCwsky
-----BEGIN OPENSSH PRIVATE KEY-----
b3BlbnNzaC1rZXktdjEAAAAABG5vbmUAAAAEbm9uZQAAAAAAAAABAAAAMwAAAAtzc2gtZWQyNTUxOQAAACBB5om2Tcirk/xjva5aEvKpmraBTmeDe3yXEUjjwsLJMgAAAIjwyswa8MrMGgAAAAtzc2gtZWQyNTUxOQAAACBB5om2Tcirk/xjva5aEvKpmraBTmeDe3yXEUjjwsLJMgA
AAEBro42f/ycDTNvMw3JHIGD5dzg+VVgshQw+RWIhN/I2WEHmibZNyKuT/GO9rloS8qmatoFOZ4N7fJcRSOPCwskyAAAAAAECAwQF
-----END OPENSSH PRIVATE KEY-----

shell でssh-keygen を回すより速そうです．更にREADME にはmoreutils のparallel を使って並列実行する方法も書かれていました．

$ time parallel -n 0 ./vanity vanity -- 1 2 3 4

以下はREADME にあった文字数によりどのくらい時間がかかるかの目安です．

Rough performance stats
Obviously since it’s brute force the times are probabilistic, but this gives you an idea of how feasible it would be to find your desired number of characters.

Substring | Time (s)

a

0.002

ar

0.015

ars

0.501

arso

3.753

arson

abandon all hope ye who seek five sequential characters

大分速いような気がしますがアドレスの指定が固定なようで大文字小文字どっちでもとか代替記号でもいいなどといったことが出来なそうです．

vanity-keygen

また別のものも試してみます．

GitHub – pcarrier/vanity-keygen: Get your vanity SSH ed25519 keypair

clone&build

$ go install github.com/pcarrier/vanity-keygen@latest
$ vanity-keygen -h
Usage of vanity-keygen:
-cpuprofile string
write cpu profile to file
-threads int
number of threads to run (default 4)

run

$ time vanity-keygen -threads `nproc` [mM][aA@][tT][oO0]
2023/04/05 08:30:06 Looking for a public key matching [mM][aA@][tT][oO0]
2023/04/05 08:30:06 Public key:
ssh-ed25519 AAAAC3NzaC1lZDI1NTE5AAAAIA2rzJZSoqwrVF/Pf2FzKgfL/eMATOI/V7bjdmqkGV5B
2023/04/05 08:30:06 Private key:
-----BEGIN OPENSSH PRIVATE KEY-----
b3BlbnNzaC1rZXktdjEAAAAABG5vbmUAAAAEbm9uZQAAAAAAAAABAAAAMwAAAAtz
c2gtZWQyNTUxOQAAACANq8yWUqKsK1Rfz39hcyoHy/3jAEziP1e243ZqpBleQQAA
AIiaywRCmssEQgAAAAtzc2gtZWQyNTUxOQAAACANq8yWUqKsK1Rfz39hcyoHy/3j
AEziP1e243ZqpBleQQAAAEDBsKpzquKe0/QTheaoVSChK8gF6d38u5mwrtqihfMY
6A2rzJZSoqwrVF/Pf2FzKgfL/eMATOI/V7bjdmqkGV5BAAAAAAECAwQF
-----END OPENSSH PRIVATE KEY-----

real 0m0.331s
user 0m0.652s
sys 0m0.048s

このツールはスレッド数も指定できるし，アドレスの指定も柔軟なので良さそうです．

$ vanity-keygen aaaaa
2023/04/05 08:30:12 Looking for a public key matching aaaaa
2023/04/05 08:30:13 Generated 71,000 keypairs (69,788 Hz)
2023/04/05 08:30:14 Generated 141,000 keypairs (70,310 Hz)
2023/04/05 08:30:15 Generated 212,000 keypairs (70,454 Hz)
2023/04/05 08:30:16 Generated 284,000 keypairs (70,792 Hz)
2023/04/05 08:30:17 Generated 356,000 keypairs (71,040 Hz)

探索中にどのくらいの鍵を生成したかも表示されます．

良さそうなのでTor のときのように少電力なSBCのRaspberry Pi 3 modelB でも試してみました．

Raspberry Pi OS armhf 向けにamd64 環境でクロスビルド

$ GOARCH=arm GOARM=7 go build .
$ file ./vanity-keygen
./vanity-keygen: ELF 32-bit LSB executable, ARM, EABI5 version 1 (SYSV), statically linked, Go BuildID=Z_Cr4XM48GAIHSA-MQng/2wFeSpgr5k0WPASNS4ho/3FEwAtva33LS2ByXLcjP/0WSk_fEc6xXCDZEo89yH, with debug_info, not stripped

Pi3Bで実行

$ ./vanity-keygen -threads 4 aaaa
2023/04/05 08:22:58 Looking for a public key matching aaaa
2023/04/05 08:22:59 Generated 0 keypairs (0 Hz)
2023/04/05 08:23:00 Generated 4,000 keypairs (1,991 Hz)
2023/04/05 08:23:01 Generated 4,000 keypairs (1,332 Hz)
2023/04/05 08:23:02 Generated 8,000 keypairs (1,990 Hz)
2023/04/05 08:23:03 Generated 8,000 keypairs (1,598 Hz)
^C
$ cat /proc/device-tree/model && echo
Raspberry Pi 3 Model B Rev 1.2

……大分遅くなりました．PCで実行したほうが良さそうです．

まとめ

気に入った鍵が出来たらパスフレーズを設定したり，

$ ssh-keygen -p -f ./key
Key has comment ''
Enter new passphrase (empty for no passphrase):
Enter same passphrase again:
Your identification has been saved with the new passphrase.

コメントを書き換えたりしましょう．

$ ssh-keygen -c -f ./key
Enter passphrase:
Old comment:
New comment: vanity
Comment 'vanity' applied

Tor のVanity adoress なんかに比べるとあまり目立たないですが，hostkey やGitHub/Lab などで一般公開している鍵に使うのはありではと思います．

Ubuntu Server インストーラの Github, Launchpad からの ssh公開鍵インポート機能 – matoken’s meme

環境

$ cpu-info
Packages:
0: Intel Core i5-7300U
Microarchitectures:
2x Sky Lake
Cores:
0: 2 processors (0-1), Intel Sky Lake
1: 2 processors (2-3), Intel Sky Lake
Logical processors (System ID):
0 (0): APIC ID 0x00000000
1 (2): APIC ID 0x00000001
2 (1): APIC ID 0x00000002
3 (3): APIC ID 0x00000003
$ lsb_release -dr
No LSB modules are available.
Description: Debian GNU/Linux 12 (bookworm)
Release: 12
$ arch
x86_64