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

["Dan Harkins" <[e-mail]>]

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.

>>> 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).

  regards,

  Dan.