A Chosen-iv Key Recovery Attack On Py And Pypy

摘要

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 2~(23) chosen IVs and time complexity 2~(72). First, we improve the WP-1 attack by using the internal-state correlation (called a P-l attack). For a 128-bit key and a 128-bit IV, the P-1 attack can recover a key with 2~(23) chosen IVs and time complexity 2~(48), which is 1/2~(24) 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 2~(28) chosen IVs and time complexity 2~(24). Second, we improve the WP-2 attack by using the internal-state correlation as well as the P-l 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 2~(24), 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.