Editing RC4 (section)

===Roos' biases and key reconstruction from permutation===
In 1995, Andrew Roos experimentally observed that the first byte of the keystream is correlated with the first three bytes of the key, and the first few bytes of the permutation after the KSA are correlated with some linear combination of the key bytes.<ref>Andrew Roos. A Class of Weak Keys in the RC4 Stream Cipher. Two posts in sci.crypt, message-id 43u1eh$1j3@hermes.is.co.za and 44ebge$llf@hermes.is.co.za, 1995.</ref> These biases remained unexplained until 2007, when Goutam Paul, Siddheshwar Rathi and Subhamoy Maitra<ref>Goutam Paul, Siddheshwar Rathi and Subhamoy Maitra. On Non-negligible Bias of the First Output Byte of RC4 towards the First Three Bytes of the Secret Key. Proceedings of the International Workshop on Coding and Cryptography (WCC) 2007, pages 285–294 and Designs, Codes and Cryptography Journal, pages 123–134, vol. 49, no. 1-3, December 2008.</ref> proved the keystream–key correlation and, in another work, Goutam Paul and Subhamoy Maitra<ref>Goutam Paul and Subhamoy Maitra. Permutation after RC4 Key Scheduling Reveals the Secret Key. SAC 2007, pages 360–377, vol. 4876, [[Lecture Notes in Computer Science]], Springer.</ref> proved the permutation–key correlations. The latter work also used the permutation–key correlations to design the first algorithm for complete key reconstruction from the final permutation after the KSA, without any assumption on the key or [[initialization vector]]. This algorithm has a constant probability of success in a time, which is the square root of the exhaustive key search complexity. Subsequently, many other works have been performed on key reconstruction from RC4 internal states.<ref>Eli Biham and Yaniv Carmeli. Efficient Reconstruction of RC4 Keys from Internal States. FSE 2008, pages 270–288, vol. 5086, Lecture Notes in Computer Science, Springer.</ref><ref>Mete Akgun, Pinar Kavak, Huseyin Demirci. New Results on the Key Scheduling Algorithm of RC4. INDOCRYPT 2008, pages 40–52, vol. 5365, Lecture Notes in Computer Science, Springer.</ref><ref>Riddhipratim Basu, Subhamoy Maitra, Goutam Paul and Tanmoy Talukdar. On Some Sequences of the Secret Pseudo-random Index j in RC4 Key Scheduling. Proceedings of the 18th International Symposium on Applied Algebra, Algebraic Algorithms and Error Correcting Codes (AAECC), 8–12 June 2009, Tarragona, Spain, pages 137–148, vol. 5527, Lecture Notes in Computer Science, Springer.</ref> Subhamoy Maitra and Goutam Paul<ref>Subhamoy Maitra and Goutam Paul. New Form of Permutation Bias and Secret Key Leakage in Keystream Bytes of RC4. Proceedings of the 15th Fast Software Encryption (FSE) Workshop, 10–13 February 2008, Lausanne, Switzerland, pages 253–269, vol. 5086, Lecture Notes in Computer Science, Springer.</ref> also showed that the Roos-type biases still persist even when one considers nested permutation indices, like {{mono|S[S[i]]}} or {{mono|S[S[S[i]]]}}. These types of biases are used in some of the later key reconstruction methods for increasing the success probability.