Subject: Re: FUD about CGD and GBDE
To: Poul-Henning Kamp <>
From: Roland Dowdeswell <>
List: tech-security
Date: 03/02/2005 11:29:28
On 1109758470 seconds since the Beginning of the UNIX epoch
Poul-Henning Kamp wrote:

>So how about it guys:  Instead of spreading FUD, lets work together
>and make the world an even better place ?

I am hoping that the discussion will yield infomation that will
allow each of us to improve our respective systems.

I shall respond to the points out of order.

>All the talk about what happens during a powerfail/crash is rather
>uninformed:  On any contemporary filesystem you will loose data,
>encrypted or not, if the system crashes before you have a zero
>return value from fsync(2).   If fsync(2) completed successfully,
>your data is safe on the disk, both with GBDE and CGD.  Adding
>journaling or before/after images to the disk encryption is totally
>the wrong way to address this problem since all your filesystems
>and disk device drivers suffer from the same issue.

Let's discuss a simple example and see how it works.  Let's walk
through a user login, with /etc/passwd on GBDE and the filesystem
mounted with mtime.


	1.  A user logs in, /etc/passwd is consulted,
	2.  mtime of /etc/passwd is updated,
	3.  the file system over GBDE at some point decides to
	    rewrite /etc/passwd's inode,
	4.  a new key is randomly generated for the inode sector,
	5.  the key-key sector is regenerated and written, and
	6.  the newly encrypted inode sector is written.

Now, if the power is cut or the operating system crashes between
steps 5 and 6, you have now lost the inode for /etc/passwd (and a
few more files).

Contemporary filesystems generally do not lose data when a file is
read.  But, unless there is some logic under GBDE or in FFS which
I have failed to see, this is possible with FFS over GBDE.

This has nothing to do with the semantics that fsync(2) guarantees.
It is a matter of the atomicity assumptions that the filesystem
expects a disk (or pseudo disk) to provide, and as I stated earlier
the requirement is that if the sector contains A and I try to write
A' then after a crash the sector will contain either A or A' but
not A''---the decryption of A with the A' key.

Now, what about GBDE or FFS makes this situation impossible?

>With respect to the dictionary attack.  The _real_ key of GBDE is
>either 512 bits (changeable, for each of the four keys) or 2176
>bits static, depending on where you decide to attack.  I have not
>heard of any realistic dictionary attacks of that size, mostly due
>to shortage of atoms in the universe.
>Now, currently the 512 bits are derived by running whatever the
>user provides through SHA2, and if the user provides "password",
>then a dictionary attack is indeed very feasible.
>That, however, is not a problem in GBDE, that is a problem in
>the users key-handling.

A dictionary attack refers specifically to the process of guessing
passphrases.  It is not a generic brute force attack on the whole
key space, and it uses the fact that passphrases have substantially
weaker security properties than random bags of bits.  Under the
assumption that my USB dongle is generally an average of 20 feet
from my laptop (because I take both of them with me most places),
I normally have to assume that the 2-factor authentication that I
use will help but the system _must_ be secure in the face of
compromise of both the dongle and the laptop.

With that in mind, the attacker will simply guess passphrases using
reasonably well known and reasonably effective techniques of
generating the kinds of passphrases that people use.  Given that
the human memory is not expanding at nearly the same rate as computer
processing power, something needs to be done about this vector.

It is all well and good for both of us to talk about 2^256 and
2^2176 and 2^128 * 2^30, etc.  But, a dictionary attack is likely
to be a lot closer to 2^35 or 2^40.  This is, I think, in the
general use case the real threat.  It is the low hanging fruit.

With GBDE, the dictionary attack can be performed half offline
because the SHA2/512 is not salted.  And, after you get to the
online portion, it basically comes down to a simple AES setkey and
encrypt to verify whether the passphrase is valid.  My laptop can
perform abut 100k of these operations per second (if it is plugged
into the wall) and it is not exactly a fast computer.  That means
that I can run through about 2^30 guesses in 2.5 hours.  This will
obtain naive user's passphrases within the first few days.  More
savvy users may take a bit longer, but it is all within the realm
of the very possible without any advances in cryptography---unlike
cracking CGD' AES256 or GEOM's AES128 on the sectors.

>The claim that CGD can change the passphrase without reencrypting
>they entire disk falls flat on its face:  One cannot seriously claim
>to have changed the passphrase if the 256 bit key used for the
>entire disk remains constant.  The static master key needs to be
>at least 1024 bits to satisfy the contemporary security policies I
>have been given access to.

Actually, given your statements the claim does not fall flat on
its face.  It just does not meet the requirement that the key is
at least 1024 bits.  Those appear to me to be different statements.

GBDE does not actually change its salt/master key when the passphrase
is changed, so the systems are equivalent from the perspective of
how they change passphrases.  The only exception is that GBDE has
a longer key.

With GBDE the keys used to encrypt each of the key-key sectors
remain static.  So, like CGD there is no effective way to revoke
access to the disk from wily and intelligent insiders who at some
point had access to the disk, except by re-encrypting the whole
thing.  With both systems, the `master key' remains static and
hence if you can calculate it once you have it.

While we are at it, I do not believe that having a key that is
larger than 1024 bits necessarily guarantees that the effort required
to crack it is commensurate with its size.  E.g. given the bit-blender
approach of GBDE [from 7.4 of your paper], if you know the salt
then you can use a divide-and-conquer strategy to tease the master
key out in a ``reasonably short'' time.  Less than 2^128 steps
certainly, if I look at things correctly.  Which means that if you
do not have the salt then to brute force both you need to put in
an effort equivalent to less than 2^128 * 2^128 = 2^256.  Which
seems to me to indicate that there is less than 2^256 of `effective'
key material.

>If an attacker decides to attack a GBDE encrypted disk by brute-forcing
>all the sectors he might have a theoretically very simple task of
>on average 2^128 * Nsect work.
>Right now 2^128 is considered a safe workload for brute force, but
>that is assuming that the algorithms stand up to analytical attack.
>But the devil is in the detail, and the detail in this case is
>knowing that you had a hit.
>The biggest problem in brute-force attacks is very often to _know_
>that you had a hit.  The actual crypto operations can be put in
>silicon, but the practical hit-recognition is usually too complex
>for hardware.
>A brute force attack will produce 2^128 possible sector contents
>and the attacker has no way of _knowing_ that he found the right
>contents until he has checked if the hit is consistent with the
>rest of his hits and the GBDE key schedule.

Knowing that you had a hit is substantially easier than you claim.
Filesystems are quite well structured and attackers are generally
looking for specific information which is quite well structured.

So, if I were attacking GBDE, what I would do would be to look for
the superblock which is ~trivial to recognise and then walk down
the directory chain until I found the files/directories that I
want.  Again, most of this is quite recognisable.  Eventually, I
would get to the file(s) that I wanted to see.  These are probably
reasonably well structured as well.  Now, I would be trying to
crack key-key sectors, so I can correlate 32 different sectors at
a time---so I think that there's a very good chance that I would
have enough information at hand to verify the results in a programatic

>The claim that:
>	"It is also structured in such a way that substantial
>	breakthroughs in the cracking of many different encryption
>	algorithms, hashes and random number generators will bring
>	the house of cards down."
>Sounds very interesting and I am very
>much looking forward to, but not
>seriously expecting ever to, read a
>substantiation of this claim.  (Notice
>that I made the margin wider here to
>make sure they don't run out of space

If a breakthrough makes AES128 very easy to crack, then you can
just crack the sectors individually, ignoring the rest of the
system.  If the results of Yarrow are found to be predictable, then
guessing the sector keys becomes much easier.  So, there are two
algorithms that will individually make cracking the disk substantially
easier independently.  If md5 is found to have predictable output
then guessing the key for the key-key sectors becomes easier.
Depending on how the predictabity manifests itself it could make
a crack a lot easier.

    Roland Dowdeswell                      http://www.Imrryr.ORG/~elric/