Max Hernandez: Blowfish

Para esta semana en la clase de seguridad de la información y criptografía estamos viendo el tema de block ciphers y como tarea para este tema nos tocó hacer un reporte sobre un algoritmo de nuestra elección para esto yo elegí el algoritmo Blowfish.

[Imagen obtenida de:https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj3UUWhIlYjaF6vg3id89ppmeUDvnkdziHXiOdd1mUUMk0g7vkuUCWkGnk6nRFehWUaLgd7VIWwdGf_F9yy-sJ_zw0KBbBcgY6lvcWa_qtn2D5D6mFqOXwptbuejY9l-sldlNHT0AwFLgBv/s1600/red-BlowFish.jpg]

Blowfish
El algoritmo Blowfish is un algoritmo simétrico de cifrado por bloques, fue diseñado en 1993 por el computologo Bruce Schneier. Este algoritmo es muy popular ya que prové un alto rango de encripción en software y hasta ahora no se ha demostrado ningún ataque efectivo contra este algoritmo.

caracteristicas:

64-bit por bloque
Longitud de la llave variable: 32 bits a 448 bits
Diseñado por Bruce Schneier
Mas rápido que DES y IDEA
No patentado y gratis
No se requiere licencia
Código abierto
Cifrado simétrico

Vulnerabilidades

muchos criptografos an examinado el algoritmo, sin embargo solo hay algunos resultados publicados. Serge Vaudenay examino llaves débiles en el algoritmo, existe una clase de llaves que pueden ser detectadas en 14 rondas o menos pero no rotas por el algoritmo Blowfish. La tesis de Vincent Rijmen's Ph.D. incluye un ataque diferencial de segundo orden en la cuarta ronda del algoritmo pero este no puede ser extendido a otras rondas.

Funcionamiento

Para el funcionamiento de este algoritmo se necesita un arreglo de 18 posiciones llamado P-array con números aleatorios obtenidos utilizando las cifras de el número Pi exceptuando las 3 primeras. También se ocupa una matriz de 4x256 con valores de 32 bits aleatorios del mismo tipo que el P-array llamado S-box.

P-array
S-box

Este es el pseudocódigo original del paper de Bruce Schneier para explicar las primeras 18 rondas del algoritmo:

Divide x into two 32-bit halves: xL, xR
For i = 1 to 16:
xL = xL XOR Pi
xR = F(xL) XOR xR
Swap xL and xR
Next i
Swap xL and xR (Undo the last swap.)
xR = xR XOR P17
xL = xL XOR P18
Recombine xL and xR

Como se puede ver recibe un dato de 64 bits el cual parte en dos y después mezcla utilizando un Exor con el P-array ronda por ronda alternando el lado derecho e izquierdo cada vez. Ademas de mezclar el PlainText con el P-array utiliza la función "F" para mezclar el S-box con el PlainText.

[Imagen obtenida de: http://upload.wikimedia.org/wikipedia/commons/3/34/BlowfishDiagram.png]

La forma de mezclar el S-box con nuestro PlainText es utilizando la siguiente función la cual divide nuestro bloque de 32 bits en cuatro bloques de ocho bits
para mezclarlos con el S-box utilizando sumas binarias y el operador Exor.

Function F (see Figure 2):
Divide xL into four eight-bit quarters: a, b, c, and d
F(xL) = ((S1,a + S2,b mod 2³²) XOR S3,c) + S4,d mod 2³²

[Imagen obtenida de:http://upload.wikimedia.org/wikipedia/commons/thumb/2/22/BlowfishFFunction.svg/1000px-BlowfishFFunction.svg.png]

Mi implementación
Como ejemplo para esta tarea intente programar el algoritmo de esta tarea pero no logre terminarlo lo que logre es cifrar una cifra utilizando los valores del Parray pero cuando intente implementar la "F" y ademas combinar las llaves con los valores del S-box. Pero es capaz de cifrar el P-array en las doce rondas y descifrarlo de igual manera con lo cual pude cifrar un número pero sin seguridad alguna.

#! /usr/bin/python

pArray = [0x243f6a88, 0x85a308d3, 0x13198a2e, 0x03707344, 0xa4093822, 0x299f31d0,0x082efa98, 0xec4e6c89, 0x452821e6, 0x38d01377, 0xbe5466cf, 0x34e90c6c,0xc0ac29b7, 0xc97c50dd, 0x3f84d5b5, 0xb5470917, 0x9216d5d9, 0x8979fb1b]
sArray = []

def constants_initialize():
    cmd = 0
    temp = ""
    fl = open("constants.txt", "r")
    for i in fl:
        if i.find("};") != -1 and cmd == 1:
            temp = temp.lstrip("\n")
            temp = temp.lstrip("\r\n")
            temp = temp.split(",")
            for i in range(len(temp)):
                temp[i] = int(temp[i])
            pArray = temp
            cmd = 0
        if cmd == 1:
            temp += i
        if i.find("unsigned long parray[] = {") != -1:
            cmd = 1
    print pArray
    fl.close()

def F(block):
    return block

def encript(data):
    data = int(data)
    xL = data >> 32
    xR = data&((2**32)-1) # "&" to perfom an and operation
    for i in range(16):
        xL = xL^pArray[i]
#        xR = F(xL) ^ xR # "^" is xor operation
        xL, xR = xL, xR
    xL, xR = xL, xR
    xR = xR^pArray[i+1]
    xL = xL^pArray[i+2]

    return ( (xL**33) | xR )

def decript(data):
    data = int(data)
    xL = data >> 32
    xR = data&((2**32)-1) # "&" to perfom an and operation
    xL = xL^pArray[17]
    xR = xR^pArray[16]
    xL, xR = xL, xR
    for i in range(16):
        xL = xL^pArray[15-i]
#        xR = F(xL) ^ xR # "^" is xor operation
        xL, xR = xL, xR
    return ( (xL**33) | xR )


def main():
#    constants_initialize()
#    print pArray
    cipherData = encript(222)
#    print "cipher data:", cipherData
    print "decipher data", decript(cipherData)
    print "Done"

main()

References:
http://en.wikipedia.org/wiki/Blowfish_%28cipher%29
http://www.schneier.com/blowfish.html
http://www.schneier.com/paper-blowfish-fse.html
http://www.schneier.com/code/constants.txt