[Whonix-devel] Argon2id security margin estimate and LUKS2 usage

Tue Aug 21 04:41:27 CEST 2018

On Tue, Aug 21, 2018 at 01:19:00 CEST, procmem wrote:
> 
> Arno Wagner wrote:
> procmem wrote:
> >> Hi Milan, Whonix (privacy distro) maintainer here. We are researching
> >> the best password advice to give to our users and while diceware is a
> >> great improvement over the status quo, the recommendation by
> >> cryptographers in light of quantum computing is to choose pass phrases
> >> with a length equivalent to 256 bits because Grovers will halve the bit
> >> length. This requires phrases to be 20 words long for 256 bits which is
> >> excessive IMO and the reason we are looking at key-stretching for
> >> shorter ones instead.
> > 
> > This is completely irrelevant for key derivation. No QC
> > will be able to do a few 1000 iterations of KDF this century,
> > and actually it would need to reverse them. Also, the size of
> > the QC needed is not the password-size, but the minimal memory
> > needed to compute the KDF on it. So with something like 
> > Argon2, the QC would need as many bits as the configured memory.
> > 
> > In addition, it is still completely unclear whether QC will 
> > ever scale. There is no indication that it will after now 
> > something like 40 years of intense research. This is just another
> > hype that will not die because too many people believe in magic
> > and normal computing has effectively stopped scaling half a 
> > decade back or so.
> > 
> > Well, actually, it is pretty clear at this time that QC does
> > not scale at all in practice and that its scale-up over time 
> > may well be inverse exponential. If so, it will never be of any use.
> > 
> 
> True. I've seen other cryptographers skeptical of QCs ever materializing
> in practice excepting a black swan event. However they still support
> development of PQ ciphers just in case this happens so we aren't caught
> with our oants down in a cryptocalypse. Projects like Tor are working on
> a PQ KEM just in case.
> 
> While I'd personally love to see quantum computing never succeed because
> it only benefits institutions and not regular people, common sense says
> its still a plausible scenario to consider until a mathematical proof
> disproving the possibility of a large QC surfaces.

For some ciphers, this makes some sense. But a KFD is not really
vulnerable to QCs, even if they eventually work and scale.
And with the large-memory property of Argon2, the QC even
able to work on it would need to be enormous.

> > 
> >> 
> >> * What is the time/sec margin added to a password with Argon2id's best
> >> parameters?
> > 
> > There are no "best" parameters. It depends on your application and
> > target system. That said, computationally, it is bascially just 
> > the same as PBKDF2, ARGON2 just adds a minimal memory requirements 
> > or you get exponentially worse.
> > 
> 
> I've read arguments to the effect of LUKS1 PBKDF2 being a badly broken
> Maginot Line in the face of adversaries with GPUs even if configured
> with 10K iterations.

Well, LUKS1 is at arond 500k iteration for a modern CPU, so that
is not a threat. Calling it "badly broken" is pretty much nonsense,
even for only 10k iterations. All a KDF does is lower the amount
of entropy in the passhrase somewhat, it does not prevent breaking
of really bad passphrases and that is not its purpose in the first
place. Its purpose is to shift the boder between "good" and "bad"
a bit and that is it.

> My reasoning was: An adversary who has a ton of GPUs can circumvent
> legacy PBKDF2's key-stretching benefits and then in the event of
> possessing a QC we then basically have nothing to rely on besides the
> master key bit size.

What makes you think a QC would be useful in breaking PBKDF2?
To the best of my knowledge, breaking PBKDF2 requires brute-forcing.
Again to the best of my knowledge, a QC has zero advantage
under these conditions. I may be wrong.

> But I'm getting the impression from you that Argon2 is merely a minor
> improvement over the original PBKDF2 and that the latter is not
> hopelessly defeated by GPUs?

The streteching effect is pretty much the same. The advantage 
is that GPUs cannot efficiently calculate Argon2.

> Unlike symmetric key strength and passphrase entropy that I can easily
> calculate, I have no idea how much PBKDF2 can delay bruteforcing by an
> adversary with massive CPU let alone GPU power. Do you know where I can
> read about this?

For GPU-power, nowhere, it is useless against Argon2, unless you
configure a tiny memory footprint. Obvously, you should not do that.
For CPU, it is pretty much "time to calculate hash" = "time for one
step brute-forcing attempt". This is a fundamental limitation, not
one of Argon2. 

[...]
> > Just keep in mind that with a good passphrase, even a single, plain,
> > unsalted SHA-1 is unbroken at this time and even secure against the
> > mythical extreme powers (not) of a QC. There is really no need to 
> > fret over key derivation, the weaknesses are in entirely different 
> > places.
> 
> Indeed. Hashing is quantum resistant and many PQ systems are based on
> this premise like DJB's SPHINCS signing suite. I guess I didn't frame my
> question properly and you thought I meant PBKDF2 being suddenly
> vulnerable to QC rather than GPUs.
> 
> Thanks for your insight and work on LUKS. I learn something new every day.

You are welcome. To sum this up, what Argon2 does is it
makes a configurable amount of memory mandatory to attack 
it. This is usually set to 1GB or so and makes GPUs completely
unusable as attack platform. CPU-based brute-forcing is not
impacted (if there is enough RAM) and nothing can be done there.
After all, the normal usage scenario also use a normal CPU.
So if a legitimate Argon2 hashing takes 1 sec on a normal
CPU, an attacker gets pretty much the same rate for brute-forcing.

Regards,
Arno

-- 
Arno Wagner,     Dr. sc. techn., Dipl. Inform.,    Email: arno at wagner.name
GnuPG: ID: CB5D9718  FP: 12D6 C03B 1B30 33BB 13CF  B774 E35C 5FA1 CB5D 9718
----
A good decision is based on knowledge and not on numbers. -- Plato

If it's in the news, don't worry about it.  The very definition of 
"news" is "something that hardly ever happens." -- Bruce Schneier