Why I have a 512 bit PGP key

[Matt Blaze <mab@research.att.com>]

A while back, I generated a PGP key pair for use on my machine at
work, a Sun SparcStation sitting on the reasonably-well-protected-
from-outside-attack AT&T internal research network.  I selected a key
length of 512 bits.

My number theory friends tell me that this is weak by modern
standards; cracking my key would probably require within an order of
magnitude of the total computational effort expended in the recent
attack on RSA-129.  I even volunteered my key as a ``target'' for the
next such attack.  Still, I'm happy with my choice, or rather, I've
got so many other security things to worry about that compromise of my
private mail based on cryptanalysis of my dinky little public key to
obtain my private key is the last thing on my mind.  In fact, I kind
of like it that my key doesn't advertise pretensions of high
theoretical security when, in fact, there is very little at all in
practice.

The first problem, of course, is secret storage.  Modern networked
computers are awful at storing secrets.  (This, after all, is one of
the problems that crypto software like PGP aims to solve).  I suspect
my situation is reasonably typical, if not better than most.  My
computer at work sits on my desk (in my locked office), has its own
local disk, only I know the root password, I try to keep up with the
latest security patches, and I keep most of my files in encrypted form
under CFS.  I'm the only regular user of my workstation, and while I'm
at work I access it directly from the console.  The network to which
it is attached is AT&T's ``R&D Internet'', the same one that sits
behind the firewall described in Cheswick and Bellovin's great new
book.  I probably have at least average system administration and
general computer security skills, and I'm reasonably good about
practicing what I preach.  Sounds like a pretty secure machine from
which to run PGP, right?

I don't think so.  While my machine's operating system is pretty
self-sufficient, my own home directory sits on a remote file server
administered by people who are good at and have time to perform
essential services for me like taking backups.  This means that, no
matter how hard I try, it's impossible for me to be sure that none of
my files have been tampered with.  We use off-the-shelf NFS, which
means that for all practical purposes anyone with access inside the
firewall (that's about 50k people in my case) can replace any of my
files.  Furthermore, even though my office has a lock, I'm not the
only person in the world with the key (Bell Labs escrows office keys,
after all), and I've managed to pick the lock once or twice on days
when I left my key at home.  I really have no idea where my machine
has been or what software I'm typing at when I run PGP.

So where should I store my private key?  Well, I could, as some have
suggested, keep it on a floppy disk that I carry around with me
everywhere I go, but first of all, that's too inconvenient.  It also
sounds dangerous in practice.  A floppy disk is about the size of a US
passport, and I've already lost two of those.  That means I'd have to
replicate the key somehow anyway, so I might as well rely on the
reasonably well established backup procedure that protects me from
loss of the rest of the files in my home directory.  For all practical
purposes, I have to assume that my secret key file is public.

That leaves the passphrase to protect the secret key.  According to
Shannon, English text contains just over 1 bit per letter of real
information.  Even if we assume twice that to account for the added
twists and turns of phrase I'm inclined to add to a passphrase, I just
can't remember (or type) a phrase with anywhere near enough entropy to
approach the level needed to do justice to even a little 512 bit RSA
key.  I think the simplest cryptanalytic attack against me would be to
go after the passphrase-based encryption of the secret key file.
(You'd need a way to enumerate the most likely keys based on a hashed
passphrase, which is a problem not yet well studied in the
unclassified literature.  I suspect a solution not out of reach of a
determined adversary, however).

An even simpler attack would be to break in to my machine and replace
my copy of PGP (or my kernel, or my shell, or whatever) with one that
records the passphrase as I type it.  (No, I don't leave this as an
exercise to the reader!)

The next problem is with PGP itself.  While I haven't looked
carefully, it seems to be a well-engineered program, and it has a
number of design features that I admire.  However, I think the basic
model it implements sits at two high a level, making it inherently
unreliable for really sensitive traffic.  It's just too hard to use.
(Most of the problems could be fixed by pushing things to a lower
level, and I understand a number of people are working on this).  In
particular, I'm have to have too much involvement in each PGP
operation, and it's just too easy for me to do stupid things like:

	- encrypting messages with the wrong public key
	- sending the cleartext file instead of the ciphertext file
	- leaving the cleartext file around in an unprotected file
	  system
	- including the passphrase in the message (especially when
	  your fingers are so used to typing it all the time...)
	- forgetting to use PGP at all
	- typing a passphrase over a network connection (especially
	  easy when you've got several windows open on several
	  machines).  Systems that use hardware keys (smartcards, etc)
	  are less vulnerable to this

I've done each of these dumb things at least once, and probably others
too.

Don't get me wrong - I advocate the use of strong encryption as much
as the next nerd.  I'm just concerned about focusing so narrowly that
we lose sight of the larger security picture.  Perry Metzger once made
reference to cryptographic "size queens" who worry about key size and
nothing else - it's a phrase that rings true.  There's something to be
said for systems that chose their security parameters provide about
the same strength everywhere.  DES is a good example - a 128 bit key
DES could be made that is no less secure than the current 56 bit
version - by a few bits.  The engineering triumph is that the
"advertised" DES security parameter - the key size - tells close to
the truth about the overall security of the system.  (Of course, in
RSA-based systems, there's an added variable - advances in factoring -
that may make it prudent to include a significant margin for error,
especially for keys that must retain their strength over time).

I have a 1024 bit key at home.

-matt

-----BEGIN PGP PUBLIC KEY BLOCK-----
Version: 2.6.1

mQBNAitm4zgAAAECANYaL7K5Ca5B4Sq3udKKkFasQNrgfKGoWRUjwB/10lAFVrhN
aKz/b6iJXFxZ6g+YlCvdQTu/EUO6JkBihshIRgEABRG0D21hYkBiaWcuYXR0LmNv
bbQhbWF0dCBibGF6ZSA8bWFiQHJlc2VhcmNoLmF0dC5jb20+iQCVAgUQLIG7Ga1S
SlGFGX+1AQEt7QQAtwhDbN/799e763LrbhB5ItoR1r2ud+nWBZi0S64OVnVkLjnd
zVwMouPiaiEs/ORWQfoVPmME6fMYlUeh+uLonSDymjzosWyU6yJRs8lcAy2MMBR+
De00mHk8+nDAuY0j4udH2oqvd6V6IEgsN8bQeme8CkNj3uULmzNMrYtns7aJAJUC
BRAr3LtEs25wSZyVhQ8BAXQwA/wIxBaxEM/DER96N6o00qzzJog8nbKGH2S4achc
P0/96N9FXgnnoKybARfG+ZfliuuMRyt40MIkg1/Z5PzLg0m5dVzXgkYv7B98bI+8
dVuzENJRzBbbmSDemcTaF2KWdtW7U66xFSP6S86RDOuQHzg6uCi2tmoJhvdWroWz
VVxGj4kAlQIFECtzeqp9h9s63RlgUQEB8UoD/ilKx2sUFzQwkM3DSRQZun5FoR1N
ujmt710NHkn3BFcRcBAU1o6VEHg0MlQXYEDk16YnhUEZDy0QuMrxXWcLee1UP2jl
k0+ezNP5NMsSMt7HVjGJ+xi+exc6+Clyl/WjSEhpears1kBWAI12eVbO1uI/uGr5
vksZqkPoT8a1WaumiQCNAgUQK21uiULwpfyXKdSbAQFErAO/TsSmabCpT4Uzi/zQ
14yBiDqwatj8mhaE60nG8wiqQv4W4hmDXjrxGRr0LQNM3eBLCkoEpKIDmL1RuwtB
Z4AUsqoJTC2Yq46KnSznfqgY0F+C4kSptxo0p1KJ79FKFlW9dyTKVBB1WOBzbsw1
Kx/oog+DmUH0VIbYiQCVAgUQK21W3FTdX6I8ZiRnAQHErAP+P+WalKGRrgM/v8pp
o4YKYmXxjsLUx89WJXMkxkoSzB7/ny7ITHo9i42qR+aXlsa+gqxdwRDrpI6k9FFF
AhZ8s/bdZKpnXOJOjaj4P5LRbYem2VOZ8e9omXhHfz7a7NRUTimLA/q6lphy3Ulp
byrua5Q8BkzQzI3RgbKEPshuOjeJAJUCBRArZuU6hr7UV33/hTMBATvGA/42wy/x
BEVb5bOQiFTpEuB80Df53zt+b4TmfeueMMiDvvj7A5joLk7X/7x6HaBxHN/thbd6
S9NncWJfvy/PMnsQEmKarn45kwn/2xxDu2Po7pUN6Uj9DyA9uY+ilzqfk7ZA3RwH
cbZA0Qv6LDNbapJXgFANwOC1tRB6yLtSG3T0iw==
=V30c
-----END PGP PUBLIC KEY BLOCK-----