Re: [TLS] [Cfrg] Collision issue in ciphertexts.

"Dang, Quynh" <quynh.dang@nist.gov> Mon, 02 November 2015 20:00 UTC

Return-Path: <quynh.dang@nist.gov>
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 935831B3841; Mon, 2 Nov 2015 12:00:45 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.901
X-Spam-Level:
X-Spam-Status: No, score=-1.901 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_PASS=-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 Soscch1TwmLR; Mon, 2 Nov 2015 12:00:41 -0800 (PST)
Received: from na01-by2-obe.outbound.protection.outlook.com (mail-by2on0111.outbound.protection.outlook.com [207.46.100.111]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 765A81B37E7; Mon, 2 Nov 2015 12:00:29 -0800 (PST)
Received: from BN1PR09MB124.namprd09.prod.outlook.com (10.255.200.27) by BN1PR09MB121.namprd09.prod.outlook.com (10.255.200.145) with Microsoft SMTP Server (TLS) id 15.1.312.18; Mon, 2 Nov 2015 20:00:28 +0000
Received: from BN1PR09MB124.namprd09.prod.outlook.com ([10.255.200.27]) by BN1PR09MB124.namprd09.prod.outlook.com ([10.255.200.27]) with mapi id 15.01.0312.014; Mon, 2 Nov 2015 20:00:27 +0000
From: "Dang, Quynh" <quynh.dang@nist.gov>
To: Watson Ladd <watsonbladd@gmail.com>
Thread-Topic: [Cfrg] Collision issue in ciphertexts.
Thread-Index: AQHRFT3/uhvieo6mr0iE/9qPshn2sZ6IgieAgACWb8s=
Date: Mon, 02 Nov 2015 20:00:27 +0000
Message-ID: <BN1PR09MB124B270CE55528F10656DECF32C0@BN1PR09MB124.namprd09.prod.outlook.com>
References: <CABcZeBODjk8rapgbNTST8bmFFVzKqB4tJyrvje-CTgk1=gfqFw@mail.gmail.com> <CABkgnnV+QrjcXJdZwwAGW-SpX0Z0_JroEVT-kMJgUAVe7DDQUw@mail.gmail.com> <CABcZeBOrL=TosONYfM_QPPYfT5N4VH7yR4hFw3Qt8W4V0uznkw@mail.gmail.com> <CABkgnnXis0mwqcsd1D0S61kqL6kvq9=ZU0BRbwbLH7Jesj0Y-w@mail.gmail.com> <CABcZeBNpV3uqOF4YohiCrtq03hR7LPnPGdny6yWB+zysVufiqA@mail.gmail.com> <CABkgnnWVJeeBuMitweCj=nOSB5cA-R-6btdQeWp0Bdnomd2XtQ@mail.gmail.com> <CAMfhd9V4WVxKbJh6KkNdVFGBGKh=tG5kC_7sPthOwhrrUi5eoQ@mail.gmail.com> <CABcZeBOc_9i83j4rjxve8PuBPWdd8eCVN2wQth3G0=T_xz1UKg@mail.gmail.com> <811734cd29d64adc98c5388870611575@XCH-ALN-004.cisco.com> <CABcZeBNZJkrVsA9UEN-ywpzUOZy4wJ=2=QDg-KhjNUCvMKi=HA@mail.gmail.com> <CABcZeBNOJNwL9Akbhnpd2fg8rk80BNYRkODRpqDb9nk2K_m1mg@mail.gmail.com> <BN1PR09MB124321AF53FE4EB4F47AFE9F32C0@BN1PR09MB124.namprd09.prod.outlook.com>, <CACsn0ckVoXHvLWMwC4ksv3Rr305uL-_7UDNFT+0RnbkjDs2Vxw@mail.gmail.com>
In-Reply-To: <CACsn0ckVoXHvLWMwC4ksv3Rr305uL-_7UDNFT+0RnbkjDs2Vxw@mail.gmail.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
authentication-results: spf=none (sender IP is ) smtp.mailfrom=quynh.dang@nist.gov;
x-originating-ip: [129.6.220.229]
x-microsoft-exchange-diagnostics: 1; BN1PR09MB121; 5:OpWbHUgnlejUIJ5h5ILIkOr8mI/mu/Tcjhtac8HG2TxLCK6uaOFuWNjYQqtp5k1gXba9LTyQZJI1sYIVgVbIcV5KVLJzc+xSG922vqrtU2A1p8PYIxnC3jMCKnW1JwiAOuO8W7dt9Hnh2yWp3JkyrQ==; 24:ffEP0CCn2hmMWc52NxtIIh55Xdcp9N8CBGCW7O7N7OrQlyKXTPWWQv5RpxnDR8C8Dds3aNp+aojZpYBegCCsoXMc6RNbSJt7I3q2tP0wiWI=; 20:B+22/OkNQh4zQxTFcCYgE0a6/NxtwcolKmLHd5gWrtqwgJ+yugbQm+Mz6yYZ5kUSSYfeadPS8yKs97a42XhDIA==
x-microsoft-antispam: UriScan:;BCL:0;PCL:0;RULEID:;SRVR:BN1PR09MB121;
x-microsoft-antispam-prvs: <BN1PR09MB12189B13889A89889CD43BDF32C0@BN1PR09MB121.namprd09.prod.outlook.com>
x-exchange-antispam-report-test: UriScan:(65766998875637);
x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(601004)(2401047)(520078)(8121501046)(5005006)(10201501046)(3002001); SRVR:BN1PR09MB121; BCL:0; PCL:0; RULEID:; SRVR:BN1PR09MB121;
x-forefront-prvs: 0748FF9A04
x-forefront-antispam-report: SFV:NSPM; SFS:(10019020)(24454002)(199003)(189002)(377454003)(19580405001)(2900100001)(76576001)(5001960100002)(19627405001)(106356001)(105586002)(15975445007)(10400500002)(93886004)(122556002)(5002640100001)(110136002)(40100003)(106116001)(102836002)(189998001)(19617315012)(86362001)(5004730100002)(5001920100001)(97736004)(16236675004)(66066001)(74316001)(92566002)(33656002)(87936001)(5008740100001)(76176999)(50986999)(54356999)(77096005)(1411001)(2950100001)(19625215002)(5007970100001)(101416001)(5003600100002)(99286002)(81156007)(19580395003); DIR:OUT; SFP:1102; SCL:1; SRVR:BN1PR09MB121; H:BN1PR09MB124.namprd09.prod.outlook.com; FPR:; SPF:None; PTR:InfoNoRecords; A:1; MX:1; LANG:en;
received-spf: None (protection.outlook.com: nist.gov does not designate permitted sender hosts)
spamdiagnosticoutput: 1:23
spamdiagnosticmetadata: NSPM
Content-Type: multipart/alternative; boundary="_000_BN1PR09MB124B270CE55528F10656DECF32C0BN1PR09MB124namprd_"
MIME-Version: 1.0
X-OriginatorOrg: nist.gov
X-MS-Exchange-CrossTenant-originalarrivaltime: 02 Nov 2015 20:00:27.6787 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 2ab5d82f-d8fa-4797-a93e-054655c61dec
X-MS-Exchange-Transport-CrossTenantHeadersStamped: BN1PR09MB121
Archived-At: <http://mailarchive.ietf.org/arch/msg/tls/mZerGp6HrX2xxQ2rTVZqN1E-6sk>
Cc: "cfrg@ietf.org" <cfrg@ietf.org>, "tls@ietf.org" <tls@ietf.org>
Subject: Re: [TLS] [Cfrg] Collision issue in ciphertexts.
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: Mon, 02 Nov 2015 20:00:45 -0000

Now, you talked about a MAC function (with AES). I previously talked about encryption.


If I , the only person, uses the MAC key, when I generate more than 2^64 MAC values (Let's say each MAC value is 96 bits), I have many collided MAC pairs. But, I am the only one (beside the person(s) verifying my MACs) who knows the MAC key in order to generate those  verified MAC values.


If the MAC length is k bits, an attacker is allowed to send 2^n failed verifications, his or her chance of success is approximately 2^n / 2^k. Let's imagine n is 64 and k is 96, the success chance is 1/2^36 which is practically ZERO!


If I am an attacker, I would choose a message that I want to be verified, and I keep changing the MAC key to generate different MAC values with different keys and hope one of them will get verified.  Let's assume the MAC key to be 96 bits ( 96 bits of random bits, the other 32 bits are known). In theory, when I get close to 2^96 attempts, I would expect some chance of success. To deal with this attacker, one would change the MAC key when the number of failed attempts gets close to a number that you don't want. For example, if you don't want a success chance of an attack to be above 1 / 2^36, then you need to change your MAC key when the number of failed verifications reaches 2^64 when your MAC length is 96 bits.


After you change the MAC key, I ( the attacker) will have to start everything again because all of the failed MACs I generated before are useless now.

________________________________
From: Watson Ladd <watsonbladd@gmail.com>
Sent: Monday, November 2, 2015 5:07 AM
To: Dang, Quynh
Cc: tls@ietf.org; cfrg@ietf.org; Eric Rescorla
Subject: Re: [Cfrg] Collision issue in ciphertexts.


On Nov 2, 2015 2:14 AM, "Dang, Quynh" <quynh.dang@nist.gov<mailto:quynh.dang@nist.gov>> wrote:
>
> Hi Eric,
>
>
> As you asked the question about how many ciphertext blocks should be safe under a single key, I think it is safe to have 2^96 blocks under a given key if the IV (counter) is 96 bits.

This is wrong for PRP, right for PRF. It's not that hard to find the right result.

>
>
> When there is a collision between two ciphertext blocks when two different counter values are used , the chance of the same plaintext was used twice is 1^128.  Collisions start to happen a lot when the number of ciphertext blocks are above 2^64. However, each collision just reveals that the corresponding plaintext blocks are probably different ones.

Which breaks IND-$. Let's not be clever, but stick to ensuring proven definitions are true.

>
>
>
> Quynh.
>
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org<mailto:Cfrg@irtf.org>
> https://www.irtf.org/mailman/listinfo/cfrg
>