Subject: static-static DH proposal

From: [email-masked] (Sam Hartman)
Date: Tue, 21 Sep 2004 16:10:46 -0400 (EDT)

I think I finally understand what we're trying to do here.

                            Current State

The document currently allows KDCs to cache DH parameters but does not
allow clients to do so.  The protocol behind this caching is
acceptable although new security considerations text would be needed
to move  forward with this option.

However Paul, Larry and I have worked on a better solution that allows
clients to cache DH parameters and will get you a good key even if
only one side is contributing good random data.  We believe that it is
worth including this proposal.  I believe the document is acceptable
even if the new proposal is not included for time reasons.

		       Summary of Current State

Currently, the document proposes that clients can enable KDC side
caching of DH parameters by setting the nonce to 0 in the
PKAuthenticator.  If a client sends a 0 nonce, then the KDC responds
with a 0 nonce and may reuse old DH parameters.  The KDC may also
reuse old signatures of the request, although it includes an
expiration time for the signature.

This text is probably acceptable given some additional security
considerations text about small group DH attacks pulled from the CMS
RFCs.  We'll also need to improve our DH group selection  to get past
the IESG.

			  Proposed Extension

First, we are going to need two new nonces.  These nonces called the
clientDHNonce and the serverDHNonce are longer than the  Kerberos
nonce; they are at least as long as the symmetric key being
negotiated.  

Instead of sending  a 0 nonce to the server to indicate support for
caching DH parameters, the client includes a clientDHNonce.    The
client always needs to generate a fresh signature.    

If the server supports caching DH parameters then it includes a
serverDHNonce and uses the key derivation discussed previously on the
list.   The server may reuse a cached signature and  may cache its DH
parameters.

If the client receives a response with a serverDHNonce then it may
reuse its DH parameters in the future.  If the response does not
include a serverDHNonce, then the client must not reuse parameters.

Specific Changes

For ASN.1, define the structure

DH-Rep-Info ::= sequence {
        dhSignedData            [0] ContentInfo,
                                    -- Type is SignedData.
                                    -- Content is KDCDHKeyInfo
                                    -- (defined below).
	serverDHNonce 		[1] DHNonce OPTIONAL
}

and redefine pa-pk-as-rep as:

    PA-PK-AS-REP ::= CHOICE {
	dhInfo 			[0] DH-Rep-Info,
        encKeyPack              [1] ContentInfo,  
				    -- Type is EnvelopedData.
				           -- Content is SignedData over
					          -- ReplyKeyPack (defined below).
        ...
    }

    PA-PK-AS-REQ ::= SEQUENCE {
        signedAuthPack          [0] ContentInfo,
                                    -- Defined in CMS [2].
                                    -- Type is SignedData.
                                    -- Content is AuthPack
                                    -- (defined below).
        trustedCertifiers       [1] SEQUENCE OF TrustedCA OPTIONAL,
                                    -- A list of CAs, trusted by
                                    -- the client, used to certify
                                    -- KDCs.
        kdcCert                 [2] IssuerAndSerialNumber OPTIONAL,
                                    -- Defined in CMS [2].
                                    -- Identifies a particular KDC
                                    -- certificate, if the client
                                    -- already has it.	
clientDHNonce			[3] DHNonce OPTIONAL,
        ...
}

In addition, the following textual changes are recommended:

--- pk	2004-09-21 16:09:30.000000000 -0400
+++ draft-ietf-cat-kerberos-pk-init-20.txt	2004-09-21 16:07:53.000000000 -0400
@@ -366,12 +366,6 @@
                                     -- in CLARIFICATIONS, for replay
                                     -- prevention.
         nonce                   [2] INTEGER (0..4294967295),
-                                    -- Binds reply to request,
-                                    -- MUST be zero when client
-                                    -- will accept cached
-                                    -- Diffie-Hellman parameters
-                                    -- from KDC. MUST NOT be
-                                    -- zero otherwise.
         paChecksum              [3] Checksum,
                                     -- Defined in CLARIFICATIONS.
                                     -- Performed over KDC-REQ-BODY,
@@ -410,14 +404,11 @@
         (See RFC 2409 [10].)

-    6.  The KDC may wish to use cached Diffie-Hellman parameters.
-        To indicate acceptance of caching, the client sends zero in
-        the nonce field of the pkAuthenticator.  Zero is not a valid
-        value for this field under any other circumstances.  Since
-        zero is used to indicate acceptance of cached parameters,
-        message binding in this case is performed using only the
-        nonce in the main request.
-
+    6.  The client may wish to cache DH parameters or to allow the KDC
+        to do so.   If so, then the client must include the
+        clientDHNonce field.  The nonce string needs to be as long as
+        the longest symmetric key type that the client supports.  The
+        nonce MUST be chosen randomly.  

 3.2.2.  Validation of Client Request
@@ -626,12 +617,11 @@
                                     -- of BIT STRING.
         nonce                   [1] INTEGER,
                                     -- Binds reply to request.
-                                    -- Exception: A value of zero
-                                    -- indicates that the KDC is
-                                    -- using cached values.
         dhKeyExpiration         [2] KerberosTime OPTIONAL,
                                     -- Expiration time for KDC's
-                                    -- cached values.
+                                    -- cached values.  If this field
+				    -- is omitted  then the
+				    -- serverDHNonce field MUST also be omitted
         ...
     }
 
@@ -660,13 +650,18 @@
         certificate.

-    5.  If the client and KDC agree to use cached parameters, the
-        KDC MUST return a zero in the nonce field and include the
-        expiration time of the cached values in the dhKeyExpiration
-        field.  If this time is exceeded, the client MUST NOT use
-        the reply.  If the time is absent, the client MUST NOT use
-        the reply and MAY resubmit a request with a non-zero nonce,
-        thus indicating non-acceptance of the cached parameters.
+    5.  If the client included the clientDHNonce field, then the KDC
+        may choose the reuse  its DH parameters.  If the server will
+        reuse DH parameters then it MUST include an expiration time in
+        the dhKeyExperiation field.  Past this point, the signature of
+        the DH-Rep-Info is invalid.  If the server will reuse DH
+        parameters then it MUST include a serverDHNonce at least as
+        long as the length of keys for the symmetric encryption system
+        used to encrypt the AS reply.  Note that including the
+        serverDHNonce changes how the client and server calculate the
+        key to  use to encrypt the reply; see below for details.
+        Clients MUST NOT reuse DH parameters unless the response
+        includes the serverDHNonce field.  

 The key is derived as follows: Both the KDC and the client calculate
@@ -678,6 +673,18 @@
 applying to it a random-to-key function, which is also dependent on
 key type.
 
+If the serverDHNonce is included, this key, k_dh goes through
+additional derivation steps.  Let k_dh be the resulting initial DH key
+after truncation and random-to-key.  Let n_c be the clientDHNonce  and
+n_k be the serverDHNonce.  
+
+k_i = prf(k_dh, n_c|n_k|i) 
+Where | is  concatenation
+k = k_0|...|k_c
+
+Then trucate the new k to be the right size and run through
+random-to-key.
+
 
 If the KDC and client are not using Diffie-Hellman, the KDC encrypts
 the reply with an encryption key, packed in the encKeyPack, which
@@ -822,15 +829,6 @@
 depends on the size of the Diffie-Hellman group.

-If a client also caches its Diffie-Hellman keys, then the session key
-could remain the same during multiple AS-REQ/AS-REP exchanges and an
-attacker which compromised the session key could fabricate his own
-AS-REP messages with a pre-recorded pre-authenticator until the
-client starts using a new Diffie-Hellman key pair and while the KDC
-pre-authenticator has not yet expired.  It is therefore not
-recommended for KDC clients to also cache their Diffie-Hellman keys.
-
-
 Care should be taken in how certificates are chosen for the purposes
 of authentication using PKINIT.  Some local policies may require
 that key escrow be used for certain certificate types.  Deployers of

---

From: "Liqiang(Larry) Zhu" <[email-masked]>
Date: Fri, 24 Sep 2004 09:30:10 -0700

Ken Raeburn wrote:
> > k_i = PRF(k_dh, i), i>=0
> The second parameter to PRF is an octet string; 
> what's the encoding here?  Four octets?  Smallest number of 
> octets that can express the value?  MSB or LSB first?  DER?

The second parameter i is expressed as four octets in big-endian order.

Ken, I noticed that on page 4 of kcrypto-7, the key generation seed
length K is in upper case, but in page 13, it is in lower case. Is this
intentional? Also the use of the symbol K as a length parameter is a bit
misleading, in that K is often used to refer to a key, how about using L
for the key generation seed length.
 
--Larry

-----Original Message-----
From: Ken Raeburn [mailto:[email-masked]] 
Sent: Friday, September 24, 2004 9:04 AM
To: Liqiang(Larry) Zhu
Cc: Sam Hartman; <[email-masked]>
Subject: Re: static-static DH proposal

On Sep 24, 2004, at 03:43, Liqiang(Larry) Zhu wrote:
> Humm... The function in my previous email needs a type-cast and here 
> is the corrected version:
>
> ----------------------------------------------------------------------
> - k_dh = random-to-key(K-truncate(PRF(random-to-key(K-fold(g^xy)),
> g^xy|n_c|n_k)|g^xy))

Couldn't K possibly be larger than PRF|g^xy?
(Unlikely, sure, but possible?)

> k_i = PRF(k_dh, i), i>=0

The second parameter to PRF is an octet string; what's the encoding
here?  Four octets?  Smallest number of octets that can express the
value?  MSB or LSB first?  DER?

> k = random-to-key(K-truncate(k_0|k_1|...))
>
> where | is concatenation, g^xy is the shared secret from the 
> Diffie-Hellman exchange, K is the key-generation seed length, The 
> K-fold and PRF operations are defined in Kcrypto.
> ----------------------------------------------------------------------
>
> The reply key is k.
>
> --Larry
>
>
> -----Original Message-----
> From: Liqiang(Larry) Zhu
> Sent: Friday, September 24, 2004 12:24 AM
> To: 'Sam Hartman'
> Cc: [email-masked]
> Subject: RE: static-static DH proposal
>
>
> Sam Hartman wrote:
>> However what you propose does not type check and is not well formed.
>> k_i is not the same type or length as k_dh.  It's not a protocol key;

>> you cannot use it as the key argument to > prf.
>
> Here is the type-safe version for deriving the reply key k:
>
>
> k_dh = random-to-key(K-truncate(PRF(K-fold(g^xy), g^xy|n_c|n_k)|g^xy))

> k_i = PRF(k_dh, i), i>=0 k = random-to-key(K-truncate(k_0|k_1|...))
>
> where | is concatenation, g^xy is the shared secret from the 
> Diffie-Hellman exchange, K is the key-generation seed length, The 
> K-fold and PRF operations are defined in Kcrypto.
>
>
> I argue for this key generation function because:
> 1) This adds no significant complexity
> 2) It is safer to include all the bits of the share secret from the DH

> exchange
> --Larry

---

From: "Liqiang(Larry) Zhu" <[email-masked]>
Date: Fri, 24 Sep 2004 18:37:07 -0700

Ken Raeburn wrote:
> There's nothing in the PRF spec that says the output can't reveal
parts of the octet string input, as long as the random-
> to-key operation isn't significantly weakened by doing so.

I understand that, that is why I did not do exactly the same thing as
what PRF+ does - feeding the derived keys as the input of PRF.

We just realized that the more common case is when the PRF hash length
is *shorter* than the key length, this makes my
hash-through-PRF-to-get-k_dh approach highly undesirable.

With that, I would like to support Sam's truncation algorithm for k_dh.

Larry

-----Original Message-----
From: Ken Raeburn [mailto:[email-masked]] 
Sent: Friday, September 24, 2004 5:05 PM
To: Liqiang(Larry) Zhu
Cc: Ken Raeburn; <[email-masked]>
Subject: Re: static-static DH proposal

On Sep 24, 2004, at 19:00, Liqiang(Larry) Zhu wrote:
> Ken Raeburn wrote:
>> For the moment.  If Something Bad happens, like AES gets broken in 
>> six months, and we come up with a new cryptosystem based on CCM mode 
>> or something and not using the simplified profile, then Kerberos 5.3 
>> might not require an n-fold implementation.
>
> The n-fold is not than hard to implement, certainly not hard to keep 
> it around when AES-CTS is removed

Yes, I don't think this is a very big deal.

>> We don't have a lot of analysis at this point in terms of how the 
>> secrecy or entropy of the result should or does relate to the inputs 
>> for compliant Kerberos cryptosystem PRFs in general.
>
> I would have more confidence if one method has been used in practice.
> Do you know anything else is using the truncated DH shared secret?

Haven't really looked.  So, no, but that doesn't mean much.

I've stared at n-fold enough to be uncomfortable with using it for
anything more than assuring equal contributions by each input bit.  
Generating collisions is easy if you control the input.  Assuring
yourself that there aren't likely to be collisions under certain
circumstances is hard.  (Of course, we can't assure the absence of
collisions for sha1 either, but we're confident the probability is low,
and we have no reason to be so confident with n-fold.)

Oh, and by the way: You still have a type mismatch error in your
proposal.  n-fold takes a bit string input, and g^xy is a number; you
need to specify the format of the bit string.

If we assume the number is converted to an octet string representation,
MSB first, and if in some cases the length is a multiple of K, then
n-fold starts to resemble modular arithmetic.  Given that we're starting
with math to get to g^xy in the first place, I'd be a bit concerned that
this could simplify an attacker's estimation of the result in some way.
(It may not, and I don't see how it would.  But it's an angle I'd want
to see someone investigate a little more.)

> I think the kcrypto spec on PRF is pretty weak, and this is the first 
> instance where the PRF is used, the spec should be updated or we 
> should come up with the next version right away to make sure the PRF 
> meets the need here.
>
> From a more philosophic perspective, nobody says HMAC has the property

> that the hash of a secret has no less entropy/secrecy than that of the

> key, but it is widely used in key derivation and the method is 
> believed to be secure.

HMAC is a specific approach that's been looked at a lot, and there are
statements that can be made about its use if you can make certain
assumptions about the hash function.  Even if certain statements cannot
be made, its resistance to attacks has given people some confidence.  
Our PRF is a place for a cryptosystem author to drop in a function of
his choosing, so we can't say much.

I kind of assumed that strong key generation would be the key (so to
speak) to having a good PRF that you could get keying material out of.  
You're using a key generation function which may or may not be strong,
and relying on having lots of unpredictable material in the octet
string.  There's nothing in the PRF spec that says the output can't
reveal parts of the octet string input, as long as the random-to-key
operation isn't significantly weakened by doing so.

Ken

---

From: "Liqiang(Larry) Zhu" <[email-masked]>
Date: Sun, 26 Sep 2004 21:58:52 -0700

BTW: ZZ is defined in RFC 2631 (http://www.ietf.org/rfc/rfc2631)

-- Larry
-----Original Message-----
From: Nicolas Williams [mailto:[email-masked]] 
Sent: Thursday, September 23, 2004 11:08 AM
To: Sam Hartman
Cc: Liqiang(Larry) Zhu; [email-masked]
Subject: Re: static-static DH proposal

On Thu, Sep 23, 2004 at 02:05:24PM -0400, Sam Hartman wrote:
> >>>>> "Liqiang(Larry)" == Liqiang(Larry) Zhu
<[email-masked]> writes:
>     Liqiang(Larry)> 2) I prefer to use the same key derivation
function when cached
>     Liqiang(Larry)> parameters are NOT used: you can use zero for both
n_c and n_k (more
>     Liqiang(Larry)> precisely, the proper length of zero octets).
> 
> That's fine with me.  How does the rest of the working group feel
about it?

I think I get it, yes, that's fine.

>     Liqiang(Larry)> 3) It won't hurt to include the whole ZZ in the
key derivation, how
>     Liqiang(Larry)> about the following key derivation algorithm:
> 
>     Liqiang(Larry)> k_0 = PRF(k_dh, n_c|n_k|ZZ)
>     Liqiang(Larry)> k_(i+1) = PRF(k_i, i), i>=0
>     Liqiang(Larry)> where | is concatenation
>     Liqiang(Larry)> k = k_0|k_1|...|k_c
> 
> I think I agree with including zz too, but I don't remember what it 
> is.

I forget also.

Nico
--