jueves, 25 de marzo de 2010

Introduccion a la criptografia, con Python: ARC4 (I)

La idea es hacer una serie de posts que cubran algunos de los algoritmos de criptografia mas usados, por lo menos uno decifrado simetrico (como ARC4) , otro de cifrado asimetrico (como RSA) y uno de hash (como MD5), vamos alla....

ARC4 (a.k.a. RC4 ) es el algoritmo de cifrado que se usa en WEP, en WPA y en SSL, entre otras cosas, y destaca por que es extremadamente sencillo y rapido... pero si no se usa correctamente no es seguro 

Mas concretamente, es un cifrado de flujo, es decir que cifra el mensaje haciendo XOR de el byte de entrada y el byte que se obtiene del algoritmo (del keystream), y que la forma de cifrar y descifrar es exactamente la misma.

El cifrado se maneja con las siguientes estructuras:
  - Dos enteros (aqui seran 'i' y 'j') que solo tendran valores del 0 al 255
  - Un array de 256 bytes (aqui sera 'S' )

La primera parte del cifrado ( el "seeding" ), tiene dos partes, la primera es llenar el array 'S' con valores del 0 al 255 (ambos incluidos), algo como:


s=range(0,256)

Y despues se mezcla un poco todo...

k
=0 for n in range(0,256): k=(k+self.s[n]+ord(clave[n % len(clave)]))%256 swap(n,k)

Swap intercambia los valores de S con los indices que se le dan...


def
swap(n,k): t=s[n] s[n]=s[k] s[k]=t

La primera parte ya esta (este es el codigo todo junto):


class
arc4: # Intercambia dos valores del array 's' def swap(self,n,k): t=self.s[n] self.s[n]=self.s[k] self.s[k]=t def __init__(self,key): # Generamos el array 's', normalmente se utilizaria un bucle para llenarlo # con los valores de 0 a 255, pero python lo hace mas facil self.s=range(0,256) k=0 for n in range(0,256): k=(k+self.s[n]+ord(key[n % len(key)]))%256 self.swap(n,k) self.i=0 self.j=0

Ahora para cifrar se extrae un byte (al flujo de bytes que se extrae se le llama keystream) por cada byte de entrada y se les hace XOR...
Para extraerlo a la variable "nuevobyte" se hace esto:


i=(i+ 1)% 256 j=(j+ s[i])% 256 swap(i,j) nuevobyte= s[(s[i]+ s[j])% 256]


Asi que para cifrar una string completa:


def
nextbyte(self): self.i=(self.i+ 1)% 256 self.j=(self.j+ self.s[self.i])% 256 self.swap(self.i,self.j) return self.s[(self.s[self.i]+ self.s[self.j])% 256] def cipherbyte(self,byte): return byte^self.nextbyte() # Aunque se usa para cifrar y descifrar... def cipher(self,text): a="" for c in text: a+=chr(self.cipherbyte(ord(c))) return a

Se utilizaria la ultima funcion (cipher) para cifrar y descifrar
Y el codigo ya esta... si lo probamos [ codigo completo: arc4.py ] :


>>> cifrador=arc4("password")
>>> text="Hola, mundo!"
>>> cifrado=cifrador.cipher(text)
>>> print cifrado
·šTo` ÙÛ 5Ä]
>>> descifrador=arc4("password")
>>> descifrado=descifrador.cipher(cifrado)
>>> print descifrado
Hola, mundo!
>>>



Como se puede ver funciona bien :)}

Como usarlo (y como no usarlo):

Como ya se dijo antes, el algoritmo funciona bien dentro de lo que cabe, pero hay que tener en cuenta unas cosas cuando se use:

Es recomendable descartar por lo menos los primeros 256 (un valor con cierto margen seria 3072 ) bytes del keystream, en el ejemplo se haria con


for
n in range(0,256):
    cifrador.nextbyte()
 antes de empezar a cifrar y


for
n in range(0,256):
    descifrador.nextbyte()
antes de  descifrar.

Esto es por que de los primeros bytes del keystream se puede extraer informacion sobre la contraseña, otra posibilidad es utilizar claves temporales, una forma de hacerlo seria enviando un texto en plano, que se añade a la contraseña, y al resultante pasarle una funcion de hash (como MD5), con esto se conseguiria que aun crackeando la clave temporal y el texto en plano añadido no se pudiera recuperar la clave original (habria que hacer un ataque de fuerza bruta sobre el hash, ya que no se pueden usar Rainbow tables por el texto añadido, que funcionaria de salt)

Por supuesto seria recomendable utilizar las dos medidas, ya que usar varias veces la misma clave (especialmente en un cifrado de flujo) es una MALA IDEA y descartar los primeros bytes supone un esfuerzo computacional muy pequeño y aumenta la seguridad.

Por ultimo, volver a recordar, NO es buena idea usar dos veces la misma clave.

Y eso es todo, hasta otra!!

Ah! y el codigo esta coloreado con pygments

El codigo fuente en Python del cifrador arc4.py

[Referencias]
RC4 en la Wikipedia

1 comentario: