From owner-freebsd-security Thu Aug 29 16:54: 1 2002 Delivered-To: freebsd-security@freebsd.org Received: from mx1.FreeBSD.org (mx1.FreeBSD.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id A043437B400 for ; Thu, 29 Aug 2002 16:53:57 -0700 (PDT) Received: from mail-blue.research.att.com (H-135-207-30-102.research.att.com [135.207.30.102]) by mx1.FreeBSD.org (Postfix) with ESMTP id E5C8743E42 for ; Thu, 29 Aug 2002 16:53:56 -0700 (PDT) (envelope-from smb@research.att.com) Received: from postal.research.att.com (postal.research.att.com [135.207.23.30]) by mail-blue.research.att.com (Postfix) with ESMTP id 8299E4CE02; Thu, 29 Aug 2002 19:53:55 -0400 (EDT) Received: from berkshire.research.att.com (postal.research.att.com [135.207.23.30]) by postal.research.att.com (8.8.7/8.8.7) with ESMTP id TAA14847; Thu, 29 Aug 2002 19:53:53 -0400 (EDT) Received: from research.att.com (localhost [127.0.0.1]) by berkshire.research.att.com (Postfix) with ESMTP id 026E37B4C; Thu, 29 Aug 2002 19:53:52 -0400 (EDT) X-Mailer: exmh version 2.5 07/13/2001 with nmh-1.0.4 X-Exmh-Isig-CompType: repl X-Exmh-Isig-Folder: netbsd From: "Steven M. Bellovin" To: "Perry E. Metzger" Cc: freebsd-security@FreeBSD.org, tech-security@netbsd.org, misc@openbsd.org Subject: Re: Long RSA keys Mime-Version: 1.0 Content-Type: text/plain Date: Thu, 29 Aug 2002 19:53:52 -0400 Message-Id: <20020829235353.026E37B4C@berkshire.research.att.com> Sender: owner-freebsd-security@FreeBSD.ORG Precedence: bulk List-ID: List-Archive: (Web Archive) List-Help: (List Instructions) List-Subscribe: List-Unsubscribe: X-Loop: FreeBSD.org In message <8765xtzb48.fsf@snark.piermont.com>, "Perry E. Metzger" writes: > > >If you think that you have something new and exciting to tell me that >I've never heard of before, check if it has been published in Crypto >or Eurocrypt or something first. If you don't know enough to read >those conference proceedings, you don't know enough to have an >intelligent opinion on the cost of building a machine to run djb's NFS >factoring ideas. > In that vein, it's worth noting that Bernstein's results have not been embraced by the community qualified to have an opinion: the cryptographic mathematicians. (I'm not qualified -- the crypto I do is cryptographic protocol work, which is a very different beast indeed. I have a decent knowledge of the literature, which leaves me in a position of having to choose which authority I believe. But we're not dealing here with matters of opinion; my vote doesn't count for nearly as much as, say, the authors of the paper I cite below.) Let me refer folks to some people who are qualifed to have an opinion: Arjen Lenstra, Adi Shamir, Jim Tomlinson, and Eran Tromer. You can find their paper at http://www.cryptosavvy.com/meshps.gz (or .pdf); here's the abstract: Abstract. In [1], Bernstein proposed a circuit-based implementation of the matrix step of the number field sieve factorization algorithm. These circuits offer an asymptotic cost reduction under the measure construction cost × run time. We evaluate the cost of these circuits, in agreement with [1], but argue that compared to previously known methods these circuits can factor integers that are 1.17 times larger, rather than 3.01 as claimed (and even this, only under the non-standard cost measure). We also propose an improved circuit design based on a new mesh routing algorithm, and show that for factorization of 1024-bit integers the matrix step can, under an optimistic assumption about the matrix size, be completed within a day by a device that costs a few thousand dollars. We conclude that from a practical standpoint, the security of RSA relies exclusively on the hardness of the relation collection step of the number field sieve. To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-security" in the body of the message