Cracking the Private RSA Key

[Back] One of the weakest things about cryptography is that you might have a strong encryption key (such as a 128-bit or 256 bit key), but you create it from a pass phrase, or where you protect it with a password. This considerable reduces the strength of the key. For example, if our password is generated from a list of 1,024 words, we only have an equivalent key size of 10 bits. For one million passwords, it rises to 20 bits, which is considerably shorter than a 128-bit key. The overhead is the time taken to try the key.

So let's look at cracking the private key. The RSA private key can be stored in a PEM file format. This applies a passwords onto the private. Unfortunately this can often be cracked with a brute force or dictionary attack.The method we can use is illustrated below:

First we generate a private key and setup a password of "qwerty":

:~/crackkey$ openssl genrsa -des3 -out private.pem 2048
Generating RSA private key, 2048 bit long modulus
....................+++
...+++
e is 65537 (0x10001)
Enter pass phrase for private.pem: qwerty
Verifying - Enter pass phrase for private.pem:qwerty

Note that we can also use the "-passout" optionn to automate the password:

openssl genrsa -aes128 -passout pass:qwerty -out private.pem 2048

Next we will list the key:

:~/crackkey$ cat private.pem 
-----BEGIN RSA PRIVATE KEY-----
Proc-Type: 4,ENCRYPTED
DEK-Info: DES-EDE3-CBC,8D8D035DDCEBAEEE

tpNB6AxbpSpYiNQnFroHMFruBG5/TOnGXSVXxmHPRHkctUvhChMHy2g3WKxe+Gm2
+UgCU5r8xZ6pyJ6QcVDJjV2cybRtjpBeoqDd9s30FaXoTHQLQhYm/yME8iP7NWxl
+oxUk+NlVqWClfWlxKYEYqLfKjTQvpO64TBHv3lBw8DhApRLbNB2Z9KMtxt/c7UE
ULzJDYCxQWpYmhP2YcDUp/juOCjxoRAicVDiW2F6MbfXiy3urlMV81frHpcjkwPW
FcetsPr5pBhypdY9nf3zQYQsXyw1X/OlcINPZsTJpIyyd1JYEfWQ0Wyye7Y0Oy45
0jlxKMRrfCeWgo3RhuYGDuRqpJdB++3t1WWY/A1ml6VqX77ZX00lNRDpESnw5lYd
R1pVO9lvsVXExrP/CoUpn3IjGc+hEKyMZzXXnpMpCjg1K5SppJT018n9Yqwa0kVw
FFxKPqoPo4M7o4KuAgYzrE8ntenIm0H9F9UDBWenbGVSOmzlAt+ONmpwQwNd54E7
vSc47m6AON7cHK9d3AzkSwZD19WofQYSEupaa2InCu1FTrca9HB7aKSK94+3Tq97
aWzajJk2eMWUcyEWzO5sR5jmJMthPBQYHio3z02aLhRoUBrA2iMUAY2wKniUnk1b
v3U8P1GRE9VIscchbyQvbQh4SlLUGlg7t5oixBwUYZgG7zdWmHmsiDtCWlpqhsCR
2Gx5suA/luRJG6OG2AZjkW5YKgkjAjQlqS+WduB/cWHHBBKlRwc/vXzt8tEUs+5q
bT3jgPUIh4swWtK7o76XibSMq1FWCMOFSGXMKG2x4fjjLmXRQpzwfgPLxSnPdfi0
XjuVEcRyAgJDpNzCpile33VYT9iWGQl2WHGQ7OjYTeGejER5AKalHLYR1weUC5rV
yRTdCdwAf2QfagSu8iB+PhIWi6sVemTD95pmgX/FT5sry/8kIGM9ofmGuBz2OtFa
hRi2xcHtmiCajwwXY6chLYH0D9AcHNZVPyQ1g620e2OhLuLyCLYZ29mpplIsTLT+
IY2FVRbp4hwnuJFWUGKfEHwJSi6pM21/yzvG80E5Zarnroza8iFcFE31G9Hzsy6Q
jAf0niY8xG9LrXQwPLgvSTkAsgprMYOvNoDPyYISqxnAN8hyWzg2SwcSBYTt+gsu
U2uU4PZyQZcZMAx/ipxPqznVjJERPNswMdrulXjHi/ogRotItmnGqjRl6UY3IS70
uKhdk0vpmRGcsMGa7DjqGRcCPptnFn6A8ASJeuP1qga4WCFOTJeBs8kGP9HiTy/N
DlnxhlQHDWNdLlUwKmOW5pqgrM12hLVf4TVTR7wjUuC7wzBp/1bhaiUifr8p8Ie0
mvC9Pz79TWg7oKCZCkdOv6valYqtwFXN7mu/a/neHOFh7Tqao9q5+iK1zdpwX1jv
ESn/O/zOFCFcK1Q2M66P9rvGqv73U2zyO22219LpbEqWh0IHARmikaZgS6XLHGVZ
mNQyjfDsO55zJHVOVA6+pw2W09fZVBS1xgV4hK3q3Egx2KytLzVtcOeTK+2MZTwb
aMBMYui04Dc4PklgwUO7cSpMG9GhBn3W0cNx8ppBXwCDFnGyaA5kfG3HjaFcseDn
-----END RSA PRIVATE KEY-----

In this case we have encrypted the key with DES-EDE3-CBC (3-DES) and with a salt of "8D8D035DDCEBAEEE" (as we used the -des3 option, and where other options include -aes128, -aes192, -aes256, -des, and -idea). Normally we would export the public key with:

:~/crackkey$ openssl rsa -in private.pem -pubout > key.pub
Enter pass phrase for private.pem: qwerty
writing RSA key
:~/crackkey$ cat key.pub
-----BEGIN PUBLIC KEY-----
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEAsp0LoOvjc5eyjcFD6wJy
SvQRBf6E++VbXCKWhB2X387j6vwjP0wKxw5BVrvFf/YfLBZnN30a598vr3exhxii
A6r8pMl4mxkuNSn0EfPHHWACdmdBCBMhOqvnjivaAXoy9P857EY1jRJGmP+04Wcd
Pi74dVNfMlJ6h37+iQl2k5c94+A3AtDw2+lNDZx621zOUa3fUjH1ECk6eBBMITt6
C18CxzigoKGau+bXxusWtbY6illKNOFskQNrED9F2qZdt6882bzc/wXVyELBVHqk
MgbjNTGW+bH9CpIsnuTdL/TCg0Ade6KUaBqOww42CJt0nmPD0ubs82Pyd/2b6krc
VQIDAQAB
-----END PUBLIC KEY-----

If we try the wrong password on the private key file we get an exception:

:~/crackkey$ openssl rsa -in private.pem -out out.key -passin pass:password123
unable to load Private Key
140735838671752:error:06065064:digital envelope routines:EVP_DecryptFinal_ex:bad decrypt:/BuildRoot/Library/Caches/com.apple.xbs/Sources/libressl/libressl-22/libressl/crypto/evp/evp_enc.c:529:
140735838671752:error:0906A065:PEM routines:PEM_do_header:bad decrypt:/BuildRoot/Library/Caches/com.apple.xbs/Sources/libressl/libressl-22/libressl/crypto/pem/pem_lib.c:486:

Next we will try the correct password:

:~/crackkey$ openssl rsa -in private.pem -out out.key -passin pass:qwerty
writing RSA key

and the message we receive is "writing RSA key". We thus just need to write a Python program which reads-in a dictionary file, and then detects the "writing RSA key" message. We now use a dictionary file (pass.lst [link]):

:~/crackkey$ head pass.lst 
12345
abc123
password
computer
123456
tigger
1234
a1b2c3
qwerty
123

And then run some Python code:

:~/crackkey$ python keyscrack.py 

0/3106
1/3106
2/3106
3/3106
4/3106
5/3106
6/3106
7/3106

The key is: qwerty

And we have cracked the key. If we view the key, we get (out.key):

:~/crackkey$ cat out.key
-----BEGIN RSA PRIVATE KEY-----
MIIEpQIBAAKCAQEA2KVGBwQdq9QyUWGPqvktNcyu3CqiZRHDlWihP3NxXklkbxa+
3L2z+hS4xxKCj6YSOOXuOCYElcjr+2oNRgvH2ExM5hQxWeYxjZQmn60rY8bQJrJQ
Zhov5U/zIdItToEakRbX1SwSPIWW5Dtqu7Q4ptN62eM6Uvkkpa/FBrRy6p+bpRPB
Z/28VAcMUVyRAUIYV8yFRY+gP3i3T1rnhEeax4omNrXN7bcw/znRxdTl2wplliMw
sJ9EXKucz4+d9xSjFK9qvsinU2xk4/5q2Sh+2TTqpvT8dYQZQl/SPBAolyT2wo+w
IQoHjvOq/L3buGubHNpfzl2hOrfWHnCCMGUvmwIDAQABAoIBAQC9UUAupWQgYeBO
yYi4ieL+Ho23i/I5jBp0F+jA/+rT0CLaCPBlCcmbAjyuifhZ+2/1FMjlfCOJmPjO
zVAoI+dRluukK4Us4EHxTMOrybIfEP+YsT4c20l7hDAdIAPDlIJYw7N8b3TIOp0v
eNS+jrDq5+d1PGIdW+awezcbstixOYkGi+MMGjPn0sHxr0G11B6GEzXy4JbQTatF
QD9Q6o8oO1p+0NS0WBaMnDdHQ9bmpVYA4LJHP+wIePZKJgNPpjaXOvNtD/4HRUwW
W/zuMEUs6D35k8VwhPfe5yo6ixGO7lZaen1cpXy/JjAELC434N2LpWeeZW6sIjtp
q03dmLMRAoGBAPMO15gvkNFQ5fYA4q/SQINX5QUSPy0xLp58uxCp/nMopB1Adroy
qXu/rvySmnizNHSOCYUwMOJg5VibpiezdzzNVPgYI3egrL7RnIUQ7fP2bu9McnSl
KI2i8GYXwWatxBnoIaZjRDUQsxDjnV3GNoHK0qT5PDQb1paGoCh1HNwvAoGBAOQu
ZoeugDXytlWZcuZtNlO8aF0HmD+zKSeR35IdrUZTkSLw681XBy/JgvdMzQaJ88xw
VrwRZOaHHE13/VIDdCz1DX9WP9z6jLX6ULfGiuYouS9CuK0cWMEcrnjR+O6V2fWt
IGTYSQn2tQqpVHoaA0vP1xAqsQ/sA/uWCBXRiCxVAoGBAJ/GbPDsq6z9Gf3pvRpJ
AwGUIMeBpCgIAZZLdgjRRqPa3m8gNivWK9VePyBnGsYnP18zE40LDcdyXLEvuDy2
27YLYESqUX5ND+FsFxDd/R33LBuATGjjPNJGfvMNwKPHrHY/QweGj4q2jI+YoJTJ
PIF7m5a5A9tZRWmz28pcmfkfAoGANmmKMZi/Ih46tLbe22v3pIgtKuIAwE/s5G64
rZM+GqMa3QYudMzn/dFD1c0OpxyGcp3nUPmk4gQeD6spUUFZls7o5RCgMgXdQBfs
36YMwU28uzRh7YXw9DvurwkDH4HEc/1Q2DtrT2DxUxWF+4fweUeatVQ43N8fJANm
8i0BF/ECgYEA7EMU9jdNgb0aBZLqrRZpBWa2WFreUsA9aLc8oeM6XxdOPi7DDW5S
merJ7GhaucXP+eafnG5iB5xb/CpJWI4RwalknhaTmEpLO+vwFeSv8fuTRhq4ySO+
woSIOMMkyvF5HVy0Osxy203tTtj2/Y+0anJd79ZmdRqgVT5doF4jLM0=
-----END RSA PRIVATE KEY-----

Python code

The Python code used is:

from subprocess import PIPE, Popen
import subprocess
import sys

def cmdline(command):
    proc = subprocess.Popen(str(command), stdout=subprocess.PIPE, stderr=subprocess.PIPE, shell=T$
    (out, err) = proc.communicate()
    return err

def main():
    words = [line.strip() for line in open('pass.lst')]
    print("\n")
    count=0

    for w in words:
        strcmd = "openssl rsa -in private.pem -out out.key -passin pass:"+w
        res=cmdline(strcmd)
        if res.startswith("writing"):
                print("\nThe key is: "+w)
                sys.exit()
        print(str(count)+"/"+str(w))
        count=count+1
    print("\n")

if __name__ == '__main__':
    main()

Presentation

Puzzle

Can you solve the password on the following [file]:

And this one [file]:

And this one [file]:

The passwords are all contained within this [file]