Re: [Cfrg] 1024 bit RSA

Peter Gutmann <pgut001@cs.auckland.ac.nz> Sat, 05 November 2016 03:51 UTC

Return-Path: <pgut001@cs.auckland.ac.nz>
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 670321296EA for <cfrg@ietfa.amsl.com>; Fri, 4 Nov 2016 20:51:26 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -5.696
X-Spam-Level:
X-Spam-Status: No, score=-5.696 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, LOTS_OF_MONEY=0.001, RCVD_IN_DNSWL_MED=-2.3, RP_MATCHES_RCVD=-1.497] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=auckland.ac.nz
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 x-ds10BYCxPd for <cfrg@ietfa.amsl.com>; Fri, 4 Nov 2016 20:51:22 -0700 (PDT)
Received: from mx4.auckland.ac.nz (mx4.auckland.ac.nz [130.216.125.248]) (using TLSv1.2 with cipher RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id A9C39129585 for <cfrg@irtf.org>; Fri, 4 Nov 2016 20:51:21 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=auckland.ac.nz; i=@auckland.ac.nz; q=dns/txt; s=mail; t=1478317881; x=1509853881; h=from:to:cc:subject:date:message-id:references: in-reply-to:content-transfer-encoding:mime-version; bh=YaUgDID0KgRS46swGPGurnLZ69OeQ1yNbviw9lH7OQU=; b=4PhorScbUVh7oZ6eUxidofjL6Jp1yWitGIi+ezaD/MYmJ+r9mN0gpD47 xgdnFprOYT2FKp53R6UUp7Zn5Kd7idQkeN+BUdvQW5bPlggwPNEpFcCUZ QWcKNj52DiPj2HrQw7zWTwLIQrpgLKquGzgfWtAz0DrCtpUFLKRisJw8K YHbheXSEuuu3TWobucm8pxl3llqsOM5h8JJtJUKDplOP6i8VdhTW0hjd9 Fu5jkxb15Vj2S4TW7SrsAZHBrgy2LWo6ZV7MYb0y95GWMvwaAGFNvZLJx genUFcXNb+xQEcESXpvIpgyxJJaZlPrSZ5/Vrf2YJZayqopIBcO0h9L1s w==;
X-IronPort-AV: E=Sophos;i="5.31,446,1473076800"; d="scan'208";a="113655512"
X-Ironport-HAT: MAIL-SERVERS - $RELAYED
X-Ironport-Source: 10.6.3.3 - Outgoing - Outgoing
Received: from smtp.uoa.auckland.ac.nz (HELO uxcn13-tdc-b.UoA.auckland.ac.nz) ([10.6.3.3]) by mx4-int.auckland.ac.nz with ESMTP/TLS/AES256-SHA; 05 Nov 2016 16:51:16 +1300
Received: from uxcn13-ogg-d.UoA.auckland.ac.nz (10.6.2.5) by uxcn13-tdc-b.UoA.auckland.ac.nz (10.6.3.23) with Microsoft SMTP Server (TLS) id 15.0.1178.4; Sat, 5 Nov 2016 16:51:16 +1300
Received: from uxcn13-ogg-d.UoA.auckland.ac.nz ([10.6.2.25]) by uxcn13-ogg-d.UoA.auckland.ac.nz ([10.6.2.25]) with mapi id 15.00.1178.000; Sat, 5 Nov 2016 16:51:16 +1300
From: Peter Gutmann <pgut001@cs.auckland.ac.nz>
To: Ilari Liusvaara <ilariliusvaara@welho.com>, Hal Murray <hmurray@megapathdsl.net>
Thread-Topic: [Cfrg] 1024 bit RSA
Thread-Index: AQHSNt7aNTqSoFCyQtexI2PQtTMFhKDIe8oAgAFET/s=
Date: Sat, 5 Nov 2016 03:51:16 +0000
Message-ID: <1478317865966.12431@cs.auckland.ac.nz>
References: <20161104210313.4C668406061@ip-64-139-1-69.sjc.megapath.net>, <20161104212348.GA20439@LK-Perkele-V2.elisa-laajakaista.fi>
In-Reply-To: <20161104212348.GA20439@LK-Perkele-V2.elisa-laajakaista.fi>
Accept-Language: en-NZ, en-GB, en-US
Content-Language: en-NZ
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-ms-exchange-transport-fromentityheader: Hosted
x-originating-ip: [130.216.158.4]
Content-Type: text/plain; charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/ZB9TPhJFYzrtgyhdWeXF1ynWvK4>
Cc: Cfrg <cfrg@irtf.org>
Subject: Re: [Cfrg] 1024 bit RSA
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.17
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: Sat, 05 Nov 2016 03:51:26 -0000

Ilari Liusvaara <ilariliusvaara@welho.com> writes:

>In summary, I would guess that factoring RSA 1024 keys would be within reach
>of groups who could do ASIC design and then ordering custom chips off fabs.
>Of course, that's still many millions, so one would need the financial case
>of spending that much money (it is going to be millions of dollars at the
>very least).

And that's the key point, would anyone bother?  There's always the
hypothetical government-level attacker with magical access to infinite
resources lurking in the shadows, but as Snowden has shown, they don't need to
spend that much to get in, or build crypto-breakers to do it.  If I was an NSA
program manager and someone came to me and said "we need $100M to build an
ASIC-based RSA cracker, which we should have tested, debugged, and operational
in two years", I'd reply "here's a full *one hundredth* of that amount, you've
got a week to get in by backdooring or subverting or bribing or whatever"
(with an optional side-order of "yer lazy bastard" in an Ernest Borgnine
accent).

Even if there was absolutely no other way in, I can't see how you could
justify building something like that unless you were using it to attack
something of extraordinarily high value like the single RSA-1024 key that the
Kremlin uses to communicate with all its local offices.  DH group 2 (group 1
in SSH terminology), sure (although an RSA-breaker can't do anything with
those anyway), but some random RSA key somewhere?

Peter.