Case Study - Openssh Private Key Recovery
Intro
Openssh keys are often used for ssh access. Under the hood, openssh uses RSA algorithm for key pair generation. RSA is an industrial standard algorithm used for encryption/decryption. In this case study, we’ll examine how to re-calculate the openssh private key once necessary bits and pieces information are obtained.
How does RSA work
Reading https://en.wikipedia.org/wiki/RSA_(cryptosystem), RSA operations can be summarised below
* Choose two distinct prime numbers, p and q
* n = pq
* Compute the Carmichael's totient function of n: λ(n) = lcm(p − 1, q − 1)
* Choose any number 1 < e < λ(n) that is coprime to λ(n)
* Compute d, the modular multiplicative inverse of e (mod λ(n))
* Public key contains n and e
* Encryption process: cipher = msg^e mode n
* Private key contains n and d
* Decryption process: msg = cipher^d mod n
So, in principle, if we have successfully obtained the n and either of p and q values, we should be able to re-calculate the necessary values in the private key and recover the openssh private key.
Where to find n
n value can be found in the public key. If we examine how a public key looks like, we may see something like the following in .ssh/id_rsa.pub
ssh-rsa AAAAB3NzaC1...........................................................96tr222+Iu/ZbU= root@kali
Using a tool called openssh_key_parser https://pypi.org/project/openssh-key-parser/, we can decode the public content for better visibility.
> python -m openssh_key ~/.ssh/id_rsa.pub
[
{
"header": {
"key_type": "ssh-rsa"
},
"params": {
"data": {
"e": 65537,
"n": 460042693500104190................032231896501
}
},
"footer": {},
"clear": {
"key_type": "ssh-rsa",
"comment": "root@kali"
}
}
]
From the above, we can see the n value and the exponent (i.e e)
Where to find q
q can be found in the private key. To understand where to look for the q, we need to understand how the openssh private key is structured.
According to https://coolaj86.com/articles/the-openssh-private-key-format/, openssh has its own format, which is structured below.
"openssh-key-v1"0x00 # NULL-terminated "Auth Magic" string
32-bit length, "none" # ciphername length and string
32-bit length, "none" # kdfname length and string
32-bit length, nil # kdf (0 length, no kdf)
32-bit 0x01 # number of keys, hard-coded to 1 (no length)
32-bit length, sshpub # public key in ssh format
32-bit length, keytype
32-bit length, pub0
32-bit length, pub1
32-bit length for rnd+prv+comment+pad
64-bit dummy checksum? # a random 32-bit int, repeated
32-bit length, keytype # the private key (including public)
32-bit length, pub0 # Public Key parts
32-bit length, pub1
32-bit length, prv0 # Private Key parts
... # (number varies by type)
32-bit length, comment # comment string
padding bytes 0x010203 # pad to blocksize (see notes below)
Note the line that says 32-bit length, prv0 # Private Key parts, this is where the private key’s q value begins. It stars with 32-bit data to indicate the length, then followed by the actual q value.
If we examine a private key example, we can see how it’s structured
> sed -e '1d' -e '$d' ~/.ssh/id_rsa | base64 -d | hexdump -C
00000000 6f 70 65 6e 73 73 68 2d 6b 65 79 2d 76 31 00 00 |openssh-key-v1..| # Auth Magic
00000010 00 00 04 6e 6f 6e 65 00 00 00 04 6e 6f 6e 65 00 |...none....none.| # ciphername length and string
# kdfname length and string
00000020 00 00 00 00 00 00 01 00 00 01 97 00 00 00 07 73 |...............s| # kdf
# number of keys
# sshpub
00000030 73 68 2d 72 73 61 00 00 00 03 01 00 01 00 00 01 |sh-rsa..........|
00000040 81 00 ca b7 b3 a1 47 a2 f9 b1 d6 b0 ec 29 34 68 |......G......)4h|
......
00000670 7e 7c 19 00 00 00 c1 00 de 56 df a2 36 93 da a9 |~|.......V..6...| # Private Key parts
# key length, 00 00 c1 00
# followed by q value
......
00000730 86 c9 14 a2 f8 ac e9 fd 00 00 00 09 72 6f 6f 74 |............root| # comment and padding
00000740 40 6b 61 6c 69 01 |@kali.|
00000746
After extracting the q value from the hexdump, we can convert it to a usable format
> python -c 'print(int(0xde56...))'
Recovering the openssh private key
With n and q values obtained, the p value can be calculated using p = n/q. This may exceed the limit of some OS, so, you can use an online big number calculator to achieve the purpose, eg: https://www.calculator.net/big-number-calculator.html. Then rest of the job is just doing some math, which can be done using the script below.
Simple script for private key recovery
n = ...
q = ...
p = ...
e = 0x010001
phi = (p -1)*(q-1)
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
def modinv(a, m):
gcd, x, y = egcd(a, m)
if gcd != 1:
return None # modular inverse does not exist
else:
return x % m
d = modinv(e,phi)
dp = modinv(e,(p-1))
dq = modinv(e,(q-1))
qi = modinv(q,p)
import pyasn1.codec.der.encoder
import pyasn1.type.univ
import base64
def pempriv(n, e, d, p, q, dP, dQ, qInv):
template = '-----BEGIN RSA PRIVATE KEY-----\n{}-----END RSA PRIVATE KEY-----\n'
seq = pyasn1.type.univ.Sequence()
for i,x in enumerate((0, n, e, d, p, q, dP, dQ, qInv)):
seq.setComponentByPosition(i, pyasn1.type.univ.Integer(x))
der = pyasn1.codec.der.encoder.encode(seq)
return template.format(base64.encodebytes(der).decode('ascii'))
key = pempriv(n,e,d,p,q,dp,dq,qi)
f = open("recovered.key","w")
f.write(key)
f.close()