例えばこのSSH公開鍵、末尾に私の名前(akiym)が入っています。
ssh-ed25519 AAAAC3NzaC1lZDI1NTE5AAAAIFC90x6FIu8iKzJzvGOYOn2WIrCPTbUYOE+eGi/akiym
そんなかっこいいssh鍵が欲しいと思いませんか？
ed25519のSSH公開鍵の構造
SSH鍵の形式にはRSAやDSA、ed25519などがありますが、最近のssh-keygenではデフォルトでed25519の鍵を生成するということもあり、ed25519を利用していることを前提として進めます。なにより、RSAの公開鍵に比べると短いので末尾部分が目立つはずです。
そもそも、ed25519のSSH公開鍵のフォーマットはどのようなものになっているか確認してみます。まずはssh-keygenコマンドで秘密鍵と公開鍵を生成します。
% ssh-keygen -t ed25519 -f test Generating public/private ed25519 key pair. Enter passphrase (empty for no passphrase): Enter same passphrase again: Your identification has been saved in test Your public key has been saved in test.pub The key fingerprint is: SHA256:NeYtBvyhXH8QwBs2qTXySfBWGQHBPwE3BBTR0rZ+HiQ <redacted> The key's randomart image is: +--[ED25519 256]--+ | .=X&O+ | | ...%o*o | | oBOX.o | | ..X+=E.. | | S =.o+. | | . ...o | | o . | | . | | | +----[SHA256]-----+ % cat test.pub ssh-ed25519 AAAAC3NzaC1lZDI1NTE5AAAAIK/99+jnYPCQvNgb/4BeckKITWKsKihl5HvHlSvfkYc1 <redacted>
生成された公開鍵test.pubに対して、以下のコマンドでbase64デコードして中身を確認してみます。
% echo 'AAAAC3NzaC1lZDI1NTE5AAAAIK/99+jnYPCQvNgb/4BeckKITWKsKihl5HvHlSvfkYc1' | base64 -d | xxd
00000000: 0000 000b 7373 682d 6564 3235 3531 3900 ....ssh-ed25519.
00000010: 0000 20af fdf7 e8e7 60f0 90bc d81b ff80 .. .....`.......
00000020: 5e72 4288 4d62 ac2a 2865 e47b c795 2bdf ^rB.Mb.*(e.{..+.
00000030: 9187 35 ..5
先頭部分は固定で、0x14バイト目以降からは0x20(32)バイト分のed25519の公開鍵が含まれています。つまりは先頭部分は変えることはできませんが、末尾部分であれば公開鍵によってはbase64の文字種の範囲内で好きな文字を指定することができそうです。
また、fingerprintは上記の公開鍵のデータ部分のSHA-256を計算し、base64エンコードしたものです。fingerprintはSHA256:NeYtBvyhXH8QwBs2qTXySfBWGQHBPwE3BBTR0rZ+HiQであったので、同じものが以下のコマンドで求められていることが分かります。
% echo 'AAAAC3NzaC1lZDI1NTE5AAAAIK/99+jnYPCQvNgb/4BeckKITWKsKihl5HvHlSvfkYc1' | base64 -d | sha256sum | xxd -r -p | base64 NeYtBvyhXH8QwBs2qTXySfBWGQHBPwE3BBTR0rZ+HiQ=
注意すべきポイントとしては、base64エンコードした結果の末尾に=が含まれているところです。base64はデータを6ビットずつに分けて変換して余った場合にパディングとして=を追加します。よって=が1つ含まれるこの場合だと6ビットのうち後ろの2ビット分が00になるため、最後の文字はAEIMQUYcgkosw048のいずれかになります。
ed25519の秘密鍵と公開鍵
ed25519の秘密鍵は32バイトのランダムなデータです。公開鍵の計算には、まず秘密鍵seedのSHA-512を計算した結果が用いられる*1ため、秘密鍵を調整すれば公開鍵に任意のバイト列を含められるようなものでもありません。
つまり、公開鍵の末尾に特定の文字列を含めるには、とにかく鍵を生成し続けて運よく引き当てるしかなさそうです。
ブルートフォースでかっこいい公開鍵を探す
単純にはssh-keygenコマンドを叩き続けるようなものがあればよいはずですが、さすがに遅いので効率よくブルートフォースしたいところです。ということでちょっとしたコードを書いてみました。
ちなみにこのコミットでは/AKIYMで終わるfingerprintのSSH鍵を使って署名をしています。
コマンドを実行すると秘密鍵と公開鍵がそれぞれoutとout.pubに出力されます。以下のようなオプションで公開鍵のsuffix、fingerprintのprefix/suffixが指定できるようになっています。オプション単体での探索時間の目安としては5文字で1時間、6文字で10時間程度です。
$ ed25519brute -authorized-key-suffix test 2024/03/20 20:37:56 start 2024/03/20 20:38:05 found % cat out.pub ssh-ed25519 AAAAC3NzaC1lZDI1NTE5AAAAINynu9CvEi6Yav1Y2L7hNxtD63RiHZkOG/ZsVzsNtest
% ed25519brute -fingerprint-prefix hello 2024/03/20 20:39:54 start 2024/03/20 21:22:53 found % ssh-keygen -l -f out 256 SHA256:helloz8d+urX+JvZmOVdewcWAx89vXeoKTLsUH0mgBc out.pub (ED25519)
$ ed25519brute -fingerprint-suffix KEY 2024/03/20 21:23:11 start 2024/03/20 21:23:11 found % ssh-keygen -l -f out 256 SHA256:8qN1j+/pE1VFyPzIzi6S9Njqvwtw52PIQJqCj9K8KEY out.pub (ED25519)
秘密鍵を生成する際の乱数生成には高速化のためにGoのmath/randを使っていますが、乱数が用いられるのは公開しない秘密鍵自体であり、このアルゴリズム自体はLagged Fibonacci generatorのようなので変に乱数に偏りがない限りは大丈夫だろうと思います(追記: これは乱数予測を主とした話)。
とはいえ利用の際にはあくまでかっこいいSSH鍵、というネタとしてお使いください。SSH鍵はssh-keygenで生成するのが正しいです。
