Paper 2013/202

Breaking NLM-MAC Generator

Mohammad Ali Orumiehchiha, Josef Pieprzyk, and Ron Steinfeld

Abstract

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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
NLM Stream CipherMAC FunctionCryptanalysisKey Recovery AttackForgery Attack
Contact author(s)
orumiehchi @ gmail com
History
2013-04-09: received
Short URL
https://ia.cr/2013/202
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/202,
      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{https://eprint.iacr.org/2013/202}},
      url = {https://eprint.iacr.org/2013/202}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.