Re: [TLS] Re: Russ Housley: Fwd: problems with draft-ietf-tls-openpgp-keys-10.txt

"Steven M. Bellovin" <smb@cs.columbia.edu> Sun, 02 July 2006 01:09 UTC

Received: from [127.0.0.1] (helo=stiedprmman1.va.neustar.com) by megatron.ietf.org with esmtp (Exim 4.43) id 1FwqTB-0005wR-UQ; Sat, 01 Jul 2006 21:09:53 -0400
Received: from [10.91.34.44] (helo=ietf-mx.ietf.org) by megatron.ietf.org with esmtp (Exim 4.43) id 1FwqTB-0005wM-Be for tls@ietf.org; Sat, 01 Jul 2006 21:09:53 -0400
Received: from machshav.com ([147.28.0.16]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1FwqT8-0003S7-UU for tls@ietf.org; Sat, 01 Jul 2006 21:09:53 -0400
Received: from berkshire.machshav.com (localhost [127.0.0.1]) by machshav.com (Postfix) with ESMTP id 26B61FB2D6; Sun, 2 Jul 2006 01:09:50 +0000 (UTC)
Received: by berkshire.machshav.com (Postfix, from userid 54047) id 775333C049B; Sat, 1 Jul 2006 21:09:48 -0400 (EDT)
Date: Sat, 1 Jul 2006 21:09:48 -0400
From: "Steven M. Bellovin" <smb@cs.columbia.edu>
To: "Kyle Hamilton" <aerowolf@gmail.com>
Subject: Re: [TLS] Re: Russ Housley: Fwd: problems with draft-ietf-tls-openpgp-keys-10.txt
Message-Id: <20060701210948.e41c5c5b.smb@cs.columbia.edu>
In-Reply-To: <6b9359640607011717m38702cdbi1d451b83409168ea@mail.gmail.com>
References: <20060626203923.59F81222426@laser.networkresonance.com> <200606290020.10111.nmav@gnutls.org> <p06230904c0c9842d3069@128.89.89.106> <200607010918.21080.nmav@gnutls.org> <6b9359640607010436l4728792qdfd988762d804fe2@mail.gmail.com> <86wtaxmk7r.fsf@raman.networkresonance.com> <6b9359640607011717m38702cdbi1d451b83409168ea@mail.gmail.com>
Organization: Columbia University
X-Mailer: Sylpheed version 2.2.6 (GTK+ 2.8.19; i386--netbsdelf)
Mime-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
X-Spam-Score: 0.0 (/)
X-Scan-Signature: 7baded97d9887f7a0c7e8a33c2e3ea1b
Cc: tls@ietf.org
X-BeenThere: tls@lists.ietf.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: "This is the mailing list for the Transport Layer Security working group of the IETF." <tls.lists.ietf.org>
List-Unsubscribe: <https://www1.ietf.org/mailman/listinfo/tls>, <mailto:tls-request@lists.ietf.org?subject=unsubscribe>
List-Archive: <http://www1.ietf.org/pipermail/tls>
List-Post: <mailto:tls@lists.ietf.org>
List-Help: <mailto:tls-request@lists.ietf.org?subject=help>
List-Subscribe: <https://www1.ietf.org/mailman/listinfo/tls>, <mailto:tls-request@lists.ietf.org?subject=subscribe>
Errors-To: tls-bounces@lists.ietf.org

On Sat, 1 Jul 2006 17:17:01 -0700, "Kyle Hamilton" <aerowolf@gmail.com>;
wrote:
> 
> The largest RSA composite number ever known to be factored was 200
> digits long.  (Source:
> http://www.crypto-world.com/FactorAnnouncements.html )  This was
> announced in May 2005, and took from "shortly before Christmas 2003"
> to October 2004 (about 10 months), plus December 2004 to May 2005
> (about 6 months).  This took about 170 Pentium 1GHz CPU-years, and
> approximately (with their clusters) 80 machines working for those 16
> months.  This means that 768 bit general RSA is in sight (if Moore's
> Law continues to hold and advances in factoring mathematics continue
> unabated, it should be less than 3 years from now before a 768-bit RSA
> composite is factored).
> 
> The largest number ever factored by the special number sieve was 274
> digits long.  This is larger than 768-bit RSA, and suggests that
> 1024-bit RSA composites that are of the special form could be
> factorable at this point or in the fairly near future.
> 
> This is why I recommend exploring options other than RSA for identity
> keys.  Why do you disagree with this recommendation?
> 
The effort with GNFS is not linear in modulus length; furthermore, a lot
of memory is needed for the row reduction.  Have a look at sections 2.4
and 2.5 of RFC 3766.  Also see table 5, and note that an 8719-bit modulus
is roughly equivalent to a 200-bit symmetric key, which NSA rates as
suitable for Top Secret data.

That said, I agree that 1024-bit RSA is not suitable for protecting
long-lived secrets.  2048-bit or 3072-bit RSA seems *way* out of reach,
barring a major theoretical breakthrough in factoring algorithsm.  I won't
even engage in guessing games about when Moore's Law will break down, but
I think we can agree that transistors smaller than a single atom are,
shall we say, unlikely, and that puts an upper bound on density no matter
what we do.



		--Steven M. Bellovin, http://www.cs.columbia.edu/~smb

_______________________________________________
TLS mailing list
TLS@lists.ietf.org
https://www1.ietf.org/mailman/listinfo/tls