Subject: [IPsec] Diet-ESP

From: Daniel Migault <[email-masked]>
Date: Fri, 4 Jul 2014 22:16:14 +0200

Hi,

Here are the drafts we wrote on Diet-ESP which designs ESP for constrain
environment.

[1] draft-mglt-ipsecme-diet-esp-requirements-00.txt
<http://datatracker.ietf.org/doc/draft-mglt-ipsecme-diet-esp-requirements/>
provides the requirements we considered for the design of Diet-ESP
[2] draft-mglt-ipsecme-diet-esp-01.txt
<http://datatracker.ietf.org/doc/draft-mglt-ipsecme-diet-esp/>
describes Diet-ESP. According to feed backs we received during the
last presentation. Diet-ESP does not modify ESP. Instead, we consider
compression / decompression of the payload sent on the wire.
[3] draft-mglt-ipsecme-diet-esp-iv-generation-00.txt
<http://datatracker.ietf.org/doc/draft-mglt-ipsecme-diet-esp-iv-generation/>
describes a way to compress th IV field in ESP encrypted payloads.
[4] draft-mglt-ipsecme-diet-esp-payload-compression-00.txt
<http://datatracker.ietf.org/doc/draft-mglt-ipsecme-diet-esp-payload-compression/>
describes how IPsec parameters negotiated with IKEv2 can be used to
compress the clear text payload. More specifically, it is expected to
compress up to the transport layer of the encrypted packet.

Feel free to make comments!

We have specific question regardin the IV compression. The general idea is
that a speudo random function is used on bth side to generate the IV. This
makes possible to send only some LSB.
    - 1) The pseudo random function uses as input the encryption key an
dthe authentication key. I do not see major security flaws, but it may be
better if a dedicated K could be used. Any ideas?
    - 2) By default we use PRF_AES128_XCBC. Another way would consist in
chosing the PRF based on the ICV function. When NULL authentication is used
the IV would not be compressed. Any opinion on that too?

[1]
http://datatracker.ietf.org/doc/draft-mglt-ipsecme-diet-esp-requirements/
[2] http://datatracker.ietf.org/doc/draft-mglt-ipsecme-diet-esp/
[3]
http://datatracker.ietf.org/doc/draft-mglt-ipsecme-diet-esp-iv-generation/
[4]
http://datatracker.ietf.org/doc/draft-mglt-ipsecme-diet-esp-payload-compression/
-- 
Daniel Migault
Orange Labs -- Security
+33 6 70 72 69 58

---

From: "Valery Smyslov" <[email-masked]>
Date: Tue, 15 Jul 2014 11:23:55 +0400

Hi,

I have some comments regarding the draft.

First, it is not absolutely clear from the draft how 
the IV is generated for each packet. I presume
that the IVs are taken sequentially for every new
ESP packet to send from the bit string generated
by prf+. But then it is not clear for me how the receiver
would regenerate the same IV in case of packets loss
and reordering. Sending LSB of IV would help here a bit, 
but then receiver would do quite a lot of work to guess
the right IV, the overall process is not deterministic
and opens a possibility for simple DoS attack.
The receiver would also look at the sequence number to 
deal with packets loss and reordering, but as far as 
I understnad the SN is optional in Diet-ESP.

Then, I'm not a crypto expert, but using the same
key for both encryption and IV generation looks
like a bit unsound. 

Finally, I would prefer defining new transorms
(for example AES-CBC with implicit IV) instead of 
negotiating IV compression separately.

Regards,
Valery Smyslov.

---

From: Daniel Migault <[email-masked]>
Date: Tue, 15 Jul 2014 09:49:55 +0200

Hi Valery and thank you for your feed backs.

Instead of negotiating the IV compression in a separate way, Valery
suggests to have a specific mode like AES-CBC_WITH_IV_COMPRESSION for
example.

To me its sounds better than what is being described in the draft.

Please let us know what you think about this alternative, and which
function would you use to generate the pseudo random IVs in each packets.

See inline for more comments.

BR,
Daniel

On Tue, Jul 15, 2014 at 9:23 AM, Valery Smyslov <[email-masked]> wrote:

> First, it is not absolutely clear from the draft how the IV is generated
> for each packet. I presume
> and reordering. Sending LSB of IV would help here a bit, but then receiver
> would do quite a lot of work to guess

This is true, and we should have added more text on that. The initial idea
is to rely on the Sequence Number, and their should be a deterministic way
to bind SN and IV for bot peers. However you are right, to avoid simple
DoS, there should also be a deterministic way to decompress the SN.

> The receiver would also look at the sequence number to deal with packets
> loss and reordering, but as far as I understnad the SN is optional in
> Diet-ESP.
>

It depends what optional means. Diet-ESP packets MUST have a complete
Sequence Number to enable anti-replay and to compute the ICV. On the other
hand, Diet-ESP provides the option to send only the LSB of the SN on the
wire. In order to avoid simple DoS attacks, the decompression of the SN
should be "almost" deterministic.

> key for both encryption and IV generation looks

This sounds bad to me too. Actually this is my main concern.

> (for example AES-CBC with implicit IV) instead of negotiating IV
> compression separately.
>

That is maybe the way to do. Thanks for your feed back.

-- 
Daniel Migault
Orange Labs -- Security
+33 6 70 72 69 58

---

From: Stephen Kent <[email-masked]>
Date: Wed, 23 Jul 2014 14:16:02 -0400

Daniel,

I read the very brief IV-generation I-D and I didn't see an explanation 
of how
to perform IV "compression." As someone else already noted on the list, 
an IV
is carried with each packet to enable decryption of packets that may 
arrive out
of order. Thus it's not enough to have each peer use the same PRF and 
seed to
generate IVs which are not explicitly transported, because of this 
requirement.
Also, if the IV is required to be pesudorandom, there is likely no 
opportunity
for compression in the usual sense. Finally, note that the specs for 
algorithm
modes like GCM treat the IV as a security critical piece of info, for 
good reason.
Thus if one tries to re-use a value such as an ESP sequence number as an 
IV, all of
the ESP sequence number generation/management code becomes security 
critical wrt
algorithm mode evaluation. This topic was discussed in London in the TLS 
WG meeting,
when considering use of Cha-Cha. I can forward the relevant messages and 
my slides
if you wish.

Steve

---

From: Daniel Migault <[email-masked]>
Date: Thu, 24 Jul 2014 20:55:18 +0200

Hi Steve,

First of all many thanks for the comments. They will be usefull to design
it right.

I have copied the 6lo ML since we presented Diet-ESP in 6lo this morning.

There has been some discussion on the IV compression too and here is the
link to the presentation Steve made at TLS in the IETF 89 in London [1
<http://www.ietf.org/proceedings/89/slides/slides-89-tls-2.pdf>]

The design we had in mind is as follows:
a) On the sender side:
    - Step 1: Each peer negotiate a key:  in the next version we will
specify that this key is derived by IKEv2 and leave to future work how
IKEv2 generates this key.
    - Step 2: Use a PRF to generate IV_1, IV_2, ...., IV_n where IV_i is
the IV the sender use to encrypt packet i
    - Step 3: Send your ESP compressed packet (let say here not sending all
the bytes of the IV)

b) On the receiver side:
    - Step 1 figuring out which packet is received -- in our case that is
packet i
    - Step 2 find / generate the corresponding IV_i
    - Step 3 decrypt packet i

The goal is to avoid sending IV in each packet that is what we call
compression. If you IV is 8 bytes, the compression can be send the least
significant last byte, (respectively two last bytes, ... 7 last bytes, the
whole IV, or no IV at all). More precisely, we do not consider zipping a
random number.

The draft does not specify how matching between IV_i and packet i is
performed.
   - 1) you may use the SN as the packet counter. Of course it is easier if
the SN increments for each packet. However SN are not part of the IV
generation.
   - 2) you may use the least significant bytes to determine which IV may
match.

This way of doing so differs in the current way of sending the IV as we do
not have the IV from the packet. In our case, the IV is not derived from
the packet, we need to generate a few number of IV in advance, and find out
which is the one matching a particular packet. Motivation for doing so is
that sending a byte in 6lo cost more than doing a few thousand operations.
In that sense, we are ready to implement some more complex IV-to-i function.

Best Regards,

Daniel

[1] http://www.ietf.org/proceedings/89/slides/slides-89-tls-2.pdf

On Wed, Jul 23, 2014 at 8:16 PM, Stephen Kent <[email-masked]> wrote:

> Daniel,
>
> I read the very brief IV-generation I-D and I didn't see an explanation of
> how
> to perform IV "compression." As someone else already noted on the list, an
> IV
> of order. Thus it's not enough to have each peer use the same PRF and seed
> to
> modes like GCM treat the IV as a security critical piece of info, for good
> reason.
> _______________________________________________
> IPsec mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/ipsec
>

-- 
Daniel Migault
Orange Labs -- Security
+33 6 70 72 69 58

---

From: Stephen Kent <[email-masked]>
Date: Fri, 25 Jul 2014 12:26:02 -0400

Daniel,

Thanks for the explanation.
> ...
>    - 1) you may use the SN as the packet counter. Of course it is 
> easier if the SN increments for each packet. However SN are not part 
> of the IV generation.
which SN? the one from ESP? Doesn't Diet-ESP significantly reduce the 
sequence number space?
if the SN space is small, then there may be ambiguity at the receiver.
>    - 2) you may use the least significant bytes to determine which IV 
> may match.
> This way of doing so differs in the current way of sending the IV as 
> we do not have the IV from the packet. In our case, the IV is not 
> derived from the packet, we need to generate a few number of IV in 
> advance, and find out which is the one matching a particular packet.
This sentence suggests that the least significant bytes above are from 
the "compressed"
IV. Is that right?  If the IV is pseudorandom, and it's compressed 
representation is small,
e.g., 2 bytes, what is the  likelihood that two IVs will have the same 
representation, within
a receive window of, say 32 packets? (This is a drawing balls from an 
urn with replacement
problem, I think). This might result in a frequency of collision that 
may be an issue, causing
the receiver to have to do crypto processing on colliding packets.
> Motivation for doing so is that sending a byte in 6lo cost more than 
> doing a few thousand operations. In that sense, we are ready to 
> implement some more complex IV-to-i function.
Isn't the "lo" in 6lo, low power? Is it clear that the cycles vs. 
bandwidth tradeoff is always
a win?

Steve

---

From: Daniel Migault <[email-masked]>
Date: Fri, 25 Jul 2014 21:36:34 +0200

Hi Steve,

Thanks for the feed back.

Just to clarify the general compression principle: When a field is
compressed, it means that the field is not (or partially) sent on the wire.
However, the complete field has been used to generate the packet, and the
whole field MUST be decompressed by the receiving side to go further. The
idea beyond this principle is that we do not want to alterate the security
of the (non- compressed) protocol and we want to benefit from the security
analyze of the (non- compressed) protocol. In our case the protocol is
IPsec/ESP.

This means that SN is always the 32 bit Sequence Number of the ESP Packet (
64 bit if you use Extended Sequence Number). These two sizes are considered
for generation of the ICV as well as for the anti replay mechanism as
described in RFC4303. The compressed SN is a portion of the SN, that should
be enough to help retrieving the whole SN. If your are not able to retrieve
the whole SN, then there is little you can do, as the whole SN MUST be
retrieve for ICV check/ anti-replay attack.

This is the same case for the SPI.

The collision has not been documented in the current draft, and you are
right we will have to do that. I am not doing the analyze in that mail --
as I want to send the response before the wifi is done-- but I will respond
later. Thanks for the suggestion.

It is also true that collision involves more computation. However, in the
IoT world, computation versus sending is (to some extend of course) always
a win. Here is the example I have in mind.
    - Computing: ranges from 0.5nJ per instruction for extremely
energy-efficient microcontrollers (such as CoolRisc or MSP430) to 200 nJ
per instruction for high-performance microprocessors (such as ARM9).
    - Communication: from 100nJ to 1uJ per bit transmitted or received,
depending on modulation complexity and transmission power (we only consider
"low-power" radios, with transmit powers lower than about 10mW).

Roughly speaking, this means that, for the energy cost of exchanging 1 bit,
our system can alternatively compute 10-100 instructions. Therefore, there
is a high interest in compressing frames before transmitting them

Note that if that is not the case in some scenarios, or with some future
technologies. As we have the flexibility to define the compression, and as
compression does not impact the IPsec processing of the (decompress)
packet, one can always redefine the number of bytes to send.

BR,
Daniel

On Fri, Jul 25, 2014 at 6:26 PM, Stephen Kent <[email-masked]> wrote:

>>    - 1) you may use the SN as the packet counter. Of course it is easier
>> if the SN increments for each packet. However SN are not part of the IV
>> generation.
>>
>> This way of doing so differs in the current way of sending the IV as we
>> do not have the IV from the packet. In our case, the IV is not derived from
>> which is the one matching a particular packet.
>>
> This sentence suggests that the least significant bytes above are from the
> "compressed"
> a receive window of, say 32 packets? (This is a drawing balls from an urn
> with replacement
> problem, I think). This might result in a frequency of collision that may
> be an issue, causing
>> doing a few thousand operations. In that sense, we are ready to implement
>> some more complex IV-to-i function.
>>

-- 
Daniel Migault
Orange Labs -- Security
+33 6 70 72 69 58

---

From: Carsten Bormann <[email-masked]>
Date: Sat, 26 Jul 2014 16:27:59 -0400

> On 25.07.2014, at 12:26, Stephen Kent <[email-masked]> wrote:
> 
> Is it clear that the cycles vs. bandwidth tradeoff is always
> a win?

Practically always.  Daniel's numbers were spot on.

Grüße, Carsten