Persistent keylist with secure deletion

Note: This is a copy of a sci.crypt post.  Python code to implement
the below is at:

   http://www.nightsong.com/phr/crypto/keytree.py

Suppose you want to store N encrypted files, numbered 0, ..., N-1.
You want to be able to access any or all of them with a single
passphrase.  You also want to be able to delete any file securely, so
it can't be recovered.  However, all the sci.crypt posts about secure
deletion have convinced you that once you write something to a disk
drive, it can never be erased: for example, it can be recovered with
fancy magnetometers, or maybe the drive itself might decide to
relocate sectors from the file from one place to another without
telling you.

OK, you encrypt each file with its own random key, K0,...,K_(N-1), and
encrypt each key with the passphrase.  Then if you can securely delete
a key, the file can't be recovered.  But now storing the keys to disk
has the same problem as storing the files to disk.  If analyzing the
disk reveals every state it's ever been in, and there's no other
persistent data store in your computer, there's no solution.

Of course you've set up your system so that RAM contents are never
paged to disk, so you can hold secret keys in system RAM, but that's
only for temporary operations since a system crash wipes out the
regular RAM.  But there are other places to squirrel away data.  PC's
have a few dozen bytes of CMOS memory (usually 32 or 64 bytes) which
hold stuff like the real-time clock (10 bytes) and the HD parameters
(sometimes not needed any more).  Or devices like the Dallas DS1991
and DS1992 iButtons,

  http://www.ibutton.com/ibuttons/memory.html

connect to the computer's serial port and hold some data (1-64 kbits)
in internal NVRAM.  The DS1992 even has a password protection feature,
so it can become an authentication token as well as a key store.
Unlike the Java iButton, though, they aren't crypto devices and don't
have fancy firmware.  So you can buy them without dealing with export
restrictions or obnoxious vendor licenses.  Also, they're much cheaper
than the Java iButton.

But what about those N keys, that won't fit in the NVRAM?  Suppose you
can fit just one key in NVRAM.  That turns out to be enough--here's
a simple but workable approach:

Generate a random key R and store it in NVRAM.  Use R to encrypt your
list of N keys and write the encrypted list to disk.  To delete a key
K_i, read R from the NVRAM, then generate a new random key R' and
store that in NVRAM, overwriting R.  Use the old R to decrypt the
list, and use R' to write a new encrypted list omitting K_i (write
random data in K_i's slot).  Since R is permanently gone, the file
can't be read.

The trouble with the above scheme is that if you have N slots, it
takes O(N) operations to read and write the file.  So that's slow if N
is large.

The solution is to use a tree structure: store a "root key" in NVRAM.
Use it to encrypt a key on disk.  Use that key to encrypt two more
keys, and each of those to encrypt two more keys, etc.  The keys are
in a binary tree where each node has an encryption key E and a user
key V.  V is encrypted by E, E is encrypted by the node's parent's E,
and so on up to the root.  To delete a V, you simply change the E for
that node, and its parent, etc.  You have to remember to re-encrypt
the node's sibling's V, and the node's children's V's if the node has
any children.  Still this is a total of O(log N) operations, which
is ok for reasonable values of N.

A sample implementation in Python is at:

   http://www.nightsong.com/phr/crypto/keytree.py

which also includes an AES-like block cipher (128 bit blocks) written
in Python (actually just a Luby-Rackoff construction using SHA as the
round function).  It uses the Linux /dev/urandom device for getting
random keys and it uses the mmap system call to operate on the disk
file efficiently, so it would take some modification to port to
Windows.  For now, it doesn't attempt to use any physical NVRAM.
There's testing code that simulates NVRAM with a disk file, though of
course that defeats the security of the whole scheme.  The code
also lets you root a keytree as a slot in another keytree, meaning
you can operate multiple trees with just one NVRAM slot.

Besides real NVRAM, making this thing useful needs some kind of
database-like transaction scheme to improve reliability (if the
current version crashes in the middle of an update, your keys can all
be lost) and some kind of backup scheme (probably some kind of online
synchronization of the tree with another tree on a remote computer).

This was written mostly as an exercise but I tried to make it fast and
solid enough to use for a real database if I feel paranoid enough to
need it.  Comments and suggestions types are welcome.