6 ms·

How do you know when you've found a piece of a key?

by dpweb 13y ago

nikcub 13y ago
store everything, reconstruct it all later by trying to work out which part of the heap each request is from. there is likely some sort of efficiency calculus you can do here (i'm not good at math so I have no idea what i'm talking about) where you could calculate for heap size x and probabilities y and z etc. just how many requests and what size they should be to cover the entire process heap. edit: OpenSSL wraps malloc, so it is different on different systems. You could find out what the probabilities are by looking at the source. For some reason FreeBSD's malloc gave up private keys with the default exploit length and not much effort. It was only a matter of time before other platforms were also figured out. Note that the FreeBSD exploit worked on a fresh server after boot, which might have also been the case here. Note that in the heap there are the intermediate values that and are used when constructing the connection and doing the encryption, you aren't exactly looking for '------BEGIN PRIVATE KEY------' or base64 string, you'd be looking for those - each which have a unique data type.
- adsche 13y ago
  > Note that in the heap there are the intermediate values that and are used when constructing the connection and doing the encryption, you aren't exactly looking for '------BEGIN PRIVATE KEY------' or base64 string, you'd be looking for those - each which have a unique data type. That's what I thought as well when I saw people POSTing strings like that and other people finding them. But when the key is first loaded from file, wouldn't actually all those base64 strings be in memory? Probably just pretty unlikely that they would persist for a long time without being overwritten.
  - alexkus 13y ago
    It shouldn't be about it eventually being overwritten, sensitive information like that (which isn't needed for runtime) should be actively scrubbed before the block of memory is freed. You can't, however, get away with not having the private key modulus in memory (in some form) all the time.
willvarfar 13y ago
From a piece? Hard. But brute force everything you get back? Easy. Take every key-sized chunk of heap you got back, and see if, when interpreted as the key, it is the private key to the public cert. When found, send it in!
rich90usa 13y ago
I would think that there could be some application of how genome sequencing is done? From what I understand chains of DNA are cut by restriction enzymes and these random chains are assembled together by some clever algorithms?
- Blahah 13y ago
  Depending on the nature of the strings, yes. If there is no repetition or errors in the representation of the sequence, you could use overlap layout consensus if it were small, or de-brujn or string graphs if it were large. For repetitive but error free sequences, de-brujn and string graph will do. For error-containing sequences, only the de-brujn graph (with the proviso that you'll reconstruct some false-positive sequences too).
coolj 13y ago
Brute force is infeasible if you get random heap data along with key fragments. Based on the way the exploit works[0], my amateur guess would be they sent small payloads and actually did get SSLv3 records, because they found the right heap allocation strategy for a specific build on a specific platform. [0] http://blog.existentialize.com/diagnosis-of-the-openssl-heartbleed-bug.html http://blog.existentialize.com/diagnosis-of-the-openssl-hear...

How do you know when you've found a piece of a key?

by dpweb 13y ago

How do you know when you've found a piece of a key?

store everything, reconstruct it all later by trying to work out which part of the heap each request is from. there is likely some sort of efficiency calculus you can do here (i'm not good at math so I have no idea what i'm talking about) where you could calculate for heap size x and probabilities y and z etc. just how many requests and what size they should be to cover the entire process heap. edit: OpenSSL wraps malloc, so it is different on different systems. You could find out what the probabilities are by looking at the source. For some reason FreeBSD's malloc gave up private keys with the default exploit length and not much effort. It was only a matter of time before other platforms were also figured out. Note that the FreeBSD exploit worked on a fresh server after boot, which might have also been the case here. Note that in the heap there are the intermediate values that and are used when constructing the connection and doing the encryption, you aren't exactly looking for '------BEGIN PRIVATE KEY------' or base64 string, you'd be looking for those - each which have a unique data type.

adsche 13y ago
> Note that in the heap there are the intermediate values that and are used when constructing the connection and doing the encryption, you aren't exactly looking for '------BEGIN PRIVATE KEY------' or base64 string, you'd be looking for those - each which have a unique data type. That's what I thought as well when I saw people POSTing strings like that and other people finding them. But when the key is first loaded from file, wouldn't actually all those base64 strings be in memory? Probably just pretty unlikely that they would persist for a long time without being overwritten.
- alexkus 13y ago
  It shouldn't be about it eventually being overwritten, sensitive information like that (which isn't needed for runtime) should be actively scrubbed before the block of memory is freed. You can't, however, get away with not having the private key modulus in memory (in some form) all the time.

willvarfar 13y ago

From a piece? Hard. But brute force everything you get back? Easy. Take every key-sized chunk of heap you got back, and see if, when interpreted as the key, it is the private key to the public cert. When found, send it in!

rich90usa 13y ago

I would think that there could be some application of how genome sequencing is done? From what I understand chains of DNA are cut by restriction enzymes and these random chains are assembled together by some clever algorithms?

Blahah 13y ago
Depending on the nature of the strings, yes. If there is no repetition or errors in the representation of the sequence, you could use overlap layout consensus if it were small, or de-brujn or string graphs if it were large. For repetitive but error free sequences, de-brujn and string graph will do. For error-containing sequences, only the de-brujn graph (with the proviso that you'll reconstruct some false-positive sequences too).

coolj 13y ago

Brute force is infeasible if you get random heap data along with key fragments. Based on the way the exploit works[0], my amateur guess would be they sent small payloads and actually did get SSLv3 records, because they found the right heap allocation strategy for a specific build on a specific platform. [0] http://blog.existentialize.com/diagnosis-of-the-openssl-heartbleed-bug.html http://blog.existentialize.com/diagnosis-of-the-openssl-hear...