Introduccion a la criptografia, con Python: MD5 (III)

Siguendo con el tema, en esta parte veremos como funciona la funcion de hash MD5:

¿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:

# Punto de inicio

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)&amp;0xFFFFFFFF

   self.c=(self.c+CC)&amp;0xFFFFFFFF

   self.d=(self.d+DD)&amp;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:

Tabla de valores utilizados en la funcion

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

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<>(32-y)))

Transformaciones

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

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

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()

===============================================================================

untagged

Web's fantasma » « Actualizando el Jamendo OGG redirector