Quickly fill a disk with random bits (without /dev/urandom)

When an encrypted medium is prepared for use, it is best practice to fill the disk end-to-end with random bits.  If the disk is not prepared with random bits, then an attacker could see which blocks have and have not been written, simply by running a block-by-block statistical analysis:  if the average 1/0 ratio is near 50%, its probably encrypted.  It may be simpler than this for new disks, since they tend to default with all-zero’s.

This is a well-known problem, and many will encourage you to use /dev/urandom to fill the disk.  Unfortuntaly, /dev/urandom is much slower than even rotational disks, let-alone GB/sec RAID on SSD’s:

root@geekdesk:~# dd if=/dev/urandom of=/dev/null bs=1M count=100
100+0 records in
100+0 records out
104857600 bytes (105 MB) copied, 7.24238 s, 14.5 MB/s
root@geekdesk:~#

So how can we fill a block device with random bits, quickly?  The answer might be surprising:  we use /dev/zero—but write to the encrypted device.  Once the encrypted device is full, we erase the LUKS header with /dev/urandom.  The second step is of course slower, but we need only overwrite the first 1MB so it takes a fraction of a second.

Note that the password we are using (below) needn’t be remembered—in fact, you shouldn’t be able to remember it.  Use something long and random for a password, and keep it just long enough to erase the volume.  I use base64 from /dev/urandom for password generation:

# 256 random bits
dd if=/dev/urandom bs=1 count=32 | base64

Now format the volume and map it with luksOpen.  Note that we are not using a filesystem—this is all at block-layer:

root@geekdesk:~# cryptsetup luksFormat /dev/loop3
This will overwrite data on /dev/loop3 irrevocably.
Are you sure? (Type uppercase yes): YES
Enter LUKS passphrase: <random one-time-use password>
Verify passphrase:
root@geekdesk:~# cryptsetup luksOpen /dev/loop3 testdev
Enter passphrase for /dev/loop3: <same password as above>

root@geekdesk:~# dd if=/dev/zero of=/dev/mapper/testdev bs=1M
dd: writing `/dev/mapper/testdev': No space left on device
99+0 records in
98+0 records out
103804928 bytes (104 MB) copied, 1.21521 s, 85.4 MB/s

See, more than 6x faster (the disk is most likely the 85MB/s bottleneck)!  This will save hours (or days) when preparing multi-terabyte volumes.  Now remove the device mapping, and urandom the first 1MB of the underlying device:

# This line is the same as "cryptsetup luksClose testdev"
root@geekdesk:~# dmsetup remove /dev/mapper/testdev
root@geekdesk:~# dd if=/dev/urandom of=/dev/loop3 bs=512 count=2056
2056+0 records in
2056+0 records out
1052672 bytes (1.1 MB) copied, 0.0952705 s, 11.0 MB/s

Note that we overwrote the first 2056 blocks from /dev/urandom.  2056 is the default LUKS payload offset, but you can verify that you’ve overwritten the correct number of blocks using luksDump:

root@geekdesk:~# cryptsetup luksDump /dev/loop3
LUKS header information for /dev/loop3

Version:           1
Cipher name:       aes
Cipher mode:       cbc-essiv:sha256
Hash spec:         sha1
Payload offset:    2056   [...snip...]

Now your volume is prepared with random bits, and you may format it with any cryptographic block-device mechanism you prefer, safe knowing that an attacker cannot tell which blocks are empty, and which are in use (assuming the attacker has a single point-in-time copy of the block device).

I like LUKS since it is based on PKCS#11 and includes features such multiple passphrase slots and passphrase changes (it never reveals the actual device key, your passphrase unlocks the real key), but other volume encryption devices exist—or you might export the volume via iSCSI/ATAoE/FCoE and use a proprietary block-layer encryption mechanism.

If someone can explain an attack against this mechanism, I would be glad to hear about it.  In this example we used AES in CBC mode so we are spreading the IV bits across the entire volume.  Conceivably one could write an AES-CTR mode tool with a random key to do the same thing and this may be a stronger mechanism.  (To my knowledge, the dm-crypt toolchain does not have a CTR mode, nor would you want one for general use).

The method above fails when an attacker can tell the difference between the original AES-CBC wipe with random bits (where all plaintext bits are set to zero)—and the new encryption mechanism with a different key that will be used in production atop of the prepared disk volume.  While there may be an attack for AES-CBC with all-zero’s (though I don’t think there is), AES-CTR mode by its definition would make this method more effective since each block is independent of the next.  One might be able to argue that AES-CBC creates an AES-CTR mode implementation where the counter is a permutation of AES itself.  If this can be proven, then both methods are equally secure.

Either way, this is likely better (and definitely faster) than /dev/urandom for filling a disk, since /dev/urandom is a pseudo-random number generator.  Using /dev/urandom for terabytes of data may begin to develop a pattern once its effective entropy pool is spread too thin.  Even with seed-help from /dev/random, /dev/urandom might run out of steam.

In the end, random bits XORed with random bits still look like random bits when placed next to other random bits—but you’re welcome to debate this.  Yay for crypto!

ok, now back to work 🙂

-Eric

Edit: Mon Sep 17 19:43:22 PDT 2012
Come to think of it, you don’t even need a password at the luksFormat stage.  LUKS generates its own strong random bits for the actual block-cipher key.  The passphrase just unlocks that key.  For the purposes of wiping the disk with random bits, you can use “<enter><enter>” as your passphrase… just make sure you wipe the LUKS header in step 2 from /dev/urandom.

Block Device Replication with rdiff

I’ve written a few articles on rdiff-backup, and if you need an increment history to go back in time, rdiff-backup is your tool. 

But what if you just want to replicate a large block device over the Internet? Well, then we turn to the utility that inspired rdiff-backup: rdiff

For our example, we wil assume you are using LVM to create device snapshots—but really, this could be any snapshot or SAN flash implementation. I’ve just written it for Linux’s LVM.

  • /dev/remote-vg0/source will be the device we are replicating from
  • /dev/local-vg0/dest will be the device we are replicating to
  • remotehost is the system that hosts /dev/remote-vg0/source
  • This script is being executed on the destination system.
# Define our source and destination
# (Note: spaces in these paths could break the script)
SOURCE=/dev/remote-vg0/source
DEST=/dev/local-vg0/dest
SSHUSER=root@remotehost

# Choose a size large enough for the remote write-activity during
# replication
SOURCE_SNAPSHOT_SIZE=4G

# Must be the same size as $DEST, because rdiff writes in sequential
# order (it thinks the destination is an empty file, so it re-writes
# everything.)
#
# See Feb 18, 2011 update notes below.  This can be much smaller now if you 
# use the patch below, since writes are avoided unless necessary.
#DEST_SNAPSHOT_SIZE=50G

# This is probably safe with the librsync patch discussed below
DEST_SNAPSHOT_SIZE=$SOURCE_SNAPSHOT_SIZE

# Enable compression
SSHOPTS='-C'

# 32k I/O buffers, and 16k blocksize.
RDIFF_OPT='-I 32768 -O 32768 -b 16384 -s'

SOURCE_NAME=`basename "$SOURCE"`
SOURCE_SNAP="`dirname $SOURCE`/$SOURCE_NAME-snap"
SOURCE_SNAP_NAME="$SOURCE_NAME-snap"

DEST_NAME=`basename "$DEST"`
DEST_SNAP="`dirname $DEST`/$DEST_NAME-snap"
DEST_SNAP_NAME="$DEST_NAME-snap"

# remove the previous snapshots, if any
ssh $SSHOPTS "$SSHUSER" "lvremove -f '$SOURCE_SNAP'"
lvremove -f "$DEST_SNAP"

# Snapshot the remote host:
ssh $SSHOPTS "$SSHUSER" "lvcreate -s -n '$SOURCE_SNAP_NAME' -L $SOURCE_SNAPSHOT_SIZE '$SOURCE'"

# Snapshot the local destination host:
lvcreate -s -n "$DEST_SNAP_NAME" -L $DEST_SNAPSHOT_SIZE "$DEST"

rdiff $RDIFF_OPT -- signature "$DEST_SNAP" - | \
  ssh $SSHOPTS "$SSHUSER" "rdiff $RDIFF_OPT -- delta - '$SOURCE_SNAP' -" | \
  rdiff $RDIFF_OPT -- patch "$DEST_SNAP" - "$DEST"

# Compare the volumes, if you like
ssh $SSHOPTS "$SSHUSER" "md5sum '$SOURCE_SNAP'"
md5sum $DEST

# cleanup, remove the snapshots.
ssh $SSHOPTS $SSHUSER "lvremove -f '$SOURCE_SNAP'"
lvremove -f "$DEST_SNAP"

This is a convenient single-pipe process for replication, and it uses the librsync rolling-checksum process, using minimal bandwidth on the network that ssh traverses.

Executing this script yields something like this on a 50GB volume; note that the md5sum’s match perfectly.

  Logical volume "source-snap" created
  Logical volume "dest-snap" created
rdiff: signature statistics: signature[3276800 blocks, 16384 bytes per block]
rdiff: loadsig statistics: signature[3276800 blocks, 16384 bytes per block]
rdiff: delta statistics: literal[27842 cmds, 805715968 bytes, 83492 cmdbytes] copy[1462034 cmds, 52881375232 bytes, 372798 false, 10746386 cmdbytes]
rdiff: patch statistics: literal[27842 cmds, 805715968 bytes, 83492 cmdbytes] copy[1462034 cmds, 52881375232 bytes, 0 false, 10746386 cmdbytes]
7fddc578cdbf5f4e30b7f815e72acebd  /dev/local-vg0/dest
7fddc578cdbf5f4e30b7f815e72acebd  /dev/remote-vg0/source-snap
  Logical volume "source-snap" successfully removed
  Logical volume "dest-snap" successfully removed

Since rdiff does not know the destination is a snapshot of the basis-file, it rewrites the whole thing. Indeed, it could simply seek instead of copy from the basis-file, but the stock rdiff tool does not support this. If I write a patch, it will get posted here—and if you write a patch, please let me know! (see update below!)

Until then, keep double the space free in your volume group that you need to run a snapshot and it should work great!

Update: Fri Feb 18 12:39:51 PST 2011 I just wrote patch for rdiff (within the librsync package) that updates in place, by patching the file-stream-sink code in buf.c. Basically, it reads before writing. If the data read in is the same that it would have written, it skips the write and advances the write pointer; otherwise, it writes as normal. Since this avoids writing to the device that had a snapshot except where necessary, much less snapshot-backing-store is required. This code passes all of the ‘make check’ tests that come with librsync, and I believe it to be stable. On my system, rdiff syncs are about 2x faster due to the much reduced write-overhead of the original implementation.

  • The patch is here
  • and the patched code, ready to compile, is here

-Eric

Digium Multi-link PPP Support: DAHDI T1 Bonding

Getting started

I have had quite the challenge recently using Digium’s multi-port T1 cards for link bonding. The plan is to have multiple links from multiple cards go to multiple locations and provide aggregate bandwidth and fault tolerence. This means I wish to unplug any wire from any bonded link and—except for reduced bandwidth from the missing link—the network should continue to operate as if nothing happened: telephone conversations must continue and open TCP sockets must stay open.

Prior Work

I found this guide in my search for multi-link PPP, however, it was written for the Zaptel device driver, which was renamed to DAHDI due trademark issues back in 2008. This means the Zaptel documentation is at least 2 years old and DAHDI has come a long way since then.

Still, this guide is nearly sufficient to provide redundant links. The challenge one might experience in using this Zaptel guide on modern DAHDI drivers is the lack of detailed documentation. Thus, the motivation for this article.

Sangoma, a competing T1/E1/J1 card manufacturer released a modified version of pppd to manage multi-link PPP under Linux in a more reliable way. From reading the code, it appears that Sangoma modified pppd such that it will exit if it looses its multilink bundle—and uses a wrapper script, pppmon, to restart the daemon upon failure.

This is not ideal, since we would like the pppd daemon to keep the pppX interface up even if the multilink bundle drops in order to keep routes in place, as the Linux kernel will drop all routes through an interface when that interface is removed. As it turns out, this is a much more difficult challenge than it sounds.

The Case of the Missing Route

There are two complete-failure scenarios (that is, multilink-bundle-failure complete) that we would like to seamlessly recover from:

  • Both remote servers stay up, but all multipoint links drop (ie, unplug/replug).
  • One pppd daemon drops (perhaps the endpoint reboots), and the other side stays on.

The first does does not need LCP negotiation, and existing PPP state can continue upoon recovery. Simply using the pppd persist argument is sufficient here after removing Sangoma’s “exit-on-error” logic, however, this presents a challenge for the latter scenario:

If the side that remains available (ie, turned on) keeps its state, then the remote side will attempt to LCP handshake when it reboots (or re-launches pppd). Since the existing side is assuming existing state, it does gets confused by LCP request frames coming down the PPP link, and the link becomes inoperable.

Thinking, “well, why not just re-initialize the link whenever a multilink-bundle fails” I added new_phase(PHASE_INITIALIZE) at the point that the multipoint bundle is lost; this is nearly the same as re-executing pppd, but it keeps the associated pppX interface—and its associated routes—alive and kicking. This worked well when the remote-end reboots complpetely but, then, the first failure scenario of unplug/replug does not recover: The DAHDI pppd plugin attempts to re-initialize the master channel carrying the PPP link and throws “device or resource busy” errors.

The “Solution”

It turns out the easiest “fix” for this is to write a wrapper shell script around pppd with no-persist and no-fork. You can background the scripts and manage them in a hand-crafted way or perhaps a SysV script. I added the config to the end of /etc/rc.local using the “hub server” to assign IP address, allowing all of the clients to dynamically pick up IP addresses. This means any tech can plug a unit in and it will train up with the proper addressing no matter which port the T1 lines are plugged into. I also used the watchdog daemon to reboot the PPP router if it hasn’t gotten a ping response in X seconds, X*2 seconds after having booted.

This is perhaps not ideal since it drops routes when pppX is downed, but the watchdog will reboot the system if access is really lost.

Future Work

It would be great if someone were to patch the mainline pppd to support graceful recovery from the two failure scenarios listed above—without bring the pppX interface down and losing the network routes. Email me if you’re curious and I will point you in the right direction. After a few hours poking at the pppd code, this change may not be trivial since multi-link PPP apears to be a hack into pppd at the moment.

-Eric