Re: Wide-block Encryption Alternative
My main criticism of that proposal is its performance characteristics,
not so much the security. Indeed, both Phil and myself started out
trying to design a mode similar to your suggestion, and only when we
couldn't find something that we liked we started working on CMC, EME.
In terms of security, it seems "almost" like an instance of the
Naor-Reingold mode (where the mixing is instantiated using the NMH
hash function of Hugo and myself). The "almost" part is for two
reasons:
1. The NR mode includes another "multiplication by a key" after you
add H1 ... H16 to P1. That is, instead of computing
PP1 = P1 + (H1 + ... + H16)
PPi = (Pi+Ki) + PP1 for i=2..32
you compute
PP1 = P1 + (H1 + ... + H16)
PPi = (Pi+Ki) + PP1*k0 for i = 2..32
2. The hash function of Hugo and me is
H(x,y) = (kx+x)*(ky+y) mod p mod 2^{128}
where p is slightly larger than 2^{128} (and + is integer addition).
If you make these two changes to the scheme, I think that you indeed
get an instance of NR, so you can use the NR proof of security, which
is simpler than that of EME (but not as simple as you may think). The
specific bounds that you get would be worse than for EME (maybe instead
of 7q^2/2^n you get 100q^2/2^n or even 1000q^2/2^n), but I don't think
that we really care. Without these two modifications, I tend to think
that the scheme is insecure:
I think that without point 1 above you can attack this scheme by
encrypting two sectors that only differ in P1, and then do some
interesting mix-n-match of the two ciphertexts and decrypt the result(s),
and you would be able to distinguish the resulting plaintext(s) from
random. (But I would have to think about it some more and to refresh
my memory of the NR mode.)
As for the point 2, until you prove to me otherwise, I think that the
proposed hash function
H(x,y) = (kx xor x)*(ky xor y) mod p (with p < 2^{128})
falls short of what you need for security. What you need is that for
all (x,y) and (x',y') and for all Delta
Pr[H(x,y) xor H(x',y') = Delta] <= epsilon
where the probability is over kx,ky and epsilon is close to 2^{-128}.
My gut feeling is that for some special "worst case constants" you can
get probability closer to 2^{-64} than 2^{-128} (because xor can be
approximated by addition, and p < 2^{128}).
Either way, making the above modification would not significantly change
the scheme, so let's just assume that we can find a secure scheme which
is close enough to the current proposal.
The main problem with this proposal (in my view) is the long keys. You
need more than 512 bytes of key which makes the scheme problematic if
you need to switch keys often (in buzzwords, it is less "key agile").
This is a common problem with the MMH family of functions (MMH, NMH,
UMAC, etc.). As for speed and gate count, I don't really know. My guess
is that it would be fairly close to EME on "high end hardware" (maybe 30%
this way or that) and slower than EME on "low end hardware". But this
is only a guess.
-- Shai
On Friday 27 February 2004 05:19 pm, Williams, Jim wrote:
> Being new to this effort, I am not sure what has already been discussed
> and or decided. So I hope this discussion is not out of order.
>
> I have attached a brief description of an alternative wide block
> encryption algorithm. I am certainly far from recommending or proposing
> this, but would be quite interested in any discussion of pros and cons.
>
> Best case, this alternative is less costly to implement at a given
> performance level, and easier to prove secure. Worst case, it is
> totally broken. And there is much room in between.
>
> - Jim