PET SNAKE: A Special Purpose Architecture to Implement an Algebraic Attack in Hardware

Willi Geiselmann; Kenneth Matheis; Rainer Steinwandt

Paper 2009/222

PET SNAKE: A Special Purpose Architecture to Implement an Algebraic Attack in Hardware

Willi Geiselmann, Kenneth Matheis, and Rainer Steinwandt

Abstract

In [Solving Multiple Right Hand Sides linear equations. Designs, Codes and Cryptography, 49:147–160, 2008] Raddum and Semaev propose a technique to solve systems of polynomial equations over GF(2) as occurring in algebraic attacks on block ciphers. This approach is known as MRHS, and we present a special purpose architecture to implement MRHS in a dedicated hardware device. Our preliminary performance analysis of this Parallel Elimination Technique Supporting Nice Algebraic Key Elimination shows that the use of ASICs seems to enable significant performance gains over a software implementation of MRHS. The main parts of the proposed architecture are scalable, the limiting factor being mainly the available bandwidth for interchip communication. Our focus is on a design choice that can be implemented within the limits of available fab technology. The proposed design can be expected to offer a running time improvement in the order of several magnitudes over a software implementation. We do not make any claims about the practical feasibility of an attack against AES-128 with our design, as we do not see the necessary theoretical tools to be available: deriving reliable running time estimates for an algebraic attack with MRHS when being applied to a full-round version of AES-128 is still an open problem.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Published elsewhere. A short version of this paper appears in Springer Transactions on Computational Science, Special Issue on "Security in Computing". This is the full version.
Keywords: block cipher algebraic attack cryptanalytic hardware MRHS
Contact author(s): kmatheis @ fau edu
History: 2010-09-01: last of 3 revisions; 2009-05-27: received; See all versions
Short URL: https://ia.cr/2009/222
License: CC BY

BibTeX

@misc{cryptoeprint:2009/222,
      author = {Willi Geiselmann and Kenneth Matheis and Rainer Steinwandt},
      title = {{PET} {SNAKE}: A Special Purpose Architecture to Implement an Algebraic Attack in Hardware},
      howpublished = {Cryptology {ePrint} Archive, Paper 2009/222},
      year = {2009},
      url = {https://eprint.iacr.org/2009/222}
}