FACTOID # 16: In the 2000 Presidential Election, Texas gave Ralph Nader the 3rd highest popular vote count of any US state.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
RELATED ARTICLES
People who viewed "RC4" also viewed:
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


In cryptography, RC4 (also known as ARC4 or ARCFOUR) is the most widely-used software stream cipher and is used in popular protocols such as Secure Sockets Layer (SSL) (to protect Internet traffic) and WEP (to secure wireless networks). While remarkable in its simplicity, RC4 falls short of the high standards of security set by cryptographers, and some ways of using RC4 can lead to very insecure cryptosystems (an example being WEP). It is not recommended for use in new systems. However, some systems based on RC4 are secure enough for practical use.CITATION NEEDED The German Lorenz cipher machine, used in World War II for encryption of very high-level general staff messages Cryptography (or cryptology; derived from Greek κρυπτός kryptós hidden, and the verb γράφω gráfo write or λεγειν legein to speak) is the study of message secrecy. ... The operation of A5/1, a LFSR-based stream cipher used to encrypt mobile phone conversations. ... Secure Sockets Layer (SSL) and Transport Layer Security (TLS), its successor, are cryptographic protocols which provide secure communications on the Internet. ... Wired Equivalent Privacy or Wireless Encryption Protocol (WEP) is a scheme to secure IEEE 802. ... There are two different meanings of the word cryptosystem. ... Wired Equivalent Privacy or Wireless Encryption Protocol (WEP) is a scheme to secure IEEE 802. ...

Contents

History

RC4 was designed by Ron Rivest of RSA Security in 1987. While it is officially termed "Rivest Cipher 4", the RC acronym is alternatively understood to stand for "Ron's Code" (see also RC2, RC5 and RC6). Election People This box:      Professor Ronald Lorin Rivest (born 1947, Schenectady, New York) is a cryptographer, and is the Andrew and Erna Viterbi Professor of Computer Science at MITs Department of Electrical Engineering and Computer Science (CSAIL). ... RSA, The Security Division of EMC Corporation (NYSE: EMC), is headquartered in Bedford, Massachusetts, and maintains offices in Ireland, the United Kingdom, Singapore, and Japan. ... In cryptography, RC2 is a block cipher designed by Ron Rivest in 1987. ... RC5 is a block cipher notable for its simplicity. ... In cryptography, RC6 is a symmetric key block cipher derived from RC5. ...


RC4 was initially a trade secret, but in September 1994 a description of it was anonymously posted to the Cypherpunks mailing list[1]. It was soon posted on the sci.crypt newsgroup, and from there to many sites on the Internet. The leaked code was confirmed to be genuine as its output was found to match that of proprietary software using licensed RC4. Because the algorithm is known, it is no longer a trade secret. The name "RC4" is trademarked, however. The current status seems to be that "unofficial" implementations are legal, but cannot use the RC4 name. RC4 is often referred to as "ARCFOUR" or "ARC4" (meaning Alleged RC4, because RSA has never officially released the algorithm), to avoid possible trademark problems. It has become part of some commonly used encryption protocols and standards, including WEP and WPA for wireless cards and TLS. A trade secret is a formula, practice, process, design, instrument, pattern, or compilation of information used by a business to obtain an advantage over competitors within the same industry or profession. ... The cypherpunks comprise an informal group of people interested in privacy and cryptography who originally communicated through the cypherpunks mailing list. ... There are several newsgroups relevant for discussions about cryptography and related issues. ... A trade secret is a formula, practice, process, design, instrument, pattern, or compilation of information used by a business to obtain an advantage over competitors within the same industry or profession. ... “(TM)” redirects here. ... RSA, The Security Division of EMC Corporation (NYSE: EMC), is headquartered in Bedford, Massachusetts, and maintains offices in Ireland, the United Kingdom, Singapore, and Japan. ... Wired Equivalent Privacy or Wireless Encryption Protocol (WEP) is a scheme to secure IEEE 802. ... Wi-Fi Protected Access (WPA and WPA2) is a class of systems to secure wireless (Wi-Fi) computer networks. ... Transport Layer Security (TLS) and its predecessor, Secure Sockets Layer (SSL), are cryptographic protocols that provide secure communications on the Internet for such things as web browsing, e-mail, Internet faxing, instant messaging and other data transfers. ...


The main factors which helped its deployment over such a wide range of applications consisted in its impressive speed and simplicity. Implementations in both software and hardware are very easy to develop.


Description

RC4 generates a pseudorandom stream of bits (a keystream) which, for encryption, is combined with the plaintext using XOR; decryption is performed the same way. (This is similar to the Vernam cipher except that pseudorandom bits, rather than random bits, are used.) To generate the keystream, the cipher makes use of a secret internal state which consists of two parts: A pseudorandom number generator (PRNG) is an algorithm that generates a sequence of numbers, the elements of which are approximately independent of each other. ... In cryptography, a keystream is a stream of random or pseudorandom characters that are combined with a cleartext message to produce an encrypted message (the ciphertext). ... Exclusive disjunction (usual symbol xor) is a logical operator that results in true if one of the operands (not both) is true. ... Gilbert Sandford Vernam (1890–7 February 1960) was a AT&T Bell Labs engineer who, in 1917, invented the stream cipher and later co-invented the one-time pad cipher. ...

  1. A permutation of all 256 possible bytes (denoted "S" below).
  2. Two 8-bit index-pointers (denoted "i" and "j").

The permutation is initialized with a variable length key, typically between 40 and 256 bits, using the key-scheduling algorithm (KSA). Once this has been completed, the stream of bits is generated using the pseudo-random generation algorithm (PRGA). Permutation is the rearrangement of objects or symbols into distinguishable sequences. ... This article refers to the unit of binary information. ... A key is a piece of information that controls the operation of a cryptography algorithm. ... The key-schedule of DES (<<< denotes a left rotation) In cryptography, the so-called product ciphers are a certain kind of ciphers, where the (de-)ciphering of data is done in rounds. The general setup of each round is the same, except for some hard-coded parameters and a part...


The key-scheduling algorithm (KSA)

The key-scheduling algorithm is used to initialize the permutation in the array "S". "keylength" is defined as the number of bytes in the key and can be in the range 1 ≤ keylength ≤ 256, typically between 5 and 16, corresponding to a key length of 40 – 128 bits. First, the array "S" is initialized to the identity permutation. S is then processed for 256 iterations in a similar way to the main PRGA algorithm, but also mixes in bytes of the key at the same time. In cryptography, the key size (alternatively key length) is a measure of the number of possible keys which can be used in a cipher. ... In mathematics, the term identity has several important uses: An identity is an equality that remains true regardless of the values of any variables that appear within it, to distinguish it from an equality which is true under more particular conditions. ...

 for i from 0 to 255 S[i] := i endfor j := 0 for i from 0 to 255 j := (j + S[i] + key[i mod keylength]) mod 256 swap(S[i],S[j]) endfor 

In computing, the modulo operation finds the remainder of division of one number by another. ...

The pseudo-random generation algorithm (PRGA)

The lookup stage of RC4. The output byte is selected by looking up the values of S(i) and S(j), adding them together modulo 256, and then looking up the sum in S; S(S(i) + S(j)) is used as a byte of the key stream, K.
The lookup stage of RC4. The output byte is selected by looking up the values of S(i) and S(j), adding them together modulo 256, and then looking up the sum in S; S(S(i) + S(j)) is used as a byte of the key stream, K.

For as many iterations as are needed, the PRGA modifies the state and outputs a byte of the keystream. In each iteration, the PRGA increments i, adds the value of S pointed to by i to j, exchanges the values of S[i] and S[j], and then outputs the value of S at the location S[i] + S[j] (modulo 256). Each value of S is swapped at least once every 256 iterations. Image File history File links This is a lossless scalable vector image. ... Image File history File links This is a lossless scalable vector image. ...

 i := 0 j := 0 while GeneratingOutput: i := (i + 1) mod 256 j := (j + S[i]) mod 256 swap(S[i],S[j]) output S[(S[i] + S[j]) mod 256] endwhile 

Implementation

Many stream ciphers are based on linear feedback shift registers (LFSRs), which while efficient in hardware are less so in software. The design of RC4 avoids the use of LFSRs, and is ideal for software implementation, as it requires only byte manipulations. It uses 256 bytes of memory for the state array, S[0] through S[255], k bytes of memory for the key, key[0] through key[k-1], and integer variables, i, j, and k. Performing a modulus 256 can be done with a bitwise AND with 255 (or on most platforms, simple addition of bytes ignoring overflow). A linear feedback shift register (LFSR) is a shift register whose input bit is a linear function of its previous state. ... In computer programming, a bitwise operation operates on one or two bit patterns or binary numerals at the level of their individual bits. ...


Here is a simple implementation in Python: Python is a high-level programming language first released by Guido van Rossum in 1991. ...

 class WikipediaARC4: def __init__(self, key = None): self.state = range(256) # Initialize state array with values 0 .. 255 self.x = self.y = 0 # Our indexes. x, y instead of i, j if key is not None: self.init(key) # KSA def init(self, key): for i in range(256): self.x = (ord(key[i % len(key)]) + self.state[i] + self.x) & 0xFF self.state[i], self.state[self.x] = self.state[self.x], self.state[i] self.x = 0 # PRGA def crypt(self, input): output = [None]*len(input) for i in xrange(len(input)): self.x = (self.x + 1) & 0xFF self.y = (self.state[self.x] + self.y) & 0xFF self.state[self.x], self.state[self.y] = self.state[self.y], self.state[self.x] r = self.state[(self.state[self.x] + self.state[self.y]) & 0xFF] output[i] = chr(ord(input[i]) ^ r) return ''.join(output) if __name__ == '__main__': test_vectors = [['Key', 'Plaintext'],  ['Wiki', 'pedia'],  ['Secret', 'Attack at dawn']] for i in test_vectors: print WikipediaARC4(i[0]).crypt(i[1]).encode('hex').upper() 

Test vectors

These test vectors are not official, but convenient for anyone testing their own RC4 program. The inputs are ASCII, the output is in hexadecimal. Image:ASCII fullsvg There are 95 printable ASCII characters, numbered 32 to 126. ... In mathematics and computer science, hexadecimal, base-16, or simply hex, is a numeral system with a radix, or base, of 16, usually written using the symbols 0–9 and A–F, or a–f. ...

 RC4( "Key", "Plaintext" ) == BBF316E8D940AF0AD3 RC4( "Wiki", "pedia" ) == 1021BF0420 RC4( "Secret", "Attack at dawn" ) == 45A01F645FC35B383552544B9BF5 

Security

RC4 falls short of the standards set by cryptographers for a secure cipher in several ways, and thus is not recommended for use in new applications.


The keystream generated by RC4 is slightly biased in favour of certain sequences of bytes. The best attack based on this bias is due to Fluhrer and McGrew, which will distinguish the keystream from a random stream given a gigabyte of output.


RC4 does not take a separate nonce alongside the key. Such a nonce is, in general, a necessary requirement for security, so that encrypting the same message twice produces a different ciphertext each time. One approach to addressing this is to generate a "fresh" RC4 key by hashing a long-term key with a nonce. However, many applications that use RC4 simply concatenate key and nonce; RC4's weak key schedule then gives rise to a variety of serious problems. In security engineering, a nonce is a number used once. ... In cryptography, a cryptographic hash function is a hash function with certain additional security properties to make it suitable for use as a primitive in various information security applications, such as authentication and message integrity. ... In security engineering, a nonce is a number used once. ... The key-schedule of DES (<<< denotes a left rotation) In cryptography, the so-called product ciphers are a certain kind of ciphers, where the (de-)ciphering of data is done in rounds. The general setup of each round is the same, except for some hard-coded parameters and a part...


Fluhrer, Mantin and Shamir attack

Main article: Fluhrer, Mantin, and Shamir attack

In 2001 a new and surprising discovery was made by Fluhrer, Mantin and Shamir: over all possible RC4 keys, the statistics for the first few bytes of output keystream are strongly non-random, leaking information about the key. If the long-term key and nonce are simply concatenated to generate the RC4 key, this long-term key can be discovered by analysing a large number of messages encrypted with this key. This and related effects were then used to break the WEP ("wired equivalent privacy") encryption used with 802.11 wireless networks. This caused a scramble for a standards-based replacement for WEP in the 802.11 market, and led to the IEEE 802.11i effort and WPA. In cryptography, the Fluhrer, Mantin, and Shamir attack allows an attacker to recover the key in an RC4 encrypted stream from a large number of messages in that stream. ... This article does not cite any references or sources. ... Wired Equivalent Privacy or Wireless Encryption Protocol (WEP) is a scheme to secure IEEE 802. ... IEEE 802. ... While the term wireless network may technically be used to refer to any type of network that is wireless, the term is most commonly used to refer to a telecommunications network whose interconnections between nodes is implemented without the use of wires, such as a computer network (which is a... IEEE 802. ... Wi-Fi Protected Access (WPA and WPA2) is a class of systems to secure wireless (Wi-Fi) computer networks. ...


Cryptosystems can defend against this attack by discarding the initial portion of the keystream (say the first 1024 bytes) before using it.


Klein's Attack

In 2005, Andreas Klein presented an analysis of the RC4 stream cipher showing more correlations between the RC4 keystream and the key. Erik Tews, Ralf-Philipp Weinmann, and Andrei Pyshkin used this analysis to create aircrack-ptw, a tool which cracks 104-bit RC4 used in 128-bit WEP in under a minute[2] Whereas the Fluhrer, Mantin, and Shamir attack used around 10 million messages, aircrack-ptw can break 104-bit keys in 40,000 frames with 50% probability, or in 85,000 frames with 95% probability.


Combinatorial problem

A combinatorial problem related to the number of inputs and outputs of the RC4 cipher was first posed by Itsik Mantin and Adi Shamir in 2001, whereby, of the total 256 elements in the typical state of RC4, if x number of elements (x ≤ 256) are only known (all other elements can be assumed empty), then the maximum number of elements that can be produced deterministically is also x in the next 256 rounds. This conjecture was put to rest in 2004 with a formal proof given by Souradyuti Paul and Bart Preneel. This article does not cite any references or sources. ... Souradyuti Paul in an Indian cryptologist (PhD, 2006, Catholic University of Leuven). ... Bart Preneel is a Belgian cryptographer and cryptanalyst. ...


RC4-based cryptosystems

Where a cryptosystem is marked with "(optionally)", RC4 is one of several ciphers the system can be configured to use. Wired Equivalent Privacy or Wireless Encryption Protocol (WEP) is a scheme to secure IEEE 802. ... Wi-Fi Protected Access (WPA and WPA2) is a class of systems to secure wireless (Wi-Fi) computer networks. ... CipherSaber is a symmetric encryption system based on RC4 that is simple enough that novice programmers can memorize the algorithm implement it from scratch, yet supposedly strong. ... Protocol encryption (PE), Message stream encryption (MSE), or Protocol header encrypt (PHE) are features of some BitTorrent clients that attempt to make BitTorrent traffic hard to throttle. ... RFC 3078 - Microsoft Point-To-Point Encryption (MPPE) Protocol Network Working Group G. Pall Request for Comments: 3078 Microsoft Corporation Category: Informational G. Zorn Updates: 2118 cisco Systems March 2001 Microsoft Point-To-Point Encryption (MPPE) Protocol Status of this Memo This memo provides information for the Internet community. ... Secure Sockets Layer (SSL) and Transport Layer Security (TLS), its successor, are cryptographic protocols which provide secure communications on the Internet. ... Secure Shell or SSH is a network protocol that allows data to be exchanged over a secure channel between two computers. ... Kerberos is the name of a computer network authentication protocol, which allows individuals communicating over an insecure network to prove their identity to one another in a secure manner, and also a suite of free software published by Massachusetts Institute of Technology (MIT) which implements this protocol. ... Simple Authentication and Security Layer (SASL) is a framework for authentication and authorization in Internet protocols. ...


See also

eSTREAM is a project to identify new stream ciphers that might become suitable for widespread adoption, organised by the EU ECRYPT network. ... General Designer(s) Roger Needham and David Wheeler First published 1994 Derived from - Cipher(s) based on this design XTEA Algorithm detail Block size(s) 64 bits Key size(s) 128 bits Structure Feistel network Number of rounds variable; recommended 64 Feistel rounds; 32 cycles Best cryptanalysis TEA suffers from... General Designer(s) Roger Needham and David Wheeler First published 1997 Derived from Tiny Encryption Algorithm (TEA) Cipher(s) based on this design - Algorithm detail Block size(s) 64 bits Key size(s) 128 bits Structure Feistel network Number of rounds variable; recommended 64 Feistel rounds; 32 cycles Best cryptanalysis... Encryption Decryption In cryptography, a block cipher is a symmetric key cipher which operates on fixed-length groups of bits, termed blocks, with an unvarying transformation. ... In cryptography, the Advanced Encryption Standard (AES), also known as Rijndael, is a block cipher adopted as an encryption standard by the U.S. government. ...

References

  1. ^ Thank you Bob Anderson. Cypherpunks mailing list (1994-09-09). Retrieved on 2007-05-28.
  2. ^ Erik Tews, Ralf-Philipp Weinmann, Andrei Pyshkin. Breaking 104-bit WEP in under a minute.
  • Scott R. Fluhrer, Itsik Mantin and Adi Shamir, Weaknesses in the Key Scheduling Algorithm of RC4. Selected Areas in Cryptography 2001, pp1 – 24 (PS).
  • Scott R. Fluhrer and David A. McGrew, Statistical Analysis of the Alleged RC4 Keystream Generator. FSE 2000, pp19 – 30 (PDF).
  • Jovan Dj. Golic, Iterative Probabilistic Cryptanalysis of RC4 Keystream Generator. ACISP 2000, pp220 – 233
  • Jovan Dj. Golic, Linear Statistical Weakness of Alleged RC4 Keystream Generator. EUROCRYPT 1997, pp226 – 238 (PDF).
  • Lars R. Knudsen, Willi Meier, Bart Preneel, Vincent Rijmen and Sven Verdoolaege, Analysis Methods for (Alleged) RC4. ASIACRYPT 1998, pp327 – 341 (PS).
  • Itsik Mantin and Adi Shamir, A Practical Attack on Broadcast RC4. FSE 2001, pp152 – 164 (PS).
  • Serge Mister and Stafford E. Tavares, Cryptanalysis of RC4-like Ciphers. Selected Areas in Cryptography 1998, pp131 – 143
  • Ilya Mironov, (Not So) Random Shuffles of RC4. CRYPTO 2002, pp304 – 319
  • Souradyuti Paul and Bart Preneel, Analysis of Non-fortuitous Predictive States of the RC4 Keystream Generator. INDOCRYPT 2003, pp52 – 67 (PDF).
  • Souradyuti Paul and Bart Preneel, A New Weakness in the RC4 Keystream Generator and an Approach to Improve the Security of the Cipher. Fast Software Encryption - FSE 2004, pp245 – 259 (PDF).

The cypherpunks comprise an informal group of people interested in privacy and cryptography who originally communicated through the cypherpunks mailing list. ... This be the Danster with a few new trickoms ahahahahahahahahahahahahah Hace fun life life // January 1 - NAFTA goes into effect. ... is the 252nd day of the year (253rd in leap years) in the Gregorian calendar. ... Year 2007 (MMVII) is the current year, a common year starting on Monday of the Gregorian calendar and the AD/CE era. ... May 28 is the 148th day of the year (149th in leap years) in the Gregorian calendar. ... Selected Areas in Cryptography (SAC) is a series of international cryptography workshops held annually in Canada, every August since 1994. ... EuroCrypt is a conditional access system for Multiplexed Analogue Components-encoded analogue satellite television. ... Lars R. Knudsen Lars Ramkilde Knudsen (born February 21, 1962) is a Danish researcher in cryptography, particularly the design and analysis of block ciphers, hash functions and message authentication codes (MACs). ... Bart Preneel is a Belgian cryptographer and cryptanalyst. ... Together with Joan Daemen, Vincent Rijmen designed the Rijndael block cipher, which was selected as the Advanced Encryption Standard in 2000. ... Asiacrypt (also ASIACRYPT) is an important international conference for cryptography research. ... This article does not cite any references or sources. ... This article or section does not adequately cite its references or sources. ... Crypto is an English prefix that means hidden or secret. The term crypto is also employed as shorthand for the following: Cryptography, the practice of the use of encryption. ... Souradyuti Paul in an Indian cryptologist (PhD, 2006, Catholic University of Leuven). ... Bart Preneel is a Belgian cryptographer and cryptanalyst. ... Indocrypt (also INDOCRYPT) is an annual international cryptography conference held each December since 2000 in India. ... Souradyuti Paul in an Indian cryptologist (PhD, 2006, Catholic University of Leuven). ... Bart Preneel is a Belgian cryptographer and cryptanalyst. ... Fast Software Encryption, often abbreviated FSE, is a workshop for cryptography research, focussed on symmetric-key cryptography with an emphasis on fast, practical techniques, as opposed to theory. ...

External links

RC4

RC4 in WEP


  Results from FactBites:
 
RC4 cipher (413 words)
RC4 is a symmetric key[?], secret key, stream cryptographic cipher designed by Ron Rivest.
RC4 was initially a trade secret, but in September of 1994 an anonymous person reverse engineered it and posted it to the Cypherpunks mailing list.
RC4 is one of the fastest ciphers to be widely used for serious work.
RC4 Page (1025 words)
A Practical Attack on Broadcast RC4, Mantin and Shamir, FSE 2001 - the main result mentioned in this paper, is the discovery of the exceptionally biased behavior of the second word of RC4 streams, which takes 0 with probability that is twice the expected (1/128 instead of 1/256).
Weaknesses in the Key Scheduling Algorithm of RC4, Fluhrer, Mantin and Shamir, SAC 2001 - this paper describes two weaknesses in the KSA of RC4 (the mechanism that extends a short key into a huge key of 1700 bits), denoted as the invariance weakness and the IV weakness.
The IV weakness, is related to a popular mode of operation of stream ciphers, where in order to avoid reusing the key, it is combined with a known vector (denoted the initialization vector or the IV) and this combination is used as the seed to the key stream generator.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m