backing up keys

[Peter Lebbing]

On 17/11/15 15:53, Andrew Gallagher wrote:
> No, there is no public key data embedded in the private key, but you can
> regenerate the important mathematical bits of the public key from the
> private key, and you can fill in your name, email etc. from memory. So
> it's not absolutely necessary - but it is convenient.

Let's look at this at three levels:

1) What GnuPG actually does when you invoke --export-secret-key

GnuPG outputs both a "Secret-Key Packet" as well as all UID's and
binding signatures. It might output all certifications by others on the
key as well; I'm going to write a separate mail about this.

2) What is in a "Secret-Key Packet"

> 5.5.1.3.  Secret-Key Packet (Tag 5)
> 
>    A Secret-Key packet contains all the information that is found in a
>    Public-Key packet, including the public-key material, but also
>    includes the secret-key material after all the public-key fields.

3) What you can do with just the RSA elements p, q, e, and optionally d
and u.

You could create a key that allows you to decrypt your encrypted data,
although you might have to jump through some hoops regarding the
fingerprint.

To be able to recreate a key with the same fingerprint, you additionally
need to know when you created your key down to the very second. This
means that even if you can reproduce your UID from memory perfectly, any
signatures you issue will not be recognised by your peers and all
certifications on your UID are lost unless you have memorised the very
second the key was created.

All in all, I wonder: did someone tell you you could recreate your
public key using just the secret parts? Have you tried it yourself? As
far as decryption goes, I might agree, but when you say

> you can fill in your name, email etc. from memory

I think you're talking about regaining certifications from others, and
for that you really do need the creation timestamp down to the second.

> Brute forcing a password is always easier than brute forcing the key
> itself (otherwise you'd be typing in your entire private key by hand!),

This is an oversimplification. A symmetric key has no structure; it is
just data. RSA, on the other hand, has specific mathematical properties.
The numbers p and q are primes, which are spaced rather far apart on the
number line; all numbers in between would make valid symmetric keys, but
not valid primes for RSA. As a consequence, the information content in
the number is lower. In practice, OpenPGP private keys also include the
numbers d and u, which in fact can be computed from p and q (given e,
which is usually a constant), so hold no additional information content
at all.

It is claimed (though not universally) a 2048-bit RSA key is about as
strong as a 112-bit symmetric key. If we take this to be the truth, then
remembering a cryptographically random 19-character base64 string and
using it as a password for your secret key would balance the relative
strengths, and brute forcing the "passphrase" is just as hard as
brute-forcing the public key to reveal the secret key. 112 bits is a
full order of magnitude smaller than 2048 bits; there is no need to put
a passphrase with 2048 bits of randomness on your key to balance it out.

>> The gpg documentation[1] seems to indicate that paperkey works
>> better at backing up to paper. Is there some reason why?

An OpenPGP Secret Key Packet is identical to the public key packet, but
with the secret material appended to it. Paperkey just stores this
appendage, and uses the public key to reconstruct the secret key from
it. So when you print out the result of --export-secret-key, most of
what you are printing is actually the same stuff that is in the public
key, and you can just store the public key anywhere without stringent
security requirements; in fact, it's often available on the keyserver
network. Paperkey just stores the non-redundant bit, which is much smaller.

> That's fine if your OCR is perfect and your paper never gets folded or
> stained or torn, but ascii-armored data has no checksum or error
> correction so you may suddenly discover your paper backup is unusable.

There certainly is checksum data in OpenPGP packets, and the fact that
your key doesn't work is a checksum in and of itself. There is no error
correction, other than that it is mathematically possible to reconstruct
a prime from a slightly corrupted copy, and furthermore that the numbers
d and u can be recomputed when p and q are still intact, and that p can
be computed from the public key when q is intact, and vice versa. So
basically, all you need is either p or q to be intact. I'm not now going
to spend time thinking about whether u or d is actually enough already.

HTH,

Peter.

-- 
I use the GNU Privacy Guard (GnuPG) in combination with Enigmail.
You can send me encrypted mail if you want some privacy.
My key is available at <http://digitalbrains.com/2012/openpgp-key-peter>