idnits 2.17.1 draft-arciszewski-xchacha-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack a Security Considerations section. ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The abstract seems to contain references ([RFC7539]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Line 163 has weird spacing: '...ccccccc ccccc...' == Line 164 has weird spacing: '...kkkkkkk kkkkk...' == Line 165 has weird spacing: '...kkkkkkk kkkkk...' == Line 166 has weird spacing: '...bbbbbbb nnnnn...' == Line 170 has weird spacing: '...ccccccc ccccc...' == (3 more instances...) == The document doesn't use any RFC 2119 keywords, yet seems to have RFC 2119 boilerplate text. -- The document date (September 7, 2018) is 2029 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '1' on line 263 -- Looks like a reference, but probably isn't: '2' on line 266 -- Looks like a reference, but probably isn't: '3' on line 268 -- Looks like a reference, but probably isn't: '4' on line 270 -- Looks like a reference, but probably isn't: '5' on line 272 -- Looks like a reference, but probably isn't: '6' on line 275 -- Looks like a reference, but probably isn't: '7' on line 277 -- Looks like a reference, but probably isn't: '8' on line 279 -- Looks like a reference, but probably isn't: '9' on line 281 -- Looks like a reference, but probably isn't: '10' on line 283 -- Looks like a reference, but probably isn't: '11' on line 285 ** Obsolete normative reference: RFC 7539 (Obsoleted by RFC 8439) Summary: 4 errors (**), 0 flaws (~~), 8 warnings (==), 12 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 (No Working Group) S. Arciszewski 3 Internet-Draft Paragon Initiative Enterprises 4 Intended status: Informational September 7, 2018 5 Expires: March 11, 2019 7 XChaCha: eXtended-nonce ChaCha and AEAD_XChaCha20_Poly1305 8 draft-arciszewski-xchacha-00 10 Abstract 12 The eXtended-nonce ChaCha cipher construction (XChaCha) allows for 13 ChaCha-based ciphersuites to accept a 192-bit nonce with similar 14 guarantees to the original construction, except with a much lower 15 probability of nonce misuse occurring. This enables XChaCha 16 constructions to be stateless, while retaining the same security 17 assumptions as ChaCha. 19 This document defines XChaCha20, which uses HChaCha20 to convert the 20 key and part of the nonce into a subkey, which is in turn used with 21 the remainder of the nonce with ChaCha20 to generate a pseudorandom 22 keystream (e.g. for message encryption). 24 This document also defines AEAD_XChaCha20_Poly1305, a variant of 25 [RFC7539] that utilizes the XChaCha20 construction in place of 26 ChaCha20. 28 Status of This Memo 30 This Internet-Draft is submitted in full conformance with the 31 provisions of BCP 78 and BCP 79. 33 Internet-Drafts are working documents of the Internet Engineering 34 Task Force (IETF). Note that other groups may also distribute 35 working documents as Internet-Drafts. The list of current Internet- 36 Drafts is at https://datatracker.ietf.org/drafts/current/. 38 Internet-Drafts are draft documents valid for a maximum of six months 39 and may be updated, replaced, or obsoleted by other documents at any 40 time. It is inappropriate to use Internet-Drafts as reference 41 material or to cite them other than as "work in progress." 43 This Internet-Draft will expire on March 11, 2019. 45 Copyright Notice 47 Copyright (c) 2018 IETF Trust and the persons identified as the 48 document authors. All rights reserved. 50 This document is subject to BCP 78 and the IETF Trust's Legal 51 Provisions Relating to IETF Documents 52 (https://trustee.ietf.org/license-info) in effect on the date of 53 publication of this document. Please review these documents 54 carefully, as they describe your rights and restrictions with respect 55 to this document. Code Components extracted from this document must 56 include Simplified BSD License text as described in Section 4.e of 57 the Trust Legal Provisions and are provided without warranty as 58 described in the Simplified BSD License. 60 Table of Contents 62 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 63 1.1. Notation and Conventions . . . . . . . . . . . . . . . . 3 64 2. AEAD_XChaCha20_Poly1305 . . . . . . . . . . . . . . . . . . . 3 65 2.1. Motivation for XChaCha20-Poly1305 . . . . . . . . . . . . 3 66 2.2. HChaCha20 . . . . . . . . . . . . . . . . . . . . . . . . 4 67 2.2.1. Test Vector for the HChaCha20 Block Function . . . . 4 68 2.3. XChaCha20 . . . . . . . . . . . . . . . . . . . . . . . . 5 69 2.3.1. XChaCha20 Pseudocode . . . . . . . . . . . . . . . . 6 70 3. References . . . . . . . . . . . . . . . . . . . . . . . . . 6 71 3.1. Normative References . . . . . . . . . . . . . . . . . . 6 72 3.2. URIs . . . . . . . . . . . . . . . . . . . . . . . . . . 6 73 Appendix A. Additional Test Vectors . . . . . . . . . . . . . . 7 74 A.1. Example and Test Vector for AEAD_XCHACHA20_POLY1305 . . . 7 75 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 8 77 1. Introduction 79 AEAD constructions (Authenticated Encryption with Associated Data) 80 allow for message confidentiality to be assured even in the presence 81 of adaptive chosen-ciphertext attacks, but they're known to be 82 brittle to nonce-misuse conditions [1]. 84 Several nonce misuse resistant cipher constructions have been 85 proposed over the years, including AES-SIV ([RFC5297]), AES-GCM-SIV 86 [2], and several CAESAR candidates [3]. 88 However, a more straightforward strategy can prevent nonce misuse 89 conditions in environments where a large number of messages are 90 encrypted. Simply use a large enough nonce such that applications 91 can generate them randomly for each message and the probability of a 92 collision remains low. 94 To this end, we propose a solution that is already implemented in 95 many software projects that extends the nonce of ChaCha20 to 192 bits 96 and uses it to build an AEAD construction. 98 1.1. Notation and Conventions 100 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 101 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 102 document are to be interpreted as described in RFC 2119 [RFC2119]. 104 2. AEAD_XChaCha20_Poly1305 106 XChaCha20-Poly1305 is a variant of the ChaCha20-Poly1305 AEAD 107 construction as defined in [RFC7539] that uses a 192-bit nonce 108 instead of a 96-bit nonce. 110 The algorithm for XChaCha20-Poly1305 is as follows: 112 1. Calculate a subkey from the first 16 bytes of the nonce and the 113 key, using HChaCha20 (Section 2.2). 115 2. Use the subkey and remaining 8 bytes of the nonce (prefixed with 116 4 NUL bytes) with AEAD_CHACHA20_POLY1305 from [RFC7539] as 117 normal. The definition for XChaCha20 is given in Section 2.3. 119 XChaCha20-Poly1305 implementations already exist in WireGuard [4], 120 libsodium [5], Monocypher [6], xsecretbox [7], and in Go's crypto/ 121 chacha20poly1305 [8] library. 123 Similarly, Google's HPolyC [9] implements XChaCha12-Poly1305. 125 2.1. Motivation for XChaCha20-Poly1305 127 The nonce used by the original ChaCha20-Poly1305 is too short to 128 safely use with random strings for long-lived keys. 129 XChaCha20-Poly1305 does not have this restriction. 131 By generating a subkey from a 128-bit nonce and the key, a reuse of 132 only the latter 64 bits of the nonce isn't security-affecting, since 133 the key (and thus, keystream) will be different. Additionally a re- 134 use of only the first 128 bits of the nonce isn't security-affecting, 135 as the nonce derived from the latter 64 bits is different. 137 Assuming a secure random number generator, random 192-bit nonces 138 should experience a single collision (with probability 50%) after 139 roughly 2^96 messages (approximately 7.2998163e+28). A more 140 conservative threshold (2^-32 chance of collision) still allows for 141 2^64 messages to be sent under a single key. 143 Therefore, with XChaCha20-Poly1305, users can safely generate a 144 random 192-bit nonce for each message and not worry about nonce-reuse 145 vulnerabilities. 147 As long as ChaCha20-Poly1305 is a secure AEAD cipher and ChaCha is a 148 secure pseudorandom function (PRF), XChaCha20-Poly1305 is secure. 150 2.2. HChaCha20 152 *HChaCha20* is an intermediary step towards XChaCha20 based on the 153 construction and security proof used to create XSalsa20 [10], an 154 extended-nonce Salsa20 variant used in NaCl [11]. 156 HChaCha20 is initialized the same way as the ChaCha cipher, except 157 that HChaCha20 uses a 128-bit nonce and has no counter. 159 Consider the two figures below, where each non-whitespace character 160 represents one nibble of information about the ChaCha states (all 161 numbers little-endian): 163 cccccccc cccccccc cccccccc cccccccc 164 kkkkkkkk kkkkkkkk kkkkkkkk kkkkkkkk 165 kkkkkkkk kkkkkkkk kkkkkkkk kkkkkkkk 166 bbbbbbbb nnnnnnnn nnnnnnnn nnnnnnnn 168 ChaCha20 State: c=constant k=key b=blockcount n=nonce 170 cccccccc cccccccc cccccccc cccccccc 171 kkkkkkkk kkkkkkkk kkkkkkkk kkkkkkkk 172 kkkkkkkk kkkkkkkk kkkkkkkk kkkkkkkk 173 nnnnnnnn nnnnnnnn nnnnnnnn nnnnnnnn 175 HChaCha20 State: c=constant k=key n=nonce 177 After initialization, proceed through the ChaCha rounds as usual. 179 Once the 20 ChaCha rounds have been completed, the first 128 bits and 180 last 128 bits of the ChaCha state (both little-endian) are 181 concatenated, and this 256-bit subkey is returned. 183 2.2.1. Test Vector for the HChaCha20 Block Function 185 o Key = 00:01:02:03:04:05:06:07:08:09:0a:0b:0c:0d:0e:0f:10:11:12:13: 186 14:15:16:17:18:19:1a:1b:1c:1d:1e:1f. The key is a sequence of 187 octets with no particular structure before we copy it into the 188 HChaCha state. 190 o Nonce = (00:00:00:09:00:00:00:4a:00:00:00:00:31:41:59:27) 191 After setting up the HChaCha state, it looks like this: 193 61707865 3320646e 79622d32 6b206574 194 03020100 07060504 0b0a0908 0f0e0d0c 195 13121110 17161514 1b1a1918 1f1e1d1c 196 09000000 4a000000 00000000 27594131 198 ChaCha state with the key setup. 200 After running 20 rounds (10 column rounds interleaved with 10 201 "diagonal rounds"), the HChaCha state looks like this: 203 82413b42 27b27bfe d30e4250 8a877d73 204 4864a70a f3cd5479 37cd6a84 ad583c7b 205 8355e377 127ce783 2d6a07e0 e5d06cbc 206 a0f9e4d5 8a74a853 c12ec413 26d3ecdc 208 HChaCha state after 20 rounds 210 HChaCha20 will then return only the first and last rows, resulting in 211 the following 256-bit key: 213 82413b4 227b27bfe d30e4250 8a877d73 214 a0f9e4d 58a74a853 c12ec413 26d3ecdc 216 Resultant HChaCha20 subkey 218 2.3. XChaCha20 220 XChaCha20 can be constructed from an existing ChaCha20 implementation 221 and HChaCha20. All one needs to do is: 223 1. Pass the key and the first 16 bytes of the 24-byte nonce to 224 HChaCha20 to obtain the subkey. 226 2. Use the subkey and remaining 8 byte nonce with ChaCha20 as normal 227 (prefixed by 4 NUL bytes, since [RFC7539] specifies a 12-byte 228 nonce). 230 XChaCha20 is a stream cipher and offers no integrity guarantees 231 without being combined with a MAC algorithm (e.g. Poly1305). 233 The same HChaCha20 subkey derivation can also be used in the context 234 of an AEAD_ChaCha20_Poly1305 implementation to create 235 AEAD_XChaCha20_Poly1305, as described in Section 2. 237 2.3.1. XChaCha20 Pseudocode 239 xchacha20_encrypt(key, nonce, plaintext): 240 subkey = hchacha20(key, nonce[0:15]) 241 return chacha20_encrypt(subkey, nonce[16:23], plaintext) 243 3. References 245 3.1. Normative References 247 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 248 Requirement Levels", BCP 14, RFC 2119, 249 DOI 10.17487/RFC2119, March 1997, 250 . 252 [RFC5297] Harkins, D., "Synthetic Initialization Vector (SIV) 253 Authenticated Encryption Using the Advanced Encryption 254 Standard (AES)", RFC 5297, DOI 10.17487/RFC5297, October 255 2008, . 257 [RFC7539] Nir, Y. and A. Langley, "ChaCha20 and Poly1305 for IETF 258 Protocols", RFC 7539, DOI 10.17487/RFC7539, May 2015, 259 . 261 3.2. URIs 263 [1] https://cryptologie.net/article/361/breaking-https-aes-gcm-or-a- 264 part-of-it/ 266 [2] https://eprint.iacr.org/2017/168.pdf 268 [3] https://competitions.cr.yp.to/caesar-submissions.html 270 [4] https://www.wireguard.com 272 [5] https://download.libsodium.org/doc/secret-key_cryptography/ 273 xchacha20-poly1305_construction.html 275 [6] https://github.com/LoupVaillant/Monocypher 277 [7] https://github.com/jedisct1/xsecretbox 279 [8] https://godoc.org/golang.org/x/crypto/chacha20poly1305#NewX 281 [9] https://github.com/google/hpolyc 283 [10] https://cr.yp.to/snuffle/xsalsa-20110204.pdf 285 [11] https://nacl.cr.yp.to 287 Appendix A. Additional Test Vectors 289 A.1. Example and Test Vector for AEAD_XCHACHA20_POLY1305 291 Plaintext: 293 000 4c 61 64 69 65 73 20 61 6e 64 20 47 65 6e 74 6c Ladies and Gentl 294 016 65 6d 65 6e 20 6f 66 20 74 68 65 20 63 6c 61 73 emen of the clas 295 032 73 20 6f 66 20 27 39 39 3a 20 49 66 20 49 20 63 s of '99: If I c 296 048 6f 75 6c 64 20 6f 66 66 65 72 20 79 6f 75 20 6f ould offer you o 297 064 6e 6c 79 20 6f 6e 65 20 74 69 70 20 66 6f 72 20 nly one tip for 298 080 74 68 65 20 66 75 74 75 72 65 2c 20 73 75 6e 73 the future, suns 299 096 63 72 65 65 6e 20 77 6f 75 6c 64 20 62 65 20 69 creen would be i 300 112 74 2e t. 302 AAD: 304 000 50 51 52 53 c0 c1 c2 c3 c4 c5 c6 c7 PQRS........ 306 Key: 308 000 80 81 82 83 84 85 86 87 88 89 8a 8b 8c 8d 8e 8f ................ 309 016 90 91 92 93 94 95 96 97 98 99 9a 9b 9c 9d 9e 9f ................ 311 IV: 313 000 40 41 42 43 44 45 46 47 48 49 4a fb 4c 4d 4e 4f @ABCDEFGHIJKLMNO 314 016 50 51 52 53 54 55 56 57 PQRSTUVW 316 32-bit fixed-common part: 318 000 00 00 00 00 .... 320 Poly1305 Key: 322 000 7b 19 1f 80 f3 61 f0 99 09 4f 6f 4b 8f b9 7d f8 {....a...OoK..}. 323 016 47 cc 68 73 a8 f2 b1 90 dd 73 80 71 83 f9 07 d5 G.hs.....s.q.... 325 Ciphertext: 327 000 bd 6d 17 9d 3e 83 d4 3b 95 76 57 94 93 c0 e9 39 .m..>..;.vW....9 328 016 57 2a 17 00 25 2b fa cc be d2 90 2c 21 39 6c bb W*..%+.....,!9l. 329 032 73 1c 7f 1b 0b 4a a6 44 0b f3 a8 2f 4e da 7e 39 s....J.D.../N.~9 330 048 ae 64 c6 70 8c 54 c2 16 cb 96 b7 2e 12 13 b4 52 .d.p.T.........R 331 064 2f 8c 9b a4 0d b5 d9 45 b1 1b 69 b9 82 c1 bb 9e /......E..i..... 332 080 3f 3f ac 2b c3 69 48 8f 76 b2 38 35 65 d3 ff f9 ??.+.iH.v.85e... 333 096 21 f9 66 4c 97 63 7d a9 76 88 12 f6 15 c6 8b 13 !.fL.c}.v....... 334 112 b5 2e .. 336 Tag: 337 c0:87:59:24:c1:c7:98:79:47:de:af:d8:78:0a:cf:49 339 Author's Address 341 Scott Arciszewski 342 Paragon Initiative Enterprises 343 United States 345 Email: security@paragonie.com