Subject: Re: [kitten] Comments on draft-ietf-kitten-aes-cts-hmac-sha2-00

From: Kelley Burgin <[email-masked]>
Date: Thu, 16 May 2013 11:15:53 -0400

Thanks for your comments, my responses inline below. Basically, I'm  
happy to make the requested changes and have some proposed solutions  
for when the plaintext length is less than the blocksize.

Kelley

> I think this is in fairly good shape. My comments seem to mostly fall
> into two categories:
>
> 1) As chair I'm requesting that this document make no reference to
> terminology or concepts introduced in the simplified profile in RFC
> 3961.
> For the most part I'd expect this spec to refer only to RFC 3961
> sections 3 and 4.
>
[kwb] No problem.

> 2) I recommend that the editors minimize references to RFC 3962; in
> general repeating text from RFC 3962 is probably better than  
> references.
> This is a recommendation, not a requirement for progression; if the
> editors consider the issue and believe that some references to RFC  
> 3962
> improve clarity or minimize the probability of specification or
> implementation error, I'll be happy with that.
>
[kwb] No problem.
>
> The salt input to string_to_key is not under the control of a
> specification of an RFC 3961 enctype.
> It's inappropriate to place restrictions on the salt in this
> specification.
> Operationally what you may want is to encourage KDCs to include 128- 
> bits
> of randomness in the salt they use.
> That doesn't belong as part of the encryption type specification; it  
> may
> be appropriate in the same document, clearly separated.
>
> However, I think there are some issues related to keying services that
> tend to come up if the salt contains random data. I know the MIT folks
> explored this; I don't remember all the conclusions.
>
> If this property is important, you'll almost certainly want to explore
> advantages attackers could gain by causing a client to use the default
> Kerberos salt--that is, just the principal and realm.  If we don't end
> up liking the implications of that analysis we'll need to look at
> changes broader in scope than are appropriate for an enctype
> specification.
>
[kwb] Are you ok with "SHOULD include 128-bits of random"?

>
> Section 5:
>
>
> You seem to be using the function dr(), defined as part of the
> simplified profile in RFC 3961, but your definition is different than
> that in RFC 3961.  I find this notation confusing and would recommend
> against adopting notation from the simplified profile.
>
> Similarly, calling the key usage input to the key derivation n is
> notation from the simplified profile, not from section 3 of RFC 3961  
> and
> is highly confusing.
>
[kwb] I'll change this.
>
> section 6:
>
> The use of notation from the simplified profile is really problematic
> here.
>
> I think using cE, D and m is fine. I just think it would be  
> desirable to
> define them yourself rather than referencing the simplified profile
> definitions.
>
> I think I'd like to hear responses to these comments before deciding
> whether we're ready for working group last call.
>
>
> ------------------------------
>
> Date: Tue, 14 May 2013 19:00:26 -0400
> From: Greg Hudson <[email-masked]>
> To: Sam Hartman <[email-masked]>
> Cc: [email-masked]
> Subject: Re: [kitten] Comments on
> 	draft-ietf-kitten-aes-cts-hmac-sha2-00
> Message-ID: <[email-masked]>
> Content-Type: text/plain; charset=ISO-8859-1
>
> I have an additional comment:
>
> Section 6 notes that "[SP800-38A+] requires the plaintext length to be
> greater than or equal to the block size" but gives no guidance on what
> to do if the input is smaller than that.  This seems like a pretty
> serious problem.

[kwb] CTS won't work, so two work arounds are:
1. Pad the plaintext to a block length, but this brings back issues  
with the ciphertext length being greater than plaintext length.
2. Use a different mode, counter mode for example (only in this  
special case). Encrypt the IV and xor the result with the plaintext  
(padded with zeros). Output the appropriate partial ciphertext so  
there's no expansion.

---

From: Sam Hartman <[email-masked]>
Date: Thu, 16 May 2013 11:26:54 -0400

>>>>> "Kelley" == Kelley Burgin <[email-masked]> writes:
    Kelley> [kwb] Are you ok with "SHOULD include 128-bits of random"?

Not really.  That feels like ignoring an important issue.  The point you
bring up about salt seems significant and I think deserves more than a
sentence, especially a SHOULD without qualifications.

I'd like to first understand from Greg or Ken or whoever looked at
random salts at MIT what the complexities are.
Then  I'd like to better understand how you want this requirement
enforced and what attacks you are worried about.

At that point I think we can propose some text for a new section.

--------------------

I'd like to ask the WG whether we think the less-than-a-block issue is a
practical problem or whether it's just a completeness issue.

If we don't expect either GSS-API or Kerberos messages to generate
inputs less than a block, then I think having "trailing crypto garbage,"
(ciphertext length greater than plaintext length) in that one case might
be fine.

Thoughts?

---

From: Greg Hudson <[email-masked]>
Date: Thu, 16 May 2013 12:36:35 -0400

> sentence, especially a SHOULD without qualifications.

I agree with Sam here.  An RFC 3961 enctype defines a (random) function,
not a set of constraints on the inputs.  This seems like fodder for the
suiteb draft or something else.

> random salts at MIT what the complexities are.

Here's what I ran into when trying to make random salts the default in
MIT krb5:

* Password history checking stops working as we currently implement it
in MIT krb5, and the obvious alternative makes changing passwords more
computationally expensive for kadmind.

* ktutil's add_entry command assumes the default salt.  A similar
problem applies when keying Windows services, if I understand how that
normally works.

* Cross-realm TGTs are currently managed by entering the same password
at two KDCs to get the same keys.  If each KDC uses a random salt, they
won't have the same keys.

All of these can be mitigated, but it adds up to a substantial project.
 We added support for random salts in 1.10, but not by default (and it
only uses a non-configurable 64 random bits at the moment, but that's a
simple change).

> practical problem or whether it's just a completeness issue.

It would be a serious practical problem if an enctype implementation was
expected to just fail on inputs less than 16 bytes.  I don't know if it
would be a practical problem to have ciphertext expansion for a small
input.  I suspect it wouldn't be a problem for MIT krb5 since we're used
to it with DES and DES3 (although not with CFX in GSSAPI).

I tried running our test suite with a 16-byte plaintext minimum to
identify small messages, but it only got as far as encrypting key data
during KDB setup.  That's not a PDU so it's not terribly interesting.

I'm interested in Kelley's idea of using CTR with the random IV as the
counter.  Obviously an IV collision would expose the XOR of the
plaintexts of the colliding blocks, but I think that's no worse than CBC
(a colliding cipher block exposes the XOR of the plaintexts of the
preceding blocks, IIRC).

---

From: Kelley Burgin <[email-masked]>
Date: Fri, 17 May 2013 09:47:44 -0400

Even though I see value in adding random to the salt, I don't think it  
warrants taking on a substantial project. Any objections to taking out  
the requirement for random in the salt, and adding some text to the  
effect of "If NIST guidance to include 128 bits of random in the salt  
is followed, be aware of these issues..." Also make a note that the  
random would need to be passed to the client in some appropriate  
padata field?

Kelley

---

From: Greg Hudson <[email-masked]>
Date: Fri, 17 May 2013 10:00:32 -0400

On 05/17/2013 09:47 AM, Kelley Burgin wrote:
> effect of "If NIST guidance to include 128 bits of random in the salt is
> followed, be aware of these issues..." Also make a note that the random
> would need to be passed to the client in some appropriate padata field?

I'm opposed to having any text in an encryption type specification about
the contents of the salt.  An enctype implementation accepts the salt as
input from a higher layer; it does not choose what goes into the salt.

An RFC can contain multiple things (an enctype spec and also some text
about salts), but they should be clearly delineated, and I'm not sure
what this RFC would need to say about salts which isn't already stated
in RFC 4120.

---

From: Sam Hartman <[email-masked]>
Date: Fri, 17 May 2013 10:10:48 -0400

>>>>> "Kelley" == Kelley Burgin <[email-masked]> writes:

    Kelley> Even though I see value in adding random to the salt, I
    Kelley> don't think it warrants taking on a substantial project. Any
    Kelley> objections to taking out the requirement for random in the
    Kelley> salt, and adding some text to the effect of "If NIST
    Kelley> guidance to include 128 bits of random in the salt is
    Kelley> followed, be aware of these issues..." Also make a note that
    Kelley> the random would need to be passed to the client in some
    Kelley> appropriate padata field?

it sounds like you and Greg might both be happy with a new section in
this document discussing random salts, and pointing out the issues.
Greg asks what there is to say beyond RFC 4120?
I think the big thing would be to give advice on how to figure out the
salt of a service or cross-realm key.

If we can find guidance for how implementations should approach that
would it be valuable to document that guidance here?

---

From: Kelley Burgin <[email-masked]>
Date: Fri, 17 May 2013 10:25:49 -0400

We do have text about prepending the enctype name to the salt, which I  
think is important (although I guess this is technically saltp but  
still used as the "salt" in PBKDF). Are you opposed to random in the  
salt in the test vectors?

---

From: Sam Hartman <[email-masked]>
Date: Fri, 17 May 2013 10:27:21 -0400

>>>>> "Kelley" == Kelley Burgin <[email-masked]> writes:

    Kelley> We do have text about prepending the enctype name to the
    Kelley> salt, which I think is important (although I guess this is
    Kelley> technically saltp but still used as the "salt" in
    Kelley> PBKDF). 

I think that the way prepending the enctype name to the salt is done is
fine.
it's entirely internal to the crypto system.

    Kelley> Are you opposed to random in the salt in the test
    Kelley> vectors?

As an individual I think that's fine.

---

From: Greg Hudson <[email-masked]>
Date: Fri, 17 May 2013 10:29:12 -0400

On 05/17/2013 10:25 AM, Kelley Burgin wrote:
> think is important (although I guess this is technically saltp but still
> used as the "salt" in PBKDF).

The distinction is important.  The salt value arrives as an input from
the RFC 4120 layer.  What the enctype feeds into PBKDF2 is an internal
detail of the enctype.  (But an enctype cannot add random data to the
input salt and feed that to PBKDF2, because string-to-key is not a
random function.)

> Are you opposed to random in the salt in the test vectors?

Not at all.  Programs which verify test vectors can feed in whatever
salt is required.  However, do note that RFC 3961 restricts salts to
valid UTF-8 sequences.

---

From: Kelley Burgin <[email-masked]>
Date: Fri, 17 May 2013 12:39:39 -0400

To be clear, in response to Sam's earlier question, are you against a  
section discussing random salts which discusses cross realm issues?

Thanks for reminding me about the UTF-8 restriction.

On May 17, 2013, at 10:29 AM, Greg Hudson wrote:

>> still

---

From: Greg Hudson <[email-masked]>
Date: Fri, 17 May 2013 12:52:01 -0400

> section discussing random salts which discusses cross realm issues?

I am not raising an objection to such a section if it is clearly
separate from the enctype specification.  (But I also don't see the need
for it, and if there is a need, I wonder if it would fit better in the
suiteb draft.)

---

From: Kelley Burgin <[email-masked]>
Date: Fri, 17 May 2013 13:27:54 -0400

I agree it might fit better in a different document, but Suite B does  
not use password based authentication (we require pkinit). The text we  
have on passwords is to be a complete enctype, that provides a high  
level of security independent of network security policy (e.g.  
password strength requirements).

I'm happy to include a section in this draft on random salts, if there  
is a need as you say, and if we can come up with a solution to cross  
realm problems (I don't have one).

---

From: Nico Williams <[email-masked]>
Date: Mon, 20 May 2013 15:41:04 -0500

> enforced and what attacks you are worried about.

In theory randomized salts should have little impact.  In practice
there are least some moderate impacts (e.g., ktutil-type applications
should not assume a salt when generating a keytab entry from a
password).

I understand the value of randomizing salts, but having *any* salt
gets us the most important feature: defeating rainbow table
precomputation (by requiring per-principal rainbow tables).

Nico
--

---

From: Tom Yu <[email-masked]>
Date: Mon, 20 May 2013 18:37:01 -0400

> (padded with zeros). Output the appropriate partial ciphertext so

I think CTS will work if you are willing to modify the "IV" sent when
the plaintext length is less than or equal to the block size;
basically treat the IV as the next to last block of CBC ciphertext,
truncating it to the length of the plaintext, and send the final block
of CBC ciphertext as the "IV".

I'm not sure how to adapt this approach to the current document,
because the current approach doesn't send the IV, but rather sends the
nonce from which the IV is derived.

---

From: Nico Williams <[email-masked]>
Date: Mon, 20 May 2013 18:13:38 -0500

> nonce from which the IV is derived.

I don't see the problem.  In the short-plaintext case we'd have:

   C = E(Ke, N | plaintext, cipherstate)
   H = HMAC(Ki, C)
   ciphertext = C

and corresponding change to the decrypt side:

   (C, H) = ciphertext
   if (H != HMAC(Ki, C)[1..h])
      stop, report error
   IV = cipherstate
   (N, P) = D(Ke, C, IV)
   cipherState = N

I remembered a reason not to confound whenever possible: performance
-- fewer encryption/decryption operations.

Nico
--

---

From: "Henry B. Hotz" <[email-masked]>
Date: Mon, 20 May 2013 16:46:13 -0700

Obviously off-topic, but I've advocated for a "keytab import" administrative function as a way to avoid retyping passwords in this case.  Yeah, yeah, "write it yourself, it's open-source", I know.

> won't have the same keys.

------------------------------------------------------
The opinions expressed in this message are mine,
not those of Caltech, JPL, NASA, or the US Government.
[email-masked], or [email-masked]

---

From: Tom Yu <[email-masked]>
Date: Mon, 20 May 2013 20:21:40 -0400

>    C = E(Ke, N | plaintext, cipherstate)

That's not quite right, unless you're redefining E.  If E is
SP800-38A+ "CBC-CS3", it doesn't really work unless len(plaintext) is
greater than the blocksize.  We can still send a truncated nonce
instead of a truncated IV, because we can recover the entire IV on
decryption.

plen = len(plaintext)
if plen < blocksize:
  C = Enc-CBC(Ke, plaintext | nullpad, IV)
  N1 = C[1..blocksize]
  C1 = N[1..plen]
  H = HMAC(Ki, N1 | C1)
  ciphertext = N1 | C1 | H[1..h]

---

From: Nico Williams <[email-masked]>
Date: Mon, 20 May 2013 19:56:23 -0500

> instead of a truncated IV, because we can recover the entire IV on

Here E() operates on a plaintext 16-31 bytes long: E | P.  There's no problem.

---

From: Tom Yu <[email-masked]>
Date: Mon, 20 May 2013 23:58:41 -0400

> Here E() operates on a plaintext 16-31 bytes long: E | P.  There's no problem.

I think you mean the plaintext is N | plaintext.  It sounds like
you're making the short-plaintext encryption change to using a
confounder, which the current document seems to deliberately avoid.

---

From: Nico Williams <[email-masked]>
Date: Mon, 20 May 2013 23:45:43 -0500

> I think you mean the plaintext is N | plaintext.  It sounds like

That's what I wrote, yes :)

> confounder, which the current document seems to deliberately avoid.

I don't know why the current document avoids confounding, not even
whether it does so deliberately or by accident -- the topic is not
addressed.  Section 1 addresses differences from aes-cts-hmac-sha-1,
but does not cover this one; it should.

Nico
--

---

From: Kelley Burgin <[email-masked]>
Date: Tue, 21 May 2013 12:18:55 -0400

Both Tom's and Nico's short-plaintext schemes miss something I'm  
looking for: the presence of the IV in the MAC computation. Otherwise  
the MAC value H is always the same for a given C (output of the  
encryption operation).

In general, we want to encrypt-then-mac, include the IV directly in  
the MAC computation and on the receiving end check the MAC before  
decryption (to save decrypting a long message only to find out later  
that the MAC doesn't verify). I'm probably fine with a scheme that  
doesn't do the last two in short-plaintext cases (like Tom's and  
Nico's). However, to achieve all three, the nonce needs to be sent as  
part of the ciphertext.

Here are my comments on the two proposed short-plaintext schemes:

In Tom's scheme for short-plaintext cases, it seems that duplicate  
information is being sent, if I understand correctly: isn't C1 a  
subset of the bits of N1? If so, it would be useful to include part of  
the IV in the MAC computation instead of C1 to diversify the MAC  
values for a given C.

Tom's:
[
plen = len(plaintext)
if plen < blocksize:
]

could change to (note the receiver has to decrypt first to recover the  
IV, then verify the MAC)

[
plen = len(plaintext)
if plen < blocksize:
  C = Enc-CBC(Ke, plaintext | nullpad, IV)
  IV* = IV[1..plen]     <-- don't truncate N1, use IV instead
H = HMAC(Ki, C | IV*)
ciphertext = C | IV* | H[1..h]
]

Nico's could also be modified to include the IV in the MAC  
computation, without expanding the ciphertext:

Nico's:
[
   ciphertext = C, H

   (C, H) = ciphertext
]

could change to

[
   C = E(Ke, N | plaintext, cipherstate)
   H = HMAC(Ki, N | C)   <-- added nonce here
   ciphertext = C, H

decrypt

   (C, H) = ciphertext
   IV = cipherstate   <-- decrypt first to recover the nonce, then  
check MAC
   (N, P) = D(Ke, C, IV)
   if (H != HMAC(Ki, N | C)[1..h])
      stop, report error
   cipherState = N
]

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Tue, 21 May 2013 12:48:48 -0400

> but does not cover this one; it should.

This is actually a problem.  Enctype design should be conservative; if
we're not going to have a confounder, I want to know why.

-- Jeff

---

From: Kelley Burgin <[email-masked]>
Date: Tue, 21 May 2013 13:05:51 -0400

Sorry - the reason was buried in the previous email:

In general, we want to
1. encrypt-then-mac,
2. include the IV directly in the MAC computation (so the MAC value H  
is different for the same output of the encryption operation C) and
3. on the receiving end check the MAC before decryption (to save  
decrypting a long message only to find out later that the MAC doesn't  
verify).

I'm probably fine with a scheme that doesn't do the last two in short- 
plaintext cases (like Tom's and Nico's). However, to achieve all  
three, the nonce needs to be sent as part of the ciphertext.

Also, we have coordinated, to the extent possible (the intended  
applications there don't have a problem with PKCS#5 padding), with  
draft-mcgrew-aead-aes-cbc-hmac-sha2

Kelley

On May 21, 2013, at 12:48 PM, Jeffrey Hutzelman wrote:

> _______________________________________________
> Kitten mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/kitten

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Tue, 21 May 2013 13:13:33 -0400

> decrypting a long message only to find out later that the MAC doesn't  

OK; none of that explains why you do not prepend a random confounder to
the data to be encrypted.  I think you need to explain both why there is
no confounder and why it is not necessary.

-- Jeff

---

From: Nico Williams <[email-masked]>
Date: Tue, 21 May 2013 12:21:54 -0500

On Tue, May 21, 2013 at 11:18 AM, Kelley Burgin <[email-masked]> wrote:
> Both Tom's and Nico's short-plaintext schemes miss something I'm looking
> for: the presence of the IV in the MAC computation. Otherwise the MAC value
> H is always the same for a given C (output of the encryption operation).

When confounding the ciphertext of the confounder is included in MAC
computation.  Why is this not sufficient?

---

From: Sam Hartman <[email-masked]>
Date: Tue, 21 May 2013 14:18:02 -0400

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

    Nico> On Tue, May 21, 2013 at 11:18 AM, Kelley Burgin <[email-masked]> wrote:
    >> looking for: the presence of the IV in the MAC
    >> computation. Otherwise the MAC value H is always the same for a
    >> given C (output of the encryption operation).

    Nico> When confounding the ciphertext of the confounder is included
    Nico> in MAC computation.  Why is this not sufficient?

The rest of the world (non-Kerberos) seems to use explicit IVs that are
sent in the clear just fine.  The only area I'd be concerned about is to
make sure an attacker does not gain an advantage if they know the
cipherstate between two messages.

it seems like using an explicit IV instead of a confounder is fairly
conservative cryptographic practice at this point.

---

From: Nico Williams <[email-masked]>
Date: Tue, 21 May 2013 13:45:44 -0500

> cipherstate between two messages.

That's not responsive.

> conservative cryptographic practice at this point.

But so is confounding.  Or, if confounding is not secure, maybe we
should find out.

Nico
--

---

From: Nico Williams <[email-masked]>
Date: Tue, 21 May 2013 13:51:30 -0500

> 1. encrypt-then-mac,

Agreed.

> 2. include the IV directly in the MAC computation (so the MAC value H is
> different for the same output of the encryption operation C) and

Note that this is true with confounding anyways: every ciphertext of
the same plaintext (as provided by the application) is randomized
because the plaintext prepended with a nonce.

If there's something wrong with confounded encrypt-then-MAC (and
verify-then-decrypt) we should know, since we rely on confounding in
Kerberos today.

> 3. on the receiving end check the MAC before decryption (to save decrypting
> a long message only to find out later that the MAC doesn't verify).

And to avoid padding attacks.  (It helps to have no padding, of course.)

>
> I'm probably fine with a scheme that doesn't do the last two in
> short-plaintext cases (like Tom's and Nico's). However, to achieve all

No, my scheme gets you all three.  Confounding does not preclude any
of (1), (2), nor (3).

Nico
--

---

From: Sam Hartman <[email-masked]>
Date: Tue, 21 May 2013 14:56:45 -0400

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

    Nico> Note that this is true with confounding anyways: every
    Nico> ciphertext of the same plaintext (as provided by the
    Nico> application) is randomized because the plaintext prepended
    Nico> with a nonce.

Note that having a nonce including in the IV also gets you this.  It's
quite important that two encryptions of the same plaintext result in
different ciphertexts.

---

From: Tom Yu <[email-masked]>
Date: Tue, 21 May 2013 15:52:56 -0400

> the MAC value H is always the same for a given C (output of the

I think both my proposal and Nico's use the nonce rather than the IV,
but they should have the same amount of entropy.  That should be
sufficient to prevent multiple encryptions of the same plaintext from
producing identical ciphertext.

> the IV in the MAC computation instead of C1 to diversify the MAC

I think I chose variable names poorly; they are not redundant.  C1 is
the the first plen bytes of the nonce N.  N1 is the single-block
output of Enc-CBC(Ke, plaintext | nullpad, IV) and does not contain
any plaintext bits of the nonce.

If the nonce N is random, it provides just as much randomization of
the ciphertext as the IV would (assuming they're independent of the
cipherstate).

> ciphertext = C | IV* | H[1..h]

That's not too different from the following:

plen = len(plaintext)
if plen < blocksize:
  C = Enc-CBC(Ke, plaintext | nullpad, IV)
  N* = N[1..plen]
  H = HMAC(Ki, C | N*)
  ciphertext = C | N* | H[1..h]

It's mostly a question of whether you send the truncated IV directly
or whether you send the truncated nonce instead.

>   C = E(Ke, N | plaintext, cipherstate)

Nico's version includes the nonce N, which the current document
specifies to be random.

---

From: Nico Williams <[email-masked]>
Date: Tue, 21 May 2013 15:05:17 -0500

> quite important that two encryptions of the same plaintext result in

There's no disagreement as to that.  I'm happy to not confound.  But
while you can tell me that not confounding is fine till your face
turns blue, that doesn't address the short plaintext issue.  Nor does
it address the need for some text explaining the departure from
Kerberos tradition -- I don't think strong justification is needed,
mind you, as I'm sold on it (at least for plaintexts 16 bytes or
longer).

Nico
--

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Tue, 21 May 2013 16:39:58 -0400

> conservative cryptographic practice at this point.

You seem to be replying to Nico with an attempt to answer my question,
or at least part of it.  When I said we should be conservative, I meant
that departures from existing designs should not be arbitrary or
gratuitous.  There needs to be a reason for the change, and there needs
to be some confidence that the change does not introduce a new problem.

I think we can agree that introducing an explicit IV does not create a
worse situation than the fixed IV used in existing enctypes.  And I
could come up with some reasons for doing so, but I'd rather hear the
actual reasons.

On the other hand, I am very nervous about omitting the random secret
confounder used by existing enctypes.  So far, I have seen neither an
indication of why this is necessary or why introducing a public IV makes
a secret confounder unnecessary.

-- Jeff

---

From: Tom Yu <[email-masked]>
Date: Tue, 21 May 2013 16:45:26 -0400

> But so is confounding.  Or, if confounding is not secure, maybe we

I think CBC with explicit random IV is better analyzed in the
literature.  Encrypt-then-MAC is provably IND-CCA and INT-CTXT secure
given some reasonable assumptions about the MAC and the encryption
scheme.  (Bellare and Namprempre, "Authenticated Encryption: Relations
among notions and analysis of the generic composition paradigm",
2000.)

The "simplified profile" in RFC 3961 (prepend confounder, then
independently MAC and CBC-encrypt with zero IV) is provably IND-CCA
and INT-CTXT secure.  See Boldyreva and Kumar, "Provable-Security
Analysis of Authenticated Encryption in Kerberos", 2007.  Among other
things, it aruges that CBC encryption with zero IV and random
confounder is at least as secure as CBC encryption with random IV.

---

From: Tom Yu <[email-masked]>
Date: Tue, 21 May 2013 18:13:21 -0400

> a secret confounder unnecessary.

See the references I posted.  If a random confounder provides
additional security properties that a public IV does not, it would be
useful to know what they are.  It may be there's a nontrivial benefit
to having a random secret confounder, but I haven't found one yet.

---

From: Kelley Burgin <[email-masked]>
Date: Wed, 22 May 2013 11:39:38 -0400

Nico,

I had forgotten about the first block of cipher being the encryption  
of the IV - you're right that your scheme achieves all 3 security  
goals below. I haven't thought more about Tom's yet, but agree that we  
need to address the short-plaintext issue in the document and I'm  
happy to include whichever scheme we agree on.

The non-security related reasons (in response to you and Jeff) for the  
decisions made in my draft, which deviate from Kerberos tradition are:

The draft is intended to support the Suite B profile for Kerberos  
draft. Suite B is more than a set of algorithm choices - it provides  
NIST compliant security guidance and further systems requirements to  
achieve as secure a complete system as possible. There is no required  
"Suite B mode of encryption", but there is a rule that we follow: Use  
GCM when it makes sense, otherwise CBC (as specified in NIST  
SP800-38A, which specifies the use of padding and an explicit nonce).  
The krb-wg discussed using GCM years ago to conclude that it didn't  
make sense (counter rollover vulnerability issues), so we moved to CBC 
+padding+explicit IV. We eventually gave in to CTS mode around the  
same time the Addendum to SP800-38A came out standardizing CTS mode.

Moving to implicit IV would deviate from NIST standards (SP800-38A  
Section 6.2 specifies the IV be xored with the first block of  
plaintext and encrypted to output the first block of ciphertext). It  
would also break the Suite B mode rule. The other protocols (that  
we've written Suite B profiles for) where GCM doesn't make sense use  
CBC mode with explicit IV: IKEv2 (in IPSec RFC) and S/MIME.

There's also the performance issue that you pointed out that implicit  
IVs require an extra encryption and decryption operation per message,  
but send the same number of bytes on the wire as explicit IV, but this  
is less important to me than the Suite B/NIST philosophical issues  
above.

Kelley

On May 21, 2013, at 2:51 PM, Nico Williams wrote:

> On Tue, May 21, 2013 at 12:05 PM, Kelley Burgin <[email-masked] 
> > wrote:
>> In general, we want to
>> 1. encrypt-then-mac,
>
> Agreed.
>
>> decrypting

---

From: Nico Williams <[email-masked]>
Date: Wed, 22 May 2013 10:38:38 -0500

> confounder is at least as secure as CBC encryption with random IV.

It should be obvious that confounding CBC (or CTS, which is a
variation on CBC) is at least as secure as CBC (or CTS) with random
IV.  It follows from the fact that encryption with CBC and a
confounder is the same as encrypting a random nonce (same size as an
IV) to get an IV for use in encrypting the original plaintext --
encrypting the nonce can't degrade security.

It is less obvious that confounding doesn't add security (and I think
it doesn't).  But then, CBC with a random IV meets our security needs
and there's plenty of analysis to back this up.

The main benefit to not confounding is performance: there's one fewer
encryption/decryption operation per-RFC3962 encryption/decryption
operation.  For small messages this is a big deal.

Some text for the intro section would be nice.  And a solution to the
short plaintext problem is critical (if nothing else because GSS
consumers are free to use shorter plaintexts and we don't know if they
do or don't; ditto AFS and other non-Internet protocols).  I'm happy
with either a counter or confounded short plaintext encryption
solution, and I'd prefer the counter one on account of performance
(again).

Nico
-- 

Nico
--

---

From: Nico Williams <[email-masked]>
Date: Wed, 22 May 2013 10:51:45 -0500

On Wed, May 22, 2013 at 10:39 AM, Kelley Burgin <[email-masked]> wrote:

Thanks.  This is what I was looking for.

I don't think confounding clashes philosophically with the NIST Suite
B requirements.  It clearly functions as CBC w/ random IV...  it uses
encryption to derive the IV from a nonce, but so what?  The
philosophical difference between CBC w/ random IV and CBC with
confounding seems about as strong as that between CBC and CTS.

That said: I'm happy to not confound, and I would found my personal
choice to dump confounding on the performance gain to be had from not
confounding.

As for short-plaintext, I think I prefer Tom's counter mode solution
(again, for performance reasons).

Nico
--

---

From: Tom Yu <[email-masked]>
Date: Wed, 22 May 2013 14:03:39 -0400

> and there's plenty of analysis to back this up.

I think I generally agree with the above.  I'm not aware of any
significant specific benefit that a secret confounder provides beyond
what a public random IV does.  Anyone know of relevant results in the
research literature?

> operation.  For small messages this is a big deal.

CTS encryption and decryption aren't symmetric in cost.  CTS
encryption of a message can use an underlying CBC encryption primitive
and only need to invoke it once.  CTS decryption, on the other hand,
will need to invoke the underlying CBC decryption primitive twice in
the general case.  (It's possible to reduce it to only one invocation,
but not without making some questionable assumptions about the
internals of the CBC decryption primitive.)

> solution, and I'd prefer the counter one on account of performance

I agree that some additional text in the introduction explaining the
design choices would be useful.

---

From: Kelley Burgin <[email-masked]>
Date: Wed, 22 May 2013 15:09:31 -0400

I'm happy to give an explanation of design choices in the document.  
(especially those that differ from Kerberos tradition)

Looking over Tom's short-plaintext scheme again, I see the mistake I  
made in reading the variables. It looks good to me, with one question:  
is len(C) ever anything but blocksize?

plen = len(plaintext)
if plen < blocksize:
  C = Enc-CBC(Ke, plaintext | nullpad, IV)
  N1 = C[1..blocksize]    <-- question here
  C1 = N[1..plen]
  H = HMAC(Ki, N1 | C1)
  ciphertext = N1 | C1 | H[1..h]

What is the feeling about including some text on the structure of  
salts (in particular the inclusion of random valid UTF-8 sequences) in  
the document? Does this make sense here? Is it worth a separate  
document?

Kelley

---

From: [email-masked] (Martin Rex)
Date: Thu, 23 May 2013 04:57:39 +0200 (CEST)

Slightly off-topic:

Kelley Burgin wrote:
> 
> (the intended applications there don't have a problem with PKCS#5 padding)

I'm confused, where does the term "PKCS#5 padding" come from?

While there is a specific DES-CBC (and DES-EDE3-CBC) padding for
64-bit block ciphers described in PKCS#5 (e.g. v2.0 rfc2898),

  - that padding is strictly limited to 64-bit

  - that padding is explicitly described as
    "being taken from rfc1423" (->Privacy Enhanced Mail (PEM))

    http://tools.ietf.org/html/rfc2898#page-13

Curiously, rfc1423 is similarily limited to 64-bit block ciphers (DES):

    http://tools.ietf.org/html/rfc1423#page-3

A "generalization" of that padding scheme for block sizes up to 255 octets
can be found in PKCS#7 v1.5 end of section 10.3 (rfc2315):

  http://tools.ietf.org/html/rfc2315#page-22

        2.   Some content-encryption algorithms assume the
             input length is a multiple of k octets, where k > 1, and
             let the application define a method for handling inputs
             whose lengths are not a multiple of k octets. For such
             algorithms, the method shall be to pad the input at the
             trailing end with k - (l mod k) octets all having value k -
             (l mod k), where l is the length of the input. In other
             words, the input is padded at the trailing end with one of
             the following strings:

                      01 -- if l mod k = k-1
                     02 02 -- if l mod k = k-2
                                 .
                                 .
                                 .
                   k k ... k k -- if l mod k = 0

             The padding can be removed unambiguously since all input is
             padded and no padding string is a suffix of another. This
             padding method is well-defined if and only if k < 256;
             methods for larger k are an open issue for further study.

-Martin

---

From: Kelley Burgin <[email-masked]>
Date: Thu, 23 May 2013 08:49:35 -0400

Sorry for the confusion. I was referring to Section B.2.5 of PKCS#5  
v2.1 (AES-CBC-Pad) which points to RFC 5652 (CMS, derived from PKCS#7).

Kelley

---

From: Benjamin Kaduk <[email-masked]>
Date: Thu, 23 May 2013 11:05:18 -0400 (EDT)

> (especially those that differ from Kerberos tradition)

That would be good, thanks.

> What is the feeling about including some text on the structure of salts (in 
> particular the inclusion of random valid UTF-8 sequences) in the document? 
> Does this make sense here? Is it worth a separate document?

I think it would be reasonable to include a "suite B considerations" (or 
similar) section at the end, possibly even in the security considerations, 
noting that this enctype is proposed to support a suite B profile, which 
will want random salts, and that salts must be valid UTF-8.  Hmm, I wonder 
whether the concept of a "random valid UTF-8 sequence" is well-defined...

-Ben

---

From: Nico Williams <[email-masked]>
Date: Thu, 23 May 2013 10:27:26 -0500

> whether the concept of a "random valid UTF-8 sequence" is well-defined...

Zalgo comes to mind...

---

From: Sam Hartman <[email-masked]>
Date: Thu, 23 May 2013 15:19:24 -0400

Speaking as an individual.  Comments on the salt issue.

I think that thinking about salting and password hashing has advanced
significantly since 4120.

I think that including a section in a document defining a new enctype
updating our thinking on salting and password hashing would be valuable.

If I were wwriting that section I'd include:

1) value of random salts

2) Issues you run into with Kerberos

2.1) Specifically including the issue of finding salt to construct a
keytab

2.2) And cross-realm keys

3) Discuss mitigations for 2

3.1) How well does performing an as-req and looking at the etype-info2
work in both cases.  Probably fine for servers and perhaps not so fine
for cross-realm

3.2) Well, there is Nico's set/change password draft, that unfortunately
no one is interested in implementing.

---

From: Nico Williams <[email-masked]>
Date: Thu, 23 May 2013 14:39:37 -0500

> 1) value of random salts

If random salts are valuable (I think they are, though *any* salt
that's different for each principal gets us most of the value of
salts) then salts must be changed when passwords are changed.
Otherwise the fact that a salt was initially selected randomly loses
the benefit of having been selected randomly: an attacker can see what
the salt is, after all.

> 2.2) And cross-realm keys

They are both exactly the same issue.  In both cases the resulting
keys are added to a sort of key database.

> 3) Discuss mitigations for 2

The only mitigations are: a) send an AS-REQ to learn the salt (and
other s2kparams) with, or b) have the salt (and other s2kparams) at
hand for off-line key generation.

> work in both cases.  Probably fine for servers and perhaps not so fine

It should work for both cases.  A cross-realm relationship might be
uni-directional, and there might be a firewall in place preventing
AS-REQs in one direction, therefore the key should be added first to
the realm whose KDCs are reachable by the other realm's admins.

> no one is interested in implementing.

Right.  Forget it.  Well, now that more implementations have/use ASN.1
compilers it might be worth reviving, but then, I think I'd just as
well do a JSON-based change/set password protocol.

Nico
--

---

From: Sam Hartman <[email-masked]>
Date: Thu, 23 May 2013 16:12:47 -0400

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

    Nico> They are both exactly the same issue.  In both cases the
    Nico> resulting keys are added to a sort of key database.

I don't think they are exactly the same.  I can think of many fewer
reasons a realm would permit an AS-req with a cross-realm princ as a
client than it would for a server.

---

From: Nico Williams <[email-masked]>
Date: Thu, 23 May 2013 15:32:41 -0500

> client than it would for a server.

True, but though it might not permit it it should still serve the
etype info2, so we get the salt for this purpose.

---

From: Nico Williams <[email-masked]>
Date: Thu, 23 May 2013 15:41:30 -0500

Alternative mitigation for x-realm: don't randomize the salt.  The
x-realm password had better be very strong anyways.

---

From: Benjamin Kaduk <[email-masked]>
Date: Thu, 23 May 2013 16:59:10 -0400 (EDT)

> client than it would for a server.

Didn't we talk about this (elsewhere) when considering how to unilaterally 
rekey a cross-realm trust?  The AS protocol only had one realm field, was 
my recollection, so a cross-realm AS-req is impossible.

-Ben

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Thu, 23 May 2013 19:41:23 -0400

> my recollection, so a cross-realm AS-req is impossible.

Right; there's no way to express an AS-REQ in which the client and
service are not in the same realm.

---

From: Nico Williams <[email-masked]>
Date: Thu, 23 May 2013 19:16:18 -0500

> service are not in the same realm.

Right, but here the client principal *is* the x-realm principal in
question, the service principal is irrelevant (could be the same as
the client principal) and the KDC can be in either realm (whichever
one the client principal was created in).  Of course, if the x-realm
principal is created first in the KDB of the *other* realm then
there's no other principals that could be used as the service
principal but itself.  Either way, it should work.  Ah, and completing
the AS exchange has some value, particularly if the service is the
same as the client principal: to validate the key.

Keeping the salt secret (and if it's randomly generated) adds to the
strength of... what should be a strong key to begin with, so I don't
see any point in disallowing the AS exchange in this case.  But it
could be disabled after the key is exchanged.

Anyways, we really need a DH x-realm key exchange protocol.  And
better: PKCROSS (and we don't need Ticket extensions, just encrypted
(or authenticated anyways) PA-DATA.

Nico
--

---

From: Sam Hartman <[email-masked]>
Date: Thu, 23 May 2013 22:23:18 -0400

>> 
    >> I don't think they are exactly the same.  I can think of many
    >> fewer reasons a realm would permit an AS-req with a cross-realm
    >> princ as a client than it would for a server.

    Nico> True, but though it might not permit it it should still serve
    Nico> the etype info2, so we get the salt for this purpose.

Treating the issues differently so we could consider whether we want to
recommend stuff like this was my primary motivation for calling out
xrealm separately.

---

From: Tom Yu <[email-masked]>
Date: Thu, 23 May 2013 23:05:30 -0400

> solution, and I'd prefer the counter one on account of performance

As an implementor, I'm reluctant to use any scheme where the
short-plaintext case requires a substantially difference code path.
Such special cases increase the risk of bugs and interop problems.
I'm not sure it's better to reconsider PKCS#7-padded CBC mode with
random public IV or confounded CTS mode.

---

From: Sam Hartman <[email-masked]>
Date: Thu, 23 May 2013 23:20:31 -0400

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

    Tom> Nico Williams <[email-masked]> writes:
    >> Some text for the intro section would be nice.  And a solution to
    >> the short plaintext problem is critical (if nothing else because
    >> GSS consumers are free to use shorter plaintexts and we don't
    >> know if they do or don't; ditto AFS and other non-Internet
    >> protocols).  I'm happy with either a counter or confounded short
    >> plaintext encryption solution, and I'd prefer the counter one on
    >> account of performance (again).

I'd like to better understand how GSS consumers contribute to the
short-plaintext problem.  won't the CFX header always be large enough to
get us a block?

---

From: Nico Williams <[email-masked]>
Date: Fri, 24 May 2013 00:30:02 -0500

> short-plaintext problem.  won't the CFX header always be large enough to

Oh, indeed!  CFX wrap token headers are 16 bytes.

KRB-PRIV and AP-REP are the PDUs with the shortest plaintext input to
encryption in RFC41210, I think.  If I count correctly a 0-byte
plaintext can yield a EncKrbPrivPart no shorter than exactly 23 bytes
assuming HostAddress types that are no shorter than 4 bytes.  As for
EncAPRepPart the ctime field (and its tags) along get us past 16
bytes.  Hmmm, an EncKrbCredPart with zero KrbCredInfoscould be shorter
than 16 bytes, but it'd be senseless.

That only leaves non-standard consumers of RFC3961 to worry about.

Nico
--

---

From: Sam Hartman <[email-masked]>
Date: Fri, 24 May 2013 08:44:42 -0400

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

    Nico> On Thu, May 23, 2013 at 10:20 PM, Sam Hartman <[email-masked]> wrote:
    Nico> That only leaves non-standard consumers of RFC3961 to worry
    Nico> about.

    Nico> Nico --

    Jeff H has argued that those non-standard consumers are important.
I've seen no disagreement here.

As chair it sounds like we want to  fix the short-plaintext problem.

However, it's not sounding like it's going to come up in practice much.

I don't know that affects our decision space much, but it seems good to
characterize the problem we're solving.

we seem to need a solution to short plaintext because it is a
specification requirement.  It does not seem to be performance critical
or often-exercised code.

we also want to be careful not to have it be code that becomes often
exercised because its bugs are convenient for attackers:-)

---

From: Greg Hudson <[email-masked]>
Date: Fri, 24 May 2013 12:04:20 -0400

> However, it's not sounding like it's going to come up in practice much.

Perhaps not with protocol data, but it comes up in MIT krb5 when
encrypting key data with the master key.  Encrypting a DES key in an AES
master key is a payload less than the block size (8 < 16); encrypting an
AES-128 key is a payload equal to the block size (16 = 16).

> specification requirement.  It does not seem to be performance critical

Decrypting key data is performance-relevant to KDCs, although my
experience is that for short payloads, API overhead competes with block
encryption costs.  Obviously, using RFC 3961 encryption for key data is
an implementation choice.

Also note that RFC 3962 has a short plaintext exception for 0-length
plaintexts--section 5 paragraphs 3 and 6.

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Fri, 24 May 2013 14:40:07 -0400

> plaintexts--section 5 paragraphs 3 and 6.

RFC3962's discussion of CTS does indeed include a short plaintext
exception.  However, this never comes into play, because the enctypes
described in that document are based on the simplified profile, which
never invokes the underlying cipher with a message shorter than an
entire cipher block.  When encrypting application data, there is a
one-cipher-block confounder.  In key derivation, the constant is first
n-folded to the block size.  This turns out to be important, because key
derivation depends on the cipher behaving deterministically, and CTS as
described in RFC3962 section 5 is not required to behave
deterministically for inputs shorter than one block.

-- Jeff

---

From: Nico Williams <[email-masked]>
Date: Fri, 24 May 2013 13:45:49 -0500

> (again, for performance reasons).

And also because it doesn't introduce any ambiguities for us to
resolve: if the ciphertext is shorter than 16 bytes then do the
counter mode thing, else do CTS.

Greg's note makes me nervous about abandoning short plaintext support.

Nico
--

---

From: Tom Yu <[email-masked]>
Date: Fri, 24 May 2013 14:58:56 -0400

> counter mode thing, else do CTS.

My suggestion didn't involve counter mode, just a different
interpretation of CTS.

---

From: Nico Williams <[email-masked]>
Date: Fri, 24 May 2013 14:30:50 -0500

> My suggestion didn't involve counter mode, just a different

Ah, I'd lost track.  Also, my approach doesn't have the ambiguity I
thought it had.

---

From: Greg Hudson <[email-masked]>
Date: Fri, 24 May 2013 15:44:24 -0400

On 05/24/2013 02:40 PM, Jeffrey Hutzelman wrote:
> entire cipher block.

But they can invoke the underlying cipher with a message length exactly
equal to one cipher block, if the RFC 3961 input length is zero.  So the
RFC 3962 exceptions for encrypting exactly one block can come into play.

(NIST SP800-38A is confusing on whether its algorithms are defined for
an input length of exactly one block.  The introductory text claims that
it specifies "three variants of CBC mode that accept any plaintext
input whose bit length is greater than or equal to the block size," but
the algorithms don't seem to work for an input equal to the block size.
 In CBC-CS1-Encrypt, for instance, you get n=1, d=b at step 1, a single
cipherblock C[1] at step 3, and then step 4 references C[0] which isn't
defined.)