7
$\begingroup$

I just check all the questions with scrypt tag about that and usually it's said that scrypt is nice in theory and theoretically better than bcrypt and PKDF2, but it's too young to be "completely safe".

I understant bcrypt is very old and yet unbroken, but since it uses relatively little amounts of RAM crackers can get around it with specialized hardware. On the other hand, scrypt uses a "lot" more ram (configurable, to a degree) and tries to solve bcrypt's issue of using so little RAM.

So the main question is, if script isn’t "old enough to be safe" – when will scrypt be old enough to be safe for proper use? Maybe even more important: which factors influence “old enough” so that I can tell if and/or when something like scrypt has aged enough to be safe for practical, cryptographic use?

$\endgroup$
  • 1
    $\begingroup$ If it resists current attacks, we will only be sure how safe (and old) scrypt is, when there will be new class of attacks/analysises against then-current, and older KDFs. When we know how to measure the weakening by those attacks, we can see how scrypt is standing among it's competitors. It may need a (few) new generation of graduates. $\endgroup$ – chexum Jan 12 '16 at 7:15
13
$\begingroup$

Actually, it turned out that scrypt was not as good as initially advertised under all conditions.

Scrypt was designed to support the specific case of password-based key derivation for full harddisk encryption. Basically, you type your password when the machine boots up (or awakes from hibernation). This is a context where the following apply:

  • The password processing time can take several seconds, since it is part of a boot-up procedure that will take a lot more time; under such conditions, user's patience is such that 5 seconds of dedicated time is not an unreasonable figure.

  • While the password is processed, nothing else happens on the machine, so the full CPU can be used for the task, and also the full RAM (so up to gigabytes).

In that context, scrypt totally rules. However, a busy authentication server, e.g. for an active Web server, can be a different beast. In particular, you will probably want to make the per-password CPU cost much lower, not only because there may be several users to handle simultaneously and concurrently with other tasks, but also because the more expensive password hashing is, the more vulnerable you become to basic denial-of-service attacks. For a busy server, a computing time down to 1 millisecond or so would be a more plausible value than the "5 seconds" alluded to above.

When scrypt must run fast, it cannot use as much RAM. In fact, at 1 ms CPU time, it uses so little RAM that GPU-based optimizations become to be worth the effort. In Litecoin, scrypt is used with 128 kBytes of RAM, and GPU implementations can be about 10x faster than CPU implementations (for the same hardware/operating cost), which is technically a function failure. One of the main points of a password hashing function is that attackers with GPU should not gain an advantage over defenders who use "normal" CPU. For fast password-hashing, bcrypt thus turns out to be more secure than scrypt. While scrypt is better than bcrypt when used for what it was designed for.

A further issue with scrypt is that it allows a time-memory trade-off: with more RAM, you can save on CPU, and vice-versa. This kind of flexibility gives some leverage to attackers who try to optimize their effort.

You may want to consult this presentation for some explanations and pointers to further information. The raw conclusion is that while scrypt is reasonably good for what it does, it cannot be said to be a drop-in improvement over bcrypt.

(As a side note, take care that use of a password-hashing function in cryptocurrencies is not the same context as use for protecting passwords in an authentication server. In an authentication server, there is an asymmetrical race between attacker and defender, because the defender uses generic hardware while the attacker can buy special-purpose dedicated hardware. In a cryptocurrency, miners compete against each other and they all buy the same GPU or ASIC anyway, so the 10x GPU speed-up in Litecoin is not a problem for Litecoin; it would be a problem, on the other hand, for an authentication server, where the defender must work with whatever PC he can get from his hosting provider.)


Such things prompted cryptographers to look for better password-hashing functions, and they did so with the usual arrangement: an open competition(*). This resulted in the Password Hashing Competition. The process took a few years and resulted in the choice of a "winner" called Argon2 (along with four other schemes with "special recognition").

The current situation is not ideal in that we now have the choice between:

  • the old bcrypt, that is reasonably good except against the very serious attackers who think big and use FPGA;

  • the newer scrypt, which is better than bcrypt in some contexts, but worse in others, and has some extra drawbacks;

  • the brand-new Argon2, who sustained some rather heavy scrutiny, but only for a limited amount of time, and thus cannot be universally recommended yet.

The bright side here is that the PHC appears to motivate extra research on Argon2, and that is good.


(*) For cryptographers, the most perfect academic process for research is the Thunderdome.

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – e-sushi Jan 19 '16 at 8:01
  • $\begingroup$ this is a nice summary of everything, I am trying to get my hands on argon, especially when it's going into PHP7.2 natively, meaning I wont need any extemsions or other more or less hilarious things. $\endgroup$ – My1 Sep 15 '17 at 10:20
5
$\begingroup$

I guess the honest answer is nobody can know for sure, however:

There's a general rule of thumb in cryptography, that once there was been wide rewards for breaking an algorithm (be it a hash function, a cipher or in this case a key deviation function) but nobody has come to close the breaking it, then we are in the "safest period".

Scrypt is almost certainly the safest PBKDF, that's been widely tested*. The estimated market cap of all scrpyt based alt-coins has been a good ~$200 million +, for a while and at some points a good lot more.

I think putting mathematics to one side for a moment, we can see this is a good enough intensive (much larger than the unclaimed \$75,000 to $200k reward for the RSA Challenges) but this is anecdotal, especially when we consider the RSA challenges were withdrawn in 2007.

You are indeed correct that scrypt is a large improvement on bcrypt, presuming that we define safety as resources needed to launch an attack on the KDF.

It's worth pointing out on the other hand, the very fact that Litecoin and the likes, exist: that scrypt has many ASICs dedicated to speeding up it's use and therefore speeding up, any brute-force attacks.

I can't offer cryptanalysis of Scrypt if that's what you're after, but your question seems to be more one of logic and I purpose that logically all evidence suggests that scrypt has already reached it's maximum "safety". Maybe this is too opinionated, but I've tried to offer some evidence to suggest: Scrypt is already the safest PBKDF (probably).

*I'm considering the wide use in crypto-currencies to be wide testing of it, because the functions performed, search and development of special hardware and financial incentives to break it are all there.

$\endgroup$
  • 5
    $\begingroup$ While you make good points, crypto currencies do not use scrypt as a PBKDF. They use it with "random" inputs, rather than passwords, and the objective is to find partial preimages. Some attacks on a password hash (like timing attacks) do not apply. It is also worth noting that the market cap is not directly an incentive. That's not the amount of money you would stand to gain if you broke the proof-of-work. $\endgroup$ – otus Jan 12 '16 at 9:43
  • $\begingroup$ Suggesting that the Market Cap of LiteCoin is equal to what you stand to gain was not what I was doing there in my answer. That said, while being a bitcoin-nerd (or whatever), I've overlooked the subtle difference in show alt-coins use the KDF to show proof-of-[probable]-work. So I up-voted Thomas' answer, too. $\endgroup$ – Iam Nick Jan 13 '16 at 16:28

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.