Subject: [Ietf-krb-wg] camellia-cts-cmac as a backup enctype for Kerberos

From: Tom Yu <[email-masked]>
Date: Wed, 27 Jul 2011 19:01:16 -0400

I believe that it is useful to have a "hot spare" or backup encryption
scheme for Kerberos in the event that serious flaws are found in the
primitives of our recommended scheme, aes256-cts-hmac-sha1-96.  I
think that the camellia-cts-cmac proposal provides a suitable
alternative in case a serious flaw is found in either AES or SHA-1.
To be a useful "hot spare", I think it's best to specify it as
Standards Track.  (We can adjust how strongly to recommend it as
conditions evolve.)

The related-key attacks discovered (around 2009) against full-round
AES256 and AES192 already cause some academics to refer to AES as
"broken", at least in a theoretical sense, and recall that "attacks
always get better".  I think it's useful to have an alternative
encryption scheme ready that we can advise people to "walk, do not
run, toward..." when the attacks get better enough to be practical.

The European Community's NESSIE project includes Camellia among its
block cipher recommendations.  The intersection of recommended block
ciphers between NESSIE and ISO/IEC 18033-3:2010 consists of AES and
Camellia (ignoring 64-bit block ciphers, where MISTY1 is in the
intersection).

Given that the NESSIE project was an open evaluation effort involving
an international community of experts, and is more recent than the AES
selection process, I believe that we should give significant weight to
its selections.

NESSIE final portfolio
https://www.cosic.esat.kuleuven.be/nessie/deliverables/decision-final.pdf

ISO/IEC 18033-3:2010
http://www.iso.org/iso/iso_catalogue/catalogue_tc/catalogue_detail.htm?csnumber=54531
_______________________________________________
ietf-krb-wg mailing list
[email-masked]
https://lists.anl.gov/mailman/listinfo/ietf-krb-wg

---

From: Sam Hartman <[email-masked]>
Date: Wed, 27 Jul 2011 20:24:25 -0400

Tom, thanks for that note.

I'd like to solicit comments on

1) Do we want to have a hot spare for AES?

2) How do existing ciphers (RC4, 3DES) play a role in 1?

3) Is Camellia a good fit for that?

Tom, you mentioned related key attacks against AES. Has the same
methodology failed against Camellia?
_______________________________________________
ietf-krb-wg mailing list
[email-masked]
https://lists.anl.gov/mailman/listinfo/ietf-krb-wg

---

From: Nico Williams <[email-masked]>
Date: Wed, 27 Jul 2011 21:35:58 -0500

> 1) Do we want to have a hot spare for AES?

Sure, but I'd rather we searched for a hot spare carefully rather than as an
ex-post justification (ok, not fair,  as I've not followed the I-D closely
enough to know if this is actually the case) for any given new enctype
proposal.  I  expect any such explicit search for a hot spare would be
highly controversial at the IESG, if not the IETF, but to be clear, it's not
my intention to cause controversy; I take no position regarding track for
publication of Camellia at this time.

Also, if we agree that we want a hot spare then I'll insist on publication
of that enctype as required-to-implement.  This too might be controversial,
but that would be the price of taking the we-need-a-hot-spare approach.

> 2) How do existing ciphers (RC4, 3DES) play a role in 1?

We have  them now.  In particular rc4 is widely deployed.  Is rc4  good
enough to last us for the year or so that it might take is deploy a new
enctype in a hurry?

> 3) Is Camellia a good fit for that?

Yes, in that it's a block cipher with a 128-bit block size, so it should be
trivial to implement the new enctype given an implementation of RFC4120 and
of Camellia, but that's as far as I'm prepared to go at the moment (i.e.,
not having looked carefully at Camellia).  That, incidentally, is quite an
advantage for Camellia in the context of Kerberos (compared to, say, Ghost,
whose 64-bit block size makes it less adequate for use in Kerberos).

Nico
-- 
On Jul 27, 2011 8:24 PM, "Sam Hartman" <[email-masked]> wrote:
_______________________________________________
ietf-krb-wg mailing list
[email-masked]
https://lists.anl.gov/mailman/listinfo/ietf-krb-wg

---

From: Tom Yu <[email-masked]>
Date: Wed, 27 Jul 2011 23:33:08 -0400

> publication of Camellia at this time.

Evaluation campaigns for cryptographic algorithms can be expensive.
The only such effort that I know of that is international in scope and
is more recent than the AES competition is NESSIE.  (If someone knows
of a more recent such evaluation effort, please let us know.)  The
IETF might not have the expertise to run such an evaluation effort,
but maybe some participants in CFRG would.  Then again, it would take
a non-trivial amount of time.  What I do believe is that NESSIE is
probably the best guidance we have so far, and it names only AES and
Camellia as recommended 128-bit block ciphers.

> but that would be the price of taking the we-need-a-hot-spare approach.

My opinion is that it shouldn't _yet_ be required-to-implement.  I
believe that it is useful, given long implementation/deployment
pipelines, to have something with a good standards-track specification
(perhaps at a "SHOULD" requirement level) ready for the time when
practical attacks against AES or SHA-1 are discovered.
Forward-looking implementors may wish to implement it before it
becomes required-to-implement.  (Maybe think of it in terms of
"warming up the hot spare" if that isn't stretching the analogy too
far.)

> enough to last us for the year or so that it might take is deploy a new

The RC4 enctype is a stream cipher and uses legacy hash algorithms.
DES3 has a 64-bit block size and is therefor less desirable for
reasons I summarize below.

> whose 64-bit block size makes it less adequate for use in Kerberos).

The MIT krb5 implementation already includes an implementation of
camellia-cts-cmac as an option (though not compiled by default because
you need to explicitly choose private-use enctype numbers at build
time).

I prefer to exclude 64-bit block ciphers such as DES3, MISTY1, GOST,
etc. from consideration in new Kerberos cipher suites because of
cipher block collision considerations -- 2**32 blocks of ciphertext
for ~50% probability of collision in CBC mode is only 2**35 bytes ==
32GB == less than _five minutes_ at 1 gigabit/sec line speed, for
example.
_______________________________________________
ietf-krb-wg mailing list
[email-masked]
https://lists.anl.gov/mailman/listinfo/ietf-krb-wg

---

From: Tom Yu <[email-masked]>
Date: Wed, 27 Jul 2011 23:40:11 -0400

> methodology failed against Camellia?

To the best of my knowledge, there are no known related-key attacks
against full-round Camellia, but I would ask actual cryptographers for
opinions on that topic.  A quick search only turns up an attack on a
variant known as "byte-Camellia" (http://eprint.iacr.org/2010/248.pdf).
_______________________________________________
ietf-krb-wg mailing list
[email-masked]
https://lists.anl.gov/mailman/listinfo/ietf-krb-wg

---

From: Sam Hartman <[email-masked]>
Date: Thu, 28 Jul 2011 07:02:53 -0400

>>>>> "Nico" == Nico Williams <[email-masked]> writes:

    >> 1) Do we want to have a hot spare for AES?

    Nico> Sure, but I'd rather we searched for a hot spare carefully
    Nico> rather than as an ex-post justification (ok, not fair, as I've
    Nico> not followed the I-D closely enough to know if this is
    Nico> actually the case) for any given new enctype proposal.  I
    Nico> expect any such explicit search for a hot spare would be
    Nico> highly controversial at the IESG, if not the IETF, but to be

Speaking as an individual.
My reading of the discussions is that finding something that the
security area could get behind as a whole or even a security area
consensus that a hot spare is needed would in fact be highly
controversial.

However, in the absence of a wider consensus, I think the IESG will back
us if we have a rough consensus for our area.  If by the time krb-wg
gets to a consensus that we want x to be our hot spare, the security
area doesn't have any consensus in the area, then we could move forward.
We'd probably have to be prepared to have good documentation of that
consensus.  However I think we'd get little pushback that we got to form
that consensus in the absence of something wider.

So, this only has to be as controversial as it needs to be within this
working group.
_______________________________________________
ietf-krb-wg mailing list
[email-masked]
https://lists.anl.gov/mailman/listinfo/ietf-krb-wg

---

From: Sam Hartman <[email-masked]>
Date: Thu, 28 Jul 2011 07:04:52 -0400

>>>>> "Tom" == Tom Yu <[email-masked]> writes:

    Tom> My opinion is that it shouldn't _yet_ be required-to-implement.
    Tom> I believe that it is useful, given long
    Tom> implementation/deployment pipelines, to have something with a
    Tom> good standards-track specification (perhaps at a "SHOULD"
    Tom> requirement level) ready for the time when practical attacks
    Tom> against AES or SHA-1 are discovered.  Forward-looking
    Tom> implementors may wish to implement it before it becomes
    Tom> required-to-implement.  (Maybe think of it in terms of "warming
    Tom> up the hot spare" if that isn't stretching the analogy too
    Tom> far.)

How would people feel about SHOULD+?
_______________________________________________
ietf-krb-wg mailing list
[email-masked]
https://lists.anl.gov/mailman/listinfo/ietf-krb-wg

---

From: Sam Hartman <[email-masked]>
Date: Thu, 28 Jul 2011 07:06:34 -0400

>> methodology failed against Camellia?

    Tom> To the best of my knowledge, there are no known related-key
    Tom> attacks against full-round Camellia, but I would ask actual
    Tom> cryptographers for opinions on that topic.  A quick search only
    Tom> turns up an attack on a variant known as "byte-Camellia"
    Tom> (http://eprint.iacr.org/2010/248.pdf).

As an individual, I'd like to do an explicit search and confirm people
tried to mount the AES attack against Camellia before I personally would
feel comfortable with Camellia on standards track. Clearly a hot spare
would need to be standards track.
_______________________________________________
ietf-krb-wg mailing list
[email-masked]
https://lists.anl.gov/mailman/listinfo/ietf-krb-wg

---

From: Satoru Kanno <[email-masked]>
Date: Thu, 28 Jul 2011 22:24:04 +0900

(2011/07/28 20:06), Sam Hartman wrote:
>>>>>> "Tom" == Tom Yu<[email-masked]>  writes:
>
>      Tom>  Sam Hartman<[email-masked]>  writes:

Generally speaking, cryptographers believe success factor for the 
related-key attack is the complexity on key schedule. AES's key schedule 
is very simple. But Camellia's key schedule is complex.

As a result, I think that Camellia is secure than AES for the 
related-key attack.

Thanks,
Satoru

-- 
Satoru Kanno

Security Business Unit
Mobile and Security Solution Business Group
NTT Software Corporation

e-mail: [email-masked]

---

From: Martin Rex <[email-masked]>
Date: Fri, 29 Jul 2011 05:02:24 +0200 (MEST)

> consensus that a hot spare is needed would in fact be highly

Are you _sure_ that it would be controversial?

Looking at the TLS ciphersuites, TLS seems to have chosen Camellia
as the most likely hot standy algorithm to AES before krb.

Have there been so many international contests/selections that
have their very own algorithm so that we have a problem choosing
among the huge masses.  I had the impression, due to the
long duration and efforts doing performing open international
selection contest for algorithms, the number of candidates was
rather small.

And I would really appreciate if more of the individual states
that are favouring their own algorithms would be ask to participate
in international contests rather than flooding the IETF with
TLS ciphersuites and kerberos enctype documents with algorithms
that might still be crypto-alg teens.   :-/

-Martin

---

From: Sam Hartman <[email-masked]>
Date: Fri, 29 Jul 2011 09:33:29 -0400

>>>>> "Martin" == Martin Rex <[email-masked]> writes:

    >> consensus that a hot spare is needed would in fact be highly

    Martin> Are you _sure_ that it would be controversial?

Yes.  There are several people in the security community who do not
believe we need a hot spare at all or who believe 3DES is sufficient.
_______________________________________________
ietf-krb-wg mailing list
[email-masked]
https://lists.anl.gov/mailman/listinfo/ietf-krb-wg

---

From: Leif Johansson <[email-masked]>
Date: Fri, 29 Jul 2011 16:17:18 +0200

> believe we need a hot spare at all or who believe 3DES is sufficient.

I'll re-iterate what I said in the room yesterday: from an operational
point of view 3DES can't be a hot-spare for _Kerberos_ since it isn't
implemented across the vendors.

	Cheers Leif

---

From: Martin Rex <[email-masked]>
Date: Fri, 29 Jul 2011 18:55:19 +0200 (MEST)

Leif Johansson wrote:
> > Martin Rex writes:

I agree with Leif.  The likelyhood of an algorithm getting
adopted by a meaningful fraction of the installed base in a
reasonable timeframe is what really matters.

Whether or not the KRB wants to have another enctype besides AES as
Recommended so that it might serve as a hot spare in case something
really bad happens to AES security is a pure matter of personal taste
and can be decided with significant majority.

The much more difficult to answer question is, which algorithm
should that be and why?

The former mandatory to implement enctype in kerberos was based
on single-DES, and I assume we all agree that the useful lifetime
of this algorithm has long ended.

There still is HMAC-RC4 out there, and if we discount single-DES,
it seems the enctype with the highest adoption.  But it looks much
more like an emergency fallback (i.e. significantly less confidence
than there currently is in AES), rather than a hot spare (with
a confidence closer to that of AES).

For a non-marginal fraction of vendors and consumers, the label
"NIST-approved" seems to be signficant.  A 3DES-enctype would
probably get NIST-approval easily, but what does NIST think about
Camellia?

And which algorithm has a higher likelyhood of getting adopted
by the implementors/vendors:  one based on 3DES or one based on
Camellia?  A very significant fraction of the installed base
seems to come from a single vendor, and when not getting that
vendor to implement a new "hot spare" candidate enctype, the
practical usefulness of the "hot spare" remains questionable.

-Martin