RE: Wide-block Encryption Alternative
I updated the slides to fix a couple flaws in the algorithm
and include a more detailed proof of security. Although it may
be of only acedemic interest, I would be interested if there are
any flaws in the proof.
Regarding implementation, I did some synthesis on the alternatives
and got some interesting numbers. I attempted to estimate the
number of gates required for a fully combinatorial implemention
of AES and of a modP multiplier. Although a fully combinatorial
design may not be the desired implementation, it is a good first
order metric of design cost.
A 32 X 32 -> 64 multiplier was 6728 gates.
Assume modP multiplier is 16 times that. Adding partial products
and modular reduction should add insignicantly to gate count.
(There may be some clever ways to do this with 9 multipliers
rather than 16, but at the cost of added complexity and extra
gates.)
Multiplier Total: 107468 gates.
AES Sbox -> 396 gates.
This is with an area optimized design. Synthesizing a simple
lookup table was almost twice as big. Assume 160 SBoxes and
that 75% of gates are SBox and 25% in remaining logic.
AES Total: 84480 gates.
Based on this, AES looks preferable to multiplier based design.
Even if complexity were the same, AES would be preferred due
to the simplicity of a single complex block rather than two,
and due to more optimum keying.
> From: Shai Halevi [mailto:shaih@WATSON.IBM.COM]
>
> 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
I couldn't determine from their paper why this second
multiply was included.
Interestingly, in the algorithm I sketched out, if the
final XOR stage is not included, there is a non-obvious
but serious flaw. The above "multiplication by a key"
also solves the problem, but looks like a more expensive
solution.
(It is interesting that the only way I found this flaw
was in attempting to do a case by case proof and having
it fail in a case that I had though would be easy and
therefore hadn't thought much about!)
- Jim
blockEncryption.ppt