How would you know a certificate/private key if you extracted it from RAM? Or would you?

Question

Related to, of course, the heartbleed vulnerability, I've been reading the news about the worst case scenario for this attack being the extraction of the SSL private key, because, of course, this would allow the attacker to decrypt all traffic to and from the compromised server, including [probably, depending on forward secrecy] any traffic that's been captured and stored somewhere.

This got me thinking, assuming the worst case scenario, that your Heartbleed vulnerable server had echoed back memory containing your private key... how would the attacker be able to differentiate it from other memory contents, or uninitialized memory, or what have you? Is there a header/footer, or a telltale pattern in the key data itself? I know some RSA Key forms (PEM/base64) have headers/footers in the file (-----BEGIN FOO BAR KEY----- and -----END FOO BAR KEY-----), though I'm having trouble imagining those strings loaded into memory. Is it maybe given away by having something recognizable using a pointer to it?

It doesn't seem like something you can brute force (trying every X bit combination of memory content against 64 KB of memory seems like it would generate an astronomically large number of permutations).

So, how's it done? How is a cryptographic key in memory recognized as a cryptographic key? And in a related question, is the answer different or the same for a symmetrical crypto key? (such as you might extract with a cold boot attack against a system using full disk encryption, for example.)

Answer 1

Yes. Most private keys have an easily identifiable format.

If its say an RSA private key generated with openssl, they have a specific format e.g., will always start with the same three bytes depending on key size:

30 82 01 (for 768 bit key or MIIB in base64)
30 82 02 (for 1024 bit key or MIIC in base64),
30 82 04 (for 2048 bit key or MIIE in base64),  
30 82 09 (for 4096 bit key or MIIJ in base64).

There are some other types of formats that the private key can be stored in as well.

You can test this yourself with openssl using the commands: openssl genrsa 1024 (1024 means 1024 bit key to see the key in its base64 representation. )

For more documentation on the format see this StackOverflow answer: Where can i find some documentation on the format of an RSA public key?

Answer 2

As an addendum to dr jimbob's answer:
There are utilities that look for these patterns and try to extract keys that way.

Disclaimer: I have not tried any of these utilities. This post is just a nicer version of the links posted by user "void-star" on HN. (See below.)

• Whitepapers about the general idea:
  • Adi Shamir and Nicko van Someren, 1998-09-22, Playing hide and seek with stored keys
  • Tobias Klein, 2006, SslKeyFinder
• Implementations:
  • Yara ruleset that looks for the pattern:
    https://github.com/SpiderLabs/yara-ruby/blob/master/samples/sslkeyfinder
  • Again Yara rules, but this time embedded in Python and usable as the "dumpcerts" plugin for the "Volatility" toolkit: dumpcerts.py. (And "Volatility", according to the Kali package description, seems to be a general framework for extracting all sorts of payloads from RAM dumps.)

Further reading

• Thread on Hacker News: 2014, Stealing unencrypted SSH-agent keys from memory
  • And especially this answer by user "void-star"

Answer 3

As a (nother) addendum to StackzOfZtuff and dr jimbob's answer's

the Adi Shamir et al. paper Playing hide and seek with stored keys takes a very different approach, than looking for headers

The Shamir approach relies on comparing blocks of data in the complete memory string (i.e. dump the entire contents of memory / disk as a string) and seeing if they are mathematically related to a previously known public key.

In order to find keys where there isn't a previously known public key, a check was made to check the entropy of the data.

Since we know that key data has more entropy than non-key data, one way to locate a key is to divide the data into small sections, measure the entropy of each section and display the locations where there is particularly high entropy

Because keys are intentionally random, this data stands out against a backdrop of data that isn't as random. This attack has the advantage that it should be possible to locate any cryptographic key.

Our techniques seem to be applicable to a wide variety of other public key schemes, in addition to the RSA scheme.

As dr jimbob pointed out, Tobias Klein took the approach of looking for the headers

The following shows the hexadecimal representation of this ASN.1 syntax:
30 82 ?? ?? - SEQUENCE (30 82), length of the SEQUENCE (?? ??)
30 82 ?? ?? - SEQUENCE (30 82), length of the SEQUENCE (?? ??)

As all certificates should be represented in this syntax, we have a pattern to search for.

With full disk encryption you would no longer be able to search for random data on the disk, because everything would be random. You would also no longer be able to search for headers because they would be encrypted.

However once the machine is booted, it would be possible to read keys directly from memory by either of these techniques. This is even easier for a VM (see my answer here)