4
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Why are you making your own system instead of using scrypt or something similar and well analyzed? $\endgroup$
    – Thomas M. DuBuisson
    Commented Dec 6, 2014 at 12:42
  • 1
    $\begingroup$ 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 $\endgroup$
    – Richie Frame
    Commented Dec 7, 2014 at 5:06
  • 1
    $\begingroup$ 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 $\endgroup$
    – Richie Frame
    Commented Dec 7, 2014 at 5:31
  • 1
    $\begingroup$ 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. $\endgroup$
    – John Meacham
    Commented Dec 7, 2014 at 13:33
  • 1
    $\begingroup$ 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. $\endgroup$
    – John Meacham
    Commented Dec 7, 2014 at 23:19

2 Answers 2

Reset to default
3
$\begingroup$

The premise that people cannot make a memory intensive password hashing function is incorrect. scrypt does approximately what is described in the question. Of course you still want to limit the amount of memory, especially if many of these hashes are to be calculated in parallel.

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.

Note that the main idea of using larger amounts of memory is to protect against brute force attempts that make use of hardware acceleration. Just scaling up the amount of memory to rely on the speed of memory access does not make sense; an attacker may have a system that does faster memory access than your system. It's less likely that an attacker has both hardware acceleration and a hugely fast & large memory system.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you, right on the point, And I did mention I'm doing this to protect myself against parallel processing specially with gpgpu. $\endgroup$
    – Behrooz
    Commented Dec 6, 2014 at 15:24
0
$\begingroup$

There are alot of trade-offs ina various tasks. People actually CAN do the things you're describing, and the question is not just about the particular task. The problem/point is, that there's no option in - for example - OpenSSL : what to use? CPU-costly or Memory-costly algo? That's a pity that there is no such option. And usually you're forced to do this by hand. Another special case you should keep in mind in such a case is a microcontroller case. You can have ~128K of fast RAM and the external one can be really slow, so the less-cpu-intensive memory algo will actually BE slower due to the amount of an external slow memory used.

Improve this answer
$\endgroup$
2
  • $\begingroup$ When I was deciding if I should go this far for authentication I thought of it this way, my application requires gigabytes of memory to function, if the user cannot afford to give it 128 MB for login then he probably shouldn't bother logging in. $\endgroup$
    – Behrooz
    Commented Dec 7, 2014 at 16:44
  • $\begingroup$ Actually gigabytes of memory is not a big problem nowdays on PC's... 8-16Gb becomes a common case. $\endgroup$
    – Alexey Vesnin
    Commented Dec 8, 2014 at 18:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.