Is the following key stretching algorithm as memory hard as I think it is?

Question

I'm having some fun designing a key stretching algorithm that can be implemented in pure Python. It's built entirely out of the standard library's hash functions in an attempt to at least wrest some speed out of this particular language.

I came up with the following construct for mutating memory. Given a hasher initialized with a key, and a zero initialized array of hash-digest sized memory cells:

• Pick a random location in the memory cell based on the low bits of the current hash digest.
• Update the hash with the data at the picked location.
• Update the memory cell with the new hash digest.

Ignoring the memory cells, at the very least this stretching algorithm ends up feeding the hash function with N values (zeros or previous digests). My question is in regards to the amount of memory required by a brute force attack on the key. Intuitively, it seems to me that any algorithm that wishes to find the digest after the last iteration of the above loop needs to invest in at least enough storage to hold all cells that have been modified. The reasoning is that the last cell that is fed into the hasher is not known until the second to last cell is processed, and so on. Does this logic hold up?

I'm also assuming the low bits of the hash functions (specifically sha256/512) are of sufficient quality to be used as shown. Is this a fair assumption?

Edit: Regarding initialization and number of iterations

It should be obvious that if the number of total iterations is so low that there is a substantial amount of empty cells, an attacker can easily conserve memory by storing modified values only.

At first I did consider initializing the memory array, as suggested by Thomas, for example with a series of digests or cheap random data. But it occurred to me that this doesn't actually thwart an attacker with an excessively high rate of calculation vs memory. Since the array is predictably constructed, the attacker can simply store the current state of initialization av various stages, for example for every 100 kb of data. Then, whenever access is required to a cell that has not been modified since initialization, at most 100kb of data needs to be re-calculated.

So, the way I see it, there is no point in using anything but the fastest possible way to initialize the array as it must be assumed an attacker can get away without storing any initial values anyway.

The entire point of the algorithm is to do continual mutations and nothing else, hopefully leaving less and less room for shortcuts as the array fills up with values that forcibly must be stored. As very clearly pointed out by Thomas below, this establishes a strong correlation between the amount of memory that can be used and number of iterations.

So, given the condition that the number of iterations must be large enough to properly seed the array, does the algorithm hold up?

Answer 1

Let $n$ be the number of "memory cells", and $t$ the number of iterations (i.e. the three steps you describe in your question). Then we see that at each iteration, each cell has an equal probability of being picked. Then, the probability that any one cell is not selected on this iteration is:

$$1 - \frac{1}{n}$$

And hence, the probability that one cell is never selected, is:

$$\left (1 - \frac{1}{n} \right )^t$$

And so if the attacker uses an intelligent memory cell addressing system, he really only needs:

$$b \cdot n \cdot \left [ 1 - \left (1 - \frac{1}{n} \right )^t \right ] ~ ~ ~ \text{bits of memory}$$

Where $b$ is the cell's size. For $b = 256$, $n = 128 ~ \text{MB} / b = 4 \cdot 10^6$ and $t = 200000$, we get:

$$\text{Memory required} \approx 6.25 ~ \text{MB}$$

Far less than the $128 ~ \text{MB}$ expected. And that's a lot of iterations. For $t = 2 \cdot 10^6$, we need $50 ~ \text{MB}$.

---

Now look at the probability of a cell only getting used once (then saving its value is irrelevant), and watch your scheme crumble. At least, if I understand it properly. To be specific, your logic fails at this point:

Intuitively, it seems to me that any algorithm that wishes to find the digest after the last iteration of the above loop needs to invest in at least enough storage to hold all cells that have been modified.

In which you didn't consider that with your current key stretching algorithm, most cells won't be modified more than once unless you have a ludicrous number of rounds, so you don't need to invest memory to save those cells (since they are zero-initialized). Take a look at how scrypt does it - you can choose to not use any memory at all if you want, but you'll need to spend a lot more computational power. It's a trade-off. In your scheme, there is no trade-off. I can choose to not spend memory... for free.

In other words, your algorithm is a bit too simple. What you are missing is a step that initializes all the memory cells with pseudorandom (not random-access) values derived from the key, in which case storing them would be a necessity, and the scheme would a priori not be subject to this weakness.

Of course, this is all for fun and academic interest. If you need a memory-hard KDF, use scrypt.