Re: [Cfrg] misuse-resistant AEAD

[David McGrew <[e-mail]>]

On 01/02/2014 10:31 AM, Watson Ladd wrote:
>
>
> On Jan 2, 2014 10:03 AM, "David McGrew" <[e-mail] 
> <mailto:[e-mail]>> wrote:
> >
> > Hi Paul,
> >
> > On 12/30/2013 02:06 PM, Paul Lambert wrote:
> >>
> >>
> >> On 12/29/13, 1:12 PM, "Paul Hoffman" <[e-mail] 
> <mailto:[e-mail]>> wrote:
> >>
> >>> On Dec 29, 2013, at 11:12 AM, Stephen Farrell 
> <[e-mail] <mailto:[e-mail]>>
> >>> wrote:
> >>>
> >>>> . . .
> >>>> I would love to see ongoing detailed work within
> >>>> CFRG as to how to counter pervasive monitoring.
> >>>
> >>> Wearing your perpass hat, how can CFRG help? I ask this because I have
> >>> seen little on the perpass mailing list that indicated that an 
> even minor
> >>> problem has been lack of crypto, or the use of crypto that is 
> thought to
> >>> be breakable. What type of crypto research or assessment would help
> >>> perpass?
> >>
> >> 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.
>

This combination of algorithms doesn't require a distinct nonce, and it 
can be secure if the encoding and IV generation is done correctly, but 
it lacks other desirable properties.   For instance, it uses serialized 
computations, expands the data a lot, is not robust against misuse of 
decrypted data prior to verification.

If you are interested in seeing that combination of algorithms used 
more, you should review draft-mcgrew-aead-aes-cbc-hmac-sha2 and offer 
your support, or suggestions for improvements.   My opinion of that 
draft: it would be better if the IVs were generated pseudorandomly and 
if ciphertext stealing were used (to avoid side channels on the 
decryption side).    There are better algorithms, so it is not clear how 
much effort the industry should spend on doing the combination of CBC 
and HMAC better.

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

Right, and I'm not advocating such things.

> Nonce reuse resistant nonce based MAC and encryption algorithms exist 
> today, namely CBC initialized with the encryption of a counter and HMAC.
>
> >>
> >> I¹ve asked NIST in the past and they have expressed no interest in the
> >> problem.  It used to be very important for algorithms to be NIST 
> approved.
> >>   Do we need to find/create a new review and approval process for
> >> algorithms that can be referenced by commercial products?
> >
> >
> > NIST is responsive when the industry and standards organizations 
> adopt new mechanisms that have some clear advantage over previous 
> mechanisms.   The problem is that NIST and the industry have gotten 
> into a deadlock (or deadly embrace) situation: the industry now 
> hesitates to adopt algorithms that are not NIST approved, and NIST 
> hesitates to approve algorithms that have not seen any adoption by 
> industry or standards.    We can not just blame NIST for being overly 
> conservative here; there are many more algorithm proposals than they 
> could reasonably incorporate into their processes.   To break the 
> deadlock, we (CFRG and the industry) need to be willing to adopt a new 
> algorithm, or at least we need to be willing to take further steps 
> towards adoption than we have shown in the past. Some things that CFRG 
> could do: write a requirements document that demonstrates the need for 
> a new algorithm, publish a document specifying the new algorithm, 
> document the fact that there is a set of adopters or potential 
> adopters that are interested, and lastly, reach out to NIST (for 
> instance, with a question like "do you have any particular concerns 
> about this algorithm that would prevent you from approving it?").
> >
>
> CAESAR is going on right now with regards to AE. If you have 
> requirements that haven't been in the call, tell us about them.
>

Yes, I will.   I'm on the CAESAR review committee, and I'm a fan of many 
aspects of the program.   The call for submissions allows a submission 
to use a deterministic nonce, and that might be OK in some situations, 
but there are other situations where it is highly undesirable.   The 
call also allows submissions that don't use a deterministic nonce.   
This inclusiveness is clearly the right thing for CAESAR.   But what the 
world needs more of are algorithms in the latter category, or at least 
algorithms that are more robust against misuse.

David

> > Going further, it might facilitate adoption if all of the 
> information needed to validate an implementation of an algorithm were 
> provided.   That is, a complete set of test cases in a format suitable 
> for automated validation (as done in the NIST Crypto Module Validation 
> Program, or CMVP) would make it easier to incorporate the algorithm in 
> an implementation-validation process.
> >
> > The CMVP is run jointly by the U.S. and Canada.   It would be good 
> to hear from the rest of the world on this topic.  I suspect that many 
> vendors outside of Northa America want to sell into the NA market, and 
> thus also would favor NIST approval of new algorithms. What is less 
> clear is the role of nation-specific block ciphers (or other 
> algorithms), which is a topic unto itself.
> >
> > David
>
> Sincerely,
> Watson
> >
> >>
> >> Paul
> >>
> >>
> >>
> >>
> >>
> >>
> >>
> >>> Note that deprecating the use of crypto that is widely known to be 
> broken
> >>> is the purview of IETF WGs, not the CFRG. The relevant WGs 
> (particularly
> >>> TLS) seem to already be doing that.
> >>>
> >>> --Paul Hoffman
> >>> _______________________________________________
> >>> Cfrg mailing list
> >>> [e-mail] <mailto:[e-mail]>
> >>> http://www.irtf.org/mailman/listinfo/cfrg
> >>
> >> _______________________________________________
> >> Cfrg mailing list
> >> [e-mail] <mailto:[e-mail]>
> >> http://www.irtf.org/mailman/listinfo/cfrg
> >>
> >
> > _______________________________________________
> > Cfrg mailing list
> > [e-mail] <mailto:[e-mail]>
> > http://www.irtf.org/mailman/listinfo/cfrg
>