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.
