Abstract
SOSEMANUK is a software-oriented stream cipher proposed by C. Berbain et al for the eSTREAM project and has been selected into the final portfolio. It is noticed that most components of SOSEMANUK can be calculated byte-oriented. Hence an attacker can observe SOSEMANUK from the view of byte units instead of the original 32-bit word units. Based on the above idea, in this work we present a new byte-based guess and determine attack on SOSEMANUK, where we view a byte as a basic data unit and guess some certain bytes of the internal states instead of the whole 32-bit words during the execution of the attack. Surprisingly, our attack only needs a few words of known key stream to recover all the internal states of SOSEMANUK, and the time complexity can be dramatically reduced to O(2176). Since SOSEMANUK has a key with the length varying from 128 to 256 bits, our results show that when the length of an encryption key is larger than 176 bits, our guess and determine attack is more efficient than an exhaustive key search.
This work was supported by the National Natural Science Foundation (Grant No. 60833008 and 60902024).
Chapter PDF
Similar content being viewed by others
References
The eSTREAM project, http://www.ecrypt.eu.org/stream/
Berbain, C., Billet, O., Canteaut, A., Courtois, N., Gilbert, H., Goubin, L., Gouget, A., Granboulan, L., Lauradoux, C., Minier, M., Pornin, T., Sibert, H.: SOSEMANUK, a fast software-oriented stream cipher, eSTREAM, the ECRYPT Stream Cipher Project, Report 2005/027 (2005)
Ekdahl, P., Johansson, T.: A new version of the stream cipher SNOW. In: Nyberg, K., Heys, H.M. (eds.) SAC 2002. LNCS, vol. 2595, pp. 47–61. Springer, Heidelberg (2003)
Anderson, R., Biham, E., Knudsen, L.R.: Serpent: A proposal for the advanced encryption standard, NIST AES Proposal (1998)
Bleichenbacher, D., Patel, S.: SOBER cryptanalysis, Fast Software Encryption. In: Knudsen, L.R. (ed.) FSE 1999. LNCS, vol. 1636, pp. 305–316. Springer, Heidelberg (1999)
Hawkes, P., Rose, G.: Exploiting multiplies of the connection polynomial in word-oriented stream ciphers. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 302–316. Springer, Heidelberg (2000)
Hawkes, P., Rose, G.: Guess and determine attacks on SNOW. In: Nyberg, K., Heys, H.M. (eds.) SAC 2002. LNCS, vol. 2595, pp. 37–46. Springer, Heidelberg (2003)
Canniere, C.D.: Guess and determine attacks on SNOW, NESSIE Public Document, NES/DOC/KUL/WP5/011/a (2001)
Ahmadi, H., Eghlidos, T., Khazaei, S.: Improved guess and determine Attack on SOSEMANUK, Tehran, Iran (2006), http://www.ecrypt.eu.org/stream/sosemanukp3.html
Tsunoo, Y., Saito, T., Shigeri, M., Suzaki, T., Ahmadi, H., Eghlidos, T., Khazaei, S.: Evaluation of SOSEMANUK with regard to guess-and-determine attacks (2006), http://www.ecrypt.eu.org/stream/sosemanukp3.html
Lin, D., Jie, G.: Guess and Determine Attack on SOSEMANUK. In: 2009 Fifth International Conference on Information Assurance and Security, vol. 1, pp. 658–661 (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 International Association for Cryptologic Research
About this paper
Cite this paper
Feng, X., Liu, J., Zhou, Z., Wu, C., Feng, D. (2010). A Byte-Based Guess and Determine Attack on SOSEMANUK. In: Abe, M. (eds) Advances in Cryptology - ASIACRYPT 2010. ASIACRYPT 2010. Lecture Notes in Computer Science, vol 6477. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-17373-8_9
Download citation
DOI: https://doi.org/10.1007/978-3-642-17373-8_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-17372-1
Online ISBN: 978-3-642-17373-8
eBook Packages: Computer ScienceComputer Science (R0)