Paper 2013/202

Breaking NLM-MAC Generator

Mohammad Ali Orumiehchiha, Josef Pieprzyk, and Ron Steinfeld


NLM generator, designed by HoonJae Lee, SangMin Sung, HyeongRag Kim, is the strengthened version of the LM-type summation generator with two memory bits; which uses non-linear combination of linear feedback shift register and non-linear feedback shift register. Recently, the cipher along with a massage authenticate function have been proposed for a lightweight communication framework in wireless sensor networks. Also, the generator has been used in two different RFID mutual authentication protocols and a protocol to secure access in internet. This paper indicates some critical cryptographic weak points leading to the key recovery and forgery attack. We prove the internal state of NLM-n can be recovered with time complexity about $n^{log7\times2}$ where the total length of internal state is $2\cdot n+2$ bits. The attack needs about $n^2$ key-stream bits. We also show attacker is able forge any MAC tag in real time by having only one pair (MAC tag, cipher-text). The proposed attacks are completely practical and break the scheme with negligible error probability.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
NLM Stream CipherMAC FunctionCryptanalysisKey Recovery AttackForgery Attack
Contact author(s)
orumiehchi @ gmail com
2013-04-09: received
Short URL
Creative Commons Attribution


      author = {Mohammad Ali Orumiehchiha and Josef Pieprzyk and Ron Steinfeld},
      title = {Breaking {NLM}-{MAC} Generator},
      howpublished = {Cryptology ePrint Archive, Paper 2013/202},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.