5 ms·

Password cracking experts decipher elusive Equation Group crypto hash

67 points by ghosh 12y ago

BuildTheRobots 12y ago
Article[1] and comments[2] from yesterday regarding the Equation Group [1] http://arstechnica.com/security/2015/02/how-omnipotent-hackers-tied-to-the-nsa-hid-for-14-years-and-were-found-at-last/ http://arstechnica.com/security/2015/02/how-omnipotent-hacke... [2] https://news.ycombinator.com/item?id=9058701 https://news.ycombinator.com/item?id=9058701
mirkules 12y ago
I'm curious how these password cracking techniques work. I have almost no background in cryptography, so pardon the basic question: is this basically just running billions of text passwords through the md5 algorithm and comparing the results with the unknown string? I assume that the hash would have been salted, so how would this work exactly (unless they obtained the salt too)?
- jacobparker 12y ago
  You store the salts with the hashes. The basic idea is that salts force attackers to actually do a hash ("slow") instead of pre-computing hashes for common passwords and doing a dictionary lookup ("fast".) All that is to say that if you (the attacker) have the hash you probably also have the salt.
  - mirkules 12y ago
    That makes sense. Since md5 can have collisions, is it also safe to assume that the cracked username is not guaranteed to be 100% accurate? In reading about it some more (particularly the md5 collision demo based on Patrick Stach's implementation), it looks like it would be trivial to create an md5 hash that resolved to a "fake" username while the real username remained uncracked. Although that would mean that both the fake username and the real one would be exempt from the exploit, so there would really be no point to it.
    - laxatives 12y ago
      Given this context, it seems like the cracked username is accurate (both usernames are "unregistered" in different languages).
- shangxiao 12y ago
  > is this basically just running billions of text passwords through the md5 algorithm and comparing the results with the unknown string? Yes: "using a computer that tried more than 300 billion plaintext guesses every second" The Arabic version was obtained by doing an educated guess based on the English version
- huhtenberg 12y ago
  Straight (unsalted) hashes are typically reversed with the help of a rainbow table - http://en.wikipedia.org/wiki/Rainbow_table http://en.wikipedia.org/wiki/Rainbow_table
sp332 12y ago
A clarification from the comments there: It's not Unicode, or an ISO charset, but a codepage mapping. $ echo -n غير مسجل | iconv -t CP1256 | md5sum e6d290a03b70cfa5d4451da444bdea39 -
- laxatives 12y ago
  Not too familiar with this stuff but doesn't the salt get appended to the word before hashing? Whats the point of the salt if you can find the input of the hash like this? Or does this mean that a salt was not used?
  - sp332 12y ago
    It looks like the MD5 matches the given one without a salt. I think the hash was taken from the malware, not a password database. In fact these are usernames, not passwords. So the malware was just using this as a quick check of a couple of usernames.
pineapplepoop 12y ago
I don't have much experience but in my baaic security class they always reiterate that don't use MD5 or SHA(1 or 2) hashing algorithms because of known vulnerabilities making it easy to crack. Any reasoning behind its use?
- wtbob 12y ago
  SHA2 is believed to be highly secure for the present.
coding4all 12y ago
Kaspersky Lab spent more than two weeks trying to crack the MD5 hash using a computer that tried more than 300 billion plaintext guesses every second. Interesting. Aren't MD5s vuln to collisions? http://www.wolframalpha.com/input/?i=%28convert+2+weeks+to+seconds%29%28300+billion%29 http://www.wolframalpha.com/input/?i=%28convert+2+weeks+to+s...
- sp332 12y ago
  No. You can construct two messages with the same MD5, but only if you control both messages. Finding a message with the same MD5 as a given message, or password, is still infeasible. Even if you try 3x10^17 ~= 2^58 in two weeks, MD5 has 128 bits of entropy so you'd need 2^70 ~= 1.1x10^21 times that to exhaust the space. Wolfram Alpha says that's 3.3x10^9 times the age of the universe.

67 points by ghosh 12y ago

Article[1] and comments[2] from yesterday regarding the Equation Group [1] http://arstechnica.com/security/2015/02/how-omnipotent-hackers-tied-to-the-nsa-hid-for-14-years-and-were-found-at-last/ http://arstechnica.com/security/2015/02/how-omnipotent-hacke... [2] https://news.ycombinator.com/item?id=9058701 https://news.ycombinator.com/item?id=9058701

mirkules 12y ago

I'm curious how these password cracking techniques work. I have almost no background in cryptography, so pardon the basic question: is this basically just running billions of text passwords through the md5 algorithm and comparing the results with the unknown string? I assume that the hash would have been salted, so how would this work exactly (unless they obtained the salt too)?

jacobparker 12y ago
You store the salts with the hashes. The basic idea is that salts force attackers to actually do a hash ("slow") instead of pre-computing hashes for common passwords and doing a dictionary lookup ("fast".) All that is to say that if you (the attacker) have the hash you probably also have the salt.
- mirkules 12y ago
  That makes sense. Since md5 can have collisions, is it also safe to assume that the cracked username is not guaranteed to be 100% accurate? In reading about it some more (particularly the md5 collision demo based on Patrick Stach's implementation), it looks like it would be trivial to create an md5 hash that resolved to a "fake" username while the real username remained uncracked. Although that would mean that both the fake username and the real one would be exempt from the exploit, so there would really be no point to it.
  - laxatives 12y ago
    Given this context, it seems like the cracked username is accurate (both usernames are "unregistered" in different languages).
shangxiao 12y ago
> is this basically just running billions of text passwords through the md5 algorithm and comparing the results with the unknown string? Yes: "using a computer that tried more than 300 billion plaintext guesses every second" The Arabic version was obtained by doing an educated guess based on the English version
huhtenberg 12y ago
Straight (unsalted) hashes are typically reversed with the help of a rainbow table - http://en.wikipedia.org/wiki/Rainbow_table http://en.wikipedia.org/wiki/Rainbow_table

sp332 12y ago

A clarification from the comments there: It's not Unicode, or an ISO charset, but a codepage mapping. $ echo -n غير مسجل | iconv -t CP1256 | md5sum e6d290a03b70cfa5d4451da444bdea39 -

laxatives 12y ago
Not too familiar with this stuff but doesn't the salt get appended to the word before hashing? Whats the point of the salt if you can find the input of the hash like this? Or does this mean that a salt was not used?
- sp332 12y ago
  It looks like the MD5 matches the given one without a salt. I think the hash was taken from the malware, not a password database. In fact these are usernames, not passwords. So the malware was just using this as a quick check of a couple of usernames.

pineapplepoop 12y ago

I don't have much experience but in my baaic security class they always reiterate that don't use MD5 or SHA(1 or 2) hashing algorithms because of known vulnerabilities making it easy to crack. Any reasoning behind its use?

wtbob 12y ago
SHA2 is believed to be highly secure for the present.

coding4all 12y ago

Kaspersky Lab spent more than two weeks trying to crack the MD5 hash using a computer that tried more than 300 billion plaintext guesses every second. Interesting. Aren't MD5s vuln to collisions? http://www.wolframalpha.com/input/?i=%28convert+2+weeks+to+seconds%29%28300+billion%29 http://www.wolframalpha.com/input/?i=%28convert+2+weeks+to+s...

sp332 12y ago
No. You can construct two messages with the same MD5, but only if you control both messages. Finding a message with the same MD5 as a given message, or password, is still infeasible. Even if you try 3x10^17 ~= 2^58 in two weeks, MD5 has 128 bits of entropy so you'd need 2^70 ~= 1.1x10^21 times that to exhaust the space. Wolfram Alpha says that's 3.3x10^9 times the age of the universe.