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

From: Brian Weis <[email-masked]>
Date: Mon, 25 Nov 2002 12:19:27 -0800

Attached are the draft minutes for the Atlanta meeting. Please forward
corrections to me (or send to the list if you like).

Thanks,
Brian

-- 
Brian Weis
Strategic Cryptographic Development, ITD, Cisco Systems
Telephone: +1 408 526 4796
Email: [email-masked]

November 19, 2002
Crypto Forum Research Group (CFRG) Meeting
IETF 55, Altanta

The meeting was brought to order by Co-chair David McGrew. It was
announced that Co-chair Ran Canetti was not present due to the recent
arrival of a child. Congratulations, Ran!

David gave an overview of CFRG. Its goals are to bridge the areas of
cryptographic theory and practice, bringing the two areas together. CFRG
is an IRTF research group which is not part of the IETF, and it will
not be producing cryptographic standards. The group should bring clueful
people together, both theoretical cryptographers and practitioners.

Since the group has just been formed, there is no current work
to report.  Future work that the group may pursue is parallelizable
message authentication and cryptographic transforms (for example,
combined transforms). A future meeting may be co-located with an IACR
venue in order to get participation from some theoretical cryptographers.

Some items from the CFRG mailing list were discussed. David
mentioned that both he and Scott Fluhrer have looked at the W7 cipher
(draft-thomas-w7cipher-03.txt) and will be posting analysis of it
soon. The goal is unique: to provide high speed crypto in as few gates
as possible.

Jon Callas gave an overview of the PGP message integrity problem, which
resulted in a lively discussion.  Earlier message formats didn't have
any message integrity. The proposed method of adding message integrity
involves adding a "modification detection code" (an unkeyed hash) to
end of the plaintext. However, the encryption mode used is CFB. CFB has
the property that bytes can be lopped of the end of the message without
detection. David Wagner has pointed out that this simple addition of an
unkeyed hash is not sufficient as it can theoretically be broken. The
question was posed by Jon as to whether the problem was sufficiently
bad that a fire alarm should be pulled? Hugo Krawczyk pointed out that
the problem was not merely theoretical, since any attacker which can
successfully decrypt the message can change the message, re-compute
the unkeyed hash to place at the end of the modified data, and then
re-encrypt the message making it appear to be the original message. There
seemed to be a consensus of attendees that this method was worse than
no integrity at all, and should be dropped in favor of a more secure
message integrity method.

David pointed out that the UMAC Internet-Draft had expired, apparently
due to a lack of interest by the authors. Hugo indicated that he
had originally written the I-D to garner interest in super fast MAC
functions, but let it expire due to an apparent lack of interest by
others.  Hugo said if there is interest that he would gladly re-submit
the draft.  David asked if anyone had implemented it other than the
authors, and Hugo replied that he did not know of any. David said
that he was interested, but found that it wasn't trivial to write a
well-performing implementation.  It was pointed out that Wei Dai had
also mentioned an interest in UMAC on the list.

The rest of the meeting was filled with presentations.

CM: Counter Mode with CBC-MAC
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,
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
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.

Advice on writing an Intern ate draft amenable to security analysis
Catherine Meadows, NRL
------------------------------------------------------------------

Catherine has been working for a number of years on semi-automated
security reviews of IETF drafts. Numerous times she found it would be
more useful if certain things were included in the drafts. She wrote
draft-irtf-cfrg-advice-00.txt to document those results for the use of
Internet Draft writers.

A security analysis is an assessment in how well the protocol functions
in the case of possible attacks. There are three types of attacks:
informal, formal, and reduction-based mathematical. All three types of
methods can be valuable, even when applied to the same protocol.

There are generally three types of information that need to be provided:
information on what the protocol does and how it operates, information
on the protocol's environment, and information on the protocol security
requirements.

David mentioned that in order for people to state the goals of a protocol,
we need a uniform terminology. For example, message authentication
is also sometimes called source origin authentication and data origin
authentication.  he asked if anyone knew of a document which might help
CFRG use common terms.  Russ mentioned that RFC 2828 might be helpful.
David commented that unfortunately, while that RFC has many good definitions, 
the Secure RTP authors found its definitions of message authentication were 
not sufficient for use in the SRTP I-D.

Determining Strengths For Public Keys Used For Exchanging Symmetric Keys
Hilarie Orman & Paul Hoffman
------------------------------------------------------------------------

Hilarie was not present, so David summarized
draft-orman-public-key-lengths-05.txt.  AES is wonderful new tool with
high security levels. It's worth doing the analysis to see what key
lengths we need to get those security levels. It turns out some of the
key lengths are really big, which might make us think about performance
for public key crypto.

David asked if the draft had been submitted for an Informational RFC.
Paul Hoffman said that the he and Hillary had handed it to the security
ADs, but they haven't heard back from them yet. Steve Bellovin (IETF
Security AD) said that a last call in this group would be a perfect thing
to do. Ran Atkinson pointed out procedurally that an IETF document can't
be put in last call in an IRTF group, and Steve said it would be fine to
re-submit it as an IRTF draft so that it could be taken forward by CFRG.

Paul said that the authors know that the draft is contentious, and some
people disagree with the numbers. But they want to know if they hit the
right topics.  Paul said that he hoped others would agree with their
methodology even if they didn't crunch the numbers the same way. They
did get a bunch of cryptographers together to discuss numbers, but there
was no consensus.  So their hope is that this document could be used as
guidance to cryptographers, to help them make their own conclusions. They
tried to stick with Moore's law and previous computations.  They also
put in other peoples' analysis .

Phillip Hallam-Baker asked if it is useful to have a draft that says "such
and such an RSA key size is equivalent to a symmetric key". It's useful to
say that "we know that this RSA thing is no more secure than this". As for
how secure it is, it's not like a symmetric key analysis where there's
just one dimension to consider. But with RFS there's more: processor
vs. memory tradeoff, so you can always argue about the tradeoffs.

Ted T'so said that the whole time/memory tradeoff issue would be very
useful to have some general understanding, about what is and isn't
realistic. If some of the original ad-hoc key length recommendations
ignored the storage problems but assumed super-fast FPGAs then that's
one thing. Ted said he has trouble conceiving feasibility with huge
amounts of memory, memory larger than project Purple which is going
to cost a tremendous amount of dollars.  If this group could issue
comments on that, it would be very helpful.  We've always talked about
single-dimension analysis in the past, so this is so different. For
example, do you also need associative memory, or need a btree in order
to organize the information, etc.

NIST Crypto modes status
Bill Burr, NIST
------------------------

Bill is the manager of that security technology group at NIST
responsible for PKI and crypto standards. The current modes of operation
are documented at http://csrc.nist.gov/encryption/modes.

NIST has held two Modes of Operation workshops: Baltimore in October of
2002, and Santa Barbara in August of 2001. A total of 17 modes have been
submitted, and NIST has an ongoing review process.

They first revisited the four classic modes. All are still recommended,
including ECB, which although some people think it's playing with fire,
some people still want it. NIST then added Counter mode.

For Counter Mode, they've made the statement that the counter should
not repeat, and recommended that people should use counters that fit
their application.

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.  RMAC requires two keys, where one is derived from
the first.  There are options, such as you can choose to not expand the
hash. If you're worried about collisions, then you can deal with that too.

They are likely to consider a CBC-MAC mode next. It's like a freight
train which has already left the station! NIST would like Federal users
to be free to use it like anyone else. Assuming no one turns up awful
problems with CCM, we'll produce another recommendation incorporating CCM.

Also AES key wrap had been considered as part of the key management work
that NIST is doing. But a number of folks have taken it (e.g., SMIME),
so NIST might extract it to a standalone encryption mode document.

David asked why NIST chose RMAC over XCBC? The reason he asked is that
someone in IPsec produced a draft based on XCBC. It would be helpful to
know if if there was anything wrong with that mode, or if it was the
next one to be considered. Bill replied that they just thought RMAC
was better because it saved an encryption. He also said that their
"friends at the Fort" told them that RMAC was better, and they weren't
very specific why! But he doesn't know that there IS actually a problem
with XCBC. Furthermore, he really just wanted to limit one of the two
block cipher MAC modes. They could have done two of them, but it made
more sense to do just one. Some people didn't think even one of the
ciphers was needed, since it was just something more to add to their chip!

David mentioned to the meeting that it was not necessary to format a
document as an Internet-Draft for CFRG to review it. In someone has a
mode of operations document that has been sent to NIST, they were also
welcome to submit it to this group as well.

The Universal Security Transform (UST)
David McGrew
--------------------------------------

There are three drafts which specify UST. draft-irtf-cfrg-ust-00.txt
is the main draft, and the other 2 describe algorithms which fit
into the transform. Those drafts are draft-irtf-cfrg-tmmh-00.txt and
draft-irtf-cfrg-icm-00.txt.

The goals of UST is to have a simple interface, with a transport
and encoding independent scheme. It's similar to a combined mode of
operation. David also wanted the transform to have minimal data expansion,
a minimized cost, and to be parallelizable. He'd like to see UST go as
fast as 10 Gbits/second next year.

UST has a keystream generator (ESA integer counter mode, which uses
counter values as integers) and a universal hash (TMMHv2).

Inputs to UST have both a "clear" and "opaque" field. The clear portion of
the message is the part you want to be protected by message authentication
but not encrypted. The opaque section is both authenticated and encrypted.

Outputs of UST are an index, ciphertext, and an message authentication
tag.  You can use UST for authentication only if you make the opaque
field 0 length.  The index is the output of the transform, and does not
rely on the user for synchronization.

TMMHv2 is the hash algorithm proposed for UST, and it has about 140 byte
keys.  Integrated Counter mode (ICM) is used as the keystream generator.

---

From: Russ Housley <[email-masked]>
Date: Tue, 26 Nov 2002 09:19:16 -0500

Brian:

Please see corrections below.

Russ

>CM: Counter Mode with CBC-MAC

CM -> CCM

>Russ Housley, RSA Labs

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.

>one of the motivating factors for this work was for the mode to

Only the encryption part is parallelizable.  The authentication is not.

>consideration than speed.

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

---

From: Jack Lloyd <[email-masked]>
Date: Tue, 26 Nov 2002 16:10:34 -0500 (EST)

On Mon, 25 Nov 2002, Brian Weis wrote:

> well-performing implementation.

GNU's Java crypto library has an implementation UMAC32:
http://www.gnu.org/software/classpathx/crypto/crypto.html

I'm considering implementing UMAC16, at least, and seeing how well x86
compilers can auto-MMX it. But it is a quite complicated algorithm, and the
lack of official test vectors makes things even more challenging.

> the first.

I wrote up a paper a couple of weeks back showing that RMAC can be attacked
faster than brute force with a few MAC queries. Today I was informed that
Lars Knudsen has developed a variant of the attack which uses less work but
a lot (>2^120 for AES) of MAC queries. Both papers are avaiable on NIST's
comments page. I wasn't aware CFRG was considering standarizing RMAC or I
would have mentioned it on the list. I have been given no indication that
NIST is considering tweaking RMAC to prevent the attacks (none of them are
at all practical), but it's possible.

-Jack