Subject: Re: [kitten] Comments on draft-ietf-kitten-password-storage-04

From: "Sam Whited" <[email-masked]>
Date: Thu, 01 Apr 2021 17:02:48 -0400

Thank you for your feedback! I think I have addressed all of these
issues (and will upload a new version soon) except for:

On Sat, Mar 20, 2021, at 20:31, Jim Fenton wrote:
> 4.1: I’m concerned that the MUST NOT here conflicts with the SHOULD
>      NOT regarding OBSOLETE and LIMITED mechanisms in Section 2. Of
>      course, MD5 is not an SASL mechanism per se, and “support any
>      mechanism” in this context may not necessarily mean an SASL
>      mechanism, but I still found this vaguely confusing.

I thought of this as just further refining the guidance from section 2.
You SHOULD NOT use anything from a specific list, and MUST NOT use
anything that meets these criteria (which may include things that are on
the list and things that aren't). However, perhapse the SHOULD NOT in
section 2 should become a MUST NOT? Re-reading it I'm not sure why I put
SHOULD NOT there.

> 5.2: Bcrypt is no longer the current (top) OWASP recommendation.

Interestingly, I had argon2id as the top recommendation in an
earlier draft of this document then they changed it back to bcrypt.
I'll swap it back.

> 7: Suggest saying something about Unicode characters and password
>    length

Good idea. I updated this to suggest counting grapheme clusters,
which I believe is going to be better than counting scalar values,
but I'm not sure that it's ideal either. Many languages probably
don't have an implementation of the segmentation algorithm, and it
adds a lot of complexity to calculating password lengths. Other
suggestions welcome. Because of the uncertainty I did not use any
normative language here for now.

I also couldn't find an existing reference for Unicode Standard Annex
reports. Is there a bibliography somewhere that includes these which I
could reference instead of making up a new ref?

—Sam

-- 
Sam Whited

---

From: "Sam Whited" <[email-masked]>
Date: Thu, 01 Apr 2021 18:57:25 -0400

Thanks for your feedback!

Out of curiosity, why the lower memory size and a single lane, as
opposed to the m=2GiB, t=1, p=4 from
https://tools.ietf.org/html/draft-irtf-cfrg-argon2-13#section-7.3

—Sam

On Sat, Mar 20, 2021, at 21:35, [email-masked] wrote:
> Note on OWASP, it is going through massive changes and should not be
> looked at for about a week. Also settings are now based on benchmarks
> or theoretical speeds, except bcrypt because "9 feels low".
>
> Argon2id: m=37 MiB, t=1, p=1 m=15 MiB, t=2, p=1
>
> bcrypt: cost 12
>
> PBKDF2: HMAC-SHA1: 720,000 iterations HMAC-SHA256: 310,000 iterations
> HMAC-SHA512: 120,000 iterations

---

From: [email-masked]
Date: Fri, 2 Apr 2021 15:16:55 -0500 (CDT)

> On 04/01/2021 5:57 PM Sam Whited <[email-masked]> wrote:
> 
> 

My suggestion of "Argon2id m=37 MiB, t=1, p=1 or m=15 MiB, t=2, p=1" is based on facts. "Argon2id m=2 GiB, t=1, p=4" is based on feelings. Also I think I gave like 4 or 5 and OWASP went with the first two. The third one "m=10 MiB, t=3, p=1" is important since those settings can be used with Argon2i (because t≥3).

https://tools.ietf.org/html/draft-irtf-cfrg-argon2-13#section-7.4:
"The Argon2id variant with t=1 and 2GiB memory is FIRST RECOMMENDED option and is suggested as a default setting for all environments. This setting is secure against side-channel attacks and maximizes adversarial costs on dedicated bruteforce hardware.  The Argon2id variant with t=3 and 64 MiB memory is SECOND RECOMMENDED option and is suggested as a default setting for memory-constrained environments."

Let's break that down. (Note section 4 states p=4 for both)

FIRST RECOMMENDED option: Argon2id m=2 GiB, t=1, p=4
SECOND RECOMMENDED option: Argon2id m=64 MiB, t=3, p=4

For an attacker with enough memory, these settings should be similarly hard. In reality the one with lower memory usage should be harder for an attacker with enough memory. *BUT* "m=2 GiB, t=1" reads/writes 4 GiB of memory and "m=64 MiB, t=3" reads/writes 0.5 GiB of memory. So "m=2 GiB, t=1" is 8x harder than "m=64 MiB, t=3" given an attacker with enough memory. To match memory reads/writes you need "m=64 MiB, t=22".

So their two recommended options don't match in quality.

"[Argon2id m=2 GiB, t=1, p=4] is suggested as a default setting for all environments." Looking at VPS services with 4 GiB and both sites I checked have 4 GiB, 2 CPU cores (yes there are 8 GiB, 4 CPU cores, but I'm going with just enough memory to run it). Which means you should have p=2. Also unless you implement a queuing system you should not run "m=2 GiB, t=1, p=4". Since an attacker can easily DoS by exceeding memory usage with only a few request per second. P.S. This takes 1.4 seconds on my computer which is a very long time for authentication.

Now "This setting is secure against side-channel attacks..." [citation needed]. Do side-channel attacks stop working when 4 threads are randomly reading in 1 GiB of memory? I'd say no. Argon2id with side-channel attacks drops it to Argon2i m=m'/4*(1+x/p), t=1 where x is 1 or 2. x is 2 with probability of ((p-1)/p)^p. Also you'll never need to keep more than m/p/2 amount of memory. The actual amount is less and based on probabilities. So "Argon2id m=2 GiB, t=1, p=4" with a side-channel attack turns into "Argon2i m=640 MiB, t=1" with 68.4% probability or "Argon2i m=768 MiB, t=1" with 31.6% probability. I'm not aware of Argon2i t=1 attacks that just disappear when m is large-ish like 640 MiB or 768 MiB.

----

OK now why is "Argon2id m=37 MiB, t=1, p=1; m=15 MiB, t=2, p=1; or m=10 MiB, t=3, p=1" based on facts? Also these are minimum good settings. You can go higher.

After searching for CPUs, GPUs, and FPGAs, the best attacker is GPUs. FPGAs have 1/2 to 1/3 the memory bandwidth as GPUs. CPUs have 1/4 to 1/20 the memory bandwidth as GPUs.

GPUs:
RTX 3080: 10 GiB, 760.0 GB/s
RTX 3090: 24 GiB, 935.8 GB/s (takes 3 "PCI slots" vs 2)
Radeon VII: 16 GiB, 1028 GB/s

There are these GPUs. Cost is unknown but a system with 8 A100 cards is $200k:
A100 80GB​: 80 GiB, 2039 GB/s
A100: 40 GiB, 1555 GB/s

Since the current best cost/performance GPU for password cracking is the RTX 3080, I'll go with that. Memory hard algorithms cracking speed is based on memory bandwidth if there's enough computing power. At low memory usage we can assume it gets near max bandwidth. The goal for a good password hash/KDF for auth is <10 kH/s/GPU. Basically <10 kH/s/GPU is good and ≥10 kH/s/GPU is not good. Therefore a memory hard algorithm needs to read/write at least 72.5 MiB (760,000,000,000/10,000/1024/1024). "m=37 MiB, t=1" does 74 MiB, "m=15 MiB, t=2" does 75 MiB, and "m=10 MiB, t=3" does 80 MiB. These are just higher than 72.5 MiB which means the theoretical max is <10 kH/s/GPU. You could argue that an attacker could buy Radeon VII's which would push those to read/write at least 98.1 MiB. I'd argue that people aren't building password cracking rigs specifically for memory hard algorithms, but let's say you win:
m=50 MiB, t=1: does 100 MiB
m=20 MiB, t=2: does 100 MiB
m=13 MiB, t=3: does 104 MiB

Now p=1, I've made this argument in a few places here's the latest with a few minor edits:

Stealing a quote from myself "For authentication you should use p=1 because a lot of people are running a VPS with a single CPU core. Even if not, one could benchmark this and think they can go higher on settings than they should because they are not thinking about throughput. Also with memory hard algorithms, it would be wise to limit the number of simultaneous instances. An attacker can likely send more requests per second than a server to do. Which will make the server exhaust all memory if there isn't a limit." There's another place I mention that with scrypt even though you can run it with multiple threads, don't. You can think of it as t in Argon2. But if you do set up a queue or mutex, you can use multiple threads (if you are mindful of throughput). This actually makes it a better experience since it's just as strong but during off-peak times latency is faster. Using a queue is better than a mutex. Also have a max queue length and serve a 503 error if queue is too long. Otherwise the connection could timeout and you'll probably still end up doing the work.

That's only for when the server is running the password hash. If the client is running a password KDF for a PAKE or some other auth scheme then yes increase p.

---

From: "Sam Whited" <[email-masked]>
Date: Fri, 02 Apr 2021 16:29:52 -0400

Thank you. Have you sent that to the IRTF list (I'm not on there, so
apologies if you have)? I feel pretty strongly that this document should
just link to and mirror what draft-irtf-cfrg-argon2 says, so we should
probably fix it there if their numbers aren't great.

Thanks again for the feedback.

—Sam

On Fri, Apr 2, 2021, at 16:16, [email-masked] wrote:
> My suggestion of "Argon2id m=37 MiB, t=1, p=1 or m=15 MiB, t=2, p=1"
> is based on facts. "Argon2id m=2 GiB, t=1, p=4" is based on feelings.
> Also I think I gave like 4 or 5 and OWASP went with the first two. The
> third one "m=10 MiB, t=3, p=1" is important since those settings can
> be used with Argon2i (because t≥3).
>
> "The Argon2id variant with t=1 and 2GiB memory is FIRST RECOMMENDED
> option and is suggested as a default setting for all environments.
> This setting is secure against side-channel attacks and maximizes
> adversarial costs on dedicated bruteforce hardware.  The Argon2id
> variant with t=3 and 64 MiB memory is SECOND RECOMMENDED option and is
> suggested as a default setting for memory-constrained environments."
>
> FIRST RECOMMENDED option: Argon2id m=2 GiB, t=1, p=4 SECOND
> RECOMMENDED option: Argon2id m=64 MiB, t=3, p=4
>
> For an attacker with enough memory, these settings should be
> similarly hard. In reality the one with lower memory usage should be
> harder for an attacker with enough memory. *BUT* "m=2 GiB, t=1"
> reads/writes 4 GiB of memory and "m=64 MiB, t=3" reads/writes 0.5 GiB
> of memory. So "m=2 GiB, t=1" is 8x harder than "m=64 MiB, t=3" given
> an attacker with enough memory. To match memory reads/writes you need
> "m=64 MiB, t=22".
>
> "[Argon2id m=2 GiB, t=1, p=4] is suggested as a default setting for
> all environments." Looking at VPS services with 4 GiB and both sites I
> checked have 4 GiB, 2 CPU cores (yes there are 8 GiB, 4 CPU cores, but
> I'm going with just enough memory to run it). Which means you should
> have p=2. Also unless you implement a queuing system you should not
> run "m=2 GiB, t=1, p=4". Since an attacker can easily DoS by exceeding
> memory usage with only a few request per second. P.S. This takes 1.4
> seconds on my computer which is a very long time for authentication.
>
> Now "This setting is secure against side-channel attacks..." [citation
> needed]. Do side-channel attacks stop working when 4 threads are
> randomly reading in 1 GiB of memory? I'd say no. Argon2id with side-
> channel attacks drops it to Argon2i m=m'/4*(1+x/p), t=1 where x is 1
> or 2. x is 2 with probability of ((p-1)/p)^p. Also you'll never need
> to keep more than m/p/2 amount of memory. The actual amount is less
> and based on probabilities. So "Argon2id m=2 GiB, t=1, p=4" with a side-
> channel attack turns into "Argon2i m=640 MiB, t=1" with 68.4%
> probability or "Argon2i m=768 MiB, t=1" with 31.6% probability. I'm
> not aware of Argon2i t=1 attacks that just disappear when m is large-
> ish like 640 MiB or 768 MiB.
>
> ----
>
> OK now why is "Argon2id m=37 MiB, t=1, p=1; m=15 MiB, t=2, p=1; or
> m=10 MiB, t=3, p=1" based on facts? Also these are minimum good
> settings. You can go higher.
>
> After searching for CPUs, GPUs, and FPGAs, the best attacker is GPUs.
> FPGAs have 1/2 to 1/3 the memory bandwidth as GPUs. CPUs have 1/4 to
> 1/20 the memory bandwidth as GPUs.
>
> GPUs: RTX 3080: 10 GiB, 760.0 GB/s RTX 3090: 24 GiB, 935.8 GB/s (takes
> 3 "PCI slots" vs 2) Radeon VII: 16 GiB, 1028 GB/s
>
> There are these GPUs. Cost is unknown but a system with 8 A100 cards
> is $200k: A100 80GB​: 80 GiB, 2039 GB/s
> A100: 40 GiB, 1555 GB/s
>
> Since the current best cost/performance GPU for password cracking is
> the RTX 3080, I'll go with that. Memory hard algorithms cracking speed
> is based on memory bandwidth if there's enough computing power. At low
> memory usage we can assume it gets near max bandwidth. The goal for a
> good password hash/KDF for auth is <10 kH/s/GPU. Basically <10
> kH/s/GPU is good and ≥10 kH/s/GPU is not good. Therefore a memory hard
> algorithm needs to read/write at least 72.5 MiB
> (760,000,000,000/10,000/1024/1024). "m=37 MiB, t=1" does 74 MiB, "m=15
> MiB, t=2" does 75 MiB, and "m=10 MiB, t=3" does 80 MiB. These are just
> higher than 72.5 MiB which means the theoretical max is <10 kH/s/GPU.
> You could argue that an attacker could buy Radeon VII's which would
> push those to read/write at least 98.1 MiB. I'd argue that people
> aren't building password cracking rigs specifically for memory hard
> algorithms, but let's say you win: m=50 MiB, t=1: does 100 MiB m=20
> MiB, t=2: does 100 MiB m=13 MiB, t=3: does 104 MiB
>
>
> Stealing a quote from myself "For authentication you should use p=1
> because a lot of people are running a VPS with a single CPU core. Even
> if not, one could benchmark this and think they can go higher on
> settings than they should because they are not thinking about
> throughput. Also with memory hard algorithms, it would be wise to
> limit the number of simultaneous instances. An attacker can likely
> send more requests per second than a server to do. Which will make the
> server exhaust all memory if there isn't a limit." There's another
> place I mention that with scrypt even though you can run it with
> multiple threads, don't. You can think of it as t in Argon2. But if
> you do set up a queue or mutex, you can use multiple threads (if you
> are mindful of throughput). This actually makes it a better experience
> since it's just as strong but during off-peak times latency is faster.
> Using a queue is better than a mutex. Also have a max queue length and
> serve a 503 error if queue is too long. Otherwise the connection could
> timeout and you'll probably still end up doing the work.
>
> That's only for when the server is running the password hash. If the
> client is running a password KDF for a PAKE or some other auth scheme
> then yes increase p.
>
> _______________________________________________
> Kitten mailing list [email-masked]
> https://www.ietf.org/mailman/listinfo/kitten
>

-- 
Sam Whited

---

From: [email-masked]
Date: Fri, 2 Apr 2021 17:19:53 -0500 (CDT)

I haven't sent it yet. I should probably read through their message history, but I was considering just forwarding that.

> On 04/02/2021 3:29 PM Sam Whited <[email-masked]> wrote:
> 
>

---

From: "Jim Fenton" <[email-masked]>
Date: Mon, 05 Apr 2021 20:01:34 -0700

> section 2 should become a MUST NOT? Re-reading it I'm not sure why I 

I haven’t looked at the specific mechanisms that might be marked 
OBSOLETE or LIMITED, but making that a MUST NOT would ensure that there 
aren’t conflicting requirements. If you do want to have one 
requirement refine the other, it would be better put them together and 
connect them with an “and”.

> earlier draft of this document then they changed it back to bcrypt.

More generally, it’s probably not a good idea to cite the “current 
OWASP recommendation”, because that will probably change over time, 
while the RFC resulting from this draft won’t.

> could reference instead of making up a new ref?

There’s a reference at 
https://pages.nist.gov/800-63-3/sp800-63b.html#ISOIEC10646 but I see 
that it no longer works. I’ll look around for a better one.

-Jim

---

From: "Sam Whited" <[email-masked]>
Date: Tue, 06 Apr 2021 07:54:36 -0400

I've gone ahead and fixed this as suggested. I set this as a "SHOULD" in
case someone needed backwards compatibility I think, but if it's in this
category a MUST seems appropriate. These are not safe mechanisms.

—Sam

On Mon, Apr 5, 2021, at 23:01, Jim Fenton wrote:
> OBSOLETE or LIMITED, but making that a MUST NOT would ensure that
> there aren’t conflicting requirements. If you do want to have one