×

Really fast syndrome-based hashing. (English) Zbl 1280.94039

Nitaj, Abderrahmane (ed.) et al., Progress in cryptology – AFRICACRYPT 2011. 4th international conference on cryptology in Africa, Dakar, Senegal, July 5–7, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-21968-9/pbk). Lecture Notes in Computer Science 6737, 134-152 (2011).
Summary: The FSB (fast syndrome-based) hash function was submitted to the SHA-3 competition by D. Augot, M. Finiasz, P. Gaborit, S. Manuel, and N. Sendrier in 2008, after preliminary designs proposed in 2003, 2005, and 2007. Many FSB parameter choices were broken by J.-S. Coron and A. Joux in 2004, M.-J. O. Saarinen in 2007, and P.-A. Fouque and G. 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 \(2^{128}\) 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.
For the entire collection see [Zbl 1216.94004].

MSC:

94A60 Cryptography

Software:

Quark; McEliece; Keccak
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Augot, D., Finiasz, M., Sendrier, N.: A fast provably secure cryptographic hash function (2003), http://eprint.iacr.org/2003/230 · Zbl 1126.94320
[2] Augot, D., Finiasz, M., Sendrier, N.: A family of fast syndrome based cryptographic hash functions. In: Dawson, E., Vaudenay, S. (eds.) Mycrypt 2005. LNCS, vol. 3715, pp. 64–83. Springer, Heidelberg (2005), http://lasecwww.epfl.ch/pub/lasec/doc/AFS05.pdf · Zbl 1126.94320
[3] Augot, D., Finiasz, M., Gaborit, P., Manuel, S., Sendrier, N.: SHA-3 proposal: FSB (2008), http://www-rocq.inria.fr/secret/CBCrypto/fsbdoc.pdf
[4] Aumasson, J.-P., Henzen, L., Meier, W., Naya-Plasencia, M.: quark: A lightweight hash. In: Mangard, S., Standaert, F.-X. (eds.) CHES 2010. LNCS, vol. 6225, pp. 1–15. Springer, Heidelberg (2010), http://131002.net/quark/quark_full.pdf · Zbl 1297.94043
[5] Bellare, M., Garay, J.A., Rabin, T.: Fast batch verification for modular exponentiation and digital signatures. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 236–250. Springer, Heidelberg (1998), http://cseweb.ucsd.edu/ mihir/papers/batch.html · Zbl 0929.68053
[6] Bellare, M., Micciancio, D.: A new paradigm for collision-free hashing: Incrementality at reduced cost. In: Fumy, W. (ed.) Advances in Cryptology - EUROCRYPT ’97. LNCS, vol. 1233, pp. 163–192. Springer, Heidelberg (1997), http://www-cse.ucsd.edu/ mihir/papers/incremental.html
[7] Bernstein, D.J.: Better price-performance ratios for generalized birthday attacks. In: Workshop Record of SHARCS 2007: Special-purpose Hardware for Attacking Cryptographic Systems (2007), http://cr.yp.to/papers.html#genbday
[8] Bernstein, D.J., Lange, T. (eds.): eBASH: ECRYPT Benchmarking of All Submitted Hashes (2011), http://bench.cr.yp.to (accessed April 21, 2011)
[9] Bernstein, D.J., Lange, T., Niederhagen, R., Peters, C., Schwabe, P.: FSBday: implementing Wagner’s generalized birthday attack against the SHA–3 round–1 candidate FSB. In: Roy, B., Sendrier, N. (eds.) INDOCRYPT 2009. LNCS, vol. 5922, pp. 18–38. Springer, Heidelberg (2009), http://eprint.iacr.org/2009/292 · Zbl 1248.94055
[10] Bernstein, D.J., Lange, T., Peters, C., Schwabe, P.: Faster 2-regular information-set decoding. In: IWCC 2011 [17], pp. 81–98 (2011), http://eprint.iacr.org/2011/120 · Zbl 1272.94096
[11] Bernstein, D.J., Schwabe, P.: New AES software speed records. In: Chowdhury, D.R., Rijmen, V., Das, A. (eds.) INDOCRYPT 2008. LNCS, vol. 5365, pp. 322–336. Springer, Heidelberg (2008), http://cr.yp.to/papers.html#aesspeed · Zbl 1203.94093
[12] Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: Note on Keccak parameters and usage (2010), http://keccak.noekeon.org/NoteOnKeccakParametersAndUsage.pdf · Zbl 1306.94028
[13] Brassard, G. (ed.): CRYPTO 1989. LNCS, vol. 435. Springer, Heidelberg (1990) · Zbl 0719.00029
[14] Brent, R.P., Kung, H.T.: The area-time complexity of binary multiplication. Journal of the ACM 28, 521–534 (1981), http://wwwmaths.anu.edu.au/ brent/pub/pub055.html · Zbl 0462.68014
[15] Buchmann, J., Ding, J. (eds.): PQCrypto 2008. LNCS, vol. 5299. Springer, Heidelberg (2008) · Zbl 1147.94002
[16] Camion, P., Patarin, J.: The knapsack hash function proposed at Crypto’89 can be broken. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 39–53. Springer, Heidelberg (1991), http://hal.inria.fr/inria-00075097/en/ · Zbl 0789.68046
[17] Chee, Y.M., Guo, Z., Ling, S., Shao, F., Tang, Y., Wang, H., Xing, C. (eds.): IWCC 2011. LNCS, vol. 6639. Springer, Heidelberg (2011) · Zbl 1214.94002
[18] Clavier, C., Gaj, K. (eds.): CHES 2009. LNCS, vol. 5747. Springer, Heidelberg (2009) · Zbl 1172.68301
[19] Wolfmann, J., Cohen, G. (eds.): Coding Theory and Applications. LNCS, vol. 388, pp. 3–540. Springer, Heidelberg (1989)
[20] Coron, J.-S., Joux, A.: Cryptanalysis of a provably secure cryptographic hash function (2004), http://eprint.iacr.org/2004/013
[21] Damgård, I.B.: A design principle for hash functions. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 416–427. Springer, Heidelberg (1990) · Zbl 0724.68029
[22] Davies, D.W. (ed.): EUROCRYPT 1991. LNCS, vol. 547, pp. 3–540. Springer, Heidelberg (1991)
[23] Dawson, E., Vaudenay, S. (eds.): Mycrypt 2005. LNCS, vol. 3715. Springer, Heidelberg (2005) · Zbl 1089.94001
[24] Finiasz, M.: Syndrome based collision resistant hashing. In: Buchmann, J., Ding, J. (eds.) PQCrypto 2008. LNCS, vol. 5299, pp. 137–147. Springer, Heidelberg (2008), http://www-rocq.inria.fr/secret/Matthieu.Finiasz/research/2008/finiasz-pqcrypto08.pdf · Zbl 1177.94144
[25] Finiasz, M., Gaborit, P., Sendrier, N.: Improved fast syndrome based cryptographic hash functions. In: Proceedings of ECRYPT Hash Workshop (2007), http://www-roc.inria.fr/secret/Matthieu.Finiasz/research/2007/finiasz-gaborit-sendrier-ecrypt-hash-workshop07.pdf
[26] Fouque, P.-A., Leurent, G.: Cryptanalysis of a hash function based on quasi-cyclic codes. In: Malkin, T. (ed.) CT-RSA 2008. LNCS, vol. 4964, pp. 19–35. Springer, Heidelberg (2008) · Zbl 1159.94360
[27] Fumy, W. (ed.): EUROCRYPT 1997. LNCS, vol. 1233. Springer, Heidelberg (1997) · Zbl 0864.00083
[28] Günther, C.G. (ed.): EUROCRYPT 1988. LNCS, vol. 330. Springer, Heidelberg (1988)
[29] Käsper, E., Schwabe, P.: Faster and timing-attack resistant AES-GCM. In: Clavier, C., Gaj, K. (eds.) CHES 2009. LNCS, vol. 5747, pp. 1–17. Springer, Heidelberg (2009), http://eprint.iacr.org/2009/129 · Zbl 1290.94102
[30] Knuth, D.E.: The art of computer programming, Vol. 3, Sorting and Searching, 2nd edn. Addison-Wesley, Reading (1998) · Zbl 0302.68010
[31] Lee, P.J., Brickell, E.F.: An observation on the security of McEliece’s public-key cryptosystem. In: Günther, C.G. (ed.) EUROCRYPT 1988. LNCS, vol. 330, pp. 275–280. Springer, Heidelberg (1988) · Zbl 0655.94006
[32] Leon, J.S.: A probabilistic algorithm for computing minimum weights of large error-correcting codes. IEEE Transactions on Information Theory 34, 1354–1359 (1988) · Zbl 0666.94017
[33] Malkin, T. (ed.): CT-RSA 2008. LNCS, vol. 4964. Springer, Heidelberg (2008) · Zbl 1134.94002
[34] Mangard, S., Standaert, F.-X. (eds.): CHES 2010. LNCS, vol. 6225. Springer, Heidelberg (2010) · Zbl 1193.68012
[35] Mathieu, C. (ed.): Proceedings of the twentieth annual ACM-SIAM symposium on discrete algorithms, SODA 2009, New York, January 4–6, 2009. SIAM, Philadelphia (2009)
[36] Minder, L., Sinclair, A.: The extended k-tree algorithm. In: SODA 2009 [35], pp. 586–595 (2009), http://www.cs.berkeley.edu/ sinclair/ktree.pdf · Zbl 1271.68241
[37] Nyberg, K. (ed.): EUROCRYPT 1998. LNCS, vol. 1403. Springer, Heidelberg (1998) · Zbl 0889.00042
[38] Chowdhury, D.R., Rijmen, V., Das, A. (eds.): INDOCRYPT 2008. LNCS, vol. 5365. Springer, Heidelberg (2008) · Zbl 1154.94005
[39] Roy, B., Sendrier, N. (eds.): INDOCRYPT 2009. LNCS, vol. 5922. Springer, Heidelberg (2009) · Zbl 1178.94007
[40] Saarinen, M.-J.O.: Linearization attacks against syndrome based hashes. In: Srinathan, K., Rangan, C.P., Yung, M. (eds.) INDOCRYPT 2007. LNCS, vol. 4859, pp. 1–9. Springer, Heidelberg (2007) · Zbl 1153.94426
[41] Srinathan, K., Rangan, C.P., Yung, M. (eds.): INDOCRYPT 2007. LNCS, vol. 4859. Springer, Heidelberg (2007) · Zbl 1135.94002
[42] Stern, J.: A method for finding codewords of small weight. In: [19], pp. 106–113 (1989) · Zbl 0678.94006
[43] Tromer, E., Osvik, D.A., Shamir, A.: Efficient cache attacks on AES, and countermeasures. Journal of Cryptology 23, 37–71 (2010), http://people.csail.mit.edu/tromer/papers/cache-joc-official.pdf · Zbl 1181.94106
[44] Wagner, D.: A generalized birthday problem. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 288–304. Springer, Heidelberg (2002), http://www.cs.berkeley.edu/ daw/papers/genbday.html · Zbl 1026.94541
[45] Yung, M. (ed.): CRYPTO 2002. LNCS, vol. 2442. Springer, Heidelberg (2002) · Zbl 0997.00039
[46] Zobrist, A.L.: A new hashing method with application for game playing. Technical Report 88, Computer Sciences Department, University of Wisconsin (1970), https://www.cs.wisc.edu/techreports/1970/TR88.pdf
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.