Subject: [openpgp] [PATCH] RFC4880bis: Argon2i

From: Nils Durner <[email-masked]>
Date: Sun, 18 Oct 2015 16:20:05 +0200

Hi,

attached is a patch against RFC 4880bis in
git://git.gnupg.org/gnupg-doc.git to include Argon2i as an S2K method.

Notes:

  * I have made room for 256-bit nonces. The Argon2 paper[0] recommends
    16 byte nonces for password hashing with a maximum length of 2^32-1.
    My reason for this is to make the nonce size equal to the AES-256
    key size so that we enjoy full key strength without relying on the
    password to contribute any entropy at all.
  * What do others think about the RECOMMENDATION of a parallelism
    degree of 1? Are use-cases known where hosts are unable to do
    multi-threading (well)?
  * Argon2 is not final yet, as far as I understand. The reference to it
    in template.xml should be checked/updated once it is.
      o Is Cryptolux.org considered a stable location to link to?
  * Private keys now MUST be protected using a salted S2K scheme

Looking at http://wiki.gnupg.org/rfc4880bis, HKDF should be removed from
the S2K candidates. From the HKDF paper[1]:

> typical PBKDFs [...] use [...] salt [...] and (ii) the slowing down of
> the KDF operation [...] This makes PBKDFs very different than the
> general-purpose KDFs studied here. In particular, while passwords can
> be modeled as a source of keying material, this source has too little
> entropy to meaningfully apply our extractor approach
So it cannot be used directly and the changes required to make it a
suitable PBKDF would replicate the work done for the Password Hashing
Competition[2] which selected Argon2 as the basis for its winner[3].

Regards,

Nils

[0] https://www.cryptolux.org/images/0/0d/Argon2.pdf
[1] https://password-hashing.net/
[2] https://groups.google.com/forum/#!topic/crypto-competitions/3QNdmwBS98o

diff --git a/misc/id/rfc4880bis/middle.mkd b/misc/id/rfc4880bis/middle.mkd
index 80c0a61..97c506a 100644
--- a/misc/id/rfc4880bis/middle.mkd
+++ b/misc/id/rfc4880bis/middle.mkd
@@ -256,6 +256,7 @@ reserved values:
            1  Salted S2K
            2  Reserved value
            3  Iterated and Salted S2K
+           4  Argon2i
   100 to 110  Private/Experimental S2K
 
 These are described in the following Sections.
@@ -340,11 +341,50 @@ even though that is greater than the octet count.  After the hashing is
 done, the data is unloaded from the hash context(s) as with the other
 S2K algorithms.
 
+#### {3.7.1.4} Argon2i
+
+This employs the password derivation scheme Argon2, which is memory-hard
+and resilient against side-channel and trade-off attacks.
+
+       Octet  0:        0x04
+       Octets 1-33:     32-octet salt
+       Octet 34:        one-octet parallelism value
+       Octets 35-39:    4-octet memory size value
+       Octets 40-44:    4-octet iteration count
+
+The salt value corresponds to the nonce parameter of Argon2. The
+parallelism value determines how many computational chains (threads) can
+be run. A parallelism degree of 1 is RECOMMENDED. The memory size value
+is the number of kilobytes of memory to be used when deriving the
+password. This value MUST at least be 8 * parallelism degree. The
+iteration account specifies the number of passes over memory. To protect
+against trade-off attacks, 3 iterations are RECOMMENDED.
+
+Other secondary inputs to Argon2 are not used: secret key K and
+associated data X MUST be passed with 0-octet length to Argon2.
+The tag length parameter to Argon2 that describes the length of the
+derived symmetric key MUST be equal to the key size of the symmetric
+cipher to be used. The version parameter v MUST be set to 0x10, the
+type parameter y to 1, thus specifying that the Argon2i variant is to be
+used.
+
+##### {3.7.1.4.1} NON-NORMATIVE NOTES
+Implementations can improve memory bandwidth usage by choosing larger
+parallelism degrees than 1. The number of memory blocks to be used in
+Argon2 is internally rounded down to the nearest multiple of
+4 * parallelism degree. The iteration count can be used to tune running
+time independently of the memory size.
+
 ### {3.7.2} String-to-Key Usage
 
-Implementations SHOULD use salted or iterated-and-salted S2K
-specifiers, as simple S2K specifiers are more vulnerable to dictionary
-attacks.
+Implementations MUST generate S2K specifiers that include salts
+(either type 2, 3 or 4), as simple S2K specifiers are more vulnerable to
+dictionary attacks. Use of Argon2i is RECOMMENDED as it offers
+protection against massive-parallel and side-channel attacks. When
+reading S2K specifiers that do not include salts, implementations SHOULD
+issue a warning about potentially insecure methods being used. When
+reading S2K specifiers other than Argon2i, implementations SHOULD issue
+a warning about outdated methods being used.
 
 #### {3.7.2.1} Secret-Key Encryption
 
@@ -1646,9 +1686,9 @@ following Symmetrically Encrypted Data packet, followed by the session
 key octets themselves.
 
 Note: because an all-zero IV is used for this decryption, the S2K
-specifier MUST use a salt value, either a Salted S2K or an
-Iterated-Salted S2K.  The salt value will ensure that the decryption
-key is not repeated even if the passphrase is reused.
+specifier MUST use a salt value, either S2K types 1, 3 or 4.
+The salt value will ensure that the decryption key is not repeated even
+if the passphrase is reused.
 
 ## {5.4} One-Pass Signature Packets (Tag 4)
 
@@ -4120,8 +4160,7 @@ SHOULD be rejected.
     MDC MUST be used when a symmetric encryption key is protected by
     ECDH.  None of the ECC methods described in this document are
     allowed with deprecated V3 keys.  A compliant application MUST only
-    use iterated and salted S2K to protect private keys, as defined in
-    Section 3.7.1.3{FIXME}, "Iterated and Salted S2K".
+    use S2K schemes that make use of salts to protect private keys.
 
     Side channel attacks are a concern when a compliant application's
     use of the OpenPGP format can be modeled by a decryption or signing
diff --git a/misc/id/rfc4880bis/template.xml b/misc/id/rfc4880bis/template.xml
index 82cfd27..a2a86a0 100644
--- a/misc/id/rfc4880bis/template.xml
+++ b/misc/id/rfc4880bis/template.xml
@@ -94,6 +94,16 @@
         <date year='2001' month='November'/>
         </front>
       </reference>
+      <reference anchor='Argon2i'
+     target='https://www.cryptolux.org/images/0/0d/Argon2.pdf'>
+        <front>
+        <title>Argon2: the memory-hard function for password hashing and other applications</title>
+        <author surname="Biryukov" initials="A." />
+        <author surname="Dinu" initials="D." />
+        <author surname="Khovratovich" initials="D." />
+        <date year='2015' month='October'/>
+        </front>
+      </reference>      
       <reference anchor='BLOWFISH'
                  target='http://www.counterpane.com/bfsverlag.html'>
         <front>