idnits 2.17.00 (12 Aug 2021) /tmp/idnits22408/draft-nir-cfrg-chacha20-poly1305-02.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 : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Line 217 has weird spacing: '...db886dc c9a62...' == Line 267 has weird spacing: '...ccccccc ccccc...' == Line 268 has weird spacing: '...kkkkkkk kkkkk...' == Line 269 has weird spacing: '...kkkkkkk kkkkk...' == Line 270 has weird spacing: '...bbbbbbb nnnnn...' == (4 more instances...) == The document seems to use 'NOT RECOMMENDED' as an RFC 2119 keyword, but does not include the phrase in its RFC 2119 key words list. -- The document date (April 3, 2014) is 2969 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '3' on line 475 -- Looks like a reference, but probably isn't: '7' on line 476 -- Looks like a reference, but probably isn't: '11' on line 477 -- Looks like a reference, but probably isn't: '15' on line 478 -- Looks like a reference, but probably isn't: '4' on line 479 -- Looks like a reference, but probably isn't: '8' on line 480 -- Looks like a reference, but probably isn't: '12' on line 481 -- Looks like a reference, but probably isn't: '16' on line 473 Summary: 0 errors (**), 0 flaws (~~), 8 warnings (==), 10 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group Y. Nir 3 Internet-Draft Check Point 4 Intended status: Informational A. Langley 5 Expires: October 5, 2014 Google Inc 6 April 3, 2014 8 ChaCha20 and Poly1305 for IETF protocols 9 draft-nir-cfrg-chacha20-poly1305-02 11 Abstract 13 This document defines the ChaCha20 stream cipher, as well as the use 14 of the Poly1305 authenticator, both as stand-alone algorithms, and as 15 a "combined mode", or Authenticated Encryption with Additional Data 16 (AEAD) algorithm. 18 This document does not introduce any new crypto, but is meant to 19 serve as a stable reference and an implementation guide. 21 Status of this Memo 23 This Internet-Draft is submitted in full conformance with the 24 provisions of BCP 78 and BCP 79. 26 Internet-Drafts are working documents of the Internet Engineering 27 Task Force (IETF). Note that other groups may also distribute 28 working documents as Internet-Drafts. The list of current Internet- 29 Drafts is at http://datatracker.ietf.org/drafts/current/. 31 Internet-Drafts are draft documents valid for a maximum of six months 32 and may be updated, replaced, or obsoleted by other documents at any 33 time. It is inappropriate to use Internet-Drafts as reference 34 material or to cite them other than as "work in progress." 36 This Internet-Draft will expire on October 5, 2014. 38 Copyright Notice 40 Copyright (c) 2014 IETF Trust and the persons identified as the 41 document authors. All rights reserved. 43 This document is subject to BCP 78 and the IETF Trust's Legal 44 Provisions Relating to IETF Documents 45 (http://trustee.ietf.org/license-info) in effect on the date of 46 publication of this document. Please review these documents 47 carefully, as they describe your rights and restrictions with respect 48 to this document. 50 Table of Contents 52 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 53 1.1. Conventions Used in This Document . . . . . . . . . . . . 3 54 2. The Algorithms . . . . . . . . . . . . . . . . . . . . . . . . 4 55 2.1. The ChaCha Quarter Round . . . . . . . . . . . . . . . . . 4 56 2.1.1. Test Vector for the ChaCha Quarter Round . . . . . . . 4 57 2.2. A Quarter Round on the ChaCha State . . . . . . . . . . . 5 58 2.2.1. Test Vector for the Quarter Round on the ChaCha 59 state . . . . . . . . . . . . . . . . . . . . . . . . 5 60 2.3. The ChaCha20 block Function . . . . . . . . . . . . . . . 6 61 2.3.1. Test Vector for the ChaCha20 Block Function . . . . . 7 62 2.4. The ChaCha20 encryption algorithm . . . . . . . . . . . . 8 63 2.4.1. Example and Test Vector for the ChaCha20 Cipher . . . 9 64 2.5. The Poly1305 algorithm . . . . . . . . . . . . . . . . . . 10 65 2.5.1. Poly1305 Example and Test Vector . . . . . . . . . . . 12 66 2.6. Generating the Poly1305 key using ChaCha20 . . . . . . . . 13 67 2.6.1. Poly1305 Key Generation Test Vector . . . . . . . . . 14 68 2.7. AEAD Construction . . . . . . . . . . . . . . . . . . . . 15 69 2.7.1. Example and Test Vector for AEAD_CHACHA20-POLY1305 . . 16 70 3. Implementation Advice . . . . . . . . . . . . . . . . . . . . 18 71 4. Security Considerations . . . . . . . . . . . . . . . . . . . 19 72 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20 73 6. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 20 74 7. References . . . . . . . . . . . . . . . . . . . . . . . . . . 20 75 7.1. Normative References . . . . . . . . . . . . . . . . . . . 20 76 7.2. Informative References . . . . . . . . . . . . . . . . . . 20 77 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 21 79 1. Introduction 81 The Advanced Encryption Standard (AES - [FIPS-197]) has become the 82 gold standard in encryption. Its efficient design, wide 83 implementation, and hardware support allow for high performance in 84 many areas. On most modern platforms, AES is anywhere from 4x to 10x 85 as fast as the previous most-used cipher, 3-key Data Encryption 86 Standard (3DES - [FIPS-46]), which makes it not only the best choice, 87 but the only choice. 89 The problem is that if future advances in cryptanalysis reveal a 90 weakness in AES, users will be in an unenviable position. With the 91 only other widely supported cipher being the much slower 3DES, it is 92 not feasible to re-configure implementations to use 3DES. 93 [standby-cipher] describes this issue and the need for a standby 94 cipher in greater detail. 96 This document defines such a standby cipher. We use ChaCha20 97 ([chacha]) with or without the Poly1305 ([poly1305]) authenticator. 98 These algorithms are not just fast and secure. They are fast even if 99 software-only C-language implementations, allowing for much quicker 100 deployment when compared with algorithms such as AES that are 101 significantly accelerated by hardware implementations. 103 These document does not introduce these new algorithms. They have 104 been defined in scientific papers by D. J. Bernstein, which are 105 referenced by this document. The purpose of this document is to 106 serve as a stable reference for IETF documents making use of these 107 algorithms. 109 1.1. Conventions Used in This Document 111 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 112 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 113 document are to be interpreted as described in [RFC2119]. 115 The description of the ChaCha algorithm will at various time refer to 116 the ChaCha state as a "vector" or as a "matrix". This follows the 117 use of these terms in DJB's paper. The matrix notation is more 118 visually convenient, and gives a better notion as to why some rounds 119 are called "column rounds" while others are called "diagonal rounds". 120 Here's a diagram of how to martices relate to vectors (using the C 121 language convention of zero being the index origin). 123 0 1 2 3 124 4 5 6 7 125 8 9 10 11 126 12 13 14 15 128 The elements in this vector or matrix are 32-bit unsigned integers. 130 The algorithm name is "ChaCha". "ChaCha20" is a specific instance 131 where 20 "rounds" (or 80 quarter rounds - see Section 2.1) are used. 132 Other variations are defined, with 8 or 12 rounds, but in this 133 document we only describe the 20-round ChaCha, so the names "ChaCha" 134 and "ChaCha20" will be used interchangeably. 136 2. The Algorithms 138 The subsections below describe the algorithms used and the AEAD 139 construction. 141 2.1. The ChaCha Quarter Round 143 The basic operation of the ChaCha algorithm is the quarter round. It 144 operates on four 32-bit unsigned integers, denoted a, b, c, and d. 145 The operation is as follows (in C-like notation): 146 o a += b; d ^= a; d <<<= 16; 147 o c += d; b ^= c; b <<<= 12; 148 o a += b; d ^= a; d <<<= 8; 149 o c += d; b ^= c; b <<<= 7; 150 Where "+" denotes integer addition without carry, "^" denotes a 151 bitwise XOR, and "<<< n" denotes an n-bit left rotation (towards the 152 high bits). 154 For example, let's see the add, XOR and roll operations from the 155 first line with sample numbers: 156 o b = 0x01020304 157 o a = 0x11111111 158 o d = 0x01234567 159 o a = a + b = 0x11111111 + 0x01020304 = 0x12131415 160 o d = d ^ a = 0x01234567 ^ 0x12131415 = 0x13305172 161 o d = d<<<16 = 0x51721330 163 2.1.1. Test Vector for the ChaCha Quarter Round 165 For a test vector, we will use the same numbers as in the example, 166 adding something random for c. 167 o a = 0x11111111 168 o b = 0x01020304 169 o c = 0x9b8d6f43 170 o d = 0x01234567 172 After running a Quarter Round on these 4 numbers, we get these: 174 o a = 0xea2a92f4 175 o b = 0xcb1cf8ce 176 o c = 0x4581472e 177 o d = 0x5881c4bb 179 2.2. A Quarter Round on the ChaCha State 181 The ChaCha state does not have 4 integer numbers, but 16. So the 182 quarter round operation works on only 4 of them - hence the name. 183 Each quarter round operates on 4 pre-determined numbers in the ChaCha 184 state. We will denote by QUATERROUND(x,y,z,w) a quarter-round 185 operation on the numbers at indexes x, y, z, and w of the ChaCha 186 state when viewed as a vector. For example, if we apply 187 QUARTERROUND(1,5,9,13) to a state, this means running the quarter 188 round operation on the elements marked with an asterisk, while 189 leaving the others alone: 191 0 *a 2 3 192 4 *b 6 7 193 8 *c 10 11 194 12 *d 14 15 196 Note that this run of quarter round is part of what is called a 197 "column round". 199 2.2.1. Test Vector for the Quarter Round on the ChaCha state 201 For a test vector, we will use a ChaCha state that was generated 202 randomly: 204 Sample ChaCha State 206 879531e0 c5ecf37d 516461b1 c9a62f8a 207 44c20ef3 3390af7f d9fc690b 2a5f714c 208 53372767 b00a5631 974c541a 359e9963 209 5c971061 3d631689 2098d9d6 91dbd320 211 We will apply the QUARTERROUND(2,7,8,13) operation to this state. 212 For obvious reasons, this one is part of what is called a "diagonal 213 round": 215 After applying QUARTERROUND(2,7,8,13) 217 879531e0 c5ecf37d bdb886dc c9a62f8a 218 44c20ef3 3390af7f d9fc690b cfacafd2 219 e46bea80 b00a5631 974c541a 359e9963 220 5c971061 ccc07c79 2098d9d6 91dbd320 222 Note that only the numbers in positions 2, 7, 8, and 13 changed. 224 2.3. The ChaCha20 block Function 226 The ChaCha block function transforms a ChaCha state by running 227 multiple quarter rounds. 229 The inputs to ChaCha20 are: 230 o A 256-bit key, treated as a concatenation of 8 32-bit little- 231 endian integers. 232 o A 96-bit nonce, treated as a concatenation of 3 32-bit little- 233 endian integers. 234 o A 32-bit block count parameter, treated as a 32-bit little-endian 235 integer. 237 The output is 64 random-looking bytes. 239 The ChaCha algorithm described here uses a 256-bit key. The original 240 algorithm also specified 128-bit keys and 8- and 12-round variants, 241 but these are out of scope for this document. In this section we 242 describe the ChaCha block function. 244 Note also that the original ChaCha had a 64-bit nonce and 64-bit 245 block count. We have modified this here to be more consistent with 246 recommendations in section 3.2 of [RFC5116]. This limits the use of 247 a single (key,nonce) combination to 2^32 blocks, or 256 GB, but that 248 is enough for most uses. In cases where a single key is used by 249 multiple senders, it is important to make sure that they don't use 250 the same nonces. This can be assured by partitioning the nonce space 251 so that the first 32 bits are unique per sender, while the other 64 252 bits come from a counter. 254 The ChaCha20 as follows: 255 o The first 4 words (0-3) are constants: 0x61707865, 0x3320646e, 256 0x79622d32, 0x6b206574. 257 o The next 8 words (4-11) are taken from the 256-bit key by reading 258 the bytes in little-endian order, in 4-byte chunks. 259 o Word 12 is a block counter. Since each block is 64-byte, a 32-bit 260 word is enough for 256 Gigabytes of data. 262 o Words 13-15 are a nonce, which should not be repeated for the same 263 key. The 13th word is the first 32 bits of the input nonce taken 264 as a little-endian integer, while the 15th word is the last 32 265 bits. 267 cccccccc cccccccc cccccccc cccccccc 268 kkkkkkkk kkkkkkkk kkkkkkkk kkkkkkkk 269 kkkkkkkk kkkkkkkk kkkkkkkk kkkkkkkk 270 bbbbbbbb nnnnnnnn nnnnnnnn nnnnnnnn 272 c=constant k=key b=blockcount n=nonce 274 ChaCha20 runs 20 rounds, alternating between "column" and "diagonal" 275 rounds. Each round is 4 quarter-rounds, and they are run as follows. 276 Rounds 1-4 are part of the "column" round, while 5-8 are part of the 277 "diagonal" round: 278 1. QUARTERROUND ( 0, 4, 8,12) 279 2. QUARTERROUND ( 1, 5, 9,13) 280 3. QUARTERROUND ( 2, 6,10,14) 281 4. QUARTERROUND ( 3, 7,11,15) 282 5. QUARTERROUND ( 0, 5,10,15) 283 6. QUARTERROUND ( 1, 6,11,12) 284 7. QUARTERROUND ( 2, 7, 8,13) 285 8. QUARTERROUND ( 3, 4, 9,14) 287 At the end of 20 rounds, the original input words are added to the 288 output words, and the result is serialized by sequencing the words 289 one-by-one in little-endian order. 291 2.3.1. Test Vector for the ChaCha20 Block Function 293 For a test vector, we will use the following inputs to the ChaCha20 294 block function: 295 o Key = 00:01:02:03:04:05:06:07:08:09:0a:0b:0c:0d:0e:0f:10:11:12:13: 296 14:15:16:17:18:19:1a:1b:1c:1d:1e:1f. The key is a sequence of 297 octets with no particular structure before we copy it into the 298 ChaCha state. 299 o Nonce = (00:00:00:09:00:00:00:4a:00:00:00:00) 300 o Block Count = 1. 302 After setting up the ChaCha state, it looks like this: 304 ChaCha State with the key set up. 306 61707865 3320646e 79622d32 6b206574 307 03020100 07060504 0b0a0908 0f0e0d0c 308 13121110 17161514 1b1a1918 1f1e1d1c 309 00000001 09000000 4a000000 00000000 311 After running 20 rounds (10 column rounds interleaved with 10 312 diagonal rounds), the ChaCha state looks like this: 314 ChaCha State after 20 rounds 316 837778ab e238d763 a67ae21e 5950bb2f 317 c4f2d0c7 fc62bb2f 8fa018fc 3f5ec7b7 318 335271c2 f29489f3 eabda8fc 82e46ebd 319 d19c12b4 b04e16de 9e83d0cb 4e3c50a2 321 Finally we add the original state to the result (simple vector or 322 matrix addition), giving this: 324 ChaCha State at the end of the ChaCha20 operation 326 e4e7f110 15593bd1 1fdd0f50 c47120a3 327 c7f4d1c7 0368c033 9aaa2204 4e6cd4c3 328 466482d2 09aa9f07 05d7c214 a2028bd9 329 d19c12b5 b94e16de e883d0cb 4e3c50a2 331 2.4. The ChaCha20 encryption algorithm 333 ChaCha20 is a stream cipher designed by D. J. Bernstein. It is a 334 refinement of the Salsa20 algorithm, and uses a 256-bit key. 336 ChaCha20 successively calls the ChaCha20 block function, with the 337 same key and nonce, and with successively increasing block counter 338 parameters. The resulting state is then serialized by writing the 339 numbers in little-endian order. Concatenating the results from the 340 successive blocks forms a key stream, which is then XOR-ed with the 341 plaintext. There is no requirement for the plaintext to be an 342 integral multiple of 512-bits. If there is extra keystream from the 343 last block, it is discarded. Specific protocols MAY require that the 344 plaintext and ciphertext have certain length. Such protocols need to 345 specify how the plaintext is padded, and how much padding it 346 receives. 348 The inputs to ChaCha20 are: 349 o A 256-bit key 350 o A 32-bit initial counter. This can be set to any number, but will 351 usually be zero or one. It makes sense to use 1 if we use the 352 zero block for something else, such as generating a one-time 353 authenticator key as part of an AEAD algorithm. 354 o A 96-bit nonce. In some protocols, this is known as the 355 Initialization Vector. 356 o an arbitrary-length plaintext 358 The output is an encrypted message of the same length. 360 2.4.1. Example and Test Vector for the ChaCha20 Cipher 362 For a test vector, we will use the following inputs to the ChaCha20 363 block function: 364 o Key = 00:01:02:03:04:05:06:07:08:09:0a:0b:0c:0d:0e:0f:10:11:12:13: 365 14:15:16:17:18:19:1a:1b:1c:1d:1e:1f. 366 o Nonce = (00:00:00:00:00:00:00:4a:00:00:00:00). 367 o Initial Counter = 1. 369 We use the following for the plaintext. It was chosen to be long 370 enough to require more than one block, but not so long that it would 371 make this example cumbersome (so, less than 3 blocks): 373 Plaintext Sunscreen: 374 000 4c 61 64 69 65 73 20 61 6e 64 20 47 65 6e 74 6c|Ladies and Gentl 375 016 65 6d 65 6e 20 6f 66 20 74 68 65 20 63 6c 61 73|emen of the clas 376 032 73 20 6f 66 20 27 39 39 3a 20 49 66 20 49 20 63|s of '99: If I c 377 048 6f 75 6c 64 20 6f 66 66 65 72 20 79 6f 75 20 6f|ould offer you o 378 064 6e 6c 79 20 6f 6e 65 20 74 69 70 20 66 6f 72 20|nly one tip for 379 080 74 68 65 20 66 75 74 75 72 65 2c 20 73 75 6e 73|the future, suns 380 096 63 72 65 65 6e 20 77 6f 75 6c 64 20 62 65 20 69|creen would be i 381 112 74 2e |t. 383 The following figure shows 4 ChaCha state matrices: 384 1. First block as it is set up. 385 2. Second block as it is set up. Note that these blocks are only 386 two bits apart - only the counter in position 12 is different. 387 3. Third block is the first block after the ChaCha20 block 388 operation. 389 4. Final block is the second block after the ChaCha20 block 390 operation was applied. 391 After that, we show the keystream. 393 First block setup: 394 61707865 3320646e 79622d32 6b206574 395 03020100 07060504 0b0a0908 0f0e0d0c 396 13121110 17161514 1b1a1918 1f1e1d1c 397 00000001 00000000 4a000000 00000000 399 Second block setup: 400 61707865 3320646e 79622d32 6b206574 401 03020100 07060504 0b0a0908 0f0e0d0c 402 13121110 17161514 1b1a1918 1f1e1d1c 403 00000002 00000000 4a000000 00000000 405 First block after block operation: 406 f3514f22 e1d91b40 6f27de2f ed1d63b8 407 821f138c e2062c3d ecca4f7e 78cff39e 408 a30a3b8a 920a6072 cd7479b5 34932bed 409 40ba4c79 cd343ec6 4c2c21ea b7417df0 411 Second block after block operation: 412 9f74a669 410f633f 28feca22 7ec44dec 413 6d34d426 738cb970 3ac5e9f3 45590cc4 414 da6e8b39 892c831a cdea67c1 2b7e1d90 415 037463f3 a11a2073 e8bcfb88 edc49139 417 Keystream: 418 22:4f:51:f3:40:1b:d9:e1:2f:de:27:6f:b8:63:1d:ed:8c:13:1f:82:3d:2c:06 419 e2:7e:4f:ca:ec:9e:f3:cf:78:8a:3b:0a:a3:72:60:0a:92:b5:79:74:cd:ed:2b 420 93:34:79:4c:ba:40:c6:3e:34:cd:ea:21:2c:4c:f0:7d:41:b7:69:a6:74:9f:3f 421 63:0f:41:22:ca:fe:28:ec:4d:c4:7e:26:d4:34:6d:70:b9:8c:73:f3:e9:c5:3a 422 c4:0c:59:45:39:8b:6e:da:1a:83:2c:89:c1:67:ea:cd:90:1d:7e:2b:f3:63 424 Finally, we XOR the Keystream with the plaintext, yielding the 425 Ciphertext: 427 Ciphertext Sunscreen: 428 000 6e 2e 35 9a 25 68 f9 80 41 ba 07 28 dd 0d 69 81|n.5.%h..A..(..i. 429 016 e9 7e 7a ec 1d 43 60 c2 0a 27 af cc fd 9f ae 0b|.~z..C`..'...... 430 032 f9 1b 65 c5 52 47 33 ab 8f 59 3d ab cd 62 b3 57|..e.RG3..Y=..b.W 431 048 16 39 d6 24 e6 51 52 ab 8f 53 0c 35 9f 08 61 d8|.9.$.QR..S.5..a. 432 064 07 ca 0d bf 50 0d 6a 61 56 a3 8e 08 8a 22 b6 5e|....P.jaV....".^ 433 080 52 bc 51 4d 16 cc f8 06 81 8c e9 1a b7 79 37 36|R.QM.........y76 434 096 5a f9 0b bf 74 a3 5b e6 b4 0b 8e ed f2 78 5e 42|Z...t.[......x^B 435 112 87 4d |.M 437 2.5. The Poly1305 algorithm 439 Poly1305 is a one-time authenticator designed by D. J. Bernstein. 440 Poly1305 takes a 32-byte one-time key and a message and produces a 441 16-byte tag. 443 The original article ([poly1305]) is entitled "The Poly1305-AES 444 message-authentication code", and the MAC function there requires a 445 128-bit AES key, a 128-bit "additional key", and a 128-bit (non- 446 secret) nonce. AES is used there for encrypting the nonce, so as to 447 get a unique (and secret) 128-bit string, but as the paper states, 448 "There is nothing special about AES here. One can replace AES with 449 an arbitrary keyed function from an arbitrary set of nonces to 16- 450 byte strings.". 452 Regardless of how the key is generated, the key is partitioned into 453 two parts, called "r" and "s". The pair (r,s) should be unique, and 454 MUST be unpredictable for each invocation (that is why it was 455 originally obtained by encrypting a nonce), while "r" MAY be 456 constant, but needs to be modified as follows before being used: ("r" 457 is treated as a 16-octet little-endian number): 458 o r[3], r[7], r[11], and r[15] are required to have their top four 459 bits clear (be smaller than 16) 460 o r[4], r[8], and r[12] are required to have their bottom two bits 461 clear (be divisible by 4) 463 The following sample code clamps "r" to be appropriate: 465 /* 466 Adapted from poly1305aes_test_clamp.c version 20050207 467 D. J. Bernstein 468 Public domain. 469 */ 471 #include "poly1305aes_test.h" 473 void poly1305aes_test_clamp(unsigned char r[16]) 474 { 475 r[3] &= 15; 476 r[7] &= 15; 477 r[11] &= 15; 478 r[15] &= 15; 479 r[4] &= 252; 480 r[8] &= 252; 481 r[12] &= 252; 482 } 484 The "s" should be unpredictable, but it is perfectly acceptable to 485 generate both "r" and "s" uniquely each time. Because each of them 486 is 128-bit, pseudo-randomly generating them (see Section 2.6) is also 487 acceptable. 489 The inputs to Poly1305 are: 490 o A 256-bit one-time key 491 o An arbitrary length message 493 The output is a 128-bit tag. 495 First, the "r" value should be clamped. 497 Next, set the constant prime "P" be 2^130-5: 498 3fffffffffffffffffffffffffffffffb. Also set a variable "accumulator" 499 to zero. 501 Next, divide the message into 16-byte blocks. The last one might be 502 shorter: 503 o Read the block as a little-endian number. 504 o Add one bit beyond the number of octets. For a 16-byte block this 505 is equivalent to adding 2^128 to the number. For the shorter 506 block it can be 2^120, 2^112, or any power of two that is evenly 507 divisible by 8, all the way down to 2^8. 508 o If the block is not 17 bytes long (the last block), pad it with 509 zeros. This is meaningless if you're treating it them as numbers. 510 o Add this number to the accumulator. 511 o Multiply by "r" 512 o Set the accumulator to the result modulo p. To summarize: Acc = 513 ((Acc+block)*r) % p. 515 Finally, the value of the secret key "s" is added to the accumulator, 516 and the 128 least significant bits are serialized in little-endian 517 order to form the tag. 519 2.5.1. Poly1305 Example and Test Vector 521 For our example, we will dispense with generating the one-time key 522 using AES, and assume that we got the following keying material: 523 o Key Material: 85:d6:be:78:57:55:6d:33:7f:44:52:fe:42:d5:06:a8:01: 524 03:80:8a:fb:0d:b2:fd:4a:bf:f6:af:41:49:f5:1b 525 o s as an octet string: 01:03:80:8a:fb:0d:b2:fd:4a:bf:f6:af:41:49: 526 f5:1b 527 o s as a 128-bit number: 1bf54941aff6bf4afdb20dfb8a800301 528 o r before clamping: 85:d6:be:78:57:55:6d:33:7f:44:52:fe:42:d5:06:a8 529 o Clamped r as a number: 806d5400e52447c036d555408bed685. 531 For our message, we'll use a short text: 533 Message to be Authenticated: 534 000 43 72 79 70 74 6f 67 72 61 70 68 69 63 20 46 6f|Cryptographic Fo 535 016 72 75 6d 20 52 65 73 65 61 72 63 68 20 47 72 6f|rum Research Gro 536 032 75 70 |up 538 Since Poly1305 works in 16-byte chunks, the 34-byte message divides 539 into 3 blocks. In the following calculation, "Acc" denotes the 540 accumulator and "Block" the current block: 542 Block #1 544 Acc = 00 545 Block = 6f4620636968706172676f7470797243 546 Block with 0x01 byte = 016f4620636968706172676f7470797243 547 Acc + block = 016f4620636968706172676f7470797243 548 (Acc+Block) * r = 549 b83fe991ca66800489155dcd69e8426ba2779453994ac90ed284034da565ecf 550 Acc = ((Acc+Block)*r) % P = 2c88c77849d64ae9147ddeb88e69c83fc 552 Block #2 554 Acc = 2c88c77849d64ae9147ddeb88e69c83fc 555 Block = 6f7247206863726165736552206d7572 556 Block with 0x01 byte = 016f7247206863726165736552206d7572 557 Acc + block = 437febea505c820f2ad5150db0709f96e 558 (Acc+Block) * r = 559 21dcc992d0c659ba4036f65bb7f88562ae59b32c2b3b8f7efc8b00f78e548a26 560 Acc = ((Acc+Block)*r) % P = 2d8adaf23b0337fa7cccfb4ea344b30de 562 Last Block 564 Acc = 2d8adaf23b0337fa7cccfb4ea344b30de 565 Block = 7075 566 Block with 0x01 byte = 017075 567 Acc + block = 2d8adaf23b0337fa7cccfb4ea344ca153 568 (Acc + Block) * r = 569 16d8e08a0f3fe1de4fe4a15486aca7a270a29f1e6c849221e4a6798b8e45321f 570 ((Acc + Block) * r) % P = 28d31b7caff946c77c8844335369d03a7 572 Adding s we get this number, and serialize if to get the tag: 574 Acc + s = 2a927010caf8b2bc2c6365130c11d06a8 576 Tag: a8:06:1d:c1:30:51:36:c6:c2:2b:8b:af:0c:01:27:a9 578 2.6. Generating the Poly1305 key using ChaCha20 580 As said in Section 2.5, it is acceptable to generate the one-time 581 Poly1305 pseudo-randomly. This section proposes such a method. 583 To generate such a key pair (r,s), we will use the ChaCha20 block 584 function described in Section 2.3. This assumes that we have a 256- 585 bit session key for the MAC function, such as SK_ai and SK_ar in 586 IKEv2, the integrity key in ESP and AH, or the client_write_MAC_key 587 and server_write_MAC_key in TLS. Any document that specifies the use 588 of Poly1305 as a MAC algorithm for some protocol must specify that 589 256 bits are allocated for the integrity key. 591 The method is to call the block function with the following 592 parameters: 593 o The 256-bit session integrity key is used as the ChaCha20 key. 594 o The block counter is set to zero. 595 o The protocol will specify a 96-bit or 64-bit nonce. This MUST be 596 unique per invocation with the same key, so it MUST NOT be 597 randomly generated. A counter is a good way to implement this, 598 but other methods, such as an LFSR are also acceptable. ChaCha20 599 as specified here requires a 96-bit nonce. So if the provided 600 nonce is only 64-bit, then the first 32 bits of the nonce will be 601 set to a constant number. This will usually be zero, but for 602 protocols with multiple sender, it may be different for each 603 sender, but should be the same for all invocations of the function 604 with the same key by a particular sender. 606 After running the block function, we have a 512-bit state. We take 607 the first 256 bits or the serialized state, and use those as the one- 608 time Poly1305 key: The first 128 bits are clamped, and form "r", 609 while the next 128 bits become "s". The other 256 bits are 610 discarded. 612 Note that while many protocols have provisions for a nonce for 613 encryption algorithms (often called Initialization Vectors, or IVs), 614 they usually don't have such a provision for the MAC function. In 615 that case the per-invocation nonce will have to come from somewhere 616 else, such as a message counter. 618 2.6.1. Poly1305 Key Generation Test Vector 620 For this example, we'll set: 622 Key: 623 000 80 81 82 83 84 85 86 87 88 89 8a 8b 8c 8d 8e 8f ................ 624 016 90 91 92 93 94 95 96 97 98 99 9a 9b 9c 9d 9e 9f ................ 626 Nonce: 627 000 00 00 00 00 00 01 02 03 04 05 06 07 ............ 629 The ChaCha state set up with key, nonce, and block counter zero: 630 61707865 3320646e 79622d32 6b206574 631 83828180 87868584 8b8a8988 8f8e8d8c 632 93929190 97969594 9b9a9998 9f9e9d9c 633 00000000 00000000 03020100 07060504 635 The ChaCha state after 20 rounds: 636 8ba0d58a cc815f90 27405081 7194b24a 637 37b633a8 a50dfde3 e2b8db08 46a6d1fd 638 7da03782 9183a233 148ad271 b46773d1 639 3cc1875a 8607def1 ca5c3086 7085eb87 641 Output bytes: 642 000 8a d5 a0 8b 90 5f 81 cc 81 50 40 27 4a b2 94 71 ....._...P@'J..q 643 016 a8 33 b6 37 e3 fd 0d a5 08 db b8 e2 fd d1 a6 46 .3.7...........F 645 And that output is also the 32-byte one-time key used for Poly1305. 647 2.7. AEAD Construction 649 Note: Much of the content of this document, including this AEAD 650 construction is taken from Adam Langley's draft ([agl-draft]) for the 651 use of these algorithms in TLS. The AEAD construction described here 652 is called AEAD_CHACHA20-POLY1305. 654 AEAD_CHACHA20-POLY1305 is an authenticated encryption with additional 655 data algorithm. The inputs to AEAD_CHACHA20-POLY1305 are: 656 o A 256-bit key 657 o A 96-bit nonce - different for each invocation with the same key. 658 o An arbitrary length plaintext 659 o Arbitrary length additional data 661 The ChaCha20 and Poly1305 primitives are combined into an AEAD that 662 takes a 256-bit key and 64-bit IV as follows: 663 o First the 96-bit nonce is constructed by prepending a 32-bit 664 constant value to the IV. This could be set to zero, or could be 665 derived from keying material, or could be assigned to a sender. 666 It is up to the specific protocol to define the source for that 667 32-bit value. 668 o Next, a Poly1305 one-time key is generated from the 256-bit key 669 and nonce using the procedure described in Section 2.6. 670 o The ChaCha20 encryption function is called to encrypt the 671 plaintext, using the same key and nonce, and with the initial 672 counter set to 1. 673 o The Poly1305 function is called with the Poly1305 key calculated 674 above, and a message constructed as a concatenation of the 675 following: 676 * The additional data 677 * The length of the additional data in octets (as a 64-bit 678 little-endian integer). TBD: bit count rather than octets? 679 network order? 681 * The ciphertext 682 * The length of the ciphertext in octets (as a 64-bit little- 683 endian integer). TBD: bit count rather than octets? network 684 order? 686 Decryption is pretty much the same thing. 688 The output from the AEAD is twofold: 689 o A ciphertext of the same length as the plaintext. 690 o A 128-bit tag, which is the output of the Poly1305 function. 692 A few notes about this design: 693 1. The amount of encrypted data possible in a single invocation is 694 2^32-1 blocks of 64 bytes each, for a total of 247,877,906,880 695 bytes, or nearly 256 GB. This should be enough for traffic 696 protocols such as IPsec and TLS, but may be too small for file 697 and/or disk encryption. For such uses, we can return to the 698 original design, reduce the nonce to 64 bits, and use the integer 699 at position 13 as the top 32 bits of a 64-bit block counter, 700 increasing the total message size to over a million petabytes 701 (1,180,591,620,717,411,303,360 bytes to be exact). 702 2. Despite the previous item, the ciphertext length field in the 703 construction of the buffer on which Poly1305 runs limits the 704 ciphertext (and hence, the plaintext) size to 2^64 bytes, or 705 sixteen thousand petabytes (18,446,744,073,709,551,616 bytes to 706 be exact). 708 2.7.1. Example and Test Vector for AEAD_CHACHA20-POLY1305 710 For a test vector, we will use the following inputs to the 711 AEAD_CHACHA20-POLY1305 function: 713 Plaintext: 714 000 4c 61 64 69 65 73 20 61 6e 64 20 47 65 6e 74 6c|Ladies and Gentl 715 016 65 6d 65 6e 20 6f 66 20 74 68 65 20 63 6c 61 73|emen of the clas 716 032 73 20 6f 66 20 27 39 39 3a 20 49 66 20 49 20 63|s of '99: If I c 717 048 6f 75 6c 64 20 6f 66 66 65 72 20 79 6f 75 20 6f|ould offer you o 718 064 6e 6c 79 20 6f 6e 65 20 74 69 70 20 66 6f 72 20|nly one tip for 719 080 74 68 65 20 66 75 74 75 72 65 2c 20 73 75 6e 73|the future, suns 720 096 63 72 65 65 6e 20 77 6f 75 6c 64 20 62 65 20 69|creen would be i 721 112 74 2e |t. 723 AAD: 724 000 50 51 52 53 c0 c1 c2 c3 c4 c5 c6 c7 PQRS........ 726 Key: 727 000 80 81 82 83 84 85 86 87 88 89 8a 8b 8c 8d 8e 8f|................ 728 016 90 91 92 93 94 95 96 97 98 99 9a 9b 9c 9d 9e 9f|................ 730 IV: 731 000 40 41 42 43 44 45 46 47 @ABCDEFG 733 32-bit fixed-common part: 734 000 07 00 00 00 .... 736 Set up for generating poly1305 one-time key (sender id=7): 737 61707865 3320646e 79622d32 6b206574 738 83828180 87868584 8b8a8988 8f8e8d8c 739 93929190 97969594 9b9a9998 9f9e9d9c 740 00000000 00000007 43424140 47464544 742 After generating Poly1305 one-time key: 743 252bac7b af47b42d 557ab609 8455e9a4 744 73d6e10a ebd97510 7875932a ff53d53e 745 decc7ea2 b44ddbad e49c17d1 d8430bc9 746 8c94b7bc 8b7d4b4b 3927f67d 1669a432 748 Poly1305 Key: 749 000 7b ac 2b 25 2d b4 47 af 09 b6 7a 55 a4 e9 55 84|{.+%-.G...zU..U. 750 016 0a e1 d6 73 10 75 d9 eb 2a 93 75 78 3e d5 53 ff|...s.u..*.ux>.S. 752 Poly1305 r = 455e9a4057ab6080f47b42c052bac7b 753 Poly1305 s = ff53d53e7875932aebd9751073d6e10a 755 Keystream bytes: 756 9f:7b:e9:5d:01:fd:40:ba:15:e2:8f:fb:36:81:0a:ae: 757 c1:c0:88:3f:09:01:6e:de:dd:8a:d0:87:55:82:03:a5: 758 4e:9e:cb:38:ac:8e:5e:2b:b8:da:b2:0f:fa:db:52:e8: 759 75:04:b2:6e:be:69:6d:4f:60:a4:85:cf:11:b8:1b:59: 760 fc:b1:c4:5f:42:19:ee:ac:ec:6a:de:c3:4e:66:69:78: 761 8e:db:41:c4:9c:a3:01:e1:27:e0:ac:ab:3b:44:b9:cf: 762 5c:86:bb:95:e0:6b:0d:f2:90:1a:b6:45:e4:ab:e6:22: 763 15:38 764 Ciphertext: 765 000 d3 1a 8d 34 64 8e 60 db 7b 86 af bc 53 ef 7e c2|...4d.`.{...S.~. 766 016 a4 ad ed 51 29 6e 08 fe a9 e2 b5 a7 36 ee 62 d6|...Q)n......6.b. 767 032 3d be a4 5e 8c a9 67 12 82 fa fb 69 da 92 72 8b|=..^..g....i..r. 768 048 1a 71 de 0a 9e 06 0b 29 05 d6 a5 b6 7e cd 3b 36|.q.....)....~.;6 769 064 92 dd bd 7f 2d 77 8b 8c 98 03 ae e3 28 09 1b 58|...-w......(..X 770 080 fa b3 24 e4 fa d6 75 94 55 85 80 8b 48 31 d7 bc|..$...u.U...H1.. 771 096 3f f4 de f0 8e 4b 7a 9d e5 76 d2 65 86 ce c6 4b|?....Kz..v.e...K 772 112 61 16 |a. 774 AEAD Construction for Poly1305: 775 000 50 51 52 53 c0 c1 c2 c3 c4 c5 c6 c7 0c 00 00 00|PQRS............ 776 016 00 00 00 00 d3 1a 8d 34 64 8e 60 db 7b 86 af bc|.......4d.`.{... 777 032 53 ef 7e c2 a4 ad ed 51 29 6e 08 fe a9 e2 b5 a7|S.~....Q)n...... 778 048 36 ee 62 d6 3d be a4 5e 8c a9 67 12 82 fa fb 69|6.b.=..^..g....i 779 064 da 92 72 8b 1a 71 de 0a 9e 06 0b 29 05 d6 a5 b6|..r..q.....).... 780 080 7e cd 3b 36 92 dd bd 7f 2d 77 8b 8c 98 03 ae e3|~.;6...-w...... 781 096 28 09 1b 58 fa b3 24 e4 fa d6 75 94 55 85 80 8b|(..X..$...u.U... 782 112 48 31 d7 bc 3f f4 de f0 8e 4b 7a 9d e5 76 d2 65|H1..?....Kz..v.e 783 128 86 ce c6 4b 61 16 72 00 00 00 00 00 00 00 |...Ka.r....... 785 Tag: 786 18:fb:11:a5:03:1a:d1:3a:7e:3b:03:d4:6e:e3:a6:a7 788 3. Implementation Advice 790 Each block of ChaCha20 involves 16 move operations and one increment 791 operation for loading the state, 80 each of XOR, addition and Roll 792 operations for the rounds, 16 more add operations and 16 XOR 793 operations for protecting the plaintext. Section 2.3 describes the 794 ChaCha block function as "adding the original input words". This 795 implies that before starting the rounds on the ChaCha state, it is 796 copied aside only to be added in later. This would be correct, but 797 it saves a few operations to instead copy the state and do the work 798 on the copy. This way, for the next block you don't need to recreate 799 the state, but only to increment the block counter. This saves 800 approximately 5.5% of the cycles. 802 It is NOT RECOMMENDED to use a generic big number library such as the 803 one in OpenSSL for the arithmetic operations in Poly1305. Such 804 libraries use dynamic allocation to be able to handle any-sized 805 integer, but that flexibility comes at the expense of performance as 806 well as side-channel security. More efficient implementations that 807 run in constant time are available, one of them in DJB's own library, 808 NaCl ([NaCl]). A constant-time but not optimal approach would be to 809 naively implement the arithmetic operations for a 288-bit integers, 810 because even a naive implementation will not exceed 2^288 in the 811 multiplication of (acc+block) and r. An efficient constant-time 812 implementation can be found in the public domain library poly1305- 813 donna ([poly1305_donna]). 815 4. Security Considerations 817 The ChaCha20 cipher is designed to provide 256-bit security. 819 The Poly1305 authenticator is designed to ensure that forged messages 820 are rejected with a probability of 1-(n/(2^102)) for a 16n-byte 821 message, even after sending 2^64 legitimate messages, so it is SUF- 822 CMA in the terminology of [AE]. 824 Proving the security of either of these is beyond the scope of this 825 document. Such proofs are available in the referenced academic 826 papers. 828 The most important security consideration in implementing this draft 829 is the uniqueness of the nonce used in ChaCha20. Counters and LFSRs 830 are both acceptable ways of generating unique nonces, as is 831 encrypting a counter using a 64-bit cipher such as DES. Note that it 832 is not acceptable to use a truncation of a counter encrypted with a 833 128-bit or 256-bit cipher, because such a truncation may repeat after 834 a short time. 836 The Poly1305 key MUST be unpredictable to an attacker. Randomly 837 generating the key would fulfill this requirement, except that 838 Poly1305 is often used in communications protocols, so the receiver 839 should know the key. Pseudo-random number generation such as by 840 encrypting a counter is acceptable. Using ChaCha with a secret key 841 and a nonce is also acceptable. 843 The algorithms presented here were designed to be easy to implement 844 in constant time to avoid side-channel vulnerabilities. The 845 operations used in ChaCha20 are all additions, XORs, and fixed 846 rotations. All of these can and should be implemented in constant 847 time. Access to offsets into the ChaCha state and the number of 848 operations do not depend on any property of the key, eliminating the 849 chance of information about the key leaking through the timing of 850 cache misses. 852 For Poly1305, the operations are addition, multiplication and 853 modulus, all on >128-bit numbers. This can be done in constant time, 854 but a naive implementation (such as using some generic big number 855 library) will not be constant time. For example, if the 856 multiplication is performed as a separate operation from the modulus, 857 the result will some times be under 2^256 and some times be above 858 2^256. Implementers should be careful about timing side-channels for 859 Poly1305 by using the appropriate implementation of these operations. 861 5. IANA Considerations 863 There are no IANA considerations for this document. 865 6. Acknowledgements 867 None of the algorithms here are my own. ChaCha20 and Poly1305 were 868 invented by Daniel J. Bernstein, and the AEAD construction was 869 invented by Adam Langley. 871 Thanks to Robert Ransom and Ilari Liusvaara for their helpful 872 comments and explanations. 874 7. References 876 7.1. Normative References 878 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 879 Requirement Levels", BCP 14, RFC 2119, March 1997. 881 [chacha] Bernstein, D., "ChaCha, a variant of Salsa20", Jan 2008. 883 [poly1305] 884 Bernstein, D., "The Poly1305-AES message-authentication 885 code", Mar 2005. 887 7.2. Informative References 889 [AE] Bellare, M. and C. Namprempre, "Authenticated Encryption: 890 Relations among notions and analysis of the generic 891 composition paradigm", 892 . 894 [FIPS-197] 895 National Institute of Standards and Technology, "Advanced 896 Encryption Standard (AES)", FIPS PUB 197, November 2001. 898 [FIPS-46] National Institute of Standards and Technology, "Data 899 Encryption Standard", FIPS PUB 46-2, December 1993, 900 . 902 [NaCl] Bernstein, D., Lange, T., and P. Schwabe, "NaCl: 903 Networking and Cryptography library", 904 . 906 [RFC5116] McGrew, D., "An Interface and Algorithms for Authenticated 907 Encryption", RFC 5116, January 2008. 909 [agl-draft] 910 Langley, A. and W. Chang, "ChaCha20 and Poly1305 based 911 Cipher Suites for TLS", draft-agl-tls-chacha20poly1305-04 912 (work in progress), November 2013. 914 [poly1305_donna] 915 Floodyberry, A., "Poly1305-donna", 916 . 918 [standby-cipher] 919 McGrew, D., Grieco, A., and Y. Sheffer, "Selection of 920 Future Cryptographic Standards", 921 draft-mcgrew-standby-cipher (work in progress). 923 Authors' Addresses 925 Yoav Nir 926 Check Point Software Technologies Ltd. 927 5 Hasolelim st. 928 Tel Aviv 6789735 929 Israel 931 Email: ynir.ietf@gmail.com 933 Adam Langley 934 Google Inc 936 Email: agl@google.com