Cracking SHA1 with EC2 GPU instances.

syg00 · 11-28-2010, 03:01 AM

Had to happen I guess - cheap cracking on the cloud; see here

win32sux · 11-28-2010, 03:19 AM

Honestly, I don't get what all the fuss is about. This news story just serves as a reminder of the importance of using strong passwords. The whole point of having strong password requirements is to prevent this sort of thing from being feasible. I gave the article(s) a quick glance and everything I read seemed to indicate this was simply brute force attack. As such, I don't even know why SHA-1 should be singled-out, as weak passwords will be weak passwords regardless of the hash algorithm used.

I'd be interested in seeing the dollar amount of the bill if this exercise was redone using strong passwords.

Matir · 11-29-2010, 08:19 PM

It's been stated that the passwords were from 1-6 characters. Let's assume it's alphanumeric, mixed-case, no special characters. This gives us a keyspace of 52^6, or about 10^11. This was searched in 49 minutes. (In reality, they probably only searched half the keyspace, but let's assume they did the whole thing). Now let's assume you have a fairly secure password of 10 characters from the same set. 52^10 is now 10^17, which will take 1 million times as long to search (10^17/10^11=10^6). Suddenly, their 49 minutes is 816,667 hours (important because at the article's stated $2.10/hour, this costs $1,715,000 to crack) or 93 computer-years. My password (18 characters, mixed case, numeric, and symbols) would take a search of 58^18 ~= 10^31 = 10^20 times as long at a cost of $171,500,000 Trillion Dollars.

Oh, and did I mention that most real-world implementations salt passwords so you can't go and "kill 2 birds with one stone"? They'll have to crack each password separately.

Nice proof of concept, no real threat here. Botnets could've done this long ago, and for free(ish).

win32sux · 11-30-2010, 06:15 AM

I get different numbers for some reason. My total dollar amount for a 10-character password comes out to $460,554,713. I'm using the 128 ASCII printable characters here, but it shouldn't make a difference as we're using the same completion time, so the comparison remains equal.

Keyspace for weak password from news article: 128^6 = 4,398,046,511,104
Time it took to crawl the keyspace*: 0.817 hours.
Attempts per hour: (128^6) / 0.817 = 5,383,165,864,264

Keyspace for a half-decent password of 10-characters: 128^10 = 1,180,591,620,717,411,303,424
Time it would take to crawl the keyspace at the above rate**: (128^10) / 5,383,165,864,264 = 219,311,768 hours (approx. 25,000 years).
At $2.10/hour that's: 460,554,713.00 USD

Using a 12-character password, which I believe is what most computer books today suggest as a minimum, would get us:
(128^12) / 5,383,165,864,264 = 410,183,104 years and 7,545,728,399,102.00 USD

* Rather to crack, which like you said doesn't require crawling the entire keyspace, but I'm making the same assumption as you for simplicity.
** Yes, the rate would change in reality as the hardware would be scaled or a botnet used instead, but bare with me.

Matir · 11-30-2010, 06:41 AM

Your math is different because you're assuming a different character set. The time it takes increases exponentially with a larger character set, but your rate of attempts per hour is linear.

Also note (just for discussion purposes) that you cannot use the entire 128 characters of ASCII in a password in most systems. Characters such as \0, \r, and \n are almost certainly rejected, and many web-based apps choke on white space, etc.

win32sux · 11-30-2010, 07:24 AM

Quote:

Originally Posted by Matir

Your math is different because you're assuming a different character set. The time it takes increases exponentially with a larger character set, but your rate of attempts per hour is linear.

Crap, you're right! Thanks for reminding me how much I suck at math!

Yeah, I went ahead and used my same calculation using 40 characters (a random number I picked) instead of 128 and it confirmed the difference which I didn't expect. I mean, I know the difficulty increases exponentially, but my fault was in assuming that as long as we keep the total time the same we could draw the same conclusions. Clearly we can't, as you've indicated. Thanks for setting me straight!

FWIW, here's what my math looks like with 40 instead of 128:

Keyspace for weak password from news article: 40^6 = 4,096,000,000
Time it took to crawl the keyspace*: 0.817 hours.
Attempts per hour: (40^6) / 0.817 = 5,013,463,892

Keyspace for a half-decent password of 10-characters: 40^10 = 10,485,760,000,000,000
Time it would take to crawl the keyspace at the above rate**: (40^10) / 5,013,463,892 = 2,091,520 hours (approx. 239 years).
At $2.10/hour that's: 4,392,192 USD

Using a 12-character password, which I believe is what most computer books today suggest as a minimum, would get us:
(40^12) / 5,013,463,892 = 382,012 years and 7,027,507,200 USD

win32sux · 11-30-2010, 07:35 AM

While we're on the subject of math, I'd like to ask you a question about this. Normally when I think about keyspaces it's with regards to actual encryption keys. Hence, for example, a 128-bit keyspace is exactly that: a 128-bit keyspace (2^128). There's gonna be 128 bits in it. In this case, however, all we know is that the password will be between 1 and 6 characters. So, we could have some that are really short, with the constraint being that the characters don't have any blanks before or after them. Like, for example, we could have a 3-character password but the three characters would need to be at the start. This tells me that calculating the keyspace would be different than with actual keys, where it's either all or nothing. I'm having flashbacks of math class where we did permutations and combinations, but I'm not sure if that's the way to go about it. Any light you could shed on this would be great.

H_TeXMeX_H · 11-30-2010, 09:12 AM

Meh, I think the more important thing to worry about with md5 and sha1 is collisions, that's the main reason to change to something else.

anomie · 11-30-2010, 06:11 PM

Quote:

Originally Posted by syg00

Had to happen I guess - cheap cracking on the cloud; see here

Some of the user comments that followed the actual experiment/essay were pretty enlightening. Main takeaway: SHA1 may not be perfect, but the author did not exploit any cryptanalysis of it. Instead, he helped reinforce that brute forcing 6-byte passwords in rapid fashion is within the capabilities of us peasants.

Use strong passwords.

Matir · 11-30-2010, 06:26 PM

Quote:

Originally Posted by win32sux

While we're on the subject of math, I'd like to ask you a question about this. Normally when I think about keyspaces it's with regards to actual encryption keys. Hence, for example, a 128-bit keyspace is exactly that: a 128-bit keyspace (2^128). There's gonna be 128 bits in it. In this case, however, all we know is that the password will be between 1 and 6 characters. So, we could have some that are really short, with the constraint being that the characters don't have any blanks before or after them. Like, for example, we could have a 3-character password but the three characters would need to be at the start. This tells me that calculating the keyspace would be different than with actual keys, where it's either all or nothing. I'm having flashbacks of math class where we did permutations and combinations, but I'm not sure if that's the way to go about it. Any light you could shed on this would be great.

It's basically the same thing either way. With a 128-bit encryption key, you have 128 values that can be one of 2 possibilities (0 or 1). This is 2^128. For text-based passwords, we usually think in characters rather than bits. If you have 6 characters that can each have one of 62 values (26 lower case + 26 upper case + 10 digits), it's 62^6. In other words, it's [possibilities for character 1] * ... * [possibilites for character n].

Some systems involve "must start with a letter" or similar. For a 6-character password that must start with a letter, you can then assume it's 52*62^5. For any sort of speed analysis, these restrictions are generally ignored.

I like to convert the size of values to base 10 for most discussion, as most people are fairly comfortable talking in base 10. For anyone who hasn't been in a math class recently, that's 10^log(ORIGINAL). So, in this case, I do 10^log(62^6) == 10^11.

Matir · 11-30-2010, 06:28 PM

Quote:

Originally Posted by H_TeXMeX_H

Meh, I think the more important thing to worry about with md5 and sha1 is collisions, that's the main reason to change to something else.

Collisions are a concern for digital signatures, but not generally for passwords. On a strong hash, the odds of there being a collision that is simpler than your real password (i.e., will be found first by a dictionary or brute force attack) is nearly 0.

H_TeXMeX_H · 12-01-2010, 04:11 AM

I was just considering the possibility that the processing power would be used to generate files with the same checksum and then upload them to distribute malware.

For passwords, indeed the most important thing is to have a strong password. However, it's one thing to say this, and it's another thing to get people to use strong passwords and remember them.

win32sux · 12-01-2010, 05:45 AM

Quote:

Originally Posted by Matir

It's basically the same thing either way. With a 128-bit encryption key, you have 128 values that can be one of 2 possibilities (0 or 1). This is 2^128. For text-based passwords, we usually think in characters rather than bits. If you have 6 characters that can each have one of 62 values (26 lower case + 26 upper case + 10 digits), it's 62^6. In other words, it's [possibilities for character 1] * ... * [possibilites for character n].

Right, but what I mean is that with crypto keys the length remains the same. With passwords, we have cases where the length can be anywhere between X and Y. For example, say I have a 3-bit key. The keyspace (2^3 = 8) would look something like:

000, 001, 011, 111, 110, 100, 101, 010.

...and that's it.

If, OTOH, we say the key could be anywhere between 1 and 3 bits, then the possibilities increase, right? Like, now it could also be:

00, 01, 10, 11 and 1, 0.

...I think this is calculated as: (2^3) + (2^2) + 2 = 14 ...but what's the formula for this? Using your 62-character example, how can we quickly determine the possibilities for a variable length password such as in this case, where it was 1-6 characters? I reckon the result should be the same as manually breaking it down as: (62^6) + (62^5) + (62^4) + (62^3) + (62^2) + 62.

EDIT: I guess what I'm saying/asking is that I know how to automate this sort of thing using a programming language (where you ask the user to enter the min/max lengths, etc.), but I'm curious about how to do it if all I have is a calculator. Like, say I want to quickly calculate the keyspace for a password that allows 94 ASCII characters, and has a length between 12 and 36. How would I do that?

win32sux · 12-03-2010, 04:19 PM

Quote:

Originally Posted by win32sux

I guess what I'm saying/asking is that I know how to automate this sort of thing using a programming language (where you ask the user to enter the min/max lengths, etc.), but I'm curious about how to do it if all I have is a calculator. Like, say I want to quickly calculate the keyspace for a password that allows 94 ASCII characters, and has a length between 12 and 36. How would I do that?

Okay, I think I found one calculator-compatible shortcut, and I'm posting it in case it helps anyone else:

(CharacterSetLength^(PasswordMaxLength+1)-CharacterSetLength^PasswordMinLength)/(CharacterSetLength-1)

So, for the scenario I presented in the quoted text above (94 ASCII, length of 12 to 36), the calculation would go like:

Code:

(94^(36+1)-94^12)/(94-1) = 108,955,117,812,980,031,260,829,358,977,018,849,062,057,332,069,268,020,020,476,008,906,141,696

...which AFAICT checks-out if we do things manually:

Code:

A = 94^12 = 475920314814253376475136
B = 94^13 = 44736509592539817388662784
C = 94^14 = 4205231901698742834534301696
D = 94^15 = 395291798759681826446224359424
E = 94^16 = 37157429083410091685945089785856
F = 94^17 = 3492798333840548618478838439870464
G = 94^18 = 328323043381011570137010813347823616
H = 94^19 = 30862366077815087592879016454695419904
I = 94^20 = 2901062411314618233730627546741369470976
J = 94^21 = 272699866663574113970678989393688730271744
K = 94^22 = 25633787466375966713243825003006740645543936
L = 94^23 = 2409576021839340871044919550282633620681129984
M = 94^24 = 226500146052898041878222437726567560344026218496
N = 94^25 = 21291013728972415936552909146297350672338464538624
O = 94^26 = 2001355290523407098035973459751950963199815666630656
P = 94^27 = 188127397309200267215381505216683390540782672663281664
Q = 94^28 = 17683975347064825118245861490368238710833571230348476416
R = 94^29 = 1662293682624093561115110980094614438818355695652756783104
S = 94^30 = 156255606166664794744820432128893757248925435391359137611776
T = 94^31 = 14688026979666490706013120620116013181398990926787758935506944
U = 94^32 = 1380674536088650126365233338290905239051505147118049339937652736
V = 94^33 = 129783406392333111878331933799345092470841483829096637954139357184
W = 94^34 = 12199640200879312516563201777138438692259099479935083967689099575296
X = 94^35 = 1146766178882655376556940967051013237072355351113897892962775360077824
Y = 94^36 = 107796020814969605396352450902795244284801403004706401938500883847315456

A+B+C+D+E+F+G+H+I+J+K+L+M+N+O+P+Q+R+S+T+U+V+W+X+Y = 108955117812980031260829358977018849062057332069268020020476008906141696

Matir · 12-03-2010, 05:54 PM

FWIW, it's essentially irrelevant to consider the minimum length for purposes of calculating runtime. A better way to approach things is to include one more character than there really is as a sort of "null" byte (e.g., a 7-character password can be considered to be an 8-character password with one byte set to NULL).

Your value for 12-36, 94 character set is about 2^235.981. Using the 95 "character set" for length 36 (e.g., 95^36) is about 2^236.514. As you can see, it's pretty close. If you want to get really precise, use the original character set for the minimum length and the +1 for the remaining characters. For example, 94^12*95^(36-12) yields a value of 2^236.332. Of course, just using 94 characters for 36 places (94^36) yields 2^235.965.

The reality is that the largest term dwarfs the smaller terms by so much that it becomes the dominating factor. You can see that in the A-Y values you posted, each one increases by 2 digits, or an approximate factor of 100.