La primera parada en esta introducción a la criptografía moderna es ARC4 (a.k.a. RC4), un sencillo cifrado de flujo, posiblemente el más usado de su categoría, forma parte de WEP, WPA y del grupo de cifrados que puede usar la familia SSL/TLS.
Cifrados de flujo
Nota: iré explicando algunos terminos por si acaso resultan desconocidos, esas palabras irán marcadas con un * y un superíndice para identificarlo, habrá información al final del post.
Dado que la operación XOR es simétrica, este cifrado es simétrico tambien, esto es, se cifra y descifra exactamente de la misma forma.
| ⊕ | 0 | 1 |
| 0 | 0 | 1 |
| 1 | 1 | 0 |
Por ejemplo, para cifrar "HxC" con el flujo "123", lo primero que tendríamos que hacer es obtener los valores que le asignaríamos a cada símbolo, normalmente se usan los códigos ASCII, por ser la opción más cómoda:
H -> 0x48
x -> 0x78
C -> 0x43
1 -> 0x31
2 -> 0x32
3 -> 0x33
Después haríamos XOR de cada símbolo (ahora representado por un byte) con su pareja:
0x48 ⊕ 0x31
0x78 ⊕ 0x32
0x43 ⊕ 0x33
0x48 -> 01001000
0x31 -> 00110001
---------------------------
01111001 -> 0x79
Y repitiendo el proceso con las distintas parejas, se va cifrando el flujo.
Si aquí hacemos XOR de la clave con el valor cifrado, se puede ver la simetría al obtener de nuevo el valor original:
0x79 -> 01111001
0x31 -> 00110001
------------------------------
01001000 -> 0x48
De lo que nos provee ARC4 es de las "parejas" con las que hacer XOR al texto plano.
ARC4: Inicialización de la clave
Volviendo al algoritmo, ARC4 se divide en dos partes, la inicialización de la clave (Key schedule), y la generación de números pseudoaleatorios*3, la inicialización, el que trataremos ahora se encarga de preparar todo para el segundo paso, y es el único que interactua con la clave original.
La inicialización se hace tradicionalmente en dos bucles, el primero inicializa en array "S" (de 256 elementos) con valores del 0 al 255, según su posición, es decir: 0, 1, 2, 3, ... 254, 255... pero como esto es una introducción con python, esto se puede resumir en una sola llamada :)
Vamos entonces con el segundo bucle, de este no se puede escapar ;), pero primero hay que inicializar un par de variables, llamemoslas 'i' y 'j' . 'i' será un contador de 0 a 255, y en cada iteración 'j' tomará el valor "(j + posición i de S + valor de la posición i de la clave módulo*4 lóngitud de la clave) módulo 256", o en forma de código, que se entiende mejor, si la clave es k:
La inicialización se hace tradicionalmente en dos bucles, el primero inicializa en array "S" (de 256 elementos) con valores del 0 al 255, según su posición, es decir: 0, 1, 2, 3, ... 254, 255... pero como esto es una introducción con python, esto se puede resumir en una sola llamada :)
S = range(256)
Vamos entonces con el segundo bucle, de este no se puede escapar ;), pero primero hay que inicializar un par de variables, llamemoslas 'i' y 'j' . 'i' será un contador de 0 a 255, y en cada iteración 'j' tomará el valor "(j + posición i de S + valor de la posición i de la clave módulo*4 lóngitud de la clave) módulo 256", o en forma de código, que se entiende mejor, si la clave es k:
j = (j + S[i] + ord(k[i % len(k)])) % 256
Solo queda una cosa más que hacer en el bucle, intercambiar los valores de S entre las posiciones 'i' y 'j', con eso la parte de inicialización de la clave quedaría así:
def inicializacion(k): S = range(256) j = 0 for i in xrange(256): # Contador de 0 a 255 j = (j + S[i] + ord(k[i % len(k)])) % 256 S[i], S[j] = S[j], S[i] # Intercambia S[i] y S[j] return S
ARC4: Generación de números pseudoaleatorios
Esta parte del algoritmo es la que se encarga de obtener los datos que se mezclaran con los originales, como a parte de 'S' hay que guardar otro par de variables, inicializadas a 0, llamemoslas de nuevo 'i' y 'j' (aunque no son las mismas que antes), crearemos una clase que lo encapsule todo, para simplificar, lo que llevamos hasta ahora quedaría así:
class ARC4: S = [] i = 0 j = 0 def inicializacion(self, k):
S = range(256) j = 0
for i in xrange(256): # Contador de 0 a 255 j = (j + S[i] + ord(k[i % len(k)])) % 256
S[i], S[j] = S[j], S[i] # Intercambia S[i] y S[j] self.S = S def __init__(self, clave): self.inicializacion(clave)
Bien, escribamos entonces la función que devuelva el siguiente número pseudoaleatorio, cada vez que queramos tomar un número haremos esto:
- Incrementar i módulo 256
- j = ( j + posición i de S ) módulo 256
- Intercambia S[i] y S[j]
- K = posición ( posición i de S + posición j de S módulo 256 ) de S
- El siguiente número es K
def siguienteByte(self): self.i = (self.i + 1) % 256 self.j = (self.j + self.S[self.i]) % 256 self.S[self.i], self.S[self.j] = self.S[self.j], self.S[self.i] K = self.S[(self.S[self.i] + self.S[self.j]) % 256] return K
Entonces solo nos falta la última parte, que ni siquiera pertenece al algoritmo, sinó que es la común a todos los algoritmos de flujo, si recordamos como funciona, toma cada byte del "flujo" de texto plano y hace XOR con su correspondiente byte del "flujo" de clave, es decir:
def cifra(self, texto): cifrado = [] for caracter in texto: # Por cada caracter byte_texto = ord(caracter) # Obtiene el codigo ASCII byte_clave = self.siguienteByte() # El numero con el que se mezcla byte_cifrado = byte_texto ^ byte_clave # XOR ! caracter_cifrado = chr(byte_cifrado) # Lo pasamos a caracter cifrado.append(caracter_cifrado) # Y lo anhadimos return ''.join(cifrado) # Junta todos los caracteres
Y ya está, tenemos nuestro cifrado listo
>>> cifrador = ARC4("HxC") >>> mensaje = "HackxCrack" >>> mensaje_cifrado = cifrador.cifra(mensaje) >>> mensaje_cifrado '\x91XA\x8b\xb0=\x1c\xe7\xf4\xb5'
>>> descifrador = ARC4("HxC") >>> mensaje_descifrado = descifrador.cifra(mensaje_cifrado) >>> mensaje_descifrado 'HackxCrack' >>>
Anexo: Consideraciones de seguridad
Otra cosa a tener en cuenta es que los primeros caracteres adolecen de ciertos problemas, son en cierto modo predecibles, y pueden desvelar la clave, así que es recomendable dejar pasar unos cuantos bytes, como mínimo 256 (un valor con cierto margen seria 3072), por ejemplo haciendo esto antes de cifrar y descifrar:
for i in xrange(3072): cifrador.siguienteByte()
Eso es todo por hoy, aquí está el código completo [ http://pastebin.com/wKZSr9eu ], ¿ alguien se anima a mandar su implementación ?
Otros posts de la serie:
*1Operación XOR: OR ( 'ò' en inglés ) exclusivo, dados dos bits, el resultado es 1 si los dos tienen distintos valores y 0 si tienen el mismo, se representa con ⊕.
*2Texto plano o claro: texto antes del cifrado, el que se desea enviar al receptor.
*3 Números pseudoaleatorio: secuencia de números que aunque parece aleatoria, se genera a través de un proceso determinista, las máquinas deterministas como los ordenadores están límitadas a este nivel de aleatoriedad. En este caso es necesario que no sean totalmente aleatorios, porque de serlo no se podría obtener otra secuencia igual y no sería posible descifrar la información.
*4Módulo: De entre todos sus significados, aquí quiere decir, el resto de la división.. sí, se podría haber usado esa palabra, pero en este ámbito se usa "módulo", así que cuanto antes se comprenda mejor ;).
*5 Sal de un hash: Es un número o una secuencia aleatoria que se añade a una contraseña a la que se va a aplicar una función hash para evitar el ataque a través de rainbow tables.
¿Por qué con Python?
ResponderEliminarPor que no es necesario escribir tanto código para hacer cosas como java y permite prestarle menos atención a la máquina y más al proceso que C, por ejemplo.
Eliminar