Subject: Re: OpenSSH key size
To: Steven M. Bellovin <email@example.com>
From: Michael Richardson <firstname.lastname@example.org>
Date: 09/17/2005 16:19:07
-----BEGIN PGP SIGNED MESSAGE-----
>>>>> "Steven" == Steven M Bellovin <email@example.com> writes:
>>> John Gilmore suggested that 2048 is the wrong number. One should
>>> add ~100 to that number.
>>> The concept being, if someone builds a machine that can crack
>>> 2048-bit numbers, it won't be able to do 2049-ones. A machine
>>> that can do 2049 may well be able to 4096. So, you get the
>>> brute-force resistance of 4096 (in terms of $$$ to build)
>>> without the cost.
>>> This is not a technical argument -- it is an economic one.
>> hopefully there is some sort of technical argument to support
>> this "factoring machines only come in powers of two" idea?
>> without any more detail, it kinda sounds like "256 bit keys are
>> twice as hard to crack as 128 bit keys".
Steven> I don't believe there is any such limit. However, the cost
Steven> of these machines is *highly* non-linear in the key size.
If you have byte-wide memory, storing a 9-bit word is as costly as
storing a 16 bit word. Maybe that doesn't matter if you are building
custom silicon, down to the gate level, but design macros tend to come in
binary widths as well.
(Now, in fact, memory these days comes in multiples of 36, to
accomodate error correction)
] ON HUMILITY: to err is human. To moo, bovine. | firewalls [
] Michael Richardson, Xelerance Corporation, Ottawa, ON |net architect[
] firstname.lastname@example.org http://www.sandelman.ottawa.on.ca/mcr/ |device driver[
] panic("Just another Debian GNU/Linux using, kernel hacking, security guy"); [
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.2 (GNU/Linux)
Comment: Finger me for keys
-----END PGP SIGNATURE-----