Subject: [kitten] PA-ENC-TIMESTAMP is worse than we thought; fix in aes-cts-hmac-sha2?

From: Nico Williams <[email-masked]>
Date: Tue, 12 Apr 2016 16:45:59 -0500

draft-ietf-kitten-aes-cts-hmac-sha2 wants randomly generated salts.

That's nice, but... why did we ever have non-randomly-generated salts?

"Convenience" seems like a nice explanation, but I suspect it wasn't
just that: it may have been a half-baked security feature.

  C->AS: AS-REQ
  AS->C: KRB-ERROR w/ PA-ETYPE-INFO2 w/ a random salt
  C:     string2key() w/ the AS's salt
  C->AS: AS-REQ w/ PA-ENC-TIMESTAMP using string2key() called with the
         server's choice of salt

Do you see the problem?

What if the AS is an active attacker?  They can then use a single salt
for all clients, one that they have a computed rainbow table for.  The
victim clients will happily use this salt.

  Mallory:    <choose salt, compute rainbow table>
  C->Mallory: AS-REQ
  Mallory->C: KRB-ERROR w/ PA-ETYPE-INFO2 w/ Mallory's rainbow table salt
  C:          string2key() w/ Mallory's choice of salt
  C->Mallory: AS-REQ w/ PA-ENC-TIMESTAMP using string2key() called with
              Mallory's choice of salt
  Mallory:    <start off-line rainbow table attack on C's PA-ENC-TIMESTAMP>
              <disappear or be MITM and pass through further exchanges
               between C and AS>
              <profit>

So randomizing the salt doesn't help at all.  It makes things worse
even: clients now can't sanity check the salt.

But if the salt *must* start with an unambiguous encoding of the
client's principal name and realm, _and_ if the client checks that this
is so, then the attacker can no longer have a single raibow table for
all victims.  And we can have a random suffix in the salt to add some
additional security (especially if this suffix is changed every time the
user changes their password).

Now, PA-ENC-TIMESTAMP is just awful and we know it, and this is NOT a
new attack: RFC3962's Security Considerations describes this attack as
to the iteration count (but not the salt, but the idea follows).

Though it does feel like a new attack: it seems likely that RFC3962
would have mentioned salt spoofing in addition to iteration count
spoofing, if the authors had thought of salt spoofing...  Back then the
WG did have a chance to improve some things for "newer" enctypes, and we
did, so we might have done that for salts too, if we'd thought of it.

Anyways, we've got two ways of addressing this problem _today_, and
we're working on a third:

 - (existing) PKINIT (look ma', no passwords; but not trivial to deploy)
 - (existing) FAST tunnel (requires a bit more configuration on the clients)
 - (upcoming) SPAKE

So maybe we just don't care about this problem.

But we could perhaps plug the above hole by requiring clients to check
that the salt is prefixed with an unambiguous encoding of the client
principal's name and realm name at least when using the new AES-CTS
HMAC-SHA2 enctypes or _newer_.  (Clients should probably _not_ require
this for older enctypes, not by default, for interop reasons.)

This has some consequences for principal renames, but pretty much
nothing else, I think.  Either principal renames cannot be supported
without an administrative password reset, or the KDC must force the user
to change their password after a rename _and_ the client must prompt the
user to confirm the rename and the previous principal name (which
further means that the client must be able to extract and decode the
principal name and realm name prefix from the salt).  I think this is
mostly a non-issue.

Do we care?  Enough to fix this?  Now?  Ever?

Now's the time for the new enctypes.  If not now, never (because the
SPAKE will take care of this problem).

If we're inclined to fix this now, I'll implement for Heimdal.

Nico
--

---

From: "Henry B (Hank) Hotz, CISSP" <[email-masked]>
Date: Tue, 12 Apr 2016 15:20:30 -0700

> On Apr 12, 2016, at 2:45 PM, Nico Williams <[email-masked]> wrote:
> 

I guess that’s a valid description. AFAIK time stamps were used because because there was no way to prevent replay attacks if you used the random nonce specified in the original Needham-Schroeder algorithm.

Anyone know when JAAS will support FAST or PKINIT?

Personal: [email-masked]
Business: [email-masked]
https://www.linkedin.com/in/hbhotz/

---

From: "Paul Miller (NT)" <[email-masked]>
Date: Tue, 12 Apr 2016 23:13:55 +0000

>>>  Mallory:    <start off-line rainbow table attack on C's PA-ENC-TIMESTAMP>

How is this supposed to work since the client injects its own entropy into the PA-ENC-TIMESTAMP?  It should not be possible to rainbow table this response as the PA-ENC-TIMESTAMP is not predictable given the password and salt.  The client time will not be predictable if the optional Microseconds is used in the PA-ENC-TS-ENC.  Even without that, the client should be using a random IV (or confounder) in its encryption of the timestamp.

At worst the AS could have a dictionary of the string-to-key for a number of passwords, but a dictionary is not nearly as powerful as a rainbow table due to its storage requirements and due to the fact that there is still a non-trivial amount of computation to test the key from each table entry.  Storing 32 bytes of key information for AES256 per potential password, a 1 EB table would hold the keys for 35 trillion passwords, which only covers 45 bits of entropy in potential passwords.

-----Original Message-----
From: Kitten [mailto:[email-masked]] On Behalf Of Nico Williams
Sent: Tuesday, April 12, 2016 2:46 PM
To: [email-masked]
Cc: Michael J. Jenkins <[email-masked]>; Kelley W. Burgin <[email-masked]>
Subject: [kitten] PA-ENC-TIMESTAMP is worse than we thought; fix in aes-cts-hmac-sha2?

"Convenience" seems like a nice explanation, but I suspect it wasn't just that: it may have been a half-baked security feature.

  C->AS: AS-REQ

Do you see the problem?

What if the AS is an active attacker?  They can then use a single salt for all clients, one that they have a computed rainbow table for.  The victim clients will happily use this salt.

But if the salt *must* start with an unambiguous encoding of the client's principal name and realm, _and_ if the client checks that this is so, then the attacker can no longer have a single raibow table for all victims.  And we can have a random suffix in the salt to add some additional security (especially if this suffix is changed every time the user changes their password).

Now, PA-ENC-TIMESTAMP is just awful and we know it, and this is NOT a new attack: RFC3962's Security Considerations describes this attack as to the iteration count (but not the salt, but the idea follows).

Though it does feel like a new attack: it seems likely that RFC3962 would have mentioned salt spoofing in addition to iteration count spoofing, if the authors had thought of salt spoofing...  Back then the WG did have a chance to improve some things for "newer" enctypes, and we did, so we might have done that for salts too, if we'd thought of it.

Anyways, we've got two ways of addressing this problem _today_, and we're working on a third:

But we could perhaps plug the above hole by requiring clients to check that the salt is prefixed with an unambiguous encoding of the client principal's name and realm name at least when using the new AES-CTS
HMAC-SHA2 enctypes or _newer_.  (Clients should probably _not_ require this for older enctypes, not by default, for interop reasons.)

This has some consequences for principal renames, but pretty much nothing else, I think.  Either principal renames cannot be supported without an administrative password reset, or the KDC must force the user to change their password after a rename _and_ the client must prompt the user to confirm the rename and the previous principal name (which further means that the client must be able to extract and decode the principal name and realm name prefix from the salt).  I think this is mostly a non-issue.

Now's the time for the new enctypes.  If not now, never (because the SPAKE will take care of this problem).

Nico
-- 

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

---

From: Nico Williams <[email-masked]>
Date: Wed, 13 Apr 2016 00:38:04 -0500

> >>>  Mallory:    <start off-line rainbow table attack on C's PA-ENC-TIMESTAMP>

Er, right, so this isn't a rainbow table.  It allows the attacker to
avoid having to compute s2k for each {password, salt}, but the attacker
still has to try every one (well, many) of those pre-computed keys to
decrypt the PA-ENC-TIMESTAMP ciphertext.  So it's an optimization on the
off-line dictionary attack, but the attack is still O(N), so not a huge
win.

I guess it's Emily Litella time for me then!

Nico
--