[Date Prev][Date Next] [Thread Prev][Thread Next] [Date Index] [Thread Index]

Re: Bits from keyring-maint

On Tue, 14 Sep 2010 16:56:50 +0000 "brian m. carlson"
<sandals@crustytoothpaste.net> wrote:
> On Tue, Sep 14, 2010 at 09:59:16AM +0200, Marco d'Itri wrote:
> > On Sep 14, Gunnar Wolf <gwolf@debian.org> wrote:
> > 
> > > pushing Debian towards adopting stronger RSA keys - We have
> > > accepted some 2048R keys, but if you don't have a real reason
> > > to keep your key at that size (i.e. you very often build on
> > > underpowered machines where a 4096R key takes forever, or
> > > something like that), we really prefer to go with 4096R keys.
> > I would like to know the process which lead to selecting these
> > figures.
> I suspect that those figures are because 2048 bits is the default
> size for RSA keys and 4096 bits is the largest size that GnuPG
> supports. Some specially patched versions of PGP can support keys
> of up to 16384 bits, but IIRC those are all v3 RSA keys, which
> aren't allowed anymore.
> Personally, I can't see a reason that using an RSA 4096 bit key
> should be that painful even on very slow machines.  You're
> performing a *single RSA encrypt operation* per signature.

The selected key length seems unreasonably long to most people who
have been discussing this on the cryptography mailing list I run. In
fairness, some call it harmless, but no one has defended it as

I will remind everyone that RSA key lengths do not provide linear
increases in security -- a 2N length is not twice as hard to brute
force as an N length, but rather many orders of magnitude harder. A 2N
key is also much slower to use than a key of length N, and although
this might seem like a small cost, it is not completely ignorable. It
is also harder to generate twice as many random bits reliably, the
hash functions used to defend the signed material may no longer be
of appropriate strength, etc.

It is telling that the DNSSEC trust anchor only uses a 2048 bit key,
and is far better defended than the keys Debian is using and arguably
a far more valuable key to steal.

Generally speaking, selecting a key length requires a threat model.
One must ask how people are likely to attack the security system the
keys are defending. The keys are being stored on people's personal
computers or on media in their homes without armed guards, safes,
tamper-resistant signing hardware, etc. There are very large numbers
of these keys. The keys are being used to sign software that comes
from upstreams with a variety of security policies, many of which are
fairly poor. The weak point is thus clearly not the keys.

Given that factoring even a 1024 bit number is difficult (and a 1200
or so bit number is probably beyond the financial capabilities of any
organization I can name, including major governments) no one is going
to be attacking the system by factoring.

For a fraction of the cost of doing detailed engineering studies to
factor a 2048 bit key (not even the actual factoring) I can conduct
targeted hacking attacks, have someone spend a few months gaining the
confidence of an upstream project so they can insert a subtle bug into
their code, hire a small army of skilled burglars to break in to the
physical locations where keys are stored or even conduct a supply
chain attack or dozens of other things. 4096 goes far beyond 2048.

I'm reminded of a rumored conversation that happened after Biham
discovered attacks on the NSA's Skipjack algorithm that limited its
security to around 80 bits. It was very noticeable that the designers
of the algorithm had picked an 80 bit key length as well. Reportedly,
this was described by someone in the know as an example of proper
engineering rather than as a coincidence. The professionals don't
reinforce a cardboard bridge with steel trusses.

Rather than recommend an increase to a key size that many will find
inconvenient, I would suggest worrying more about the process that
assures that what is being signed is in fact safe, and that keys are
not being misused. Several attacks against Windows recently have
involved stolen keys (note, stolen, not cracked) and I doubt Debian's
average key is better defended. Attackers look for weak points in
systems -- defenders must do the same.

Perry E. Metzger		perry@piermont.com

Reply to: