Background. All MKDF (memory-hard KDF) algorithms that I know (Scrypt, Argon2, Balloon) don't really require all the memory at every moment during the run time of algorithm's implementation, but instead require a hefty computational penalty when less memory is used.
Roughly, the memory usage against time graph looks like this (of course, better MKDFs will have more adjacent spikes):
(Image from there)
I think this limitation (not needing memory at every moment) is due to how general purpose computers work (e.g. CPU, RAM).
Question. If we lax the assumption about hardware (e.g. allow for specialised hardware) can we define an MKDF algorithm that requires all its memory at every time moment? E.g. can we make it such that the graph shows a straight line?
My thoughts so far. Imagine if we have a mechanical memory plane, where the state of every memory bit is connected to the state of every other bit, such that if we flip one bit's value, it will cause to flip every other bit in the entire memory.
With this mechanical memory plane, we perform a single instruction that flips 1 bit, and that single operation will mechanically flip the state of all other bits.
If the relationship between the bits is not predictable (e.g. similar to how a small change in a block worth of clear text results in complete change in the cipher text), then I guess this mechanical memory has became an MKDF that can work like this:
- User initialises the memory by filling it with random bits that are generated off some seed. This is done only once.
- User encodes his password in the most significant bits the mechanical memory plane. This is obviously done every time the user wants to derive a more secure key off his password.
- As the user is encoding his password in the early bits of that mechanical memory sheet, the states of all bits in the mechanical memory sheet will be flipping in an unpredictable way.
- Finally, when the user is done encoding his password, he simply picks the least significant bits of that mechanical memory plane as the derived key.
If an adversary tries to do this with a smaller mechanical memory plane (with less memory bits), then his derived key will be totally random.
If my guesses are right, and that implementing such hardware is doable, then:
- This is a platform for MKDF hardware-based algorithms that always require the same amount of memory, at every single time moment during the run-time of the key derivation function.
- The user buys a single mechanical memory plane for his own logins, so the user can afford it as it's a single purchase. But the adversary will have to buy many of these sheets in order to do them in parallel. So I guess it's scalable for the user, but not scalable for the adversary.
I guess we can implement this mechanical memory plane using:
- Entangled quanta is probably a more natural way of thinking about it.
- A large mechanical board with lots of grease so that the cogs don't get stuck.
- Electronics for a smaller and less greasy alternative.
