Toggle between light and dark mode.
Your selection will not be saved. From GDPR with ❤.

All Your Private Keys are Belong to Us

How to Find and Extract RSA Private Keys and Certificates Hidden in Large Amounts of Data

Last Updated on December 6, 2020

Cover Image
Photo by Chunlea Ju on Unsplash.

In 2006, I published a paper titled »All Your Private Keys are Belong to Us. Extracting RSA Private Keys and Certificates from Process Memory« in which I discussed a then novel technique to locate and extract RSA private keys and certificates hidden in process memory. What follows below is a revised, and hopefully more accessible version of the paper.

Introduction.

In this article I will discuss a technique to find and extract RSA private keys and certificates which are hidden in large amounts of data, such as memory dumps.

This technique can be used in malware analysis, memory forensics, or in attacks to extract cryptographic material, such as SSL/TLS private keys or VPN private keys.

The idea of this technique came to me after reading a paper called Playing ‘Hide and Seek’ with Stored Keys (Shamir and Someren, 1999). This paper describes theoretical approaches to find RSA cryptographic keys hidden in gigabytes of data by using stochastic information. Not an easy read, but for me, very inspiring ( 💡 ).

After finishing the paper, I came up with an alternative approach:

The standard storage formats for RSA private keys and certificates, as described in PKCS #8 and x509 respectively, are used to create a signature for locating them in memory. Using this signature, a simple pattern match could be done to extract the candidate RSA private keys and certificates in their plaintext form, which could then be verified using an external tool such as OpenSSL.

Although this approach does not have such a high scientific standard as the paper of Shamir and Someren, it has been proven to work in real-life situations 😉.

The remainder of this text is organized as follows:

  1. First, I will discuss the standard storage formats of RSA private keys and certificates, as well as the signatures to locate these in large amounts of data, such as memory dumps.
  2. Then, I will demonstrate how the extracted keys and certificates could be verified using OpenSSL.
  3. Finally, I will discuss some tools that implement the proposed methodology.

RSA Private Key Format in ASN.1 Syntax.

An RSA private key has the following ASN.1 syntax (only the relevant parts are shown):

PrivateKeyInfo ::= SEQUENCE {
 version Version,
..

The hexadecimal representation of the above ASN.1 syntax is:

30 82 ?? ?? - SEQUENCE (30 82), length of the SEQUENCE (?? ??)
02 01 00    - integer (02), length (01), value (00)

This 7-byte signature can be used to locate RSA private keys. In addition, the SEQUENCE length provides information about the length of the key. With this information it is possible to extract complete RSA private keys.

RSA Certificate Format in ASN.1 Syntax.

An RSA certificate has the following ASN.1 syntax (again, only the relevant parts are shown):

SEQUENCE {
 SEQUENCE {
..

The hexadecimal representation of the above ASN.1 syntax is:

30 82 ?? ?? - SEQUENCE (30 82), length of the SEQUENCE (?? ??)
30 82 ?? ?? - SEQUENCE (30 82), length of the SEQUENCE (?? ??)

This 8-byte signature can be used to locate RSA certificates. In addition, the length of the first SEQUENCE provides information about the length of the certificate. With this information it is possible to extract complete RSA certificates.

Key and Certificate Validation.

The described signatures to locate RSA private keys and certificates are quite weak, so there is usually a high rate of false positives, especially when there are large amounts of data to be searched. It is therefore recommended to validate the extracted keys and certificates with an external tool such as OpenSSL.

The command-line options below instruct OpenSSL to verify an extracted candidate RSA private key:

$ openssl rsa -inform DER -check -text -in extracted_key.bin

The command-line options below instruct OpenSSL to verify an extracted candidate RSA certificate:

$ openssl x509 -inform DER -text -in extracted_cert.bin

Tools.

In the original paper from 2006, I presented the details of two prototype implementations of this approach. I called these tools SSL Keyfinder. Both implementations, a plugin for IDA Pro version 4.6 as well as an exploit payload written in IA-32 assembly, are no longer available (well, I somehow managed to lose the source code 🤦).

However, third-party implementations of the approach are readily available: Volatility plugin, IDA Pro script

ⓘ Note

Michael Hale Ligh, a core developer of The Volatility Framework, wrote an interesting blog post analyzing Stuxnet's footprint in memory with the afore-mentioned Volatility plugin.

In-the-Wild Exploitation.

It seems that the so-called Equation Group (widely believed to be operated by the NSA) used a similar technique to remotely extract RSA private keys from Cisco PIX devices.

In 2016, ten years after I published my original paper, the so-called BENIGNCERTAIN exploit was dropped by The Shadow Brokers. BENIGNCERTAIN is a remote exploit for Cisco PIX devices that sends an Internet Key Exchange (IKE) packet to the victim machine, causing it to dump some of its memory. The memory dump is then parsed to extract an RSA private key and other sensitive configuration information.

I became aware of the possible connection between BENIGNCERTAIN and my paper through the following tweet.

Tweet
Disassembly of the BENIGNCERTAIN exploit.

The first screenshot in the above tweet shows that the memory dump is searched for an RSA private key signature similar to the one I described in my paper (see address .text:080496C2 in the screenshot). Then, in the second screenshot, the length of the key is extracted (see the location private_key_found). Finally, in the third screenshot, OpenSSL is used to verify the extracted candidate key (see .text:08049652).

For a more detailed description of the BENIGNCERTAIN exploit refer to the following Twitter thread.

Tweet
More information on the BENIGNCERTAIN exploit.

The Shadow Brokers leak illustrates that the proposed technique to find and extract RSA private keys from memory dumps is easy to use, very effective in the wild and extensively field-tested by the Equation Group.

Citations.

The original paper as well as SSL Keyfinder are cited in various academic journals and books.

Mitigation.

Specialized hardware, such as hardware security modules or smartcards, can safeguard cryptographic keys from such an attack.