Subject: [kitten] Password KDF settings on draft-ietf-kitten-password-storage-01

From: [email-masked]
Date: Fri, 30 Oct 2020 22:11:36 -0500 (CDT)

For section 5 "KDF Recommendations" you should aim for an attacker to be slower than 10 kH/s/GPU for password authentication and slower than 1 kH/s/GPU for encryption. This is the current recommendation from professionals in the field. A GPU is a current high end GPU but not ultra high end, as those tend to have a lower performance per cost. A "GPU" is currently an "RTX 3080". There is another way professionals look at settings and that's the defender taking <100ms for password authentication and <1000ms for encryption. The password authentication <100ms is assuming one thread because for authentication you care about throughput and it's >10 auths/s/core. I like to look at limiting the attacker as that tells you minimums for good. Looking at defender's time sets a maximum which might still make it bad. Also a defender's hardware varies a lot and settings are all over the place, but we know what GPUs attackers can use.

You should also state that these are minimum values for password authentication and that minimums should change when faster hardware or software is released.

Minimums for password authentication (<10 kH/s/GPU):
Argon2id:      m=32*1024, t=1, p=1 * (unchanged)
bcrypt:        cost 9 **
PBKDF2-SHA1:   720,000
PBKDF2-SHA256: 310,000
PBKDF2-SHA512: 120,000
scrypt:        N=32768 (N=2^15), r=8, p=1 * (unchanged)

Minimums for encryption (<1 kH/s/GPU):
Argon2id:      m=256*1024, t=1, p=1 * ***
bcrypt:        cost 12 (even though this doesn't really make sense unless you wrap the output in a KDF)
PBKDF2-SHA1:   7,200,000
PBKDF2-SHA256: 3,100,000
PBKDF2-SHA512: 1,200,000
scrypt:        N=262144 (N=2^18), r=8, p=1 * ***

* According to theoretical maximum speeds (see below) memory should be at least 36.2 MiB, 48.3 MiB, 362 MiB, and 483 MiB respectively. Actual memory bandwidth utilization is lower so I just went with 32 MiB and 256 MiB. Bandwidth utilization would need to be less than 88%, 66%, 71%, and 53% respectively on these settings. Which seems very likely. Side note on parameters, you can lower memory usage and increase t for Argon2id and p for scrypt. Basically you can think of it like:
Argon2id: m * t >= 32768 (or this to be more accurate: m * (3 * (t - 1) + 2) >= 65536)
scrypt:   N * p >= 32768

** It's on the cusp of being cost 9 and there's an optimization that should push it over the line to cost 9. (see next section)

*** It is likely that using 128 MiB will be <1 kH/s/GPU due to reaching the point where doubling memory quarters attacker's speed. Bandwidth utilization would need to be less than 35% and 26% respectively on these settings with 128 MiB.

----

Benchmarks (https://gist.github.com/Chick3nman/bb22b28ec4ddec0cb5f59df97c994db4):
PBKDF2-HMAC-SHA1 (i=1000):   7135.9 kH/s
PBKDF2-HMAC-SHA256 (i=1000): 3029.2 kH/s
PBKDF2-HMAC-SHA512 (i=1000): 1179.3 kH/s
bcrypt (cost=5):             75778 H/s ****

To get settings for <10kH/s/GPU with PBKDF2 take the speed and divide by 10 and round up (multiply by 1000 to get speed for "1 iteration" then divided by 10000 H/s to get iterations for 10 kH/s). For bcrypt the number of iterations is (1+2*2^cost). The formula to get bcrypt cost for <10kH/s is (started with "speed * (1 + 2 * 2^5) / (1 + 2 * 2^cost) = 10000 H/s" and solved for cost):
cost = ceiling(log2((speed * (1 + 2 * 2^5) / 10000 - 1) / 2))

Settings for <10kH/s/GPU:
PBKDF2-HMAC-SHA1:   720,000
PBKDF2-HMAC-SHA256: 310,000
PBKDF2-HMAC-SHA512: 120,000
bcrypt:             8 ****

**** I have an optimization that should put it over the line to cost 9 (which is at >78930 H/s in a benchmark for cost 5). It has not been benchmarked on an RTX 3080 and there's an issue with it on the current version of hashcat that I need to fix. This was benchmarked on an older version of hashcat and on a different card. The increased speed means an RTX 3080 would be cost 9 for <10kH/s/GPU. Since the RTX 3080 has more shared memory, it would benefit even more from this optimization. Anyway I don't have actual benchmarks to back this up, but bcrypt should be cost 9 for <10kH/s/GPU.

----

For memory hard algorithms like Argon2 and scrypt, we're going to need to look at theoretical numbers. Looking at the bandwidth from https://en.wikipedia.org/wiki/List_of_Nvidia_graphics_processing_units#GeForce_30_series an RTX 3080 has 760.0 GB/s.

For scrypt, it reads 1x and writes like 0.5x (depends on time-memory optimization) the memory used in the algorithm:
N = 2^ceiling(log2(gpuBandwidth / 10000 / 1.5 / 128 / r / p))

For Argon2, the first iteration reads 1x and writes 1x the memory used in the algorithm and after that it reads 2x and writes 1x:
m = ceiling(gpuBandwidth / 10000 / (2 + 3 * (t - 1)) / 1024 / 4 / p) * 4 * p

Note the "ceiling(.../4/p)*4*p" this is because Argon2 rounds down 37,110 to 37,108 (for 760.0 GB/s, t=1, p=1). With Argon2 you have more leeway with the exact amount of memory but usually you round up the the nearest nice binary number.

----

Benchmarks for RTX 2080 Super (https://gist.github.com/epixoip/47098d25f171ec1808b519615be1b90d)

> Hashmode: 8900 - scrypt (Iterations: 1)
> Speed.#4.........:   1115.7 kH/s (7.23ms) @ Accel:16 Loops:1 Thr:16 Vec:1

Settings are N=1024, r=1, p=1 and GPU bandwidth utilization is about 44%. The runtime on it "7.23ms" is a little low so the speed should be higher with custom settings because less time is wasted in API calls.

> Hashmode: 9300 - Cisco-IOS $9$ (scrypt) (Iterations: 1)
> Speed.#4.........:      46069 H/s (99.74ms) @ Accel:16 Loops:1 Thr:8 Vec:1

Settings are N=16384, r=1, p=1 and GPU bandwidth utilization is about 29%.

The low amount of GPU bandwidth utilization is interesting and I'm likely off with my estimates above as those are theoretical maximum speeds. Also as you use more memory you hit a point where doubling memory quarters attacker's speed. Hmm it appears it's not utilizing a lot of memory. Ignoring the scrypt time-memory optimization, it's only using 96 MiB and 768 MiB and the card has 8 GiB.

---

From: "Sam Whited" <[email-masked]>
Date: Sat, 31 Oct 2020 16:17:00 -0400

Hi,

On Fri, Oct 30, 2020, at 23:11, [email-masked] wrote:
> This is the current recommendation from professionals in the field.

Do you have a citation for these recommendations? As I mentioned in our
private emails I'm hesitant to publish original research that hasn't
been peer reviewed. Of course, if after undergoing expert review the
folks here come to similar conclusions I'm happy to update the doc. For
now I'm just using recommendations from OWASP and NIST.

Including recommendations for how long a single round of your KDF should
take on some theoretical "average" hardware might be a good idea if we
can come to a conclusion about what that hardware is.

> You should also state that these are minimum values for password
> authentication and that minimums should change when faster hardware or
> software is released.

The latest draft of the document (-01) does so.

—Sam

---

From: [email-masked]
Date: Sat, 31 Oct 2020 20:01:55 -0500 (CDT)

> On 10/31/2020 3:17 PM Sam Whited <[email-masked]> wrote:
> 
> Hi,
> 
> Do you have a citation for these recommendations?

Two panelists from the Password Hashing Competition (Jeremi Gosney and me). I believe Jeremi is the one who first stated the recommendation of <10 kH/s/GPU for password authentication. He has a company that sells password cracking hardware to large companies and governments. Also Sam Croley, an esteemed professional password cracker, agrees. If you want I could probably find a few others in the industry that agree, but it is unlikely that anyone is going to write a paper on this topic as it's more like a tweet than a paper.

> As I mentioned in our
> folks here come to similar conclusions I'm happy to update the doc.

You told me to post it on the IETF mailing list for review. So I collected everything I wrote and updated it for *-01 and for RTX 3080 since that just replaced the RTX 2080 Super as a "GPU".

> For

Note that the recommendation from OWASP for bcrypt was briefly changed to cost 12 by one person and switched back to cost 10. Their defense cited your draft as why to keep it at cost 12. Until I pointed out that they are now citing each other.

> The latest draft of the document (-01) does so.

Only PBKDF2 says that the settings are a minimum. Oh the "should change when faster hardware" that was in *-00. I must of missed that the first time I read it and obviously it wasn't highlighted in the diff.