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?