Entrada # 7

Reporte # 2

Blocks Ciphers

First shall begin with a little explanation about what this is.

Consists of a symmetric key cipher (in which the same key is used to encrypt and decrypt messages) that operates on groups of bits of fixed length, called blocks, applying a transformation invariant.

When performing encryption, this takes a block of plain text as input and produces a ciphertext of the same size as the original text.

For this week is to choose one of the existing encrypted and explain.

Akelarre Cipher

Who and When Proposing

Was design for G. Álvarez Marañón, D. Guía Martínez, F. Montoya Vitini, A. Peinado Domínguez in 1996.

Mejoras que tenía de los ya existentes

Akelarre combines the best of this cipher's:

      IDEA.- Handles multiple arithmetic.
      RC5.- Rotation of Keys.

This encryption aims to be a strong encryption system most efficient.

How it Works

First we have a define the next points:


Variable numbers of rounds

•      The autors claim the 4 rounds is more safe.
•      Although the reality is unsafe for any number of rounds!

Block length is 128 bits

Key length can be any multiple of 64 bits

•      The common lenght of the key is the 128 bits.

Lots of blocks subkey: 13R + 8

• Every of the subkeys its a word of 32 bits.

Mod also employs 232 and XOR

Adding rotation (AR) structure

Proceso del Cifrado

For the encryption:

• Inputs data, this we have transformating for your use
• Round 0,1,2, ..., R-1
• Cifred data

Explain of more extensing form:

Taking: 


(A0, A1, A2, A3), this would be the input to round r.
(B0, B1, B2, B3), the output would rotation keys.


Then Apply the struct of Akelarre
(B0, B1, B2, B3) = (A0, A1, A2, A3) <<<<
Where "<<<" is left rotation and , this means bits i thru j (inclusive) of X

• Recall, the bits enumerating the left to right, started in 0

Explain of visual form:

Where:

• W = X
• W1 make first
• Rotate 31 bits, with 1 bit fixed

Taking:

(T0 ,T1), output would AR structure

(T0 ,T1) = AR(B0 ⊕ B2, B1 ⊕ B3), indicating the input values ​​and which has the form AR obtain these.

Later: 

(D0, D1, D2, D3), output would round r.

Then:

(D0, D1, D2, D3) = (B0⊕T1, B1⊕T0, B2⊕T1, B3⊕T0)

One Time to Finished This:

The Block (D0, D1, D2, D3) whold:

• The entrance of the next round.
• If the last one, whold the output of all the process.

For the decryption process would use the same process only data that would introduce a little different.

Math Type which is based

As based on IDEA uses XOR (⊕) combined with rotation values, and modular arithmetic.

Example

The following is a problem which show difficulties if used have certain values ​​in this.

-------------------------------------------------------------------------------------------------------------------

Only to start:

• z is K in the explication.

Given X = (0x53,0x8d,0x86,0x80), Y = (0x74,0x21,0x9c,0xca):

Create an equation, substituting in the values for x and y:

(0x53-z5) ^ 0x86 ^ z7 = (0x74 + z1) ^ 0x9c ^ z3

Starting with the low-order bit (denoted zi[0]), determine which of the following bit combinations solve the above equation:

(z5[i],z1[i],z3[i]^z7[i]) = ((0,0,0),(0,0,1),...,(1,1,0),(1,1,1))

Provided sufficient plaintext-ciphertext pairs, it should theoretically be possible to uniquely determine the values of the unknown subkeys using this technique.

In order to solve for the unknown plaintext, we need to solve the below equation:

We know the entire right-hand side of the equation and z1 on the left-hand side.

Given sufficient redundancy, it is possible to determine the values of x1 and x3. The papers we read did not go into detail about how to perform this recovery.

Determining z1...z8:

Tried multiple approaches that either resulted in hundreds of potential subkey values, or did not find a single subkey value

           Bit-by-bit as described

                           Resulted in hundreds of matches

           Bit-by-bit, taking carry bits into consideration

                           Resulted in zero matches

           Byte-by-byte bruteforce attack

                           Worked if the input size was a single byte, but did not work otherwise

-------------------------------------------------------------------------------------------------------------------

Let

A = (A0, A1, A2, A3), be input to round r
U = (U0, U1, U2, U3), be result of rotation
T = (T0, T1), be output of AR structure
B = (B0, B1, B2, B3), be output of round r

Denote A = (a0 ,a1,…,a127)

• And similarly for U,T,B

Let l be size of keyed rotation

Then U = (A <<< l) and (B0, B1, B2, B3) = (U0⊕T1, U1⊕T0, U2⊕T1, U3⊕T0)

It follows that B0⊕B2 = U0⊕U2 and B1⊕B3 = U1⊕U3

AR structure has vanished!

The crucial observation for attack

Atacks Y/O Vulnerabilities

Akelarre shows that your design is complicated encryption.

An attack is conceptually simple, but the details are not so simple.

There is an attack in the year 1997, using Ciphertext-only attack.

It therefore proves to be very vulnerable to attacks.

References:

http://www.schneier.com/paper-akelarre.pdf
http://es.wikipedia.org/wiki/Akelarre_(cifrado)
http://www.sacconference.org/proc/SAC_96_002.pdf
http://es.wikipedia.org/wiki/Cifrado_por_bloques
http://en.wikipedia.org/wiki/Akelarre_(cipher)
http://cs.sjsu.edu/~stamp/crypto/PowerPoint_PDF/12_Akelarre.pdf