Re: [TLS] Data volume limits

Brian Smith <brian@briansmith.org> Wed, 16 December 2015 22:26 UTC

Return-Path: <brian@briansmith.org>
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 280EF1A9022 for <tls@ietfa.amsl.com>; Wed, 16 Dec 2015 14:26:21 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.278
X-Spam-Level:
X-Spam-Status: No, score=-1.278 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, FM_FORGED_GMAIL=0.622, HTML_MESSAGE=0.001, SPF_PASS=-0.001] autolearn=no
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 fK-n8Myeky5j for <tls@ietfa.amsl.com>; Wed, 16 Dec 2015 14:26:19 -0800 (PST)
Received: from mail-ob0-x232.google.com (mail-ob0-x232.google.com [IPv6:2607:f8b0:4003:c01::232]) (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 E3A141A900A for <tls@ietf.org>; Wed, 16 Dec 2015 14:26:18 -0800 (PST)
Received: by mail-ob0-x232.google.com with SMTP id iw8so43650513obc.1 for <tls@ietf.org>; Wed, 16 Dec 2015 14:26:18 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=briansmith-org.20150623.gappssmtp.com; s=20150623; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=jn23w2DRkZIWt/tXtyeBlpaw4xWj0ZYhYQt8Grdmgj8=; b=HbRaXFZSx2uzzCFMNnrAYgv/K2k3YooZxVn6I+2bl5uU8waT0qqM/iu3J3GBUXbHlN RmqLOOS4lYkfBDhf0TqJJhoKakU7T77LtMs2IyftHP/zuu8Ne2Ui8F6BkPDuJkMbHBhP k+ZWJITDKlsM280IfHI2IN6AFjhQ5WQl5BEZ3tEXCOveO6gORAoJFw1BbdnXRZnTV69y u4I1Ck2by2kJwM0SuHMZwBmnsnT/rbAvDegeo7ySm8MrxOylRt1BOU1vyyIFamba9VIj TUudRSnQ48t1E4Hxef8JXNtSHY6ddQPgCa4wRqeCk3F+2UE5qKBbl71vUiXPoWCVkgqZ zghQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:date :message-id:subject:from:to:cc:content-type; bh=jn23w2DRkZIWt/tXtyeBlpaw4xWj0ZYhYQt8Grdmgj8=; b=GpuOgL/uJdZqftwSI+8L4DtBlA7+jfkdCQBbBY/XP7vsP8hMQt9x71bWO4IcCiRuTO 6/4nDbtygTXQA8zzvLooccFfnTBgNzw4axlkMm29Hb7UcDGAdMVgsdMBYZoD7WoN+SkE wkMzFA6R2cOvUWXIV1YIjxJTB36Dv/L7DZvOVrPObupNjrHezCpRB1w/IH0k6aVoAjev 2lrhVopKg8JPO/Qk531N+B/S3qn1rV9tyDOkN+vOU2guCUwiwPik9ka9OA+Zvp02aBTQ g5f69NakU5cZ1ASIE1LCd+MZLRDKeRS6X5s6YAJbZCYR+YI0/KIbQyQV/bbyiep6suoX XJmw==
X-Gm-Message-State: ALoCoQlSZvZH2db9d5VXhS2aWBHQT+BCXM5kxYIMRmIwbA7SagDX+CQbm7A1VZrebTXPBuTCEkrBuGE0HSVkmF7ykT8DrkywEA==
MIME-Version: 1.0
X-Received: by 10.60.98.33 with SMTP id ef1mr34058306oeb.62.1450304778263; Wed, 16 Dec 2015 14:26:18 -0800 (PST)
Received: by 10.76.82.41 with HTTP; Wed, 16 Dec 2015 14:26:17 -0800 (PST)
In-Reply-To: <CACsn0cktrKQtaNU3=pYy-=P3Awsf+2_AqXsu4HatesBr7qRoOw@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>
Date: Wed, 16 Dec 2015 12:26:17 -1000
Message-ID: <CAFewVt6eaxaq0yt+cjkYkmcOuaKr7LVDnjat8Nz2M6bGUVStbQ@mail.gmail.com>
From: Brian Smith <brian@briansmith.org>
To: Watson Ladd <watsonbladd@gmail.com>
Content-Type: multipart/alternative; boundary=089e0115edca1ff96105270b65b6
Archived-At: <http://mailarchive.ietf.org/arch/msg/tls/8o748l0UmFxO7Ej8BLb-csyclUU>
Cc: Simon Josefsson <simon@josefsson.org>, "tls@ietf.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:26:21 -0000

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.

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.

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.

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