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

[Sam Whited <[e-mail]>]

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, [e-mail] wrote:
> > On 04/01/2021 5:57 PM Sam Whited <[e-mail]> wrote:
> >
> >
> > 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
> >
>
> 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.
>
> _______________________________________________
> Kitten mailing list [e-mail]
> https://www.ietf.org/mailman/listinfo/kitten
>

-- 
Sam Whited