Steganography Challenge (part 1)

My images :

 

 

MUGI - Stream Cipher

MUGI is a pseudorandom number generator  designed for use as a stream cipher. Was designed by Dai Watanabe, Soichi Furuya, Kazuo Takaragi, Bart Preneel, Hirotaka Yoshida, basing in Panama algorithm which can be used both as a hash function and a stream cipher and is aimed to be suitable for both of software and hardware. Was published in 2002 and has the standard ISO/IEC 18033-4 achieved in 2005.

MUGI is a PRNG with an128-bit secret key K (secret parameter) and an 128-bit initial vector I (public  parameter). It generates 64-bit length random bit string for each round.

The process for encrypt a plaintext using MUGI is:

 

1.- Divide the plaintext data into 64-bit blocks. 

2.- XOR to the output units generated by the secret key K and the initial vector I for each round.

The process for decrypt a plaintext using MUGI is:

 

The decryption can be implemented in the same manner.

The outline of the algorithm is as follows:

Input: Secret key K, Initial vector I, Output size n (units)
Output: Random number sequence Out[i] (0 ≤ i < n)
  

Algorithm 

Initialization

1. First input the secret key K into state a. Then initialize buffer b with running ρ.

2. Add the initial vector I into state a and initialize state a with running ρ.
3. Mix whole internal state with running the update function of MUGI for bringing to completion.

Random number generation
4. Run n rounds update function and output a part of the internal state (64-bit) for each round.

Here the explanation of some of this points/steps:

Input
MUGI has two input as a parameter, one is an 128-bit secret key K and the other is an128-bit initial vector I and is a public parameter. The higher and lower units of K are denoted by K0 and K1 respectively. In the same manner I0 and I1 are used.

State
State a consists of 3 units. Each of them is denoted by a0, a1, a2 inrotation , i.e.
                                      a = [Higher] a0||a1||a2 [Lower]

Buffer
Buffer n consists of 16 units. Each of them is denoted by b0, . . . , b15 inrotation in the same manner as state a.

Random Number Generation
After the initialization of MUGI generates 64-bit random number and transform the internal state at all round. Denote the output at round t as Out[t], thenthe output is given as below:
                                       Out[t] = a(t)

Rhoρ is the update function of state a. It is a kind of target heavy Feistel structure with two F-functions and uses buffer b as a parameter. The function ρ is described as follows:

C1, C2 in the equations above are constants. The F-function of MUGI reuses the components of AES.

Security and Attacks

MUGI is not yet broken.

The security was evaluated according to re-synchronization attack, related-key attack, and linear correlation of an output sequence.

• Randomness: An attacker fixes a secret key and an initial vector, and then he observes the relation in the output sequence.
• Re-synchronization attack: An attacker fixes a secret key, and then he observes the relation between initial vectors and output sequences.
• Related-key: An attacker fixes an initial vector, and then he observes the relation between keys and output sequences. The related-key attack includes observing the relation between keys and initial vectors.

An exhaustive key search require 2¹²⁷ computations on average to find correct key. So an attack is efficient when it costs less than 2¹²⁷ encryptions on average to find the correct key.

In the article, "Analysis of the Non-linear Part of Mugi" by Alex Biryukov and Adi Shamir, they say:
"We study the nonlinear component of this cipher and identify several potential weaknesses in its design. While we can not break the full Mugi design, we show that it is extremely sensitive to small variations."

"For example, it is possible to recover the full 1216-bit state of the cipher and the original 128-bit secret key using just 56 words of known stream and in 2¹⁴ steps of analysis if the cipher outputs any state word which is different than the one used in the actual design."

 

___________________________________________________________________________________

Enlaces:

http://www.hitachi.com/rd/yrl/crypto/mugi/ 

http://en.wikipedia.org/wiki/MUGI

FEAL ( Fast data Encipherment ALgorithm)

Para esta estrada vamos a explicar algunos datos acerca del algoritmo de bloques FEAL (fast data encipherment algorithm).

Historia

Al parecer fue publicado por primera vez en 1987 (la versión FEAL-4) por Akihiro Shimizu y Shoji Miyaguchi, los dos son japonéses, en la Eurocrypt 87.

FEAL-8, se concibió como software para microprocesadores de 8 bits en las tarjetas IC (“Tarjetas con chip”) , el principal impulso de desarrollado de FEAL-8 es que era más rápido que el DES.

Ha habido varias revisiones diferentes de FEAL, aunque todas en cifras de Feistel  y hacen uso de la misma función de redondeo base y operan en bloques de 64-bits. Uno de los primeros diseños actualmente se denomina FEAL-4, tiene cuatro rondas y una clave de 64 bits.

Posteriormente se publicó lo que hoy se conoce como FEAL-8 en 1988 por los mismos autores de FEAL-4, esto debido a que la primera versión mostró debilidades, que se mencionan mas adelante en el apartado de ataques/vulnerabilidades.

Posteriormente debido a la mismas situaciones de vulnerabilidad se vieron en la necesidad de publicar FEAL-N donde N era el numero de rondas y lo elegía el usuario.

Después publicaron tambien FEAL-NX que prácticamente era lo mismo que FEAL-N, solo que eran diferentes en el tamaño de sus llaves/keys/claves, FEAL-N manejaba llaves de 64bits y FEAL-NX llaves de 128bits.

La versión más reciente es FEAL-32X.

¿Cómo funciona?

Como ya se había mencionado, este algoritmo se basa en el tipo de Feistel. 

El inventor de este algoritmo fue Horst Feistel. Feistel usó este método para su algoritmo LUCIFER, en 1970. En 1974 se propone a la NSA (Agencia de la Seguridad Nacional). Como resultado nació DES.

Los principales pasos del funcionamiento de un algoritmo tipo Feistel:

• Dado un mensaje de una longitud N, típicamente 64 bits, 128 bits, etc., se divide en dos bloques de tamaño N/2, A y B.
• El bloque A es una de las entradas de la función F, la otra entrada es una sub clave Ki.
• La función F es una serie de operaciones, lo cual la vuelve una función difícil de modificar.
• El bloque B es una de las entradas de la función XOR, la otra entrada es la salida de la función F.
• Se realizan una serie operaciones con la función F y la clave solo con una de mitades del mensaje A o B, en cada iteración se permuta la mitad usada. Este proceso es repetido n-veces.
• Finalmente se combinan los bloques A y B para producir el texto cifrado. 

Una red de Feistel es un método general de transformación de cualquier función (usualmente llamada función F) dentro de una permutación.

FEAL al basarse en el tipo Feistel, es muy parecido y en lo unico que difieren es en la cantidad de rounds en los que se realizará el proceso. En la imagen se muestra el proceso para la implementacion del FEAL-N.

 

Actualmente se usa FEAL-32X, que como su nombre lo indica se maneja con 32 rounds y llave de 128 bits, además de 64 bits de plaintexts.

 Su esquema general:

 

El generador de claves de este algoritmo crea 40 subclaves, las cuales son separadas en tres grupos.
Para el cifrador las claves desde K0 a K31 alimentan cada una de las rondas en forma ascendente. Las claves K32 a K35 son concatenadas para realizar una operación XOR con el texto plano. Luego de realizar cada una de las rondas las claves K36 a la K39 son concatenadas para realizar una operación XOR con el texto saliente de la última ronda, el resultado de esta operación es el texto cifrado. 

Para el descifrador las claves desde K0 a K31 alimentan cada una de las rondas en orden descendente. Las claves K36 a K39 son concatenadas para realizar una operación XOR con el texto cifrado. Luego de realizar cada una de las rondas las claves K32 a la K35 son concatenadas para realizar una operación XOR con el texto que saliente de la última ronda, el resultado de esta operación es el texto plano.

La función f es equivalente a f (α , β). Donde α y β son entradas y se dividen de la siguiente manera (αi y βi son de 8-bits de longitud). 

S0 y S1 se definen como:
S0 (X1, X2) = Rot2 ((X1 + X2) mod 256)
S1 (X1, X2) = Rot2 ((X1 + X2 + 1) mod 256)

Donde X1 y X2 son bloques de 8 bits y Rot2 (T) es el resultado de un 2-bits izquierda.
α = (α0,α1,α2,α3)     β = (β0,β1)
f = (α0,α1,α2,α3), se calculan en secuencia.
f1= α1 ⊕ β0
f2= α2 ⊕ β1
f1= f1 ⊕ α0
f2= f2 ⊕ α3
f1= S1 (f1 , f2)
f2= S0 (f1 , f2)
f0= S0 (α0 , f1)
f3= S1 (α3 , f2)

Ejemplo:

El algoritmo usará bloques de tamaño 8 caracteres. Tendrá dos vueltas y en cada vuelta realizará una operación de sustitución S y una permutación P sobre la 1ª mitad.
Sustitución: Ci = (Mi +1 ) mod 27
Permutación: Ci = Π3241 (el carácter 1º pasa a la 4ª posición en el criptograma, el 4º a la 3ª, el 2º a la 2ª y el 3º a la 1ª)
Mensaje: M = STAR WARS LA MISION CONTINUA

 n = 27

C = SBTX BUST PJÑT NBJM VÑBJ ÑPUD

Para obtener el plaintext de nuevo, se hace prácticamente lo mismo, a diferencia que ahora el mensaje que se usaría el inicio sería el ciphertext obtenido.

Ataques/Vulnerabilidades

• En artículo, den Boer en  1988 describe un ataque que requiere 100-10000 plaintexts y lo publica en la Eurocrypt 88.
• Sean Murphy en 1990 realizó una mejora al ataque publicado por den Boer y en esta ocasión solo se necesitan 20 plaintext.
• Un criptoanálisis lineal puede romper FEAL-4 con 5 plaintexts (conocidos) y esta vulnerabilidade fue encontrada por Matsui y Yamagishi en 1992.  Estos mismos tipos publicaron vulnerabilidades para FEAL-6 con 100 plaintexts y para FEAL-8 con 2¹⁵ plaintexts.
• Un ataque diferencial puede romper FEAL-N/NX con menos de 31 rondas y fue descubierto por Biham y Shamir en 1991.
• En 1994, Ohta y Aoki presentaron un ataque criptoanalítico lineal para FEAL-8 que usaba 2¹² plaintexts.

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

Enlaces: 

http://en.wikipedia.org/wiki/FEAL

http://info.isl.ntt.co.jp/crypt/eng/archive/index.html#feal

http://groups.google.com/groups?selm=54gq4q%242d7%40scream.auckland.ac.nz