Hitag2 is a widely applied lightweight stream cipher with a traditional structure containing linear shift feedback and nonlinear filtering. It uses a Boolean function of 20 variables as its nonlinear filter. For easy implementation, this function is constructed by a two-layer composition of one 5-variable Boolean function and five 4-variable Boolean functions. In this paper, the concept of nested function is extracted from the construction of the two-layer Boolean function in Hitag2. Then we study some general properties of nested functions, such as balancedness, algebraic degree, Walsh spectra and algebraic immunity. We prove that the Walsh spectra of a nested function can be split into a product of the Walsh spectra of its subfunctions and generating function when the subfunctions are all balanced. Moreover, two upper bounds on algebraic immunity of nested functions are proposed. By using a hybrid approach of logical reasoning and computer computation, we obtain the precise value of the algebraic immunity of the filter function used in Hitag2, which is equal to 6.

References in zbMATH (referenced in 10 articles )

Showing results 1 to 10 of 10.
Sorted by year (citations)

  1. Heydari, Farideh; Ghahremanian, Alireza: A graph theoretic method for securing key fobs (2021)
  2. Roy, Dibyendu; Datta, Pratish; Mukhopadhyay, Sourav: Algebraic cryptanalysis of stream ciphers using decomposition of Boolean function (2015)
  3. Shan, Jinyong; Hu, Lei; Zeng, Xiangyong: Cryptographic properties of nested functions and algebraic immunity of the Boolean function in Hitag2 stream cipher (2014)
  4. Korak, Thomas; Plos, Thomas: Applying remote side-channel analysis attacks on a security-enabled NFC tag (2013)
  5. Strobel, Daehyun; Driessen, Benedikt; Kasper, Timo; Leander, Gregor; Oswald, David; Schellenberg, Falk; Paar, Christof: Fuming acid and cryptanalysis: handy tools for overcoming a digital locking and access control system (2013)
  6. Bogdanov, Andrey (ed.); Sanadhya, Somitra (ed.): Security, privacy, and applied cryptography engineering. Second international conference, SPACE 2012, Chennai, India, November 3--4, 2012. Proceedings (2012)
  7. Immler, Vincent: Breaking HITAG 2 revisited (2012)
  8. Sun, Siwei; Hu, Lei; Xie, Yonghong; Zeng, Xiangyong: Cube cryptanalysis of Hitag2 stream cipher (2011)
  9. Bard, Gregory V.; Courtois, Nicolas T.; Nakahara, Jorge jun.; Sepehrdad, Pouyan; Zhang, Bingsheng: Algebraic, AIDA/Cube and side channel analysis of KATAN family of block ciphers (2010)
  10. Courtois, Nicolas T.; O’Neil, Sean; Quisquater, Jean-Jacques: Practical algebraic attacks on the Hitag2 stream cipher (2009)