License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.09031.6
URN: urn:nbn:de:0030-drops-19443
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2009/1944/
Go to the corresponding Portal

Aumasson, Jean-Philippe ; Dinur, Itai ; Meier, Willi ; Shamir, Adi

Cube Testers and Key Recovery Attacks On Reduced-Round MD6 and Trivium

pdf-format:
09031.AumassonJeanPhilippe.Paper.1944.pdf (0.2 MB)

Abstract

CRYPTO 2008 saw the introduction of the hash function
MD6 and of cube attacks, a type of algebraic attack applicable to cryptographic
functions having a low-degree algebraic normal form over GF(2).
This paper applies cube attacks to reduced round MD6, finding the full
128-bit key of a 14-round MD6 with complexity 2\^22 (which takes less
than a minute on a single PC). This is the best key recovery attack announced
so far for MD6. We then introduce a new class of attacks called
cube testers, based on efficient property-testing algorithms, and apply
them to MD6 and to the stream cipher Trivium. Unlike the standard
cube attacks, cube testers detect nonrandom behavior rather than performing
key extraction, but they can also attack cryptographic schemes
described by nonrandom polynomials of relatively high degree. Applied
to MD6, cube testers detect nonrandomness over 18 rounds in 2\^17 complexity;
applied to a slightly modified version of the MD6 compression
function, they can distinguish 66 rounds from random in 2\^24 complexity.
Cube testers give distinguishers on Trivium reduced to 790 rounds from
random with 2^30 complexity and detect nonrandomness over 885 rounds
in 2\^27, improving on the original 767-round cube attack.

BibTeX - Entry

@InProceedings{aumasson_et_al:DagSemProc.09031.6,
  author =	{Aumasson, Jean-Philippe and Dinur, Itai and Meier, Willi and Shamir, Adi},
  title =	{{Cube Testers and Key Recovery Attacks On Reduced-Round MD6 and Trivium}},
  booktitle =	{Symmetric Cryptography},
  pages =	{1--22},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9031},
  editor =	{Helena Handschuh and Stefan Lucks and Bart Preneel and Phillip Rogaway},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2009/1944},
  URN =		{urn:nbn:de:0030-drops-19443},
  doi =		{10.4230/DagSemProc.09031.6},
  annote =	{Keywords: Cube attacks, property testing, MD6, Trivium}
}

Keywords: Cube attacks, property testing, MD6, Trivium
Collection: 09031 - Symmetric Cryptography
Issue Date: 2009
Date of publication: 30.03.2009

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI