Realizations of the Length Attack on AAFG1 Cryptosystem
by
James Hughes
Storage Technology Corp

Recently a length attack on the AAFG1 Cryptosystem was proposed. In this talk, we describe a possible realization. This is important since it has been suggested that this type of attack is "probabilistic" and "requires a very large computational power". We show to the contrary that it is not probabilistic, and introduce results showing why it works specifically against the AAFG1 cryptosystem.

One can characterize the length attack as an ordered search problem in which most solutions can be found rather quickly with a reasonable complexity. Indeed, we will provide such results and extrapolate the modal and average complexity of a solution.

Finally, we will give our perspective on what properties a cipher in this algorithmic class must possess in order to be accepted by the cryptographic community as "secure".

Date received: March 30, 2005