XORLY? Losing your GPG private key safely

  • 23 January, 2008

It's quite convenient to have your GPG private key on your desktop, laptop and USB stick.. but if one of these is stolen or lost, you are pretty much obliged to issue a revocation.

Now, RAID-5 has this wonderful property whereby it is impossible to recover data from an array of size n if you have (at most) n-2 elements. So, one idea would be to create a small loopback device -based array that you can spread around your nice stealable items - you then use your key by combining >= n-1 of them.

..Or Eve must steal n-1 items before she can reconstruct your secret key. You can recover the "missing data" from single lost device, obviously.

There are almost certainly cooler algorithms for this, but none that are in the Linux kernel. Some scriptage that seems to work for me:

#!/bin/sh

set -eu

NUMITEMS=3
SIZE=30

create() {
   for NUM in $(seq $NUMITEMS);
   do
       dd if=/dev/zero of=$NUM.img bs=1M count=$(echo "$SIZE/($NUMITEMS-1)" | bc)
       losetup /dev/loop$NUM $NUM.img
   done

   sudo mdadm --create -l5 -n$NUMITEMS /dev/md0 $(seq -f "/dev/loop%g" $NUMITEMS)
   sudo mkfs.ext3 /dev/md0
}

stop() {
   sudo mdadm --stop /dev/md0

   for NUM in $(seq 1 $NUMITEMS);
   do
       sudo losetup -d /dev/loop$NUM || true
   done
}

start() {
   # Collect array elements from argv
   NUM=0
   for ELEM in $ELEMENTS;
   do
       NUM=$(( $NUM + 1 ))
       sudo losetup /dev/loop$NUM "$ELEM"
   done
   sudo mdadm --assemble --run /dev/md0 $(seq -f "/dev/loop%g" $NUM)
}

recreate() {
   # Assume already running
   dd if=/dev/zero of=$NUMITEMS.img bs=1M count=$(echo "$SIZE/($NUMITEMS-1)" | bc)
   losetup /dev/loop$NUMITEMS $NUMITEMS.img

   sudo mdadm --add /dev/md0 $NEW
   sudo mdadm --misc --wait /dev/md0
}

(This proof-of-concept script is deliberately broken: you'll have to write the argument handling yourself and convince yourself you don't have anything important at /dev/loop* or /dev/md0 or /. It might also make sense to only use the array in read-only mode, or you will have syncing issues.)

Ingenious learners may wish to construct other scenarios with other RAID levels; 5-device RAID-6 would only require 3 elements present to function (or to be stolen by Eve, naturally).

Not that I'm actually doing this: it's almost certainly as stupid as it sounds, I just haven't thought of a convincing reason yet.

Comments (11)

Evan

Cooler algorithm: <a href="http://en.wiki…" rel="nofollow">secret sharing</a>.

Jan. 23, 2008, 7:18 a.m. #

Pretty certain this won't work. Your GPG key is likely to be considerably smaller than
a block and therefore likely contained entirely on one device. While you couldn't assemble
the RAID array if you lost the device with the key on an attacker could probably find it.
XOR is only used for the parity not the data IIRC.

Jan. 23, 2008, 7:21 a.m. #
Anonymous

For another example of this, try the package "ssss", which implements Shamir's Secret Sharing Scheme. It provides, cryptographically, a system where you split a secret s into n parts and can recover the secret from any m of them. You can set m and n arbitrarily.

The basic idea behind it:

Construct a polynomial y=s + c_1 * x + c_2 * x**2 + ... + c_(m-1) * x**(m-1). Now, give out n different (x_i, y_i) pairs evaluated from this polynomial; do not give out any pair with x_i = 0, as then y_i = s. You can consider the x_i values public, and many implementations simply use x_i=i. Given any (m-1) or fewer of the (x_i, y_i) pairs, you have an infinite number of possible polynomials which pass through all of those points. However, any m of the (x_i, y_i) pairs will uniquely determine the polynomial. Once you have the polynomial, just look at its constant term for the secret (or evaluate it at zero as you compute it).

Jan. 23, 2008, 9:03 a.m. #

You could do worse than look at sss too:

http://www.deb…

Jan. 23, 2008, 9:52 a.m. #

http://etbe.co…

I think it's a bad idea.

Jan. 23, 2008, 1:20 p.m. #

That approach cannot be considered a safe way of storing a gpg key. Actually, the plain text data is distributed across all RAID 5 devices, along with a checksum. So if the thief steals the device that actually contains the key you are SOL.

The flaw in your reasoning is the assumption "impossible to recover data" where it should really say "impossible to recover ALL data".

A cryptographically secure way would be to use Shamir's Secret Sharing or an equivalent approach.

Jan. 23, 2008, 1:32 p.m. #
Simon McVittie

libgfshare gets this splitting behaviour right (on a per-byte level, and accompanied by a proof that it works), and is in Debian unstable (I maintain it).

Jan. 23, 2008, 1:33 p.m. #
Justin

What happens if the gpg key is smaller than the stripe size?

Jan. 23, 2008, 2:14 p.m. #
Euan

This is the library I told you about at the LAN: http://www.dig…

Jan. 23, 2008, 2:46 p.m. #
lamby

These comments (and other blog posts) fit into two categories.

1. Useful comments about why it's a bad idea.
2. Simply pointers to alternative solutions.

I really don't care about (2), I know how to use a search engine. Thanks to everyone who posted a (1).

Jan. 23, 2008, 6:22 p.m. #
Anonymous 8

3. None of the above

I don't see the use of posting this if you know how to us a search engine..

But to do something useful of what we have on this page, would it be possible to make a RAID-like storage solution using ssss?

Jan. 23, 2008, 11:22 p.m. #