Re: [babel] Solving HMAC replay once and for all

[David Schinazi <[e-mail]>]

> On Jun 27, 2018, at 15:20, Juliusz Chroboczek <[e-mail]> wrote:
> 
>>> Basically this breaks the property that "any packet without a valid HMAC is
>>> silently ignored" and that worries me, as it was a good property to have.
> 
>> Good point, noted.
> 
> So:
> 
>  Property D: a packet is silently ignored after an HMAC failure,
> 
> and
> 
>  Property M: nonces are not carried in every packet.
> 
> are both good properties to have.  Can we have both?

I think so, yes. Straw man proposal:

We add two new TLVs: ChallengeRequest and ChallengeResponse, which MUST be sent unicast.
Those TLVs are allowed to be parsed if the HMAC validates but the counter does not.

Alice is the receiver. Alice maintains a per-neighbour table of counters.
When Alice receives a packet from Bob:
- if HMAC does not validate, Alice drops bob's packet silently
- else if Alice has counter information about Bob, and the counter is in [savedCounter + 1, savedCounter + 256], the packet is accepted and Alice sets savedCounter(Bob) to the counter from the packet;
- else (Alice has no counter information about Bob or Alice has counter information about Bob and the counter is outside of that range), Alice parses Challenge TLVs, silently ignores any non-Challenge TLVs in Bob's packet and sends a challenge (with rate limiting)

Only the challenges contain an arbitrary-length opaque nonce.

The counter should be 48 or 64 bytes long.
- Devices who believe they have reliable monotonically increasing clocks can use their time as a counter
- Devices that can save their counter to disk start at zero and increase for each packet send
- Devices that have neither start off with a random counter then increment by one for the duration of this boot. The security for those devices depends on how much entropy they have in the high order bits of their initial random counter value.

This proposal has Properties D and M, and also

Property S: if Alice and Bob do not have clocks or storage and they reboot at the same time, they are still secure as long as there are enough bits of entropy in the high order bits of their initial counters to ensure that those won't intersect with values they previously chose.

Property R: If something goes wrong (reliable clocks aren't, etc.) devices are able to reestablish communication after 1RTT

Conceptually this is similar to treating the high order bits of the counter as a nonce in cases where you do not have a clock or storage. So I guess for those devices property M is somewhat not quite guaranteed-ish...

Also, to handle reordering we can have a replay window similar to IPsec/ESP where Alice keeps a bit mask of packets received in [savedCounter - 256, savedCounter - 1] to allow receiving out of order packets in that range.

David