Hola a todos, hace poco he creado un algoritmo generador de hashes, la verdad es que en dos días ya le he encontrado un montón de fallos, y se lo she arreglado, por supuesto.

No he hecho ningún estudio teórico sobre él, y no se si es demasiado seguo, no se si se producen colisiones fácilmente, no se si se pueden deducir contenidos que generen el hash a partir del él...

Así que dejaré mi algoritmo escrito, para someterlo a revisión, explicaré cada parte, a ver que os parece :P .

El hash constaría de 128 bits(aunque su estructura es tan sencilla que se podria ampliar cómodamente a millones de bits, si me lo propusiera, claro, :P). tengo pensado ampliarlo a 160 bits, pero no se en que medida esto aumentaría la seguridad, por eso presento aquí el algoritmo.

Pues bien, los primeros 4 bytes se inicializan con un valor entero de 32 bits, yo puse "0xABCDEF01"(es en hexadecimal), no se que impacto puede tener el que sea de un modo u otro, ese número inicial.

Los otros 4 bytes siguientes se inicializan con un entero que representa la longitud del mensaje a digerir, pero en modulo 2^32. Así podría digerir más de medio giga, aunque lo representaría como sivolviera a empezar desde 0.

los 8 bytes restantes se inicializan con 0.

bueno, a partir de entonces, se van llenando los espacios que quedan con los bytes del mensaje. cuando se llega al final de la matriz(la del hash), se empieza a llenar una segunda matriz vacía de la misma longitud que la del hash. Si se acabara el mensaje, se seguría llenando hasta llenar porlomenos la segunda matriz. pero se llenaría otra vez con la secuencia numerica inicial, y después la longitud del mensaje. Si el mensaje fuera más largo que la longitud de las dos matrices, los siguientes bytes se sumarian a los ya existentes de la primera matriz, como en un bucle, así llenaría otra vez la primera matriz, i si fuera necesaria continuaría también con la segunda..

Bien, una vez sumado todo, cuando ya se han llenado las amtrices con esos valores, se suman las dos matrices, y se almacena el resultado en la primera, de la forma A[i] = A[i] + B[i].

Asta aquí es nmuy sencillo, aquí no se acaba, pues en este punto, se podrian obtener millones de colisiones muy fácilmente, se pueden obtener muchas cadenas que satisfagan el resultado de esas sumas.

Lo siguiente es la difusion, esto se hace para que si un mensaje tiene pocas diferencias respecto al anterior, esas diferencias afecten a todo el hash i no solamente unos bloques. La difusion que yo hago es la siguiente, no la hago habiendo finalizado las sumas, la hago durante las sumas(antes de sumar las dos matrices).

cojo el elemento de la matriz que acabo de sumar, y xoreo los dos elementos adyacentes con este, al ir prosiguiendo con las sumas, el xoreo que se ha hecho con el único elemento cambiado ha acabado afectando a todo el hash.

Esto, como he dicho es para la difusión, y aunque también dificulta un poco el plantear los sistemas de ecuaciones que permitan resolver las cadenas que cumplen con le hash hasta ahora hecho, una vez planteados esos ssitemas ya no hay mayor dificultad.

Bien, ahora viene lo que dificulta, creo yo, lo de las colisiones.

cojo el primer entero de 4 bytes del hash, y con el resultado del entero_modulo_longitudmensaje selecciono un byte del mensaje, este byte lo multiplico por ese entero, y el resultado lo aplicamos al entero también.

con el segundo, el tercer, y el cuarto entero se hace lo mismo. con esto se hace que el número que se muestra en el hash no solo depende de las sumas y la difusión, sinó de otros carácteres del mensaje.

Ah, me olvidaba, esa multiplicación, no se hace realmente entre el entero y el byte del mensaje, se hace así: entero*(byte_mensaje+entero_siguiente).

Esto del entero siguiente es por si el byte del mensaje fuese 0, entonces la homogeneidad del hash quedaria anulada, y además, se podrian deducir más fácilmente mensajes que produjeran ese hash, creo.

Lo que he visto ahora , mientras escribía..., cuando hago la difusión, al hacerla mientras se procesan las sumas, si que interviene mucho el cómo sea el mensaje, y no sólo el resultado de las sumas, porque como todavía no hay resultados fijos eso va variando. Sería entonces realmente útil la capa de las multiplicaciones, o se podria considerar una parafernalia para hacer creer que es mas seguro y ya esta?

el problema está en que al escribir código puse lo de la difusion después de cada suma, y no despues del resultado, ahora me parece más seguro, pero no lo pensé con ese proposito al escribir el código.. :P

Aquí teneis el código en c, da el resumen hash de cualquier archivo que le indiqueis, es como un md5sum pero sin tener la confirmación de ser seguro.

  1. // HASHER.CPP
  2.  
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. #include <string.h>
  6. #include <time.h>
  7. #include "CSCHasher_private.h"
  8.  
  9. union quadbyte
  10. {
  11.   unsigned int i;
  12.   unsigned char c[4];
  13. };
  14.  
  15. union cschash
  16. {
  17.   unsigned int i[8];
  18.   unsigned char c[32];
  19. };
  20.  
  21. int main(int argc, char* argv[])
  22. {
  23.     FILE* arch;
  24.  
  25.     putchar('\n');
  26.     for(int x = 1; x < argc; x++)
  27.     {
  28.         if((arch = fopen(argv[x], "rb+"))==0)
  29.         {
  30.           printf("El archivo no es accesible.\n");
  31.           exit(1);
  32.         }
  33.  
  34.         fseek(arch, 0, SEEK_END);
  35.  
  36.         int archsize = ftell(arch);
  37.  
  38.         fseek(arch, 0, SEEK_SET);
  39.  
  40.         cschash hashete;
  41.  
  42.         memset(&hashete, 0, sizeof(cschash));
  43.  
  44.         hashete.i[0] = 0xABCDEF01;
  45.         hashete.i[1] = archsize;
  46.  
  47.         unsigned int _size = archsize;
  48.         for(register int i=8; (i<_size+8) || (i<32); i++)
  49.         {    
  50.           hashete.c[i%32] += (unsigned char)(fgetc(arch));
  51.  
  52.           if(i%32 < 31) hashete.c[(i%32)+1] ^= hashete.c[i%32];
  53.           else hashete.c[0] ^= hashete.c[31];
  54.  
  55.           if(i%32 > 0) hashete.c[(i%32)-1] ^= hashete.c[i%32];
  56.           else hashete.c[31] ^= hashete.c[0];
  57.  
  58.           if(i>=(_size+7) && i < 32)
  59.           {
  60.             quadbyte tmp;
  61.  
  62.             hashete.c[(++i)%32] += 0x01;
  63.             hashete.c[(++i)%32] += 0xEF;
  64.             hashete.c[(++i)%32] += 0xCD;
  65.             hashete.c[(++i)%32] += 0xAB;
  66.  
  67.             tmp.i = archsize;
  68.  
  69.             hashete.c[(++i)%32] += tmp.c[0];
  70.             hashete.c[(++i)%32] += tmp.c[1];
  71.             hashete.c[(++i)%32] += tmp.c[2];
  72.             hashete.c[(++i)%32] += tmp.c[3];
  73.  
  74.             _size *= 2;
  75.             _size += 8;
  76.             rewind(arch);
  77.           }
  78.         }
  79.         for(register int i = 0; i < 16; i++) hashete.c[i] += hashete.c[i+16];
  80.  
  81.         // Hago estas multiplicaciones 4 veces para crear un segundo
  82.         // efecto de difusión, ya que puede ser necesario en mensajes
  83.         // con un carácter repetido más de ocho veces consecutivas.
  84.         // Al estar repetido tantas veces, pueden quedar fijados los
  85.         // valores de hasta 3 bytes( o +), sin cambio alguno, de ahí el uso de
  86.         // estas multiplicaciones.
  87.  
  88.         unsigned int i = hashete.i[0]; 
  89.         fseek(arch, (unsigned)(hashete.i[0]%(archsize)), SEEK_SET);
  90.         hashete.i[0] *= ((fgetc(arch))+hashete.i[1]);
  91.         fseek(arch, (unsigned)(hashete.i[1]%(archsize)), SEEK_SET);
  92.         hashete.i[1] *= ((fgetc(arch))+hashete.i[2]);
  93.         fseek(arch, (unsigned)(hashete.i[2]%(archsize)), SEEK_SET);
  94.         hashete.i[2] *= ((fgetc(arch))+hashete.i[3]);
  95.         fseek(arch, (unsigned)(hashete.i[3]%(archsize)), SEEK_SET);
  96.         hashete.i[3] *= ((fgetc(arch))+i);
  97.  
  98.         i = hashete.i[3];
  99.         fseek(arch, (unsigned)(hashete.i[3]%(archsize)), SEEK_SET);
  100.         hashete.i[3] *= ((fgetc(arch))+hashete.i[2]);
  101.         fseek(arch, (unsigned)(hashete.i[2]%(archsize)), SEEK_SET);
  102.         hashete.i[3] *= ((fgetc(arch))+hashete.i[1]);
  103.         fseek(arch, (unsigned)(hashete.i[1]%(archsize)), SEEK_SET);
  104.         hashete.i[2] *= ((fgetc(arch))+hashete.i[0]);
  105.         fseek(arch, (unsigned)(hashete.i[0]%(archsize)), SEEK_SET);
  106.         hashete.i[0] *= ((fgetc(arch))+i);
  107.  
  108.         i = hashete.i[0];
  109.         fseek(arch, (unsigned)(hashete.i[0]%(archsize)), SEEK_SET);
  110.         hashete.i[0] *= ((fgetc(arch))+hashete.i[1]);
  111.         fseek(arch, (unsigned)(hashete.i[1]%(archsize)), SEEK_SET);
  112.         hashete.i[1] *= ((fgetc(arch))+hashete.i[2]);
  113.         fseek(arch, (unsigned)(hashete.i[2]%(archsize)), SEEK_SET);
  114.         hashete.i[2] *= ((fgetc(arch))+hashete.i[3]);
  115.         fseek(arch, (unsigned)(hashete.i[3]%(archsize)), SEEK_SET);
  116.         hashete.i[3] *= ((fgetc(arch))+i);
  117.  
  118.         i = hashete.i[3];
  119.         fseek(arch, (unsigned)(hashete.i[3]%(archsize)), SEEK_SET);
  120.         hashete.i[3] *= ((fgetc(arch))+hashete.i[2]);
  121.         fseek(arch, (unsigned)(hashete.i[2]%(archsize)), SEEK_SET);
  122.         hashete.i[3] *= ((fgetc(arch))+hashete.i[1]);
  123.         fseek(arch, (unsigned)(hashete.i[1]%(archsize)), SEEK_SET);
  124.         hashete.i[2] *= ((fgetc(arch))+hashete.i[0]);
  125.         fseek(arch, (unsigned)(hashete.i[0]%(archsize)), SEEK_SET);
  126.         hashete.i[0] *= ((fgetc(arch))+i);
  127.         fclose(arch);
  128.  
  129.         printf("%s -- %08x%08x%08x%08x\n", argv[x], hashete.i[0], hashete.i[1], hashete.i[2], hashete.i[3]);
  130.     }
  131.  
  132.     if(argc == 1)
  133.     {
  134.       printf("%s version: %s\n\nEl programa necesita argumentos. Ejemplo:\n", PRODUCT_NAME, VER_STRING);
  135.       printf("    %s file_1 [file_2] ... [file_n]\n\n", INTERNAL_NAME);
  136.     }
  137.     else printf("\nPicadillo generado en %lu milisegundos.\n", clock());
  138.  
  139.     return 0;
  140. }
  141.  
  142.  
  143. // Fin archivo

He reeditado este post, esto se parece más a un programa usable ahora.

He solucionado algunos problemas del mecanismo de hashing... si alguien supiera revisarlo, yo ya lo he mejorado unas cuantas veces.