Subject: RE: [Cfrg] Draft minutes for CFRG meeting in Atlanta

From: "David A. Mcgrew" <[email-masked]>
Date: Mon, 9 Dec 2002 08:12:15 -0800

Phill,

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]]On Behalf Of
> Hallam-Baker, Phillip
> Sent: Tuesday, November 26, 2002 7:50 AM
> To: [email-masked]
> Subject: RE: [Cfrg] Draft minutes for CFRG meeting in Atlanta
>
>
> Question, do we really need to address parallelization at the stream
> level?

it is certainly preferable.  Actually, the low-cost counter mode systems have a
pipelined architecture, rather than a parallel one.  I believe that's not an
important distinction from an algorithm design standpoint, though.  An algorithm
which can be implemented in parallel is one that can be pipelined.

>
> OK so we have a 10Gb/sec firehose feeding us bits.
>
> Let us say we want to apply 8 parallel processing units to the problem.
>
>
> One approach (the hard way) is to look for some means of precalculating
> or otherwise parallizing the processing steps necessary to implement the
> cipher block chaining algorithm.

Ah, but many crypto algorithms are not amenable to this kind of optimization.
Functions like AES with the 'avalanche effect' that changing a single bit of
input affects all output bits typically have long critical paths in their
computation graphs.

>
> Another approach would be to establish 8 independent (or
> quasi-independent) sets of keying information and then partition the
> stream into 8 interlaced substreams, so taking 4 substreams for the sake
> of simplicity we would have:
>
> A B C D A B C D A B C D [A] [B] [C] [D]
>
> where [X] stands for the checksum of stream X.
>
> It may even be possible to collapse down the 4 separate checksums into
> one with appropriate cryptographic caution likely to be chaining mode
> dependent.
>
>
> OK so this is not as pretty as doing the thing in an integrated fashion,
> the sender and receiver have to negotiate features such as the number of
> streams to use. However I assert that if you are going to insist on
> being on the bleeding edge such pain should be expected. Wherever a
> 10Gb/sec sender is to be found there had better be a 10Gb/sec receiver
> connected thereto and the two had better have a somewhat intimate
> relationship if the implementation technology is clocked at 2GHz or
> so...
>
> So ultra parallel composability is a 'nice' feature but certainly not
> interesting enough to get all hot and patent encumbered over.

The speed limit for an AES mode of operation which can't be pipelined will be
significantly lower than a mode which can be pipelined.  For ten-round AES 128,
it's probably around a factor of ten different.   There's also a similar cost
difference for both methods at the same throughput, at least at higher speeds.

All that said, I admit that I'm not a hardware expert.  Perhaps someone who is
one can chime in with more info.

On the IPR issue, I agree that it is easiest and best when we can avoid using
encumbered algorithms.  Though if the licensing terms were reasonable and the
licensing process were simple, I'm not sure how many vendors would care about
it.  The "simple" part seems to often be the hardest.

David

>
>
> 		Phill
>
> > -----Original Message-----
> > From: Russ Housley [mailto:[email-masked]]
> > Sent: Tuesday, November 26, 2002 9:19 AM
> > To: Brian Weis; [email-masked]
> > Subject: Re: [Cfrg] Draft minutes for CFRG meeting in Atlanta
> >
> >
> > Brian:
> >
> > Please see corrections below.
> >
> > Russ
> >
> >
> >
> > >CM: Counter Mode with CBC-MAC
> >
> > CM -> CCM
> >
> > >Russ Housley, RSA Labs
> > >-----------------------------
> > >
> > >Russ Housley gave a presentation on his Counter Mode with
> > CBC-MAC (CCM)
> > >mode draft (draft-housley-ccm-mode-00.txt).  It is a combined mode of
> > >operation (providing both encryption and authentication).
> > >
> > >CCM is currently  mandatory to implement in the IEEE 802.11i
> > draft, and
> > >has been submitted to NIST for consideration as a mode for
> > AES. Multiple
> > >implementations are available, and information on them is
> > available at
> > >http://www.hifn.com/support/scm.htm. Russ would like to published CCM
> > >as an Informational RFC, and this group seems to be an
> > appropriate place
> > >for submittal.
> > >
> > >Russ mentioned that CCM may be covered by up to three
> > different patents,
> >
> > NO!  Alternatives to CCM, such as OCB, may be covered by these
> > patents.  CCM is the only authenticated encryption algorithm
> > that I know
> > about that is not encumbered.
> >
> > >but each of the authors has been gracious enough to
> > explicitly release
> > >any IPR rights into the public domain.
> > >
> > >David asked about performance limits of CCM. Russ replied that
> > >one of the motivating factors for this work was for the mode to
> >
> > Only the encryption part is parallelizable.  The
> > authentication is not.
> >
> > >be parallelizable. The encryption key stream of the mode is even
> > >pre-computable. So the limiting factor is the CBC-MAC integrity
> > >operation. He doesn't have any good data on when that becomes the
> > >bottleneck. Someone mentioned that in this application, the
> > constrained
> > >engineering limitation is the amount of resource available to do the
> > >processing. Dealing with the device limitations was a more important
> > >consideration than speed.
> >
> > _______________________________________________
> > Cfrg mailing list
> > [email-masked]
> > https://www1.ietf.org/mailman/listinfo/cfrg
> >
>

_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: [email-masked] (David Wagner)
Date: 17 Dec 2002 07:36:15 GMT

Brian Weis  wrote:
>Attached are the draft minutes for the Atlanta meeting.
[...]
>NIST Crypto modes status
>Bill Burr, NIST
[...]
>The first thing they concentrated on after that was a block cipher MAC.
>They needed one without IPR claims. RMAC was submitted (NIST Special
>Publication  800-38B. Comments are still open but December 2, 2002 is
>the closing date.

The public comments have been posted at
  http://csrc.nist.gov/encryption/modes/comments/
If the CFRG is interested in considering RMAC, I encourage you to read
the concerns described in Phil Rogaway's and my comments, as well as
the other comments and the response from the designers.

One of the concerns Phil Rogaway raised is that the proof of security
for RMAC is in the "ideal cipher model".  Phil pointed out that is not as
desirable as a proof of security in the standard reduction-based setting
(and I agree).  In particular, security in the "ideal cipher model" does
not necessarily guarantee security in the real world.  I recently wrote an
email trying to explain why the "ideal cipher model" is not so ideal for
evaluating modes of operation, and David McGrew encouraged me to forward
it here, so it is listed below, for your information.  Comments welcomed.

...

I can elaborate a bit on Phil's comments on the ideal cipher model.
I think this truly is important.  To show you that this is more than just
quibbling over the theory, I can give a vivid example of what can go wrong
with the ideal cipher model.  Funnily enough, my example is 3DES-RMAC,
exactly the mode we're talking about, but that's just a coincidence.

If you remember, 3DES-RMAC was proven secure in the ideal cipher model
a year ago.  But then if you look at the public comments to NIST, you'll
notice that Lars Knudsen has a very recent paper showing that 3DES-RMAC
is broken.

What's going on here?  We have a scheme that looks like it was proven
secure, and yet we have someone claiming a working attack on it.
That's not supposed to happen!  Clearly *someone* has some explaining
to do.  Let me try to resolve the paradox, but first let me back up and
give a little background.

As Phil said, the ideal cipher model implicitly encodes the assumption
that the cipher is secure against related-key attacks (as well as other
assumptions, but let's just take related-key attacks as one example for
the moment).  If your block cipher is susceptible to related-key attacks,
then it would be inappropriate to model it as an ideal cipher.

Now we can look at 3DES.  RMAC was proven secure in the ideal cipher
model, which means that 3DES-RMAC "ought" to be secure if 3DES can be
modelled faithfully by an ideal cipher.  For these and other reasons,
NIST's RMAC standard included 3DES-RMAC as one of the two options.

However, it's known that 3DES is not secure against related-key attacks
[1], which should already make you a little queasy.  Now you might hope
that maybe the assumption of security against related-key attacks is
something needed only to make the proof go through, but maybe security
against related-key attacks isn't required in practice.  Maybe.

But it turns out that such a hope gets dashed against the rocks when you
read Lars Knudsen's note to NIST [2].  Knudsen breaks 3DES-RMAC using 2^16
chosen messages and about 2^56 work.  If you read his attack carefully,
you'll recognize that it looks familiar: It is almost the same as the
related-key attack on 3DES, but this time extended a little so that it
breaks RMAC.

So now we can explain what happened here.  The proof of security for RMAC
only works if you assume use an ideal cipher.  If you want to draw any
conclusions about RMAC with a real block cipher like 3DES or AES, you
have to hope that your real block cipher behaves enough like an ideal
cipher that the same proof still carries over.  In the case of 3DES,
that hope was ill-founded: 3DES is not well modelled as an ideal cipher,
because 3DES is vulnerable to related-key attacks, whereas ideal ciphers
are supposed to be secure against related-key attacks.  And as Knudsen
showed, if there are related-key attacks on your real block cipher,
this not only renders the proof irrelevant and "invalidates the security
warranty", it can also lead to serious attacks on RMAC.

After all this explanation, maybe the most interesting question is whether
AES-RMAC is secure.  If you want to think that the proof of security for
RMAC says anything about AES-RMAC, you have to hope that AES behaves
like an ideal cipher.  One necessary condition for the latter is that
AES must be secure against related-key attacks.

Yet I'm not very confident that the security of AES against related-key
attacks has been well-studied.  In my experience, cryptanalysts mostly
focus on the standard threat model (chosen plaintext/ciphertext attacks),
and related-key attacks are only occasionally studied.  What little we do
know about the security of AES against related-key attacks suggests that
AES may have less strength against related-key attacks than against normal
attacks: The best standard attacks on AES break 7 or 8 rounds, while
the best related-key attack breaks 9 rounds [3].  (I'm excluding the XSL
attacks from consideration here, because there is still controversy about
whether they work.)  Also, if you look at the AES key schedule, you'll see
that it has a lot less "cryptographic goo" than the AES round function.
This makes me worry about assuming that AES can be safely modelled as
an ideal cipher -- at the least, it seems to be less safe than assuming
that AES is secure against standard chosen-plaintext/ciphertext attacks.

The lesson I draw from this experience is that the proof in the ideal
cipher model is not as helpful as we'd like; it doesn't give me as much
confidence as a reduction-based proof would.  I tried to make this point
in my letter to NIST [4], but I'm not sure whether this was clear or not.
Feel free to read my letter for a bit more elaboration on these points
if you like.

I hope this explains you why we are a little concerned and convinces
you that this concern is not merely "academic".  Please don't hesitate
let me know if there's anything here that didn't make sense!

-- David

[1] John Kelsey, Bruce Schneier, and David Wagner.  "Key-schedule
cryptanalysis of IDEA, G-DES, GOST, SAFER, and triple-DES."  CRYPTO
'96. http://www.cs.berkeley.edu/~daw/papers/keysched-crypto96.ps

[2] Lars R. Knudsen.  "Analysis of RMAC".  NIST public comment.
http://csrc.nist.gov/encryption/modes/Recommendation/Knudsen_RMAC_paper.pdf

[3] Niels Ferguson, John Kelsey, Stefan Lucks, Bruce Schneier, Mike Stay,
David Wagner, and Doug Whiting.  "Improved Cryptanalysis of Rijndael".
FSE 2000.  http://www.cs.berkeley.edu/~daw/papers/rijndael-fse00.ps

[4] David Wagner. "Comments on RMAC".  NIST public comment.
http://csrc.nist.gov/encryption/modes/Recommendation/Wagner_RMAC_comments.pdf
_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg