FSM criptoanálisis WEP (II)

Tras la introducción de ayer y la descripción de la relación que existe entre la clave de cifrado maestra y los IVs de la cadena que conforma la entrada al algoritmo KSA, hoy continuaremos con el análisis del algoritmo KSA. El código de éste se puede observar a continuación.

     KSA

     for i = 0 to 255
          S[i] := i
     j := 0
     for i = 0 to 255
          j := (j + S[i] + Clave[i mod “tamañodelaclave"]) mod 256
          Intercambia(S[i], S[j])

Vemos que principalmente esta compuesto por dos bucles; un primer bucle que inicializa un vector de enteros S, muy importate como posteriormente veremos, y una segunda iteración que tiene como objetivo desordenar el vector anterior en función de la clave maestra. En este caso el valor de la variable “tamañodelaclave“ será 5 para 64 bits y 16 para 128 bits. Realicemos una pequeña traza de las tres primeras iteraciones que nos ayudaran a comprender su funcionamiento. En el estado inicial, tras la inicialización del vector S, el valor de las variables es el siguiente:

     Clave[] = (A+3, 255, X, Clave[3], …, Clave[A+3], …)
     S[] = (0, 1, 2, …, A+3, …, 255)

Partiendo de este estado vamos a aplicar las tres primeras iteraciones para observar el comportamiento del algoritmo.

     Iteración 0
     
     i = 0
     j = 0 + 0 + Clave[0] = A+3
     S[] = (A+3, 1, 2, ..., 0, ...) 

     Iteración 1

     i = 1
     j = (A+3) + 1 + 255 = A+3                  [Ya que se aplica “j mod 256"]
     S[] = (A+3, 0, 2, ..., 1, ...)

     Iteración 2

     i = 2
     j = (A+3) + 2 + X
     S[] = (A+3, 0, S[j], ..., 1, ...)


La última iteración del bucle corresponde al valor desordenado de S para S2 (con esa nomenclatura indicamos el valor del vector S en la iteración 2). Cabe destacar que tan solo podremos calcular el valor de Clave[A] si conocemos los Clave[i] anteriores. En este caso hemos logrado simular correctamente hasta SA+2 para A = 0 debido a que los valores de las variables son conocidos, es decir todavía no ha entrado en juego la clave. La siguiente iteración sería pues la A+3 = 3. Así pues el desarrollo sería el siguiente:

     Iteración A+3

     iA+3 = A+3
     jA+3 = j2 + SA+2[A+3] + Clave[A+3]
     S[] = (A+3, A+3, 0, S[2], ..., S[j], ...)

En estos momentos el valor de la variable j ya depende de los bytes de la clave preestablecida y por lo tanto no podríamos seguir conociendo cual es el siguiente valor ya que nos es desconocido. Despejemos ahora la variable Clave[] y veamos qué conocemos y qué desconocemos de la ecuación:

    Clave[A+3] =  jA+3 - j2 - SA+2[A+3]

En esta iteración desconocemos el valor de Clave[A+3] (que evidentemente es nuestro objetivo) y el valor jA+3. El resto, “j2 – SA+2[A+3]» es conocido. Centrémonos en tratar de averiguar cual es el valor de jA+3. En este momento sabemos que se ha de realizar la permutación del bucle, en la que el valor de SA+3[A+3] ha de ser sustituido por el valor de SA+2[jA+3] (el valor del vector S resultado de la iteración anterior, con el nuevo índice a calcular y que desconocemos). Recordemos que necesitamos determinar jA+3 para poder averiguar el byte de la clave. Es evidente que si conociéramos el valor de SA+3[A+3] podríamos averiguar el ansioso jA+3 sustituyendo en la iteración anterior. Pero, ¿podemos conocer el valor de SA+3[A+3]? Aquí es donde entra en juego el segundo modulo de RC4, el algoritmo PRGA, que es mostrado y comentado a continuación:

     PRGA

     i := 0
     j := 0
     Mientras GeneraUnByte:
          i := (i + 1) mod 256
          j := (j + S[i]) mod 256
          Intercambia(S[i],S[j])
          Salida S[(S[i] + S[j]) mod 256]
     FinMientras

Para la iteración A+3 lo que devolvería PRGA sería S[S[0] + S[1]] = S[A+3 + 0] = S[A+3]; nuestro ansiado SA+3[A+3]. Pero, ¿qué probabilidad existe de que los valores de S[0], S[1] y S[A+3] permanezcan estables una vez el algoritmo KSA haya terminado el barajado? La respuesta a esta pregunta y entrada final de esta serie, mañana.