idnits 2.17.1 draft-irtf-cfrg-chacha20-poly1305-09.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 259 has weird spacing: '...db886dc c9a62...' == Line 310 has weird spacing: '...ccccccc ccccc...' == Line 311 has weird spacing: '...kkkkkkk kkkkk...' == Line 312 has weird spacing: '...kkkkkkk kkkkk...' == Line 313 has weird spacing: '...bbbbbbb nnnnn...' == (9 more instances...) -- The document date (February 2, 2015) is 3364 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 590 -- Looks like a reference, but probably isn't: '7' on line 591 -- Looks like a reference, but probably isn't: '11' on line 592 -- Looks like a reference, but probably isn't: '15' on line 593 -- Looks like a reference, but probably isn't: '4' on line 594 -- Looks like a reference, but probably isn't: '8' on line 595 -- Looks like a reference, but probably isn't: '12' on line 596 -- Looks like a reference, but probably isn't: '16' on line 588 == Missing Reference: '0x01' is mentioned on line 648, but not defined 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: August 6, 2015 Google Inc 6 February 2, 2015 8 ChaCha20 and Poly1305 for IETF protocols 9 draft-irtf-cfrg-chacha20-poly1305-09 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. It is a 20 product of the Crypto Forum Research Group (CFRG) 22 Status of This Memo 24 This Internet-Draft is submitted in full conformance with the 25 provisions of BCP 78 and BCP 79. 27 Internet-Drafts are working documents of the Internet Engineering 28 Task Force (IETF). Note that other groups may also distribute 29 working documents as Internet-Drafts. The list of current Internet- 30 Drafts is at http://datatracker.ietf.org/drafts/current/. 32 Internet-Drafts are draft documents valid for a maximum of six months 33 and may be updated, replaced, or obsoleted by other documents at any 34 time. It is inappropriate to use Internet-Drafts as reference 35 material or to cite them other than as "work in progress." 37 This Internet-Draft will expire on August 6, 2015. 39 Copyright Notice 41 Copyright (c) 2015 IETF Trust and the persons identified as the 42 document authors. All rights reserved. 44 This document is subject to BCP 78 and the IETF Trust's Legal 45 Provisions Relating to IETF Documents 46 (http://trustee.ietf.org/license-info) in effect on the date of 47 publication of this document. Please review these documents 48 carefully, as they describe your rights and restrictions with respect 49 to this document. 51 Table of Contents 53 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 54 1.1. Conventions Used in This Document . . . . . . . . . . . . 4 55 2. The Algorithms . . . . . . . . . . . . . . . . . . . . . . . 4 56 2.1. The ChaCha Quarter Round . . . . . . . . . . . . . . . . 4 57 2.1.1. Test Vector for the ChaCha Quarter Round . . . . . . 5 58 2.2. A Quarter Round on the ChaCha State . . . . . . . . . . . 5 59 2.2.1. Test Vector for the Quarter Round on the ChaCha state 6 60 2.3. The ChaCha20 block Function . . . . . . . . . . . . . . . 6 61 2.3.1. The ChaCha20 Block Function in Pseudo-Code . . . . . 8 62 2.3.2. Test Vector for the ChaCha20 Block Function . . . . . 8 63 2.4. The ChaCha20 encryption algorithm . . . . . . . . . . . . 9 64 2.4.1. The ChaCha20 encryption algorithm in Pseudo-Code . . 10 65 2.4.2. Example and Test Vector for the ChaCha20 Cipher . . . 10 66 2.5. The Poly1305 algorithm . . . . . . . . . . . . . . . . . 12 67 2.5.1. The Poly1305 Algorithms in Pseudo-Code . . . . . . . 14 68 2.5.2. Poly1305 Example and Test Vector . . . . . . . . . . 14 69 2.6. Generating the Poly1305 key using ChaCha20 . . . . . . . 16 70 2.6.1. Poly1305 Key Generation in Pseudo-Code . . . . . . . 17 71 2.6.2. Poly1305 Key Generation Test Vector . . . . . . . . . 17 72 2.7. A Pseudo-Random Function for ChaCha/Poly-1305 based 73 Crypto Suites . . . . . . . . . . . . . . . . . . . . . . 17 74 2.8. AEAD Construction . . . . . . . . . . . . . . . . . . . . 18 75 2.8.1. Pseudo-Code for the AEAD Construction . . . . . . . . 20 76 2.8.2. Example and Test Vector for AEAD_CHACHA20-POLY1305 . 20 77 3. Implementation Advice . . . . . . . . . . . . . . . . . . . . 22 78 4. Security Considerations . . . . . . . . . . . . . . . . . . . 23 79 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 24 80 6. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 24 81 7. Changes from Previous Versions . . . . . . . . . . . . . . . 25 82 7.1. Changes from version -01 to version -02 . . . . . . . . . 25 83 7.2. Changes from version -00 to version -01 . . . . . . . . . 25 84 7.3. Changes from draft-nir-cfrg to draft-irtf-cfrg . . . . . 25 85 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 25 86 8.1. Normative References . . . . . . . . . . . . . . . . . . 25 87 8.2. Informative References . . . . . . . . . . . . . . . . . 26 88 Appendix A. Additional Test Vectors . . . . . . . . . . . . . . 27 89 A.1. The ChaCha20 Block Functions . . . . . . . . . . . . . . 27 90 A.2. ChaCha20 Encryption . . . . . . . . . . . . . . . . . . . 30 91 A.3. Poly1305 Message Authentication Code . . . . . . . . . . 33 92 A.4. Poly1305 Key Generation Using ChaCha20 . . . . . . . . . 39 93 A.5. ChaCha20-Poly1305 AEAD Decryption . . . . . . . . . . . . 40 94 Appendix B. Performance Measurements of ChaCha20 . . . . . . . . 43 95 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 43 97 1. Introduction 99 The Advanced Encryption Standard (AES - [FIPS-197]) has become the 100 gold standard in encryption. Its efficient design, widespread 101 implementation, and hardware support allow for high performance in 102 many areas. On most modern platforms, AES is anywhere from 4x to 10x 103 as fast as the previous most-used cipher, 3-key Data Encryption 104 Standard (3DES - [SP800-67]), which makes it not only the best 105 choice, but the only practical choice. 107 There are several problems with this. If future advances in 108 cryptanalysis reveal a weakness in AES, users will be in an 109 unenviable position. With the only other widely supported cipher 110 being the much slower 3DES, it is not feasible to re-configure 111 deployments to use 3DES. [Standby-Cipher] describes this issue and 112 the need for a standby cipher in greater detail. Another problem is 113 that while AES is very fast on dedicated hardware, its performance on 114 platforms that lack such hardware is considerably lower. Yet another 115 problem is that many AES implementations are vulnerable to cache- 116 collision timing attacks ([cache-collisions]). 118 This document provides a definition and implementation guide for 119 three algorithms: 121 1. The ChaCha20 cipher. This is a high-speed cipher first described 122 in [ChaCha]. It is considerably faster than AES in software-only 123 implementations, making it around three times as fast on 124 platforms that lack specialized AES hardware. See Appendix B for 125 some hard numbers. ChaCha20 is also not sensitive to timing 126 attacks (see the security considerations in Section 4) This 127 algorithm is described in Section 2.4 128 2. The Poly1305 authenticator. This is a high-speed message 129 authentication code. Implementation is also straight-forward and 130 easy to get right. The algorithm is described in Section 2.5. 131 3. The CHACHA20-POLY1305 Authenticated Encryption with Associated 132 Data (AEAD) construction, described in Section 2.8. 134 This document does not introduce these new algorithms for the first 135 time. They have been defined in scientific papers by D. J. 136 Bernstein, which are referenced by this document. The purpose of 137 this document is to serve as a stable reference for IETF documents 138 making use of these algorithms. 140 These algorithms have undergone rigorous analysis. Several papers 141 discuss the security of Salsa and ChaCha ([LatinDances], 142 [LatinDances2], [Zhenqing2012]). 144 This document represents the consensus of the Crypto Forum Research 145 Group (CFRG). 147 1.1. Conventions Used in This Document 149 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 150 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 151 document are to be interpreted as described in [RFC2119]. 153 The description of the ChaCha algorithm will at various time refer to 154 the ChaCha state as a "vector" or as a "matrix". This follows the 155 use of these terms in Prof. Bernstein's paper. The matrix notation 156 is more visually convenient, and gives a better notion as to why some 157 rounds are called "column rounds" while others are called "diagonal 158 rounds". Here's a diagram of how the matrices relate to vectors 159 (using the C language convention of zero being the index origin). 161 0 1 2 3 162 4 5 6 7 163 8 9 10 11 164 12 13 14 15 166 The elements in this vector or matrix are 32-bit unsigned integers. 168 The algorithm name is "ChaCha". "ChaCha20" is a specific instance 169 where 20 "rounds" (or 80 quarter rounds - see Section 2.1) are used. 170 Other variations are defined, with 8 or 12 rounds, but in this 171 document we only describe the 20-round ChaCha, so the names "ChaCha" 172 and "ChaCha20" will be used interchangeably. 174 2. The Algorithms 176 The subsections below describe the algorithms used and the AEAD 177 construction. 179 2.1. The ChaCha Quarter Round 181 The basic operation of the ChaCha algorithm is the quarter round. It 182 operates on four 32-bit unsigned integers, denoted a, b, c, and d. 183 The operation is as follows (in C-like notation): 185 1. a += b; d ^= a; d <<<= 16; 186 2. c += d; b ^= c; b <<<= 12; 187 3. a += b; d ^= a; d <<<= 8; 188 4. c += d; b ^= c; b <<<= 7; 189 Where "+" denotes integer addition modulo 2^32, "^" denotes a bitwise 190 Exclusive OR (XOR), and "<<< n" denotes an n-bit left rotation 191 (towards the high bits). 193 For example, let's see the add, XOR and roll operations from the 194 fourth line with sample numbers: 196 o a = 0x11111111 197 o b = 0x01020304 198 o c = 0x77777777 199 o d = 0x01234567 200 o c = c + d = 0x77777777 + 0x01234567 = 0x789abcde 201 o b = b ^ c = 0x01020304 ^ 0x789abcde = 0x7998bfda 202 o b = b <<< 7 = 0x7998bfda <<< 7 = 0xcc5fed3c 204 2.1.1. Test Vector for the ChaCha Quarter Round 206 For a test vector, we will use the same numbers as in the example, 207 adding something random for c. 209 o a = 0x11111111 210 o b = 0x01020304 211 o c = 0x9b8d6f43 212 o d = 0x01234567 214 After running a Quarter Round on these 4 numbers, we get these: 216 o a = 0xea2a92f4 217 o b = 0xcb1cf8ce 218 o c = 0x4581472e 219 o d = 0x5881c4bb 221 2.2. A Quarter Round on the ChaCha State 223 The ChaCha state does not have 4 integer numbers, but 16. So the 224 quarter round operation works on only 4 of them - hence the name. 225 Each quarter round operates on 4 pre-determined numbers in the ChaCha 226 state. We will denote by QUARTERROUND(x,y,z,w) a quarter-round 227 operation on the numbers at indexes x, y, z, and w of the ChaCha 228 state when viewed as a vector. For example, if we apply 229 QUARTERROUND(1,5,9,13) to a state, this means running the quarter 230 round operation on the elements marked with an asterisk, while 231 leaving the others alone: 233 0 *a 2 3 234 4 *b 6 7 235 8 *c 10 11 236 12 *d 14 15 238 Note that this run of quarter round is part of what is called a 239 "column round". 241 2.2.1. Test Vector for the Quarter Round on the ChaCha state 243 For a test vector, we will use a ChaCha state that was generated 244 randomly: 246 Sample ChaCha State 248 879531e0 c5ecf37d 516461b1 c9a62f8a 249 44c20ef3 3390af7f d9fc690b 2a5f714c 250 53372767 b00a5631 974c541a 359e9963 251 5c971061 3d631689 2098d9d6 91dbd320 253 We will apply the QUARTERROUND(2,7,8,13) operation to this state. 254 For obvious reasons, this one is part of what is called a "diagonal 255 round": 257 After applying QUARTERROUND(2,7,8,13) 259 879531e0 c5ecf37d *bdb886dc c9a62f8a 260 44c20ef3 3390af7f d9fc690b *cfacafd2 261 *e46bea80 b00a5631 974c541a 359e9963 262 5c971061 *ccc07c79 2098d9d6 91dbd320 264 Note that only the numbers in positions 2, 7, 8, and 13 changed. 266 2.3. The ChaCha20 block Function 268 The ChaCha block function transforms a ChaCha state by running 269 multiple quarter rounds. 271 The inputs to ChaCha20 are: 273 o A 256-bit key, treated as a concatenation of 8 32-bit little- 274 endian integers. 275 o A 96-bit nonce, treated as a concatenation of 3 32-bit little- 276 endian integers. 277 o A 32-bit block count parameter, treated as a 32-bit little-endian 278 integer. 280 The output is 64 random-looking bytes. 282 The ChaCha algorithm described here uses a 256-bit key. The original 283 algorithm also specified 128-bit keys and 8- and 12-round variants, 284 but these are out of scope for this document. In this section we 285 describe the ChaCha block function. 287 Note also that the original ChaCha had a 64-bit nonce and 64-bit 288 block count. We have modified this here to be more consistent with 289 recommendations in section 3.2 of [RFC5116]. This limits the use of 290 a single (key,nonce) combination to 2^32 blocks, or 256 GB, but that 291 is enough for most uses. In cases where a single key is used by 292 multiple senders, it is important to make sure that they don't use 293 the same nonces. This can be assured by partitioning the nonce space 294 so that the first 32 bits are unique per sender, while the other 64 295 bits come from a counter. 297 The ChaCha20 state is initialized as follows: 299 o The first 4 words (0-3) are constants: 0x61707865, 0x3320646e, 300 0x79622d32, 0x6b206574. 301 o The next 8 words (4-11) are taken from the 256-bit key by reading 302 the bytes in little-endian order, in 4-byte chunks. 303 o Word 12 is a block counter. Since each block is 64-byte, a 32-bit 304 word is enough for 256 gigabytes of data. 305 o Words 13-15 are a nonce, which should not be repeated for the same 306 key. The 13th word is the first 32 bits of the input nonce taken 307 as a little-endian integer, while the 15th word is the last 32 308 bits. 310 cccccccc cccccccc cccccccc cccccccc 311 kkkkkkkk kkkkkkkk kkkkkkkk kkkkkkkk 312 kkkkkkkk kkkkkkkk kkkkkkkk kkkkkkkk 313 bbbbbbbb nnnnnnnn nnnnnnnn nnnnnnnn 315 c=constant k=key b=blockcount n=nonce 317 ChaCha20 runs 20 rounds, alternating between "column" and "diagonal" 318 rounds. Each round is 4 quarter-rounds, and they are run as follows. 319 Quarter-rounds 1-4 are part of a "column" round, while 5-8 are part 320 of a "diagonal" round: 322 1. QUARTERROUND ( 0, 4, 8,12) 323 2. QUARTERROUND ( 1, 5, 9,13) 324 3. QUARTERROUND ( 2, 6,10,14) 325 4. QUARTERROUND ( 3, 7,11,15) 326 5. QUARTERROUND ( 0, 5,10,15) 327 6. QUARTERROUND ( 1, 6,11,12) 328 7. QUARTERROUND ( 2, 7, 8,13) 329 8. QUARTERROUND ( 3, 4, 9,14) 331 At the end of 20 rounds (or 10 iterations of the above list), we add 332 the original input words to the output words, and serialize the 333 result by sequencing the words one-by-one in little-endian order. 335 Note: "addition" in the above paragraph is done modulo 2^32. In some 336 machine languages this is called carryless addition on a 32-bit word. 338 2.3.1. The ChaCha20 Block Function in Pseudo-Code 340 Note: This section and a few others contain pseudo-code for the 341 algorithm explained in a previous section. Every effort was made for 342 the pseudo-code to accurately reflect the algorithm as described in 343 the preceding section. If a conflict is still present, the textual 344 explanation and the test vectors are normative. 346 inner_block (state): 347 Qround(state, 0, 4, 8,12) 348 Qround(state, 1, 5, 9,13) 349 Qround(state, 2, 6,10,14) 350 Qround(state, 3, 7,11,15) 351 Qround(state, 0, 5,10,15) 352 Qround(state, 1, 6,11,12) 353 Qround(state, 2, 7, 8,13) 354 Qround(state, 3, 4, 9,14) 355 end 357 chacha20_block(key, counter, nonce): 358 state = constants | key | counter | nonce 359 working_state = state 360 for i=1 upto 10 361 inner_block(working_state) 362 end 363 state += working_state 364 return serialize(state) 365 end 367 2.3.2. Test Vector for the ChaCha20 Block Function 369 For a test vector, we will use the following inputs to the ChaCha20 370 block function: 372 o Key = 00:01:02:03:04:05:06:07:08:09:0a:0b:0c:0d:0e:0f:10:11:12:13: 373 14:15:16:17:18:19:1a:1b:1c:1d:1e:1f. The key is a sequence of 374 octets with no particular structure before we copy it into the 375 ChaCha state. 376 o Nonce = (00:00:00:09:00:00:00:4a:00:00:00:00) 377 o Block Count = 1. 379 After setting up the ChaCha state, it looks like this: 381 ChaCha State with the key set up. 383 61707865 3320646e 79622d32 6b206574 384 03020100 07060504 0b0a0908 0f0e0d0c 385 13121110 17161514 1b1a1918 1f1e1d1c 386 00000001 09000000 4a000000 00000000 388 After running 20 rounds (10 column rounds interleaved with 10 389 diagonal rounds), the ChaCha state looks like this: 391 ChaCha State after 20 rounds 393 837778ab e238d763 a67ae21e 5950bb2f 394 c4f2d0c7 fc62bb2f 8fa018fc 3f5ec7b7 395 335271c2 f29489f3 eabda8fc 82e46ebd 396 d19c12b4 b04e16de 9e83d0cb 4e3c50a2 398 Finally we add the original state to the result (simple vector or 399 matrix addition), giving this: 401 ChaCha State at the end of the ChaCha20 operation 403 e4e7f110 15593bd1 1fdd0f50 c47120a3 404 c7f4d1c7 0368c033 9aaa2204 4e6cd4c3 405 466482d2 09aa9f07 05d7c214 a2028bd9 406 d19c12b5 b94e16de e883d0cb 4e3c50a2 408 After we serialize the state, we get this: 410 Serialized Block: 411 000 10 f1 e7 e4 d1 3b 59 15 50 0f dd 1f a3 20 71 c4 .....;Y.P.... q. 412 016 c7 d1 f4 c7 33 c0 68 03 04 22 aa 9a c3 d4 6c 4e ....3.h.."....lN 413 032 d2 82 64 46 07 9f aa 09 14 c2 d7 05 d9 8b 02 a2 ..dF............ 414 048 b5 12 9c d1 de 16 4e b9 cb d0 83 e8 a2 50 3c 4e ......N......P.S. 982 Poly1305 r = 455e9a4057ab6080f47b42c052bac7b 983 Poly1305 s = ff53d53e7875932aebd9751073d6e10a 984 Keystream bytes: 985 9f:7b:e9:5d:01:fd:40:ba:15:e2:8f:fb:36:81:0a:ae: 986 c1:c0:88:3f:09:01:6e:de:dd:8a:d0:87:55:82:03:a5: 987 4e:9e:cb:38:ac:8e:5e:2b:b8:da:b2:0f:fa:db:52:e8: 988 75:04:b2:6e:be:69:6d:4f:60:a4:85:cf:11:b8:1b:59: 989 fc:b1:c4:5f:42:19:ee:ac:ec:6a:de:c3:4e:66:69:78: 990 8e:db:41:c4:9c:a3:01:e1:27:e0:ac:ab:3b:44:b9:cf: 991 5c:86:bb:95:e0:6b:0d:f2:90:1a:b6:45:e4:ab:e6:22: 992 15:38 994 Ciphertext: 995 000 d3 1a 8d 34 64 8e 60 db 7b 86 af bc 53 ef 7e c2 ...4d.`.{...S.~. 996 016 a4 ad ed 51 29 6e 08 fe a9 e2 b5 a7 36 ee 62 d6 ...Q)n......6.b. 997 032 3d be a4 5e 8c a9 67 12 82 fa fb 69 da 92 72 8b =..^..g....i..r. 998 048 1a 71 de 0a 9e 06 0b 29 05 d6 a5 b6 7e cd 3b 36 .q.....)....~.;6 999 064 92 dd bd 7f 2d 77 8b 8c 98 03 ae e3 28 09 1b 58 ....-w......(..X 1000 080 fa b3 24 e4 fa d6 75 94 55 85 80 8b 48 31 d7 bc ..$...u.U...H1.. 1001 096 3f f4 de f0 8e 4b 7a 9d e5 76 d2 65 86 ce c6 4b ?....Kz..v.e...K 1002 112 61 16 a. 1004 AEAD Construction for Poly1305: 1005 000 50 51 52 53 c0 c1 c2 c3 c4 c5 c6 c7 00 00 00 00 PQRS............ 1006 016 d3 1a 8d 34 64 8e 60 db 7b 86 af bc 53 ef 7e c2 ...4d.`.{...S.~. 1007 032 a4 ad ed 51 29 6e 08 fe a9 e2 b5 a7 36 ee 62 d6 ...Q)n......6.b. 1008 048 3d be a4 5e 8c a9 67 12 82 fa fb 69 da 92 72 8b =..^..g....i..r. 1009 064 1a 71 de 0a 9e 06 0b 29 05 d6 a5 b6 7e cd 3b 36 .q.....)....~.;6 1010 080 92 dd bd 7f 2d 77 8b 8c 98 03 ae e3 28 09 1b 58 ....-w......(..X 1011 096 fa b3 24 e4 fa d6 75 94 55 85 80 8b 48 31 d7 bc ..$...u.U...H1.. 1012 112 3f f4 de f0 8e 4b 7a 9d e5 76 d2 65 86 ce c6 4b ?....Kz..v.e...K 1013 128 61 16 00 00 00 00 00 00 00 00 00 00 00 00 00 00 a............... 1014 144 0c 00 00 00 00 00 00 00 72 00 00 00 00 00 00 00 ........r....... 1016 Note the 4 zero bytes in line 000 and the 14 zero bytes in line 128 1018 Tag: 1019 1a:e1:0b:59:4f:09:e2:6a:7e:90:2e:cb:d0:60:06:91 1021 3. Implementation Advice 1023 Each block of ChaCha20 involves 16 move operations and one increment 1024 operation for loading the state, 80 each of XOR, addition and Roll 1025 operations for the rounds, 16 more add operations and 16 XOR 1026 operations for protecting the plaintext. Section 2.3 describes the 1027 ChaCha block function as "adding the original input words". This 1028 implies that before starting the rounds on the ChaCha state, we copy 1029 it aside, only to add it in later. This is correct, but we can save 1030 a few operations if we instead copy the state and do the work on the 1031 copy. This way, for the next block you don't need to recreate the 1032 state, but only to increment the block counter. This saves 1033 approximately 5.5% of the cycles. 1035 It is not recommended to use a generic big number library such as the 1036 one in OpenSSL for the arithmetic operations in Poly1305. Such 1037 libraries use dynamic allocation to be able to handle any-sized 1038 integer, but that flexibility comes at the expense of performance as 1039 well as side-channel security. More efficient implementations that 1040 run in constant time are available, one of them in D. J. 1041 Bernstein's own library, NaCl ([NaCl]). A constant-time but not 1042 optimal approach would be to naively implement the arithmetic 1043 operations for a 288-bit integers, because even a naive 1044 implementation will not exceed 2^288 in the multiplication of 1045 (acc+block) and r. An efficient constant-time implementation can be 1046 found in the public domain library poly1305-donna ([poly1305_donna]). 1048 4. Security Considerations 1050 The ChaCha20 cipher is designed to provide 256-bit security. 1052 The Poly1305 authenticator is designed to ensure that forged messages 1053 are rejected with a probability of 1-(n/(2^102)) for a 16n-byte 1054 message, even after sending 2^64 legitimate messages, so it is SUF- 1055 CMA in the terminology of [AE]. 1057 Proving the security of either of these is beyond the scope of this 1058 document. Such proofs are available in the referenced academic 1059 papers ([ChaCha],[Poly1305],[LatinDances], [LatinDances2], and 1060 [Zhenqing2012]) 1062 The most important security consideration in implementing this draft 1063 is the uniqueness of the nonce used in ChaCha20. Counters and LFSRs 1064 are both acceptable ways of generating unique nonces, as is 1065 encrypting a counter using a 64-bit cipher such as DES. Note that it 1066 is not acceptable to use a truncation of a counter encrypted with a 1067 128-bit or 256-bit cipher, because such a truncation may repeat after 1068 a short time. 1070 Consequences of repeating a nonce: If a nonce is repeated, then both 1071 the one-time Poly1305 key and the key-stream are identical between 1072 the messages. This reveals the XOR of the plaintexts, because the 1073 XOR of the plaintexts is equal to the XOR of the ciphertexts. 1075 The Poly1305 key MUST be unpredictable to an attacker. Randomly 1076 generating the key would fulfill this requirement, except that 1077 Poly1305 is often used in communications protocols, so the receiver 1078 should know the key. Pseudo-random number generation such as by 1079 encrypting a counter is acceptable. Using ChaCha with a secret key 1080 and a nonce is also acceptable. 1082 The algorithms presented here were designed to be easy to implement 1083 in constant time to avoid side-channel vulnerabilities. The 1084 operations used in ChaCha20 are all additions, XORs, and fixed 1085 rotations. All of these can and should be implemented in constant 1086 time. Access to offsets into the ChaCha state and the number of 1087 operations do not depend on any property of the key, eliminating the 1088 chance of information about the key leaking through the timing of 1089 cache misses. 1091 For Poly1305, the operations are addition, multiplication and 1092 modulus, all on >128-bit numbers. This can be done in constant time, 1093 but a naive implementation (such as using some generic big number 1094 library) will not be constant time. For example, if the 1095 multiplication is performed as a separate operation from the modulus, 1096 the result will sometimes be under 2^256 and some times be above 1097 2^256. Implementers should be careful about timing side-channels for 1098 Poly1305 by using the appropriate implementation of these operations. 1100 Validating the authenticity of a message involves a bitwise 1101 comparison of the calculated tag with the received tag. In most use 1102 cases nonces and AAD contents are not "used up" until a valid message 1103 is received. This allows an attacker to send multiple identical 1104 messages with different tags until one passes the tag comparison. 1105 This is hard if the attacker has to try all 2^128 possible tags one 1106 by one. However, if the timing of the tag comparison operation 1107 reveals how long a prefix of the calculated and received tags is 1108 identical, the number of messages can be reduced significantly. For 1109 this reason, with online protocols, implementation MUST use a 1110 constant-time comparison function rather than relying on optimized 1111 but insecure library functions such as the C language's memcmp(). 1113 5. IANA Considerations 1115 IANA is requested to assign an entry in the "Authenticated Encryption 1116 with Associated Data (AEAD) Parameters" registry with 1117 "AEAD_CHACHA20-POLY1305" as the name and this document as reference. 1119 6. Acknowledgements 1121 ChaCha20 and Poly1305 were invented by Daniel J. Bernstein. The 1122 AEAD construction and the method of creating the one-time Poly1305 1123 key were invented by Adam Langley. 1125 Thanks to Robert Ransom, Watson Ladd, Stefan Buhler, Dan Harkins, and 1126 Kenny Paterson for their helpful comments and explanations. Thanks 1127 to Niels Moeller for suggesting the more efficient AEAD construction 1128 in this document. Special thanks to Ilari Liusvaara for providing 1129 extra test vectors, helpful comments, and for being the first to 1130 attempt an implementation from this draft. And thanks to Sean 1131 Parkinson for suggesting improvements to the examples and the pseudo- 1132 code. Thanks to David Ireland for pointing out a bug in the pseudo- 1133 code, and to Stephen Farrell and Alyssa Rowan for pointing out 1134 missing advise in the security considerations. 1136 Special thanks goes to Gordon Procter for performing a security 1137 analysis of the composition and publishing [Procter]. 1139 7. Changes from Previous Versions 1141 NOTE TO RFC EDITOR: PLEASE REMOVE THIS SECTION BEFORE PUBLICATION 1143 7.1. Changes from version -01 to version -02 1145 Added IANA considerations and a paragraph in the security 1146 considerations detailing the consequences of repeating a nonce. 1148 Added the pseudo-code. 1150 Replaced the example of a quarterround in section 2.1 1152 7.2. Changes from version -00 to version -01 1154 Added references to [LatinDances2] and [Procter]. 1156 Added this section. 1158 7.3. Changes from draft-nir-cfrg to draft-irtf-cfrg 1160 Added references to [Zhenqing2012] and [LatinDances]. 1162 Many clarifications and improved terminology. 1164 More test vectors from Illari. 1166 8. References 1168 8.1. Normative References 1170 [ChaCha] Bernstein, D., "ChaCha, a variant of Salsa20", January 1171 2008, . 1173 [Poly1305] 1174 Bernstein, D., "The Poly1305-AES message-authentication 1175 code", March 2005, 1176 . 1178 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1179 Requirement Levels", BCP 14, RFC 2119, March 1997. 1181 8.2. Informative References 1183 [AE] Bellare, M. and C. Namprempre, "Authenticated Encryption: 1184 Relations among notions and analysis of the generic 1185 composition paradigm", December 2000, 1186 . 1188 [FIPS-197] 1189 National Institute of Standards and Technology, "Advanced 1190 Encryption Standard (AES)", FIPS PUB 197, November 2001, 1191 . 1194 [LatinDances] 1195 Aumasson, J., Fischer, S., Khazaei, S., Meier, W., and C. 1196 Rechberger, "New Features of Latin Dances: Analysis of 1197 Salsa, ChaCha, and Rumba", December 2007, 1198 . 1200 [LatinDances2] 1201 Ishiguro, T., Kiyomoto, S., and Y. Miyake, "Latin Dances 1202 Revisited: New Analytic Results of Salsa20 and ChaCha", 1203 February 2012, . 1205 [NaCl] Bernstein, D., Lange, T., and P. Schwabe, "NaCl: 1206 Networking and Cryptography library", July 2012, 1207 . 1209 [Procter] Procter, G., "A Security Analysis of the Composition of 1210 ChaCha20 and Poly1305", August 2014, 1211 . 1213 [RFC4868] Kelly, S. and S. Frankel, "Using HMAC-SHA-256, HMAC-SHA- 1214 384, and HMAC-SHA-512 with IPsec", RFC 4868, May 2007. 1216 [RFC5116] McGrew, D., "An Interface and Algorithms for Authenticated 1217 Encryption", RFC 5116, January 2008. 1219 [RFC7296] Kaufman, C., Hoffman, P., Nir, Y., Eronen, P., and T. 1220 Kivinen, "Internet Key Exchange Protocol Version 2 1221 (IKEv2)", RFC 7296, September 2010. 1223 [SP800-67] 1224 National Institute of Standards and Technology, 1225 "Recommendation for the Triple Data Encryption Algorithm 1226 (TDEA) Block Cipher", NIST 800-67, January 2012, 1227 . 1230 [Standby-Cipher] 1231 McGrew, D., Grieco, A., and Y. Sheffer, "Selection of 1232 Future Cryptographic Standards", draft-mcgrew-standby- 1233 cipher (work in progress), January 2013. 1235 [Zhenqing2012] 1236 Zhenqing, S., Bin, Z., Dengguo, F., and W. Wenling, 1237 "Improved key recovery attacks on reduced-round salsa20 1238 and chacha", 2012. 1240 [cache-collisions] 1241 Bonneau, J. and I. Mironov, "Cache-Collision Timing 1242 Attacks Against AES", 2006, 1243 . 1245 [poly1305_donna] 1246 Floodyberry, A., "Poly1305-donna", February 2014, 1247 . 1249 Appendix A. Additional Test Vectors 1251 The sub-sections of this appendix contain more test vectors for the 1252 algorithms in the sub-sections of Section 2. 1254 A.1. The ChaCha20 Block Functions 1255 Test Vector #1: 1256 ============== 1258 Key: 1259 000 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................ 1260 016 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................ 1262 Nonce: 1263 000 00 00 00 00 00 00 00 00 00 00 00 00 ............ 1265 Block Counter = 0 1267 ChaCha State at the end 1268 ade0b876 903df1a0 e56a5d40 28bd8653 1269 b819d2bd 1aed8da0 ccef36a8 c70d778b 1270 7c5941da 8d485751 3fe02477 374ad8b8 1271 f4b8436a 1ca11815 69b687c3 8665eeb2 1273 Keystream: 1274 000 76 b8 e0 ad a0 f1 3d 90 40 5d 6a e5 53 86 bd 28 v.....=.@]j.S..( 1275 016 bd d2 19 b8 a0 8d ed 1a a8 36 ef cc 8b 77 0d c7 .........6...w.. 1276 032 da 41 59 7c 51 57 48 8d 77 24 e0 3f b8 d8 4a 37 .AY|QWH.w$.?..J7 1277 048 6a 43 b8 f4 15 18 a1 1c c3 87 b6 69 b2 ee 65 86 jC.........i..e. 1279 Test Vector #2: 1280 ============== 1282 Key: 1283 000 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................ 1284 016 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................ 1286 Nonce: 1287 000 00 00 00 00 00 00 00 00 00 00 00 00 ............ 1289 Block Counter = 1 1291 ChaCha State at the end 1292 bee7079f 7a385155 7c97ba98 0d082d73 1293 a0290fcb 6965e348 3e53c612 ed7aee32 1294 7621b729 434ee69c b03371d5 d539d874 1295 281fed31 45fb0a51 1f0ae1ac 6f4d794b 1297 Keystream: 1298 000 9f 07 e7 be 55 51 38 7a 98 ba 97 7c 73 2d 08 0d ....UQ8z...|s-.. 1299 016 cb 0f 29 a0 48 e3 65 69 12 c6 53 3e 32 ee 7a ed ..).H.ei..S>2.z. 1300 032 29 b7 21 76 9c e6 4e 43 d5 71 33 b0 74 d8 39 d5 ).!v..NC.q3.t.9. 1301 048 31 ed 1f 28 51 0a fb 45 ac e1 0a 1f 4b 79 4d 6f 1..(Q..E....KyMo 1302 Test Vector #3: 1303 ============== 1305 Key: 1306 000 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................ 1307 016 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 01 ................ 1309 Nonce: 1310 000 00 00 00 00 00 00 00 00 00 00 00 00 ............ 1312 Block Counter = 1 1314 ChaCha State at the end 1315 2452eb3a 9249f8ec 8d829d9b ddd4ceb1 1316 e8252083 60818b01 f38422b8 5aaa49c9 1317 bb00ca8e da3ba7b4 c4b592d1 fdf2732f 1318 4436274e 2561b3c8 ebdd4aa6 a0136c00 1320 Keystream: 1321 000 3a eb 52 24 ec f8 49 92 9b 9d 82 8d b1 ce d4 dd :.R$..I......... 1322 016 83 20 25 e8 01 8b 81 60 b8 22 84 f3 c9 49 aa 5a . %....`."...I.Z 1323 032 8e ca 00 bb b4 a7 3b da d1 92 b5 c4 2f 73 f2 fd ......;...../s.. 1324 048 4e 27 36 44 c8 b3 61 25 a6 4a dd eb 00 6c 13 a0 N'6D..a%.J...l.. 1326 Test Vector #4: 1327 ============== 1329 Key: 1330 000 00 ff 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................ 1331 016 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................ 1333 Nonce: 1334 000 00 00 00 00 00 00 00 00 00 00 00 00 ............ 1336 Block Counter = 2 1338 ChaCha State at the end 1339 fb4dd572 4bc42ef1 df922636 327f1394 1340 a78dea8f 5e269039 a1bebbc1 caf09aae 1341 a25ab213 48a6b46c 1b9d9bcb 092c5be6 1342 546ca624 1bec45d5 87f47473 96f0992e 1344 Keystream: 1345 000 72 d5 4d fb f1 2e c4 4b 36 26 92 df 94 13 7f 32 r.M....K6&.....2 1346 016 8f ea 8d a7 39 90 26 5e c1 bb be a1 ae 9a f0 ca ....9.&^........ 1347 032 13 b2 5a a2 6c b4 a6 48 cb 9b 9d 1b e6 5b 2c 09 ..Z.l..H.....[,. 1348 048 24 a6 6c 54 d5 45 ec 1b 73 74 f4 87 2e 99 f0 96 $.lT.E..st...... 1350 Test Vector #5: 1351 ============== 1353 Key: 1354 000 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................ 1355 016 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................ 1357 Nonce: 1358 000 00 00 00 00 00 00 00 00 00 00 00 02 ............ 1360 Block Counter = 0 1362 ChaCha State at the end 1363 374dc6c2 3736d58c b904e24a cd3f93ef 1364 88228b1a 96a4dfb3 5b76ab72 c727ee54 1365 0e0e978a f3145c95 1b748ea8 f786c297 1366 99c28f5f 628314e8 398a19fa 6ded1b53 1368 Keystream: 1369 000 c2 c6 4d 37 8c d5 36 37 4a e2 04 b9 ef 93 3f cd ..M7..67J.....?. 1370 016 1a 8b 22 88 b3 df a4 96 72 ab 76 5b 54 ee 27 c7 ..".....r.v[T.'. 1371 032 8a 97 0e 0e 95 5c 14 f3 a8 8e 74 1b 97 c2 86 f7 .....\....t..... 1372 048 5f 8f c2 99 e8 14 83 62 fa 19 8a 39 53 1b ed 6d _......b...9S..m 1374 A.2. ChaCha20 Encryption 1375 Test Vector #1: 1376 ============== 1378 Key: 1379 000 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................ 1380 016 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................ 1382 Nonce: 1383 000 00 00 00 00 00 00 00 00 00 00 00 00 ............ 1385 Initial Block Counter = 0 1387 Plaintext: 1388 000 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................ 1389 016 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................ 1390 032 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................ 1391 048 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................ 1393 Ciphertext: 1394 000 76 b8 e0 ad a0 f1 3d 90 40 5d 6a e5 53 86 bd 28 v.....=.@]j.S..( 1395 016 bd d2 19 b8 a0 8d ed 1a a8 36 ef cc 8b 77 0d c7 .........6...w.. 1396 032 da 41 59 7c 51 57 48 8d 77 24 e0 3f b8 d8 4a 37 .AY|QWH.w$.?..J7 1397 048 6a 43 b8 f4 15 18 a1 1c c3 87 b6 69 b2 ee 65 86 jC.........i..e. 1399 Test Vector #2: 1400 ============== 1402 Key: 1403 000 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................ 1404 016 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 01 ................ 1406 Nonce: 1407 000 00 00 00 00 00 00 00 00 00 00 00 02 ............ 1409 Initial Block Counter = 1 1411 Plaintext: 1412 000 41 6e 79 20 73 75 62 6d 69 73 73 69 6f 6e 20 74 Any submission t 1413 016 6f 20 74 68 65 20 49 45 54 46 20 69 6e 74 65 6e o the IETF inten 1414 032 64 65 64 20 62 79 20 74 68 65 20 43 6f 6e 74 72 ded by the Contr 1415 048 69 62 75 74 6f 72 20 66 6f 72 20 70 75 62 6c 69 ibutor for publi 1416 064 63 61 74 69 6f 6e 20 61 73 20 61 6c 6c 20 6f 72 cation as all or 1417 080 20 70 61 72 74 20 6f 66 20 61 6e 20 49 45 54 46 part of an IETF 1418 096 20 49 6e 74 65 72 6e 65 74 2d 44 72 61 66 74 20 Internet-Draft 1419 112 6f 72 20 52 46 43 20 61 6e 64 20 61 6e 79 20 73 or RFC and any s 1420 128 74 61 74 65 6d 65 6e 74 20 6d 61 64 65 20 77 69 tatement made wi 1421 144 74 68 69 6e 20 74 68 65 20 63 6f 6e 74 65 78 74 thin the context 1422 160 20 6f 66 20 61 6e 20 49 45 54 46 20 61 63 74 69 of an IETF acti 1423 176 76 69 74 79 20 69 73 20 63 6f 6e 73 69 64 65 72 vity is consider 1424 192 65 64 20 61 6e 20 22 49 45 54 46 20 43 6f 6e 74 ed an "IETF Cont 1425 208 72 69 62 75 74 69 6f 6e 22 2e 20 53 75 63 68 20 ribution". Such 1426 224 73 74 61 74 65 6d 65 6e 74 73 20 69 6e 63 6c 75 statements inclu 1427 240 64 65 20 6f 72 61 6c 20 73 74 61 74 65 6d 65 6e de oral statemen 1428 256 74 73 20 69 6e 20 49 45 54 46 20 73 65 73 73 69 ts in IETF sessi 1429 272 6f 6e 73 2c 20 61 73 20 77 65 6c 6c 20 61 73 20 ons, as well as 1430 288 77 72 69 74 74 65 6e 20 61 6e 64 20 65 6c 65 63 written and elec 1431 304 74 72 6f 6e 69 63 20 63 6f 6d 6d 75 6e 69 63 61 tronic communica 1432 320 74 69 6f 6e 73 20 6d 61 64 65 20 61 74 20 61 6e tions made at an 1433 336 79 20 74 69 6d 65 20 6f 72 20 70 6c 61 63 65 2c y time or place, 1434 352 20 77 68 69 63 68 20 61 72 65 20 61 64 64 72 65 which are addre 1435 368 73 73 65 64 20 74 6f ssed to 1437 Ciphertext: 1438 000 a3 fb f0 7d f3 fa 2f de 4f 37 6c a2 3e 82 73 70 ...}../.O7l.>.sp 1439 016 41 60 5d 9f 4f 4f 57 bd 8c ff 2c 1d 4b 79 55 ec A`].OOW...,.KyU. 1440 032 2a 97 94 8b d3 72 29 15 c8 f3 d3 37 f7 d3 70 05 *....r)....7..p. 1441 048 0e 9e 96 d6 47 b7 c3 9f 56 e0 31 ca 5e b6 25 0d ....G...V.1.^.%. 1442 064 40 42 e0 27 85 ec ec fa 4b 4b b5 e8 ea d0 44 0e @B.'....KK....D. 1443 080 20 b6 e8 db 09 d8 81 a7 c6 13 2f 42 0e 52 79 50 ........./B.RyP 1444 096 42 bd fa 77 73 d8 a9 05 14 47 b3 29 1c e1 41 1c B..ws....G.)..A. 1445 112 68 04 65 55 2a a6 c4 05 b7 76 4d 5e 87 be a8 5a h.eU*....vM^...Z 1446 128 d0 0f 84 49 ed 8f 72 d0 d6 62 ab 05 26 91 ca 66 ...I..r..b..&..f 1447 144 42 4b c8 6d 2d f8 0e a4 1f 43 ab f9 37 d3 25 9d BK.m-....C..7.%. 1448 160 c4 b2 d0 df b4 8a 6c 91 39 dd d7 f7 69 66 e9 28 ......l.9...if.( 1449 176 e6 35 55 3b a7 6c 5c 87 9d 7b 35 d4 9e b2 e6 2b .5U;.l\..{5....+ 1450 192 08 71 cd ac 63 89 39 e2 5e 8a 1e 0e f9 d5 28 0f .q..c.9.^.....(. 1451 208 a8 ca 32 8b 35 1c 3c 76 59 89 cb cf 3d aa 8b 6c ..2.5.vC.. 1490 080 1a 55 32 05 57 16 ea d6 96 25 68 f8 7d 3f 3f 77 .U2.W....%h.}??w 1491 096 04 c6 a8 d1 bc d1 bf 4d 50 d6 15 4b 6d a7 31 b1 .......MP..Km.1. 1492 112 87 b5 8d fd 72 8a fa 36 75 7a 79 7a c1 88 d1 ....r..6uzyz... 1494 A.3. Poly1305 Message Authentication Code 1496 Notice how in test vector #2 r is equal to zero. The part of the 1497 Poly1305 algorithm where the accumulator is multiplied by r means 1498 that with r equal zero, the tag will be equal to s regardless of the 1499 content of the Text. Fortunately, all the proposed methods of 1500 generating r are such that getting this particular weak key is very 1501 unlikely. 1503 Test Vector #1: 1504 ============== 1506 One-time Poly1305 Key: 1507 000 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................ 1508 016 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................ 1510 Text to MAC: 1511 000 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................ 1512 016 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................ 1513 032 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................ 1514 048 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................ 1516 Tag: 1517 000 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................ 1519 Test Vector #2: 1520 ============== 1522 One-time Poly1305 Key: 1523 000 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................ 1524 016 36 e5 f6 b5 c5 e0 60 70 f0 ef ca 96 22 7a 86 3e 6.....`p...."z.> 1526 Text to MAC: 1527 000 41 6e 79 20 73 75 62 6d 69 73 73 69 6f 6e 20 74 Any submission t 1528 016 6f 20 74 68 65 20 49 45 54 46 20 69 6e 74 65 6e o the IETF inten 1529 032 64 65 64 20 62 79 20 74 68 65 20 43 6f 6e 74 72 ded by the Contr 1530 048 69 62 75 74 6f 72 20 66 6f 72 20 70 75 62 6c 69 ibutor for publi 1531 064 63 61 74 69 6f 6e 20 61 73 20 61 6c 6c 20 6f 72 cation as all or 1532 080 20 70 61 72 74 20 6f 66 20 61 6e 20 49 45 54 46 part of an IETF 1533 096 20 49 6e 74 65 72 6e 65 74 2d 44 72 61 66 74 20 Internet-Draft 1534 112 6f 72 20 52 46 43 20 61 6e 64 20 61 6e 79 20 73 or RFC and any s 1535 128 74 61 74 65 6d 65 6e 74 20 6d 61 64 65 20 77 69 tatement made wi 1536 144 74 68 69 6e 20 74 68 65 20 63 6f 6e 74 65 78 74 thin the context 1537 160 20 6f 66 20 61 6e 20 49 45 54 46 20 61 63 74 69 of an IETF acti 1538 176 76 69 74 79 20 69 73 20 63 6f 6e 73 69 64 65 72 vity is consider 1539 192 65 64 20 61 6e 20 22 49 45 54 46 20 43 6f 6e 74 ed an "IETF Cont 1540 208 72 69 62 75 74 69 6f 6e 22 2e 20 53 75 63 68 20 ribution". Such 1541 224 73 74 61 74 65 6d 65 6e 74 73 20 69 6e 63 6c 75 statements inclu 1542 240 64 65 20 6f 72 61 6c 20 73 74 61 74 65 6d 65 6e de oral statemen 1543 256 74 73 20 69 6e 20 49 45 54 46 20 73 65 73 73 69 ts in IETF sessi 1544 272 6f 6e 73 2c 20 61 73 20 77 65 6c 6c 20 61 73 20 ons, as well as 1545 288 77 72 69 74 74 65 6e 20 61 6e 64 20 65 6c 65 63 written and elec 1546 304 74 72 6f 6e 69 63 20 63 6f 6d 6d 75 6e 69 63 61 tronic communica 1547 320 74 69 6f 6e 73 20 6d 61 64 65 20 61 74 20 61 6e tions made at an 1548 336 79 20 74 69 6d 65 20 6f 72 20 70 6c 61 63 65 2c y time or place, 1549 352 20 77 68 69 63 68 20 61 72 65 20 61 64 64 72 65 which are addre 1550 368 73 73 65 64 20 74 6f ssed to 1552 Tag: 1553 000 36 e5 f6 b5 c5 e0 60 70 f0 ef ca 96 22 7a 86 3e 6.....`p...."z.> 1554 Test Vector #3: 1555 ============== 1557 One-time Poly1305 Key: 1558 000 36 e5 f6 b5 c5 e0 60 70 f0 ef ca 96 22 7a 86 3e 6.....`p...."z.> 1559 016 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................ 1561 Text to MAC: 1562 000 41 6e 79 20 73 75 62 6d 69 73 73 69 6f 6e 20 74 Any submission t 1563 016 6f 20 74 68 65 20 49 45 54 46 20 69 6e 74 65 6e o the IETF inten 1564 032 64 65 64 20 62 79 20 74 68 65 20 43 6f 6e 74 72 ded by the Contr 1565 048 69 62 75 74 6f 72 20 66 6f 72 20 70 75 62 6c 69 ibutor for publi 1566 064 63 61 74 69 6f 6e 20 61 73 20 61 6c 6c 20 6f 72 cation as all or 1567 080 20 70 61 72 74 20 6f 66 20 61 6e 20 49 45 54 46 part of an IETF 1568 096 20 49 6e 74 65 72 6e 65 74 2d 44 72 61 66 74 20 Internet-Draft 1569 112 6f 72 20 52 46 43 20 61 6e 64 20 61 6e 79 20 73 or RFC and any s 1570 128 74 61 74 65 6d 65 6e 74 20 6d 61 64 65 20 77 69 tatement made wi 1571 144 74 68 69 6e 20 74 68 65 20 63 6f 6e 74 65 78 74 thin the context 1572 160 20 6f 66 20 61 6e 20 49 45 54 46 20 61 63 74 69 of an IETF acti 1573 176 76 69 74 79 20 69 73 20 63 6f 6e 73 69 64 65 72 vity is consider 1574 192 65 64 20 61 6e 20 22 49 45 54 46 20 43 6f 6e 74 ed an "IETF Cont 1575 208 72 69 62 75 74 69 6f 6e 22 2e 20 53 75 63 68 20 ribution". Such 1576 224 73 74 61 74 65 6d 65 6e 74 73 20 69 6e 63 6c 75 statements inclu 1577 240 64 65 20 6f 72 61 6c 20 73 74 61 74 65 6d 65 6e de oral statemen 1578 256 74 73 20 69 6e 20 49 45 54 46 20 73 65 73 73 69 ts in IETF sessi 1579 272 6f 6e 73 2c 20 61 73 20 77 65 6c 6c 20 61 73 20 ons, as well as 1580 288 77 72 69 74 74 65 6e 20 61 6e 64 20 65 6c 65 63 written and elec 1581 304 74 72 6f 6e 69 63 20 63 6f 6d 6d 75 6e 69 63 61 tronic communica 1582 320 74 69 6f 6e 73 20 6d 61 64 65 20 61 74 20 61 6e tions made at an 1583 336 79 20 74 69 6d 65 20 6f 72 20 70 6c 61 63 65 2c y time or place, 1584 352 20 77 68 69 63 68 20 61 72 65 20 61 64 64 72 65 which are addre 1585 368 73 73 65 64 20 74 6f ssed to 1587 Tag: 1588 000 f3 47 7e 7c d9 54 17 af 89 a6 b8 79 4c 31 0c f0 .G~|.T.....yL1.. 1590 Test Vector #4: 1591 ============== 1593 One-time Poly1305 Key: 1594 000 1c 92 40 a5 eb 55 d3 8a f3 33 88 86 04 f6 b5 f0 ..@..U...3...... 1595 016 47 39 17 c1 40 2b 80 09 9d ca 5c bc 20 70 75 c0 G9..@+....\. pu. 1597 Text to MAC: 1598 000 27 54 77 61 73 20 62 72 69 6c 6c 69 67 2c 20 61 'Twas brillig, a 1599 016 6e 64 20 74 68 65 20 73 6c 69 74 68 79 20 74 6f nd the slithy to 1600 032 76 65 73 0a 44 69 64 20 67 79 72 65 20 61 6e 64 ves.Did gyre and 1601 048 20 67 69 6d 62 6c 65 20 69 6e 20 74 68 65 20 77 gimble in the w 1602 064 61 62 65 3a 0a 41 6c 6c 20 6d 69 6d 73 79 20 77 abe:.All mimsy w 1603 080 65 72 65 20 74 68 65 20 62 6f 72 6f 67 6f 76 65 ere the borogove 1604 096 73 2c 0a 41 6e 64 20 74 68 65 20 6d 6f 6d 65 20 s,.And the mome 1605 112 72 61 74 68 73 20 6f 75 74 67 72 61 62 65 2e raths outgrabe. 1607 Tag: 1608 000 45 41 66 9a 7e aa ee 61 e7 08 dc 7c bc c5 eb 62 EAf.~..a...|...b 1610 Test Vector #5: If one uses 130-bit partial reduction, does the code 1611 handle the case where partially reduced final result is not fully 1612 reduced? 1614 R: 1615 02 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 1616 S: 1617 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 1618 data: 1619 FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF 1620 tag: 1621 03 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 1623 Test Vector #6: What happens if addition of s overflows modulo 2^128? 1625 R: 1626 02 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 1627 S: 1628 FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF 1629 data: 1630 02 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 1631 tag: 1632 03 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 1633 Test Vector #7: What happens if data limb is all ones and there is 1634 carry from lower limb? 1636 R: 1637 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 1638 S: 1639 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 1640 data: 1641 FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF 1642 F0 FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF 1643 11 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 1644 tag: 1645 05 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 1647 Test Vector #8: What happens if final result from polynomial part is 1648 exactly 2^130-5? 1650 R: 1651 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 1652 S: 1653 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 1654 data: 1655 FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF 1656 FB FE FE FE FE FE FE FE FE FE FE FE FE FE FE FE 1657 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 1658 tag: 1659 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 1661 Test Vector #9: What happens if final result from polynomial part is 1662 exactly 2^130-6? 1664 R: 1665 02 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 1666 S: 1667 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 1668 data: 1669 FD FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF 1670 tag: 1671 FA FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF 1672 Test Vector #10: What happens if 5*H+L-type reduction produces 1673 131-bit intermediate result? 1675 R: 1676 01 00 00 00 00 00 00 00 04 00 00 00 00 00 00 00 1677 S: 1678 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 1679 data: 1680 E3 35 94 D7 50 5E 43 B9 00 00 00 00 00 00 00 00 1681 33 94 D7 50 5E 43 79 CD 01 00 00 00 00 00 00 00 1682 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 1683 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 1684 tag: 1685 14 00 00 00 00 00 00 00 55 00 00 00 00 00 00 00 1687 Test Vector #11: What happens if 5*H+L-type reduction produces 1688 131-bit final result? 1690 R: 1691 01 00 00 00 00 00 00 00 04 00 00 00 00 00 00 00 1692 S: 1693 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 1694 data: 1695 E3 35 94 D7 50 5E 43 B9 00 00 00 00 00 00 00 00 1696 33 94 D7 50 5E 43 79 CD 01 00 00 00 00 00 00 00 1697 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 1698 tag: 1699 13 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 1701 A.4. Poly1305 Key Generation Using ChaCha20 1703 Test Vector #1: 1704 ============== 1706 The key: 1707 000 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................ 1708 016 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................ 1710 The nonce: 1711 000 00 00 00 00 00 00 00 00 00 00 00 00 ............ 1713 Poly1305 one-time key: 1714 000 76 b8 e0 ad a0 f1 3d 90 40 5d 6a e5 53 86 bd 28 v.....=.@]j.S..( 1715 016 bd d2 19 b8 a0 8d ed 1a a8 36 ef cc 8b 77 0d c7 .........6...w.. 1717 Test Vector #2: 1718 ============== 1720 The key: 1721 000 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................ 1722 016 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 01 ................ 1724 The nonce: 1725 000 00 00 00 00 00 00 00 00 00 00 00 02 ............ 1727 Poly1305 one-time key: 1728 000 ec fa 25 4f 84 5f 64 74 73 d3 cb 14 0d a9 e8 76 ..%O._dts......v 1729 016 06 cb 33 06 6c 44 7b 87 bc 26 66 dd e3 fb b7 39 ..3.lD{..&f....9 1731 Test Vector #3: 1732 ============== 1734 The key: 1735 000 1c 92 40 a5 eb 55 d3 8a f3 33 88 86 04 f6 b5 f0 ..@..U...3...... 1736 016 47 39 17 c1 40 2b 80 09 9d ca 5c bc 20 70 75 c0 G9..@+....\. pu. 1738 The nonce: 1739 000 00 00 00 00 00 00 00 00 00 00 00 02 ............ 1741 Poly1305 one-time key: 1742 000 96 5e 3b c6 f9 ec 7e d9 56 08 08 f4 d2 29 f9 4b .^;...~.V....).K 1743 016 13 7f f2 75 ca 9b 3f cb dd 59 de aa d2 33 10 ae ...u..?..Y...3.. 1745 A.5. ChaCha20-Poly1305 AEAD Decryption 1747 Below we'll see decrypting a message. We receive a ciphertext, a 1748 nonce, and a tag. We know the key. We will check the tag, and then 1749 (assuming that it validates) decrypt the ciphertext. In this 1750 particular protocol, we'll assume that there is no padding of the 1751 plaintext. 1753 The key: 1754 000 1c 92 40 a5 eb 55 d3 8a f3 33 88 86 04 f6 b5 f0 ..@..U...3...... 1755 016 47 39 17 c1 40 2b 80 09 9d ca 5c bc 20 70 75 c0 G9..@+....\. pu. 1757 Ciphertext: 1758 000 64 a0 86 15 75 86 1a f4 60 f0 62 c7 9b e6 43 bd d...u...`.b...C. 1759 016 5e 80 5c fd 34 5c f3 89 f1 08 67 0a c7 6c 8c b2 ^.\.4\....g..l.. 1760 032 4c 6c fc 18 75 5d 43 ee a0 9e e9 4e 38 2d 26 b0 Ll..u]C....N8-&. 1761 048 bd b7 b7 3c 32 1b 01 00 d4 f0 3b 7f 35 58 94 cf ...<2.....;.5X.. 1762 064 33 2f 83 0e 71 0b 97 ce 98 c8 a8 4a bd 0b 94 81 3/..q......J.... 1763 080 14 ad 17 6e 00 8d 33 bd 60 f9 82 b1 ff 37 c8 55 ...n..3.`....7.U 1764 096 97 97 a0 6e f4 f0 ef 61 c1 86 32 4e 2b 35 06 38 ...n...a..2N+5.8 1765 112 36 06 90 7b 6a 7c 02 b0 f9 f6 15 7b 53 c8 67 e4 6..{j|.....{S.g. 1766 128 b9 16 6c 76 7b 80 4d 46 a5 9b 52 16 cd e7 a4 e9 ..lv{.MF..R..... 1767 144 90 40 c5 a4 04 33 22 5e e2 82 a1 b0 a0 6c 52 3e .@...3"^.....lR> 1768 160 af 45 34 d7 f8 3f a1 15 5b 00 47 71 8c bc 54 6a .E4..?..[.Gq..Tj 1769 176 0d 07 2b 04 b3 56 4e ea 1b 42 22 73 f5 48 27 1a ..+..VN..B"s.H'. 1770 192 0b b2 31 60 53 fa 76 99 19 55 eb d6 31 59 43 4e ..1`S.v..U..1YCN 1771 208 ce bb 4e 46 6d ae 5a 10 73 a6 72 76 27 09 7a 10 ..NFm.Z.s.rv'.z. 1772 224 49 e6 17 d9 1d 36 10 94 fa 68 f0 ff 77 98 71 30 I....6...h..w.q0 1773 240 30 5b ea ba 2e da 04 df 99 7b 71 4d 6c 6f 2c 29 0[.......{qMlo,) 1774 256 a6 ad 5c b4 02 2b 02 70 9b ..\..+.p. 1776 The nonce: 1777 000 00 00 00 00 01 02 03 04 05 06 07 08 ............ 1779 The AAD: 1780 000 f3 33 88 86 00 00 00 00 00 00 4e 91 .3........N. 1782 Received Tag: 1783 000 ee ad 9d 67 89 0c bb 22 39 23 36 fe a1 85 1f 38 ...g..."9#6....8 1784 First, we calculate the one-time Poly1305 key 1786 @@@ ChaCha state with key set up 1787 61707865 3320646e 79622d32 6b206574 1788 a540921c 8ad355eb 868833f3 f0b5f604 1789 c1173947 09802b40 bc5cca9d c0757020 1790 00000000 00000000 04030201 08070605 1792 @@@ ChaCha state after 20 rounds 1793 a94af0bd 89dee45c b64bb195 afec8fa1 1794 508f4726 63f554c0 1ea2c0db aa721526 1795 11b1e514 a0bacc0f 828a6015 d7825481 1796 e8a4a850 d9dcbbd6 4c2de33a f8ccd912 1798 @@@ out bytes: 1799 bd:f0:4a:a9:5c:e4:de:89:95:b1:4b:b6:a1:8f:ec:af: 1800 26:47:8f:50:c0:54:f5:63:db:c0:a2:1e:26:15:72:aa 1802 Poly1305 one-time key: 1803 000 bd f0 4a a9 5c e4 de 89 95 b1 4b b6 a1 8f ec af ..J.\.....K..... 1804 016 26 47 8f 50 c0 54 f5 63 db c0 a2 1e 26 15 72 aa &G.P.T.c....&.r. 1806 Next, we construct the AEAD buffer 1808 Poly1305 Input: 1809 000 f3 33 88 86 00 00 00 00 00 00 4e 91 00 00 00 00 .3........N..... 1810 016 64 a0 86 15 75 86 1a f4 60 f0 62 c7 9b e6 43 bd d...u...`.b...C. 1811 032 5e 80 5c fd 34 5c f3 89 f1 08 67 0a c7 6c 8c b2 ^.\.4\....g..l.. 1812 048 4c 6c fc 18 75 5d 43 ee a0 9e e9 4e 38 2d 26 b0 Ll..u]C....N8-&. 1813 064 bd b7 b7 3c 32 1b 01 00 d4 f0 3b 7f 35 58 94 cf ...<2.....;.5X.. 1814 080 33 2f 83 0e 71 0b 97 ce 98 c8 a8 4a bd 0b 94 81 3/..q......J.... 1815 096 14 ad 17 6e 00 8d 33 bd 60 f9 82 b1 ff 37 c8 55 ...n..3.`....7.U 1816 112 97 97 a0 6e f4 f0 ef 61 c1 86 32 4e 2b 35 06 38 ...n...a..2N+5.8 1817 128 36 06 90 7b 6a 7c 02 b0 f9 f6 15 7b 53 c8 67 e4 6..{j|.....{S.g. 1818 144 b9 16 6c 76 7b 80 4d 46 a5 9b 52 16 cd e7 a4 e9 ..lv{.MF..R..... 1819 160 90 40 c5 a4 04 33 22 5e e2 82 a1 b0 a0 6c 52 3e .@...3"^.....lR> 1820 176 af 45 34 d7 f8 3f a1 15 5b 00 47 71 8c bc 54 6a .E4..?..[.Gq..Tj 1821 192 0d 07 2b 04 b3 56 4e ea 1b 42 22 73 f5 48 27 1a ..+..VN..B"s.H'. 1822 208 0b b2 31 60 53 fa 76 99 19 55 eb d6 31 59 43 4e ..1`S.v..U..1YCN 1823 224 ce bb 4e 46 6d ae 5a 10 73 a6 72 76 27 09 7a 10 ..NFm.Z.s.rv'.z. 1824 240 49 e6 17 d9 1d 36 10 94 fa 68 f0 ff 77 98 71 30 I....6...h..w.q0 1825 256 30 5b ea ba 2e da 04 df 99 7b 71 4d 6c 6f 2c 29 0[.......{qMlo,) 1826 272 a6 ad 5c b4 02 2b 02 70 9b 00 00 00 00 00 00 00 ..\..+.p........ 1827 288 0c 00 00 00 00 00 00 00 09 01 00 00 00 00 00 00 ................ 1829 We calculate the Poly1305 tag and find that it matches 1831 Calculated Tag: 1832 000 ee ad 9d 67 89 0c bb 22 39 23 36 fe a1 85 1f 38 ...g..."9#6....8 1834 Finally, we decrypt the ciphertext 1836 Plaintext:: 1837 000 49 6e 74 65 72 6e 65 74 2d 44 72 61 66 74 73 20 Internet-Drafts 1838 016 61 72 65 20 64 72 61 66 74 20 64 6f 63 75 6d 65 are draft docume 1839 032 6e 74 73 20 76 61 6c 69 64 20 66 6f 72 20 61 20 nts valid for a 1840 048 6d 61 78 69 6d 75 6d 20 6f 66 20 73 69 78 20 6d maximum of six m 1841 064 6f 6e 74 68 73 20 61 6e 64 20 6d 61 79 20 62 65 onths and may be 1842 080 20 75 70 64 61 74 65 64 2c 20 72 65 70 6c 61 63 updated, replac 1843 096 65 64 2c 20 6f 72 20 6f 62 73 6f 6c 65 74 65 64 ed, or obsoleted 1844 112 20 62 79 20 6f 74 68 65 72 20 64 6f 63 75 6d 65 by other docume 1845 128 6e 74 73 20 61 74 20 61 6e 79 20 74 69 6d 65 2e nts at any time. 1846 144 20 49 74 20 69 73 20 69 6e 61 70 70 72 6f 70 72 It is inappropr 1847 160 69 61 74 65 20 74 6f 20 75 73 65 20 49 6e 74 65 iate to use Inte 1848 176 72 6e 65 74 2d 44 72 61 66 74 73 20 61 73 20 72 rnet-Drafts as r 1849 192 65 66 65 72 65 6e 63 65 20 6d 61 74 65 72 69 61 eference materia 1850 208 6c 20 6f 72 20 74 6f 20 63 69 74 65 20 74 68 65 l or to cite the 1851 224 6d 20 6f 74 68 65 72 20 74 68 61 6e 20 61 73 20 m other than as 1852 240 2f e2 80 9c 77 6f 72 6b 20 69 6e 20 70 72 6f 67 /...work in prog 1853 256 72 65 73 73 2e 2f e2 80 9d ress./... 1855 Appendix B. Performance Measurements of ChaCha20 1857 The following measurements were made by Adam Langley for a blog post 1858 published on February 27th, 2014. The original blog post was 1859 available at the time of this writing at 1860 https://www.imperialviolet.org/2014/02/27/tlssymmetriccrypto.html . 1862 +---------------------------+-------------+-------------------+ 1863 | Chip | AES-128-GCM | ChaCha20-Poly1305 | 1864 +---------------------------+-------------+-------------------+ 1865 | OMAP 4460 | 24.1 MB/s | 75.3 MB/s | 1866 | Snapdragon S4 Pro | 41.5 MB/s | 130.9 MB/s | 1867 | Sandy Bridge Xeon (AESNI) | 900 MB/s | 500 MB/s | 1868 +---------------------------+-------------+-------------------+ 1870 Table 1: Speed Comparison 1872 Authors' Addresses 1873 Yoav Nir 1874 Check Point Software Technologies Ltd. 1875 5 Hasolelim st. 1876 Tel Aviv 6789735 1877 Israel 1879 Email: ynir.ietf@gmail.com 1881 Adam Langley 1882 Google Inc 1884 Email: agl@google.com