2
$\begingroup$

I refer to the following wiki description of the Argon2 key derivation function:-

Generate initial 64-byte block H0.
    All the input parameters are concatenated and input as a source of additional entropy.
    Errata: RFC says H0 is 64-bits; PDF says H0 is 64-bytes.
    Errata: RFC says the Hash is H^, the PDF says it's ℋ (but doesn't document what ℋ is). It's actually Blake2b.
    Variable length items are prepended with their length as 32-bit little-endian integers.
   buffer ← parallelism ∥ tagLength ∥ memorySizeKB ∥ iterations ∥ version ∥ hashType
         ∥ Length(password)       ∥ Password
         ∥ Length(salt)           ∥ salt
         ∥ Length(key)            ∥ key
         ∥ Length(associatedData) ∥ associatedData
   H0 ← Blake2b(buffer, 64) //default hash size of Blake2b is 64-bytes

Not only are the input parameters concatenated (and so their entropies), but also the sheer algebraic lengths too. I would have thought that the content would explicitly define the entropy of a variable. Shannon's entropy formula certainly doesn't explicitly feature a length component.

So does length add anything so is it just artistic flair?

$\endgroup$
1
  • $\begingroup$ It doesn't increase the entropy since this information is the property of the input. Once you know the input you know the size, too. $\endgroup$
    – kelalaka
    Commented May 9 at 20:46

1 Answer 1

1
$\begingroup$

does length add anything?

Yes.

Without the lengths, (password="aqwal", salt="[email protected]") and (password="aqwalc", salt="[email protected]") would always generate the same hash. This is a hash collision, and undesirable for this reason alone.

This can have consequences: in a password hashing application with the salt doubling as the login, for an adversary who does not know the key, but is able to create a login as [email protected], this property allows the adversary to test if the password of [email protected] is any particular string at most one less character than the maximum password length (if any), by changing their own password to this string followed by c and comparing the hashes. And with read/write access to the hashes, they can change the hash for [email protected] so that they can log in as [email protected].

More generally, if we consider inputs that are variable-length random strings up to some limit, the Shannon entropy of the output tends to be higher with lengths than without.

Argument: for a source generating $n$ distinguishable outcomes with probability $p_i>0$ of outcome $i$ and $1=\displaystyle\sum_{0\le i<n} p_i$, the Shannon entropy (in bit) is $\displaystyle\sum_{0\le i<n}p_i\log_2(1/p_i)$. When the source is modified so that two outcomes $i$ and $j\ne i$ become indistinguishable, their contribution to the Shannon entropy goes from $p_i\log_2(1/p_i)+p_j\log_2(1/p_j)$ to $(p_i+p_j)\log_2(1/(p_i+p_j))$, and the later contribution is lower.

Granted, if at most one of the input strings is variable-length, there is no reason that adding the length makes an improvement.

$\endgroup$
5
  • $\begingroup$ Maybe we should call it input collision not a hash collision since the inputs are the same for the hash. I don't get how one creates a login [email protected] and then uses it as an attack. The salt is assumed public and the attacker cannot change it. $\endgroup$
    – kelalaka
    Commented May 9 at 12:45
  • $\begingroup$ @kelalaka: Yes it's a collision in the input part of the Argon2 variant without lengths. That's why we have the length in the actual Argon2, much like we have input padding in SHA-256. With the modified Argon2 and the answer's setup, to login as [email protected], the attacker with R/W access to the hashes choose a password ending in c and not of the minimum length for [email protected], copies the hash from the entry for [email protected] to the entry for [email protected], then logins as [email protected] with their password truncated from the final c. $\endgroup$
    – fgrieu
    Commented May 9 at 12:54
  • $\begingroup$ If one has R/W access, they do not need such tricks, write whatever you want and the hash value, and it will work, There are more complicated attacks than this even on encrypted databases if you have R/W access but have no encryption key. I think the length is there for reducing attack vectors, but not this one. $\endgroup$
    – kelalaka
    Commented May 9 at 13:39
  • $\begingroup$ @kelalaka: the answer assumes the key input of the hash is secret. Hence the usefulness of the collision for an attack. $\endgroup$
    – fgrieu
    Commented May 9 at 14:18
  • $\begingroup$ Thanks fgrieu, but remember that your key (above) is not the key that comes out of the kdf. It's some form of additional discretionary key and may be/is commonly null. $\endgroup$
    – Paul Uszak
    Commented May 11 at 12:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.