Subject: [Cfrg] CCM

From: "Housley, Russ" <[email-masked]>
Date: Tue, 03 Sep 2002 09:14:48 -0400

The discussion on my CCM mode Internet-Draft has gone quiet.  This could 
mean one of two things: (a) people are satisfied, and it is time to publish 
an Informational RFC; or (b) people are still reviewing it.  To find out, I 
request that the chairs conduct a Last Call on the document.

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

---

From: David Hopwood <[email-masked]>
Date: Tue, 03 Sep 2002 18:18:18 +0000

-----BEGIN PGP SIGNED MESSAGE-----

"Housley, Russ" wrote:
> an Informational RFC; or (b) people are still reviewing it.

(c) People are waiting to see the claimed security proof before commenting.

- -- 
David Hopwood <[email-masked]>

Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5  0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip

---

From: "Housley, Russ" <[email-masked]>
Date: Tue, 03 Sep 2002 15:12:18 -0400

David:

The proof is now available.  I sent it to you.  I have also sent it to 
NIST, so hopefully it will be put on their web site for everyone to fetch.

Russ

At 06:18 PM 9/3/2002 +0000, David Hopwood wrote:
>-----BEGIN PGP SIGNATURE-----
>Version: 2.6.3i
>Charset: noconv
>
>iQEVAwUBPXT81jkCAxeYt5gVAQFHJggArUqjVsUpvTTKTOoVhXNCksOuHZ7PBaJm
>mwu3CIi0VyY9Ev5xnt4E6NBHylO7PqMz8dIX3Jd5p8Y1Grif08Xuj2Uj1XAXNWk1
>vp7Yzw8ItvdxH8F9adse8k1rxgqIrCfyngxD21h5rafVPYvyed7aD2TlW1t5jILp
>p6xGvsLAgQ8c36DsEH/gwnT5fcgbXnwxDuuaRYy5Q4ntImD+a2myojgn5fVx9N/y
>bYETow+OLjOl/jE2OO85+5q3DFRdApOjXaG4hKJREBZ0cY1lKbj2MLEoPkVDoa1F
>j6hs8m2twbb/vjH3Cr3Xeoi3TeTl8FedFKMnVSenpRCy5LRcOnccJQ==
>=oavw
>-----END PGP SIGNATURE-----

---

From: David Hopwood <[email-masked]>
Date: Wed, 04 Sep 2002 00:27:15 +0000

-----BEGIN PGP SIGNED MESSAGE-----

> NIST, so hopefully it will be put on their web site for everyone to fetch.

OK, here are my comments:

 - the security proof depends on the fact that the nonce N is independent
   of any previous ciphertext. The draft only says that it must be
   unique. Actually, it's not sufficient that it be unique: it must
   also be impossible for an attacker to influence the choice of nonce.

 - the "additional authenticated data" corresponds to the "label" of a
   Data Encapsulation Method as defined in [Shoup01]. Please mention this
   correspondance.

 - the security proof paper uses different names for some variables
   (a -> H and m -> M), and also refers to the label as the "header".
   The draft and the paper should be consistent (it doesn't matter
   which one is changed). Section 2.3 of the paper should probably
   also fully describe the encoding function in the draft, for
   completeness.

 - the bit numbering convention for the Flags field is not explicitly
   stated (I assume it's that bit k has weight 2^k). Since octet values
   are integers from 0 to 255, it would be clearer to specify how the
   Flags field is encoded as an integer:

     Flags = 64*Adata + 8*M + L  (in section 2.2)
   and
     Flags = 8*M + L             (in section 2.3)

 - the draft assumes that the interface to the block cipher is defined in
   terms of octet strings. The AES FIPS strictly speaking only defines the
   interface to AES in terms of bit strings. The draft should therefore
   specify that when used with AES, the most significant bit of each octet
   corresponds to the first bit of the octet as defined by the AES FIPS.
   (This is in practice what all AES implementations do.)

 - in section 2.4:
   # The final result c consists of the encrypted message m, followed by
   # the encrypted authentication value U.

   U is indeed the encrypted authentication value, but m is the variable
   name for the plaintext message.

 - decryption should be described more explicitly in section 2.5, rather
   than having to be inferred from encryption.

 - in section 2.6:
   # All implementations MUST limit the total amount of data that is
   # encrypted with a single key.  The sender MUST ensure that the total
   # number of block cipher encryption operations in the CBC-MAC and
   # encryption together does not exceed 2^61.

   (2^61 * 16)/2 octets is 16 exabytes (~ 16 million terabytes).
   It's extremely unlikely that this amount of data would (or could)
   be encrypted with a single key, even if an implementation did not
   include an explicit check. However, this paragraph could be
   interpreted as requiring that implementations include an explicit
   check, and that protocols include some mechanism for changing keys
   that will increase the protocol complexity, even though these
   are unlikely to ever be triggered in practice.

 - it might be useful to use this mode with block ciphers (or PRFs) that
   encrypt > 16-octet blocks in future. It would be no more complicated
   to define the mode generically for z-octet blocks (provided that z >= M,
   and z-1-L octets is large enough for the nonce).

 - the draft should informatively reference the security proof paper.

 - before the draft is published as an RFC, someone should write an
   independent implementation and check that it matches the test vectors
   in section 8.

[Shoup01] Victor Shoup,
          "A Proposal for an ISO Standard for Public Key Encryption
           (version 2.1)",
          Revised December 20, 2001.
          <http://www.shoup.net/papers/>

- --

---

From: David Hopwood <[email-masked]>
Date: Wed, 04 Sep 2002 03:00:38 +0000

-----BEGIN PGP SIGNED MESSAGE-----

>    also be impossible for an attacker to influence the choice of nonce.

I take this back; the proof only depends on the nonce being independent
of the cipher inputs used to compute the MAC (which are hidden from the
adversary), not the ciphertext. So the nonce does only need to be unique
(unless I've missed something else).

- --

---

From: "Housley, Russ" <[email-masked]>
Date: Fri, 06 Sep 2002 17:06:24 -0400

David:

Thank you for taking the time to review the CCM Internet-Draft.  Please 
seem my responses below.

>    also be impossible for an attacker to influence the choice of nonce.

In many cases the nonce values are completely predictable.  In fact, IEEE 
802.11 will construct the nonce by concatenating the sender MAC address and 
a packet counter.

>    Data Encapsulation Method as defined in [Shoup01]. Please mention this

I never thought about it this way.  I think about it as a packet with an 
authenticated plaintext header and an authenticated ciphertext 
payload.  What audience would be helped by the "label" reference?

>    also fully describe the encoding function in the draft, for

This is a problem when things are developed in parallel.  Obviously, you 
were not confused.  I do not see the CCM Proof being published as an 
Informational RFC.  A version of the CCM Proof will be in the proceedings 
of SAC.

>      Flags = 8*M + L             (in section 2.3)

I have no objection to adding a formula to describe the same thing. If it 
helps someone understand, then it is useful.  I will make the additions.

I think you have the wrong formula for section 2.3.  It should be: Flags = L.

>    (This is in practice what all AES implementations do.)

Please point me to the text where this is confusing.

>    name for the plaintext message.

Okay.  I will change it to: "The final result c consists of the encrypted 
message followed by the encrypted authentication value U."

>    than having to be inferred from encryption.

Several implementors have found this to be sufficient to build 
interoperable implementations.  In fact, many of them have been made freely 
available.  Doug Whiting has pointers to the ones that we know about from: 
http://www.hifn.com/support/ccm.htm.

I am not saying that it could not be made better, but I do think that it is 
good enough...

>    are unlikely to ever be triggered in practice.

Good point. How about the following: "To preserve security, implementations 
need to limit the total amount of data that is encrypted with a single key; 
the total number of block cipher encryption operations in the CBC-MAC and 
encryption together cannot exceed 2^61.  (This allows nearly 2^64 octets to 
be encrypted and authenticated using CCM.  This is roughly 16 million 
terabytes, which should be more than enough for most applications.)  In an 
environment where this limit might be reached, the sender MUST ensure that 
the total number of block cipher encryption operations in the CBC-MAC and 
encryption together does not exceed 2^61.  Receivers that do not expect to 
decrypt the same message twice MAY also check this limit."

>    and z-1-L octets is large enough for the nonce).

You are correct.  It is also very straightforward to translate the 
specification to another block size when it is needed.  Given the number of 
people that have already chosen to implement CCM, I am reluctant to make 
significant changes for non-security reasons.

>  - the draft should informatively reference the security proof paper.

Agree.  I did not have a reference at the time it was written.

>    independent implementation and check that it matches the test vectors

Already done.  The first two implementations confirmed the test 
vectors.  They are both referenced  on the web page.  Many thanks to John 
Viega and Doug Whiting for their efforts.

Russ

---

From: Jakob Jonsson <[email-masked]>
Date: Sat, 7 Sep 2002 13:48:41 +0200 (CEST)

Hi,

The CCM proof is available at

http://csrc.nist.gov/encryption/modes/proposedmodes/ccm/ccm-ad.pdf

via

http://csrc.nist.gov/encryption/modes/proposedmodes/ .

> >    also be impossible for an attacker to influence the choice of nonce.

Actually no, the security proof does not require this at all. In fact, just as
in the OCB proof, the adversary in my attack model is allowed to choose
whatever nonces she wants as long as the same nonce is not used more than once:

"... the adversary A has access to [a CCM] encryption oracle O that on input
([nonce],[header],[message]) returns a ciphertext C. [The adversary] may send
arbitrary queries to the oracle, except that the same nonce must not be used in
more than one query; such a query is immediately rejected by the oracle. Thus
we restrict our attention to /nonce-respecting/ adversaries." (Section 3.2)

The reason why we may allow the adversary to control the nonce is that the only
plaintext-ciphertext pairs the adversary is given "for free" are the ones
corresponding to the CTR encryption of the message. These pairs are tightly
associated with a specific nonce that must not be used again, which implies
that they leak only negligible information about plaintext-ciphertext pairs
associated with nonces to be used in the future.

Jakob

_____________________________________________________
Gratis e-mail resten av livet på www.yahoo.se/mail
Busenkelt!
_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg