RFC: backporting GEOM to the 4.x branch

ALeine aleine at austrosearch.net
Tue Mar 1 15:18:38 PST 2005

smb at xxxxxxxxxxxxxxx wrote: 

> I confess that I still don't see the threat model here.  What
> sort of cryptanalytic breakthrough would make this a requirement? 
> I will state categorically that I know of no threat to AES that
> would be addressed by this, but wouldn't require replacing AES entirely.
> The canonical example is "encrypting too much data with the same
> key".  That can be a real concern.  With DES or 3DES (or any other
> cipher with a 64-bit blocksize), one should never encrypt more than
> 8*2^32 bytes -- about 32G -- with a single key if you're using CBC mode.
> The corresponding figure for AES is 16*2^64 -- a *much* larger number,
> and one well beyond any conceivable disk drive.
> Historically, there have been ciphers that were attackable with
> lots of traffic, but typically the issue was repetition of the key
> stream.  
> That's not going to happen here.  I leave as an exercise for the
> reader computing just how unlikely it is -- but it's *very* unlikely.  
> Remember that we're dealing with 128-bit input blocks.
> It is, of course, conceivable that someone will find a way to use 
> hundreds of gigabytes of data encrypted with one key to find some 
> shortcut attack on AES -- perhaps 2^112 trials instead of 2^128. 
> Given the reaction in the cryptographic community to the SHA1 attack,
> which cuts the time to 2^69 from 2^80, I'm quite confident of what
> would happen: a replacement for AES.
Thank you for taking the time to write that insightful post, I have
read a number of your books and let me say it's an honour to hear
your comments on this. :-)

Regarding the threat model - imagine an attacker sending you a number
of large (> 128kb), specially crafted emails and then getting hold of
your CGD encrypted disk with those emails stored on that encrypted disk.
Let's also assume the attacker would be roughly familiar with the disk
layout on your computer and could locate the 4 Mb block on the disk
inside which his emails are located. This would make CGD an easier target
to a kind of known plaintext attack than if the emails were stored in
chunks encrypted with different keys, as that is the case with GBDE.

Algebraic attacks on AES show that AES may indeed be broken sooner than
we would hope, at least according to the information at:


In a recent paper (Asiacrypt 2002), Nicolas Courtois and Josef Pieprzyk
show that Rijndael can be written as an overdefined system of multivariate
quadratic equations (MQ). For example authors show that for 128-bit
Rijndael, the problem of recovering the secret key from one single
plaintext can be written as a system of 8000 quadratic equations with
1600 binary unknowns. Thus the security of Rijndael requires that there
are no efficient algorithms for solving such systems. In a paper published
at Eurocrypt 2000 Shamir et al. describe an algorithm called XL (or/and FXL)
able to solve efficiently many such systems of equations. Attacking
AES/Rijndael by such a method requires only a few known plaintexts to succeed.
If this method can be made to work in practice, it is a major revolution in
cryptanalysis: all classical attacks on block ciphers such as
linear/differential and other approximation attacks  require a number of
plaintexts that is very big and grows exponentially in the number of rounds.

In practice the algorithm XL fails (quite miserably) to break Rijndael.
However the system obtained from Rijndael is not random, and has many
special properties: it is overdefined, sparse and very structured. From
this, in a recent paper, Nicolas Courtois and Josef Pieprzyk investigate
how to improve XL and adapt it to such special systems. They propose a new
class of attacks, attack, called XSL attacks. 

There is no doubt that attacks such as XL and XSL do work in many
interesting cases. Unfortunately they are heuristic, and their behaviour
is not well understood. There are examples where these or similar attacks
do behave in practice as it is predicted, and there are examples where
they don't.
This is how the security of AES became a hot topic.

> That said, if you were concerned there's a very simple solution: 
> to encrypt block B with master key K, calculate some cryptographic 
> function F(K, B) -- ECB encryption is the obvious choice -- and
> use that as the block key.  Use F'(B) or F'(K, B) to get the
> per-block IV.
> Add any wrinkles you want, such as caching F and F' values, or
> having F apply to a range of blocks.

That is roughly what I had in mind.

> I see no need to rekey the disk.  I do see a need to change the 
> user-specified key, but that can be handled by a layer of
> indirection. If there were some sort of compromise that made you
> want to rekey the entire disk, having per-block keys won't help;
> you still need to read, decrypt, re-encrypt, and rewrite each block,
> since any likely  compromise scenario would involve compromise of the
> key block as well.

Agreed, the user-specified key would be used to encrypt keys for data
encryption, so only those keys would have to be rekeyed, the data itself
would remain unchanged. This would be done in a way which would not make
it possible for someone to reconstruct the master key or decrypt any other
keys, so any compromise would be very localized. The user-specified key
would naturally have to be changed regularly because it is the weakest
link in that chain.

> There's a school of cryptographic design that tosses in
> mechanisms on the vague hunch that there's threat out there.  Unless you
> understand the threats and the tradeoffs, though, you're likely to make
> matters worse, not better.  Often, there is no perfect solution, but if
> you don't understand the *real* threats you'll make the wrong tradeoffs.
> It's worth noting that there is a very real threat not addressed
> here: detecting unauthorized changes to an encrypted disk. For a very 
> elegant solution, see
> http://www.isoc.org/isoc/conferences/ndss/05/proceedings/papers/storageint.pdf

Thank you, I will definitely take a closer look, perhaps that approach
might also be used to provide faster guaranteed atomic writes in a multistep
scenario such as the one I described.

WebMail FREE http://mail.austrosearch.net 

More information about the Kernel mailing list