Block Ciphers: RC5

Hi!, for this week we need to choose a block cipher to investigate and also put an example, so, I chose RC5, is a block cipher quick and easy, designed by Ronald Rivest in 1995 in the MIT's Laboratory of Computer Science, this encryption algorithm, works for hardware and software, use as a parameters the length of the word, the number of iterations and the length of the private key.

RC5 has the following characteristics:

• Is a symmetric cipher, both the encryption and decryption uses the same private key.
• It works in both, hardware and software because RC5 uses only elementary operations.
• Is adaptable to processors with different word lengths, for example, if we have a 64-bit processor, RC5 can use the entire length of the word.
• Has an iterative structure with a variable number of iterations.
• Has a cryptographic key variable length, this allows that the user can choose the desired level of security for your application and solves problems related to the export of cryptographic algorithms that use more than 40 bits keys.
• It is easy to implement.
• A request has limited memory, so it can be easily implement on devices with small memory.
• Provides a high safety
• Using data-dependent rotations, in which words are rotated cyclically.

One of the fundamental characteristics of RC5 is that uses three parameters, W, R, B, if two users exchange messages using RC5 for encryption must agree with that parameters.

• W: is the word length in bits. RC5 uses basically values such as 16, 32 and 64 in W, We need to know that RC5 cipher blocks of 2 words use the plaintext and the ciphertext uses 2W bits. so if we have a W = 32, the blocks of plaintext and ciphetext are of 64 bits.

• R: represents the number of iterations of the algorithm and varies from 0 to 255. the security level of the cipher depends from this parameter: the larger choose R, the better the security.

• B: is the length of the private key K. Allowed values of b are 0, 1, …, 255.

For convenience, we can use RC5-W/R/B to denote those parameters, for example, the algorithm RC5-32/16/10 uses 32-bits words, leaving 16 iterations of the algorithm and has a key of 80 bits (10 bytes). Not necessarily all the parameters must be specified. We can omitted the last parameter or can be omitted the last two. For example, with RC5-32, is indicated the RC5 algorithm that uses 32-bits words, without any reference to the number of iterations and the length of the key.

RC5 uses only the following three operations and their inverses:

• Sum of words module W/8, this operation is denoted by +, the inverse operation, subtraction, is denoted by -.

• Bitwise exclusive-OR, denoted XOR (The reverse is itself).

• Rotation to the left of words. The cyclical rotation of the word x of y bits to the left is denoted with 2^w y is considered the modulo w, so when w is a power of two, are need only x << y low order bits of y to determine the number of position to rotate. the reverse operation is to the right.

These operations are supported efficiently by many processors, the main feature of RC5 is the use of data-dependent rotations, rotations dependent on the plaintext and the key, also, the rotations are the only nonlinear operator in RC5.

The RC5 cipher contains the three following procedures:

• Key expansion algorithm
• Encryption algorithm
• Decryption algorithm

The plaintext input to RC5 consists of two w-bit words, contained in the registers A and B, also uses a "expanded key table" containing t = 2(r+1), obtained from the user's private key K.

The key expansion algorithm, use the secret key K, fills the key table S with t = 2(r+1) binary words, use also two "magic constants" P and Q. which are defined as a W for arbitrary.

Pw = ODD((e-2)2^w)
Qw = ODD((phi-1)2^w)

where e = 2.7182... , phi = 1.618... and ODD(x) is the odd integer closest to x.

For w = 16, 32, 64, have the following values in hexadecimal.

• Pw 16-bit = B7 E1
• Pw 32-bit = B7 E1 51 63
• Pw 64-bit = B7 E1 51 62 8A ED 2A 6B

• Qw 16-bit = 9E 37
• Qw 32-bit = 9E 37 79 B9
• Qw 64-bit = 9E 37 79 B9 7F 4A 7C 15

The key expansion algorithm is divided into two steps:

Conversion of the secret key from bytes to words. The B-byte secret key K [0 .. B-1] is copied into an array L [0 … c-1] of c words. each w-bit, so in this way, in L[0] is stored the first byte of the key and L[c-1] contains, if  necessary, of the null bits, added to make the key size equal to a certain number of words, namely 8*b must be a multiple of W. 

So, the size of the array L[] is c = [8*b/w]

Creation of the expanded key table, the array S is initialized by using an arithmetic progression modulo w/8 determined by magic constants, 

S[0] = Pw 

for i = 1 to 2r+1 do  

        S[i] = S[i-1]+Qw

Then the algorithm performs the actual expansion of the key processing arrays S and L in the following way:

X ,  Y = 0
i, j = 0
do 3*max(x, 2r+1) times:
X = S[i] = (S[i]+X+Y) << 3
Y = L[j] = (L[j]+X+Y) << (X+Y)
i = (i+1) mod (2r+1)
j = (j+1) mod c

So in S[0, …, 2*r + 1] contains the key will be scheduled. The expansion function key can be considered one way. It is not easy to determine K from S.

The encryption algorithm takes as input the plaintext stored in two registers A and B, each of w bits, the number r of iterations to be performed and the key, stored in S[0, …., 2*r + 1], returns the cipher text in the registers A and B, the algorithm in pseudocode:

A = A + S[0]
B = B + S[1]
for i = 1 to r do:
A = ((A XOR B) << B) + S[2i]
B = ((B XOR A) << A) + S[2i+1] 

The output is contained in the registers A and B.

We observe that RC5, at each iteration, updates both registers A and B. During each iteration of the DES, however, only half word is actually transformed, while the other half remains unchanged, Therefore an iteration on RC5 "is equivalent" in two iterations of the DES.

The decryption routine is easily derived from the encryption routine: just do the reverse in reverse order:

for i = r downto 1 do:
B = ((B-2[2*i+1] >> A) XOR A
A = ((A - S[2i]) >> B) XOR B
      B = B - S[1]
      A = A - S[0]

The output is stored in the registers A and B containing the plaintext.

The RC5 algorithm is extremely simple. Its cryptographic strength depends heavily on the use of data-dependent rotations. Sice they depend on the input data, do not allow to collect statistics and avoid attacks of differential cryptanalysis and linear cryptanalysis.

I tried to understand the vulnerabilities of the RC5, I saw that if we have two similar plaintext blocks can give us results very similar, so I put the example about that:

This is first iteration and we already have the table expansion.

A = A XOR B 

A = A << B 

A = A + S[i] 

B = B XOR A 

B = B << A 

B = B + S[i+1]

A = 11111101100001001101111001100011
B = 10110001100110011010111100110001
   

Now, we can made the first 3 steps.

A = A XOR B

A =
      11111101100001001101111001100011 XOR
      10110001100110011010111100110001
      ---------------------------------------------------------
      11001100000111010111000101010010


A = 11001100000111010111000101010010

A = 11111101100001001101111001100011 << 10110001100110011010111100110001

A = 11100010101001011001100000111010

A = A + S[i]

A = 
   11100010101001011001100000111010 
+ 01110001100111101110010011011001
    --------------------------------------------------------
    01110001000001011011001101100001

A = 1110001000001011011001101100001

Then, imagine that we have a A and B just only one letter different.

A = 11111101100001001101111001100011
B =  00110001100110011010111100110001

Now, we can made the next 3 steps.

A = A XOR B

A = 11111101100001001101111001100011  XOR
       00110001100110011010111100110001
    -----------------------------------------------------------
       11001100000111010111000101010010

A = A << B

A = 11001100000111010111000101010010 << 00110001100110011010111100110001

A = 11100010101001011001100000111010

A = A + S[i]

A = 11100010101001011001100000111010
     + 01110001100111101110010011011001
     ----------------------------------------------------------
       001110001000001101011001101100001

A = 1110001000001101011001101100001


Now, compare A.

A_1 = 1110001000001011011001101100001
A_2 = 1110001000001101011001101100001

You can see that we have two plaintext blocks very similar, if we have the ciphertext very similar, we have a problem because an attacker can see that ciphertext blocks and check similarities to have things for the plain text.

So it is important to know that we have issues that involves vulnerabilities but we can improve put, as I explain in the algorithm,  put a lager R that represents the number of iterations of the algorithm and varies from 0 to 255. the security level of the cipher depends from this parameter: the larger choose R, the better the security.

Bibliography.
* The RC5 Encryption Algorithm MIT, Ronald Rivest link