Re: [Cfrg] [Ext] Re: Analysis of ipcrypt?

"Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com> Fri, 23 February 2018 06:53 UTC

Return-Path: <sfluhrer@cisco.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 0CDE71243FE for <cfrg@ietfa.amsl.com>; Thu, 22 Feb 2018 22:53:31 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -14.531
X-Spam-Level:
X-Spam-Status: No, score=-14.531 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_HI=-5, RCVD_IN_MSPIKE_H3=-0.01, RCVD_IN_MSPIKE_WL=-0.01, SPF_PASS=-0.001, T_RP_MATCHES_RCVD=-0.01, USER_IN_DEF_DKIM_WL=-7.5] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=cisco.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 lNEBPnFXoco4 for <cfrg@ietfa.amsl.com>; Thu, 22 Feb 2018 22:53:29 -0800 (PST)
Received: from rcdn-iport-3.cisco.com (rcdn-iport-3.cisco.com [173.37.86.74]) (using TLSv1.2 with cipher DHE-RSA-SEED-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 9E7E9124234 for <cfrg@irtf.org>; Thu, 22 Feb 2018 22:53:29 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cisco.com; i=@cisco.com; l=2041; q=dns/txt; s=iport; t=1519368809; x=1520578409; h=from:to:cc:subject:date:message-id:references: in-reply-to:content-transfer-encoding:mime-version; bh=ZoC9EGXaS1HUspSOQG39D/i+nSxuJEgTZjaIn6REpQY=; b=hCXOnkrrOqWockuG/7Bv6ENc6hNYIoxEX7dFJ6aVROgkcgYEp4eTheBc 0E9dXIy/n3DJQvVu6a5qIw0w2lOUiGkNIPA1kHdHIfGwfjBR/YS2zE6uJ CjNJww1Mudt1+RzIYBEHjDme0r+clNGsvcCvJhB6HYBf9B4k/ZCjNbTTe 8=;
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: =?us-ascii?q?A0ApAQAWuY9a/5RdJa1cGQEBAQEBAQE?= =?us-ascii?q?BAQEBAQcBAQEBAYNPgVYoCo4DjXyCAoEWlk6CFgqFMwKCLlQYAQIBAQEBAQE?= =?us-ascii?q?CayiFIwEBAQQ6PwwEAgEIEQQBAQEeCQcyFAkIAgQBDQUIihuuToh5gh4BAQE?= =?us-ascii?q?BAQEBAQEBAQEBAQEBAQEBAQEdhRQEgieBV4Fmgy2LHQWaM4oNCQKML4lVgii?= =?us-ascii?q?GKIt9l30CERkBgTsBHzmBUXAVgn2CVByCBniLQIEZAQEB?=
X-IronPort-AV: E=Sophos;i="5.47,382,1515456000"; d="scan'208";a="349001573"
Received: from rcdn-core-12.cisco.com ([173.37.93.148]) by rcdn-iport-3.cisco.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 23 Feb 2018 06:53:28 +0000
Received: from XCH-RTP-008.cisco.com (xch-rtp-008.cisco.com [64.101.220.148]) by rcdn-core-12.cisco.com (8.14.5/8.14.5) with ESMTP id w1N6rS8i019542 (version=TLSv1/SSLv3 cipher=AES256-SHA bits=256 verify=FAIL); Fri, 23 Feb 2018 06:53:28 GMT
Received: from xch-rtp-006.cisco.com (64.101.220.146) by XCH-RTP-008.cisco.com (64.101.220.148) with Microsoft SMTP Server (TLS) id 15.0.1320.4; Fri, 23 Feb 2018 01:53:27 -0500
Received: from xch-rtp-006.cisco.com ([64.101.220.146]) by XCH-RTP-006.cisco.com ([64.101.220.146]) with mapi id 15.00.1320.000; Fri, 23 Feb 2018 01:53:27 -0500
From: "Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com>
To: Paul Hoffman <paul.hoffman@icann.org>, Greg Rose <ggr@seer-grog.net>
CC: "cfrg@irtf.org" <cfrg@irtf.org>
Thread-Topic: [Cfrg] [Ext] Re: Analysis of ipcrypt?
Thread-Index: AQHTrDvvsgPHADcpcUeI7bBEoTRfWKOxio4Q
Date: Fri, 23 Feb 2018 06:53:27 +0000
Message-ID: <c26b761a9902417f8be3e7a271a94b0f@XCH-RTP-006.cisco.com>
References: <18C83761-E442-45D9-BDBF-71DC7F751007@icann.org> <CAHmME9r3awwZxjEU-HWnOCyARhBx54VOcUOFJB4opmneKdZsyA@mail.gmail.com> <72BE956C-7D0F-41BE-88DE-C7C2063A7FED@seer-grog.net> <877er4h8n5.fsf@fifthhorseman.net> <149857F4-859F-45C8-AA6E-E1F72342B988@seer-grog.net> <A17CCC93-1AEE-47E3-B1A3-CA2791AA3AE0@icann.org>
In-Reply-To: <A17CCC93-1AEE-47E3-B1A3-CA2791AA3AE0@icann.org>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-ms-exchange-transport-fromentityheader: Hosted
x-originating-ip: [10.61.196.61]
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/ZCmNRv1I8-3Lw2-xEZRkMoKaGJY>
Subject: Re: [Cfrg] [Ext] Re: Analysis of ipcrypt?
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.22
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: Fri, 23 Feb 2018 06:53:31 -0000

I just looked at ipcrypt.

Obviously, a simple MITM attack would recover the key with 2^64 work (and a handful of known plaintexts/ciphertexts).

In addition, I believe I found a linear characteristic through the permutation; the bias is about 0.5 - 0.016.  This linear characteristic should (haven't verified) lead to something that recovers an outer round key (or, at least, places it within a 100 or so of potential values) with your 2^24 known plaintexts/ciphertexts and about 2^54 work (where 'work' is the equivalent of evaluating the cipher once).

I'm currently searching for more linear characteristics; that would drasticly improve this result.  However, even with what I have, this doesn't look good for this cipher.

> -----Original Message-----
> From: Cfrg [mailto:cfrg-bounces@irtf.org] On Behalf Of Paul Hoffman
> Sent: Thursday, February 22, 2018 7:19 PM
> To: Greg Rose <ggr@seer-grog.net>
> Cc: cfrg@irtf.org
> Subject: Re: [Cfrg] [Ext] Re: Analysis of ipcrypt?
> 
> On Feb 22, 2018, at 4:14 PM, Greg Rose <ggr@seer-grog.net> wrote:
> > Anyone who wants to do 32-bit encryption with a key longer than 80 bits
> already needs to have their threat model reviewed ;-).
> 
> OK, so please review what I said at the top of the thread:
> 
> For a project I'm on, ipcrypt is attractive if an attacker cannot derive the 128-
> bit random key without a lot (maybe 2^80ish) effort. For cases in common
> use, assume that the attacker has 2^24 known plaintext/ciphertext pairs
> under a single 128-bit random key. For additional ciphertexts, how much
> effort must the attacker expend to get the key in order to decrypt additional
> unknown ciphertexts?
> 
> The threat model then is that an attacker with 2^24 known
> plaintext/ciphertext pairs wants to determine the 128-bit random key that
> was used so that the attacker can de-anonymize addresses that are not in
> their current set.
> 
> Why is that threat model worth a smiley?
> 
> --Paul Hoffman