Abstract: We introduce two new correlation attacks on stream ciphers that make use of non-linearly combined linear feedback shift-registers (LFSRs). The first attack utilises the well-known Lempel-Ziv complexity measure for binary sequences. The second attack is based on the Binary Derivative, applied in conjnction with the distribution of runs in a binary sequence. Both attacks make use of ciphertext-only, and give very good results. They are able to recover the unknown (secret) initial state of an internal LFSR, even when only a very small correlation of q = 0.52 occurs between the observed ciphertext and the output of an internal LFSR, and approximately 60000 ciphertext bits are required for attacks to succeed. The computational complexity and memory requirements ofthe Binary Derivative attack are substantially lower than for the LempelZiv attack, making it feasible to attack stream ciphers with LFSR-lengths of approximately 40 to 50 bits.
Publication Year: 2002
Publication Date: 2002-01-01
Language: en
Type: article
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot