Abstract
Integral attack is a powerful method to recover some round keys of block ciphers by exploiting the characteristic that a set of outputs after several rounds encryption has (integral distinguisher). Recently, Todo proposed a new algorithm to construct integral distinguisher with division property. However, the existence of integral distinguisher which holds in additional rounds can not be denied by the algorithm. On the contrary, our approach is to obtain the number of rounds which integral distinguisher does not hold. The approach is based on algebraic degree estimation. We execute a random search for a term which has a degree equals the number of all inputted variables. We propose two algorithms and apply them to PRESENT and RECTANGLE. Then, we confirm that there exists no 8-round integral distinguisher in PRESENT and no 9-round integral distinguisher in RECTANGLE. From these facts, it is infeasible to attack more than 11-round and 13-round of PRESENT and RECTANGLE, respectively.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bogdanov, A., Knudsen, L.R., Leander, G., Paar, C., Poschmann, A., Robshaw, M.J.B., Seurin, Y., Vikkelsoe, C.: PRESENT: an ultra-lightweight block cipher. In: Paillier, P., Verbauwhede, I. (eds.) CHES 2007. LNCS, vol. 4727, pp. 450–466. Springer, Heidelberg (2007). doi:10.1007/978-3-540-74735-2_31
Knudsen, L., Wagner, D.: Integral cryptanalysis. In: Daemen, J., Rijmen, V. (eds.) FSE 2002. LNCS, vol. 2365, pp. 112–127. Springer, Heidelberg (2002). doi:10.1007/3-540-45661-9_9
Knudsen, L.R.: Truncated and higher order differentials. In: Preneel, B. (ed.) FSE 1994. LNCS, vol. 1008, pp. 196–211. Springer, Heidelberg (1995). doi:10.1007/3-540-60590-8_16
Todo, Y.: Structural evaluation by generalized integral property. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 287–314. Springer, Heidelberg (2015). doi:10.1007/978-3-662-46800-5_12
Todo, Y., Morii, M.: Bit-based division property and application to simon family. IACR Cryptology ePrint Archive 2016, 285 (2016). http://eprint.iacr.org/2016/285
Wu, S., Wang, M.: Integral attacks on reduced-round PRESENT. In: Qing, S., Zhou, J., Liu, D. (eds.) ICICS 2013. LNCS, vol. 8233, pp. 331–345. Springer, Cham (2013). doi:10.1007/978-3-319-02726-5_24
Z’aba, M.R., Raddum, H., Henricksen, M., Dawson, E.: Bit-pattern based integral attack. In: Nyberg, K. (ed.) FSE 2008. LNCS, vol. 5086, pp. 363–381. Springer, Heidelberg (2008). doi:10.1007/978-3-540-71039-4_23
Zhang, H., Wu, W., Wang, Y.: Integral attack against bit-oriented block ciphers. In: Kwon, S., Yun, A. (eds.) ICISC 2015. LNCS, vol. 9558, pp. 102–118. Springer, Cham (2016). doi:10.1007/978-3-319-30840-1_7
Zhang, W., Bao, Z., Lin, D., Rijmen, V., Yang, B., Verbauwhede, I.: RECTANGLE: A bit-slice ultra-lightweight block cipher suitable for multiple platforms. Cryptology ePrint Archive, Report 2014/084 (2014). http://eprint.iacr.org/
Zhang, W., Su, B., Wu, W., Feng, D., Wu, C.: Extending higher-order integral: an efficient unified algorithm of constructing integral distinguishers for block ciphers. In: Bao, F., Samarati, P., Zhou, J. (eds.) ACNS 2012. LNCS, vol. 7341, pp. 117–134. Springer, Heidelberg (2012). doi:10.1007/978-3-642-31284-7_8
Acknowledgment
This work was supported by JSPS KAKENHI Grant Number 24560491.
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Kosuge, H., Tanaka, H. (2017). Algebraic Degree Estimation for Integral Attack by Randomized Algorithm. In: Choi, D., Guilley, S. (eds) Information Security Applications. WISA 2016. Lecture Notes in Computer Science(), vol 10144. Springer, Cham. https://doi.org/10.1007/978-3-319-56549-1_25
Download citation
DOI: https://doi.org/10.1007/978-3-319-56549-1_25
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-56548-4
Online ISBN: 978-3-319-56549-1
eBook Packages: Computer ScienceComputer Science (R0)