¿Que es una funcion HASH?
En informática, Hash se refiere a una función o método para generar claves o llaves que representen de manera casi unívoca a un documento, registro, archivo, etc., resumir o identificar un dato a través de la probabilidad, utilizando una función hash o algoritmo hash. Un hash es el resultado de dicha función o algoritmo. [Wikipedia]Es decir, es una funcion de un solo sentido (a partir del resultado no se puede recuperar el original) que identifica un "objeto" con precision, si cambia un byte, cambia todo el resultado.
Esto se suele utilizar (por ejemplo) para comprobar que las descargas se realizaron correctamente, comparando el hash del archivo original y el del archivo descargado, si son iguales, todo fue bien :)
MD5 es una funcion de hash, pero presenta debilidades, como colisiones, por eso se deberia evitar usar en el futuro, de todas formas, aun se utiliza y servira de introduccion para este tipo de funciones.
Vamos alla...
class md5:
def __init__(self,s):
ln=len(s)*8
self.padd(s)
self.attach_len(ln)
self.buff_init()
self.update(ln)
self.final()
El primer paso es añadir un bit '1' a lo que se quere hashear, y despues añadir '0's hasta que el tamaño en bits sea igual a 448, siendo modulo 512 (o 56, modulo 64, en bytes):
def padd(self,s):
self.stream=s+"\x80"
while ((len(self.stream)%64)!=56):
self.stream+="\x00"
Despues hay que añadir a continuacion el tamaño en bits (al principio, antes del paso anterior) del archivo/mensaje/etc..., con un numero de 64 bits(8 bytes):
def attach_len(self,ln):
ln%=1<<64
i=7
l=[]
while i>=0:
k=256**i
aux=ln/k
l.append(aux)
ln-=aux*(k)
i-=1
while len(l)>0:
self.stream+=chr(l.pop(len(l)-1))
Se inicializan cuatro buffers (A,B,C y D) (de 32 bits) que se utilizan en el algoritmo:
def buff_init(self):
self.a = 0x67452301
self.b = 0xefcdab89
self.c = 0x98badcfe
self.d = 0x10325476
Se procesa el objeto/archivo/..., esto es la parte mas "opaca" del algoritmo...
Para comenzar se divide el objeto en partes de 64 bytes, concretamente en arrays de 16 elementos, con 4 bytes cada uno:
def update(self,ln):
i=0
while i<(len(self.stream)/64):
j=0
x=[]
while j<16:
t=((ord(self.stream[(i*64)+(j*4)+0]))|
(ord(self.stream[(i*64)+(j*4)+1])<< 8)|
(ord(self.stream[(i*64)+(j*4)+2])<< 16)|
(ord(self.stream[(i*64)+(j*4)+3])<< 24))
x.append(t)
j+=1
self.transform(x)
i+=1
Despues, con cada division se obtienen los valores de los buffer's:
def transform(self,x):
AA=self.a
BB=self.b
CC=self.c
DD=self.d
Y se le aplican una serie de transformaciones (veremos despues en detalle como funcionan esas transformaciones):
#Ronda 1
AA=FF (AA, BB, CC, DD, x[ 0], S11, 0xd76aa478) # 1
DD=FF (DD, AA, BB, CC, x[ 1], S12, 0xe8c7b756) # 2
CC=FF (CC, DD, AA, BB, x[ 2], S13, 0x242070db) # 3
BB=FF (BB, CC, DD, AA, x[ 3], S14, 0xc1bdceee) # 4
AA=FF (AA, BB, CC, DD, x[ 4], S11, 0xf57c0faf) # 5
DD=FF (DD, AA, BB, CC, x[ 5], S12, 0x4787c62a) # 6
CC=FF (CC, DD, AA, BB, x[ 6], S13, 0xa8304613) # 7
BB=FF (BB, CC, DD, AA, x[ 7], S14, 0xfd469501) # 8
AA=FF (AA, BB, CC, DD, x[ 8], S11, 0x698098d8) # 9
DD=FF (DD, AA, BB, CC, x[ 9], S12, 0x8b44f7af) # 10
CC=FF (CC, DD, AA, BB, x[10], S13, 0xffff5bb1) # 11
BB=FF (BB, CC, DD, AA, x[11], S14, 0x895cd7be) # 12
AA=FF (AA, BB, CC, DD, x[12], S11, 0x6b901122) # 13
DD=FF (DD, AA, BB, CC, x[13], S12, 0xfd987193) # 14
CC=FF (CC, DD, AA, BB, x[14], S13, 0xa679438e) # 15
BB=FF (BB, CC, DD, AA, x[15], S14, 0x49b40821) # 16
# Round 2
AA=GG (AA, BB, CC, DD, x[ 1], S21, 0xf61e2562) # 17
DD=GG (DD, AA, BB, CC, x[ 6], S22, 0xc040b340) # 18
CC=GG (CC, DD, AA, BB, x[11], S23, 0x265e5a51) # 19
BB=GG (BB, CC, DD, AA, x[ 0], S24, 0xe9b6c7aa) # 20
AA=GG (AA, BB, CC, DD, x[ 5], S21, 0xd62f105d) # 21
DD=GG (DD, AA, BB, CC, x[10], S22, 0x2441453) # 22
CC=GG (CC, DD, AA, BB, x[15], S23, 0xd8a1e681) # 23
BB=GG (BB, CC, DD, AA, x[ 4], S24, 0xe7d3fbc8) # 24
AA=GG (AA, BB, CC, DD, x[ 9], S21, 0x21e1cde6) # 25
DD=GG (DD, AA, BB, CC, x[14], S22, 0xc33707d6) # 26
CC=GG (CC, DD, AA, BB, x[ 3], S23, 0xf4d50d87) # 27
BB=GG (BB, CC, DD, AA, x[ 8], S24, 0x455a14ed) # 28
AA=GG (AA, BB, CC, DD, x[13], S21, 0xa9e3e905) # 29
DD=GG (DD, AA, BB, CC, x[ 2], S22, 0xfcefa3f8) # 30
CC=GG (CC, DD, AA, BB, x[ 7], S23, 0x676f02d9) # 31
BB=GG (BB, CC, DD, AA, x[12], S24, 0x8d2a4c8a) # 32
# Round 3
AA=HH (AA, BB, CC, DD, x[ 5], S31, 0xfffa3942) # 33
DD=HH (DD, AA, BB, CC, x[ 8], S32, 0x8771f681) # 34
CC=HH (CC, DD, AA, BB, x[11], S33, 0x6d9d6122) # 35
BB=HH (BB, CC, DD, AA, x[14], S34, 0xfde5380c) # 36
AA=HH (AA, BB, CC, DD, x[ 1], S31, 0xa4beea44) # 37
DD=HH (DD, AA, BB, CC, x[ 4], S32, 0x4bdecfa9) # 38
CC=HH (CC, DD, AA, BB, x[ 7], S33, 0xf6bb4b60) # 39
BB=HH (BB, CC, DD, AA, x[10], S34, 0xbebfbc70) # 40
AA=HH (AA, BB, CC, DD, x[13], S31, 0x289b7ec6) # 41
DD=HH (DD, AA, BB, CC, x[ 0], S32, 0xeaa127fa) # 42
CC=HH (CC, DD, AA, BB, x[ 3], S33, 0xd4ef3085) # 43
BB=HH (BB, CC, DD, AA, x[ 6], S34, 0x4881d05) # 44
AA=HH (AA, BB, CC, DD, x[ 9], S31, 0xd9d4d039) # 45
DD=HH (DD, AA, BB, CC, x[12], S32, 0xe6db99e5) # 46
CC=HH (CC, DD, AA, BB, x[15], S33, 0x1fa27cf8) # 47
BB=HH (BB, CC, DD, AA, x[ 2], S34, 0xc4ac5665) # 48
# Round 4
AA=II (AA, BB, CC, DD, x[ 0], S41, 0xf4292244) # 49
DD=II (DD, AA, BB, CC, x[ 7], S42, 0x432aff97) # 50
CC=II (CC, DD, AA, BB, x[14], S43, 0xab9423a7) # 51
BB=II (BB, CC, DD, AA, x[ 5], S44, 0xfc93a039) # 52
AA=II (AA, BB, CC, DD, x[12], S41, 0x655b59c3) # 53
DD=II (DD, AA, BB, CC, x[ 3], S42, 0x8f0ccc92) # 54
CC=II (CC, DD, AA, BB, x[10], S43, 0xffeff47d) # 55
BB=II (BB, CC, DD, AA, x[ 1], S44, 0x85845dd1) # 56
AA=II (AA, BB, CC, DD, x[ 8], S41, 0x6fa87e4f) # 57
DD=II (DD, AA, BB, CC, x[15], S42, 0xfe2ce6e0) # 58
CC=II (CC, DD, AA, BB, x[ 6], S43, 0xa3014314) # 59
BB=II (BB, CC, DD, AA, x[13], S44, 0x4e0811a1) # 60
AA=II (AA, BB, CC, DD, x[ 4], S41, 0xf7537e82) # 61
DD=II (DD, AA, BB, CC, x[11], S42, 0xbd3af235) # 62
CC=II (CC, DD, AA, BB, x[ 2], S43, 0x2ad7d2bb) # 63
BB=II (BB, CC, DD, AA, x[ 9], S44, 0xeb86d391) # 64
Y por ultimo, se devuelven los valores que se tomaron de los buffer a ellos:
self.a=(self.a+AA)&0xFFFFFFFF
self.b=(self.b+BB)&0xFFFFFFFF
self.c=(self.c+CC)&0xFFFFFFFF
self.d=(self.d+DD)&0xFFFFFFFF
Una cosa... el hacer and con 0xFFFFFFFF a las variables es para evitar que ocupen mas de 32 bytes, otra forma seria hacerlo modulo 0x100000000, pero esta es mas rapida.
Bien, veamos en que consisten las transformaciones... para empezar, S11,S12,S.. son constantes predefinidas, sus valores son estos:
S11=7
S12=12
S13=17
S14=22
S21=5
S22=9
S23=14
S24=20
S31=4
S32=11
S33=16
S34=23
S41=6
S42=10
S43=15
S44=21
Ademas en las transformaciones se utilizan unas funciones basicas:
def F(x,y,z):
return (x&y)|((~x&0xFFFFFFFF)&z)
def G(x,y,z):
return (x&z)|(y&(~z&0xFFFFFFFF))
def H(x,y,z):
return x^y^z
def I(x,y,z):
return y^(x|(~z&0xFFFFFFFF))
# Rotacion
def rotate_left(x,y):
return ((x<<y)|(x>>(32-y)))
Una vez definido eso, las transformaciones no son demasiado complejas:
def FF(a,b,c,d,x,s,ac):
a=(a+(F(b,c,d)+x+ac))&0xFFFFFFFF
a= rotate_left(a,s)&0xFFFFFFFF
a=(a+b)&0xFFFFFFFF
return a
def GG(a,b,c,d,x,s,ac):
a=(a+(G(b,c,d)+x+ac))&0xFFFFFFFF
a= rotate_left(a,s)&0xFFFFFFFF
a=(a+b)&0xFFFFFFFF
return a
def HH(a,b,c,d,x,s,ac):
a=(a+(H(b,c,d)+x+ac))&0xFFFFFFFF
a= rotate_left(a,s)&0xFFFFFFFF
a=(a+b)&0xFFFFFFFF
return a
def II(a,b,c,d,x,s,ac):
a=(a+(I(b,c,d)+x+ac))&0xFFFFFFFF
a= rotate_left(a,s)&0xFFFFFFFF
a=(a+b)&0xFFFFFFFF
return a
Como se puede ver, el patron es bastante obvio:
def XX(a,b,c,d,x,s,ac):
a=(a+(X(b,c,d)+x+ac))
a= rotate_left(a,s)
a=(a+b)
return a
El resto solo sirve para evitar que los valores se salgan de los 32 bits
Y por ultimo, se presenta como resultado lo que hay en los buffers, comenzando por el byte menos significativo de A y acabando por el mas significativo de D, normalmente se hace directamente en la representacion hexadecimal:
def final(self):
self.digest=[]
for some in [self.a,self.b,self.c,self.d]:
t=uint4tochar(some)
while len(t)>0:
thing=t.pop(len(t)-1)
self.digest.append(myhex(thing)[2:4])
def hexdigest(self):
from string import join
return join(self.digest,'')
Las funciones utilizadas son estas:
#Pasa un entero de 4 bytes a un array de 4 bytes
def uint4tochar(s):
i=0
t=[0,0,0,0]
while i<4:
aux=(s>>(8*i))&0xFF
t[3-i]=int(aux)
i+=1
return t
#Devuelve un hexadecimal con 4 caracteres o mas
def myhex(a):
r=hex(a)
if (len(r)==3):
r="0x0"+r[2]
return r
El código completo aqui [md5.py]
Si se ejecuta directamente (no importandolo), hace unas pruebas para comprobar que funciona bien, las comprobaciones se hacen contra hashlib:
d41d8cd98f00b204e9800998ecf8427e = d41d8cd98f00b204e9800998ecf8427e True
81dc9bdb52d04dc20036dbd8313ed055 = 81dc9bdb52d04dc20036dbd8313ed055 True
9e107d9d372bb6826bd81d3542a419d6 = 9e107d9d372bb6826bd81d3542a419d6 True
e4d909c290d0fb1ca068ffaddf22cbd0 = e4d909c290d0fb1ca068ffaddf22cbd0 True
6f728eb0a9ef9387cb17dba7cc2116fb = 6f728eb0a9ef9387cb17dba7cc2116fb True
Hasta la proxima ;)
[Referencia]
RFC 1321
MD5 - Wikipedia
Otra implementacion
No hay comentarios:
Publicar un comentario