Subject: Re: [IPsec] Please review draft-ietf-ipsecme-chacha20-poly1305

From: "Valery Smyslov" <[email-masked]>
Date: Tue, 21 Apr 2015 19:19:39 +0300

Hi,

this is my review of draft-ietf-ipsecme-chacha20-poly1305-02.

I think that the draft is in a good shape. A few issues need to be resolved.

Technical issues.

1. For the question raised in the draft:

    TBD: do we want an extra 32 bits as salt for the nonce like
    in GCM, or keep the salt (=SenderID) at zero?

I prefer to follow GCM-like approach, i.e. to take these 32 bits
from the KEYMAT. It is cryptographically sound and is good
from evaluation point of view - you know where these bits come from.

I understand that it would require some adaptation
for multi-sender case, like in RFC6054, but AFAIK currently
Many-to-Many IPsec SAs are rare and look exotic.
And as RFC6054 states, the nonce is not transferred in packet,
so it is not the best place for SenderID (unlike explicit IV).

2. Section 4.

   When negotiating the ChaCha20-Poly1305 algorithm for use in IKE or
   IPsec, the value xxx (TBA by IANA) should be used in the transform
   substructure of the SA payload as the ENCR (type 1) transform ID.  As
   with other AEAD algorithms, INTEG (type 3) transform substructures
   SHOULD NOT be specified unless at least one of the ENCR transforms is
   non-AEAD.

The last sentence is wrong. Section 3.3 of RFC7296 states:

   Combined-mode ciphers include
   both integrity and encryption in a single encryption algorithm, and
   MUST either offer no integrity algorithm or a single integrity
   algorithm of "NONE", with no integrity algorithm being the
   RECOMMENDED method.

So INTEG either MUST NOT be present in the proposal substructure
containing ChaCha20-Poly1305 or MUST be NONE. And RFC7296
requires not to mix AEAD and non-AEAD algorithms in the same proposal:

   If an initiator wants to propose both combined-
   mode ciphers and normal ciphers, it must include two proposals: one
   will have all the combined-mode ciphers, and the other will have all
   the normal ciphers with the integrity algorithms.

Editorial issues.

1. Section 2, first bullet.

   o  The Initialization Vector (IV) is 64-bit, and is used as part of
      the nonce.  The IV MUST be unique for each SA but does not need to
      be unpredictable.  The use of a counter or an LFSR is RECOMMENDED.

The IV MUST be unique for each invocation (ESP packet or IKEv2 message),
not for each SA.

2. Section 2, last but one bullet:

      *  The length of the additional data in octets (as a 64-bit
         little-endian integer).

"additional data" is a bit vague, please use "Authenticated Additional Data"
(or "AAD") for clarity.

3. Informative References

   [FIPS-46]  National Institute of Standards and Technology, "Data
              Encryption Standard", FIPS PUB 46-2, December 1993,
              <http://www.itl.nist.gov/fipspubs/fip46-2.htm>.

The url is incorrect, it leads to the NIST home page.
I believe the correct url is
http://csrc.nist.gov/publications/fips/archive/fips46-3/fips46-3.pdf
(and it is FIPS 46-3, that superceeded FIPS 46-2).

Minor nits (subjective).

1. Section 1.

I think the main problem with 3DES is not that it is significantly slower
than AES, but that it has blocksize of 64 bits, that is considered
loo small for high-speed networks, when the possibility of birthday attack
leads to necessity to frequently rekey.

2. Section 2.

>From the description of how ESP packet is constructed it is not
absolutely clear what parts of the nonce are explicitely included in
the packet, and what aren't. I guess it is 64 bit IV that is included
and the higher 32 bits (SenderID) - that aren't, but it is not explicitely
stated. I'd prefer to it to be spelled out.

3. Section 3.

The last sentence is too long and refers to different sections in different
documents (this draft and RFC5282). That makes it a bit difficult to follow.
Could you, please, split it into several shorter sentences.

4. Section 5.

The terms "64-bit cipher", "128-bit cipher" and "256-bit cipher"
look like a jargon (and could be mixed up with key length by naive reader).
I'd prefer to use "block cipher with 64-bit block" etc.

5. Section 6.

I think it is worth to instruct IANA that tis document must be referenced
in both ESP and IKEv2 columns of IANA registry.
However it is not strictly necessary since IANA will ask this question 
anyway.

Regards,
Valery Smyslov.

---

From: Yoav Nir <[email-masked]>
Date: Tue, 21 Apr 2015 22:21:44 +0300

Hi, Valery.

Thanks for the review. See my reply inline.

> On Apr 21, 2015, at 7:19 PM, Valery Smyslov <[email-masked]> wrote:
> 
> Hi,
> 

I thought so as well. In the meantime, the TLS working group is discussing the same thing for TLS 1.3, and they are proposing to get rid of the salt (or IV) for AES-GCM as well as ChaCha20. 

http://www.ietf.org/mail-archive/web/tls/current/msg15884.html

The TLS working group is not making decisions for us, but I think it would be a shame to arrive at different conclusions where the cases are very similar. More technically, I use a single crypto library for both TLS and IPsec, and having a “salt" parameter that is always set to zero for TLS makes me sad.

> so it is not the best place for SenderID (unlike explicit IV).

As RFC 6045 says in section 3, the sender ID is carved out of the explicit IV, not out of the invisible salt. So that part of my question made no sense anyway. We either want the salt to protect against something, or we don’t. It’s not reserved for sender ID.

>  the normal ciphers with the integrity algorithms.

Thanks. I forgot about this restriction. Will fix in the next draft.

> The IV MUST be unique for each invocation (ESP packet or IKEv2 message),

Unique for each invocation *with the same key, no?  And keys are different from one SA to another.

> "additional data" is a bit vague, please use "Authenticated Additional Data"

OK.

> (and it is FIPS 46-3, that superceeded FIPS 46-2).

It worked when I first wrote the draft. Will fix.

> leads to necessity to frequently rekey.

It’s hard to make that case. The blocksize is 64 bits. So it’s prudent to not use more than, say, a billion blocks. A billion blocks is 64 Gb. There are very few real tunnels that run that kind of throughput in under a minute. OTOH it’s no problem at all to run a CreateChildSA every minute, or even every five seconds. So I think there are very few cases that *can’t* use 3DES.

> stated. I'd prefer to it to be spelled out.

OK. I’ll fix that when we decide what to do with the salt.

> Could you, please, split it into several shorter sentences.

I guess I can split that.

> I'd prefer to use "block cipher with 64-bit block" etc.

I think I’ll just drop everything after "Counters and LFSRs are both acceptable ways of generating unique nonces.” Encrypting counters gets the job done, but is a very inefficient way of generating unique IV. Especially if it means bringing DES into the mix.

> However it is not strictly necessary since IANA will ask this question anyway.

OK.

Yoav

---

From: "Valery Smyslov" <[email-masked]>
Date: Wed, 22 Apr 2015 11:39:15 +0300

Hi Yoav,

> I thought so as well. In the meantime, the TLS working group is discussing
> the same thing for TLS 1.3, and they are proposing to get rid of the salt
> (or IV) for AES-GCM as well as ChaCha20.
>

AFAIK they are discussing the possibility to get rid of explicit IV at all
and to use record number for that purpose. I don't think it will work
in our case. More precisely it could work for ESP, where sequence numbers
are unique, but it won't work for IKEv2, since Message ID is not unique
and can repeat (in cases of cluster synchronization or IKE Fragmentation).
So either we need to define two different mechnisms (implicit IV for ESP
and explicit IV for IKE) or always use explicit IV.

> The TLS working group is not making decisions for us, but I think it would 
> be a shame
> to arrive at different conclusions where the cases are very similar. More 
> technically,
> I use a single crypto library for both TLS and IPsec, and having a “salt" 
> parameter
> that is always set to zero for TLS makes me sad.

I agree that it is better to have a single mechanism for TLS and IPsec.
However I doubt if TLS WG would take into considerations our problems,
when making its own decision. On the other hand I think that implicit
IV is unacceptable for us (at least for IKE).

> As RFC 6045 says in section 3, the sender ID is carved out of the explicit 
> IV,
> not out of the invisible salt. So that part of my question made no sense 
> anyway.
> We either want the salt to protect against something, or we don’t. It’s 
> not reserved for sender ID.

Then, I think, it's better to use the salt as a salt, than not to use it :-)

> Unique for each invocation *with the same key, no?  And keys are different 

In its current form the text could be read that the IV is static
(unique for each SA, but not changing during the lifetime of SA,
so that each message of a particular SA have the same IV).
But in fact the IV must be unique for each message encrypted with the same 
key,
so it must change (e.g. incremented) after each use.
I just wanted to emphasize that fact and avoid possible readers confusion.

> It’s hard to make that case. The blocksize is 64 bits. So it’s prudent to 
> not use more than, say, a billion blocks.
> A billion blocks is 64 Gb. There are very few real tunnels that run that 
> kind of throughput in under a minute.
> OTOH it’s no problem at all to run a CreateChildSA every minute, or even 
> every five seconds.
> So I think there are very few cases that *can’t* use 3DES.

Well, I'm not a cryptographer, but I've heard several times that
the real problem of 3DES is its short block. And the attacker could
precalculate large number of keys, in which case a billion blocks
would not be prudent, the safe number could be a million blocks,
that is too small even for 1Gb networks. Of course it is possible to rekey
every 5 seconds, but it would consume more resourses.

Eventually all those frequent rekeys would lead to decreased performance,
so your initial idea is correct :-)

> Yoav

Regards,
Valery.

---

From: Tero Kivinen <[email-masked]>
Date: Thu, 23 Apr 2015 13:44:13 +0300

> and explicit IV for IKE) or always use explicit IV.

What I proposed earlier was that we define that chacha20 uses explicit
IV, but the IV is always generated as running counter incremented by
one.

In normal case the IV is sent inside the both IKEv2 and ESP packets.
In ESP the sequence number is used normally for replay protection.

Then we could create new "ESP Sequence number + IV compression"
protocol, that would negotiate the support for this in the IKEv2 for
ESP, and if enabled by both ends, then they would set the ESP sequence
number and chacha20 IV to be linked, i.e. they would always be same,
and then we could compress one of them away after the encryption, and
decompress them back in place before decryption.

I.e. the actual packets sent would only have one number, and IV and
ESP sequence number would be derived from that before decryption.

For IKEv2 we would still use just normal explict IV.

This would require us to define chacha20 IV generation so it uses
running counter starting from fixed value, but everything else can be
done later.

> the real problem of 3DES is its short block.

That is also my understanding, and I would rather use real reason why
3DES cannot be used (short blocksize) than some other random reason
(i.e. claiming it to be too slow).

If we claim 3DES cannot be used because it is slower than AES, then
vendors having separate hardware acceleration for 3DES, but very slow
CPU otherwise, could say that they have no reason to implement chacha,
as their 3DES acceleration is fast enough.
-- 
[email-masked]

---

From: Michael Richardson <[email-masked]>
Date: Mon, 27 Apr 2015 11:05:39 -0400

> IV is unacceptable for us (at least for IKE).

Whatever problems we have with an implicit IV in ESP will also be felt by DTLS.

--
Michael Richardson <[email-masked]>, Sandelman Software Works
 -= IPv6 IoT consulting =-

---

From: Michael Richardson <[email-masked]>
Date: Mon, 27 Apr 2015 11:08:33 -0400

> decompress them back in place before decryption.

That's an interesting proposal.
It seems excessively modular to me, but I'm willing to listen more to why it
makes sense.  Are there actually IKE daemons that use the IPsec code to do
their decryption?  I can see how this might happen in IoT space..

---

From: Michael Richardson <[email-masked]>
Date: Mon, 27 Apr 2015 11:25:04 -0400

I read draft-ietf-ipsecme-chacha20-poly1305 on Friday last, and then found
that I needed to further review draft-nir-cfrg-chacha20-poly1305-06 to better
understand the questions in para 2 of the security considerations, the
question about the uniqueness the nonce, so my initial reading, being
mostly ignorant about ChaCha and Poly1305 was very confusing.

(In preparing this email, I was also using the -05 document, which I see is
new. I think that I read -03 on Friday. -04 seems to have been skipped?)

I had not yet read any of the discussion on the list (intentionally) so as
to judge whether I understood the document on it's own.

{in preparing this email, I read the thread afterwards, and I now see that
some discussion was previously about IV being derived from replay counter, a
notion which I think has been removed from the ID. I don't think that I have
any new questions;  I think that after having read the document well, that
I can implement from the documents as they are}

I don't understand:
  > As the ChaCha20 block function is not applied directly to the
  > plaintext, no padding should be necessary.  However, in keeping with

could this be a typo ChaCha20 vs Poly1305?
If the encryption algorithm is now applied directly, then what is?
Or is meant that the block function for ChaCha20 used only to generate
bits for a stream cipher, and the XOR is what is "applied directly"?

>   The same key and nonce, along with a block counter of zero are passed
>   to the ChaCha20 block function, and the top 256 bits of the result
>   are used as the Poly1305 key.  The nonce passed to the block
>   function here is the same nonce that is used in ChaCha20, including the 32-bit
>   Salt, and the key passed is the same as the encryption key.

I think that if I have a block encryption function, that I need to encrypt
something to get an output.  I don't know what that is here....
Later I understood from reading cfrg-chacha20 that the ChaCha20 block
function acts as a prng, and that's why this is a stream ciper, not a block
cipher.  The use of the term "block function" here was confusing to me.

At first, I understand the nonce, was going to be the IV. Was there some
discussion/options in a previous version of the draft?
I initially understood that the the 32-bit block counter would be taken from
the replay counter, but now I see that this is incorrect, that it's unrelated
to the replay counter, and that I misunderstood at first.

So the Salt is really part of the key material.  We have a 36-byte key.  It
matters to people debugging things with a tool like TCPDUMP, that they know they
should expect 36-bytes.

Is this diagram correct:

keymat:                            iv:               ctr:
  +-----------------------+----+     +--------+      +----+
  |01234567890123456789012|0123|     |abcdefgh|      |0001|
  +-----------------------+----+     +--------+      +----+
            |               |           |              |
            |               |           |              |
            |               |           |              |
key:        V                nonce:     V      block   V
  +-----------------------+   +------------+     ctr:+----+
  |01234567890123456789012|   |0123abcdefgh|         |00xx|
  +-----------------------+   +------------+         +----+
    words: 4-11                words: 13-15          word 12

  \-----\  /------------\    /-----------------------------/
         \/              \  /
         | ctr=0          \/ 64-byte chunks prng
         |                ||
         |                |^^xor^ --< plaintext+padding+NH
         |  replay#       ||
         |  spi#    +----------+
         |  |       | cipher   |
         |  | /--<--| text     |
         |  | |     +----------+
         |  | |           |
         |  | |           |
         V  V V           |
      /----------\        |
      | Poly1305 |        |
      |   algo   |        |
      \----------/        |
            V             V
         +----+
         |MIC |
         +----+

I am very very very happy that cfrg-chacha20 has so many examples in it.
That's really awesome.

It wasn't until I read all of cfrg-chacha20 that I understood that the
Poly1305 needs to seeded for *each* packet.   I also think that the Poly1305
is not used in an HMAC construction.

I think that the IANA considerations of ipsecme-chacha20-poly1305 should say
something like,
          "According to cfrg-chacha20, Poly-1305 is not suitable for
           use as a PRF for IKEv2, and this specification explicitely
           does not allocate a code point for that."

=====

---

From: Yoav Nir <[email-masked]>
Date: Tue, 28 Apr 2015 01:52:09 +0300

> On Apr 27, 2015, at 6:25 PM, Michael Richardson <[email-masked]> wrote:
> 
> 
> bits for a stream cipher, and the XOR is what is "applied directly”?

Yeah, perhaps I didn’t phrase it the best way. If you’re using AES and you have a 19-byte plaintext and you’re using ECB (or CBC) you can encrypt the first 16-byte block of the plaintext, but for the second block you only have 3 bytes, whereas AES requires 16. So you need to pad. With CTR, CCM, GCM you encrypt a counter, which is always 16 bytes, Since you’re not applying AES to the plaintext (but to a counter) you don’t need to pad the plaintext - you just throw away the extra bytes of XOR mask that you created.
ChaCha20 is the same: you generate a 64-byte block from a key, a nonce and a counter, and you XOR as much of it as you need with the plaintext - so no pad is needed.

> cipher.  The use of the term "block function" here was confusing to me.

It’s not that different from AES-GCM. With AES-GCM (or just CTR) you have a 128-bit counter (actually it’s just a 32-bit counter as 96-bits are the per-packet nonce). You encrypt the counter and get a 16-byte block that you XOR with the plaintext.
With ChaCha20-Poly1305 you also have a 128-bit counter with 96 fixed bits. You run the ChaCha20 block function to generate a 64-byte block that you XOR with the plaintext.
The only difference is that the size of the counter is not the same as the size of the output block.
This is different from a real stream cipher where a single key with no nonce can generate an arbitrary length byte stream. ChaCha20 can only produce 64 bytes from a single value of the nonce.

>           does not allocate a code point for that.”

That’s kind of a weird thing to write. We don’t allocate an ICMPv6 type number either. It’s kind of sad because while Poly1305 is not a good PRF, ChaCha20 is. But unfortunately it’s not a good PRF for IKEv2 as it requires a constant-size key, and RFC 7296 requires that all PRFs support any size key. Of course we could add the blake2 hash function to convert any non-256-bit key to a 256-bit key, and blake2 is based on the ChaCha20 block function.  But we chose not to do this. At least not yet.

Yoav

---

From: Michael Richardson <[email-masked]>
Date: Tue, 28 Apr 2015 09:09:48 -0400

>> Is this diagram correct:

some comment on the accuracy of my diagram would be appreciated :-)

    > That’s kind of a weird thing to write. We don’t allocate an ICMPv6 type
    > number either. It’s kind of sad because while Poly1305 is not a good
    > PRF, ChaCha20 is. But unfortunately it’s not a good PRF for IKEv2 as it
    > requires a constant-size key, and RFC 7296 requires that all PRFs
    > support any size key. Of course we could add the blake2 hash function
    > to convert any non-256-bit key to a 256-bit key, and blake2 is based on
    > the ChaCha20 block function.  But we chose not to do this. At least not
    > yet.

I predict that in two years, there will be a stream of queries from
@gmail/@hotmail accounts asking in broken english why there isn't a PRF
number.  I'll bet we even get an Errata filed :-)

The bit about ChaCha also being wrong would be useful to write down
somewhere.

---

From: Yoav Nir <[email-masked]>
Date: Tue, 28 Apr 2015 18:17:04 +0300

> On Apr 28, 2015, at 4:09 PM, Michael Richardson <[email-masked]> wrote:
> 
> 

I’ll get to that later.

> number.  I'll bet we even get an Errata filed :-)

But we’re not even creating an AUTH entry…

> The bit about ChaCha also being wrong would be useful to write down

https://tools.ietf.org/html/draft-irtf-cfrg-chacha20-poly1305-10#section-2.7

Yoav