Re: [TLS] Data volume limits

Watson Ladd <watsonbladd@gmail.com> Wed, 16 December 2015 22:33 UTC

Return-Path: <watsonbladd@gmail.com>
X-Original-To: tls@ietfa.amsl.com
Delivered-To: tls@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 0E1DE1A903D for <tls@ietfa.amsl.com>; Wed, 16 Dec 2015 14:33:32 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.999
X-Spam-Level:
X-Spam-Status: No, score=-1.999 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, SPF_PASS=-0.001] autolearn=ham
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 vQADJmt5ZpMV for <tls@ietfa.amsl.com>; Wed, 16 Dec 2015 14:33:29 -0800 (PST)
Received: from mail-qk0-x235.google.com (mail-qk0-x235.google.com [IPv6:2607:f8b0:400d:c09::235]) (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 5FF351A9041 for <tls@ietf.org>; Wed, 16 Dec 2015 14:33:29 -0800 (PST)
Received: by mail-qk0-x235.google.com with SMTP id u65so69974821qkh.2 for <tls@ietf.org>; Wed, 16 Dec 2015 14:33:29 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=YEyKDquoKsSiCbYTjg6DDMk0KjBe04yughaVPb8XjpA=; b=yLTDmWm1yQaETPp0igYvwd1lrwTdFvC2eSYjhQL4OueQjdPPx4XfSE+QWTBVaeXTD5 TJuvRC1Pp70t8NjFW7sdEEHer/PVt++qOI/wt2EC8K2qsuslOISFuZvp/27HDgCayfWp 4QvGhmJN5Hsse3p9ElJZBCaqVQQswQhLq5Nt4ZFB5vmvNilPbfs/sD6tBjjio/TJ0Qgg nDlIX2zaiL9n9YXn7jOs73naQZYi2pUHjRdy8lxr/6bdExhusdeMWDtzMx0yA5Y6TYCA zXZBPNG9YeKWGvfr/7kDDKHrxr2top3J0TiqkxD7BKO564sLRWigQnGsRS+5OIkMPC55 ErMw==
MIME-Version: 1.0
X-Received: by 10.129.99.195 with SMTP id x186mr29275162ywb.345.1450305208525; Wed, 16 Dec 2015 14:33:28 -0800 (PST)
Received: by 10.129.148.131 with HTTP; Wed, 16 Dec 2015 14:33:28 -0800 (PST)
Received: by 10.129.148.131 with HTTP; Wed, 16 Dec 2015 14:33:28 -0800 (PST)
In-Reply-To: <CAFewVt6eaxaq0yt+cjkYkmcOuaKr7LVDnjat8Nz2M6bGUVStbQ@mail.gmail.com>
References: <CABcZeBNR76DqPo0Mukf5L2G-WBSC+RCZKhVGqBZq=tJYfEHLUg@mail.gmail.com> <87twnibx5p.fsf@latte.josefsson.org> <CABcZeBO=MQTu2t+EGBn4m2LZt_DKtY3RggF-GcM0S=jAwXeSRw@mail.gmail.com> <CAFewVt7wL9bY0S6Rm2nJMgYbN-FwkEo66JQMm9Fq5k0LDdP9xA@mail.gmail.com> <CACsn0cktrKQtaNU3=pYy-=P3Awsf+2_AqXsu4HatesBr7qRoOw@mail.gmail.com> <CAFewVt6eaxaq0yt+cjkYkmcOuaKr7LVDnjat8Nz2M6bGUVStbQ@mail.gmail.com>
Date: Wed, 16 Dec 2015 17:33:28 -0500
Message-ID: <CACsn0cnBuM=AJGNYUnuYeCYP4UcNyO18cUtWKq=-top+eRxNuw@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
To: Brian Smith <brian@briansmith.org>
Content-Type: multipart/alternative; boundary=001a114920f8c52eb805270b7e6d
Archived-At: <http://mailarchive.ietf.org/arch/msg/tls/j27Kr_-fsrqg0w6sA4UYw4QMRgg>
Cc: Simon Josefsson <simon@josefsson.org>, tls@ietf.org
Subject: Re: [TLS] Data volume limits
X-BeenThere: tls@ietf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: "This is the mailing list for the Transport Layer Security working group of the IETF." <tls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/tls>, <mailto:tls-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/tls/>
List-Post: <mailto:tls@ietf.org>
List-Help: <mailto:tls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/tls>, <mailto:tls-request@ietf.org?subject=subscribe>
X-List-Received-Date: Wed, 16 Dec 2015 22:33:32 -0000

On Dec 16, 2015 5:26 PM, "Brian Smith" <brian@briansmith.org> wrote:
>
> Watson Ladd <watsonbladd@gmail.com> wrote:
>
>> Brian Smith <brian@briansmith.org> wrote:
>> > So, if [2] is correct, then we can take Watson's 2^36 and multiply it
by
>> > 2^17 to get 2^53 bytes as the limit? It seems so, since [2] claims that
>> > they've improved the bounds by 2^17. Note that 3 out of 4 of the
authors of
>> > [2] are the same authors as [1], which is the paper that defined the
formula
>> > that the 2^36 number was calculated from.
>>
>> You need to actually read the papers and understand which formulas are
>> modified. If you did you would see the improvement is in AES-GCM with
>> funny nonce sizes, not the confidentiality issue.
>
>
> Great. Thank you for pointing out my mistake. First, I'll correct my
mistake in understanding [2]. Then, I'll verify your derivation how we can
get the "2^36 bytes" figure. Lastly, I'll ask whether the initial premise
under which we derived that number is meaningful. In particular, many
people seem to be using a limit of 2^-18 for the attackers
distinguishability advantage to allow (over) 2^48 bytes to be sent, but the
2^36 limit we derived comes from using the number 2^-60 instead. But, is
2^-60 really the right number to use? It seems like we can likely tolerate
a much higher probability of distinguishability. However, it isn't clear
what probability of distinguishability is sufficient. In other words, there
is a tension between the strictness in demanding proof of IND-* security
vs. the simplicity of the protocol (rekeying or now) for AES-GCM. I believe
it is worth asking more cryptographers for help in determining this limit.

We've already decided to add a far more complicated support for new
authentication. Reykeyinh is not that complicated.

>
> First, my mistake in understanding [2]: The improvements to [2] are for
Theorem 1 in [1], which is about AES-GCM in general, for all nonce lengths.
However, [1] also defined Corollary 3 that tightens the bound for the case
where the nonce length is 96 bits, which completely avoids the term with
factor 2^22. So, the 2^17 improvement in [2] for Theorem 1 is not relevant
because we're using Corollary 3, which is already even tighter. Sorry for
wasting people's time with that.
>
> Second, let's go back to how we got 2^36. We used Corollary 3 from [1],
which has this formula:
>
>         0.5(σ + q + 1)^2 / 2^n
>
> We rename σ to s:
>
>         0.5(s + q + 1)^2 / 2^n
>
> substitute n == 128:
>
>         0.5(s + q + 1)^2 / 2^128
>
> and simplify:
>
>         (s + q + 1)^2 / 2^127
>
> we get the formula in Watson's email [3]. In that email, Watson then
claimed that we want to keep this quantity under 2^-60:
>
>         (s + q + 1)^2 / 2^127 < 2^-60.
>
> Simplified:
>
>         (s + q + 1)^2 < 2^67.
>
> Further simplified:
>
>         s + q + 1 < 2^33.5.
>
> So, Watson's point in [3], as I understand it, is that even if we ignore
q, s must be less than 2^32. 2^32 blocks * 2^4 bytes per block = 2^36 bytes
in order to have a proof of IND-* security for AES-GCM, So we'd need to
send 2^36 or fewer bytes to have proven IND-* security.
>
> Lastly, let's reconsider Watson's claim in [3] that 1/2^60 is the correct
bound. In [0], the authors wrote: "To provide a concrete example, these
results show that, if AES is indistinguishable from a random permutation,
and fewer than 2^48 packets are protected, then the attacker’s advantage is
no more than 2^−18." This implies that David thought that 2^-18 was a
sufficient bound.

There are likely to be over 2^40 tls connections globally.

>
> Note that even the conclusion of [1] says that its bounds for the 96-bit
nonce case is tighter than the bounds from the original proof [0]. So, it
seems strange to use [1] to refute the above claim from [0], when in fact
[1] strengthens [0] for the case of 96-nonces, which is what TLS uses.

The claim may be true. But I'm saying 2^-18 is insufficient.
>
> [0] https://eprint.iacr.org/2004/193.pdf
>
>> > [1] https://eprint.iacr.org/2012/438.pdf
>> > [2] https://eprint.iacr.org/2015/214.pdf
>
>
> [3] https://www.ietf.org/mail-archive/web/tls/current/msg18240.html
>
> Cheers,
> Brian
> --
> https://briansmith.org/
>