12

You are probably familiar with this table:

KDF comparison

The source of the table is this here

This table is 10+ years old. Is this still valid with current technology?

Wikipedia says that since 2014 there is ASIC equipment used for crypto-currencies. Do they affect the table?

Also, let's consider the last row in the above table. Suppose that a key is derived by scrypt from a 10 chars password in 5 seconds on an average computer. In this situation the paper estimates the equipment budget at 175T. Also suppose that the attacker has a maximum budget of only 1 billion dollars for this task. Does that mean that the estimated chances to break the password in 1 year should be less than 1/175.000?

Given the above does that mean that the password is safe for a few years? Or maybe a few months?

Thanks!

Martin Weil
  • 502
  • 3
  • 10
vidi
  • 287
  • 1
  • 8
  • 2
    If you're not familiar with [the Password Hashing Competition](https://password-hashing.net/), the hypertext and papers on that site have a lot of good and fairly recent information on the current state of affairs in password hashing. – Xiong Chiamiov Feb 13 '17 at 22:18
  • Can you clarify what you mean when you ask "is this still valid with actual technology?" Are you mostly interested in whether there is faster tech now, whether the tech of that time is cheaper now, whether there have been relative performance changes in cracking PBKDF2 versus bcrypt versus scrypt, or something else? – PwdRsch Feb 13 '17 at 22:21
  • Also, since you reject the estimated $1 billion for a budget, what amount do you want to consider? – PwdRsch Feb 13 '17 at 22:25
  • @PwdRsch I'm mostly concerned if the ratio between the time spent on key derivation and the equipment budget is the same given the recent availability of ASICs for scrypt based crypto-currencies – vidi Feb 14 '17 at 05:28
  • @PwdRsch I updated the question to clarify the part about the budget of $1B. I hope it's more clear now – vidi Feb 14 '17 at 05:42
  • @XiongChiamiov I've seen PHC and I tried to read&understand the papers but the technical details are too much for me. I haven't found a comparison similar to the one in scrypt paper, that would be easy to understand by somebody without in-depth knowledge of cryptography. Is there any? – vidi Feb 14 '17 at 10:23
  • I don't think there's a way to easily answer this without needing to compare the reduced cost in processing power as well as for memory. The table would effectively have to be re-created from scratch. It should still be accurate within the ballpark, though. – forest Dec 19 '17 at 08:26

1 Answers1

1

To understand the table it is worthwhile to read the article. The table is only an illustration and estimation for memory hard function. Furthermore, the article states:

We caution again that these values are very approximate and reflect only the cost of the cryptographic circuitry with circa 2002 technology: It is quite possible that the costs of other hardware (control circuitry, boards, power supplies) and operating costs (power, cooling) would increase the costs by a factor of 10 above these; and it is equally possible that improvements in semiconductor technology and improved cryptographic circuit designs could each reduce the costs by a factor of 10.

The price of computing power has dropped quite a bit; in 2003, the KAYSO cost $82 per gigaflops, in 2017, an AMD RX Vega 64 cost $0.03 per gigaflops (so a factor 2733). Granted that FLOPS is not a real measure for dealing with brute-force cryptography, but you should, for the costs take a factor 2500 into account.

Bitcoin miners could probably, with quite a lot of effort, be used to crack AES256 hashes, which are not in the table. But for the rest they're quite useless. You might, if you are determined, create your own ASIC for this. That may be quite costly to develop, but afterwards easier to distribute.

That also brings us to your probability calculation. They are a very gross simplification. Real values depend on the scalability of the algorithm (might not be linear) and a lot of other factors.

Look also at the development of new algorithms. For example: Andrey Bogdanov e.a. presented in 2011 a paper how to significantly reduce the cracking time of AES 128, 192 and 256 bit keys (Biclique Cryptanalysis of the Full AES).

From al that to the question if a password is safe is really a step too far. For passwords, there are a lot of other issues. Most passwords are cracked because they are relatively easy to guess (qwerty123) and/or are in dictionary files. On the other hand, if a cracking device does not have the encrypted password, it will be difficult to decrypt, so access to your (even encrypted) passwords must also be controlled.

Ljm Dullaart
  • 1,897
  • 4
  • 11