Paper 2009/128

Attacks on a Lightweight Cipher Based on a Multiple Recursive Generator

Lu Xiao and Gregory G. Rose

Abstract

At IEEE GLOBECOM 2008, a lightweight cipher based on a Multiple Recursive Generator (MRG) was proposed for use in resource limited environment such as sensor nodes and RFID tags. This paper proposes two efficient attacks on this MRG cipher. A distinguishing attack is firstly introduced to identify the use of an MRG cipher that has a modulus suggested by its designers. It requires $2^{18}$ words of ciphertext and the most significant bit of each corresponding plaintext word. Then an efficient known plaintext attack is proposed to construct the cipher's current state and generate subkeys used for all subsequent encryption. The known plaintext attack, when targeted at the MRG ciphers optimized for efficiency, only requires 2k words of known plaintext and trivial computation where k is the MRG order. Even the ciphers based on complicated and inefficient MRGs can be attacked with low complexity, e.g., in the magnitude of $2^{12}$ words of known plaintext for all MRG ciphers with order 47, regardless of which MRG modulus is used. These two attacks indicate that the examined MRG cipher structure is seriously flawed.

Metadata
Available format(s)
PDF PS
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
ciphercryptanalysis
Contact author(s)
lxiao @ qualcomm com
History
2009-03-20: received
Short URL
https://ia.cr/2009/128
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/128,
      author = {Lu Xiao and Gregory G.  Rose},
      title = {Attacks on a Lightweight Cipher Based on a Multiple Recursive Generator},
      howpublished = {Cryptology ePrint Archive, Paper 2009/128},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/128}},
      url = {https://eprint.iacr.org/2009/128}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.