Re: [Cfrg] matching AES security

Peter Gutmann <pgut001@cs.auckland.ac.nz> Fri, 01 August 2014 02:13 UTC

Return-Path: <pgut001@cs.auckland.ac.nz>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 23F211A037A for <cfrg@ietfa.amsl.com>; Thu, 31 Jul 2014 19:13:50 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.501
X-Spam-Level:
X-Spam-Status: No, score=-0.501 tagged_above=-999 required=5 tests=[BAYES_05=-0.5, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, RP_MATCHES_RCVD=-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 pu14ajmQLSFk for <cfrg@ietfa.amsl.com>; Thu, 31 Jul 2014 19:13:45 -0700 (PDT)
Received: from mx2.auckland.ac.nz (mx2.auckland.ac.nz [130.216.125.245]) (using TLSv1 with cipher RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id E39821A035F for <cfrg@irtf.org>; Thu, 31 Jul 2014 19:13:44 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=auckland.ac.nz; i=@auckland.ac.nz; q=dns/txt; s=uoa; t=1406859225; x=1438395225; h=from:to:subject:date:message-id: content-transfer-encoding:mime-version; bh=5UxW6Wds8jNYgf51Wb+ih4ujedMRdtEbvQRsrFqshq0=; b=uGzT1b5a1TD+kTjpgaB+EzB3Z7ZAh+Rw35uvn8hInVr960YfP8iHC1cq qaWhQG/1w2xccNUAkEb7hXlIEWKyQ1FYevgkyfHhGyStWVREMaeFicUv4 EaRUuzTobmK91v6wsn9IAv894IROaotmxK/ZSGLmeXFguNUvkC5oWsbcR I=;
X-IronPort-AV: E=Sophos;i="5.01,776,1399982400"; d="scan'208";a="266749121"
X-Ironport-HAT: MAIL-SERVERS - $RELAYED
X-Ironport-Source: 130.216.4.171 - Outgoing - Outgoing
Received: from uxchange10-fe4.uoa.auckland.ac.nz ([130.216.4.171]) by mx2-int.auckland.ac.nz with ESMTP/TLS/AES128-SHA; 01 Aug 2014 14:13:41 +1200
Received: from UXCN10-5.UoA.auckland.ac.nz ([169.254.5.247]) by uxchange10-fe4.UoA.auckland.ac.nz ([169.254.109.63]) with mapi id 14.03.0174.001; Fri, 1 Aug 2014 14:13:40 +1200
From: Peter Gutmann <pgut001@cs.auckland.ac.nz>
To: "'cfrg@irtf.org'" <cfrg@irtf.org>
Thread-Topic: [Cfrg] matching AES security
Thread-Index: Ac+tLjX2dUjMZENtSvieo4tmEFvSoQ==
Date: Fri, 1 Aug 2014 02:13:40 +0000
Message-ID: <9A043F3CF02CD34C8E74AC1594475C738EFB3D63@uxcn10-5.UoA.auckland.ac.nz>
Accept-Language: en-NZ, en-GB, en-US
Content-Language: en-NZ
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-originating-ip: [130.216.158.4]
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/JnHxF_KhlyUCnmPSw0omQh3LUfY
Subject: Re: [Cfrg] matching AES security
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Fri, 01 Aug 2014 02:13:50 -0000

Johannes Merkle <johannes.merkle@secunet.com> writes:
>The attack is very simple:
>- Gather a list of 2^N cipher texts resulting from the _same_ plain text
>encrypted under 2^N random keys.
>- For 2^(128-N) randomly chosen (different) keys, encrypt the known plain
>text and check if the resulting cipher text matches one of the gathered
>cipher texts

That attack is *conceptually* very simple, in the same way that getting humans
to Mars is conceptually very simple:

- Build a rocket capable of travelling to Mars and back.
- Board rocket and fly to Mars.

Practically, though, some of the steps are a bit tricky.

Peter.