In message <20050302162928.0916237012@arioch.imrryr.org>, Roland Dowdeswell wri
tes:

>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.

These days, on the majority of low cost disks used in enduser
configurations you risk looking an entire track if the disk were
writing when you pulled power.  (People complain about this, but
doesn't seem to be willing to pay to avoid it.)

So the cummulative increase of risk from using GBDE doesn't really
register on the radar for people.

And therein lies a very important lesson for you:  It may not be a
100% theoretical ironclad guarantee, because few people are prepared
to pay for that in the first place.

>Contemporary filesystems generally do not lose data when a file is
>read.

... unless they operate on contemporary products for data storage.


>A dictionary attack refers specifically to the process of guessing
>passphrases.

As I said in so many words:  GBDE does not in any way shape or form
address this problem.  GBDE provides a simple model for authentication
on which many different key handing schemes, can be built.

"There is no problems left in crypto research except key-handling",
and I (or anybody else) would be very wrong if we claimed to have
the EndlÖsung for that problem.

The important feature in this situation is to be able to work with
whatever keyhandling scheme the user (or administrator) wants to
implement, not to ram our preference down their throat.

>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.

Yes, absolutely.

The difference between CGD and GBDE in this area is that for CGD
it is not convincibly shown that it is the only feasible attack
(because you use the same key for all sectors thus exposing the
ciphers possible weaknesses big time), for GBDE everybody so far
agrees that the key is the only feasible attack.

>With GBDE, the dictionary attack can be performed half offline
>because the SHA2/512 is not salted.

Sure, but if the dictionary includes guessing the 1KB of random
bits on my USB gadget, you are more than welcome to do so.

If you as a user are worried about dictionary attacks, then you
obviously will employ a key handling method which mitigates it.

My preference is a storage gadget with a large slap of bits which
are one part of the passphrase, other people have other preferences.

GBDE supports them all.

But there are also users who are rightly not worried about dictionary
attacks:  People transmitting data via CDroms in envelopes.  They
ship the bulk of thier data that way (and I mean BULK! in the case
I'm thinking about.  BofA could learn something here BTW!), but the
GBDE key is generated from a PRNG and emailed using PGP.  The entire
process is automated.

>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.

That is a non-problem which GBDE doesn't claim to address: The
vily insider is very likely to already have taken a copy of the
data he wanted.

>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.

That obviously depends on the attack method and direction.

>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.

I don't think you do.

2^128 will give you only one data sector.

Then you need 2^128 to bruteforce the key encryption.

Then you need 2^128 inverse MD5 operations, however much effort we
assign that it is not zero, it will take you at least one clock
cycle for each to store the result.

By the time you've done that, you know 16 byte values which appear
in the master key, but you do not know their indices in the master
key

There are between (256!/(256-16)!) and 256^16 (= 2^127...2^128)
different possibilities for those sixteen indices and you won't
know which it is until you know how many, if any, of those 16 values
are identical.

You may have a detection mechanism for the data sector which allows
you to stop as soon as you have a hit, but there is no detection
mechanism to let you know when you have a hit for the key encryption
(or the MD5 unless "MD5^-1" is truly found), so you will be forced
to operate with all 2^128 possibilities for the key-key, and spend
some effort on the inverse MD5 for all of those before you continue.

(MD5 may or may not add any real strengt at this point, it's there
only as a bit blender.  If MD5 adds strength, it is multiplicative
not additive, because it applies to all of the 2^128 possibilities.)

At this point you will need to find storage space for the 2^128 *
16 bytes if you want to avoid recomputations.  I belive this means
that you'll need to store 2^32 bits on every hydrogen atom in the
universe (and then some.)

Once you break the second data sector open, you can start to weed
some of the 2^128 possibilities out, but it will be a long time
before you get that down to a manageable number because only
impossible output codes from MD5 will prune it for you.

Of the 2^128 possibilities from the first sector and the 2^128
possibilities for the second data sector you broke, some, but not
all, will have shared values for some of the 16 bytes from the
masterkey.  Being identical is no guarantee that they have the same
index in the masterkey, but you can nontheless at this point start
to attack the toplevel MD5 based on that theory.  Getting
more like 10-20 sectors would improve your chances a lot but
then you need more storage space.

Attacking from the top side means breaking the 512 bytes which
protect one of the master keys.  Given that there are four of them,
I will conceeede to 508 bits of work.

If we cut that in half just on general principles of being very
very conservative, we get down to where the 256 bit version of CGD
is if we ignore the CGD's little issue with key reuse.

>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.

I'll give you the headstart that you know where the superblock is.

So you brute force the superblock. (2^128).

From that you can find the relative sector position of the inode
table (we totally ignore the uncertainty of the for keysectors
interleaving here).

Then you bruteforce the first inode block (2^128)

Then you bruteforce the first sector of the root directory (2^128)
and you are lucky and find the file right there.

You're even more lucky that the file has an inode in the same inode
sector you already handled.

And now you can start to bruteforce the data sector of the
file (of which there is only one) (2^128).

Now, you can't possibly be more lucky than this so that was
2^132 in the ultimate best case, downhill etc etc.

But let us be a bit realistic:  In case you get a false hit on the
superblock, when do you find out ?   The superblock is highly
structured, but it is not free of entropy, so this is a very
real risk.

The answer is that you will not be sure to find out until you have
broken the inode sector as well.

Well, what if that gives you false hit too ?

You get the picture.

With CGD if I suspect a hit I can just run fsck or mount it.  Fsck
may be slow when you are in a hurry, but it is a lot faster than
bruteforcing a 128 bit AES.

By the way: you keep comparing your AES256 version of CGD to
my AES128 version of GBDE, but at the same time you want me
to conceede that your 256 bit key is almost 1024 bits when
seen in the right light.

Lets us be fair and use a level ground:  Let us compare two 128 bit
version or two 256 bit versions.

Now, which algorithm is stronger ?

>If a breakthrough makes AES128 very easy to crack, then you can
>just crack the sectors individually, ignoring the rest of the
>system.

Yes, but is would be Nsect easier with CGD as the entire thing
unravels at the first sector I break.  With GBDE I have to
attack them one by one.

And since it is almost a given that any attack on AES will be
statistical in nature, GBDE is much more resistant because
there is no two-way leverage on any of the algoritms.

So, I will still claim that you get points for your key handling
and flunk on the disk encryption side.

-- 
Poul-Henning Kamp       | UNIX since Zilog Zeus 3.20
phk@FreeBSD.ORG         | TCP/IP since RFC 956
FreeBSD committer       | BSD since 4.3-tahoe    
Never attribute to malice what can adequately be explained by incompetence.