Optimal memory-hard KDF parameters when faced with small, slow memory

Question

I am developing for a low-power embedded system. It has two ARM9 processors at 48 MHz each. One of the processors has access to 6 MiB of "fast" memory as well as access to 26 MiB of "slow" memory. The other processor does not have direct access to memory, so it's going to be pretty much useless in this scenario (I keep it halted). The fast memory timings are complicated, and memory timings change based on whether it's a read or a write, and whether memory access is sequential or not, as well as whether accesses are 16 or 32 bits. The slow memory is much slower, but is consistently slow.

I need to implement a KDF on this system. I considered Argon2, but I do not know how to decide if it's better to run many passes on the "fast" memory, or a few passes on the "slow" memory, or some combination of the two. How do I decide what the optimal parameters are for a memory-hard KDF if the memory is going to be significantly slower than typical systems? Or is memory-hardness a losing game in this scenario and I should just use PBKDF2 (in which case I could make use of both CPUs)?

---

Update: I write this a little late (long after I finished this project, but reading the datasheet for another ARM-based device reminded me), but I ended up going with bcrypt in a region of very fast memory called the TCM (Tightly Coupled Memory), which can be accessed at the full speed of the processor. This allowed me to use the second processor simultaneously for improved security despite it not having full access to memory, since it has its own TCM region independent of the other processor. The following pseudocode is roughly what was done to turn password into result:

(CPU 0) hash_0 := tcm_bcrypt(password || 0x0)
(CPU 1) hash_1 := tcm_bcrypt(password || 0x1)
(CPU 0) result := hash_0 ^ hash_1

Answer 1

It depends. There is no answer that is the only right one.

1. Increasing the memory for Argon2 increases also time needed to process it. Test your system, what is the correlation. May be increasing memory usage 2x will reduce the performance not 2x but 6x or 10x.

2. It depends on design/architecture of your system. Namely, do you need to use Argon2 in every single request or only in some requests, let say in 1% of requests? In the 1st case high usage of Argon2 will cause high power consumption. Then, considering you have a lowe-power system, the solution should be preferred that uses CPU less, i.e. less iterations and slow memory. In the 2nd case both approaches are possible. Launch the desired number of parallel requests and check with which parameters you get the desired response times - when you use slow memory and less iterations or when you use fast memory and more iterations.

3. How important is that your system is low-power? If it is very important to consume as little power as possible, and if you have to use Argon2 in every or in many requests, then the approach with less iterations and more slow memory can be preferred. Again, first test how much more power (the total power of your system, not only CPU) is used if you use more memory.

I would assume that A) little power consumption is very important, B) that increasing used memory increases used power non-proportionally less, C) there are only a few simultaneous requests and parallel processing is not important. Then I would prefer to use more memory for Argon2, means slow memory, and less iterations.

Regarding combination of two: I would suggest not to do that. Why? Suppose you decide to spend 50% of time many iterations with the fast memory and 50% for less iterations with slow memory. If an attacker has fast memory, then for brute forcing he run many processes in parallel for your part with many iterations. Since the 2nd part is very quick, the attacker will not need as many processes for the 2nd part as for the 1st part. That's why the 2nd part (with more memory) will be for an attacker of no much importance and effectively brute forcing and protection will depends on your 1st part. It means that the 2nd part of your 2-step scheme will be more or less waste of resources. In other combination, it can be that brute forcing the 1st part is for attacker much cheaper than the 2nd part. Means, in such case the 1st step you would do would be wasting of resources and protection will depend on the 2nd step only. Where as if you decide for one step only, the attacker will have to repeat exactly this combination always, and no of your resource will be wasted.

Resources for brute forcing: Consider also the resources needed to brute force your passwords. Suppose you use password of 15 chars which means ~6bit x 15 =~90 bit =~10^30 passwords to try. To keep it simple, suppose 1 iteration of Argon2 with 1K memory costs 1FLOP (actually much more). The most powerful supercomputer Sunway TaihuLight can give about 10^17 FLOPS. To brute force your password it would needed 10^13 seconds =~ 10^5 years = 100 000 years. If you use all super computers in the world, this would be not more than 100 of its size. Means, with all super computers in the world would need 1000 years to brute force such password.

What can you do for protection? Make sure passwords are long enough and complex enough, better - that they are more or less random. If users use words from a normal dictionary with small modifications or use random but short passwords, the entropy will be small and one doesn't much resources to brute force it. If you enforce proper password policy, even a small number of iterations and a small amount of memory can be quite sufficient to make your system very secure.

Answer 2

Your goal is to minimize the hash rate of the attacker based on the resources you have. The cracker's goal is to maximize their hash rate.

Find out what parameters work well for your hardware. Pick a few variants. (More passes with less memory, as much fast memory as possible with as many passes as that permits, as much slow memory with however many passes you can afford, and a few minor tweaks on whatever cost parameters those give you.)

Next, for each variant test how many hashes per second you can get out of a good x64 PC or server. Although you can't benefit from multi-threading for your application, the password cracker can. You should leave p=1 but for your hash rate benchmark spawn a variable number of threads. Each thread of the benchmark process should call the Argon2 library in a loop to independently hash random inputs.

How many simultaneous evaluations that can be done to maximize the hash rate depends on the cracking rig's hardware and the Argon2 parameters chosen. Obviously you get diminishing returns, but I don't know of a way to estimate the optimal number of threads.

Because you have such little memory, even if you use all 32 MiB, demand for RAM would likely not be the limiting factor on a commodity hardware cracking rig. It would most likely be RAM bandwidth or the number of available cores.

Testing on an appropriate x64 machine is probably a good enough method to reason about maximum cracking hash rates. Normal GPUs cannot handle Argon2. When an FPGA user needs large amounts of memory, I think they have the FPGA communicate with commodity hardware so most of their memory is basically the same as "normal" RAM.

I haven't read much about Argon2 ASIC cracking. If you can make multiple passes on your own hardware to make the TMTO costly, then the cracker's hash rate should suffer if they try to reduce chip area by reducing memory. I also bet that 6 MiB would be good enough to limit how much an advantage ASICs could have, but I definitely have no evidence for that.

The Argon2 paper recommends that the algorithm be used with on the order of a gigabyte of RAM. I'm not sure if the authors would recommend using much much less memory, but the algorithm is flexible enough to work with a lot less. If all you have is a few MiB, then that's the best you can do.

They also recommend using as many threads as available. It's obviously preferable to use more, but I think adding more threads on the defender's side doesn't do much more than linearly reducing the cracker's hash rate.

---

My guess is that using all available fast RAM and none of the slow RAM would work best for unmodified Argon2. Do you have SIMD support on your processor? If not then quickly filling much more than 6 MiB of RAM might be hard on a slow single core computer.

I really don't know enough about hardware to have much confidence in my own speculation on which method is best. There are so many factors involved in Argon2 performance and we don't have any hard numbers, so I think it's best to benchmark.