[Botan-devel] SQLite3 encryption codec with Botan

Jack Lloyd lloyd at randombit.net
Tue Apr 14 01:31:58 EDT 2009


On Tue, Apr 14, 2009 at 10:48:51AM +0800, Mr Diggilin wrote:

> In the Bitlocker paper, they discuss AES, Bear and Lion as the only
> secure block ciphers that fulfill the requirements. They dismiss Lion
> and Bear as too slow, then they go on to see what modes would provide
> their "poor man's authentication" with AES. After all is said and done
> they settle on what they call diffusion.
> Then there's the question of XEX/XTS, which they don't discuss at all in
> the paper (didn't exist yet?).

I believe XEX/XTS were created after the Bitlocker design. There were
other modes that solve the same problem, in particular I know a mode
called OCB was published several years before Bitlocker was designed,
but OCB is patented and was probably ignored for this reason.

> Are these modes the solution to what they used diffusion for?

Short answer: Somehwat.

Longer answer: There are two basic forms for disk encryption modes.
One technique is to convert a small block cipher (like AES, which
processes 16 bytes at a time) into a larger one (for instance that
encrypts 512 bytes (== a disk sector) at a time). Modes in this style
include CMC and EME (and, if you squint a bit, Bitlocker). Because the
block is effectively the entire sector, and you need the entire
block's worth of data to decrypt properly, changing a single bit of
ciphertext corrupts the entire sector when it is decrypted.  This is
terrible in terms of reliability but good in terms of preventing an
attacker from making controlled changes to a sector. As disk
encryption operates under the constraint of not increasing the size,
it is impossible to provide a strong level of authentication, and the
best that can be done is to provide what the Bitlocker paper refers to
as poor mans auth: make it difficult for an attacker to create
ciphertexts that decrypt to semantically meaningful plaintext. This
difficult is what provides the 'authentication': if you decrypt some
data encrypted in one of these modes, and everything seems to make
sense, then (presumably) nothing was tampered with, since with
overwhelming probability anyone tampering with the ciphertext will
cause you to end up with just random junk (this is a problem if your
plaintext looks pretty much like random junk anyway, for instance x86
opcodes, but that isn't at issue here).

The other methods (like LRW and XTS) are referred to as a "narrow
block" modes - they encrypt (with AES) only 16 bytes at a time.  These
designs prevent copy and paste and dictionary attacks, but do not
provide the "pseudo-integrity" (as a IEEE 1619 draft aptly put it)
that the wide modes do. However they have the advantage of being
faster (and not patented, at least AFAIK).

> You mention that you'll probably have to add something (another cipher?)
> to Botan because Lion is too slow... but everyone seems to be saying
> that AES is the only alternative, and of course AES is in Botan. What am
> I missing here? Is AES a "length-preserving" cipher? Are there any
> others that aren't too slow?

Here AES is just acting as a standin for any reasonably fast block
cipher (eg one could just as easily use Serpent, Twofish, or MARS
rather than AES with any of these modes). For Bitlocker and the IEEE,
AES happens to be convenient for political reasons: any cryptographic
system using any cipher other than AES (or 3DES) cannot be validated
under FIPS-140, and the US government will not buy cryptographic
hardware or software that is not FIPS validated. So for commercial
developers who are in the US or who expect to sell to the US
government, AES has some major (financial, not technical)
advantages. But outside of that there is nothing special about AES for
these purposes.

As to my reference to adding new code: that would primarily be in the
form of adding one or more of the cipher modes. For my purposes, XTS
mode seems the most useful, because it solves the same problems that
LRW and XEX mode do, but in an IEEE-approved way. While I don't much
care, in and of itself, that the IEEE likes it, it does mean that XTS
mode will receive more cryptanalytic attention than competitors not
being mass deployed in commercial devices, and that it is likely to be
more widely implemented, which means prospects for interop are better.

It feels like XTS is a good choice for your SQLite codec problem as
well. The use of the tweakable cipher makes it much easier to analyze
the use, in terms of the same key potentially being reused across
databases due to the previously discussed salting limitations. If the
pseudo-integrity of a wide block mode was desired, XTS could be
combined with something like the Bitlocker diffusion layer.

Bad news: I may not have much time to look at this for a while (maybe
later this week, but if not this week, then probably not this month).
If you would like to have a try at writing XTS before I have a chance,
I did find there is an implementation in libtomcrypt 1.17. I have no
idea if it is correct, but the IEEE P1619 website lists it as a
reference implementation, which sounds promising.

-Jack



More information about the botan-devel mailing list