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

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

• 1) What kind of attacks you expect? 2) How much memory per password are you going to use for this - 10K, 100K, 1 MB, 4MB? 3) What is the difference between fast and slow memory - is slower memory 2 times slower, 10 times, 1000 times slower than the fast? – mentallurg Sep 7 '19 at 9:26
• @mentallurg 1) Same threat model as Argon2, so anything from CPU to GPU to ASIC. 2) Effectively the entire memory can be used, so around 6 MiB of I use the fast memory only, 26 MiB if I use slow memory only, and 32 MiB if I use both. 3) I'm not entirely sure and I'd have to check, but something like 5x to 10x. – forest Sep 7 '19 at 9:42
• Note that you can also split the PBKDF to run on different computers, e.g. the device that enters the password can pre-hash. I'm missing that option here, but that could be because it is a standalone system. Anyway, I think it is worth mentioning. – Maarten Bodewes Oct 24 '19 at 12:10

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.

• Little power consumption actually isn't that important, and the CPUs are actually expected to be nearly maxed out for extended periods. It's just that low power requirements also lead to a less powerful system. I'm not the one choosing the system. If I was, I'd stick in some faster RAM and a faster CPU. As for the architecture of the system, the KDF is required only occasionally, not for network requests but during access to sensitive data. I can afford a few seconds at most. I.e. I could just use PBKDF2 configured for 2 seconds and call it a day. – forest Sep 7 '19 at 10:55
• My main issue with simply testing it is that its performance is not representative of that of the attacker. If I use some memory-hard KDF, the CPUs will be mostly idle as they wait on memory accesses (and unlike powerful, high-end CPUs, there is no SMT to reduce the impact of this). Compare this with something like PBKDF2 where the ALU and friends will be constantly doing work. This makes it more difficult to tell whether or not a memory-hard KDF might actually make things worse and give the attacker an advantage. – forest Sep 7 '19 at 11:09
• Hyperbolic pathological example: A single memory access takes as long as a single hash compression function evaluation. In such a case, no matter how much memory I use, an attacker will always be better off (in terms of silicon area and power use) than if I just used PBKDF2. Argon2 is usually meant for fast memory, since memory access with modern DRAM on a server is not that much slower than memory access for an optimized ASIC. – forest Sep 7 '19 at 11:13

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.

• I can't run extra threads since the second processor has no (genuine) access to memory. The processor does not have SIMD. It is a very basic ARM processor. I believe that the processor speed doesn't really matter due to the slow memory. The processor will spend most of its time waiting on memory. – forest Sep 9 '19 at 2:05
• @forest I was aware of the thread limit on the ARM processor. My point was that you should benchmark on a system that's better suited for Argon2 cracking. The only good that benchmarking on the ARM does is inform you what parameterizations are practical to use on that same platform. On the x64 try running 4 instances of Argon2 with parallelism=1. (Not 1 instance with parallelism=4.) Are we on the same page with respect to that? – Future Security Sep 9 '19 at 23:44
• Yes, I understand what you mean, but that wouldn't help with regards to the memory-hardness, where an ASIC attacker may find it more worthwhile to use a TMTO attack due to the relatively lower number of memory passes. Doing a quick test shows that PBKDF2 on the embedded system provides significantly better resistance against an Intel Xeon CPU than Argon2, with the hardware being used. – forest Sep 10 '19 at 6:54