[Cfrg] tcpinc: session ID unlinkability

Kyle Rose <krose@krose.org> Tue, 25 October 2016 15:00 UTC

Return-Path: <krose@krose.org>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id 2842F1296B1 for <cfrg@ietfa.amsl.com>; Tue, 25 Oct 2016 08:00:07 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.7
X-Spam-Status: No, score=-2.7 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=krose.org
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id hoqTRfmRNH1z for <cfrg@ietfa.amsl.com>; Tue, 25 Oct 2016 08:00:03 -0700 (PDT)
Received: from mail-qt0-x234.google.com (mail-qt0-x234.google.com [IPv6:2607:f8b0:400d:c0d::234]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id E2EEF129591 for <cfrg@irtf.org>; Tue, 25 Oct 2016 08:00:02 -0700 (PDT)
Received: by mail-qt0-x234.google.com with SMTP id p53so4499219qtp.7 for <cfrg@irtf.org>; Tue, 25 Oct 2016 08:00:02 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=krose.org; s=google; h=mime-version:from:date:message-id:subject:to:cc; bh=m2Mut3BXpgufqbKP2CGPvtit1PMheBGSbtivQWg2Uqk=; b=ntqtB9FUWMT6S3VDNnt6AESNDc+ahy3AD38mb7KKImsnj+Ysrp7RLn45vnso/ejvTO mekA68IBHLXJUjbB8FbiVmV0DHDYIQfz00qZFWoX4ZH+f5wiyqCiACFYh4L6bC0LppvH tKF/oTDjsJ/cDZ7KrqAlT1CaYVP8kmAhXybeI=
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:from:date:message-id:subject:to:cc; bh=m2Mut3BXpgufqbKP2CGPvtit1PMheBGSbtivQWg2Uqk=; b=VDgWPTPzS3TJsPvVnIBX51h11M9OLeZ+QEeqn/ioc9rggdR0oY5tJFqPuGu2+dFsql 6vP0VQk/zP3bJ+yFdMKL/Zn2KcEE5H9CB8BKRDu6t7yOtDQ2bZhlZ9oKg/1RNeBNFUVE IXGsTd4iG1FbakASFX9x1Rhmxhj9ghIvR6KQMq+9JT7T1+DAqqposFVXL+7cU1oEExqf YcleNGAajpRQBmH6+ExQf7yEQYWQB9HlqdKwfKxCLzdzU9Wn/yQ6Ve59KrJWc/ycZHaq IrDsd4TR4OXXBUXD+XITthJdIvicUx/zy/f5Y3F2WnVmTkBYxhaRFaq8r0eBU88molRx G6kw==
X-Gm-Message-State: ABUngvc59FvGQu8TdUYUrKr+cKyb5uuseP6+zeTJvIBtPhXHb1sGn/EC7zByPpalzSQkVSatZ6tn+bcMaLQ+Sw==
X-Received: by with SMTP id s13mr20378578qta.29.1477407601748; Tue, 25 Oct 2016 08:00:01 -0700 (PDT)
MIME-Version: 1.0
Received: by with HTTP; Tue, 25 Oct 2016 08:00:01 -0700 (PDT)
X-Originating-IP: []
From: Kyle Rose <krose@krose.org>
Date: Tue, 25 Oct 2016 11:00:01 -0400
Message-ID: <CAJU8_nX=xoQ8TVpGYOikLRwwopqN=9F4POinELE0r_vaUx3q9Q@mail.gmail.com>
To: cfrg@irtf.org, tcpinc-chairs@ietf.org
Content-Type: multipart/alternative; boundary=001a1144e02c4ab6b5053fb1c343
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/j9r8yg6NMEr1eCCtgngQjB-kif8>
Subject: [Cfrg] tcpinc: session ID unlinkability
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.17
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Tue, 25 Oct 2016 15:00:07 -0000

I got some great feedback from the last question. Thanks to everyone, and
especially to Natanael, who helpfully provided a convincing argument that
uniqueness of the session ID even against adversary-as-endpoint is
sufficient for endpoint authentication (i.e., that secrecy and even
unpredictability of the session ID are not required).

Now for the second inquiry...

The TCP-ENO draft (https://tools.ietf.org/html/draft-ietf-tcpinc-tcpeno-04)

"Unless and until applications disclose information about the session ID,
all but the first byte MUST be computationally indistinguishable from
random bytes to a network eavesdropper."

I don't think this is actually the property we want. It's really okay, for
instance, if the first K>=1 bytes (for some constant K) are predictable as
long as they do not impact the security of the system (see my previous
question in the "endpoint authentication and session ID privacy" thread),
and as long as they cannot be used to violate privacy, e.g., by enabling
tracking of clients or interesting classes of clients. (In the case of
tcpcrypt, the first byte of the session ID is the ENO suboption
representing the negotiated key exchange mechanism, to ensure that
cross-protocol session ID attacks are not possible by putting session IDs
for different KEX mechanisms into disjoint spaces.)

Conversely, it's not okay for the first byte to be used to encode something
interesting about the user in the clear (e.g., user agent), because that
could be used by a passive observer to track clients.

Furthermore, as discussed in the previous question, we really do need these
session IDs to be unique even when one endpoint is an adversary.

I'm struggling with how to phrase this whole thing. So my first question
is: what property/properties do we actually want here?

Daniel Franke's draft for the NTS project has a very similar requirement,
as I noted on this thread:

q( Section 6.1.6 should list required properties of cookies; in particular,
something like "To prevent tracking of clients, a cookie issued by a server
will be repeated at most once by the client in plaintext; therefore, all
cookies issued by a server must be constructed in such a way that, even in
large numbers, they cannot be correlated to specific clients by an observer
not in possession of the keying material used to create them." Basically,
to a third-party, the cookies must be cryptographically indistinguishable
from each other with respect to the input data they represent. A
cryptographer might be able to come up with some precise language to
describe this. )


An answer here might be generally useful, maybe even to the point of a BCP
for these kinds of cookies. (Heck, there might even be one that I don't
know about.)

Furthermore, some protocols may require most of the bits to be
unpredictable, but even that's not quite right: what's really needed is
enough entropy (say, >= 256 bits) over the totality of the session ID. If
you take a 512-bit session ID and bias each bit slightly toward 0, I
imagine you've still got more than enough entropy.

So my second question is: do we need to capture this, or should we simplify
and say that each session ID should have at least 256 bits that are
computationally indistinguishable from random?