(void *) blog

Posted on by fortytwo_de


Blowfish es un algoritmo de cifrado que brilla por su simplicidad, sin sacrificar seguridad criptográfica. Está compuesto por 18 semiclaves y 4 substitution boxes (S-boxes).

Es un cifrado simétrico, es decir, conociendo la clave (con un tamaño máximo de 56 bytes (448 bits)) y el texto cifrado se puede obtener el texto plano.

El algoritmo para cifrar el texto plano es sencillo; la siguiente imagen lo explica gráficamente:


Nota: en el último paso, a la derecha debería leerse xR XOR P17, pero OpenOffice explotó justo después de guardar esta imagen.

Algoritmo de cifrado

  • Se divide un bloque de 64 bits en dos de 32 bits. Como ya expliqué en el post de Base64, esto se hace con bitmasks y logic shifts.
  • Se aplica la operación binaria XOR a los 32 bits altos (xL en el diagrama) con la primera de las sub-claves.
  • Se aplica la función F al resultado de la operación xL XOR Pi (el paso anterior).
  • Se aplica la operación binaria XOR a los 32 bits bajos (xR en el diagrama) con el resultado de la operación F(xL)
  • Se intercambian los bits altos con los bajos.
  • Se repite el proceso 16 veces.
  • Se deshace el último intercambio.
  • Se aplica la operación binaria XOR a los bits altos resultantes con la semiclave 18.
  • Se aplica la operación binaria XOR a los bits bajos resultantes con la semiclave 17.
  • Se recomponen los dos grupos de 32 bits en uno de 64 bits, ya cifrado.

Función F

La función F de Blowfish es la que se encarga de sustituir los valores XOReados utilizando las 4 S-boxes.

La función F divide el grupo de 32 bits que tiene como parámetro en 4 octetos. Igual que en el problema de Base64, hago un croquis de la composición binaria de los octetos.

C0 DE BA BE
-- -- -- -- 
a  b  c  d

En este caso es mucho más fácil definir los octetos, ya que no hay que juntar bits de varias variables. Así que, en este caso:

a = input >> 24
b = (input >> 16) & 0xFF
c = (input >> 8) & 0xFF
d = input & 0xFF

Schneier, la mente detrás de Blowfish, ha descrito la función F como:

$$ F(a, b, c, d) = ((S1,a + S2,b\ \%\ 2^{32}))\ XOR\ S3,c) + S4,d\ \%\ 2^{32} $$

Nota: % es la función módulo.

Para la implementación, se puede "obviar" la aplicación de los módulos, ya que al trabajar con enteros sin signo no hay necesidad de aplicar el módulo.

XOR

Para implementar la función de cifrado y la función F, conviene entender la función binaria XOR. Como su nombre indica, eXclusive OR, se comportará de forma parecida a la operación OR, pero solo si es un bit exclusivo. La tabla de verdad de la operación XOR:

La operación binaria XOR es utilizada en la criptografía precisamente porque es reversible, conociendo la semiclave con la que se ha aplicado la operación.

Inicialización de las semiclaves y S-boxes

En el estado no-inicializado del algoritmo Blowfish, las 18 semiclaves y S-boxes tienen los valores (en hexadecimal) de los dígitos de π. Schneier eligió utilizar decimales de π para inicializar las semiclaves y S-boxes porque es un número completamente arbitrario y no sospechoso (nothing up my sleeve number).

Sin embargo, para cifrar los bloques de 64 bits con los 448 bits de clave es necesario inicializar las semiclaves y S-boxes. Este es un proceso un poco más complicado, pero es lo que asegura la robustez criptográfica de Blowfish, y su reversibilidad.

El procedimiento para inicializar las semiclaves y S-boxes, según Schneier (traducción de su paper):

  • Aplicar la operación binaria XOR al primer elemento de las semiclaves con los 32 primeros bits de la clave.
  • Repetir el primer paso con los 18 elementos de las semiclaves, incrementando la posición de los 32 bits de la clave que se eligen.
  • Cifrar el bloque vacío de 64 bits (0x0000000000000000) utilizando el algoritmo de cifrado Blowfish, con las semiclaves inicializadas previamente.
  • Reemplazar el elemento n de las semiclaves con los 32 bits altos del resultado de cifrar el bloque vacío de 64 bits.
  • Reemplazar el elemento n+1 de las semiclaves con los 32 bits bajos del resultado de cifrar el bloque vacío de 64 bits.
  • Repetir el proceso hasta que todos los elementos de las semiclaves hayan sido reemplazados por los valores cifrados del resultado de los pasos anteriores.
  • Repetir el proceso anterior con todas las S-boxes y sus valores.

Implementación

Una vez se tienen las semiclaves y S-boxes inicializadas con la clave, se pueden cifrar los bloques arbitrarios de 64 bits. Mi implementación en C a continuación:

blowfish.c

#include <stdio.h>
#include <stdlib.h>

#include "blowfish.h"

void swap(uint32_t* a, uint32_t* b) {
    uint32_t tmp;

    tmp = *a;
    *a = *b;
    *b = tmp;
}

uint32_t blowfish_f(blowfish_t* container, uint32_t input) {
    uint8_t a, b, c, d;

    a = input >> 24;
    b = (input >> 16) & 0xff;
    c = (input >> 8) & 0xff;
    d = input & 0xff;

    return ((container->s[0][a] + container->s[1][b]) ^ container->s[2][c]) +
            container->s[3][d];
}

void blowfish_cipher(blowfish_t* container, uint32_t* xl, uint32_t* xr, uint8_t mode) {
    int i;
    uint32_t loc_xl, loc_xr;

    loc_xl = *xl;
    loc_xr = *xr;

    if(mode == BLOWFISH_ENCRYPT) {
        for(i = 0; i < PASSES; i++) {
            loc_xl = loc_xl ^ container->p[i];
            loc_xr = blowfish_f(container, loc_xl) ^ loc_xr;

            swap(&loc_xl, &loc_xr);
        }
    } else if(mode == BLOWFISH_DECRYPT) {
        for(i = PASSES+1; i > 1; i--) {
            loc_xl = loc_xl ^ container->p[i];
            loc_xr = blowfish_f(container, loc_xl) ^ loc_xr;

            swap(&loc_xl, &loc_xr);
        }
    }

    swap(&loc_xl, &loc_xr);

    if(mode == BLOWFISH_ENCRYPT) { 
        loc_xr = loc_xr ^ container->p[PASSES];
        loc_xl = loc_xl ^ container->p[PASSES+1];
    } else if(mode == BLOWFISH_DECRYPT) {
        loc_xr = loc_xr ^ container->p[1];
        loc_xl = loc_xl ^ container->p[0];
    }

    *xl = loc_xl;
    *xr = loc_xr;
}

blowfish_t* blowfish_initialize(unsigned char* key, uint32_t length) {
    blowfish_t* container = malloc(sizeof(blowfish_t));
    unsigned int i, ii, j = 0;
    uint32_t tmp, tmp_l = 0, tmp_r = 0;  

    if(length > BLOWFISH_MAX_KEY_BYTES) return (blowfish_t*) NULL;

    for(i = 0; i < PASSES+2; i++) {
        container->p[i] = P[i];
    }

    for(i = 0; i < SBOXES; i++) {
        for(ii = 0; ii < 256; ii++) {
            container->s[i][ii] = S[i][ii];
        }
    }

    for(i = 0; i < PASSES+2; i++) {
        tmp = 0;
        for(ii = 0; ii < 4; ii++) {
            tmp = (tmp << 8) | key[j];
            j++;
            if(j == length) 
                j = 0;
        }
        container->p[i] = container->p[i] ^ tmp;
    }

    for(i = 0; i < PASSES+1; i += 2) {
        blowfish_cipher(container, &tmp_l, &tmp_r, BLOWFISH_ENCRYPT);
        container->p[i] = tmp_l;
        container->p[i+1] = tmp_r;
    }

    for(i = 0; i < SBOXES; i++) {  
        for(ii = 0; ii < 256; ii += 2) { 
            blowfish_cipher(container, &tmp_l, &tmp_r, BLOWFISH_ENCRYPT);
            container->s[i][ii] = tmp_l;
            container->s[i][ii+1] = tmp_r;
        }
    }
}

int main(int argc, char** argv) {
    uint32_t high, low;
    blowfish_t* container = blowfish_initialize("test", 4);

    high = 0xc0debabe;
    low = 0xdeadbeef;
    blowfish_cipher(container, &high, &low, BLOWFISH_ENCRYPT);
    printf("high: %x low: %x\n", high, low); // should yield "high: 7589e5fa low: e0fa3586"
    return 0;
}

blowfish.h

#ifndef __BLOWFISH_H
#define __BLOWFISH_H

#include <stdint.h>

#define PASSES 16
#define SBOXES 4

#define BLOWFISH_ENCRYPT 1
#define BLOWFISH_DECRYPT 2

#define BLOWFISH_MAX_KEY_BYTES 56

typedef struct {
    uint32_t p[PASSES+2];
    uint32_t s[4][256];
} blowfish_t;

uint32_t P[PASSES + 2] =
{
    /* snip */
};

uint32_t S[SBOXES][256] = 
{
    {
        /* snip */
    }
};

#endif 

El código fuente está disponible en mi GitHub.

Posted on by fortytwo_de | Posted in C, Criptografía, Programación


2 Responses to Blowfish

  1. Nelson says:


    Very informative post, i am regular reader of your blog. I noticed that
    your site is outranked by many other blogs in google’s search results.
    You deserve to be in top-10. I know what can help you,
    search in google for:
    Omond’s tips outsource the work


  2. FirstRubye says:


    I see you don’t monetize your blog, don’t waste your traffic,
    you can earn extra cash every month because you’ve got high quality content.
    If you want to know how to make extra bucks, search for:
    Boorfe’s tips best adsense alternative


Leave a Reply to FirstRubye Cancel reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>