From Wikipedia, the free encyclopedia

• Py is a stream cipher submitted to eSTREAM by Eli Biham and Jennifer Seberry. It is one of the fastest eSTREAM candidates at around 2.6 cycles per byte on some platforms. It has a structure a little like RC4, but adds an array of 260 32-bit words which are indexed using a permutation of bytes, and produces 64 bits in each round.

The authors assert that the name be pronounced "Roo", a reference to the cipher's Australian origin, by reading the letters "Py" as Cyrillic (РУ) rather than Latin characters. This somewhat perverse pronunciation is understood to be their answer, in jest, to the difficult-to-pronounce name Rijndael for the cipher which was adopted as the Advanced Encryption Standard.

• In January 2007, three new ciphers TPy, TPypy and TPy6 have been designed by Eli Biham and Jennifer Seberry as strengthened variants of the original Py.

• At Indocrypt 2007, Gautham Sekar, Souradyuti Paul and Bart Preneel proposed two new ciphers RCR-32 and RCR-64 based on the design principles of Py.

[edit] Attacks on the Py-family

As of 2006, the best cryptanalytic attack on Py (by Hongjun Wu and Bart Preneel) can under some circumstances (eg where the IV is much longer than the key) recover the key given partial keystreams for 2²⁴ chosen IVs [1].

In a more difficult scenario from the point of view of attacker, given only known plaintext (rather than chosen plaintext), there is also a distinguishing attack on the keystream (by Paul Crowley) which requires around 2⁷² bytes of output and comparable time. This is an improvement on an attack presented by Gautham Sekar, Souradyuti Paul and Bart Preneel which requires 2⁸⁸ bytes. There is a still a debate whether these attacks constitute an academic break of Py. When the attackers claim that the above attacks can be built with workload less than the exhaustive search under the design specifications of Py and therefore, it is clearly a theoretical break of the cipher, the designers rule out the attacks because Py's security bounds limit any attacker to a total of 2⁶⁴ bytes of output across all keystreams everywhere. A recent revision of the Paul, Preneel, and Sekar paper includes a detailed discussion of this issue in section 9. There are no doubts about the legitimacy of the Wu and Preneel attack.

Py was selected as Phase 2 Focus Candidate for Profile 1 (software) by the eSTREAM project [2] but did not advance to Phase 3 due to the Wu and Preneel chosen IV attack. [3].

In January 2007, three new ciphers namely TPy, TPypy and TPy6 have been proposed by the designers of Py to eliminate the above attacks. The TPy is still vulnerable against the above distinguishing attacks by Paul et al. (complexity 2⁸⁸) and Crowley (complexity 2⁷²). The best attack so far on the TPypy, which is conjectured to be the strongest of the Py-family of ciphers, is by Sekar et al. which is a distinguishing attack with data complexity 2²⁸¹. This attack is only meaningful if the key-size of TPypy is longer than 281 bits.

To remove attacks on TPy and TPypy, Sekar, Paul and Preneel at Indocrypt 2007 gave proposals for two new ciphers RCR-32 and RCR-64. So far there are no attacks against the RCR-32 and RCR-64.

[edit] External links

• Eli Biham,Jennifer Seberry, Py specification (PostScript)
• Eli Biham,Jennifer Seberry, Tweaking the IV Setup of the Py Family of Stream Ciphers -- The Ciphers TPy, TPypy, and TPy6
• eStream page on Py
• Paul Crowley,Cryptanalysis of Py
• Souradyuti Paul,Bart Preneel,Gautham Sekar, Distinguishing attacks on the stream cipher Py, FSE 2006.
• Gautham Sekar,Souradyuti Paul,Bart Preneel, Weaknesses in the Pseudorandom Bit Generation Algorithms of the Stream Ciphers TPypy and TPy, IACR-ePrint report.
• Souradyuti Paul,Bart Preneel, On the (In)security of Stream Ciphers Based on Arrays and Modular Addition (Full Version) , Asicrypt 2006.
• Gautham Sekar,Souradyuti Paul,Bart Preneel, Related-key Attacks on the Py-family of Ciphers and an Approach to Repair the Weaknesses, Indocrypt 2007.
• The Rijndael page - the "Rijndael FAQ" is gently parodied in Appendix B of the Py specification.

v • d • e   Stream ciphers Algorithms:A5/1 | A5/2 | E0 | FISH | Grain | HC-256 | ISAAC | MUGI | Panama | Phelix | Pike | Py | QUAD  | Rabbit | RC4 | Salsa20 | Scream | SEAL | SOBER | SOBER-128 | SOSEMANUK | Trivium | VEST | WAKE Theory: Shift register | LFSR | NLFSR | Shrinking generator | T-function | IV Standardization: eSTREAM v • d • e   Cryptography History of cryptography | Cryptanalysis | Cryptography portal | Topics in cryptography Symmetric-key algorithm | Block cipher | Stream cipher | Public-key cryptography | Cryptographic hash function | Message authentication code | Random numbers | Steganography