# Memory-expensive hash from an array of hashes?

Why can't people make a hash function that requires dozens of mega bytes of memory instead of cpu to avoid all the cracking and hacking?
What I have in mind myself is this:

1. We have an input $X$, we choose hash function SHA2-256, make a multi-megabyte array.
2. Hash $X$ and put it in the beginning of the array.
3. Hash the previous hash and put it next to it.
$(hash(x), hash(hash(x)))$
4. Step 3 until the array is full
5. Reverse the array
6. Hash the array in N passes, In each pass reading 1 byte and skipping $N-1$

I'm planning to use this for authentication, I'm not sure if it's a good idea or not, just need to know if it stop the damn GPUs from cracking my passwords.

EDIT:

This is why people shouldn't make their own encryption – see the comment by John Meacham proving this algorithm insecure. An easy fix IMO is to require the algorithm to go multiple passes over the reversed array. Like: get the first byte, skip 15 bytes, get another byte and so on… and when we reach end of the array, start from beginning, only this time we get the second byte, skip 15 bytes and so on… and we do this 16 times until we have read every byte in the array. Of course number $16$ is probably not a good number but still I think the whole idea is good.

• Why are you making your own system instead of using scrypt or something similar and well analyzed? – Thomas M. DuBuisson Dec 6 '14 at 12:42
• scrypt has some issues, and has a complex implementation, there is great demand for alternatives. I use this exact method with 16 round SHA-256 in an experimental password hashing scheme, it has provable properties, but bad implementation can lead to information leakage – Richie Frame Dec 7 '14 at 5:06
• I would suggest that you make the array size at least 4X the size of the total largest L2 cache on whatever device you are trying to defend against (including in the future), which is currently 2MB (Maxwell), so a 16-32MB minimum array – Richie Frame Dec 7 '14 at 5:31
• With that scheme you can reduce your memory usage to a small constant by trading a polynomial increase in CPU time for it. by just squaring the number of hash evaluations, you just start from the end and work backwards (recalculating intermediate hashes) building up your hash along the way. You can split the difference by selecting intermediate hashes like a binary tree requiring only O(n * log n) hashs and O(log n) memory. – John Meacham Dec 7 '14 at 13:33
• You still only have a polynomial increase but with a bigger factor, if you could calculate any bit before in 'n^2' time, you now have 'n^2' (to reproduce any bit) * nb (where b is the number of bytes in a hash) so bn^3. I also worry that any repeating pattern like that can be taken advantage of. using the result of the full hash to indicate the skip patterns for the next generation and so forth a few times may be better. I still think it may be polynomial, but with an exponential relationship to the number of 'rounds', make the skip pattern include previous rounds for more memory use. – John Meacham Dec 7 '14 at 23:19

Furthermore, you could have a look at the password hashing competition where m_cost is specifically mentioned as a possible parameter to the hash function. You'll have to look at the candidates to see if that parameter is present and how it is used though.