Really fast syndrome-based hashing

D.J. Bernstein, T. Lange, C.P. Peters, P. Schwabe

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

8 Citations (Scopus)

Abstract

The FSB (fast syndrome-based) hash function was submitted to the SHA-3 competition by Augot, Finiasz, Gaborit, Manuel, and Sendrier in 2008, after preliminary designs proposed in 2003, 2005, and 2007. Many FSB parameter choices were broken by Coron and Joux in 2004, Saarinen in 2007, and Fouque and Leurent in 2008, but the basic FSB idea appears to be secure, and the FSB submission remains unbroken. On the other hand, the FSB submission is also quite slow, and was not selected for the second round of the competition. This paper introduces RFSB, an enhancement to FSB. In particular, this paper introduces the RFSB-509 compression function, RFSB with a particular set of parameters. RFSB-509, like the FSB-256 compression function, is designed to be used inside a 256-bit collision-resistant hash function: all known attack strategies cost more than 2128 to find collisions in RFSB-509. However, RFSB-509 is an order of magnitude faster than FSB-256. On a single core of a Core 2 Quad CPU, RFSB-509 runs at 13.62 cycles/byte: faster than SHA-256, faster than 6 of the 14 secondround SHA-3 candidates, and faster than 2 of the 5 SHA-3 finalists.
Original languageEnglish
Title of host publicationProgress in Cryptology - AfricaCrypt 2011 (4th International Conference on Cryptology in Africa, Dakar, Senegal, July 5-7, 2011. Proceedings)
EditorsA. Nitaj, D. Pointcheval
Place of PublicationBerlin
PublisherSpringer
Pages134-152
ISBN (Print)978-3-642-21968-9
DOIs
Publication statusPublished - 2011

Publication series

NameLecture Notes in Computer Science
Volume6737
ISSN (Print)0302-9743

Fingerprint

Hash functions
Program processors
Costs

Cite this

Bernstein, D. J., Lange, T., Peters, C. P., & Schwabe, P. (2011). Really fast syndrome-based hashing. In A. Nitaj, & D. Pointcheval (Eds.), Progress in Cryptology - AfricaCrypt 2011 (4th International Conference on Cryptology in Africa, Dakar, Senegal, July 5-7, 2011. Proceedings) (pp. 134-152). (Lecture Notes in Computer Science; Vol. 6737). Berlin: Springer. https://doi.org/10.1007/978-3-642-21969-6_9
Bernstein, D.J. ; Lange, T. ; Peters, C.P. ; Schwabe, P. / Really fast syndrome-based hashing. Progress in Cryptology - AfricaCrypt 2011 (4th International Conference on Cryptology in Africa, Dakar, Senegal, July 5-7, 2011. Proceedings). editor / A. Nitaj ; D. Pointcheval. Berlin : Springer, 2011. pp. 134-152 (Lecture Notes in Computer Science).
@inproceedings{4da3d32007894e8791887e08ef5a71ee,
title = "Really fast syndrome-based hashing",
abstract = "The FSB (fast syndrome-based) hash function was submitted to the SHA-3 competition by Augot, Finiasz, Gaborit, Manuel, and Sendrier in 2008, after preliminary designs proposed in 2003, 2005, and 2007. Many FSB parameter choices were broken by Coron and Joux in 2004, Saarinen in 2007, and Fouque and Leurent in 2008, but the basic FSB idea appears to be secure, and the FSB submission remains unbroken. On the other hand, the FSB submission is also quite slow, and was not selected for the second round of the competition. This paper introduces RFSB, an enhancement to FSB. In particular, this paper introduces the RFSB-509 compression function, RFSB with a particular set of parameters. RFSB-509, like the FSB-256 compression function, is designed to be used inside a 256-bit collision-resistant hash function: all known attack strategies cost more than 2128 to find collisions in RFSB-509. However, RFSB-509 is an order of magnitude faster than FSB-256. On a single core of a Core 2 Quad CPU, RFSB-509 runs at 13.62 cycles/byte: faster than SHA-256, faster than 6 of the 14 secondround SHA-3 candidates, and faster than 2 of the 5 SHA-3 finalists.",
author = "D.J. Bernstein and T. Lange and C.P. Peters and P. Schwabe",
year = "2011",
doi = "10.1007/978-3-642-21969-6_9",
language = "English",
isbn = "978-3-642-21968-9",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "134--152",
editor = "A. Nitaj and D. Pointcheval",
booktitle = "Progress in Cryptology - AfricaCrypt 2011 (4th International Conference on Cryptology in Africa, Dakar, Senegal, July 5-7, 2011. Proceedings)",
address = "Germany",

}

Bernstein, DJ, Lange, T, Peters, CP & Schwabe, P 2011, Really fast syndrome-based hashing. in A Nitaj & D Pointcheval (eds), Progress in Cryptology - AfricaCrypt 2011 (4th International Conference on Cryptology in Africa, Dakar, Senegal, July 5-7, 2011. Proceedings). Lecture Notes in Computer Science, vol. 6737, Springer, Berlin, pp. 134-152. https://doi.org/10.1007/978-3-642-21969-6_9

Really fast syndrome-based hashing. / Bernstein, D.J.; Lange, T.; Peters, C.P.; Schwabe, P.

Progress in Cryptology - AfricaCrypt 2011 (4th International Conference on Cryptology in Africa, Dakar, Senegal, July 5-7, 2011. Proceedings). ed. / A. Nitaj; D. Pointcheval. Berlin : Springer, 2011. p. 134-152 (Lecture Notes in Computer Science; Vol. 6737).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Really fast syndrome-based hashing

AU - Bernstein, D.J.

AU - Lange, T.

AU - Peters, C.P.

AU - Schwabe, P.

PY - 2011

Y1 - 2011

N2 - The FSB (fast syndrome-based) hash function was submitted to the SHA-3 competition by Augot, Finiasz, Gaborit, Manuel, and Sendrier in 2008, after preliminary designs proposed in 2003, 2005, and 2007. Many FSB parameter choices were broken by Coron and Joux in 2004, Saarinen in 2007, and Fouque and Leurent in 2008, but the basic FSB idea appears to be secure, and the FSB submission remains unbroken. On the other hand, the FSB submission is also quite slow, and was not selected for the second round of the competition. This paper introduces RFSB, an enhancement to FSB. In particular, this paper introduces the RFSB-509 compression function, RFSB with a particular set of parameters. RFSB-509, like the FSB-256 compression function, is designed to be used inside a 256-bit collision-resistant hash function: all known attack strategies cost more than 2128 to find collisions in RFSB-509. However, RFSB-509 is an order of magnitude faster than FSB-256. On a single core of a Core 2 Quad CPU, RFSB-509 runs at 13.62 cycles/byte: faster than SHA-256, faster than 6 of the 14 secondround SHA-3 candidates, and faster than 2 of the 5 SHA-3 finalists.

AB - The FSB (fast syndrome-based) hash function was submitted to the SHA-3 competition by Augot, Finiasz, Gaborit, Manuel, and Sendrier in 2008, after preliminary designs proposed in 2003, 2005, and 2007. Many FSB parameter choices were broken by Coron and Joux in 2004, Saarinen in 2007, and Fouque and Leurent in 2008, but the basic FSB idea appears to be secure, and the FSB submission remains unbroken. On the other hand, the FSB submission is also quite slow, and was not selected for the second round of the competition. This paper introduces RFSB, an enhancement to FSB. In particular, this paper introduces the RFSB-509 compression function, RFSB with a particular set of parameters. RFSB-509, like the FSB-256 compression function, is designed to be used inside a 256-bit collision-resistant hash function: all known attack strategies cost more than 2128 to find collisions in RFSB-509. However, RFSB-509 is an order of magnitude faster than FSB-256. On a single core of a Core 2 Quad CPU, RFSB-509 runs at 13.62 cycles/byte: faster than SHA-256, faster than 6 of the 14 secondround SHA-3 candidates, and faster than 2 of the 5 SHA-3 finalists.

U2 - 10.1007/978-3-642-21969-6_9

DO - 10.1007/978-3-642-21969-6_9

M3 - Conference contribution

SN - 978-3-642-21968-9

T3 - Lecture Notes in Computer Science

SP - 134

EP - 152

BT - Progress in Cryptology - AfricaCrypt 2011 (4th International Conference on Cryptology in Africa, Dakar, Senegal, July 5-7, 2011. Proceedings)

A2 - Nitaj, A.

A2 - Pointcheval, D.

PB - Springer

CY - Berlin

ER -

Bernstein DJ, Lange T, Peters CP, Schwabe P. Really fast syndrome-based hashing. In Nitaj A, Pointcheval D, editors, Progress in Cryptology - AfricaCrypt 2011 (4th International Conference on Cryptology in Africa, Dakar, Senegal, July 5-7, 2011. Proceedings). Berlin: Springer. 2011. p. 134-152. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-642-21969-6_9