1
$\begingroup$

I am building a client-side app that will encrypt data, using password-based key generation, into the database. Can someone verify my calculations to figure out what is the right number of iterations I should use to dissuade a potential hacker?

  1. We'll assume that the password is at least eight characters long with a mix of numbers and upper, lower, and special characters. So that makes $72$ possibilities per character

  2. Thus total passwords to brute force $= 72^8 \approx 722$ trillion

  3. If I want it to take 100 years to try all possibilities using 10 computers, then per second my settings should be able to produce 22,900 passwords

  4. Now what I am unable to figure out is, how many iterations would it take to limit a GPU such as 8x Nvidia GTX 1080 to be able to generate 22,900 passwords?

We can assume HMAC-SHA-1 or HMAC-SHA-256.

$\endgroup$
  • $\begingroup$ What you really want here is a memory-hard password hashing scheme such as Argon2, Lyra2 or Catena. $\endgroup$ – SEJPM Jun 2 '17 at 16:16
5
$\begingroup$

There is a basic problem with your idea, which makes the entire calculation and the result pretty much meaningless. Your actual question is:

Can someone verify my calculations to figure out what is the right number of iterations I should use to dissuade a potential hacker.

Let's keep that in mind for now. You want security.

  1. We'll assume that the password is at least eight characters long with a mix of numbers and upper, lower, and special characters. So that makes 72 possibilities per character
  2. Thus total passwords to brute force = 72^8 = 722 trillion

It is approximately $722$ trillion, that is not equal to $72^8$ but an approximation. Other than that, this is fine (although I find $10^{12}$ more intuitive than trillion).

  1. If I want it to take 100 years to try all possibilities using 10 computers, then per second my settings should be able to produce 22,900 passwords
  2. Now what I am unable to figure out is, how many iterations would it take to limit a GPU such as 8x Nvidia GTX 1080 to be able to generate 22,900 passwords?

We can assume HmacSHA1 or HmacSHA256

Okay, these all belong together and can't be answered alone. Your math in 3. is fine, the question in 4. can be answered with basic arithmetic and a benchmark of the system, and the statement about the used algorithm is needed to answer number 4 at all.

I think it would be much clearer to go this way:

  • Find a benchmark or generate one yourself. For your specific setup I found this source. It only lists SHA1 and SHA256, but for a rough approximation it's fine to consider two hashes euqal to one HMAC ($0.5$ times the number of hashes per second). For SHA-256 it's around $23\cdot 10^9$ hashes per second and SHA-1 almost exactly three times this number.
  • Calculate how long it takes for your setup ($10$ systems) to test all combinations ($72^8$ - but actually this is a lower bound, not the exact number). For example for HMAC-SHA256 this would be: $\frac{72^8}{0.5 \cdot 23 \cdot 10^9} \approx 62800$ seconds for one system, and thus $\approx 6280$ seconds for 10 systems.
  • If you want to achieve "security for a 100 years", calculate the number of requires iterations as $6280 x = 3153600000$, where the righthand side is the number of seconds in 100 years. The result is approximately $5 \cdot 10^8$.

To put this number into context: You can't run these $500$ million hashes in parallel. According to this list SHA256 can process around $223 \cdot 1024^2$ Byte per second, with blocksize $512$ bit that's around $3.65$ million SHA256 operations per second. So as a very rough estimate we get $\approx 137$ seconds for $500$ million iterations.


Now let's go back to the original question:

Can someone verify my calculations to figure out what is the right number of iterations I should use to dissuade a potential hacker.

Unfortunately, you completely disregarded that passwords are not uniformly distributed - and you are asking about a hacker: a person who can adapt and choose which values to test first - it is not just a brute force algorithm.

Passwords are usually not drawn from all possible passwords with equal probability, but they are usually chosen by a person instead. The hacker knows this - and he can use it to his advantage. This can be used e.g. in a so-called dictionary attack - and if we talk about passwords we have to keep this in mind.

An alternative point of view is: Passwords actually have much less entropy than a truly random (uniformly and independently drawn) string of the same length with the same set of symbols.

So while your idea is not entirely wrong, it does not have any meaning regarding the security of the password - unless you can make sure that the passwords actually are not chosen by a person but generated with the full entropy.


Instead of trying to make up your own password hashing scheme and calculations like this one, I would suggest checking out existing solutions. There are key-derivation functions for passwords, e.g. Argon2 won the Password Hashing Competition (from 2013 to 2015). Another popular function is scrypt, and previously PBKDF2 (I wouldn't recommend using this today, but it was very popular at some point). All of them offer various parameters you can adjust to your needs, including more than just number of iterations. The modern ones allow you to adjust the memory requirement to evaluate the function, which is an entirely different countermeasure to the full search than just increasing the number of iterations.

$\endgroup$
  • 1
    $\begingroup$ Two things you may want to add to your answer: a) 500 million iterations of either SHA-2 or SHA-1 is very hefty for most systems and b) you may want to point towards memory-hard hashing schemes :) $\endgroup$ – SEJPM Jun 2 '17 at 16:16
  • $\begingroup$ @tylo Actually, this data will reside on a phone and I am definitely not going to get 5*10^8 iterations and my users happy together.The point was to give the user enough time to change some password/data/other actions, in case he looses his phone and a hacker tries to extract the database within. 10,000 iterations give them about nine months if 25 computers are used. I understand password entropy and will try to make the user as well. Sorry I can't accept this as the answer since I created the question without signing up. $\endgroup$ – Shahid Thaika Jun 2 '17 at 17:52
  • $\begingroup$ @ShahidThaika You probably can't change the question then either, maybe a moderator could help you with that (I don't know for sure). Given your information now, I suggest reading about the XY problem. To your actual idea, maybe the last paragraph adresses the issue: Whatever cryptographic library you use - it probably offers some sort of password-hashing function, which you should use for hashing passwords. And in questions about security rely on the cryptanalysis done for those. $\endgroup$ – tylo Jun 2 '17 at 18:04
  • $\begingroup$ @tylo I flagged the question. Unfortunately, I am also limited by what phones can do and most of them probably only support PBKDF2, which was where I came from. However, I am planning to design the encryption in a way that the user can choose a higher secure one and test the time taken. Main problem is how to make it simple for them to decide what to choose. $\endgroup$ – Shahid Thaika Jun 2 '17 at 18:16

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.