The search for the perfect SSH key

SSH keys are a widely used tool among developers, they are the equivalent of a username and password in the development world. They allow you to prove your identity and they are the gateway into accessing servers remotely in a secure manner.

The SSH public key format

When generating an ssh key, you get 2 files, one with no extension that stores the private key and another that ends with a .pub. The public key is what you share publicly on your profile or add to a remote server to login through SSH.

Here’s how a typical SSH public key looks

ssh-ed25519 AAAAC3NzaC1lZDI1NTE5AAAAIBSSj+yfJLWEb+Df4r4603TOFAUBREYS43qQB+c9i9UW

It consists of 2 parts, the algorithm, in this case it’s ssh-ed25519, but it can be other ones too such as ssh-rsa. The second part is a base64 encoded custom binary format.

Let’s break it down

• the length of the algorithm string, for ed25519 it’s always 11 (4 bytes long)
• the algorithm type, for ed25519 it’s always ssh-ed25519 in binary (11 bytes long)
• the length of the key, 32 bytes for ed25519 (4 bytes long)
• the raw bytes for the ed25519 key (32 bytes long)

Embedding a word in base64

Base64 is a widely used format for displaying binary in a compact and human readable way, it uses A-Z, a-z, 0-9, ’/’ and ’+’ adding up to 64 unique characters.

It’s possible to choose specific bytes in a way that when encoding it with base64 it will form a word.

For example, to encode “Kyren” in base64, we can use the bytes
00101011 00101010 01001110 or in hex 2b 2a de.

So by controlling the 32 bytes at the end of the ssh we are able to get a ssh public key containig any keyword we want.

Brute Force

Unfortunately this approach won’t work, we still want to be able to use the key so we will need to know the corresponding private key, but it’s impossible to reverse engineer the private key using the public one, that’s why cryptography is so secure.

The solution is simple, just generate a bunch of keys until we get lucky and find the desired keyword. So that’s what I have done, here’s a basic go program that does exactly that.

package main

import (
  "bytes"
  "crypto/ed25519"
  "encoding/base64"
  "fmt"

  "golang.org/x/crypto/ssh"
)

func main() {
  keyword := []byte("Kyren")
  for {
    pubKey, privKey, _ := ed25519.GenerateKey(nil)
    sshPubKey, _ := ssh.NewPublicKey(pubKey)
    pub := ssh.MarshalAuthorizedKey(sshPubKey)
    if bytes.Contains(pub, keyword) {
      privBase64 := base64.StdEncoding.EncodeToString(privKey)
      fmt.Printf("Found %s in %s with private key %s\n", string(keyword), string(pub), privBase64)
      break
    }
  }
}

I have later improved this program by adding multithreading and made it easier to use. The final code is available on my GitHub at this link .

Results

After running it for 2 days (about 24 hours in total) on my AMD Ryzen 5 7530U laptop (12 threads), here are the results:

Completed Search
Time Elapsed: 12h9m11.225248108s
Searched: 6733606724 Found: 737

• Generated and searched 150k SSH keys per second
• Found a 5-character keyword every 9.1 million keys or about 1 every minute
• Found a 6 character keyword every 1/64 of every 5-character keyword, or about 1 every hour
• Found 5-character that are at the end of the SSH key 1/50 of every 5-character keyword

My goal was to find a /kyren at the end of the key, on average that’d be 1 every 3200 5-character keywords.

At the end after only 1862 keywords I found the key, here it is

ssh-ed25519 AAAAC3NzaC1lZDI1NTE5AAAAIO7P9K9D5RkBk+JCRRS6AtHuTAc6cRpXfRfRMg/Kyren

I hope this inspires you to try and find your own SSH key, hopefully your name is not 7 characters long, and if it’s 8, I hope you have 170 years to spare.

Thanks for reading! this is my first blog post so any feedback will be appreciated!