RE: Wide-block Encryption Alternative
> At first blush, the current state of the art, this type of construction
> has never been formally presented as secure.
When I first sketched this out, Shai referred me to a paper
by Naor and Reingold. After reading the paper I concluded
that other than a few implementation details, there was nothing
really new here. I suspect the group may have already discussed this
type of construction at some length and understand the
implications better than I, but I thought it might be worth
a little discussion.
> The way I would attacking this is by manipulating P_1 and
> P_32 in such
> a way that I can determine relationships between K_1 and K_32 and then
> unraveling the rest. Since you are proposing this, I would think that
> you may have thought about this and already have an answer?
I believe that using a chosen plain text attack that varies only
P_1 and P_32, and selecting on the order of 2^64 different
inputs, one should be able to create a collision at PP_1. At this
point the resulting output, C_2 ... C_30, will also collide,
and therefore exhibit highly non-random behavior easily observed
by the attacker. At this point the algorithm is broken.
However I believe the EME algorithm exhibits exactly the same
behavior. It should require about 2^64 trial inputs differing
only in P_1 and P_32 to create
a collision on the 128 bit value of "M". This will also create
a collision on C_2 ... C_31. (Correct me if I am wrong on this
Shai.)
So that brings up an interesting question. Is it acceptable that
the wide block encryption algorithm exhibits observable non-random
behavior when subjected to chosen plain text on the order
of 2^64?
It also seems plausible that the EME algorithm is to be preferred
because the severity of the break is less than MEM. Keys can't
be recovered. However this makes me nervous. It's not immediately
obvious how much damage an attacker could do to EME with
modest size dictionary of collisions. Does the security analysis
that has been done cover this case?
If you can recover any key without creating a collision, or can
create a collision with less than 2^64 chosen inputs, that would
of course be a failure of the algorithm, but you would have to
give me a few more hints as to how this could be done.
>
> I am interested in your answer.
>
> As a matter of process, this is an OK first step, but the procedure I
> would suggest (but the committee could override me) is that we would
> like to only standardize things that have been peer reviewed
> first, to
> get around WiFi problem where, after the fact they showed it to
> cryptographers that said "I would not have done it that way, but I
> don't see any problems" but there were problems later.
>
> To get this peer reviewed in the Crypto community you need to write a
> serious paper and there are several members on the committee that can
> help you write this, and if it still survives, get it submitted to
> conferences.
Sounds right but you are way ahead of me there. I would be interested
first in vetting for obvious problems, as well as getting some better
data on whether there would be any practical advantages to this
type of approach.
- Jim