[CFRG] Comments on draft-irtf-cfrg-argon2-13.txt

steve@tobtu.com Sun, 11 April 2021 03:18 UTC

Return-Path: <steve@tobtu.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 7A4683A26E7 for <cfrg@ietfa.amsl.com>; Sat, 10 Apr 2021 20:18:28 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.899
X-Spam-Level:
X-Spam-Status: No, score=-1.899 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, SPF_NONE=0.001] autolearn=ham autolearn_force=no
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id UPkIpdMNOuTP for <cfrg@ietfa.amsl.com>; Sat, 10 Apr 2021 20:18:26 -0700 (PDT)
Received: from mout.perfora.net (mout.perfora.net [74.208.4.196]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id D8CEF3A26E5 for <cfrg@ietf.org>; Sat, 10 Apr 2021 20:18:25 -0700 (PDT)
Received: from oxusgaltgw13.schlund.de ([10.72.72.59]) by mrelay.perfora.net (mreueus002 [74.208.5.2]) with ESMTPSA (Nemesis) id 0MYh3k-1kzzbm3hek-00VRFi for <cfrg@ietf.org>; Sun, 11 Apr 2021 05:18:24 +0200
Date: Sat, 10 Apr 2021 22:18:24 -0500 (CDT)
From: steve@tobtu.com
To: "cfrg@ietf.org" <cfrg@ietf.org>
Message-ID: <587454483.311259.1618111104472@email.ionos.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
X-Priority: 3
Importance: Normal
X-Mailer: Open-Xchange Mailer v7.10.4-Rev20
X-Originating-Client: open-xchange-appsuite
X-Provags-ID: V03:K1:j9dN2jO25HwmFteBA0p1vNDKaIXRIKN+di9NwNUdEzwbJRVyngF MZDzy0sAhh6Y8W1MK42AmIFJvwmreu6a7eLE7xwpA+pYHHdRrKiz01kmEsNNV10YvrhwO8M 2j8UQBUytTBfXxHwy+CmVdxyIQxEdSPy3Rra9q8WoHQvb+RxYuLF3qXROWTMMFCyD5iiKGZ sPaqVv/gqAVLXBEMbOyvQ==
X-UI-Out-Filterresults: notjunk:1;V03:K0:9WjZBkB5Xy8=:0BHAzZBEYJQ55bfbYAcG8C e1/MWFxDD7COjOEOYYMncuQSqToKjiKgO3/vfrVYKJ/RUA3IrWpiEp46fEc82+VhFgfKlg2WG 65Tbe+/JQOxXJqHgKHyt0Rs2Tn+iqNOW0Z2+BsNL2Dkwb6MFsaMSaA6g4j/WBWk3FzotN+NpI a7NSYrDz1u/Ku8DruMhB9QMwtrqUBmc/Ek+DZQwB5qNaNLKKuoMw0VMZAUk31WlS8P6n58UaL WKVpWf8C4hx7wmUCBqUhGrcHQP2RJihCPeCJHoW62UGJ/hwN4reNzMhbDayM3ZQB4SxlX/Qi7 bL3CDC6f+FLFr0cqgcaIP56uHnciuaCuobXWkmh+n31CvmmSf6H1cVsnCK9szkKE3YJVn3jC/ RMfd7mZb7gxSioxFf+n4mMm75bv7CUNz8V/bvs+Ad6ipRuJR9c4Xbxf1kKpzlPbzsphQM5+vO VPJiV/80WmsFmAWkJWFpzk+JpG/GfqlJeA+Ysti/7l1HE6wQTgsJ
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/fk_UMzR_uhXo-EbCBvRNTiN7RsA>
Subject: [CFRG] Comments on draft-irtf-cfrg-argon2-13.txt
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Sun, 11 Apr 2021 03:18:28 -0000

> 4. Parameter Choice
>
> Argon2id is optimized for more realistic settings, where the adversary possibly can access the same machine, use its CPU or mount cold-boot attacks.

"mount cold-boot attacks" needs to be removed.

----

> 7.4. Recommendations
>
> 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.

"This setting is secure against side-channel attacks" this is not true. Note Argon2id with side-channel attacks drops it to basically 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. You only need to do 99% of the first slice on all lanes then the second slice on one lane. Then you get to a dependent read that is in the current lane (that ((p-1)/p)^p probability) use that to get a the second dependent read location. With those two you should have a low probability (1 in 10000 or so) of a false positive. In some cases if m is large enough, you only need the first one dependent read location. Thus you don't care if it's in the current lane.

----

Argon2id: m=2 GiB, t=1, p=4
Argon2id: m=64 MiB, t=3, p=4

Why are these so disparate? 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". Bandwidth used for Argon2 is m*(3*t-1)).

I'm all for going to 11 on settings but you want a server to do "m=2 GiB, t=1, p=4" with no mention of a queue. When settings are this high, it is very important to set up a queue to prevent it from exhausting all memory. Also there is no mention of throughput: number of password checks per second. In the past it was suggested to be able to do about 10 checks/core/second.

----

It maybe be useful to state minimum settings. Basically a bottom of the barrel, don't go lower than these settings. 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
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

----

Note for encryption you want these to be <1 kH/s/GPU. At these memory sizes the GPU likely can't use max bandwidth unless p>1.

m=363 MiB, t=1: does 726 MiB
m=145 MiB, t=2: does 725 MiB
m=91 MiB, t=3: does 728 MiB

Or for Radeon VII:
m=491 MiB, t=1: does 982 MiB
m=197 MiB, t=2: does 985 MiB
m=123 MiB, t=3: does 984 MiB

----

To future proof these you could say find a GPU that has an MSRP of about $700 in 2015 USD with the highest memory bandwidth or 1000 GB/s which ever is higher. Then divide memory bandwidth by ((3*t-1)*10.5 GB/s) for minimum memory size in MiB.