RSA Encryption Key Recovery
A few years back while competing in a hacking competition, I became totally obsessed with one particular RSA key recovery challenge – so much so, that I burned the midnight hours for a couple of days solving it.
As a consequence it turned out I was the only person to complete it!
The experience and the knowledge I gained during this challenge, which forced me to dig into how RSA encryption actually works, left me with more questions than answers, which I’ll explain shortly.
The Challenge
First, let’s start with the crypto challenge itself in which the competitor is provided with only two items:
- an encrypted file that contains the flag for the challenge; and
- a badly corrupted RSA key that (if recovered) will decrypt the file
Here’s what the key looked like:
The task is to successfully decrypt the encrypted file but only after somehow repairing or recovering the RSA key.
As you can see from the corrupted key shown, there isn’t much of it left! And the first obvious thing to note is that the first line of question marks is supposed to be:
-----BEGIN RSA PRIVATE KEY-----
Next I needed to work out how long the key was – is it 1024 bit, or 2048 bit, and what else can I tell about the key – what remnants are left?
What follows are the main steps in my approach that helped me solve this challenge, that culminated in some tin-foil-hat speculation along with a Python script that did the job in just a couple of seconds.
Determining the length of the key
Generating keys of various standard lengths helped this process, so I just ran a couple of quick ones, such as:
openssl genrsa 512
openssl genrsa 1024
openssl genrsa 2048
Each one of these commands outputs an RSA private key, and by comparing the lines it was obvious the 1024-bit at 13 lines looked like a match.
What’s in an RSA key exactly?
-----BEGIN PRIVATE KEY----- MIICdwIBADANBgkqhkiG9w0BAQEFAASCAmEwggJdAgEAAoGBAKx0+bp2zk446c5J EQIV/F3axj2cKPtyK+6bansE4utNicLpWAs25RX5R+Ujj65HhrWO/9GIcMBEkbHH YGSq2Q+sfKs93FlcbP5/BL/J8xpRiBIIsGC7Uhe21rtmHfW6GN/LWovXgYso0nsV Qkur056pseAf7BI0RIROsgURg7/NAgMBAAECgYEAq/hZrp8aStZmD9a8px/VcKHg XT+DfnnzZRSFsfbFcW74mOynZ0duWeMi1lQHyvp4UkQuxXsRNCksP+NZNAlKOLtZ un356YKFlNovkXpCWhs8iFyI4K+n/YuMXGYugXIoWCJHpGl0XYQVzWday7RXWYw4 btD0lbX5A0d8UbLirOECQQDdoFIOn6O+i2z5JS/LrNwf8NgE94flmtr5GBbNCryS a9sF0RJBR3mMLWRDLObVU2vYMt+OpT++J+z/LBlYByaLAkEAxzRinlAkGNrdVJe4 sbNgRH4saOBP+tE6OGTkJDRRUGB7eDoh3hTv9ACPE1wcm3KzOjhKtS05ZYn0qh9w 4f1WBwJAcXS3TUEwREWAHfOJik0Ny1QyYiiN617hJo/MbF9ItfR9BXdITx7V/Iro PvNnoGG6Xc19YLr77M7npqHev4+5jQJBALVcwUinaCXk5cuFktbenA/f2+jkCI0v flUnrfo0U6/dF6x/KKR75Xb+J0UWAMmaJQklhQbslKwYbNOSaoCl2HMCQDw6CRYB Wuh4qEESaRSD7n7kPvzZQotcgOtbi/cgHjZO4VX2/iyrZW2ErFZNey0XMAM7Qcou QdM+3lkT5A40ucg= -----END PRIVATE KEY-----
Next I had to consider, what is inside one of these blobs of random looking text?
Funny how I’ve been dealing with cryptography in business for years, and yet I never really had time to stop and look at what’s in one of these.
First thing to understand is that the format we’re looking at is known technically as PEM which stands for “Privacy Enhanced Mail” – and it’s really nothing more than some data (more on that in a moment) which has been Base64 encoded and has the START and END lines attached.
The RSA key itself in its more native binary format known as DER (Distinguished Encoding Rules) can be extracted like this.
root@localhost:~# openssl rsa -in my1024.key -outform der | xxd
writing RSA key
00000000: 3082 0277 0201 0030 0d06 092a 8648 86f7 0..w...0...*.H..
00000010: 0d01 0101 0500 0482 0261 3082 025d 0201 .........a0..]..
00000020: 0002 8181 00ac 74f9 ba76 ce4e 38e9 ce49 ......t..v.N8..I
00000030: 1102 15fc 5dda c63d 9c28 fb72 2bee 9b6a ....]..=.(.r+..j
00000040: 7b04 e2eb 4d89 c2e9 580b 36e5 15f9 47e5 {...M...X.6...G.
00000050: 238f ae47 86b5 8eff d188 70c0 4491 b1c7 #..G......p.D...
...
Funnily enough if you just took the Base64 block of text from the PEM format and decoded it directly, you’ll get exactly the same thing as above.
Notice the first two bytes are 0x3082 and this indicates the data is an ASN.1 sequence – there’s some good info from Let’s Encrypt on ASN.1 and DER if you’re interested in the fine detail.
So, other than the binary format of the data, what does it parse out to if we read the key using something that can interpret and decode DER and ASN.1 sequences? We do that like this:
openssl rsa -in some1024.key -noout -text
This will output all the pieces of data inside the key (show with hex removed):
Private-Key: (1024 bit, 2 primes) modulus: <hex data in here> publicExponent: 65537 (0x10001) privateExponent: <hex data in here> prime1: <hex data in here> prime2: <hex data in here> exponent1: <hex data in here> exponent2: <hex data in here> coefficient: <hex data in here>
Analysing the corrupted key
Armed with a bit more knowledge about how the RSA keys are stored in these formats, I was able to simply take the non-corrupted part of the challenge key and Base64 decode it – which returned a partial DER encoded ASN.1 sequence.
Using a hex editor I was able to determine the only two usable parts to be equivalent to this (a sample here not from the actual challenge)
exponent1:
71:74:b7:4d:41:30:44:45:80:1d:f3:89:8a:4d:0d:
cb:54:32:62:28:8d:eb:5e:e1:26:8f:cc:6c:5f:48:
b5:f4:7d:05:77:48:4f:1e:d5:fc:8a:e8:3e:f3:67:
a0:61:ba:5d:cd:7d:60:ba:fb:ec:ce:e7:a6:a1:de:
bf:8f:b9:8d
exponent2:
00:b5:5c:c1:48:a7:68:25:e4:e5:cb:85:92:d6:de:
9c:0f:df:db:e8:e4:08:8d:2f:7e:55:27:ad:fa:34:
53:af:dd:17:ac:7f:28:a4:7b:e5:76:fe:27:45:16:
00:c9:9a:25:09:25:85:06:ec:94:ac:18:6c:d3:92:
6a:80:a5:d8:73
What is an “exponent” in an RSA key?
It turns out these values are stored in an RSA key to speed up some of the mathematics operations since RSA uses multiplication of very large numbers – this is based on Chinese Remainder Theorem.
At this point in the challenge I had enough information to start thinking about a solution.
RSA key recovery and my tin-foil-hat
When searching for “RSA key recovery” and associated terms in search engines, I started reading all the documents where RSA, including the original RSA paper and also RFC3447 define the specifications.
The only references you’ll find to “key recovery” in official documentation is in the context of “message recovery” (i.e. protecting the integrity of the encrypted data), and otherwise it will refer to recovering a key from escrow or backup of some kind – but certainly is not what this challenge calls for, which is to somehow reconstruct a key some other way.
Initially it felt like I was on a dead end, until I was a few pages deep into one Google search when I stumbled across this…
“Key Recovery Method for CRT Implementation of RSA“
Paper: https://eprint.iacr.org/2004/147.pdf
What!? CRT – Chinese Remainder Theorem. Yes, this was exactly what I was looking for. I read this entire document. Several times.
Have you ever researched something, only to realise the magnitude of effort that awaits in order to realise whatever goal you’re trying to achieve? That’s how I was feeling, especially when I looked at the source code in the appendix.
Finishing the solution – RSA Key Recovery in Python
It took me a couple of days effort, and what I arrived at was a working Python (albeit Python 2) solution that amazingly is able to reconstruct the RSA key primes (p and q) in just a matter of seconds – all from the CRT exponents.
Behold the solution published here on Github. Enjoy, and stay safe out there.
* Feature image for this story, courtesy of Thomas T and Unsplash.