Salt-based memory accesses

[samuel-lucas6]

I'm still unsure whether the memory access pattern should depend on the salt. This means a unique access pattern per user, which helps against attacks. However, there was concern on the PHC mailing list that a cache-timing attack may leak who has logged in (see #14).

From the wording in the Balloon paper and comments on the PHC mailing list, it sounds like Balloon was the first algorithm to propose using the salt. Therefore, I'm not sure there's any literature on this.

The next best thing if the salt isn't used would be getting the user to specify a context string (e.g., the website/application name) alongside the other parameters to make the access pattern unique to that service. However, this means yet another parameter for the user (in addition to the associatedData as well), and the length would need to be restricted for performance.

[cipriancraciun]

I too am concerned about possible side-channel leaks of the salt being used, and firstly I would like to explain my use-case: as per the discussion I had with @samuel-lucas6 on samuel-lucas6/Cahir#1 (comment), sometimes the "salt" isn't independent of the password (or other input parameters), thus should be treated with the same care as the actual "password".

However, perhaps in my use-case I kind of miss-use the "salt", and perhaps the "salt" argument to any derivation function should be treated exactly as the general expectation: namely as a publicly known value that holds nothing secret and has no security impact if found out.

---

Thus, potential solutions to the "should the algorithm be independent on both the salt and the password" problem might be the following:

(A) As @samuel-lucas6 suggested, having a constant "context string" (or "customization string"), perhaps mashed together with some constant-ish user arguments (i.e. "associated data", e.g. file-name, site name, etc.).

However, and assuming most of the time the same context string is used (for example if the attacker targets a specific application), and the same default "associated data" is used, then the attacker has a deterministic flow through the hashes, thus perhaps he can get some advantages by employing ASICS or other hardware-based implementations;

(B) Perhaps the developer should take the password and the salt, and generate a new pair that can be then used as input for the algorithm, like for example:

let _input_password, _input_salt = ...
let _hashed_password = hash ("balloon-password-hashed", _input_password)
let _hashed_salt = hash ("balloon-salt-hashed", _input_salt)
let _intermediate_key = keyed_hash (_hashed_salt, _hashed_password)
let _balloon_password = hash ("balloon-password", _intermediate_key)
let _balloon_salt = hash ("balloon-salt", _intermediate_key)

Observations:

• hash and keyed_hash are the same as the hash function used in the rest of the algorithm; (if there isn't a "keyed" variant, then HMAC can be used);
• the intermediary hash step might seem superfluous (i.e. computing _hashed_*), but some keyed hash algorithms might allow only fixed size inputs; (for example Blake3's variant of keyed hash expects a 32 bytes, 256 bits, input which is exactly the default output of the function;)
• given the original algorithm description, the _balloon_password could in fact be used directly as the b[0] value (which is the single place where the password is used);

Thus, even if the internal salt or password is leaked, they are in fact hashes of the actual inputs, thus a separate brute-force attack has to be undertaken.

---

On a second thought, given the original paper description where the salt is used to choose the dependent blocks:

int other = to_int(hash(cnt++, salt, idx_block)) mod s_cost

Given it is hashed, the side-channel leaks would be in fact about the hash of the salt, which furthermore reduced in entropy by the modulo s_cost.

Thus, perhaps in real terms, there is no leak at all, and just a theoretical problem? (I don't know, I'm not a cryptographer.)

[samuel-lucas6]

However, and assuming most of the time the same context string is used (for example if the attacker targets a specific application), and the same default "associated data" is used, then the attacker has a deterministic flow through the hashes, thus perhaps he can get some advantages by employing ASICS or other hardware-based implementations;

This is the problem with data-independent schemes. Having a context parameter should be better than Argon2i and is I think the best you can do without relying on the salt or changing the access pattern each time but somehow resulting in the same output, which I think there's a paper for that I haven't read but would be a lot more complicated. Someone I spoke to also suggested relying on the salt wouldn't help much anyway.

Thus, even if the internal salt or password is leaked, they are in fact hashes of the actual inputs, thus a separate brute-force attack has to be undertaken.

This is quite confusing to reason about. It's a lot of hashing, and the only thing that helps is if the salt is unknown. But what's the goal here? The scheme is already password-independent.

Thus, perhaps in real terms, there is no leak at all, and just a theoretical problem? (I don't know, I'm not a cryptographer.)

I'm obviously not a cryptographer either, and this topic hasn't been properly discussed. However, the people I've spoken to have said using the salt is a bad idea, which would explain why no algorithm besides Balloon (as far as I know) uses the salt.