Does a big salt have the same memory effects as Bcrypt?

Question

Citing Thomas Pornin on the question Why can't one implement bcrypt in Cuda?:

bcrypt is a variant of the Blowfish key scheduling, which is defined over a table (a few kilobytes) which is constantly accessed and modified throughout the algorithm. Due to the size of the table, each core will have to store it in the GPU main RAM, and they will compete for usage of the memory bus.

In short, it's slow because it uses a relatively big amount of RAM. This is its advantage over PBKDF2, again from Thomas Pornin:

Bcrypt happens to heavily rely on accesses to a table which is constantly altered throughout the algorithm execution. This is very fast on a PC, much less so on a GPU, where memory is shared and all cores compete for control of the internal memory bus. Thus, the boost that an attacker can get from using GPU is quite reduced, compared to what the attacker gets with PBKDF2 or similar designs.

As far as my understanding goes, this means both PBKDF2 and Bcrypt's password hashing features can be summarized as:

function password_hash(password, iterations, memoryUsage) {
  salt = system("cat /dev/urandom | head -c " + memoryUsage);

  for i = 0 to iterations {
    # hash() is a function like SHA256
    password = hash(password + salt);
  }

  return salt + "," + password
}

# 1 million iterations; 8KiB memory usage
password_hash("letmein", 1000 * 1000, 1024 * 8);

(Where + is concatenation.) Basically this does iterated hashing with a big salt.

I know PBKDF2 can output arbitrary key sizes for e.g. block cipher encryption purposes. I also know Bcrypt accepts iterations in the form of a log number, which makes more sense. And I've considered using HMACs instead of just hash(), but I don't see how this could be exploited, especially since we're not in the message authentication business here. So in general, isn't this equivalent to what Bcrypt and PBKDF2 do in terms of password storage security?

I've commented basically the same question on the post which I linked earlier, but didn't understand the answer, and perhaps it's better as a new question anyway.

Another question I've found is very specific for SHA3; and another once again reiterates that "bcrypt needs more RAM than PBKDF2 and is thus slower on GPUs" (once again from Thomas Pornin).

Disregarding the bigger storage required to store all those huge salts, and ignoring algorithms like Scrypt and Argon2 which use even more memory but without the additional storage requirements, the only reason I see for not wanting to do this is "you shouldn't be designing your own crypto anyway." Is that correct?

Answer 1

So in general, isn't this equivalent to what Bcrypt and PBKDF2 do in terms of password storage security?

PBKDF2, yes, pretty much. The only real difference is that salt/password are used the other way around, with the password mixed in at every step.

Bcrypt, however, is different.

In your case an attacker only needs a small amount of memory compared to computational resources. For example, you can imagine a long pipeline of hashing units, which each compute one block of the salt value and then pass the output onto the next unit.

In terms of tradeoffs, say you had memory to store a million hashes long (part of the) salt. Instead of using it all on the salt, you could store a 500k hash long part of it and 500k different password guesses. Then you can calculate a huge amount of work (500k squared) before you need the next part of the salt.

What bcrypt does is have a large part of memory it modifies. That means the memory cannot be shared among different password guesses. Also, the access pattern issue (which Thomas Pornin's comment raised) can play a part – if the access pattern is non-linear, tradeoffs are worse (halving the memory used can lead to a huge slowdown).

---

The salt storage issue Maarten Bodewes mentioned in comments is also important. A large number of large salts would be unwieldy to store. And you cannot just store some seed or you are in a way back to square one – a fast way to generate the "full" salt could be used to avoid storing it all.