1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
|
---
title: The search for the perfect SSH key
description: How you can embed your name in an SSH key
date: 2024-11-15
---
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.
```go
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](https://github.com/Kyren223/ed25519-key-gen).
## 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!
|
