FUD about CGD and GBDE

[Poul-Henning Kamp]

In message <20050303214150.GA28836 at panix.com>, Thor Lancelot Simon writes:
>On Thu, Mar 03, 2005 at 10:15:55PM +0100, Poul-Henning Kamp wrote:
>> 
>> And if CGD is _so_ officially approved as you say, then I can not
>> for the life of me understand how it can use the same key to generate
>> the IV and perform the encryption.  At the very least two different
>> keys should have been used at the "expense" of making the masterkey
>> 512 bits instead of 256.
>
>Why "should" two different keys have been used?  It is possible that I
>misunderstand the underlying theory, but so far as I do understand it
>the only real requirement for IVs is that the Hamming distance between
>any two used with the same encryption key be large.

I have studied the AES papers and in particular the attacks and
critisisms of it very carefully, and they have proven a whole lot
of things to be impossible, but they have not proven that there
are not more that needs to be proven impossible.

When DES was designed, nobody knew that differential attacks existed.

Shortly after AES was gold-plated the earlier mentioned attack
method where it is decomposed into a massive number of equations
was presented.

Since we cannot possibly know how AES can be attacked in the future,
we have to think about how we provide the least help to _any_
potential attack.

So my approach is to regard the algorithms as black boxes, and
study the information flow and degrees of freedom involved.

Try to zoom out a bit, and think of this as a black box with wires
going into it.  I belive CGD looks like this:


   Block no---------------------> AES >-----
                                   ^        |
                                   |        |
                                   |        |
   KEY(256b) ----------------------+        |
                                   |        |
                                   |        |
                                   v        |
   DATA -----------------------> AES <------
                                   |
                                   |
                                   v
				to disk

By constraining the two AES instances to use the same key, we give
the attacker a lot less degrees of freedom to figure out.

Even worse, we may be helping him because worst case, the two uses
of the key could cancel something out in some way when two instances
of AES are hooked up this exact way.

Since the master keysize could have been 512 bits at no expense to
anybody, it only takes a minute modification to improve the diagram
above:


   KEY1(256b) ---------------------
                                   |
                                   |
                                   v
   Block no---------------------> AES >-----
                                            |
                                            |
                                            |
   KEY2(256b) ----------------------        |
                                   |        |
                                   |        |
                                   v        |
   DATA -----------------------> AES <------
                                   |
                                   |
                                   v
				to disk

Now, if there are any weakness in hooking two AES instances together,
we at least are not giving the attacker any help exploiting it, this is
what I call lack of "two-way leverage".

But there is (I belive) still a trivial mistake:  The IV generation
has totally predictable input.  Lets add another handful of bits
to the masterkey and fix that also:


   KEY1(256b) ---------------------
                                   |
                                   |
                                   v
   Block no---------------------> AES >-----
   + SALT (256b)                            |
                                            |
                                            |
                                            |
   KEY2(256b) ----------------------        |
                                   |        |
                                   |        |
                                   v        |
   DATA -----------------------> AES <------
                                   |
                                   |
                                   v
				to disk


There.  I'm not a card-carrying cryptographer, but I belive I just
improved CGD in a fairly obvious way.

I would be very surprised if anybody can show me to have done any
harm with these two modifications because all I did was to improve
how the components were hooked together and add more bits to the
input side of the whoe thing, and that can never be a bad thing,
provided those bits are generated by a competent (P)RNG of course.

I am still uncomfortable with the KEY2 being constant over all
sectors and that is why GBDE doesn't look like this.  (We can not
just derive KEY2 from the block number like we do the IV because
then we would again have given a two-way leverage to an attacker
since the block number would appear in both the key and the IV of
the lower AES.)

You will notice no doubt, that the above considerations and changes
are not in any way tied to AES.  They are valid for any encryption
algorithm you employ, also if they are two different algorithms.

It appears to me, that the people who designed CGD and the Linux
Loop-AES and similar focused very hard on the box that said "AES"
without giving much consideration to where the arrows between the
boxes went.

But again, I know nothing...

Poul-Henning

-- 
Poul-Henning Kamp       | UNIX since Zilog Zeus 3.20
phk at 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.