# Getting password cracking time and byte storage from bruteforce?

I am stuck with this question, you can see it in the picture I have included below.

PARTS (a and b) I know a-z will be 26^8, A-Z will be 26^8 guesses, and 0-9 will be 10^8 guesses. But I can't relate guesses to time, I need help.

PART c) Password = 8 characters = 32 bits. SHA256 = 512 bits. total = 544 =68 bytes per (password/sha) entry. How can I relate this info to part (a) which is in time and not bytes?

• Please oh please don't post an image of a block of text out of your textbook. It's just rude. – Jeff Ferland Mar 14 '15 at 18:43

To put you on the right track, we must first take you out of the wrong track. In your case:

• If you think "268 + 268 + 108", then you are thinking wrong. That would be the count of possible passwords, assuming that a password is either a sequence of eight uppercase letters, OR a sequence of eight lowercase letters, OR a sequence of eight digits. But that's not what the text is telling; it says that passwords contain 8 characters, and that each character is an uppercase letter, a lowercase letter, or a digit. A password like "G8hw45zA" is valid, as per the question rules. Therefore, the number of possible passwords is 628 = 218340105584896 (whereas your computation yields 417754129152).

• Numbers of possible passwords relate to time through speed. If the attacker has N passwords to try, and can try T passwords per second, then he will need N/T seconds to try them all. Since, on average, the attacker will get lucky after trying out half of the possible passwords, answer to question (a) is N/(2T). With N = 628 (see above) and T = 4 millions (read the question ! It is written there). Convert the seconds to hours, since the questions asks for "how many hours...?"

• Question (b) is the same as (a), but with a larger attacker. Attacker now has k machines instead of just one, and can then try kT passwords per second. Average cracking time has become N/(2kT). Compute k such that this value is less than one hour (since you expressed the answer to (a) in hours, this is going to be simple).

• Question (c) is more interesting. Well, the interesting part is the one that is not asked. First, consider that SHA-256 is called SHA-256 for a reason, the reason being that it outputs 256 bits. If it produced 512-bit results they would not have called it SHA-256 but SHA-512. Actually, they also defined another hash function that produces 512-bit outputs, and they called it SHA-512. But here we talk about SHA-256, not SHA-512.

As stated, the table is supposed to contain N entries, each with a hash value (256 bits, i.e. 32 bytes) and the corresponding password (8 characters, which are classically encoded over 8 bytes). So 40 bytes per entry, N*40 bytes in total. This yields a rather huge result of about 8.7 petabytes. You can store that on about 2000 off-the-shelf hard disks (4 TB each).

The really interesting part comes after. At that point, all the exercise was mostly about reading: read the question, understand the words, apply some basic mathematic operations. Now we can discuss optimizations and practical issues.

(If you try to write any of the following in your homework then your teacher will likely challenge you about it, so you'd better understand it thoroughly.)

## Lookup strategy

The hash values will be sorted so that lookups are fast. But how fast ? With a classic binary search, you can find an entry among N with log N operations; in this case, there are a bit less than 248 entries, so you are in for 48 reads. With mechanical hard disks, each read access takes about 10 ms, and you need its result to know where to read next, so a lookup will take half a second. That's fast, unless the attacker has one million lookups to do (because he stole a million hashed passwords), in which case it will take all week.

A smarter attacker will parallelize things: though each disk takes 10 ms for each read operation, there are 2000 disks here, so, conceptually, 2000 accesses can be done within these 10 ms, provided that they all occur in distinct disks. This may require some more or less elaborate sorting step on the hash values to lookup.

An even smarter attacker will notice that a binary search is far from being the best that can be expected:

• The attacker can build an in-RAM index, that records the exact position of, say, one entry in one million. The index will contain 228 such entries, where an entry contains the first few bytes of the hash and an offset (a 48-bit offset, since there are 248 entries in the table in all). This should fit in 3 gigabytes or so. Finding the right one-million chunks will be done in a few microseconds by doing a RAM-only binary search in the index. The number of read accesses has been reduced from 48 to about 20.

• Hash values are quite uniformly distributed among possible 256-bit results. So, based on the first bytes of the hash value, one can compute the approximate position of the entry without doing any lookup. In a one-million entry chunk, realistically, the approximation will fall, on average, within one or two thousands of entries of the right one (because the square root of "one million" is "one thousand" -- I am lightheartedly talking about gaussian distributions here). The number of read accesses has been further reduced to about 10.

• Mechanical hard disks don't read bytes; they read sectors. And, in fact, several sectors in one go. The hard part is moving the disk heads; reading sequential data is fast. The industry measures I/O by assuming that individual accesses are for a 4 kB page. This maps to what disks do. Whenever we read "one byte" we actually read at least 4096 bytes for the same cost. This means that the last read accesses in the binary search can be coalesced in a single access, because a 4096 page will contain hundreds of entries. Number of actual read accesses is down to 2 or 3 -- more than 10 times faster than the non-smart attacker.

## Table compression

We said that an entry was 40 bytes: 32 for the hash, and 8 for the password. But that's a lot more than actually needed.

First, there are "only" 248 entries in the table, so, morally, only the first 48 bits (6 bytes) of each hash value should be needed. In particular, the attacker does not really need true uniqueness: what he wants is to narrow down the number of candidates to a few dozens, that his computer can then rehash (his computer can do 4 millions hashes per second !). So entries are now 14 bytes long (6 for the truncated hash, 8 for the password) instead of 40. Total size has shrunk from 8.7 petabytes to about 3 petabytes.

Then, the hash values are sorted. So if an entry contains the (truncated) hash value "d41d8cd98f" then the next entry is likely to begin with "d41d8cd9" as well. The average difference between two successive values should be one bit. We don't need to keep all 48 bits for all entries. By grouping entries into pages, and some header for handling the few extreme cases (long "gaps" in the sequence of 48-bit values), one can achieve, say, an average of 10 bytes per entry. The original 8.7 petabytes have become 2.2 petabytes. Or, in a more vivid image, the 2000 hard disks are now 500 hard disks. Note, too, that using less bytes per entry means that a single 4096-byte I/O operation reads more entries, so not only you are using less disks, but you are also speeding up lookups.

Yet a further optimization is that there are only 62 possible characters in the passwords, and you do not need a full byte to store one character out of 62. 6 bits suffice. So the "8 bytes" for a password can be replaced with "6 bytes", and the average size of each entry is now 8 bytes. The 500 disks are now 400.

Of course, really efficient table compression would be a rainbow table. With rainbow tables, you walk possible passwords in a smart way which allows you to store them all in a table where you only keep, say, one in a thousand hashed passwords. The 500 hard disks have become a single hard disk. Of course, you have to pay for it: each lookup now involves substantial CPU. If rainbowisation shrinks the table by a factor x, then the lookup will involve about x2 hash computations. But, as said above, the attacker can do 4 millions of hashes per second. So a rainbow shrinking of x = 1000 is probably a good idea (from the point of view of the attacker).

Plus, the really really smart attacker won't implement any of this; he will just download an existing, already computed rainbow table.

## On sorting

Sorting 248 elements is not that easy. They don't fit in RAM. You can read them, but it takes quite some time to read and rewrite 2000 full disks. Moreover, reading or writing in non-sequential order will be atrociously slow.

This points at the merge sort as the right sort for that job. But while the basic merge sort is binary in nature (you split the data in two chunks, sorts them independently, and then merge them), you can get substantial speedups by extending the merge sort into larger splits: to sort N elements, split them into, say, 50 lists of size N/50, sort them independently (and recursively with a merge sort...), and then merge them. Merging 50 lists, obtained from 50 disks, with optimal bandwidth, is a nice programming exercise... (hint 1: use a heap for the merge; hint 2: use O_DIRECT, if the Linux people have not broken it).

The question isn't asking you to relate the answers to A and C, it's only saying that an attacker would realize that A is not the most efficient solution if he has more than one batch of passwords to guess, because he can get more than one use out of a rainbow table of 8 character SHA-256 hashed words.

So you need to compute the number of possible passwords, which in your case is defined as 8^(26+26+10). That tells you how many rows will be in your table. Now multiply that by the size of each row, which is the size-of-hash-in-bytes + size-of-password-in-bytes + extra-bytes-of-formatting-per-row (perhaps you need a two-byte-length integer in front of each password.) That's the answer the question is seeking.

It's asking how many bytes of storage are necessary to store all possible hashes and one password that hashes to it.

The way to look at this is to calculate the total number of passwords, then multiply that by the total space required to store both the password and its hash.

So, if you have 10 possible passwords requiring 1byte to store each, and you have a hash that takes 32 bytes to store, you need ( (1 byte for the password) +(32 bytes for the hash) ) To store one entry in your dictionary. You need 10 times that space to store all 10 possible passwords.

Related to part A

There's really no need to calculate this related to part (a), but if you really want to, you can. You can get the number of passwords from the time to crack and the attack speed.

Of course, you already had this value, because you used it to solve for A. Once you do this extra work, use the formulas above.

but wait! There's more!

Depending upon how pedantic you want to get, you also need to define your dictionary format, since you need to be able to differentiate the passwords. For example, if you store it as a delimited list (comma separating the password and the hash and newline separating entries) then you need to add two bytes to each record. Except the last record if you don't store a final newline.

And you can get it at a lower price!

Most passwords aren't a fixed width - they can be between some minimum and some maximum length. This means you don't need to store passwords that are too short - below the minimum length. Depending upon the difference in min and max lengths, and the total number of passwords, this may save you the cost of buying several disks.

There are also techniques for more efficiently storing the data. For example, you might store all hashes that begin with 000A in one file, so that you can ignore the 0000000A prefix in the stored hash. That is, if you have a million hashes that start with the same 4 bytes, you can save 4 million bytes of storage by storing them this way (4bytes per password). Look up rainbow tables and rainbow table formats for much more information about efficient storage tricks.

Or ask your teacher about more efficient storage - it's likely an upcoming topic in the book.

but what is your teacher looking for

Realistically, your teacher is probably only looking for the first part of the answer - the theoretical storage size. The rest of the answer is realistic requirements that are usually glossed over,

• 000A would be two bytes. Aside from that, if you had 4 bytes worth of files (4 billion files), you'd need the 4 billion directory entries to store them. There is no free space to be gained there. – Jeff Ferland Mar 14 '15 at 18:39
• @Jeff, fixed the four byte typo. I think you misinterpreted the file name stuff. the very simplified example of space saving technique was that thise million values would all be stored in the same file, thereby saving four bytes per value, all shared with the same single file name. Yes, there would be many files to create, but the amoubt of space a file requires for metadata (at least on many file systems) is far less than the 4M bytes that would be saved. – atk Mar 14 '15 at 20:36

Question (a)

There are (26+26+10)^8 different passwords = 218,340,105,584,896. Call that the dictionary_size.

The attacker can test 4*10^6 per second => tests_per_hour: (60*60)*4*10^6 = 14,400,000,000

On average he will have to test half the dictionary, to find the average password

solution: dictionary_size / 2 / tests_per_hour = 7581.25 hours.

Question (b)

it takes 1 computer 7581 hour. The task can be perfectly parallelized. Hence 7581 bots can each work 1 hour with the same result.

Question (c)

Each hash is 32 byte. Each password, if encoded as ASCII, would be 8 byte. (*)

Ignoring minor formatting, something in the neighbourhood of (32+8) bytes * 218,340,105,584,896. Around 8733 Terabyte, give or take (I'm not going into the 1024^n vs 1000^n bytes per K/M/G/T-byte discussion).

(*) the charset a-ZA-Z0-9 being only 62 chars, each char could be stored in 6 bits instead of 8, so that could shave 2/40th or 5% of the total storage: 8296 TB. (ps: earlier version of my answer miscalculated this saving).

• the question is 't about how much of the key space needs to be tested (about which you are correct) but rather about how much storage space is needed to store all possible hashes. – atk Mar 14 '15 at 20:37
• in my opinion, the question seems to bear on all 3 (a,b,c) of the questions off the textbook quote. I've updated my answer to include (b) and (c) as well, in the mean time.. – Fred H Mar 14 '15 at 20:45
• while it's great to have an answer key, you kight also want to show your work so the OP can learn how you got your answers. – atk Mar 14 '15 at 21:18
• though not terribly verbose, I thought the logic is already explained. I tried to improve a little. Anyway, the answer by Thomas is in line and very verbose. :) – Fred H Mar 14 '15 at 22:31