RE: Wide-block Encryption Alternative
> -----Original Message-----
> From: james Hughes [mailto:james_hughes@stortek.com]
> Sent: Monday, March 01, 2004 10:06 AM
> To: Williams, Jim
> Cc: james Hughes; stds-P1619@majordomo.ieee.org
> Subject: Re: Wide-block Encryption Alternative
>
>
>
> On Feb 29, 2004, at 4:44 PM, Williams, Jim wrote:
> > 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?
>
> If indeed it requires a full birthday surprise to get a collision, then
> I would expect that this is secure.
>
> I will look at this further. My concern is still stands about potential
> collisions at PP_1 with only a few trials.
The idea is as follows (perhaps you can poke a hole in this).
In order to create a collision at PP_1, you need to satisfy the following
equation.
P_1A ^ P_1B = H( P_31, P_32A, K_31, K_32) ^ H( P_31, P_32B, K_31,
K_32)
Where P_32A and P_32B are two trial values of P_32 and P_1A and P_1B are
trial
values of P_1. H is the hash primitive where
H( x, y, K1, K2 ) = ( (x^K1)*(y^K2) % P ).
Given a "perfect" hash H, you can pick any values you want for P_1A, P_1B,
P32_A, and P32_B, and exactly 2^128 values of K31 and K32 (out of the total
of 2^256 joint possibilities) will satisfy the equation. Since K31 and K32
are
unknown, the attacker has a 1/(2^128) probability of success.
This leaves two avenues of attack.
1. Exploit the fact that the proposed hash is not "perfect".
2. Mount an adaptive attack where subsequent guesses are progressively
better based on data from previous guesses.
The intent is that attack #1 is prevented by the hash being "good enough",
and attack #2 is prevented by the AES encryption layer hiding
any information that would be of use to the attacker in mounting an
adaptive attack.