Subject: [IPsec] Teaser for pitch talk at IETF 108

From: Michael Rossberg <[email-masked]>
Date: Wed, 22 Jul 2020 12:26:58 +0200

We have been analyzing issues ESP has in current data-center networks and came to
the conclusion that changes in the protocol could significantly improve its behavior. Some
of results will be presented next Tuesday in a pitch talk at IETF 108. This mail is just a
small teaser, in case some of you wanted to gather some arguments for the discussion.

In particular, we propose the following changes to ESP:

	* Allow multiple windows per SA to allow for scaling over CPUs, windows per QoS
	  class & replay protection in multicast groups
	* 64 bit sequence counters in each header to ease protocol handling and allow for
	  replay protection in multicast groups
	* Removing the trailer to ease segment & fragment handling and alignment
	* Implicit IVs in spirit of RFC 8750 removing the need for AAD

Further details and benchmark results may be found in a paper preprint [1] and a
presentation [2] we held with at the Linux IPsec Workshop.

Michael

[1] https://telematik.prakinf.tu-ilmenau.de/files/packetformat.pdf
[2] https://telematik.prakinf.tu-ilmenau.de/files/VPE.pdf

---

From: William Allen Simpson <[email-masked]>
Date: Fri, 24 Jul 2020 07:33:42 -0400

I was forwarded this message.  As a matter of fact, I've never left the list,
but very rarely read it.

Speaking as one of the original designers of ESP, I'm delighted that folks
are finally catching up to our original design of 25+ years ago!

There's no need to rename ESP.  The Security Parameters Index was always
intended to always be in exactly same place, while the following fields
were per transform:

    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                Security Parameters Index (SPI)                |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                                                               |
    ~                        Transform Data                         ~
    |                                                               |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

> 	  class & replay protection in multicast groups

I'll post on this separately.

> 	  replay protection in multicast groups

ESP as originally specified circa 1994-1995 permitted larger sequence numbers.
We had expected all stacks to support them.

       The size of this field is variable, though for any given Security
       Association it has a particular known size. ...

       All conformant implementations MUST correctly process a 64-bit
       field size. ...

As IPsec was originally developed in the SIPP IPng WG, we were advocates of
64-bit alignment of the TCP data.

Sadly, a later WG editor removed that facility over my objections.

We'd always envisioned that DES would not be the be-all and end-all.  But
some short-sighted folks restricted the initial RFC published transforms.
Heck, they wouldn't even publish triple-DES or DES-XEX.  (I was on both of
those internet-drafts.)

Because of the DES unicity distance, there should never be more than 2^31
packets on the same DES session key.  You've been stuck for 25 years with
DES-specific transform formats.

> 	* Removing the trailer to ease segment & fragment handling and alignment

The trailing payload type was always a poor choice.  Caused already
perfectly aligned packets to need extra block cipher padding, and even
IP fragmentation.  But we lost that fight, too.

It was a compromise advocated by certain IP stacks of the day that
couldn't/wouldn't pass up their stack based upon the SPI.

We'd envisioned the SPI to be provisioned on a per socket basis.

The payload type and even the port number were to be specified or
negotiated by the session key manager.

> 	* Implicit IVs in spirit of RFC 8750 removing the need for AAD

I'll post on this separately.

---

From: William Allen Simpson <[email-masked]>
Date: Fri, 24 Jul 2020 14:28:17 -0400

No firestorm on the previous message, so here's more fuel....

> 	  class & replay protection in multicast groups

In the SIPP (IPv6) IPng WG, where we were designing IPsec circa 1993, one of the
principal authors was Steve Deering, a/the father of multicast.  Some multicast
issues were known and discussed at that time.

I'm not sure that including a number for the sender is the best way to achieve
this goal.  We already have the IP sender's address, and in IPv6 the Flow Label,
so that's duplicate information.

OTOH, I'm very sure that duplicating TCP sliding window functionality is unwise.
The proposed field is much too short for large bandwidth-delay products.  Perhaps
you want it for UDP?

However, we were also aware of the need for multiple concurrent SPI flows.  We
need to keep each CPU working as long as possible on the same data.

(When I was at university in the 70s, we had a CDC 6500: 2 main CPUs, and 10
peripheral CPUs.  Multi-processing was part of the curriculum, as was OS
design, plus a year-long compiler design and implementation class.)

Therefore, I'd recommend that IPsec instead implement a block of related SPIs.
Each SPI should have its unique session-key as usual, but all would have the
same next protocol header and TCP/UDP port associated with the same flow.

In the Photuris Extended Attributes internet-draft circa July 1997, we defined
the SPI-Block option.  Without the overhead of multiple negotiations, a single
exchange could generate a list of many related SPIs.

You could send on several SPIs concurrently.

---

From: Yoav Nir <[email-masked]>
Date: Fri, 24 Jul 2020 21:43:36 +0300

Hi, Michael.

Thanks for bringing this to the group.

> On 22 Jul 2020, at 13:26, Michael Rossberg <[email-masked]> wrote:
> 
> 

RFC 6311 allows multiple members in a cluster of IPsec gateways to have independent parallel SAs so as to solve the problem of synchronization and counter re-use among nodes. 

While the focus there is on different nodes, the synchronization problem also exists between cores of a single node. There is no reason to think RFC 6311 could not be adapted to multi-core nodes.

So I’m wondering if we really need multi-window logic to scale over CPUs, or whether it would be simpler to just generate multiple SAs for multiple CPUs.

Yoav
(with no hats other than co-author of RFC 6311)

---

From: Michael Rossberg <[email-masked]>
Date: Fri, 24 Jul 2020 22:42:23 +0200

Wiliam, Yoav,

thanks for the comments, I’ll try to elaborate in a single mail as you are heading in a similar direction.

> So I’m wondering if we really need multi-window logic to scale over CPUs, or whether it would be simpler to just generate multiple SAs for multiple CPUs.

If one just has a couple of IPsec gateways happening to be many-core systems, I totally agree that
multiple SAs would be the way to go. IMHO there are still a couple differences in protocol handling
that may be an advantage here and there, but nothing which justifies a protocol change in the data
plane.

Now our believe is that the many-core issue is just a special case of a broader issue. There are more
reasons to have unsynchronised replay windows.

Let me give a small example: Assume we have tenant with 10,000 VMs in a data center, all VMs are
coupled over VXLANs, which are in turn IPsec encrypted. Each of the machine may have 16 cores or so.
Having SAs for each possible multicast sender being proactively installed requires 16,000 SAs. If we had
8 potential QoS classes, that problem becomes worse. If another VM pops up, a group controller needs
to push 8*16 SAs to each of the potential receivers, before communication may take place.
Having on-demand replay windows using the same key material, would make the approach much more
scalable - without compromising security (people tend to simply disable replay protection, use a single
SA and split up IV room). We only had one SA for that tenant, and if there are multicast packets we can
direct them to any of our cores for decryption (as long as we do so consistently).

This is most likely a kind of odd view on IPsec, but I am pretty sure people will do much more L2 in L3
encapsulation and still want security (zero trust is just one of the buzzwords here).

There may be other ways to achieve the same properties, eg creating entire SAs blocks on demand by
deriving them locally from a master secret, but the SPI space will get exhausted pretty quickly when we
leave room for more CPUs, multicast members etc.

@William: The 16-bit sender ID is something we already get from protocols like GDOI to do IV space
partitioning (details in https://tools.ietf.org/html/rfc6054). So the mistake is already there.

I hope you have more fuel to get a little more heat (in good sense :)

---

From: Yoav Nir <[email-masked]>
Date: Sat, 25 Jul 2020 18:23:59 +0300

> On 24 Jul 2020, at 23:42, Michael Rossberg <[email-masked]> wrote:
> 
> Wiliam, Yoav,
> 

Right. And my question is, why not have multiple SAs instead of multiple windows within an SA.

The advantage of multiple SAs is that you don’t really need to change the other side of the IPsec connection (especially if the peer already supports 6311).  So if you have 30 cluster members, or 30 CPUs, or 30 virtual LANs, or 30 QoS classes, you can generate 30 SAs rather than 30 windows within 1 SA.

An SA is rather cheap:  It requires a value out of a 32-bit space. It requires at a minimum saving the key and current counter. Usually also a 64-bit replay bitmap at the receiver. Add metadata and we’re talking about a few dozen bytes. Add an expanded key for performance, and we’re still under a kilobyte. 

I’m not saying it’s a better design, but a new design should come with an explanation of why it’s better.

Yoav

---

From: William Allen Simpson <[email-masked]>
Date: Sat, 25 Jul 2020 13:59:08 -0400

> partitioning (details in https://tools.ietf.org/html/rfc6054). So the mistake is already there.
My memory was 8 bits, ludicrously small.  Reading more carefully, they
illustrated 8 bits, but also specified 12 and 16 bits.

But this is an opportunity to do better.  Let's not repeat mistakes.

In my own area of experience, RDMA for large storage clusters across multiple
data centers, you are going to run out quickly.  Use existing IP Source header
fields to build the IV.  Add and xor are sufficiently fast.

---

From: Michael Richardson <[email-masked]>
Date: Sun, 26 Jul 2020 14:10:46 -0400

> same next protocol header and TCP/UDP port associated with the same flow.

I agree with this model.

And I think that IKEv2 makes this significantly easier than IKEv1 did.
We are still relearning Photuris.

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

---

From: "Valery Smyslov" <[email-masked]>
Date: Tue, 28 Jul 2020 11:13:33 +0300

Hi,

a few thoughts about this proposal.

> 	  class & replay protection in multicast groups

An ability to have multiple windows per SA is an interesting idea.
However, in most cases the same result can be achieved with several parallel ESP SAs
with the same traffic selectors. Comparing with this proposal:

1. Several parallel ESP SAs require more resources to set up. On the other hand I don't 
    think it really matters (2 short IKE messages per SA is not a big deal, especially if no PFS is used and
    we are going to transmit millions of ESP packets then). 
2. Several parallel ESP SAs require more resources in the kernel. This is true.
3. If multiple windows are used for several QoS classes, then this proposal won't work in case 
    of TCP encapsulation, while several ESP SAs will (if we have several IKE SAs too).

Having replay protection in case of multicast is a feature that is not currently
available in ESP. However, it's easy to add this feature (with the limitation
that it only will be available if counter mode ciphers are used) by simply 
letting all GMs know the number of SID bits, so that they can guess
Sender ID from the IV. It's very simple modification of G-IKEv2.

Having said this, I think that the replay protection for multicast 
is not a feature that is absolutely needed. Multicast is performed
over UDP, so application protocols have to deal with packet 
replication and loss in any case (when they are used without 
IPsec protection). So, while a nice feature to have, I don't think
it's absolutely necessary and if one needed, it can be achieved without any 
modification to ESP with the same limitations as the proposed 
solution.

> 	  replay protection in multicast groups

This would simplify replay protection logic on receiver, but will waste
4 bytes on the wire for unicast SAs. I agree that ESN with ESP would not be available 
for multicast even if the above mentioned solution (letting GMs know SID) is implemented.
But I'm still not convinced we need it.

> 	* Removing the trailer to ease segment & fragment handling and alignment

I was told by Linux kernel people that having trailer in ESP is a headache for them.
However, this simplification has its cost:

1. Ciphers that require padding  cannot be used. I admit that CBC and the like
     are out of fashion today, but I don't know which cipher modes will be in fashion tomorrow
     and what requirement for padding they will have.
2. No Next Header field eliminates transport mode (BTW, widely used for multicast!)
     and makes it difficult to implement TFC (you can add TFC  padding, but you can't send 
     dummy packets and you can't use IPTFS)

> 	* Implicit IVs in spirit of RFC 8750 removing the need for AAD

I don't consider removing AAD is a benefit, since all the AEAD schemes I'm aware of
allow to have AAD. On the other hand, implicit IV is only applicable
to some transforms. I'm not only talking about non counter-based AEAD ciphers,
(like CBC), but even for counter-based AEAD  a situation is possible when there is a need
for IV to be somehow structured and not be a plain counter (e.g if you implement key trees).

> presentation [2] we held with at the Linux IPsec Workshop.

A few more considerations. 

It seems that performance of this proposal depends on ICV size 
for the plaintext to be properly aligned.
If ICV is 16 bytes, then plaintext is ideally aligned on 32 bytes,
but if one use 12 byes ICV (e.g. ENCR_AES_GCM_12)
then the plaintext is aligned on 4 bytes, that is even worse
than ESP, where it is for most AEAD transforms aligned on 16 bytes.

Since this proposal allows only tunnel mode, it will have
larger overhead for small packets. This is partially
compensated by having IV to be implicit...

And about security. In order to have IV combined with 
ESN and sub-windows identifiers this proposal removes secret 
salt from the nonce. This may have impact on security. 
I'm not a cryptographer, but I believe the impact is not negligible.
On the last CFRG session a draft draft-wood-cfrg-aead-limits was
discussed that calculates limits of data to be safely encrypted
by various AEAD ciphers. The authors claimed that having 
secret salt in the nonce increases this limits in case of multi-user
attacks and that the results in the draft are calculated
for this case. If plain AEAD ciphers (with no secret salt) are used
the limits are lower. 

So, on one hand this proposal makes it possible to transfer
larger amount of data with a single key (because you can 
combine all the traffic from different QoS classes and
all the CPU cores into one SA, no need to have
several ESP SAs). On the other hand
it simultaneously decreases the limit of data that 
can be safely protected with a single key.

I think that it's an interesting work, but I don't think it is 
a candidate for ESP replacement. The main problems with it
(as I see it from my corner) is that it is not generic enough:
it is optimized for small number of crypto transforms and 
use cases.

Regards,
Valery.

---

From: "Valery Smyslov" <[email-masked]>
Date: Tue, 28 Jul 2020 11:26:53 +0300

Hi,

> partitioning (details in https://tools.ietf.org/html/rfc6054). So the mistake is already there.

RFC 6054 doesn't limit the number of SID bits to 16, it only says that 8, 12 and 16 bits
MUST be supported. You may use longer values...

Regards,
Valery.

---

From: Michael Rossberg <[email-masked]>
Date: Tue, 28 Jul 2020 12:27:46 +0200

> I’m not saying it’s a better design, but a new design should come with an explanation of why it’s better.

A key advantage of the replay window approach is that there is no need to setup every window proactively.
That is there is no overhead at all as long as a replay window is not used. In a multicast environment it would
require reliably pushing a key to every possible sender, which may become a fairly large group. That is IMHO
a non-negligible overhead.

We could also solve this by adding some kind of associated SA that is automatically set up on-demand, but then
we need to subdivide the SPI space somehow. As Valery and William are “unhappy" with only 16-bit sender IDs
(perhaps for a good reason), we would require larger SPI fields...

---

From: Michael Rossberg <[email-masked]>
Date: Tue, 28 Jul 2020 12:31:06 +0200

> fields to build the IV.  Add and xor are sufficiently fast.

While I love the approach, there would be a significant chance for a collision in the
rather small IV space. Thus, modern ciphers would break. Due to IPv6 addresses
being much larger than current IVs, we have to do some explicit numbering, if we
want to use the same key.

---

From: "Valery Smyslov" <[email-masked]>
Date: Wed, 29 Jul 2020 09:23:44 +0300

Hi Michael,

> > The advantage of multiple SAs is that you don’t really need to change the other side of the IPsec connection
> (especially if the peer already supports 6311).  So if you have 30 cluster members, or 30 CPUs, or 30 virtual
> LANs, or 30 QoS classes, you can generate 30 SAs rather than 30 windows within 1 SA.
> >
> > An SA is rather cheap:  It requires a value out of a 32-bit space. It requires at a minimum saving the key and
> current counter. Usually also a 64-bit replay bitmap at the receiver. Add metadata and we’re talking about a
> few dozen bytes. Add an expanded key for performance, and we’re still under a kilobyte.
> >

You can get replay protection in multicast environment using unmodified ESP and modified receiver's logic
(with the same limitations as in your design). You don't need multiple SAs (one per sender).
All you need to do - allow GMs to know where to look for Sender ID, which is located in the higher 
order bits of IV. Of course, it will only work with counter-based ciphers, (as well as in your proposal).

> (perhaps for a good reason), we would require larger SPI fields...

Just for clarification - I'm not unhappy with 16-bit (in fact I think it's enough in _most_ cases),
I'm unhappy with this limit hardcoded into the design.

Regards,
Valery.

---

From: Steffen Klassert <[email-masked]>
Date: Wed, 29 Jul 2020 12:04:57 +0200

Hi Valery,

a few comments inline.

> a few thoughts about this proposal.

...

> 4 bytes on the wire for unicast SAs.

We have already the option to send the high sequence number bits
when a combined mode algorithm is used.

RFC 4303, Section 2.2.1. says:

If a combined mode algorithm is employed, the algorithm choice determines
whether the high-order ESN bits are transmitted or are included implicitly
in the computation.

We could just give multicast the same option if it wants to use replay
protection.

>      dummy packets and you can't use IPTFS)

Instead of a trailer, an (optional) encrypted header could be used
for transport mode, IPTFS etc.

That could be | Pad Length | Next Header | Pad to align payload |

> for IV to be somehow structured and not be a plain counter (e.g if you implement key trees).

Right, we should always have the option to include an explicit IV
as the IV construction depends on the used algorithm.

> than ESP, where it is for most AEAD transforms aligned on 16 bytes.

We could pad a 12 byes ICV up to 16 bytes, but I have to
admit that this might not be the best option.

> for this case. If plain AEAD ciphers (with no secret salt) are used

A secret salt in the nonce would be a new requirement anyway.
I've checked RFC 4106 (ESP for GCM) and RFC 7634 (ESP for
ChaCha20-Poly1305), both don't require a secret salt.

But I'm not sure if the IV construction in this proposal
would be always a good choice. As far as I understand,
Sender ID is only used with multicast, so will be most
likely zero on unicast. Also the replay window ID will
have a lot of zero bits on unicast (given that most
nodes have much less than 2^16 cpus these days).

Steffen

---

From: Tero Kivinen <[email-masked]>
Date: Wed, 29 Jul 2020 16:22:15 +0300

> whether the high-order ESN bits are transmitted or are included implicitly

We do not have any algorithms that use that feature, and we do not
have option to negotiate it in IKEv2.

We could add new value for transform type 5 (Extended Sequence
Numbers) to say that we use extended sequence number, and that we
actually transmit the full extended sequence number. 

> We could just give multicast the same option if it wants to use
> replay protection.

As others have already pointed out earlier, with multicast the upper
layer must make care of replays and dropped packets themselves in any
case, so doing that also on the IPsec level does not really provide
that much more security. I mean if the multicast protocol run over UDP
over IPsec simply has internal sequence number inside the UDP, which
will then be authenticated by the IPsec that should be good enough for
replay protection.

There is issue that in that case attacker could do Denial of Service
attack against the IPsec, by replaying packets, and then the IPsec
gateway would decrypt and forward them.

When using multicast you already need to use SPI, and destination
address as your SAD lookup (RFC4303, section 2.1), i.e. use option 2
there. On the other hand you could use the SPI, destination address,
and source address to find the replay window and largest sequence
number used if you want to do anti-replay protection on multicast SAs
so that each sender has separate replay windows.

I assume this is not normally done as it would create so much more
extra work for keeping track of replay windows for every single
sender, and where the benefit is not that big as upper layer protocols
usually do have anti-replay built in.

> ChaCha20-Poly1305), both don't require a secret salt.

It is true that they do not need secret salt, but they do have
unpredictable salt, which is created by the key derivation step. My
understanding was that this proposal did get rid of that salt too:

----------------------------------------------------------------------
4.  Nonce Format

   The nonce passed to the GCM-AES encryption algorithm has the
   following layout:

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                             Salt                              |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                     Initialization Vector                     |
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                          Figure 2: Nonce Format

   The components of the nonce are as follows:

   Salt
      The salt field is a four-octet value that is assigned at the
      beginning of the security association, and then remains constant
      for the life of the security association.  The salt SHOULD be
      unpredictable (i.e., chosen at random) before it is selected, but
      need not be secret.  We describe how to set the salt for a
      Security Association established via the Internet Key Exchange in
      Section 8.1.

-- 
[email-masked]

---

From: Steffen Klassert <[email-masked]>
Date: Wed, 29 Jul 2020 15:36:40 +0200

> understanding was that this proposal did get rid of that salt too:

Yes, this proposal removes the unpredictable salt. I did not say it
explicitely, but that was part of my critism on how they create
the IV in my original mail.

---

From: Michael Rossberg <[email-masked]>
Date: Wed, 29 Jul 2020 17:47:39 +0200

>    of TCP encapsulation, while several ESP SAs will (if we have several IKE SAs too).

With IPsec in TCP I do not believe one requires QoS anymore =) But honestly one could go
the same way. Multicast, CPU steering etc is a non-issue anyways.

> Sender ID from the IV. It's very simple modification of G-IKEv2.

If you have an explicit IV that is true. If you want implicit IVs, this approach no longer
works. Note rfc 8750 rules out multicast by design.

> modification to ESP with the same limitations as the proposed

I disagree. As people more and more send VXLAN etc over IPsec I am afraid that there
might be side effects that at least I can no longer foresee. I remember WEP with its non-
existing replay protection, an we could replay certain packets that generate legitimate
answers in order to obtain more traffic for cryptanalysis more quickly.

>     and what requirement for padding they will have.

You can still pad implicitly (just like in IPTFS) and are not even limited to 256 bytes.

>     dummy packets and you can't use IPTFS)

We have ideas to save the field for transport mode, but did not want to stress the teaser
too much. Basically we add an encrypted part to the header.

> allow to have AAD.

They are allowed to have AAD, but it will double en/decryption operations for small packets.

> On the other hand, implicit IV is only applicable

As written in the chat during presentation we could look at that. But it is always possible to
go back to an explicit IV.

> than ESP, where it is for most AEAD transforms aligned on 16 bytes.

Alignment may - depending on the architecture - be a plus. With only a
header one can adjust the headroom to have proper alignment. In any
of that cases.
For the trailer ESP takes care of 4 byte alignment only. For the header
one can use the same tricks, but out of the box you only have 4 byte
alignment by IP and even worse 2 byte alignment by Ethernet.

> compensated by having IV to be implicit...

We simplified for presentation as said above. Transport mode
is still possible with an additional inner header.

> for this case. If plain AEAD ciphers (with no secret salt) are used

The salt is a precaution. Just like the numbers in  the padding. Nothing
you want to build your security upon. NIST GCM document does not
mention it. MACsec does not use a salt.

> can be safely protected with a single key.

I do not under stand why the data is reduced. The probability for internal
collisions in GCM is not affected by the proposal.

> it is optimized for small number of crypto transforms and

Indeed we concentrate on the ciphers we found predominant today. For
low speed connections there is still CBC, we could add it for sake of completeness.
The optimization for a certain use case is true, too. We concentrated on
high speed data center SAs, as it is always easy to make things slower later on =)
You can make unicast from a multicast-capable protocol, but not vice versa.
If an outcome of this discussion is, this being special purpose solution for data
centers, that would be absolutely fine I guess.

---

From: Michael Rossberg <[email-masked]>
Date: Wed, 29 Jul 2020 18:10:20 +0200

> actually transmit the full extended sequence number.

That would already help for the case.

> gateway would decrypt and forward them.

Like pointed out in the answer to Valery’s mail. There are possibly more
issues, as attackers are able to generate new traffic, they can use for
cryptanalysis (see
https://www.aircrack-ng.org/doku.php?id=arp-request_reinjection).
Having anti-replay guarantees is just a reliable foundation. IMHO the
case of applications being responsible holds just as well for unicast
applications. TCP takes care of that, still no-one honestly discusses
removing replay checks for high volume unicast SAs.

> so that each sender has separate replay windows.

This still requires to know all possible senders beforehand. Also the
SAs will still need to agree on an IV subspace and sending an explicit
IV per packet.

> understanding was that this proposal did get rid of that salt too:

Like written already: An unpredictable value of 32bit size is of no real value
from a crypto point of view. One could simply guess the value and have
a realistic chance of being right after a couple of thousand tries. I believe it
is only in the standard, as with 64 bit sequence numbers there where 32 bits
left; needing to be filled.

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Wed, 29 Jul 2020 16:57:04 +0000

> -----Original Message-----
> From: IPsec <[email-masked]> On Behalf Of Michael Rossberg
> Sent: Wednesday, July 29, 2020 12:10 PM
> To: Tero Kivinen <[email-masked]>
> Cc: Steffen Klassert <[email-masked]>; [email-masked]; Valery
> Smyslov <[email-masked]>
> Subject: Re: [IPsec] Teaser for pitch talk at IETF 108
> 
> 
> >> We have already the option to send the high sequence number bits when
> >> a combined mode algorithm is used.
> >>
> >> If a combined mode algorithm is employed, the algorithm choice
> >> determines whether the high-order ESN bits are transmitted or are
> >> included implicitly in the computation.
> >
> cryptanalysis (see https://www.aircrack-ng.org/doku.php?id=arp-
> request_reinjection).
> Having anti-replay guarantees is just a reliable foundation. IMHO the case of
> applications being responsible holds just as well for unicast applications. TCP
> takes care of that, still no-one honestly discusses removing replay checks for
> high volume unicast SAs.
> 
> This still requires to know all possible senders beforehand. Also the SAs will
> still need to agree on an IV subspace and sending an explicit IV per packet.
> 
> >>> And about security. In order to have IV combined with ESN and
> >>> sub-windows identifiers this proposal removes secret salt from the
> >>> nonce. This may have impact on security.
> >>> discussed that calculates limits of data to be safely encrypted by
> >>> various AEAD ciphers. The authors claimed that having secret salt in
> >>> the nonce increases this limits in case of multi-user attacks and
> >>> that the results in the draft are calculated for this case. If plain
> >>> AEAD ciphers (with no secret salt) are used the limits are lower.
> >>
> from a crypto point of view. One could simply guess the value and have a
> realistic chance of being right after a couple of thousand tries. 

Actually, it does add value from a crypto point of view, at least from a specific attack.  In a multitarget attack, that is, an attack where we assume that the attacker has encrypted packets from a large number of SAs, and his goal is to recover the keys for any one of the encrypted packets, here is what the attacker can do (assuming GCM or ChaCha20-Poly1305); if he has packet encrypted with each SA with the same nonce, he can guess a key, and generate the internal GCM/ChaCha20 keystream based on that key/nonce combination.  He can then scan through all the packets to see if the encryption makes sense (or the ICV tag works out); this can be done far faster than checking each packet individually.  Assuming the packets are encrypted with AES-128, and the attacker has packets from 2**L SAs, then against this attack, we have only 128-L bits of security.

By including 32 bits of unpredictable values, we make this attack 4 billion times harder, and for AES-128, that would give us 160-L bits of security. This doesn't actually add any security against attacks against a single SA, and the salt doesn't actually need to be secret.

> I believe it is
> only in the standard, as with 64 bit sequence numbers there where 32 bits

Nope; it was included to increase security.  For 256 bit keys, one can easily argue that this is not needed; however for 128 bit keys, it is considerably more marginal.

---

From: Tero Kivinen <[email-masked]>
Date: Wed, 29 Jul 2020 21:29:57 +0300

> https://www.aircrack-ng.org/doku.php?id=arp-request_reinjection).

If any of our algorithms are vulnerable to that kind of attacks, we
immediately need to move that algorithm to MUST NOT category. None of
the modern ciphers should be affected by that. 

> removing replay checks for high volume unicast SAs.

Actually there are several complains that people are disabling
anti-replay for VPNs just as there are buggy implementations of it,
and if you disable it then at least some connections might be more
stable... The thing is that you never know whether it is disabled on
the receiver or not...

> SAs will still need to agree on an IV subspace and sending an explicit

Yes, this is similar than your proposal, except it uses standard ESP.
I.e., you need to know which sender IDs are to be used, here you need
to know which source addresses are used. You also need to transmit
Sender ID inplace, in standard ESP you reserve part of IV for that
purpose and use that.

Note, that if you use SPI, destination address and source address to
find the replay protection information you do not need to transmit
that part of IV inplace. I.e. the SAD has the 32-bit salt for GCM
Nonce + the IV from the packet (whether it is actual transmitted IV,
or implicit IV in form of sequence number does not matter). You could
simply make multicast SAs in such way that they only have 16-bit
random salt per SA, and other 16-bit of the random salt is per sender.
This means when multicast SA is created it creates 16-bits of common
salt, and then when sender joins the group, it will get unique 16-bits
random salt assigned to it. This 16-bit salt part + sequence number +
replay window is stored to the list of senders indexed by sender
address under the SA.

There are most likely also other ways of doing the same thing. Good
thing is that we already have the g-ikev2 doing group key management
using IKEv2, so we can easily make sure we can do needed negotiations
in there.

All multicast traffic cases are going to be needing that g-ikev2
anyways, so my proposal is that we move discussion about multicast
cases to that g-ikev2 discussion. 

> Like written already: An unpredictable value of 32bit size is of no
> real value from a crypto point of view. One could simply guess the
> value and have a realistic chance of being right after a couple of
> thousand tries. I believe it is only in the standard, as with 64 bit
> sequence numbers there where 32 bits left; needing to be filled.

I think it came from the NIST documents where it was called fixed
field. The idea was to make sure that even if someone accidently used
same key twice for two different SAs, this will not cause issues, as
that fixed field is going to be unique anyways.

I.e. NIST 800-38D section 8.2.1 says:
----------------------------------------------------------------------
...
The lengths and positions of the fixed field and the invocation field
shall be fixed for each supported IV length for the life of the key.
In order to promote interoperability for the default IV length of 96
bits, this Recommendation suggests, but does not require, that the
leading (i.e., leftmost) 32 bits of the IV hold the fixed field; and
that the trailing (i.e., rightmost) 64 bits hold the invocation field.
-- 
[email-masked]

---

From: Michael Rossberg <[email-masked]>
Date: Wed, 29 Jul 2020 20:35:10 +0200

> By including 32 bits of unpredictable values, we make this attack 4 billion times harder, and for AES-128, that would give us 160-L bits of security. This doesn't actually add any security against…

Thanks for clarification. I guess I have been thinking too SA centric.
In fact we always discussed AES-256 only.

Do you agree that starting the window/sender IDs with random offsets would fix this weakness?

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Wed, 29 Jul 2020 18:52:32 +0000

> From: IPsec <[email-masked]> On Behalf Of Tero Kivinen
> Sent: Wednesday, July 29, 2020 2:30 PM
> To: Michael Rossberg <[email-masked]>
> I think it came from the NIST documents where it was called fixed field. The
> idea was to make sure that even if someone accidently used same key twice
> for two different SAs, this will not cause issues, as that fixed field is going to
> be unique anyways.

No, RFC4106 (June 2005) predated 800-38D (November 2007) by over two years.

Instead, it was inserted to harden the system against multitarget attacks, as I said earlier...

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Wed, 29 Jul 2020 18:54:19 +0000

> From: Michael Rossberg <[email-masked]>
> Sent: Wednesday, July 29, 2020 2:35 PM
> To: Scott Fluhrer (sfluhrer) <[email-masked]>
> Cc: ipsecme mailing list <[email-masked]>
> > Actually, it does add value from a crypto point of view, at least from a
> specific attack.  In a multitarget attack, that is, an attack where we assume
> that the attacker has encrypted packets from a large number of SAs, and his
> goal is to recover the keys for any one of the encrypted packets, here is what
> the attacker can do (assuming GCM or ChaCha20-Poly1305); if he has packet
> encrypted with each SA with the same nonce, he can guess a key, and
> generate the internal GCM/ChaCha20 keystream based on that key/nonce
> combination.  He can then scan through all the packets to see if the
> encryption makes sense (or the ICV tag works out); this can be done far
> faster than checking each packet individually.  Assuming the packets are
> encrypted with AES-128, and the attacker has packets from 2**L SAs, then
> against this attack, we have only 128-L bits of security.
> >
> > By including 32 bits of unpredictable values, we make this attack 4 billion
> times harder, and for AES-128, that would give us 160-L bits of security. This
> doesn't actually add any security against attacks against a single SA, and the
> salt doesn't actually need to be secret.
> 

Yes, it would address this weakness.  On the other hand, with AES-256, you don't really need this anyways...

---

From: Tero Kivinen <[email-masked]>
Date: Wed, 29 Jul 2020 22:20:33 +0300

> No, RFC4106 (June 2005) predated 800-38D (November 2007) by over two years.

Ah, didn't check the dates, and the NIST document didn't really
explain the reason behind it, it just said you preferrably need to
have 32-bit fixed part.

> attacks, as I said earlier...

Thanks for that explination.

So we do want to keep that, and of course as it is part of NIST
document you might have issues trying to get certifications for you
implementations if you do not follow NIST documents. You most likely
would still get certification even if you do not follow some RFCs.
-- 
[email-masked]

---

From: "Valery Smyslov" <[email-masked]>
Date: Thu, 30 Jul 2020 11:07:18 +0300

Hi Scott,

> > salt doesn't actually need to be secret.

Thank you for the good explanation.

> Yes, it would address this weakness.  On the other hand, with AES-256, you don't really need this anyways...

What's your opinion - if we consider quantum computers (so that the real strength of AES-256 is 128 bit),
then does addition of unpredicted salt to AES-256 make sense?

Regards,
Valery.

> _______________________________________________
> IPsec mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/ipsec

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Thu, 30 Jul 2020 18:00:24 +0000

> From: Valery Smyslov <[email-masked]>
> Sent: Thursday, July 30, 2020 4:07 AM
> To: Scott Fluhrer (sfluhrer) <[email-masked]>; 'Michael Rossberg'
> <[email-masked]>
> Cc: 'ipsecme mailing list' <[email-masked]>
> Subject: RE: [IPsec] Teaser for pitch talk at IETF 108
> 
> Hi Scott,
> 
> > > specific attack.  In a multitarget attack, that is, an attack where
> > > we assume that the attacker has encrypted packets from a large
> > > number of SAs, and his goal is to recover the keys for any one of
> > > the encrypted packets, here is what the attacker can do (assuming
> > > GCM or ChaCha20-Poly1305); if he has packet encrypted with each SA
> > > with the same nonce, he can guess a key, and generate the internal
> > > GCM/ChaCha20 keystream based on that key/nonce combination.  He
> can
> > > then scan through all the packets to see if the encryption makes
> > > sense (or the ICV tag works out); this can be done far faster than
> > > checking each packet individually.  Assuming the packets are
> > > encrypted with AES-128, and the attacker has packets from 2**L SAs,
> then against this attack, we have only 128-L bits of security.
> > > >
> > > times harder, and for AES-128, that would give us 160-L bits of
> > > security. This doesn't actually add any security against attacks
> > > against a single SA, and the salt doesn't actually need to be secret.
> 
> What's your opinion - if we consider quantum computers (so that the real
> strength of AES-256 is 128 bit), then does addition of unpredicted salt to AES-
> 256 make sense?

That is a surprisingly deep question; however since you specified "my opinion", I would say "it doesn't appear to be needed" (but wouldn't hurt anything)

Here are some of the complexities (and unknown factors):

- We have Grover's algorithm (which is an algorithm that runs on a Quantum Computer that supposedly does "key halving" of symmetric ciphers; that is, it searches for an n bit key in 2*(n/2) time)

- However, if we insert the assumption of bounded quantum circuit depth; that is, we insist that we get the result of the search quickly, say, within 1000 years, then the attacker using Grover's algorithm needs to significantly more computation resources to search for a large key, that is, the level of security is significantly higher then what "halve the key" would indicate.  With a conventional computer, we can perform parallel searches without increasing the cost (total amount of computation performed); with Grover's, performing the search in parallel cuts into the advantage that Grover's brings to the table.

- How expensive is a multitarget comparison for a Quantum Computer (as opposed to a conventional one, where it is cheap)?  After all, the entire point of this effort is to use a multitarget comparison to search against a large number of targets at once.  This is relevant because if it is of significant cost, it would require more computational resources, which against, would effectively raise the security level achieved.  I did glance at a similar scenario a while back; I came to the conclusion that a multitarget version of Grover's would cut circa 10-12 bits from the security level (by searching against circa a million targets - increasing the targets beyond that started to increase the cost most than just adding additional parallel searchers); however this was a fairly informal study, and I never published it.

- How costly (in terms of performance and expense) is a Quantum Gate (of various different flavors) compared to conventional gates?  This is a constant factor; however if it is large constant (e.g. a Quantum Gate is as expensive as one billion conventional gates), well, a factor of 2**30 really can't be ignored in practice.

However, when I plug in plausible numbers to the above unknowns (especially the last; for the previous, we do have some reasonable guesses), I still get that a quantum multicollision attack against AES-256 is still not feasible...

---

From: William Allen Simpson <[email-masked]>
Date: Thu, 30 Jul 2020 21:28:30 -0400

> You could send on several SPIs concurrently.

Although there has been some pushback, have we agreed that instead of multiple
windows (however defined), a more general solution is multiple SPIs?

Who is going to write the SPI block/group extension for IKEv2?

Would it be best to add to an existing draft already in the pipeline?

---

From: Michael Rossberg <[email-masked]>
Date: Fri, 31 Jul 2020 10:37:05 +0200

> windows (however defined), a more general solution is multiple SPIs?

Sorry, I have not caught up with answering all mails yet.

For each of the cases multicast, multicore & QoS there have been a lot of people arguing
for such a solution. However, I still see the argument, that enabling all of these features
will lead to a combinatorial explosion of SAs, which are brought up proactively, even though
perhaps never used.

Somehow associated SAs would perhaps allow us to derive/install a key locally on demand.
However, due to the combinatorial explosion, these blocks of SAs may easily become pretty
large, ie. with a reservation for multicast senders and QoS groups SPIs may be a little short.

> Who is going to write the SPI block/group extension for IKEv2?

I am afraid there are more things affected with such a way to go, e.g. g-ike.

There are still other things uncovered: Explicit 64 bit sequence numbers, implicit IVs for
group communication, the whole trailer discussion.

All in all these changes make raise the complexity even further, a thing we tried to reduce
by unifying things for the multi/unicast case. Allowing people to use the same dataplane
configuration to encap L2 frames.

> Would it be best to add to an existing draft already in the pipeline?

I would volunteer to perhaps write things together in a longer argumentation over this fall.