2
$\begingroup$

Suppose one had no computer (or rainbow tables), but had access a pen and paper as well as all the necessary documentation for modern (best practice, not outdated) hashing algorithms and mathematical formulae.

How long would it take to compute the hash of a password?

Define password

  • a random 8 character string of characters (numbers, letters, allowable symbols)

Define best practice

  • bcrypt (or similar) with calculation performed n=10 (so 1024 times total)
$\endgroup$
  • 5
    $\begingroup$ Suggestion: examine the pseudocode of bcrypt, find the loop where most of the time is spent, and how it decomposes, with reference to blowfish. Count the number of elementary operations performed. Estimate how much time each will take. Multiply to get a result. Incidentally, estimate the probability there was no error, and think of a way to catch and fix these (which I guess more than double the time). $\endgroup$ – fgrieu Sep 19 at 6:29
  • 1
    $\begingroup$ well, it will certainly be much longer than you will live, so at that point does it really matter? $\endgroup$ – Richie Frame Sep 20 at 2:22
  • $\begingroup$ @RichieFrame very interesting. I thought it wouldn't take too long if the input is small? (e.g. 8 characters). But I guess if it takes a computer a little bit of time (some non trivial part of a second), then it will take a human a very long time. Curious to know how the time it would take a human varies as the length of the input changes $\endgroup$ – stevec Sep 20 at 6:48
  • 1
    $\begingroup$ An input length into bcrypt takes the same amount of time to process since it is xor'd into the subkey array as an array of 18 32-bit values, even an input of nothing $\endgroup$ – Richie Frame Sep 21 at 6:28
4
$\begingroup$

If you want a "quick" way of determining how long it will take for bcrypt-n10, you can process by hand a very very VERY small subset of its calculation, then multiply that time by how many times the algorithm will use it.

The round function is used many times, you can perform components just once to get a base time. There are operations on 32-bit values, you can just do 1.

There are 3072 round operations after key setup (64x16x3)
There are 521 round operations per expand key
There are 539 32-bit XORs per expand key
There are 2048 expand keys per key setup

That gives you 1070080 round operations and 1103872 32-bit XORs A round contains 2 XOR and 3 32-bit addition operations and 4 S-Box lookups, you can now break this into:

3,210,240 unsigned 32-bit additions
3,244,032 32-bit XOR operations
4,280,320 S-Box lookups (which change all the time)
64 blowfish key schedule operations (ignore, maybe it will add 3% to the time)
Moving tons of data around

If you were SUPER fast and could do an XOR in only 10s, an addition in only 20s, and an S-Box lookup in 10s, that is 4842 days calculating 8 hours per day, just for those operations.

You would still need to take into account how much paper it would take, transferring data from page to page when full, and the additional writing required, and the additional verification of operations to make sure you don't make a 1-bit mistake somewhere and screw the whole thing up. Just go ahead and double the time.

That is 26 years working 7 days a week or 37 years working 5 days a week.

It would probably take me at least that long to do it even if I had an electronic calculator that had hex input and an assistant or apprentice helping me to expand s-boxes and verify my work; there is no way my fingers could do that much work a day or work that quickly.

Out of the 365 million or so bit operations you need to perform, the allowed error rate is 0. How much extra effort would it take you to make sure you make no mistakes in calculation over the course of decades? So try it out, get 2 random numbers, do one addition and one XOR, and see if the numbers line up... or if it takes you more time.

| improve this answer | |
$\endgroup$
  • $\begingroup$ 37 years is roughly an entire career’s worth of work, just to login to a website (once)! Incredible. And incredible answer! $\endgroup$ – stevec Sep 21 at 7:50
  • 1
    $\begingroup$ @stevec it took a while to calculate the operation count, and that was just simple arithmetic! doing millions of ops on 32-bit integers... screw that noise, I imagine I am massively underestimating the amount of time this will really take, especially the s-box lookup, since the outputs are so big $\endgroup$ – Richie Frame Sep 21 at 7:53
  • $\begingroup$ thanks for the edits, I typically answer q's after work, and my brain is.... not 100% $\endgroup$ – Richie Frame Oct 2 at 0:34
  • $\begingroup$ Welcome and we took this for the rest, too :) This will delete itself, when upped. $\endgroup$ – kelalaka Oct 2 at 12:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.