Subject: [Ietf-krb-wg] FAST: do we need the checksum

From: Sam Hartman <[email-masked]>
Date: Wed, 04 Mar 2009 12:13:24 -0500

The FAST checksum in the finish messages is probably the most
complicated part of FAST.  It requires the KDC to be able to produce a
checksum of the entire conversation with the client in the last
message, even though the KDC's only state is the fast cookie.

You can do this by either having checksum primitives that allow you to
serialize the internal state of the checksum, or by including previous
messages in the cookie.
        
It's clearly doable but it is kind of ugly and complicated.

I was looking yesterday at what the checksum actually buys us.

Note that similar checksums are important in TLS and SSH because those
protocols exchange negotiation parameters in the clear and need to
confirm them at the end.  FAST starts out with an armor key, so
everything starting with the first message is protected.
(Obtaining the armor key is not, but that is a separate exchange.)

So, what does a checksum of a conversation give you?

* protects all fields in all messages in the conversation [1]
* Guarantees that both sides received the same messages in the same order
    ** no insertions
     * no reorderings
    ** no replays

[1] It turns out that the FAST checksum does not cover the message
that contains it, but other mechanisms protect the content of that
message.

It turns out that the only thing used from outside the encrypted FAST
request in the message from the client to the KDC is the cookie.  The
request body is taken from inside the FAST request, not the outer
body.  The only thing else in a kdc req is the sequence of padata.
Except for the cookie everything else is taken from inside the fast
request.

For error responses, everything except for the padata is taken from the pa-fx-error.

For the as-rep or tgs-rep, everything is taken from the finish message
except for the ticket (and probably absent cookie).  The ticket is
covered by the ticket checksum in the finish message.

So in terms of preventing message modifications, the checksum in the
finish message only protects the cookie.  Of course, the only reason
the cookie is outside of FAST is that the checksum in the finish
message is far easier to deal with that way.

The armor key is unique to a conversation; that prevents a message from one conversation from appearing to be part of another conversation.

So, the checksum buys us replay protection and sequence protection.

I think we could get the same thing by including the nonce in the fast
response for both errors and replies and asking clients to choose a
random nonce.

Does it make sense to do that?  Do other people agree it has adequate security properties?
Do people want to make the change?
_______________________________________________
ietf-krb-wg mailing list
[email-masked]
https://lists.anl.gov/mailman/listinfo/ietf-krb-wg

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Fri, 06 Mar 2009 00:02:43 -0500

> serialize the internal state of the checksum, or by including previous

Another possibility is to define the checksum to be recursive, such that 
each checksum is a hash of the last checksum and the most recent message. 
This allows the cookie to contain only the most recent checksum, rather 
than all of the previous messages, and works even when the checksum does 
not allow incremental computation.

Note that virtually any hash we actually use will allow incremental 
computation, because this is considered to be a fairly important feature 
from a practical standpoint.  However, that doesn't mean that every hash 
will have exportable state, or portably exportable state, and the RFC3961 
abstraction does not require hashses to be incrementally computable in any 
event.

> So, the checksum buys us replay protection and sequence protection.

Yes, I think that's accurate.  I think.

> response for both errors and replies and asking clients to choose a

You mean, a new random nonce for every round trip?  If I understand what 
you're proposing correctly, then yes, I think that would do the job. 
However, if possible I'd rather see an approach that doesn't require the 
client to come up with quite so much random data, which can be challenging 
on some types of clients.  Maybe some sort of pseudo-random sequence based 
on the armor key and a counter?

> Does it make sense to do that?  Do other people agree it has adequate
> security properties? Do people want to make the change?

<hat type=chair>
I would be very interested in seeing other people's responses to these 
questions.  We need to be sure we understand the possible impact of the 
proposed change.
</hat>

-- Jeff

---

From: Sam Hartman <[email-masked]>
Date: Fri, 06 Mar 2009 10:37:04 -0500

>>>>> "Jeffrey" == Jeffrey Hutzelman <[email-masked]> writes:

    Jeffrey> --On Wednesday, March 04, 2009 12:13:24 PM -0500 Sam
    Jeffrey> Hartman
    Jeffrey> <[email-masked]> wrote:

    >> complicated part of FAST.  It requires the KDC to be able to
    >> produce a checksum of the entire conversation with the client
    >> in the last message, even though the KDC's only state is the
    >> fast cookie.
    >> 
    >> You can do this by either having checksum primitives that allow
    >> you to serialize the internal state of the checksum, or by
    >> including previous messages in the cookie.

    Jeffrey> Another possibility is to define the checksum to be
    Jeffrey> recursive, such that each checksum is a hash of the last
    Jeffrey> checksum and the most recent message. This allows the
    Jeffrey> cookie to contain only the most recent checksum, rather
    Jeffrey> than all of the previous messages, and works even when
    Jeffrey> the checksum does not allow incremental computation.

That is not consistent with the current spec.
You are correct the spec could be changed to support this.

    >> I think we could get the same thing by including the nonce in
    >> the fast response for both errors and replies and asking
    >> clients to choose a random nonce.

    Jeffrey> You mean, a new random nonce for every round trip?  If I
    Jeffrey> understand what you're proposing correctly, then yes, I
    Jeffrey> think that would do the job. However, if possible I'd
    Jeffrey> rather see an approach that doesn't require the client to
    Jeffrey> come up with quite so much random data, which can be
    Jeffrey> challenging on some types of clients.  Maybe some sort of
    Jeffrey> pseudo-random sequence based on the armor key and a
    Jeffrey> counter?

I assume every Kerberos implementation has a relatively good PRF
sitting around somewhere.  For MIT Kerberos, I was just planning on
calling the make random octets function.  You could definitely use the
pseudo_random function on the armor key.  The real constraint is that
a nonce not be reused with the same armor key.

I would greatly appreciate comments on this very soon: I'll end up
making an optimistic prediction based on how things are going to turn
out probably next Tuesday.  As with all speculative execution,
annulments create wasted space in the pipeline:-)

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Fri, 06 Mar 2009 11:18:23 -0500

> You are correct the spec could be changed to support this.

Sorry if I was unclear.  Yes, doing this would certainly require a change 
to the spec, since the checksum must be computed in the same way by both 
sides.

> annulments create wasted space in the pipeline:-)

The I-D cutoff for IETF74 is next Monday, so I suggest making your 
prediction by then. :-)

-- Jeff

---

From: "Henry B. Hotz" <[email-masked]>
Date: Fri, 6 Mar 2009 12:53:06 -0800

Without saying anything about other issues: I know that delays due to  
using high-quality /dev/random have been seen in the wild.  I recall  
some problems with the earlier /dev/random implementations on NetBSD  
in particular.

A protocol which requires a lot of random data for each round-trip  
seems unwise.

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

---

From: Sam Hartman <[email-masked]>
Date: Fri, 06 Mar 2009 16:26:40 -0500

>>>>> "Henry" == Henry B Hotz <[email-masked]> writes:

    Henry> Without saying anything about other issues: I know that
    Henry> delays due to using high-quality /dev/random have been seen
    Henry> in the wild.  I recall some problems with the earlier
    Henry> /dev/random implementations on NetBSD in particular.

    Henry> A protocol which requires a lot of random data for each
    Henry> round-trip seems unwise.

Again, use a PRF.  As an example, in the MIT implementation, we only
use /dev/random for kadmind and then only rarely.  (This is enough to
block sometimes on startup for Linux) The clients use /dev/urandom,
which on Linux does not block.  But mostly within the library, the
yarrow PRNG is used.
_______________________________________________
ietf-krb-wg mailing list
[email-masked]
https://lists.anl.gov/mailman/listinfo/ietf-krb-wg

---

From: Nicolas Williams <[email-masked]>
Date: Fri, 6 Mar 2009 15:23:58 -0600

> A protocol which requires a lot of random data for each round-trip  

I don't think this matters much.  In practice the krb5 stack should be
using /dev/urandom, which should be a high-quality PRNG seeded with
entropy from the same sources that /dev/random gets entropy from (but
not the same entropy!).

At a glance I think I would prefer the chain of checksums.  But that's
just because it seems obvious (from Sam's and Jeff's posts) that that
will do, whereas I really need to pull up the latest FAST I-Ds and read
them to decide if the nonces will do.

Nico
--

---

From: Sam Hartman <[email-masked]>
Date: Fri, 06 Mar 2009 17:50:52 -0500

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

    Nicolas> At a glance I think I would prefer the chain of
    Nicolas> checksums.  But that's just because it seems obvious
    Nicolas> (from Sam's and Jeff's posts) that that will do, whereas
    Nicolas> I really need to pull up the latest FAST I-Ds and read
    Nicolas> them to decide if the nonces will do.

I strongly prefer the current text or getting rid of the checksum
entirely somehow.
_______________________________________________
ietf-krb-wg mailing list
[email-masked]
https://lists.anl.gov/mailman/listinfo/ietf-krb-wg

---

From: "Srinivas Cheruku" <[email-masked]>
Date: Tue, 10 Mar 2009 10:32:50 +0530

Sam,

In draft 9/10, in section "6.5.2 FAST Request"

        FastOptions ::= KerberosFlags
            -- reserved(0),
            -- hide-client-names(1),
            -- kdcfollow--referrals(16)

Where as in "Appendix B.  ASN.1 module"
      FastOptions ::= KerberosFlags
          -- reserved(0),
          -- anonymous(1),
          -- kdc-referrals(16)

It might be better if you use the same naming conventions. Just a thought.

Thanks,
Srini

-----Original Message-----
From: [email-masked]
[mailto:[email-masked]] On Behalf Of Sam Hartman
Sent: 07 March 2009 04:21
To: Nicolas Williams
Cc: [email-masked]; Jeffrey Hutzelman
Subject: Re: [Ietf-krb-wg] FAST: do we need the checksum

---

From: Sam Hartman <[email-masked]>
Date: Tue, 10 Mar 2009 09:33:23 -0400

Hi.  The text in 6.5.2 is roughly correct (although I notice a typo)
and that in the appendix is incorrect.

Thanks for pointing this out.

---

From: "Srinivas Cheruku" <[email-masked]>
Date: Wed, 11 Mar 2009 10:29:07 +0530

Sam,

I hope you correct the same in the next draft.

>From the same section
____
   The kdc-follow-referrals Option

If the kdc-follow-referrals option is
      set, the KDC MAY act as the client to follow TGS referrals
      [REFERRALS], and return the service ticket to the named server
      principal in the client request using the reply key expected by
      the client.  That is, rather than returning a referral, the KDC
      follows that referral by contacting a remote KDC and processing
      the referral.  The kdc-referrals option can be implemented when
      the KDC knows the reply key.  The KDC can ignore kdc-referrals
...
____

KDC acts as client and get the service ticket in case of referrals instead
of returning referral info - Is anyone implemented this or is this new? 

I also noticed kdc-referrals being using in the text portion of
kdc-follow-referrals option.

Thanks and Regards,
Srini