You allocate a 1MB array. Salt the password (this is the only time the salt is used other than being stored at the end) and hash the password with SHA256 8 times. Place 31,250 copies (125,000 was an error) of the first hash to fill the array, so it cannot be de-allocated or used for anything else until the process is complete. You then use the first hash as salt for the 1MB array and hash the entire array salted with the hash 8 times and place copies of the result in the second 1 KB block of the array. Keep repeating the hash and fill procedure until the entire 1 MB array is over-written step by step and then finally hash the entire 1MB. That is the hash you store next to your salt.

The default I am trying for is 8,000 SHA-256 hashes with a 1 MB memory requirement.

If the user wants higher memory requirements, the array can be 1 MB, 2 MB, up to maybe 8 MB. The algorithm is simply copying intermediate hashes 125 times, 250 times, etc. If the user wants more iterations, each hash is performed somewhere between 8 times, 16 times, 32 times etc.

I'm trying to make it so an attacker cannot de-allocate the 1 MB array or use it for anything else for the entire duration.

How would this stack up against BCrypt or SCrypt in terms of defending passwords against offline attacks?

  • $\begingroup$ Nice try. I Would suggest you use figures and equations for a clearer understanding of the design. This will help you to see the weak and strong points, too. $\endgroup$ – kelalaka Oct 10 '20 at 10:55
  • $\begingroup$ Like $A[1...125.000] = SHA256^8(Salt \mathbin\| password)$, Here one should prefer $A[1...125.000] = SHA256^8(Salt \mathbin\| password \mathbin\| index)$ $\endgroup$ – kelalaka Oct 10 '20 at 11:02

The question's construction is an attempt at making a memory-hard function. This is more difficult than it seems, and the construction proposed has several flaws:

  1. An adversary performing a password dictionary attack needs only a little over half a megabyte of memory per concurrently running process. This is because adversaries are not bound to "put 31,250 copies of the first hash to fill the array"; they can take advantage of the fact that the last copy will not get changed (become different from the but last) until the last of the passes in the process. For large $n$, this allows running nearly $2n$ processes interleaved (that is, with their stages of progress evenly distributed at a given time) using only $n$ megabytes of memory.

  2. Independently, an adversary can save about 1/16 of the hashing effort by noticing that typically, in the step reading "hash the entire array salted with the hash 8 times", the beginning of what's hashed (on average, 0.5 MB out of 8 MB) is identical to what it was in the previous step.

  3. It is hard to rule out that an adversary using an ASIC (or perhaps FPGA) for a password dictionary attack can organize things so that some of the (half-)megabyte of memory needed per process can be in relatively slow/cheap memory such as off-die DRAM, and only very little in fast on-die static RAM or flip-flops.

  4. In a SHA-256 internal block hash, a sizable part of the computational effort goes into the so-called expansion of the 64-byte message block. Because most of the data hashed by the overall algorithm is hashed many times and with the same alignment to 64-byte blocks, it is theoretically possible to cache expanded message blocks and save most of that expansion work. That's quite worthwhile when repeatedly hashing the same data block, which happens nearly half of the time due to flaw 1.

Flaw 1 can be fixed by adding an outer loop performed many times, so that during all except the first of these loops the 32-byte blocks of the memory array have different and arbitrary-like content. However, that exacerbates the risk that flaw 3 becomes serious, and/or that memory even slower/cheaper than DRAM becomes usable.

Flaw 2 can be fixed by incrementing the first word of the first block before starting each hash.

Flaw 3 is the theoretically hardest to repel. Using data-dependent addresses might help, but tends to slow down legitimate use too, and may introduce undesirable side channel leakage.

Flaw 4 becomes merely theoretical after flaw 1 has been fixed: exploiting it requires a lot of extra memory, so that's most likely not worthwhile in practice.

Memory hard functions are like most crypto: anyone, from the most clueless amateur to the best cryptographer, can create one they can't break (Bruce Schneier). Thus the prudent thing is to use the ones that passed scrutiny; or if the objective is learning, study that. The current recognized standard is Argon2. It's worth reading about Balloon, too.

  • $\begingroup$ Another fix for 1. Don't limit the pass to 125000 values grow it with the new produced hash so that the final index of the array requires all. $\endgroup$ – kelalaka Oct 10 '20 at 11:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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