Decrypt AES-128-CBC encypted partial RSA Key

Question

I am given a private RSA key, which header indicates that it is AES-128-CBC encypted. Note that the last ten lines of the key are missing. (This is part of an educational task.)

-----BEGIN RSA PRIVATE KEY-----
Proc-Type: 4,ENCRYPTED
DEK-Info: AES-128-CBC,8B7CE35DB731727CEABA217FAE404DB8

... 37 and a half lines with 64 characters each

The task is to find out the passphrase of the key (is known to be a four digit number). I already achieved the general cracking mechanism by using John The Ripper and added the obligatory -----END RSA PRIVATE KEY----- to the end of the partial key, but so far, the key could not be decrypted, which might be related to the fact that the last few lines of the key are missing (because CBC involves all blocks of a file). I already tried to cut the key content length to a multiple of 128bit and decrypt that, but that did not change anything. To find a proper way to still be able to decrypt the key, I need to furtherly understand the decryption process.

How does the process of decryption work, and how is the passphrase of the key involved in this? I already looked up some webpages containing wikipedia on CBC encryption in general, but I was unable to understand on how the actual decryption process does take place involving the key's passphrase.

Thanks in advance for all explanations or hints on how to approach this task.

Answer 1

Proc-Type: 4,ENCRYPTED indicates that the key is derived from the password specified by RFC 1421 §4.6.1.1 ff.. For the meaning of DEK-Info, RFC 1423 is older than AES, and I don't know of a reference other than the OpenSSL source code.

The encryption key is derived from the password using PBKDF1-MD5 as specified by PKCS#5. The salt is the second part of the DEK-Info header and the iteration count is 1. (Yes, this is ridiculously weak. Only ever use high-entropy passwords for PEM encryption, not actual memorable passwords!) Again, the only reference I know of is the OpenSSL source code: pem_bytes_read_bio_flags calls PEM_do_header which calls EVP_BytesToKey.

There is no built-in mechanism to check whether the password is correct when decrypting. An invalid password just likely results in garbage. If you pass a truncated input to a tool that expects a valid RSA key, it'll just error out all the time. You may have to write your own tool.

To determine whether the decryption of the part that you have is correct, check whether it matches the format of an RSA private key as found inside such a PEM file. This format is specified in PKCS#1 §A.1.2. If you aren't familiar with ASN.1, the Let's Encrypt ASN.1 primer should help, and of course you should look at some examples. An RSA private key begins with 0x30 (the sequence indicator), then the length (typically 0x82 and two more bytes) of the whole, then 0x02 0x01 0x00 (encoding of the version as an ASN.1 integer), then (for a 2048-bit exponent, as an example) 0x02 0x82 0x01 0x01 0x00 and the 256 bytes of the exponent value, then 0x02 0x03 0x01 0x00 0x01 for the public exponent 65537, etc.