Semantically Secure / is on Nostr

Semantics, semantic security, security.

Blog: [scottarc.blog](https://scottarc.blog/ )

Last Notes

2024-06-17 11:44:41

*Musing about Password-Based Cryptography for the Government*
What would a modern NIST standard for password-based cryptography look like?
Obviously, we have PBKDF2–which, if used with a FIPS-approved hash function, gives you a way to derive encryption keys and/or password validators from human-memorable secrets.
**However, PBKDF2 isn’t memory-hard.**
In 2012, several cryptographers initiated the Password Hashing Competition (PHC) to study the state-of-the-art for password-based cryptography at the time. Part of this motivation was that memory-hard hashing (first developed by Colin Percival in scrypt a few years prior) provided greater defense against the increasing parallelism of modern password cracking techniques.
After a few years of cryptanalysis, the PHC selected an algorithm called [Argon2](https://github.com/P-H-C/phc-winner-argon2 ), and gave special recognition to four other finalists.
And, quote the [NIST SP 800-63B](https://pages.nist.gov/800-63-3/sp800-63b.html#-5112-memorized-secret-verifiers ):
> A memory-hard function SHOULD be used because it increases the cost of an attack.If you were expecting, “Nevermore,” you’re currently reading the wrong literary genre.
“So, we’re done, right? Just use Argon2 and call it a day.”
We did it! Yayyyyyyyy~
…
**Of course, it’s not that simple.**
(Artist source unknown, meme generated from imgflip)##
What is Argon2?Argon2 is defined in [IETF RFC 9106](https://datatracker.ietf.org/doc/rfc9106/ ). There are several variants of Argon2 that have subtly different security properties (Argon2d, Argon2i, Argon2id, Argon2ds — the latter one providing a property called cache-hardness. which [Steve Thomas’s slide deck from BSidesLV 2022](https://tobtu.com/files/bsideslv2022.pdf ) explores in depth).
Argon2id is the variant most of us settled on in 2024.
Regardless of the variant used, the same underpinnings are used. From [RFC 9106, section 3.2](https://www.rfc-editor.org/rfc/rfc9106.html#name-argon2-operation ):
> Argon2 uses an internal compression function G with two 1024-byte inputs, a 1024-byte output, and an internal hash function H^x(), with x being its output length in bytes. > **Here, H^x() applied to string A is the BLAKE2b ([BLAKE2], Section 3.3) function**> , which takes (d,ll,kk=0,nn=x) as parameters, where d is A padded to a multiple of 128 bytes and ll is the length of d in bytes. The compression function G is based on its internal permutation. A variable-length hash function H’ built upon H is also used. G is described in Section 3.5, and H’ is described in Section 3.3.Bold text for emphasis.
If you weren’t adept at playing Crypto Algorithm Bingo, it might be easy to miss the fact that BLAKE2b is **NOT** a cryptographic algorithm approved for use in FIPS validated modules.
So, full stop, unless NIST and the US Department of Commerce turn over a new leaf and add BLAKE2 to the approved algorithms list for FIPS, this is a non-starter.###
Well, why not use yescrypt? Or scrypt for that matter?Yescrypt (and scrypt before it) are based on Salsa20/8. In fact, most of the time computing a KDF output with either algorithm is spent on Salsa20-encryption regions of memory.
After all the computing resources are spent on Salsa20/8 and memory management, PBKDF2-SHA256 is used to compress the output to a fixed length. This is arguably complying with NIST’s requirements to use PBKDF2–albeit with an iteration count of 1 (so it’s just artificially sweetened HMAC, if we’re being honest with ourselves).###
How are systems complying today?I’ve heard a few conflicting stories over the years from folks that care *a lot* about FIPS (presumably because the US government is a significant chunk of their annual recurring revenue). It’s possible I’m misremembering what they said, so please take these secondhand anecdotes with an appropriate amount of salt.
One person claimed that Scrypt is fine since “the last step is PBKDF2”, and if an auditor blinks, you allegedly just need to document all the Salsa20 stuff as “obfuscation” and PBKDF2 is what you’re *really* doing to comply.
Another approach I heard was to run a memory-hard KDF in parallel with PBKDF2, then use HKDF to combine the two outputs.
Between the two, I’m more likely to believe that an auditor would approve the latter HKDF-based design, but I’ve never worked at a NIST CMVP lab, so who knows?
Unfortunately, [NIST SP 800-63B](https://pages.nist.gov/800-63-3/sp800-63b.html#-5112-memorized-secret-verifiers ) has little to say about the specifics:
> Examples of suitable key derivation functions include Password-based Key Derivation Function 2 (PBKDF2) > [> [SP 800-132]](https://pages.nist.gov/800-63-3/sp800-63b.html#SP800-132 )> and Balloon > [> [BALLOON]](https://pages.nist.gov/800-63-3/sp800-63b.html#balloon )> . A memory-hard function SHOULD be used because it increases the cost of an attack.
I already said that PBKDF2 isn’t memory hard, so that’s useless here.
The other example they gave, [Balloon Hashing](https://eprint.iacr.org/2016/027 ), is frankly a weird recommendation to make, given the lack of a stable reference implementation and how poorly specified it is.
This is starting to look like a catch-22. Maybe we would be better off not supporting passwords anymore.
But what if you can’t make that decision?
What would a modern NIST standard for password-based cryptography *even look like*?##
Towards Gargon: Government-flavored Argon2Is that last question even answerable?
I argue, “Probably yes.” From the introduction to RFC 9106:
> Argon2 is also a mode of operation over a fixed-input-length compression function G and a variable-input-length hash function H. > **Even though Argon2 can be potentially used with an arbitrary function H**> , as long as it provides outputs up to 64 bytes, the BLAKE2b function [BLAKE2] is used in this document.
Clearly, the Argon2 RFC authors intended to allow the hash function be swapped out for another one.
So can we just str_replace() BLAKE2b with SHA512 (or SHA3-512) and call our job done?
No, that would be too easy.###
The internal compression function, GArgon2’s design involves computing [the internal compression function, G](https://www.rfc-editor.org/rfc/rfc9106.html#name-compression-function-g ), over regions of memory. The linked section of that version of RFC 9106 provides a good overview of the construction.<li>G is defined in terms of the permutation, P.</li><li>P is based on the round function of BLAKE2b.</li><li>The BLAKE2b round function is based on ChaCha, which is similar to Salsa20 (and designed by the same author), which we already established isn’t approved for FIPS.</li>
So if we’re going to invent a Government-tolerable variant of Argon2, we’ll need to be a bit more creative about our choice for G as well.
More precisely, even if we keep the overall structure of G intact, we’ll need to define a FIPS-able permutation, P.###
The permutation, P, for building the internal compression function, GA reasonable person would assume we would need to pick a component from the hash function we’re building atop which has an increased circuit depth. After all, that’s what the Argon2 designers did:
> The modular additions in GB are combined with 64-bit multiplications. Multiplications are the only difference from the original BLAKE2b design. This choice is done to increase the circuit depth and thus the running time of ASIC implementations, while having roughly the same running time on CPUs thanks to parallelism and pipelining.<a href="https://www.rfc-editor.org/rfc/rfc9106.html#name-permutation-p">RFC 9106</a>
And this is where reasonableness hits a wall. There are several directions that one could go to invent Government-tolerable Argon2.<li>The SHA-2 family compression function (i.e., <img src="http://s0.wp.com/latex.php?latex=Ch%28%29&bg=111111&fg=eeeeee&s=3&c=20201002" srcset="http://s0.wp.com/latex.php?latex=Ch%28%29&bg=111111&fg=eeeeee&s=3&c=20201002 1x, http://s0.wp.com/latex.php?latex=Ch%28%29&bg=111111&fg=eeeeee&s=3&c=20201002&zoom=4.5 4x" alt="Ch()" class="latex">, <img src="http://s0.wp.com/latex.php?latex=Ma%28%29&bg=111111&fg=eeeeee&s=3&c=20201002" srcset="http://s0.wp.com/latex.php?latex=Ma%28%29&bg=111111&fg=eeeeee&s=3&c=20201002 1x, http://s0.wp.com/latex.php?latex=Ma%28%29&bg=111111&fg=eeeeee&s=3&c=20201002&zoom=4.5 4x" alt="Ma()" class="latex">, <img src="http://s0.wp.com/latex.php?latex=%5CSigma_%7B0%7D%28%29&bg=111111&fg=eeeeee&s=3&c=20201002" srcset="http://s0.wp.com/latex.php?latex=%5CSigma_%7B0%7D%28%29&bg=111111&fg=eeeeee&s=3&c=20201002 1x, http://s0.wp.com/latex.php?latex=%5CSigma_%7B0%7D%28%29&bg=111111&fg=eeeeee&s=3&c=20201002&zoom=4.5 4x" alt="\Sigma_{0}()" class="latex">, and <img src="http://s0.wp.com/latex.php?latex=%5CSigma_%7B1%7D%28%29&bg=111111&fg=eeeeee&s=3&c=20201002" srcset="http://s0.wp.com/latex.php?latex=%5CSigma_%7B1%7D%28%29&bg=111111&fg=eeeeee&s=3&c=20201002 1x, http://s0.wp.com/latex.php?latex=%5CSigma_%7B1%7D%28%29&bg=111111&fg=eeeeee&s=3&c=20201002&zoom=4.5 4x" alt="\Sigma_{1}()" class="latex">).</li><li>The basic block permutation function from SHA3 (i.e., <img src="http://s0.wp.com/latex.php?latex=%5Ctheta&bg=111111&fg=eeeeee&s=3&c=20201002" srcset="http://s0.wp.com/latex.php?latex=%5Ctheta&bg=111111&fg=eeeeee&s=3&c=20201002 1x, http://s0.wp.com/latex.php?latex=%5Ctheta&bg=111111&fg=eeeeee&s=3&c=20201002&zoom=4.5 4x" alt="\theta" class="latex">, <img src="http://s0.wp.com/latex.php?latex=%5Crho&bg=111111&fg=eeeeee&s=3&c=20201002" srcset="http://s0.wp.com/latex.php?latex=%5Crho&bg=111111&fg=eeeeee&s=3&c=20201002 1x, http://s0.wp.com/latex.php?latex=%5Crho&bg=111111&fg=eeeeee&s=3&c=20201002&zoom=4.5 4x" alt="\rho" class="latex">, <img src="http://s0.wp.com/latex.php?latex=%5Cpi&bg=111111&fg=eeeeee&s=3&c=20201002" srcset="http://s0.wp.com/latex.php?latex=%5Cpi&bg=111111&fg=eeeeee&s=3&c=20201002 1x, http://s0.wp.com/latex.php?latex=%5Cpi&bg=111111&fg=eeeeee&s=3&c=20201002&zoom=4.5 4x" alt="\pi" class="latex">, <img src="http://s0.wp.com/latex.php?latex=%5Cchi&bg=111111&fg=eeeeee&s=3&c=20201002" srcset="http://s0.wp.com/latex.php?latex=%5Cchi&bg=111111&fg=eeeeee&s=3&c=20201002 1x, http://s0.wp.com/latex.php?latex=%5Cchi&bg=111111&fg=eeeeee&s=3&c=20201002&zoom=4.5 4x" alt="\chi" class="latex">, and <img src="http://s0.wp.com/latex.php?latex=%5Ciota&bg=111111&fg=eeeeee&s=3&c=20201002" srcset="http://s0.wp.com/latex.php?latex=%5Ciota&bg=111111&fg=eeeeee&s=3&c=20201002 1x, http://s0.wp.com/latex.php?latex=%5Ciota&bg=111111&fg=eeeeee&s=3&c=20201002&zoom=4.5 4x" alt="\iota" class="latex">).</li><li>Look elsewhere in the FIPS algorithm suite, such as AES (e.g., in Counter Mode, to exploit the hardware acceleration of AES in modern CPUs).</li>
Each of these ideas is terrible in their own way.
The cryptanalysis results showing that the best attack against a full hash function costs 2 to some power queries don’t imply the security of each constituent component. So you’re really rolling the dice if you pursue this.
AES might be okay, depending on how it’s constructed and used. But the devil’s always in the details.
It’s starting to seem like Gargon’s possibility is fleeting, after all.###
Wouldn’t life be simpler if NIST just approved BLAKE2b and/or Argon2 for use in FIPS validated modules?**Yes**, life would be much simpler. NIST should do that.
Unfortunately, until that day comes, there are yet more windmills that need tilting.
https://scottarc.blog/2024/06/17/the-quest-for-the-gargon/
#Argon2 #crypto #Cryptography #CryptographyStandards #cybersecurity #encryption #FIPS #NIST #passwordBasedCryptography #passwords #PBKDF2 #security
https://scottarc.blog/wp-content/uploads/2024/06/fips-windmills.jpg