A Chosen-IV Key Recovery Attack on Py and Pypy

Takanori ISOBE  Toshihiro OHIGASHI  Hidenori KUWAKADO  Masakatu MORII  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E92-D   No.1   pp.32-40
Publication Date: 2009/01/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E92.D.32
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Application Information Security
Keyword: 
cryptanalysis,  stream cipher,  Py,  Pypy,  eSTREAM,  key recovery attack,  

Full Text: PDF(374.5KB)>>
Buy this Article




Summary: 
In this paper, we propose an effective key recovery attack on stream ciphers Py and Pypy with chosen IVs. Our method uses an internal-state correlation based on the vulnerability that the randomization of the internal state in the KSA is inadequate, and it improves two previous attacks proposed by Wu and Preneel (a WP-1 attack and a WP-2 attack). For a 128-bit key and a 128-bit IV, the WP-1 attack can recover a key with 223 chosen IVs and time complexity 272. First, we improve the WP-1 attack by using the internal-state correlation (called a P-1 attack). For a 128-bit key and a 128-bit IV, the P-1 attack can recover a key with 223 chosen IVs and time complexity 248, which is 1/224 of that of the WP-1 attack. The WP-2 attack is another improvement on the WP-1 attack, and it has been known as the best previous attack against Py and Pypy. For a 128-bit key and a 128-bit IV, the WP-2 attack can recover a key with 223 chosen IVs and time complexity 224. Second, we improve the WP-2 attack by using the internal-state correlation as well as the P-1 attack (called a P-2 attack). For a 128-bit key and a 128-bit IV, the P-2 attack can recover a key with 223 chosen IVs and time complexity 224, which is the same capability as that of the WP-2 attack. However, when the IV size is from 64 bits to 120 bits, the P-2 attack is more effective than the WP-2 attack. Thus, the P-2 attack is the known best attack against Py and Pypy.