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

"Paul Miller (NT)" <paumil@microsoft.com> Tue, 12 April 2016 23:13 UTC

Return-Path: <paumil@microsoft.com>
X-Original-To: kitten@ietfa.amsl.com
Delivered-To: kitten@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 7462B12D5C4 for <kitten@ietfa.amsl.com>; Tue, 12 Apr 2016 16:13:59 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.993
X-Spam-Level:
X-Spam-Status: No, score=-1.993 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_MSPIKE_H2=-0.001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001, T_TVD_FUZZY_SECURITIES=0.01] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=microsoft.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id h8hRWrEZjsjr for <kitten@ietfa.amsl.com>; Tue, 12 Apr 2016 16:13:57 -0700 (PDT)
Received: from na01-by2-obe.outbound.protection.outlook.com (mail-by2on0120.outbound.protection.outlook.com [207.46.100.120]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 4E2FE12D15D for <kitten@ietf.org>; Tue, 12 Apr 2016 16:13:57 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=selector1; h=From:To:Date:Subject:Message-ID:Content-Type:MIME-Version; bh=aBgq+DqGZeM6ZvV4941ukYR3R6zqmxKnXRO/XffG4Kc=; b=CQIsYpGGiXV8h17PrPiQHay3pa/fWpaEsQm+Idf0i2vqnGqOKK5z6gaI94JE9QbE83tNcBoDuJBtLQh9PPujKDxpjNkKY4th+5JqHUcSZPNz8pzrVR5P+Ye5/oVIi27qEuWqsdaza+6lyt7EmQ6lSi9+GsORNRH+hbLG6b9xltw=
Received: from BLUPR0301MB1953.namprd03.prod.outlook.com (10.164.21.23) by BLUPR0301MB1953.namprd03.prod.outlook.com (10.164.21.23) with Microsoft SMTP Server (TLS) id 15.1.453.26; Tue, 12 Apr 2016 23:13:55 +0000
Received: from BLUPR0301MB1953.namprd03.prod.outlook.com ([10.164.21.23]) by BLUPR0301MB1953.namprd03.prod.outlook.com ([10.164.21.23]) with mapi id 15.01.0453.029; Tue, 12 Apr 2016 23:13:55 +0000
From: "Paul Miller (NT)" <paumil@microsoft.com>
To: Nico Williams <nico@cryptonector.com>, "kitten@ietf.org" <kitten@ietf.org>
Thread-Topic: [kitten] PA-ENC-TIMESTAMP is worse than we thought; fix in aes-cts-hmac-sha2?
Thread-Index: AQHRlQS+S13dp28DIEqkb5Jwn29+Jp+G8glw
Date: Tue, 12 Apr 2016 23:13:55 +0000
Message-ID: <BLUPR0301MB1953D569A4D0077ECE4556BFCD950@BLUPR0301MB1953.namprd03.prod.outlook.com>
References: <20160412214556.GE19617@localhost>
In-Reply-To: <20160412214556.GE19617@localhost>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
authentication-results: cryptonector.com; dkim=none (message not signed) header.d=none;cryptonector.com; dmarc=none action=none header.from=microsoft.com;
x-originating-ip: [2001:4898:80e8:3::3d8]
x-ms-office365-filtering-correlation-id: 22cb3f65-deb7-4cf3-9728-08d363281ee5
x-microsoft-exchange-diagnostics: 1; BLUPR0301MB1953; 5:Omod0opjUAIHuZUL2e5V7+Er60K/hyDSMUbr+KsZnJzvl217NJ1XgSa2QfbiNkfuKhHmMLLfs7s2/ZKXbNPtaITTjxL7CWDKNWwiROb4eENeIiJaPEE++vgtlj0ZUFwzEE+vsAf8PmFY1WHAebMq9Q==; 24:j3f/1kihEsuN0mV94dNaVM+vPTtOQdV/NJgDwZMVr3/ZurIg9/+pkql5kqZMlmO0ed3G/a7q3cQAmALvVOlcEb/aq/PS8PbULF5ZwjFbYZY=
x-microsoft-antispam: UriScan:;BCL:0;PCL:0;RULEID:;SRVR:BLUPR0301MB1953;
x-microsoft-antispam-prvs: <BLUPR0301MB1953515C407E6CDB350EF433CD950@BLUPR0301MB1953.namprd03.prod.outlook.com>
x-exchange-antispam-report-test: UriScan:;
x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(61425038)(601004)(2401047)(5005006)(8121501046)(3002001)(10201501046)(6055026)(61426038)(61427038); SRVR:BLUPR0301MB1953; BCL:0; PCL:0; RULEID:; SRVR:BLUPR0301MB1953;
x-forefront-prvs: 0910AAF391
x-forefront-antispam-report: SFV:NSPM; SFS:(10019020)(6009001)(377454003)(106116001)(81166005)(3280700002)(99286002)(3660700001)(10090500001)(2900100001)(2950100001)(33656002)(2501003)(5001770100001)(15975445007)(77096005)(5003600100002)(92566002)(76576001)(86362001)(19580405001)(5004730100002)(1096002)(1220700001)(4326007)(54356999)(50986999)(76176999)(122556002)(5002640100001)(86612001)(189998001)(6116002)(5008740100001)(230783001)(586003)(87936001)(10400500002)(5005710100001)(2906002)(11100500001)(551544002)(9686002)(74316001)(102836003)(10290500002)(8990500004)(19580395003)(3826002); DIR:OUT; SFP:1102; SCL:1; SRVR:BLUPR0301MB1953; H:BLUPR0301MB1953.namprd03.prod.outlook.com; FPR:; SPF:None; MLV:sfv; LANG:en;
spamdiagnosticoutput: 1:23
spamdiagnosticmetadata: NSPM
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-OriginatorOrg: microsoft.com
X-MS-Exchange-CrossTenant-originalarrivaltime: 12 Apr 2016 23:13:55.6326 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 72f988bf-86f1-41af-91ab-2d7cd011db47
X-MS-Exchange-Transport-CrossTenantHeadersStamped: BLUPR0301MB1953
Archived-At: <http://mailarchive.ietf.org/arch/msg/kitten/MgfCB__DFt04WZzlRER8JZNSkWs>
Cc: "Michael J. Jenkins" <mjjenki@tycho.ncsc.mil>, "Kelley W. Burgin" <kelley.burgin@gmail.com>
Subject: Re: [kitten] PA-ENC-TIMESTAMP is worse than we thought; fix in aes-cts-hmac-sha2?
X-BeenThere: kitten@ietf.org
X-Mailman-Version: 2.1.17
Precedence: list
List-Id: Common Authentication Technologies - Next Generation <kitten.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/kitten>, <mailto:kitten-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/kitten/>
List-Post: <mailto:kitten@ietf.org>
List-Help: <mailto:kitten-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/kitten>, <mailto:kitten-request@ietf.org?subject=subscribe>
X-List-Received-Date: Tue, 12 Apr 2016 23:13:59 -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:kitten-bounces@ietf.org] On Behalf Of Nico Williams
Sent: Tuesday, April 12, 2016 2:46 PM
To: kitten@ietf.org
Cc: Michael J. Jenkins <mjjenki@tycho.ncsc.mil>; Kelley W. Burgin <kelley.burgin@gmail.com>
Subject: [kitten] PA-ENC-TIMESTAMP is worse than we thought; fix in aes-cts-hmac-sha2?

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
-- 

_______________________________________________
Kitten mailing list
Kitten@ietf.org
https://www.ietf.org/mailman/listinfo/kitten