< draft-nir-cfrg-chacha20-poly1305-00.txt   draft-nir-cfrg-chacha20-poly1305-01.txt >
Network Working Group Y. Nir Network Working Group Y. Nir
Internet-Draft Check Point Internet-Draft Check Point
Intended status: Informational January 27, 2014 Intended status: Informational A. Langley
Expires: July 31, 2014 Expires: August 4, 2014 Google Inc
January 31, 2014
ChaCha20 and Poly1305 for IETF protocols ChaCha20 and Poly1305 for IETF protocols
draft-nir-cfrg-chacha20-poly1305-00 draft-nir-cfrg-chacha20-poly1305-01
Abstract Abstract
This document defines the ChaCha20 stream cipher, as well as the use This document defines the ChaCha20 stream cipher, as well as the use
of the Poly1305 authenticator, both as stand-alone algorithms, and as of the Poly1305 authenticator, both as stand-alone algorithms, and as
a :"combined mode", or Authenticated Encryption with Additional Data a "combined mode", or Authenticated Encryption with Additional Data
(AEAD) algorithm. (AEAD) algorithm.
This document does not introduce any new crypto, but is meant to This document does not introduce any new crypto, but is meant to
serve as a stable reference and an implementation guide. serve as a stable reference and an implementation guide.
Status of this Memo Status of this Memo
This Internet-Draft is submitted in full conformance with the This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79. provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/. Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on July 31, 2014. This Internet-Draft will expire on August 4, 2014.
Copyright Notice Copyright Notice
Copyright (c) 2014 IETF Trust and the persons identified as the Copyright (c) 2014 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of (http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
skipping to change at page 2, line 18 skipping to change at page 2, line 18
1.1. Conventions Used in This Document . . . . . . . . . . . . 3 1.1. Conventions Used in This Document . . . . . . . . . . . . 3
2. The Algorithms . . . . . . . . . . . . . . . . . . . . . . . . 4 2. The Algorithms . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1. The ChaCha Quarter Round . . . . . . . . . . . . . . . . . 4 2.1. The ChaCha Quarter Round . . . . . . . . . . . . . . . . . 4
2.1.1. Test Vector for the ChaCha Quarter Round . . . . . . . 4 2.1.1. Test Vector for the ChaCha Quarter Round . . . . . . . 4
2.2. A Quarter Round on the ChaCha State . . . . . . . . . . . 5 2.2. A Quarter Round on the ChaCha State . . . . . . . . . . . 5
2.2.1. Test Vector for the Quarter Round on the ChaCha 2.2.1. Test Vector for the Quarter Round on the ChaCha
state . . . . . . . . . . . . . . . . . . . . . . . . 5 state . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3. The ChaCha20 block Function . . . . . . . . . . . . . . . 6 2.3. The ChaCha20 block Function . . . . . . . . . . . . . . . 6
2.3.1. Test Vector for the ChaCha20 Block Function . . . . . 7 2.3.1. Test Vector for the ChaCha20 Block Function . . . . . 7
2.4. The ChaCha20 encryption algorithm . . . . . . . . . . . . 8 2.4. The ChaCha20 encryption algorithm . . . . . . . . . . . . 8
2.4.1. Example and Test Vector for the ChaCha20 Cipher . . . 8 2.4.1. Example and Test Vector for the ChaCha20 Cipher . . . 9
2.5. The Poly1305 algorithm . . . . . . . . . . . . . . . . . . 10 2.5. The Poly1305 algorithm . . . . . . . . . . . . . . . . . . 10
2.5.1. Poly1305 Example and Test Vector . . . . . . . . . . . 12 2.5.1. Poly1305 Example and Test Vector . . . . . . . . . . . 12
2.6. Generating the Poly1305 key using ChaCha20 . . . . . . . . 13 2.6. Generating the Poly1305 key using ChaCha20 . . . . . . . . 13
2.7. AEAD Construction . . . . . . . . . . . . . . . . . . . . 14 2.7. AEAD Construction . . . . . . . . . . . . . . . . . . . . 14
2.7.1. Example and Test Vector for AEAD_CHACHA20-POLY1305 . . 15 2.7.1. Example and Test Vector for AEAD_CHACHA20-POLY1305 . . 15
3. Implementation Advice . . . . . . . . . . . . . . . . . . . . 17 3. Implementation Advice . . . . . . . . . . . . . . . . . . . . 17
4. Security Considerations . . . . . . . . . . . . . . . . . . . 17 4. Security Considerations . . . . . . . . . . . . . . . . . . . 18
5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 19 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 19
6. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 19 6. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 19
7. References . . . . . . . . . . . . . . . . . . . . . . . . . . 19 7. References . . . . . . . . . . . . . . . . . . . . . . . . . . 19
7.1. Normative References . . . . . . . . . . . . . . . . . . . 19 7.1. Normative References . . . . . . . . . . . . . . . . . . . 19
7.2. Informative References . . . . . . . . . . . . . . . . . . 19 7.2. Informative References . . . . . . . . . . . . . . . . . . 19
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 20 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 20
1. Introduction 1. Introduction
The Advanced Encryption Standard (AES - [FIPS-197]) has become the The Advanced Encryption Standard (AES - [FIPS-197]) has become the
gold standard in encryption. Its efficient design, wide gold standard in encryption. Its efficient design, wide
implementation, and hardware support allow for high performance in implementation, and hardware support allow for high performance in
many areas. On most modern platforms, AES is anywhere from 4x to 10x many areas. On most modern platforms, AES is anywhere from 4x to 10x
as fast as the previous most-used cipher, 3-key Data Encryption as fast as the previous most-used cipher, 3-key Data Encryption
Standard (3DES - [FIPS-46]), which makes it not only the best choice, Standard (3DES - [FIPS-46]), which makes it not only the best choice,
but the only choice. but the only choice.
skipping to change at page 6, line 22 skipping to change at page 6, line 22
Note that only the numbers in positions 2, 7, 8, and 13 changed. Note that only the numbers in positions 2, 7, 8, and 13 changed.
2.3. The ChaCha20 block Function 2.3. The ChaCha20 block Function
The ChaCha block function transforms a ChaCha state by running The ChaCha block function transforms a ChaCha state by running
multiple quarter rounds. multiple quarter rounds.
The inputs to ChaCha20 are: The inputs to ChaCha20 are:
o A 256-bit key, treated as a concatenation of 8 32-bit little- o A 256-bit key, treated as a concatenation of 8 32-bit little-
endian integers. endian integers.
o A 32-bit sender ID, treated as a little-endian integer. o A 96-bit nonce, treated as a concatenation of 3 32-bit little-
o A 64-bit nonce, treated as a concatenation of 2 32-bit little-
endian integers. endian integers.
o A 32-bit block count parameter, treated as a 32-bit little-endian o A 32-bit block count parameter, treated as a 32-bit little-endian
integer. integer.
The output is 64 random-looking bytes. The output is 64 random-looking bytes.
The ChaCha algorithm described here uses a 256-bit key. The original The ChaCha algorithm described here uses a 256-bit key. The original
algorithm also specified 128-bit keys and 8- and 12-round variants, algorithm also specified 128-bit keys and 8- and 12-round variants,
but these are out of scope for this document. In this section we but these are out of scope for this document. In this section we
describe the ChaCha block function. describe the ChaCha block function.
Note also that the original ChaCha had a 64-bit nonce and 64-bit
block count. We have modified this here to be more consistent with
recommendations in section 3.2 of [RFC5116]. This limits the use of
a single (key,nonce) combination to 2^32 blocks, or 256 GB, but that
is enough for most uses. In cases where a single key is used by
multiple senders, it is important to make sure that they don't use
the same nonces. This can be assured by partitioning the nonce space
so that the first 32 bits are unique per sender, while the other 64
bits come from a counter.
The ChaCha20 as follows: The ChaCha20 as follows:
o The first 4 words (0-3) are constants: 0x61707865, 0x3320646e, o The first 4 words (0-3) are constants: 0x61707865, 0x3320646e,
0x79622d32, 0x6b206574. 0x79622d32, 0x6b206574.
o The next 8 words (4-11) are taken from the 256-bit key by reading o The next 8 words (4-11) are taken from the 256-bit key by reading
the bytes in little-endian order, in 4-byte chunks. the bytes in little-endian order, in 4-byte chunks.
o Word 12 is a block counter. Since each block is 64-byte, a 32-bit o Word 12 is a block counter. Since each block is 64-byte, a 32-bit
word is enough for 256 Gigabytes of data. word is enough for 256 Gigabytes of data.
o Word 13 is called Sender ID, or SID. Note that in the original
ChaCha20 word 13 is also part of the block count, in case the o Words 13-15 are a nonce, which should not be repeated for the same
encrypted data exceeds 256 gigabytes. That is not necessary for key. The 13th word is the first 32 bits of the input nonce taken
protocols such as TLS, IPsec, or SSH. as a little-endian integer, while the 15th word is the last 32
o Words 14-15 are a nonce, which should not be repeated for the same bits.
combination of key and sender ID. The 14th word is the least
significant 32 bits of the input nonce (nonce & 0xffffffff), while cccccccc cccccccc cccccccc cccccccc
the 15th word is the most significant 32 bits (nonce >> 32). kkkkkkkk kkkkkkkk kkkkkkkk kkkkkkkk
kkkkkkkk kkkkkkkk kkkkkkkk kkkkkkkk
bbbbbbbb nnnnnnnn nnnnnnnn nnnnnnnn
c=constant k=key b=blockcount n=nonce
ChaCha20 runs 20 rounds, alternating between "column" and "diagonal" ChaCha20 runs 20 rounds, alternating between "column" and "diagonal"
rounds. Each round is 4 quarter-rounds, and they are run as follows. rounds. Each round is 4 quarter-rounds, and they are run as follows.
Rounds 1-4 are part of the "column" round, while 5-8 are part of the Rounds 1-4 are part of the "column" round, while 5-8 are part of the
"diagonal" round: "diagonal" round:
1. QUARTERROUND ( 0, 4, 8,12) 1. QUARTERROUND ( 0, 4, 8,12)
2. QUARTERROUND ( 1, 5, 9,13) 2. QUARTERROUND ( 1, 5, 9,13)
3. QUARTERROUND ( 2, 6,10,14) 3. QUARTERROUND ( 2, 6,10,14)
4. QUARTERROUND ( 3, 7,11,15) 4. QUARTERROUND ( 3, 7,11,15)
5. QUARTERROUND ( 0, 5,10,15) 5. QUARTERROUND ( 0, 5,10,15)
6. QUARTERROUND ( 1, 6,11,12) 6. QUARTERROUND ( 1, 6,11,12)
7. QUARTERROUND ( 2, 7, 8,13) 7. QUARTERROUND ( 2, 7, 8,13)
8. QUARTERROUND ( 3, 4, 9,14) 8. QUARTERROUND ( 3, 4, 9,14)
skipping to change at page 7, line 28 skipping to change at page 7, line 42
one-by-one in little-endian order. one-by-one in little-endian order.
2.3.1. Test Vector for the ChaCha20 Block Function 2.3.1. Test Vector for the ChaCha20 Block Function
For a test vector, we will use the following inputs to the ChaCha20 For a test vector, we will use the following inputs to the ChaCha20
block function: block function:
o Key = 00:01:02:03:04:05:06:07:08:09:0a:0b:0c:0d:0e:0f:10:11:12:13: o Key = 00:01:02:03:04:05:06:07:08:09:0a:0b:0c:0d:0e:0f:10:11:12:13:
14:15:16:17:18:19:1a:1b:1c:1d:1e:1f. The key is a sequence of 14:15:16:17:18:19:1a:1b:1c:1d:1e:1f. The key is a sequence of
octets with no particular structure before we copy it into the octets with no particular structure before we copy it into the
ChaCha state. ChaCha state.
o Nonce = 74 (00:00:00:00:00:00:00:4a) o Nonce = (00:00:00:09:00:00:00:4a:00:00:00:00)
o Sender ID = 00:00:00:09. Usually this will be all zeros, but
we've set it to non-zero here so it will be visually conspicuous.
o Block Count = 1. o Block Count = 1.
After setting up the ChaCha state, it looks like this: After setting up the ChaCha state, it looks like this:
ChaCha State with the key set up. ChaCha State with the key set up.
61707865 3320646e 79622d32 6b206574 61707865 3320646e 79622d32 6b206574
03020100 07060504 0b0a0908 0f0e0d0c 03020100 07060504 0b0a0908 0f0e0d0c
13121110 17161514 1b1a1918 1f1e1d1c 13121110 17161514 1b1a1918 1f1e1d1c
00000001 09000000 4a000000 00000000 00000001 09000000 4a000000 00000000
skipping to change at page 8, line 19 skipping to change at page 8, line 31
c7f4d1c7 0368c033 9aaa2204 4e6cd4c3 c7f4d1c7 0368c033 9aaa2204 4e6cd4c3
466482d2 09aa9f07 05d7c214 a2028bd9 466482d2 09aa9f07 05d7c214 a2028bd9
d19c12b5 b94e16de e883d0cb 4e3c50a2 d19c12b5 b94e16de e883d0cb 4e3c50a2
2.4. The ChaCha20 encryption algorithm 2.4. The ChaCha20 encryption algorithm
ChaCha20 is a stream cipher designed by D. J. Bernstein. It is a ChaCha20 is a stream cipher designed by D. J. Bernstein. It is a
refinement of the Salsa20 algorithm, and uses a 256-bit key. refinement of the Salsa20 algorithm, and uses a 256-bit key.
ChaCha20 successively calls the ChaCha20 block function, with the ChaCha20 successively calls the ChaCha20 block function, with the
same key, sender ID and nonce, and with successively increasing block same key and nonce, and with successively increasing block counter
counter parameters. The resulting state is then serialized by parameters. The resulting state is then serialized by writing the
writing the numbers in little-endian order. Concatenating the numbers in little-endian order. Concatenating the results from the
results from the successive blocks forms a key stream, which is then successive blocks forms a key stream, which is then XOR-ed with the
XOR-ed with the plaintext. There is no requirement for the plaintext plaintext. There is no requirement for the plaintext to be an
to be an integral multiple of 512-bits. If there is extra keystream integral multiple of 512-bits. If there is extra keystream from the
from the last block, it is discarded. Specific protocols MAY require last block, it is discarded. Specific protocols MAY require that the
that the plaintext and ciphertext have certain length. Such plaintext and ciphertext have certain length. Such protocols need to
protocols need to specify how the plaintext is padded, and how much specify how the plaintext is padded, and how much padding it
padding it receives. receives.
The inputs to ChaCha20 are: The inputs to ChaCha20 are:
o A 256-bit key o A 256-bit key
o A 32-bit sender ID. Ordinarily, this will be zero. However, in
protocols that allow multiple senders for the same keys, different
sender IDs MAY be used.
o A 32-bit initial counter. This can be set to any number, but will o A 32-bit initial counter. This can be set to any number, but will
usually be zero or one. It makes sense to use 1 if we use the usually be zero or one. It makes sense to use 1 if we use the
zero block for something else, such as generating a one-time zero block for something else, such as generating a one-time
authenticator key as part of an AEAD algorithm. authenticator key as part of an AEAD algorithm.
o A 64-bit nonce. In some protocols, this is known as the Initial o A 96-bit nonce. In some protocols, this is known as the
Vector. Initialization Vector.
o an arbitrary-length plaintext o an arbitrary-length plaintext
The output is an encrypted message of the same length. The output is an encrypted message of the same length.
2.4.1. Example and Test Vector for the ChaCha20 Cipher 2.4.1. Example and Test Vector for the ChaCha20 Cipher
For a test vector, we will use the following inputs to the ChaCha20 For a test vector, we will use the following inputs to the ChaCha20
block function: block function:
o Key = 00:01:02:03:04:05:06:07:08:09:0a:0b:0c:0d:0e:0f:10:11:12:13: o Key = 00:01:02:03:04:05:06:07:08:09:0a:0b:0c:0d:0e:0f:10:11:12:13:
14:15:16:17:18:19:1a:1b:1c:1d:1e:1f. 14:15:16:17:18:19:1a:1b:1c:1d:1e:1f.
o Nonce = (00:00:00:00:00:00:00:4a:00:00:00:00).
o Nonce = 74 (00:00:00:00:00:00:00:4a).
o Sender ID = zero (0).
o Initial Counter = 1. o Initial Counter = 1.
We use the following for the plaintext. It was chosen to be long We use the following for the plaintext. It was chosen to be long
enough to require more than one block, but not so long that it would enough to require more than one block, but not so long that it would
make this example cumbersome (so, less than 3 blocks): make this example cumbersome (so, less than 3 blocks):
Plaintext Sunscreen: Plaintext Sunscreen:
000 4c 61 64 69 65 73 20 61 6e 64 20 47 65 6e 74 6c|Ladies and Gentl 000 4c 61 64 69 65 73 20 61 6e 64 20 47 65 6e 74 6c|Ladies and Gentl
016 65 6d 65 6e 20 6f 66 20 74 68 65 20 63 6c 61 73|emen of the clas 016 65 6d 65 6e 20 6f 66 20 74 68 65 20 63 6c 61 73|emen of the clas
032 73 20 6f 66 20 27 39 39 3a 20 49 66 20 49 20 63|s of '99: If I c 032 73 20 6f 66 20 27 39 39 3a 20 49 66 20 49 20 63|s of '99: If I c
skipping to change at page 10, line 47 skipping to change at page 11, line 6
The original article ([poly1305]) is entitled "The Poly1305-AES The original article ([poly1305]) is entitled "The Poly1305-AES
message-authentication code", and the MAC function there requires a message-authentication code", and the MAC function there requires a
128-bit AES key, a 128-bit "additional key", and a 128-bit (non- 128-bit AES key, a 128-bit "additional key", and a 128-bit (non-
secret) nonce. AES is used there for encrypting the nonce, so as to secret) nonce. AES is used there for encrypting the nonce, so as to
get a unique (and secret) 128-bit string, but as the paper states, get a unique (and secret) 128-bit string, but as the paper states,
"There is nothing special about AES here. One can replace AES with "There is nothing special about AES here. One can replace AES with
an arbitrary keyed function from an arbitrary set of nonces to 16- an arbitrary keyed function from an arbitrary set of nonces to 16-
byte strings.". byte strings.".
Regardless of how the key is generated, the key is partitioned into Regardless of how the key is generated, the key is partitioned into
two parts, called "r" and "k". "k" MUST be unique and secret for each two parts, called "r" and "s". The pair (r,s) should be unique, and
invocation (that is why it was originally obtained by encrypting a MUST be unpredictable for each invocation (that is why it was
nonce), while "r" MAY be constant, but needs to be modified as originally obtained by encrypting a nonce), while "r" MAY be
follows before being used: ("r" is treated as a 16-octet little- constant, but needs to be modified as follows before being used: ("r"
endian number): is treated as a 16-octet little-endian number):
o r[3], r[7], r[11], and r[15] are required to have their top four o r[3], r[7], r[11], and r[15] are required to have their top four
bits clear (be smaller than 16) bits clear (be smaller than 16)
o r[4], r[8], and r[12] are required to have their bottom two bits o r[4], r[8], and r[12] are required to have their bottom two bits
clear (be divisible by 4) clear (be divisible by 4)
The following sample code clamps "r" to be appropriate. Note that The following sample code clamps "r" to be appropriate:
the parameter is a 32-byte key, and "r" is considered to be at offset
16, so it's the 2nd half of the key:
/* /*
poly1305aes_test_clamp.c version 20050207 Adapted from poly1305aes_test_clamp.c version 20050207
D. J. Bernstein D. J. Bernstein
Public domain. Public domain.
*/ */
#include "poly1305aes_test.h" #include "poly1305aes_test.h"
void poly1305aes_test_clamp(unsigned char kr[32]) void poly1305aes_test_clamp(unsigned char r[16])
{ {
#define r (kr + 16)
r[3] &= 15; r[3] &= 15;
r[7] &= 15; r[7] &= 15;
r[11] &= 15; r[11] &= 15;
r[15] &= 15; r[15] &= 15;
r[4] &= 252; r[4] &= 252;
r[8] &= 252; r[8] &= 252;
r[12] &= 252; r[12] &= 252;
} }
The "k" portion MUST NOT be re-used, but it is perfectly acceptable The "s" should be unpredictable, but it is perfectly acceptable to
to generate both "k" and "r" uniquely each time. Because each of generate both "r" and "s" uniquely each time. Because each of them
them is 128-bit, randomly generating them (see Section 2.6) is also is 128-bit, pseudo-randomly generating them (see Section 2.6) is also
acceptable. acceptable.
The inputs to Poly1305 are: The inputs to Poly1305 are:
o A 256-bit one-time key o A 256-bit one-time key
o An arbitrary length message o An arbitrary length message
The output is a 128-bit tag. The output is a 128-bit tag.
First, the "r" value should be clamped. First, the "r" value should be clamped.
Next, set the constant "P" (for "polynomial") be 2^130-5: Next, set the constant prime "P" be 2^130-5:
3fffffffffffffffffffffffffffffffb. Also set a variable "accumulator" 3fffffffffffffffffffffffffffffffb. Also set a variable "accumulator"
to zero. to zero.
Next, divide the message into 16-byte blocks. The last one might be Next, divide the message into 16-byte blocks. The last one might be
shorter: shorter:
o Read the block as a little-endian number. o Read the block as a little-endian number.
o Add one bit beyond the number of octets. For a 16-byte block this o Add one bit beyond the number of octets. For a 16-byte block this
is equivalent to adding 2^128 to the number. For the shorter is equivalent to adding 2^128 to the number. For the shorter
block it can be 2^120, 2^112, or any power of two that is evenly block it can be 2^120, 2^112, or any power of two that is evenly
divisible by 8, all the way down to 2^8. divisible by 8, all the way down to 2^8.
o If the block is not 17 bytes long (the last block), pad it with o If the block is not 17 bytes long (the last block), pad it with
zeros. This is meaningless if you're treating it them as numbers. zeros. This is meaningless if you're treating it them as numbers.
o Add this number to the accumulator. o Add this number to the accumulator.
o Multiply by "r" o Multiply by "r"
o Set the accumulator to the result modulu p. To summarize: Acc = o Set the accumulator to the result modulo p. To summarize: Acc =
((Acc+block)*r) % p. ((Acc+block)*r) % p.
Finally, the value of the secret key "k" is added to the accumulator, Finally, the value of the secret key "s" is added to the accumulator,
and the 128 least significant bits are serialized in little-endian and the 128 least significant bits are serialized in little-endian
order to form the tag. order to form the tag.
2.5.1. Poly1305 Example and Test Vector 2.5.1. Poly1305 Example and Test Vector
For our example, we will dispense with generating the one-time key For our example, we will dispense with generating the one-time key
using AES, and assume that we got the following keying material: using AES, and assume that we got the following keying material:
o Key Material: 85:d6:be:78:57:55:6d:33:7f:44:52:fe:42:d5:06:a8:01: o Key Material: 85:d6:be:78:57:55:6d:33:7f:44:52:fe:42:d5:06:a8:01:
03:80:8a:fb:0d:b2:fd:4a:bf:f6:af:41:49:f5:1b 03:80:8a:fb:0d:b2:fd:4a:bf:f6:af:41:49:f5:1b
o k as an octet string: 01:03:80:8a:fb:0d:b2:fd:4a:bf:f6:af:41:49: o s as an octet string: 01:03:80:8a:fb:0d:b2:fd:4a:bf:f6:af:41:49:
f5:1b f5:1b
o k as a 128-bit number: 1BF54941AFF6BF4AFDB20DFB8A800301 o s as a 128-bit number: 1bf54941aff6bf4afdb20dfb8a800301
o r before clamping: 85:d6:be:78:57:55:6d:33:7f:44:52:fe:42:d5:06:a8 o r before clamping: 85:d6:be:78:57:55:6d:33:7f:44:52:fe:42:d5:06:a8
o Clamped r as a number: 806D5400E52447C036D555408BED685. o Clamped r as a number: 806d5400e52447c036d555408bed685.
For our message, we'll use a short text: For our message, we'll use a short text:
Message to be Authenticated: Message to be Authenticated:
000 43 72 79 70 74 6f 67 72 61 70 68 69 63 20 46 6f|Cryptographic Fo 000 43 72 79 70 74 6f 67 72 61 70 68 69 63 20 46 6f|Cryptographic Fo
016 72 75 6d 20 52 65 73 65 61 72 63 68 20 47 72 6f|rum Research Gro 016 72 75 6d 20 52 65 73 65 61 72 63 68 20 47 72 6f|rum Research Gro
032 75 70 |up 032 75 70 |up
Since Poly1305 works in 16-byte chunks, the 34-byte message divides Since Poly1305 works in 16-byte chunks, the 34-byte message divides
into 3 blocks. In the following calculation, "Acc" denotes the into 3 blocks. In the following calculation, "Acc" denotes the
accumulator and "Block" the current block: accumulator and "Block" the current block:
Block #1 Block #1
Acc = 00 Acc = 00
Block = 6f4620636968706172676f7470797243 Block = 6f4620636968706172676f7470797243
Block with 0x01 byte = 016f4620636968706172676f7470797243 Block with 0x01 byte = 016f4620636968706172676f7470797243
Acc + block = 016f4620636968706172676f7470797243 Acc + block = 016f4620636968706172676f7470797243
(Acc+Block) * r = (Acc+Block) * r =
B83FE991CA66800489155DCD69E8426BA2779453994AC90ED284034DA565ECF b83fe991ca66800489155dcd69e8426ba2779453994ac90ed284034da565ecf
Acc = ((Acc+Block)*r) % P = 2C88C77849D64AE9147DDEB88E69C83FC Acc = ((Acc+Block)*r) % P = 2c88c77849d64ae9147ddeb88e69c83fc
Block #2 Block #2
Acc = 2C88C77849D64AE9147DDEB88E69C83FC Acc = 2c88c77849d64ae9147ddeb88e69c83fc
Block = 6f7247206863726165736552206d7572 Block = 6f7247206863726165736552206d7572
Block with 0x01 byte = 016f7247206863726165736552206d7572 Block with 0x01 byte = 016f7247206863726165736552206d7572
Acc + block = 437FEBEA505C820F2AD5150DB0709F96E Acc + block = 437febea505c820f2ad5150db0709f96e
(Acc+Block) * r = (Acc+Block) * r =
21DCC992D0C659BA4036F65BB7F88562AE59B32C2B3B8F7EFC8B00F78E548A26 21dcc992d0c659ba4036f65bb7f88562ae59b32c2b3b8f7efc8b00f78e548a26
Acc = ((Acc+Block)*r) % P = 2D8ADAF23B0337FA7CCCFB4EA344B30DE Acc = ((Acc+Block)*r) % P = 2d8adaf23b0337fa7cccfb4ea344b30de
Last Block Last Block
Acc = 2D8ADAF23B0337FA7CCCFB4EA344B30DE Acc = 2d8adaf23b0337fa7cccfb4ea344b30de
Block = 7075 Block = 7075
Block with 0x01 byte = 017075 Block with 0x01 byte = 017075
Acc + block = 2D8ADAF23B0337FA7CCCFB4EA344CA153 Acc + block = 2d8adaf23b0337fa7cccfb4ea344ca153
(Acc + Block) * r = (Acc + Block) * r =
16D8E08A0F3FE1DE4FE4A15486ACA7A270A29F1E6C849221E4A6798B8E45321F 16d8e08a0f3fe1de4fe4a15486aca7a270a29f1e6c849221e4a6798b8e45321f
((Acc + Block) * r) % P = 28D31B7CAFF946C77C8844335369D03A7 ((Acc + Block) * r) % P = 28d31b7caff946c77c8844335369d03a7
Adding k we get this number, and serialize if to get the tag: Adding s we get this number, and serialize if to get the tag:
Acc + k = 2A927010CAF8B2BC2C6365130C11D06A8 Acc + s = 2a927010caf8b2bc2c6365130c11d06a8
Tag: a8:06:1d:c1:30:51:36:c6:c2:2b:8b:af:0c:01:27:a9 Tag: a8:06:1d:c1:30:51:36:c6:c2:2b:8b:af:0c:01:27:a9
2.6. Generating the Poly1305 key using ChaCha20 2.6. Generating the Poly1305 key using ChaCha20
As said in Section 2.5, it is acceptable to generate the one-time As said in Section 2.5, it is acceptable to generate the one-time
Poly1305 pseudo-randomly. This section proposes such a method. Poly1305 pseudo-randomly. This section proposes such a method.
To generate such a key pair (k,r), we will use the ChaCha20 block To generate such a key pair (r,s), we will use the ChaCha20 block
function described in Section 2.3. This assumes that we have a 256- function described in Section 2.3. This assumes that we have a 256-
bit session key for the MAC function, such as SK_ai and SK_ar in bit session key for the MAC function, such as SK_ai and SK_ar in
IKEv2, the integrity key in ESP and AH, or the client_write_MAC_key IKEv2, the integrity key in ESP and AH, or the client_write_MAC_key
and server_write_MAC_key in TLS. Any document that specifies the use and server_write_MAC_key in TLS. Any document that specifies the use
of Poly1305 as a MAC algorithm for some protocol must specify that of Poly1305 as a MAC algorithm for some protocol must specify that
256 bits are allocated for the integrity key. 256 bits are allocated for the integrity key.
The method is to call the block function with the following The method is to call the block function with the following
parameters: parameters:
o The 256-bit session integrity key is used as the ChaCha20 key. o The 256-bit session integrity key is used as the ChaCha20 key.
o The specific protocol specifies the sender ID, but for any sender,
all calls are made with the same sender ID. Usually, this will be
set to zero. For the AEAD protocol specified in Section 2.7, the
sender ID is set to the same value as for the encryption.
o The block counter is set to zero. o The block counter is set to zero.
o The protocol will specify a 64-bit nonce. This MUST be unique per o The protocol will specify a 96-bit or 64-bit nonce. This MUST be
invocation with the same key, so it MUST NOT be randomly unique per invocation with the same key, so it MUST NOT be
generated. A counter is a good way to implement this, but other randomly generated. A counter is a good way to implement this,
methods, such as an LFSR are also acceptable. but other methods, such as an LFSR are also acceptable. ChaCha20
as specified here requires a 96-bit nonce. So if the provided
nonce is only 64-bit, then the first 32 bits of the nonce will be
set to a constant number. This will usually be zero, but for
protocols with multiple sender, it may be different for each
sender, but should be the same for all invocations of the function
with the same key by a particular sender.
After running the block function, we have a 512-bit state. We take After running the block function, we have a 512-bit state. We take
the first 256 bits or the serialized state, and use those as the one- the first 256 bits or the serialized state, and use those as the one-
time Poly1305 key. The other 256 bits are discarded. time Poly1305 key: The first 128 bits are clamped, and form "r",
while the next 128 bits become "s". The other 256 bits are
discarded.
Note that while many protocols have provisions for a nonce for Note that while many protocols have provisions for a nonce for
encryption algorithms (often called Initialization Vectors, or IVs), encryption algorithms (often called Initialization Vectors, or IVs),
they usually don't have such a provision for the MAC function. In they usually don't have such a provision for the MAC function. In
that case the per-invocation nonce will have to come from somewhere that case the per-invocation nonce will have to come from somewhere
else, such as a message counter. else, such as a message counter.
2.7. AEAD Construction 2.7. AEAD Construction
Note: Much of the content of this document, including this AEAD Note: Much of the content of this document, including this AEAD
construction is taken from Adam Langley's draft ([agl-draft]) for the construction is taken from Adam Langley's draft ([agl-draft]) for the
use of these algorithms in TLS. The AEAD construction described here use of these algorithms in TLS. The AEAD construction described here
is called AEAD_CHACHA20-POLY1305. is called AEAD_CHACHA20-POLY1305.
AEAD_CHACHA20-POLY1305 is an authenticated encryption with additional AEAD_CHACHA20-POLY1305 is an authenticated encryption with additional
data algorithm. The inputs to AEAD_CHACHA20-POLY1305 are: data algorithm. The inputs to AEAD_CHACHA20-POLY1305 are:
o A 256-bit key o A 256-bit key
o A 32-bit sender ID o A 96-bit nonce - different for each invocation with the same key.
o A 64-bit nonce - different for each invocation with the
combination of key and sender ID.
o An arbitrary length plaintext o An arbitrary length plaintext
o Arbitrary length additional data o Arbitrary length additional data
The ChaCha20 and Poly1305 primitives are combined into an AEAD that The ChaCha20 and Poly1305 primitives are combined into an AEAD that
takes a 256-bit key and 64-bit IV as follows: takes a 256-bit key and 64-bit IV as follows:
o First, a Poly1305 one-time key is generated from the 256-bit key, o First the 96-bit nonce is constructed by prepending a 32-bit
sender ID and nonce using the procedure described in Section 2.6. constant value to the IV. This could be set to zero, or could be
derived from keying material, or could be assigned to a sender.
It is up to the specific protocol to define the source for that
32-bit value.
o Next, a Poly1305 one-time key is generated from the 256-bit key
and nonce using the procedure described in Section 2.6.
o The ChaCha20 encryption function is called to encrypt the o The ChaCha20 encryption function is called to encrypt the
plaintext, using the same key, sender ID, nonce and plaintext, and plaintext, using the same key and nonce, and with the initial
with the initial counter set to 1. counter set to 1.
o The Poly1305 function is called with the Poly1305 key calculated o The Poly1305 function is called with the Poly1305 key calculated
above, and a message constructed as a concatenation of the above, and a message constructed as a concatenation of the
following: following:
* The additional data * The additional data
* The length of the additional data in octets (as a 64-bit * The length of the additional data in octets (as a 64-bit
little-endian integer). TBD: bit count rather than octets? little-endian integer). TBD: bit count rather than octets?
network order? network order?
* The ciphertext * The ciphertext
* The length of the ciphertext in octets (as a 64-bit little- * The length of the ciphertext in octets (as a 64-bit little-
endian integer). TBD: bit count rather than octets? network endian integer). TBD: bit count rather than octets? network
order? order?
Decryption is pretty much the same thing. Decryption is pretty much the same thing.
The output from the AEAD is twofold: The output from the AEAD is twofold:
o A ciphertext of the same length as the plaintext. o A ciphertext of the same length as the plaintext.
o A 128-bit tag (the result of the Poly1305 function. o A 128-bit tag, which is the output of the Poly1305 function.
A few notes about this design: A few notes about this design:
1. The amount of encrypted data possible in a single invocation is 1. The amount of encrypted data possible in a single invocation is
2^32-1 blocks of 64 bytes each, for a total of 247,877,906,880 2^32-1 blocks of 64 bytes each, for a total of 247,877,906,880
bytes, or nearly 256 GB. This should be enough for traffic bytes, or nearly 256 GB. This should be enough for traffic
protocols such as IPsec and TLS, but may be too small for file protocols such as IPsec and TLS, but may be too small for file
and/or disk encryption. For such uses, we can return to the and/or disk encryption. For such uses, we can return to the
original design, eliminate the Sender ID parameter, and use the original design, reduce the nonce to 64 bits, and use the integer
integer at position 13 as the top 32 bits of a 64-bit block at position 13 as the top 32 bits of a 64-bit block counter,
counter, increasing the total message size to over a million increasing the total message size to over a million petabytes
petabytes (1,180,591,620,717,411,303,360 bytes to be exact). (1,180,591,620,717,411,303,360 bytes to be exact).
2. Despite the previous item, the ciphertext length field in the 2. Despite the previous item, the ciphertext length field in the
construction of the buffer on which Poly1305 runs limits the construction of the buffer on which Poly1305 runs limits the
ciphertext (and hence, the plaintext) size to 2^64 bytes, or ciphertext (and hence, the plaintext) size to 2^64 bytes, or
sixteen thousand petabytes (18,446,744,073,709,551,616 bytes to sixteen thousand petabytes (18,446,744,073,709,551,616 bytes to
be exact). be exact).
3. TBD: perhaps we allocate only 6 bits for sender ID, leaving 58
bits for block counter, which means the maximum number of blocks
is just enough to fill the 64-bit octet counter.
2.7.1. Example and Test Vector for AEAD_CHACHA20-POLY1305 2.7.1. Example and Test Vector for AEAD_CHACHA20-POLY1305
For a test vector, we will use the following inputs to the For a test vector, we will use the following inputs to the
AEAD_CHACHA20-POLY1305 function: AEAD_CHACHA20-POLY1305 function:
Plaintext: Plaintext:
000 4c 61 64 69 65 73 20 61 6e 64 20 47 65 6e 74 6c|Ladies and Gentl 000 4c 61 64 69 65 73 20 61 6e 64 20 47 65 6e 74 6c|Ladies and Gentl
016 65 6d 65 6e 20 6f 66 20 74 68 65 20 63 6c 61 73|emen of the clas 016 65 6d 65 6e 20 6f 66 20 74 68 65 20 63 6c 61 73|emen of the clas
032 73 20 6f 66 20 27 39 39 3a 20 49 66 20 49 20 63|s of '99: If I c 032 73 20 6f 66 20 27 39 39 3a 20 49 66 20 49 20 63|s of '99: If I c
048 6f 75 6c 64 20 6f 66 66 65 72 20 79 6f 75 20 6f|ould offer you o 048 6f 75 6c 64 20 6f 66 66 65 72 20 79 6f 75 20 6f|ould offer you o
064 6e 6c 79 20 6f 6e 65 20 74 69 70 20 66 6f 72 20|nly one tip for 064 6e 6c 79 20 6f 6e 65 20 74 69 70 20 66 6f 72 20|nly one tip for
080 74 68 65 20 66 75 74 75 72 65 2c 20 73 75 6e 73|the future, suns 080 74 68 65 20 66 75 74 75 72 65 2c 20 73 75 6e 73|the future, suns
096 63 72 65 65 6e 20 77 6f 75 6c 64 20 62 65 20 69|creen would be i 096 63 72 65 65 6e 20 77 6f 75 6c 64 20 62 65 20 69|creen would be i
112 74 2e |t. 112 74 2e |t.
AAD:
000 50 51 52 53 c0 c1 c2 c3 c4 c5 c6 c7 PQRS........
Key: Key:
000 80 81 82 83 84 85 86 87 88 89 8a 8b 8c 8d 8e 8f|................ 000 80 81 82 83 84 85 86 87 88 89 8a 8b 8c 8d 8e 8f|................
016 90 91 92 93 94 95 96 97 98 99 9a 9b 9c 9d 9e 9f|................ 016 90 91 92 93 94 95 96 97 98 99 9a 9b 9c 9d 9e 9f|................
IV: IV:
000 40 41 42 43 44 45 46 47 @ABCDEFG 000 40 41 42 43 44 45 46 47 @ABCDEFG
32-bit fixed-common part:
000 07 00 00 00 ....
Set up for generating poly1305 one-time key (sender id=7): Set up for generating poly1305 one-time key (sender id=7):
61707865 3320646e 79622d32 6b206574 61707865 3320646e 79622d32 6b206574
83828180 87868584 8b8a8988 8f8e8d8c 83828180 87868584 8b8a8988 8f8e8d8c
93929190 97969594 9b9a9998 9f9e9d9c 93929190 97969594 9b9a9998 9f9e9d9c
00000000 00000007 43424140 47464544 00000000 00000007 43424140 47464544
After generating Poly1305 one-time key: After generating Poly1305 one-time key:
252bac7b af47b42d 557ab609 8455e9a4 252bac7b af47b42d 557ab609 8455e9a4
73d6e10a ebd97510 7875932a ff53d53e 73d6e10a ebd97510 7875932a ff53d53e
decc7ea2 b44ddbad e49c17d1 d8430bc9 decc7ea2 b44ddbad e49c17d1 d8430bc9
8c94b7bc 8b7d4b4b 3927f67d 1669a432 8c94b7bc 8b7d4b4b 3927f67d 1669a432
Poly1305 Key: Poly1305 Key:
000 7b ac 2b 25 2d b4 47 af 09 b6 7a 55 a4 e9 55 84|{.+%-.G...zU..U. 000 7b ac 2b 25 2d b4 47 af 09 b6 7a 55 a4 e9 55 84|{.+%-.G...zU..U.
016 0a e1 d6 73 10 75 d9 eb 2a 93 75 78 3e d5 53 ff|...s.u..*.ux>.S. 016 0a e1 d6 73 10 75 d9 eb 2a 93 75 78 3e d5 53 ff|...s.u..*.ux>.S.
Poly1305 r = 455E9A4057AB6080F47B42C052BAC7B Poly1305 r = 455e9a4057ab6080f47b42c052bac7b
Poly1305 K = FF53D53E7875932AEBD9751073D6E10A Poly1305 s = ff53d53e7875932aebd9751073d6e10a
Keystream bytes: Keystream bytes:
9f:7b:e9:5d:01:fd:40:ba:15:e2:8f:fb:36:81:0a:ae: 9f:7b:e9:5d:01:fd:40:ba:15:e2:8f:fb:36:81:0a:ae:
c1:c0:88:3f:09:01:6e:de:dd:8a:d0:87:55:82:03:a5: c1:c0:88:3f:09:01:6e:de:dd:8a:d0:87:55:82:03:a5:
4e:9e:cb:38:ac:8e:5e:2b:b8:da:b2:0f:fa:db:52:e8: 4e:9e:cb:38:ac:8e:5e:2b:b8:da:b2:0f:fa:db:52:e8:
75:04:b2:6e:be:69:6d:4f:60:a4:85:cf:11:b8:1b:59: 75:04:b2:6e:be:69:6d:4f:60:a4:85:cf:11:b8:1b:59:
fc:b1:c4:5f:42:19:ee:ac:ec:6a:de:c3:4e:66:69:78: fc:b1:c4:5f:42:19:ee:ac:ec:6a:de:c3:4e:66:69:78:
8e:db:41:c4:9c:a3:01:e1:27:e0:ac:ab:3b:44:b9:cf: 8e:db:41:c4:9c:a3:01:e1:27:e0:ac:ab:3b:44:b9:cf:
5c:86:bb:95:e0:6b:0d:f2:90:1a:b6:45:e4:ab:e6:22: 5c:86:bb:95:e0:6b:0d:f2:90:1a:b6:45:e4:ab:e6:22:
15:38 15:38
skipping to change at page 17, line 7 skipping to change at page 17, line 25
000 d3 1a 8d 34 64 8e 60 db 7b 86 af bc 53 ef 7e c2|...4d.`.{...S.~. 000 d3 1a 8d 34 64 8e 60 db 7b 86 af bc 53 ef 7e c2|...4d.`.{...S.~.
016 a4 ad ed 51 29 6e 08 fe a9 e2 b5 a7 36 ee 62 d6|...Q)n......6.b. 016 a4 ad ed 51 29 6e 08 fe a9 e2 b5 a7 36 ee 62 d6|...Q)n......6.b.
032 3d be a4 5e 8c a9 67 12 82 fa fb 69 da 92 72 8b|=..^..g....i..r. 032 3d be a4 5e 8c a9 67 12 82 fa fb 69 da 92 72 8b|=..^..g....i..r.
048 1a 71 de 0a 9e 06 0b 29 05 d6 a5 b6 7e cd 3b 36|.q.....)....~.;6 048 1a 71 de 0a 9e 06 0b 29 05 d6 a5 b6 7e cd 3b 36|.q.....)....~.;6
064 92 dd bd 7f 2d 77 8b 8c 98 03 ae e3 28 09 1b 58|...-w......(..X 064 92 dd bd 7f 2d 77 8b 8c 98 03 ae e3 28 09 1b 58|...-w......(..X
080 fa b3 24 e4 fa d6 75 94 55 85 80 8b 48 31 d7 bc|..$...u.U...H1.. 080 fa b3 24 e4 fa d6 75 94 55 85 80 8b 48 31 d7 bc|..$...u.U...H1..
096 3f f4 de f0 8e 4b 7a 9d e5 76 d2 65 86 ce c6 4b|?....Kz..v.e...K 096 3f f4 de f0 8e 4b 7a 9d e5 76 d2 65 86 ce c6 4b|?....Kz..v.e...K
112 61 16 |a. 112 61 16 |a.
AEAD Construction for Poly1305: AEAD Construction for Poly1305:
000 50 51 52 53 0c 00 00 00 00 00 00 00 0c 00 00 00|PQRS............ 000 50 51 52 53 c0 c1 c2 c3 c4 c5 c6 c7 0c 00 00 00|PQRS............
016 00 00 00 00 d3 1a 8d 34 64 8e 60 db 7b 86 af bc|.......4d.`.{... 016 00 00 00 00 d3 1a 8d 34 64 8e 60 db 7b 86 af bc|.......4d.`.{...
032 53 ef 7e c2 a4 ad ed 51 29 6e 08 fe a9 e2 b5 a7|S.~....Q)n...... 032 53 ef 7e c2 a4 ad ed 51 29 6e 08 fe a9 e2 b5 a7|S.~....Q)n......
048 36 ee 62 d6 3d be a4 5e 8c a9 67 12 82 fa fb 69|6.b.=..^..g....i 048 36 ee 62 d6 3d be a4 5e 8c a9 67 12 82 fa fb 69|6.b.=..^..g....i
064 da 92 72 8b 1a 71 de 0a 9e 06 0b 29 05 d6 a5 b6|..r..q.....).... 064 da 92 72 8b 1a 71 de 0a 9e 06 0b 29 05 d6 a5 b6|..r..q.....)....
080 7e cd 3b 36 92 dd bd 7f 2d 77 8b 8c 98 03 ae e3|~.;6...-w...... 080 7e cd 3b 36 92 dd bd 7f 2d 77 8b 8c 98 03 ae e3|~.;6...-w......
096 28 09 1b 58 fa b3 24 e4 fa d6 75 94 55 85 80 8b|(..X..$...u.U... 096 28 09 1b 58 fa b3 24 e4 fa d6 75 94 55 85 80 8b|(..X..$...u.U...
112 48 31 d7 bc 3f f4 de f0 8e 4b 7a 9d e5 76 d2 65|H1..?....Kz..v.e 112 48 31 d7 bc 3f f4 de f0 8e 4b 7a 9d e5 76 d2 65|H1..?....Kz..v.e
128 86 ce c6 4b 61 16 72 00 00 00 00 00 00 00 |...Ka.r....... 128 86 ce c6 4b 61 16 72 00 00 00 00 00 00 00 |...Ka.r.......
Tag: Tag:
58:7f:5c:12:9f:27:f8:e9:2e:a7:e3:2d:9f:2a:76:f2 18:fb:11:a5:03:1a:d1:3a:7e:3b:03:d4:6e:e3:a6:a7
3. Implementation Advice 3. Implementation Advice
Each block of ChaCha20 involves 16 move operations and one increment Each block of ChaCha20 involves 16 move operations and one increment
operation for loading the state, 80 each of XOR, addition and Roll operation for loading the state, 80 each of XOR, addition and Roll
operations for the rounds, 16 more add operations and 16 XOR operations for the rounds, 16 more add operations and 16 XOR
operations for protecting the plaintext. Section 2.3 describes the operations for protecting the plaintext. Section 2.3 describes the
ChaCha block function as "adding the original input words". This ChaCha block function as "adding the original input words". This
implies that before starting the rounds on the ChaCha state, it is implies that before starting the rounds on the ChaCha state, it is
copied aside only to be added in later. This would be correct, but copied aside only to be added in later. This would be correct, but
it saves a few operations to instead copy the state and do the work it saves a few operations to instead copy the state and do the work
on the copy. This way, for the next block you don't need to recreate on the copy. This way, for the next block you don't need to recreate
the state, but only to increment the block counter. This saves the state, but only to increment the block counter. This saves
approximately 5.5% of the cycles. approximately 5.5% of the cycles.
It is NOT RECOMMENDED to use a generic big number library such as the It is NOT RECOMMENDED to use a generic big number library such as the
one in OpenSSL for the arithmetic operations in Poly1305. Such one in OpenSSL for the arithmetic operations in Poly1305. Such
libraries use dynamic allocation to be able to handle any-sized libraries use dynamic allocation to be able to handle any-sized
integer, but that flexibility comes at the expense of performance as integer, but that flexibility comes at the expense of performance as
well as side-channel security. More efficient implementations that well as side-channel security. More efficient implementations that
run in constant time are easy to find, and one is even available in run in constant time are available, one of them in DJB's own library,
[poly1305] paper (although DJB describes its performance as NaCl ([NaCl]).
"intolerable").
4. Security Considerations 4. Security Considerations
The ChaCha20 cipher is designed to provide 256-bit security. The ChaCha20 cipher is designed to provide 256-bit security.
The Poly1305 authenticator is designed to ensure that forged messages The Poly1305 authenticator is designed to ensure that forged messages
are rejected with a probability of 1-(n/(2^102)) for a 16n-byte are rejected with a probability of 1-(n/(2^102)) for a 16n-byte
message, even after sending 2^64 legitimate messages, so it is SUF- message, even after sending 2^64 legitimate messages, so it is SUF-
CMA in the terminology of [AE]. CMA in the terminology of [AE].
skipping to change at page 18, line 20 skipping to change at page 18, line 37
papers. papers.
The most important security consideration in implementing this draft The most important security consideration in implementing this draft
is the uniqueness of the nonce used in ChaCha20. Counters and LFSRs is the uniqueness of the nonce used in ChaCha20. Counters and LFSRs
are both acceptable ways of generating unique nonces, as is are both acceptable ways of generating unique nonces, as is
encrypting a counter using a 64-bit cipher such as DES. Note that it encrypting a counter using a 64-bit cipher such as DES. Note that it
is not acceptable to use a truncation of a counter encrypted with a is not acceptable to use a truncation of a counter encrypted with a
128-bit or 256-bit cipher, because such a truncation may repeat after 128-bit or 256-bit cipher, because such a truncation may repeat after
a short time. a short time.
The same kind of collision risk as in the above paragraph also exists The Poly1305 key MUST be unpredictable to an attacker. Randomly
in the selection of the Poly1305 key in both the AEAD construction generating the key would fulfill this requirement, except that
(Section 2.7). ChaCha20 is used to generate a 512-bit value, which Poly1305 is often used in communications protocols, so the receiver
is unique to each packet, but this uniqueness is not guaranteed for should know the key. Pseudo-random number generation such as by
its 256-bit truncation, which serves as the actual key for Poly1305. encrypting a counter is acceptable. Using ChaCha with a secret key
While uniqueness is not guaranteed, it is still very likely. and a nonce is also acceptable.
Birthday paradox calculations show that generating Poly1305 keys
needs to happen over 2^101 times (way more than the 2^64 allowed by
IPsec or TLS) to drive the chances of collision up to
0.00000000000001%. This is why we may safely ignore the possibility
of collision.
The algorithms presented here were designed to be easy to implement The algorithms presented here were designed to be easy to implement
in constant time to avoid side-channel vulnerabilities. The in constant time to avoid side-channel vulnerabilities. The
operations used in ChaCha20 are all additions, XORs, and fixed operations used in ChaCha20 are all additions, XORs, and fixed
rotations. All of these can and should be implemented in constant rotations. All of these can and should be implemented in constant
time. Access to offsets into the ChaCha state and the number of time. Access to offsets into the ChaCha state and the number of
operations do not depend on any property of the key, eliminating the operations do not depend on any property of the key, eliminating the
chance of information about the key leaking through the timing of chance of information about the key leaking through the timing of
cache misses. cache misses.
skipping to change at page 19, line 15 skipping to change at page 19, line 25
5. IANA Considerations 5. IANA Considerations
There are no IANA considerations for this document. There are no IANA considerations for this document.
6. Acknowledgements 6. Acknowledgements
None of the algorithms here are my own. ChaCha20 and Poly1305 were None of the algorithms here are my own. ChaCha20 and Poly1305 were
invented by Daniel J. Bernstein, and the AEAD construction was invented by Daniel J. Bernstein, and the AEAD construction was
invented by Adam Langley. invented by Adam Langley.
Much of the text in this document was inspired by Adam Langley's Thanks to Robert Ransom and Ilari Liusvaara for their helpful
draft for TLS, and by "inspired" I mean "shamelessly copied". The comments and explanations.
author would also like to thank Adam, Watson Ladd and Dave McGrew for
allaying his fears about writing a document describing crypto.
7. References 7. References
7.1. Normative References 7.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997. Requirement Levels", BCP 14, RFC 2119, March 1997.
[chacha] Bernstein, D., "ChaCha, a variant of Salsa20", Jan 2008. [chacha] Bernstein, D., "ChaCha, a variant of Salsa20", Jan 2008.
skipping to change at page 19, line 48 skipping to change at page 20, line 11
<http://cseweb.ucsd.edu/~mihir/papers/oem.html>. <http://cseweb.ucsd.edu/~mihir/papers/oem.html>.
[FIPS-197] [FIPS-197]
National Institute of Standards and Technology, "Advanced National Institute of Standards and Technology, "Advanced
Encryption Standard (AES)", FIPS PUB 197, November 2001. Encryption Standard (AES)", FIPS PUB 197, November 2001.
[FIPS-46] National Institute of Standards and Technology, "Data [FIPS-46] National Institute of Standards and Technology, "Data
Encryption Standard", FIPS PUB 46-2, December 1993, Encryption Standard", FIPS PUB 46-2, December 1993,
<http://www.itl.nist.gov/fipspubs/fip46-2.htm>. <http://www.itl.nist.gov/fipspubs/fip46-2.htm>.
[NaCl] Bernstein, D., Lange, T., and P. Schwabe, "NaCl:
Networking and Cryptography library",
<http://nacl.cace-project.eu/index.html>.
[RFC5116] McGrew, D., "An Interface and Algorithms for Authenticated
Encryption", RFC 5116, January 2008.
[agl-draft] [agl-draft]
Langley, A. and W. Chang, "ChaCha20 and Poly1305 based Langley, A. and W. Chang, "ChaCha20 and Poly1305 based
Cipher Suites for TLS", draft-agl-tls-chacha20poly1305-04 Cipher Suites for TLS", draft-agl-tls-chacha20poly1305-04
(work in progress), November 2013. (work in progress), November 2013.
[standby-cipher] [standby-cipher]
McGrew, D., Grieco, A., and Y. Sheffer, "Selection of McGrew, D., Grieco, A., and Y. Sheffer, "Selection of
Future Cryptographic Standards", Future Cryptographic Standards",
draft-mcgrew-standby-cipher (work in progress). draft-mcgrew-standby-cipher (work in progress).
Author's Address Authors' Addresses
Yoav Nir Yoav Nir
Check Point Software Technologies Ltd. Check Point Software Technologies Ltd.
5 Hasolelim st. 5 Hasolelim st.
Tel Aviv 6789735 Tel Aviv 6789735
Israel Israel
Email: synp71@live.com Email: synp71@live.com
Adam Langley
Google Inc
Email: agl@google.com
 End of changes. 61 change blocks. 
126 lines changed or deleted 134 lines changed or added

This html diff was produced by rfcdiff 1.48. The latest version is available from http://tools.ietf.org/tools/rfcdiff/