Saving encrypted state to disk

Introduction

Yenta needs to save its state to disk. This state has a great deal of private data in it; not only does it contain conversations that the user has had, but it also contains the user's private key. It must not ever be left unencrypted. The strategy used is to encrypt the data directly to disk, using IDEA in cipher-block-chaining (CBC) mode. It uses ePTOBs, aka encrypting Scheme port objects, which act like normal Scheme ports, but encrypt or decrypt along the way. The question then is, how does Yenta store the key so the data may be decrypted later?

What it does is to write out a small preamble, which consists of some bootstrapping data, and then the main data, which consists of the encrypted state. Both of these are written to the same file on disk.

Yenta's actual persistent state is a variable-length string of bytes, called D. [We do not compute a MAC of D; perhaps we should if we can. This would provide some protection against an attack that changes bit(s) of ciphertext (hence trashing the plaintext), but it would require somehow either precomputing a checksum, or computing one on the fly as data is written out. Both are somewhat inconvenient.]

When Yenta first starts up, it asks the user for a passphrase, P. This passphrase does not change unless the user manually changes it. Yenta immediately computes the SHA-1 hash of the passphrase, P_SHA, and throws away P.

Saving state

Each time Yenta needs to save state, it generates a new 128-bit session key, K, which is used for keying the cipher. It also generates a 64-bit verifier, V. Both of these are high-quality random numbers, drawn from the random pool. Finally, it generates an encrypted version of the session key, K_P, using the first 128 bits of P_SHA as the encryption key and IDEA as the cipher. (Since we're encrypting 128 bits of random data, we need neither any block-chaining, nor any IV.)

It then writes out the following data:

To the preamble (key) portion of the file, in the clear:
- The cleartext version of the browser cert (see below).
- The encrypted version of the session key, K_P.
To the main (data) portion of the file, encrypted on the fly (via an ePTOB keyed by K, the session key):
- Two copies of the verifier, V, one immediately after the other; we shall call this V₁V₂.
- The persistent state, D.
Because data is encrypted on the fly, before it hits the disk, what we have really written to the main data portion of the file is really [V₁V₂]_K and D_K.

Restoring state

Yenta only reads its persistent state upon startup. The first thing it must do is to read the cleartext version of the browser cert from the keyfile. It requires this data so it can establish an SSL connection to the user's browser, without generating a brand-new certificate---doing so would require that the user walk through all the cert-validation menus in the browser for every Yenta startup.

Yenta then prompts the user for the passphrase, P, and computes P_SHA, as above.

It then reads the encrypted session key, K_P, from the preamble, and decrypts it, using the first 128 bits of P_SHA as the key. This regenerates the true session key, K.

Now that K is known, Yenta continues reading, now in the encrypted portion of the file, and reads the first 128 bits from it, which should be V₁V₂---the two concatenated copies of V. If V₁ does not match V₂, then K must be incorrect. For K to be incorrect, we must have incorrectly decrypted K_P, which implies that P_SHA is wrong. The only way this could happen is if the user mistyped the passphrase, so we prompt again, and repeat.

Assuming that the verifier matches, we now have a correct session key, so we supply that to the decrypting ePTOB and read the rest of the file, which converts D_K back to D.

Vulnerablity assumptions and analysis

This does not purport to be a complete list.

Data is never left unencrypted anywhere on disk.
We assume that IDEA-CBC is secure up to brute-force keysearch. Nonetheless, we assume that we do not want to gratuitously enable a known-plaintext attack. [The ePTOB itself also includes a 64-bit IV before the encrypted data; this helps to foil known-plaintext attacks on the first block. This would otherwise be a very simple attack, since the contents of the first block are nearly constant for all Yentas.]
We assume good random numbers.
We are not secure against an attack that can read the contents of Yenta's address space. (This is true of the entire design: anyone who can read the address space can suck out P_SHA, which is kept around indefinitely. This doesn't matter, though, because such an attack could suck out the RSA keypair which defines the basis of the user's identity---this is far worse, and is basically a complete compromise, allowing both eavesdropping and spoofing.)
A weak passphrase is vulnerable to dictionary attack, which will allow decrypting the session key and thus allow access to the plaintext of the private key.
It's possible that [V₁V₂]_K could leak some information to a cryptanalyst. E.g., it's known that 4 bytes are repeated in the next block in a predictable place in the ciphertext (since we use an IV but not variable padding). This does not appear to be an actual vulnerability, since V is not known plaintext. (Hashing the second copy might help even so, or might only add a constant factor to the attack; not clear.)

It appears, as usual, that the primary vulnerabilities are (a) insecure process address space, and (b) the user picking a poor passphrase.

A note about disk-full and other lossage

Yenta tries to be relatively careful about the integrity of the saved statefile. After all, if this file is corrupted, the user's private key goes with it, and hence all of the user's identity and reputations (via attestations signed by other users) as well. This is an intolerable loss.

The most obvious defense is to write a temporary copy of the statefile, ensure that it is correct, and then atomically rename it over the old copy. This means that a crash in the middle of the write will not corrupt the existing statefile. But how do we know that the tempfile was, in fact, written correctly?

SCM does not signal any errors in any of its stream-writing functions, because it fails to check the return values of any of the underlying C calls. This means that, if the disk fills up, "write", "display", and friends will merrily attempt to fill the disk to full and bursting, and will continue dumping data overboard even after the disk is full, all without signalling any errors.

Even if we check at the beginning and the end whether the disk is full (by writing a sacrificial file and seeing if we get the bytes back when we read it), consider what happens if the disk momentarily fills in the middle of saving state, then unfills. This could easily happen if something writes a tempfile at the wrong moment. In this case, SCM will dump n bytes on the floor, then keep going. We won't have detected the failure. Even rereading the file may fail to detect it, if the dropped bytes were inside a string constant. One possible solution is to force-output after every single character, then stat the file and see if its length has incremented, or, alternatively, to write and read a sacrificial file after each character of real output. Either of these approaches is (a) extremely difficult to implement (since we write output in larger chunks, and through an encrypting stream as well), and (b) horribly inefficient, probably slowing down checkpointing by at least two orders of magnitude if not more.

To avoid this, we run a verification function over the data written, every time it is written. This function does the work of reading and checking the contents of the preamble against the running Yenta (e.g., encryption protocol version, the browser cert and browser private key, etc), and then computes the SHA-1 hash of the entire encrypted portion of the file, e.g., of the data portion in the discussion above. This is then compared with an identical hash, computed seconds earlier when the data was written to disk. If anything is wrong with the preamble or if the hashes do not match, then something is wrong with the data we just wrote; a single byte missing or even a single bit trashed will be evident.

In this case, we do not rename our obviously-corrupt tempfile over the last successfully-saved statefile. Instead, we delete it again, since it may be contributing to a disk-full condition and is bad in any event. In addition, we set a variable so the user interface knows that something is wrong, and can tell the user, who can presumably attempt to fix whatever is preventing us from successfully writing the statefile.

Note that this gives us no protection over having the statefile trashed after we have checkpointed. If Yenta is still running, the damage will be undone at the next checkpoint, since the old file will simply be thrown away unread. However, if Yenta was not running when the file was trashed, Yenta will simply fail to be able to correctly read the entire thing. (Chances are overwhelming that any corruption of the file will yield garbage after decryption that "read" will complain about, and Yenta will be unable to finish loading its variables.) In this case, the user will have no choice but to restore the file from backup. This is the expected case anyway if files are being trashed at random in the filesystem.

Note also that Yenta's support applications, which write plaintext statefiles and do not save state using encryption, do not do this checking. They save very little irrecoverable state in normal operation; the big exception is the statistics logger, which will simply have its data truncated, losing log entries that arrive while the disk is full and possibly leaving a corrupted last entry. This is not considered a serious problem. Furthermore, this state is not being saved in a statefile at all, but is being explicitly written to a a separate logfile.

Lenny Foner

Last modified: Thu Apr 29 16:22:27 EDT 1999