RC4

What is RC4

• RC4 designed in 1987 by RSA (Ron Rivest, Adi Shamir, and Leonard Adleman) .
• A symmetric key encryption algorithm .
• Stream Cipher .

​

​

​

A symmetric key encryption algorithm

• Symmetric-key algorithms are a class of algorithms are a class of algorithms for cryptography are a class of algorithms for cryptography that use trivially related, often identical, cryptographic keys for both decryption and encryption.
• Types of symmetric-key algorithms

1- stream ciphers

2- block ciphers

Stream Cipher

• While block ciphers operate on large blocks of data, stream ciphers typically operate on smaller units of plaintext, usually bits or bytes .
• A stream cipher generates what is called a key stream (a sequence of bits used as a key).
• Encryption is accomplished by combining the key stream with the plaintext, usually with the bitwise XOR operation .

​

​

​

​

11001100 plaintext

01101100 key stream

10100000 Cipher text

​

RC4 Block Diagram

​

​

​

How does it work ?

1. Initialize an array of 256 bytes.
2. Run the Key Scheduling Algorithm (KSA) on them.
3. Run the Pseudo-Random Generation Algorithm (PRGA) on the (KSA) output to generate Key stream.
4. XOR the data with a key stream.

​

​

Initialization of array

• [S] .. To begin, the entries of S are set equal to the values from 0 through 255 in ascending order; that is; S[0] = 0, S[1] = 1,..., S[255] = 255.
• [T] .. A temporary vector, T, is also created.
• [K] .. Array of bytes of Secret Key.
• [key len] .. Length of (K)

​

​

for i = 0 to 255

do

S[i] = i;

T[i] = K[i mod keylen];

​

Key Scheduling Algorithm

• Next we use T to produce the initial permutation of (S)

​

​

​

​

• Because the only operation on S is a swap, the only effect is a permutation. S still contains all the numbers from 0 through 255.

​

​

j = 0;

for i = 0 to 255

do

j = (j + S[i] + T[i]) mod 256;

Swap (S[i], S[j]);

​

Pseudo-Random Generation Algorithm

• Once the S vector is initialized, the input key is no longer used.

​

​

​

i, j = 0;

for (int x = 0; x < byteLen; x++)

do

i = (i + 1) mod 256;

j = (j + S[i]) mod 256;

Swap (S[i], S[j]);

t = (S[i] + S[j]) mod 256;

k = S[t];

​

Pseudo-Random Generation Algorithm

RC4

Security of RC4

• Bit-flipping attack
• Roos' Biases and Key Reconstruction from Permutation
• Biased Outputs of the RC4
• Fluhrer, Mantin and Shamir attack
• Klein's Attack
• Combinatorial problem

Bit-flipping attack

• A bit-flipping attack is an attack on a cryptographic is an attack on a cryptographic cipher is an attack on a cryptographic cipher in which the attacker is an attack on a cryptographic cipher in which the attacker can change the ciphertext is an attack on a cryptographic cipher in which the attacker can change the ciphertext in such a way as to result in a predictable change of the plaintext is an attack on a cryptographic cipher in which the attacker can change the ciphertext in such a way as to result in a predictable change of the plaintext, although the attacker is not able to learn the plaintext itself. Note that this type of attack is not—directly—against the cipher itself (as cryptanalysis is an attack on a cryptographic cipher in which the attacker can change the ciphertext in such a way as to result in a predictable change of the plaintext, although the attacker is not able to learn the plaintext itself. Note that this type of attack is not—directly—against the cipher itself (as cryptanalysis of it would be), but against a particular message or series of messages. In the extreme, this could become a Denial of service attack against all messages on a particular channel using that cipher.
• The attack is especially dangerous when the attacker knows the format of the message. In such a situation, the attacker can turn it into a similar message but one in which some important information is altered. For example, a change in the destination address might alter the message route in a way that will force re-encryption with a weaker cipher, thus possibly making it easier for an attacker to decipher the message.
• When applied to digital signaturesWhen applied to digital signatures, the attacker might be able to change a promissory note stating "I owe you $10.00" into one stating "I owe you $10000".

​

Roos' Biases and Key Reconstruction from Permutation

• In 1995, Andrew Roos experimentally observed that the first byte of the keystream is correlated to the first three bytes of the key and the first few bytes of the permutation after the KSA are correlated to some linear combination of the key bytes. These biases remained unproved until 2007, when Paul, Rathi and Maitra proved the keystream-key correlation and Paul and Maitra proved the permutation-key correlations. The latter work also used Roos' 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 IV. 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 done on key reconstruction from RC4 internal states. In another work, Maitra and Paulshowed that the Roos type biases still persist even when one considers nested permutation indices, like S[S[i]] or S[S[S[i]]]. These types of biases are used in some of the later key reconstruction methods for increasing the success probability.

Biased Outputs of the RC4

• The keystream generated by the RC4 is biased in varying degrees towards certain sequences. The best such attack is due to Itsik Mantin and Adi Shamir who showed that the second output byte of the cipher was biased toward zero with probability 1/128 (instead of 1/256). This is due to the fact that if the third byte of the original state is zero, and the second byte is not equal to 2, then the second output byte is always zero. Such bias can be detected by observing only 256 bytes

Fluhrer, Mantin and Shamir attack

• In 2001, a new and surprising discovery was made by FluhrerIn 2001, a new and surprising discovery was made by Fluhrer, MantinIn 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 key stream 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 analyzing a large number of messages encrypted with this key. This and related effects were then used to break the WEPThis and related effects were then used to break the WEP ("wired equivalent privacy") encryption used with 802.11This and related effects were then used to break the WEP ("wired equivalent privacy") encryption used with 802.11 wireless networksThis 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.11iThis 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.

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 TewsIn 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 WeinmannIn 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 Pychkine used this analysis to create aircrack-ptw, a tool which cracks 104-bit RC4 used in 128-bit WEP in under a minute 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 MantinA 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 in the next 256 rounds. This conjecture was put to rest in 2004 with a formal proof given by Souradyuti Paul and Bart Preneel.

RC4-based cryptosystems

• WEP
• WPA (default algorithm, but can be configured to use AES-CCMP instead of RC4)
• Bit Torrent protocol encryption
• Microsoft Point-to-Point Encryption
• Secure Sockets Layer (optionally)
• Secure shell (optionally)
• Remote Desktop Protocol
• Kerberos (optionally)
• SASL Mechanism Digest-MD5 (optionally)

​

RC5

Outline

• Introduction (Feistel Networks)
• What is RC5
• Parameterization
• Algorithm
• The security of RC5
• Conclusion

​

Introduction (Feistel Networks)

If you don’t know where to go all roads will get you there.

Feistel Network

• block cipher is a symmetric key cipher operating on fixed-length groups of bits, called blocks.
• One of the most structures used in construction block ciphers is Feistel Network Structure

​

​

Feistel Network

• Feistel networks were first seen commercially in IBM's Lucifer cipher, designed by Horst Feistel and Don Coppersmith.
• Feistel networks gained respectability when the U.S. Federal Government adopted the DES (a cipher based on Lucifer, with some changes NSA).
• RC5 is like a Feistel Network structure.

Feistel Network - Construction Details

Recap

• Introduction (Feistel Networks)
• What is RC5
• Parameterization
• Algorithm
• The security of RC5
• Conclustion

​

What is RC5

What is RC5

• RC5 is a block cipher notable for its simplicity. Designed by Ronald Rivest in 1994^.
• RC stands for "Rivest Cipher", or alternatively, "Ron's Code.
• Rivest announced also RC2 and RC4 and now there is RC6 which is The Advanced Encryption Standard (AES) candidate (RC6 was based on RC5).

Features

• Symmetric block cipher (Like Feistel Network Structure)
• the same secret cryptographic key is used for encryption and decryption
• Suitable for hardware and software
• It uses only computational primitive operations commonly found on typical microprocessors
• Fast
• Cause it uses Word-Oriented operations

​

Features count.

• Adaptable to processors of different word lengths
• For example with 64 bit processor RC5 can exploit their longer work length
• Therefore the number w of bits in a word is a parameter of RC5, different choices of this parameter results different algorithms.
• Variable number of rounds
• The user can explicitly manipulate the trade-off between higher speed and higher security.
• So the number of rounds i is a second parameter of RC5

​

Features count.

• Variable length cryptographic key
• The user can choose the level of security appropriate for his application the key length b in bytes is thus a third parameter of RC5
• Simple
• It is simple to implement, This simplicity makes it more interesting to analyze and evaluate, so that the cryptographic strength can be more rapidly determined
• Low memory requirements
• So it is easily implemented on devices with restricted memory

​

Features count.

• Data-dependent rotations
• RC5 highlight the use of data-dependent rotations and encourage the assessment of the cryptographic strength data-dependent can provide

​

Features - Highlight

• Data-dependent rotations
• Variable block size
• Variable number of rounds
• Variable key size

​

​

Recap

• Introduction (Feistel Networks)
• What is RC5
• Parameterization
• Algorithm
• The security of RC5
• Conclusion

​

Parameterization

Parameterization

Parameterization count.

• RC5 algorithm example: RC5-32/16/7
• similar to DES
• Two 32-bit word inputs and outputs
• 16 rounds
• 7-byte(56-bit) secret key
• Choices for w and r
• speed vs. security
• Choosing larger number of rounds provides an increased level of security

​

​

Dropped parameters

• RC5 Dropped parameters
• The default is 32/12/ 7 for 32 bit words
• The default is 64/16/7 for 64 bit words
• So if any parameter is dropped use the corresponding default parameter
• Examples
• RC5-32 Means 32/12/7
• RC5-32, 9 Means 32/9/ 7
• RC5-64 Means 64/16/7

​

Notations and Primitive operations

Recap

• Introduction (Feistel Networks)
• What is RC5
• Parameterization
• Algorithm
• The security of RC5
• Conclusion

​

Algorithm

Algorithm

• The are three components of RC5
• Key expansion algorithm
• Encryption algorithm
• Decryption algorithm

​

Encryption

Encryption

A = A + S[0];

B = B + S[1];

​

for i = 1 to r do

A = ((A ⊕ B) <<< B) + S[2*i];

B = ((B ⊕ A) <<< A) + S[2*i + 1];

A <<< B

Bits in A are rotated to left by the amount specified by lower log2(w) bits in B

Decryption

Decryption

for i = r downto 1 do

B = ((B - S[2*i +1]) >>> A) ⊕ A;

A = ((A - S[2*i]) >>> B) ⊕ B;

​

B = B - S[1];

A = A - S[0];

A >>> B

Bits in A are rotated to right by the amount specified by lower log2(w) bits in B

Encryption and Decryption

Key Expansion

• RC5 performs some operations on the secret key to generate a total of t sub keys, which are stored in S array, S[0],S[1], …, S[t-1]
• The key expansion algorithm consists of two constants (Magic numbers) and three simple algorithm parts
• Step-1: Convert secret key bytes to words
• Step-2: Initialize sub key array S (S[0], S[1], …, S[t-1])
• Step-3: Mix the secret key into sub key array S

​

RC5

Key Expansion

The magic constants

• In key expansion, magic constants are used
• Pw = Odd((e - 2)2w); e=2.718281828…. (base of natural logarithms)
• Qw = Odd((φ - 1)2w); φ=1.618033988…. (golden ratio = (1+sqr(5))/2)
• Odd(x): odd integer nearest to x
• Example

​

w 16 32 64

P_w B7E1 B7E15163 B7E151628AED2A6B

Q_w 9E37 9E3779B9 9E3779B97F4A7C15

Step-1: Convert secret key bytes to words

Copy the Key into new array L of Words with size equal c

Any unfilled byte positions of L are zeroed

In case b = c = 0 we reset c =1 and set L[0] = 0

​

Step-2: Initialize sub key array S

• create an expanded key table, S[0...t-1]
• has t entries, t = 2(r + 1) w-bit words
• Initialize array S

S[0] = P_w;

for i = 1 to t - 1 do

S[i] = S[i - 1] + Q_w;

​

Step-3: Mix the secret key into sub key array S

• Mix the secret key into table, S

i = j = 0; A = B = 0;

do 3 * max(t, c) times:

A = S[i] = (S[i] + A + B) <<< 3;

B = L[j] = (L[j] + A + B) <<< (A + B);

i = (i + 1) mod(t);

j = (j + 1) mod(c);

​

Key Expansion Algorithm

Recap

• Introduction (Feistel Networks)
• What is RC5
• Parameterization
• Algorithm
• The security of RC5
• Conclusion

​

The security of RC5

The security of RC5

• Exhaustive Search
• Differential cryptanalysis
• Linear cryptanalysis
• Timing Attacks

Exhaustive Search

• RC5-32/r/b allows
• a maximum of 2040 secret key bits
• a maximum of 25(2r + 2) expanded key table bits
• Choosing large values for r and b can prevent exhaustive attacks

Differential cryptanalysis

• Pioneered by Biham and Shamir
• It has a quite evolutionary effect on the design and analysis of block ciphers
• The basic Idea
• Two plaint text are chose with a certain difference P` (The difference here is measured by xor but for other cipher alternative measure may be applied)
• The two plaintexts are enciphered to give two cipher texts such that their difference C`
• Such a pair (P` , C`) is called a characteristic
• Depending on the cipher and the analysis the behavior of this characteristics can be useful in deriving certain bit of the key

Linear cryptanalysis

• Introduced By Matsui.
• The basic idea is
• to find relations among certain bits of plaintext, cipher text and key
• Such as relation is called linear approximation which can be used to obtain information about the key
• Becomes impractical for r > 6

Differential and Linear attack

Timing Attacks

• Developed by Kocher
• The opponent can obtain some information about the secret key by recording and analyzing the time used for cryptographic operations that involve the key.
• Kocher found that RC5 may be subject to Timing attack if RC5 is implemented on platforms for which the time for computing a single rotation is proportional to the rotation amount
• RC5 can easily implemented to make the total time is data-independent (ex by computing the rotation of t bits using left-shift of t bits and right shift of w-t bits)

​

Conclusion

• Provides good security against the four main attacks
• Simple encryption/decryption algorithms
• RC5 is relatively is still under scrutiny by other cryptanalysis attack

Thank you for your

attention