En el espíritu del concurso Underhanded C , estoy comenzando un concurso de código Underhanded Code. El objetivo de este concurso es implementar directamente un código, mientras se oculta sutilmente un error nefasto en su interior.

El concurso

Eres un topo secreto ruso que trabaja en el departamento de TI de una agencia de espionaje estadounidense. Su jefe estadounidense acaba de pedirle que implemente un algoritmo de hash de contraseña para usar para cifrar mensajes secretos.

Su jefe quiere que implemente la siguiente función:

f: String -> byte[16]

que convierte una contraseña en una cantidad de 16 bytes adecuada para usar como clave AES. Su jefe quiere una función segura, lo que en este contexto significa que diferentes cadenas de contraseña deberían generar resultados diferentes con una probabilidad abrumadora. Por ejemplo, devolver el hash md5 de la entrada sería una implementación simple de f.

Por supuesto, su verdadero jefe en la agencia de espionaje rusa querría que usted subvierta este proceso. Su tarea es implementar de fmanera que los rusos puedan descifrar todos los mensajes secretos cifrados con las claves devueltas por f.

Para hacerlo, debe implementar de fmodo que devuelva solo un pequeño subconjunto de las 2 ^ 128 salidas posibles. En particular, fdebe devolver a lo sumo 2 ^ 16 resultados diferentes para que los rusos puedan hacer una búsqueda fácil por fuerza bruta de la clave correcta para cada mensaje cifrado que desean descifrar.

Tenga en cuenta, sin embargo, que el espionaje conlleva la pena de muerte. Para no quedar atrapado, su función fdebe generar al menos 2 ^ 8 resultados diferentes, por lo que una inspección superficial de algunas salidas fes poco probable que revele un duplicado. Y lo más importante, el código que introduce para limitar el rango de fdebe parecer involuntario, no deliberado. Si alguna vez lo llevan a una sala del tribunal, debe haber alguna duda razonable sobre si introdujo el error deliberadamente o por accidente.

Juzgar

Yo y otros dos que recluto juzgaremos las entradas (envíeme un correo electrónico si desea juzgar). Estoy ofreciendo una recompensa de 200 reputación por la entrada ganadora. Las presentaciones deben cargarse antes del 1 de mayo.

La evaluación tendrá en cuenta los siguientes criterios:

• Se fadhiere a la especificación, es decir, genera entre 2 ^ 8 y 2 ^ 16 salidas posibles. No sienta que estos son límites duros, pero deduciremos puntos si está demasiado fuera de alcance.
• ¿Es el error plausiblemente el resultado de un error involuntario?
• ¿Las salidas de flook al azar?
• Cuanto más corta sea su implementación f, mejor.
• Cuanto más clara sea su implementación f, mejor.

Notas

Puede usar cualquier idioma para implementar su código. Está tratando de ocultar un error a simple vista, por lo que no se sugiere el código ofuscado.

Es posible que desee echar un vistazo a algunos de los ganadores anteriores del concurso Underhanded C para tener una idea de lo que hace una buena presentación.

Las cadenas de entrada serán ascii imprimibles (32 a 126, inclusive). Puede asumir una longitud máxima razonable si lo desea.

do

2 ^ 16 salidas posibles (o 2 ^ 8 veces el número de caracteres utilizados).
Utiliza la implementación MD5 de Linux, que es, AFAIK, bien. Pero esto da el mismo hash, por ejemplo, para "40" y "42".
EDITAR: renombrado bcopya memcpy(parámetros intercambiados, por supuesto).
EDITAR: convertido de programa a función, para cumplir mejor los requisitos.

#include <string.h>
#include <openssl/md5.h>

void f(const unsigned char *input, unsigned char output[16]) {

    /* Put the input in a 32-byte buffer, padded with zeros. */
    unsigned char workbuf[32] = {0};
    strncpy(workbuf, input, sizeof(workbuf));

    unsigned char res[MD5_DIGEST_LENGTH];
    MD5(workbuf, sizeof(workbuf), res);

    /* NOTE: MD5 has known weaknesses, so using it isn't 100% secure.
     * To compensate, prefix the input buffer with its own MD5, and hash again. */
    memcpy(workbuf+1, workbuf, sizeof(workbuf)-1);
    workbuf[0] = res[0];
    MD5(workbuf, sizeof(workbuf), res);

    /* Copy the result to the output buffer */
    memcpy(output, res, 16);
}

/* Some operating systems don't have memcpy(), so include a simple implementation */
void *
memcpy(void *_dest, const void *_src, size_t n)
{
    const unsigned char *src = _src;
    unsigned char *dest = _dest;
    while (n--) *dest++ = *src++;
    return _dest;
}

do

Puede que esta no sea la entrada más llamativa del concurso, pero creo que el siguiente es el tipo de función hash que podría haber hecho cualquier codificador demasiado inteligente para su propio bien, con una vaga idea del tipo de operaciones que ves en las funciones hash:

#include <stdio.h>
#include <string.h>
#include <stdint.h>

void hash(const char* s, uint8_t* r, size_t n)
{
     uint32_t h = 123456789UL;
     for (size_t i = 0; i < n; i++) {
          for (const char* p = s; *p; p++) {
               h = h * 33 + *p;
          }
          *r++ = (h >> 3) & 0xff;
          h = h ^ 987654321UL;
     }
}

int main()
{
     size_t n = 1024;
     char s[n];
     size_t m = 16;
     uint8_t b[m];
     while (fgets(s, n, stdin)) {
          hash(s, b, m);
          for (size_t i = 0; i < m; ++i)
               printf("%02x", b[i]);
          printf("\n");
     }
}

De hecho, la función hash no puede devolver más de L * 2048 resultados diferentes, donde L es el número de longitudes de cadena de entrada diferentes que pueden ocurrir. En la práctica, probé el código en 1.85 millones de líneas de entrada únicas de páginas manuales y documentos html en mi computadora portátil, y obtuve solo 85428 hashes únicos diferentes.

Scala:

// smaller values for more easy tests:
val len = 16
// make a 16 bytes fingerprint
def to16Bytes (l: BigInt, pos: Int=len) : List[Byte] = 
  if (pos == 1) List (l.toByte) else (l % 256L).toByte :: to16Bytes (l / 256L, pos-1)
/** if number isn't prime, take next */
def nextProbPrime (l: BigInt) : BigInt = 
  if (l.isProbablePrime (9)) l else nextProbPrime (l + 1)
/** Take every input, shift and add, but take primes */
def codify (s: String): BigInt = 
  (BigInt (17) /: s) ((a, b) => nextProbPrime (a * BigInt (257) + b))
/** very, very short Strings - less than 14 bytes - have to be filled, to obscure them a bit: */
def f (s: String) : Array [Byte] = {
  val filled = (if (s.size < 14) s + "secret" + s else s)
  to16Bytes (codify (filled + filled.reverse)).toArray.map (l => nextProbPrime (l).toByte) 
}

Prueba, si el resultado no se ve similar para una entrada similar:

val samples = List ("a", "aa", "b", "", "longer example", "This is a foolish, fishy test") 

samples.map (f) 

 List[Array[Byte]] = List(
Array (-41, -113, -79, 127, 29, 127, 31, 67, -19, 83, -73, -31, -101, -113, 97, -113), 
Array (-19, 7, -43, 89, -97, -113, 47, -53, -113, -127, -31, -113, -67, -23, 127, 127), 
Array (-41, -113, -79, 127, 29, 127, 31, 67, -19, 83, -73, -31, -101, -113, 97, -113), 
Array (37, -19, -7, 67, -83, 89, 59, -11, -23, -47, 97, 83, 19, 2, 2, 2), 
Array (79, 101, -47, -103, 47, -13, 29, -37, -83, -3, -37, 59, 127, 97, -43, -43), 
Array (37, 53, -43, -73, -67, 5, 11, -89, -37, -103, 107, 97, 37, -71, 59, 67))

El error está usando solo primos para la codificación. En lugar de

scala> math.pow (256, 16)
res5: Double = 3.4028236692093846E38

valores, terminamos con

scala> math.pow (54, 16)
res6: Double = 5.227573613485917E27

ya que hay 54 primos por debajo de 256.