Re: [Cfrg] misuse-resistant AEAD (was: Re: CFRG and thwarting pervasive montoring)

[Watson Ladd <[e-mail]>]

On Thu, Jan 2, 2014 at 5:06 PM, Dan Harkins <[e-mail]> wrote:
>
>
> On Thu, January 2, 2014 7:31 am, Watson Ladd wrote:
>> On Jan 2, 2014 10:03 AM, "David McGrew" <[e-mail]> wrote:
>>>
>>> Hi Paul,
>>>
>>> On 12/30/2013 02:06 PM, Paul Lambert wrote:
>>>>
>>>> In the past I¹ve never considered CFRG a viable discussion forum for
>>>> making an impact by creating or approving new algorithms Š but if it
>>>> is:
>>>>
>>>>         We need an Œapproved' nonce-insensitive AEAD algorithm.
>>>>
>>>> I¹m designing multicast communications in a mesh topology and CCM and
>>>> GCM
>>>> suffer from N^2 complexity (since they require unique nonce/key).  Yes
>>>> Š
>>>> there are ways that some link proposals like 802.1ae mitigate the issue
>>>> using device addresses as part of the key setup.  The best solution is
>>>> a
>>>> nonce-insensitive AEAD.
>>>
>>> I agree.   The best solution would be an authenticated encryption
>> algorithm that did not require a nonce as input.   An alternative which is
>> not quite as good would be an algorithm that requires a nonce as input,
>> but
>> which has security that suffers only a minimal degradation if nonces are
>> repeated.
>>
>> Already exists: it's called CBC mode with HMAC. IVs are random and can
>> repeat.
>
>   There are still security sensitive requirements on IVs in CBC mode.
> Namely, they have to be unpredictable to the attacker. That problem does
> not exist with SIV. The nonce is completely arbitrary, it can be a counter,
> pseudo-random material, it can be partially derived, it can repeat or not.
>
>   And as a formal AEAD construction SIV avoids the ad hoc nature in which
> CBC plus HMAC has been put together in the past. It also has a nice and
> fixed API for things like passing AAD as a vector of inputs.

CBC+HMAC is an instance of generic composition. So is GCM and
Chacha/Salsa/XSalsa/Poly1305.
What sort of device can encrypt, but not use a PRNG or count?

>
>>>> We already have an RFC for SIV which is deterministic and a decent
>>>> solution, but it is not ŒNIST¹ approved, so I have problems
>>>> introducing
>> it
>>>> into consumer equipment.  It¹s also a little slow Š but I¹m not sure
>>>> that
>>>> efficiency should be the primary evaluation criteria.
>>>
>>>
>>> All valid points.   SIV shows that it is possible to have a
>> misuse-resistant algorithm.  It may not have all of the properties that
>> one
>> might want in an algorithm (for instance: more amenable to parallel
>> processing), but it shows that we can achieve more robust security than
>> nonce-based AEAD.
>>>
>>
>> Deterministic encryption leaks considerable information when used on low
>> entropy messages. Nonce reuse resistant nonce based MAC and encryption
>> algorithms exist today, namely CBC initialized with the encryption of a
>> counter and HMAC.
>
>   With SIV, authenticity remains and the leakage is limited to knowledge
> that the plaintext equals a prior plaintext, and that is further constrained
> by the fact that it's the same plaintext plus the same AAD, if the AAD
> changes (due to a message header that encapsulates the encrypted blob
> being different) then there is no leakage.
>
>   It really is the "swiss army knife" of crypto tools-- it slices, it dices,
> it provides misuse-resistant AEAD, it does key wrapping with AAD!
> (And it has a security proof behind it too).

It's wonderful, but slow as molasses. 2 AES passes, only 1 of which
can be parallelized.
For the example of mesh networking it certainly has a place, but I
don't know if the security
is really that great for that application.

For example, imagine a simple message format with (sender, dest) as
header and a temperature as
the message. A mesh network passing around temperature measurements
will reveal a lot to a passive attacker:
remember temperatures are continuous, so all you need is the direction
change the same or different as before to
see just about everything.

Add a counter and everything is golden. But you need that counter. And
if you have a counter, nonce-based misuse-resistant
is just fine, and moreover can be done faster than SIV at the cost of
leaking common prefixes.

Authenticity doesn't make sense with repeated nonces. All you get is
the attacker cannot introduce new messages, but
they can still repeat old ones. This can be enough to have some fun.

>
>   regards,
>
>   Dan.
>
>
>
Sincerely,
Watson Ladd


-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin