Rumba20
D. J. Bernstein
Hash functions and ciphers
The Rumba20 compression function
The Rumba20 compression function maps a 192-byte (1536-bit) string
to a 64-byte (512-bit) string.
Rumba20 is designed to provide collision resistance at high speed.
Rumba20 reuses large components of the successful
Salsa20 stream cipher.
Implementors can reuse their Salsa20 speedups to save time in Rumba20,
and cryptanalysts can reuse some of their Salsa20 analysis to get a head start in analyzing Rumba20.
The following papers define Rumba20,
and present the best attack currently known against Rumba20:
-
[expandxor]
(PDF)
10pp.
D. J. Bernstein.
What output size resists collisions in a xor of independent expansions?
Document ID: dee774697b66f19a00071db1b0666cab.
URL: https://cr.yp.to/papers.html#expandxor.
Date: 2007.05.03.
Supersedes:
(PDF)
2007.04.11.
-
[genbday]
(PDF)
8pp.
D. J. Bernstein.
Better price-performance ratios for generalized birthday attacks.
Document ID: 7cf298bebf853705133a84bea84d4a07.
URL: https://cr.yp.to/papers.html#genbday.
Date: 2007.09.04.
Supersedes:
(PDF)
2007.07.19.
The attack has price-performance ratio on the scale of 2^256
when the attacker has fewer than 2^85 processors;
price-performance ratio on the scale of 2^171
when the attacker has more than 2^114 processors;
and intermediate price-performance ratios for intermediate numbers of processors.
The attack obviously will not be carried out in the foreseeable future,
and would have to be dramatically improved before it becomes a threat.
I've also given a talk on the same topic:
2007.05.24.
Rumba20 is not designed to provide
unpredictability, truncated collision resistance, etc.
These features must be provided by an appropriate output filter.
Rumba20's goal is to efficiently compress a long input
so that only a small amount of data has to be handled by the output filter.
Reduced-round Rumba20 variants
Rumba20 has 20 rounds, just like the full Salsa20/20.
This is many more rounds than I know how to break;
I'm a fan of confidence in cipher design,
so I recommend the full 20 rounds.
However, I presume that
users who need higher speed, and who don't care so much about confidence,
will consider reduced-round versions of Rumba20:
12-round Rumba12, for example, and 8-round Rumba8.
Note that the naming convention for reduced-round versions of Rumba20
differs from the naming convention for reduced-round versions of Salsa20:
Rumba8 corresponds to Salsa20/8,
for example, and
Rumba12 corresponds to Salsa20/12.
Rumba20 prizes
At the end of 2007,
I will award a $1000 prize
for the public Rumba20 cryptanalysis that I consider most interesting.
I won't make any promises regarding what I'll find interesting,
but here are some guidelines:
- Finding reduced-round collisions is the obvious way to start.
- Handling more rounds wins bonus points.
- Better price-performance ratio for a collision wins bonus points.
- Early publication wins bonus points. Don't hold back!
- New ideas win bonus points.
Cryptanalysts are also encouraged to consider variants of Rumba20,
for example replacing Salsa20 with ChaCha.
2008.01.02 update:
Yesterday I awarded the prize to
Jean-Philippe Aumasson,
Simon Fischer,
Shahram Khazaei,
Willi Meier,
and
Christian Rechberger
for the paper "New features of Latin dances: Analysis of Salsa, ChaCha, and Rumba."
Here's a
copy
of the 2007.12.18 version of the paper,
as posted on IACR's Cryptology ePrint Archive.