Cryptographic hash golf

34

Este concurso ha terminado.

Debido a la naturaleza de los desafíos de , el desafío de policías se vuelve mucho más fácil cuando el interés en el desafío de ladrones asociado ha disminuido. Por lo tanto, si bien aún puede publicar funciones hash, su respuesta no será aceptada ni formará parte de la tabla de clasificación.

Este desafío es la búsqueda de la implementación más corta de una función hash que sea resistente a colisiones , es decir, no debería ser factible encontrar dos mensajes diferentes con el mismo hash.

Como policía, intenta inventar e implementar una función hash para encontrar el mejor compromiso entre el tamaño del código y la resistencia a la colisión. ¡Usa demasiados bytes y otro policía te superará!

Como ladrón, intentas frustrar los intentos de los policías al descifrar sus funciones, demostrando que no son adecuadas. ¡Esto los obligará a usar más bytes para fortalecer sus algoritmos!

Desafío policías

Tarea

Implemente una función hash criptográfica H: I -> O de su elección, donde I es el conjunto de todos los enteros no negativos por debajo de 2 2 30 y O es el conjunto de todos los enteros no negativos por debajo de 2 128 .

Puede implementar H como una función real que acepta y devuelve un solo entero, una representación de cadena de un entero o una matriz de enteros o un programa completo que lee desde STDIN e imprime en STDOUT en la base 10 o 16.

Tanteo

  • H que tiene que resistir el desafío de los ladrones define a continuación.

    Si un ladrón derrota su envío en las primeras 168 horas después de publicarlo, se considera agrietado .

  • La implementación de H debe ser lo más breve posible. La presentación sin descifrar más corta será el ganador del desafío policial.

Reglas adicionales

  • Si implementa H como una función, proporcione un contenedor para ejecutar la función desde un programa que se comporte como se explicó anteriormente.

  • Proporcione al menos tres vectores de prueba para su programa o contenedor (entradas de ejemplo y sus salidas correspondientes).

  • H puede ser su diseño novedoso (preferido) o un algoritmo conocido, siempre que lo implemente usted mismo. Está prohibido usar cualquier tipo de función hash incorporada, función de compresión, cifrado, PRNG, etc.

    Cualquier juego incorporado comúnmente utilizado para implementar funciones de hashing (por ejemplo, conversión de base) es un juego justo.

  • La salida de su programa o función debe ser determinista.

  • Debe haber un compilador / intérprete gratuito (como en cerveza) que pueda ejecutarse en una plataforma x86 o x64 o desde un navegador web.

  • Su programa o función debe ser razonablemente eficiente y debe procesar cualquier mensaje en I por debajo de 2 2 19 en menos de un segundo.

    Para los casos extremos, el tiempo (de pared) que tome mi máquina (Intel Core i7-3770, 16 GiB de RAM) será decisivo.

  • Dada la naturaleza de este desafío, está prohibido cambiar el código de su respuesta de cualquier manera, ya sea que altere la salida o no.

    Si su envío ha sido descifrado (o incluso si no lo ha sido), puede publicar una respuesta adicional.

    Si su respuesta no es válida (por ejemplo, no cumple con la especificación de E / S), elimínela.

Ejemplo

Python 2.7, 22 bytes

def H(M):
 return M%17

Envoltura

print H(int(input()))

Desafío de ladrones

Tarea

Grieta cualquiera de de los policías presentaciones mediante la publicación de la siguiente en los ladrones hilo : dos mensajes M y N en I de tal manera que H (M) = H (N) y M ≠ N .

Tanteo

  • Romper las presentaciones de cada policía te da un punto. El ladrón con más puntos gana.

    En el caso de un empate, el ladrón atado que logró la sumisión más larga gana.

Reglas adicionales

  • Cada envío de policía solo se puede descifrar una vez.

  • Si un envío de policía se basa en un comportamiento definido o no definido por la implementación, solo tiene que encontrar una grieta que funcione (verificablemente) en su máquina.

  • Cada grieta pertenece a una respuesta separada en el hilo de los ladrones.

  • Publicar un intento de craqueo inválido le prohíbe descifrar ese envío en particular durante 30 minutos.

  • No puede descifrar su propia presentación.

Ejemplo

Python 2.7, 22 bytes por usuario8675309

1

y

18

Tabla de clasificación

Envíos seguros

  1. CJam, 21 bytes por eBusiness
  2. C ++, 148 bytes por tucuxi
  3. C ++, 233 (?) Bytes por Vi.

Envíos sin descifrar

Puede usar este fragmento de pila para obtener una lista de respuestas aún no resueltas.

function g(p){$.getJSON('//api.stackexchange.com/2.2/questions/51068/answers?page='+p+'&pagesize=100&order=desc&sort=creation&site=codegolf&filter=!.Fjs-H6J36w0DtV5A_ZMzR7bRqt1e',function(s){s.items.map(function(a){var h=$('<div/>').html(a.body).children().first().text();if(!/cracked/i.test(h)&&(typeof a.comments=='undefined'||a.comments.filter(function(b){var c=$('<div/>').html(b.body);return /^cracked/i.test(c.text())||c.find('a').filter(function(){return /cracked/i.test($(this).text())}).length>0}).length==0)){var m=/^\s*((?:[^,(\s]|\s+[^-,(\s])+)\s*(?:[,(]|\s-).*?([0-9]+)/.exec(h);$('<tr/>').append($('<td/>').append($('<a/>').text(m?m[1]:h).attr('href',a.link)),$('<td class="score"/>').text(m?m[2]:'?'),$('<td/>').append($('<a/>').text(a.owner.display_name).attr('href',a.owner.link))).appendTo('#listcontent');}});if(s.length==100)g(p+1);});}g(1);
table th, table td {padding: 5px} th {text-align: left} .score {text-align: right} table a {display:block}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script><link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"><table><tr><th>Language</th><th class="score">Length</th><th>User</th></tr><tbody id="listcontent"></tbody></table>

Dennis
fuente
Si una función hash devuelve erróneamente números mayores que 2 ^ 128-1, ¿eso invalida el envío o simplemente tomamos el módulo de resultado 2 ^ 128?
Martin Ender
@ MartinBüttner: Sí, tendría que tomar el resultado módulo 2 ^ 128.
Dennis
1
@Scimonster no cumple los requisitos (hasta 2 ^ 30 bits de entrada, 128 bits de salida)
CodesInChaos
1
¿Los policías y los ladrones no suelen ir al revés?
haneefmubarak 01 de
2
Tal vez podríamos tener una regla de que las presentaciones deben incluir hashes de ejemplo, es bastante molesto tener que ejecutar el lenguaje de programación elegido por los remitentes para tener un resultado con el que comparar las implementaciones de craqueo.
aaaaaaaaaaaa

Respuestas:

6

CJam, 21 bytes

1q3*{i+_E_#*^26_#)%}/

Toma una cadena de bytes como entrada.

En pseudocódigo:

hash = 1
3 times:
    for i in input:
        hash = hash + i
        hash = hash xor hash * 14^14
        hash = hash mod (26^26 + 1)
output hash

Ejemplo de hashes:

"" (cadena vacía) -> 1
"Prueba" -> 2607833638733409808360080023081587841
"prueba" -> 363640467424586895504738713637444713

Puede ser un poco simple, el rango de salida es solo un poco más de 122 bits, el fortalecimiento de la iteración triple ya está un poco roto ya que hace exactamente lo mismo cada vez, así que ingrese ese hash a 1 en el primer La iteración será un descanso completo. Pero es breve y no es divertido estar demasiado seguro.

aaaaaaaaaaaa
fuente
¿Hay una versión C acompañante como en la otra publicación de CJam?
Vi.
@Vi. No, todavía no al menos. Nunca incursioné en bigint en C, ¿hay una biblioteca estándar para eso?
aaaaaaaaaaaa
GMP ?
Vi.
3
Aquí: pastebin.com/SDzA3JK4
apretujado ossifrage
1
@ Agawa001 Está confundiendo su terminología. Es un algoritmo hash de función de esponja de triple paso. Un cifrado César es un algoritmo de cifrado específico sin estado interno.
aaaaaaaaaaaa
7

Python, 109 bytes [ agrietado , y de nuevo ]

def f(n,h=42,m=2**128):
 while n:h+=n&~-m;n>>=128;h+=h<<10;h^=h>>6;h%=m
 h+=h<<3;h^=h>>11;h+=h<<15;return h%m

Intenté implementar la función única de Jenkins tal cual, con la única diferencia de ser la semilla y el número de bits.

Dato curioso: aparentemente Perl usó el hash de Jenkins en algún momento .

Envoltura

print(f(int(input())))

Ejemplos

>>> f(0)
12386682
>>> f(1)
13184902071
>>> f(2**128-1)
132946164914354994014709093274101144634
>>> f(2**128)
13002544814292
>>> f(2**128+1)
13337372262951
>>> f(2**(2**20))
290510273231835581372700072767153076167
Sp3000
fuente
6

C ++, 148 bytes

typedef __uint128_t U;U h(char*b,U n,U&o){U a=0x243f6a8885a308d,p=0x100000001b3;for(o=a;n--;)for(U i=27;--i;){o=(o<<i)|(o>>(128-i));o*=p;o^=b[n];}}

__uint128_t es una extensión de GCC y funciona como se esperaba. El hash se basa en iterar el hash FNV (he tomado prestada su prima, aunque ason los primeros dígitos de Pi en hexadecimal) con una rotación similar a sha1 al comienzo de cada iteración. Compilando con-O3 hashing un archivo de 10 MB lleva menos de 2 segundos, por lo que todavía hay margen para aumentar las iteraciones en el bucle interno, pero hoy me siento generoso.

Des-uglified (nombres de variables cambiados, comentarios agregados, espacios en blanco y un par de llaves) para su placer:

typedef __uint128_t U;
U h(char* input, U inputLength, U &output){
    U a=0x243f6a8885a308d,p=0x100000001b3;    
    for(output=a;inputLength--;) {   // initialize output, consume input
        for(U i=27;--i;) {                          // evil inner loop
            output = (output<<i)|(output>>(128-i)); // variable roll 
            output *= p;                            // FNV hash steps
            output ^= input[inputLength];        
        }
    }
    // computed hash now available in output
}

Las sugerencias de golf son bienvenidas (incluso si no puedo mejorar el código basado en ellas).

editar: errores tipográficos fijos en código des-uglified (la versión de golf permanece sin cambios).

tucuxi
fuente
oParece no haber sido inicializado. ¿Dónde outputse declara? O tal vez oes output?
Vi.
Lo mismo para n. ¿Realmente has verificado el código "des-uglified" para ejecutar?
Vi.
Comenzó el bruteforcer ...
Vi.
Incluso la versión de 3 rondas no es fácil.
Vi.
@Vi. Se corrigió la versión des uglificada: perdón por no comprobarlo mejor. Estoy orgulloso de ese circuito interno; U i=81;i-=3podría haber sido aún más vil, sin costos de ejecución significativos.
tucuxi
5

CJam, 44 bytes [ agrietado ]

lW%600/_z]{JfbDbGK#%GC#[md\]}%z~Bb4G#%\+GC#b

La entrada está en la base 10.

CJam es lento. Espero que se ejecute en 1 segundo en alguna computadora ...

Explicaciones

lW%600/            e# Reverse, and split into chunks with size 600.
_z                 e# Duplicate and swap the two dimensions.
]{                 e# For both versions or the array:
    JfbDb          e# Sum of S[i][j]*13^i*19^j, where S is the character values,
                   e# and the indices are from right to left, starting at 0.
    GK#%GC#[md\]   e# Get the last 32+48 bits.
}%
z~                 e# Say the results are A, B, C, D, where A and C are 32 bits.
Bb4G#%             e# E = the last 32 bits of A * 11 + C.
\+GC#b             e# Output E, B, D concatenated in binary.

Bueno, las cosas bidimensionales parecían ser una debilidad ... Tenía la intención de hacer algunos cálculos lentos más rápido al principio. Pero no puede ejecutarse en un segundo, no importa lo que haga, así que finalmente eliminé el código lento.

It should be also better if I have used binary bits and higher bases.

C version

__uint128_t hash(unsigned char* s){
    __uint128_t a=0,b=0;
    __uint128_t ar=0;
    __uint128_t v[600];
    int l=0,j=strlen(s);
    memset(v,0,sizeof v);
    for(int i=0;i<j;i++){
        if(i%600)
            ar*=19;
        else{
            a=(a+ar)*13;
            ar=0;
        }
        if(i%600>l)
            l=i%600;
        v[i%600]=v[i%600]*19+s[j-i-1];
        ar+=s[j-i-1];
    }
    for(int i=0;i<=l;i++)
        b=b*13+v[i];
    a+=ar;
    return (((a>>48)*11+(b>>48))<<96)
        +((a&0xffffffffffffull)<<48)
        +(b&0xffffffffffffull);
}
jimmy23013
fuente
Could you please add a description? Not everyone knows CJam.
orlp
@orlp Edited...
jimmy23013
This takes 0.4 s on my computer, so it's well within the allowed range.
Dennis
What is A, B, C and so on? Some matrices? Which dimensions? Can it be easily implemented in C?
Vi.
1
Cracked, I believe.
Sp3000
5

C++, 182 characters (+ about 51 characters of boilerplate)

h=0xC0CC3051F486B191;j=0x9A318B5A176B8125;char q=0;for(int i=0;i<l;++i){char w=buf[i];h+=((w<<27)*257);j^=(h+0x5233);h+=0xAA02129953CC12C3*(j>>32);j^=(w+0x134)*(q-0x16C552F34);q=w;}

Boilerplate:

void hash(const unsigned char* buf, size_t len, unsigned long long *hash1, unsigned long long *hash2)
{
    unsigned long long &h=*hash1;
    unsigned long long &j=*hash2;
    size_t l = len;
    const unsigned char* b = buf;

    // code here
}

Runnable program with a golfed function

#include <stdio.h>

// The next line is 227 characters long
int hash(char*b,int l,long long&h,long long&j){h=0xC0CC3051F486B191;j=0x9A318B5A176B8125;char q=0;for(int i=0;i<l;++i){char w=b[i];h+=((w<<27)*257);j^=(h+0x5233);h+=0xAA02129953CC12C3*(j>>32);j^=(w+0x134)*(q-0x16C552F34);q=w;}}

int main() {
    char buf[1024];
    int l  = fread(buf, 1, 1024, stdin);
    long long q, w;
    hash(buf, l, q, w);
    printf("%016llX%016llX\n", q, w);
}
Vi.
fuente
2
I think the function declaration etc. counts towards the character count.
Ypnypn
@Ypnypn, counted characters in a golfed down function declaration.
Vi.
What is the output hash? I am assuming it is ((h<<64)|j).
tucuxi
Yes. Or just a pair of 64-bit numbers. I found out about __uint128_t only after implemeting this.
Vi.
1
@Dennis, Done.󠀠
Vi.
4

Pyth, 8 Cracked

sv_`.lhQ

Try it online

A bit of a silly answer, I'll explain how it works because most people can't read Pyth. This takes the natural log of one plus the input, and then converts that to a string. That string is reversed, and then evaluated and then converted to an integer.

A python translation would look like:

import math
n = eval(input()) + 1
rev = str(math.log(n))[::-1]
print(int(eval(rev)))
FryAmTheEggman
fuente
Cracked?
Sp3000
4

Python 3, 216 bytes [cracked]

def f(m):
 h=1;p=[2]+[n for n in range(2,102)if 2**n%n==2];l=len(bin(m))-2;*b,=map(int,bin((l<<(l+25)//26*26)+m)[2:])
 while b:
  h*=h
  for P in p:
   if b:h=h*P**b.pop()%0xb6ee45a9012d1718f626305a971e6a21
 return h

Due to an incompatibility with the spec I can think of at least one slight vulnerability, but other than that I think this is at least brute-force proof. I've checked the first 10 million hashes, among other things.

In terms of golf this would be shorter in Python 2, but I've sacrificed some bytes for efficiency (since it's probably not going to win anyway).

Edit: This was my attempt at implementing the Very Smooth Hash, but unfortunately 128-bits was far too small.

Wrapper

print(f(int(input())))

Examples

>>> f(0)
2
>>> f(123456789)
228513724611896947508835241717884330242
>>> f(2**(2**19)-1)
186113086034861070379984115740337348649
>>> f(2**(2**19))
1336078

Code explanation

def f(m):
 h=1                                             # Start hash at 1
 p=[2]+[n for n in range(2,102)if 2**n%n==2]     # p = primes from 2 to 101
 l=len(bin(m))-2                                 # l = bit-length of m (input)
 *b,=map(int,bin((l<<(l+25)//26*26)+m)[2:])      # Convert bits to list, padding to
                                                 # a multiple of 26 then adding the
                                                 # bit-length at the front

 while b:                                        # For each round
  h*=h                                           # Square the hash
  for P in p:                                    # For each prime in 2 ... 101
   if b:h=(h*P**b.pop()                          # Multiply by prime^bit, popping
                                                 # the bit from the back of the list
           %0xb6ee45a9012d1718f626305a971e6a21)  # Take mod large number

 return h                                        # Return hash

An example of the padding for f(6):

[1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0]

(len 3)(------------------ 23 zeroes for padding -------------------------)(input 6)
       (---------------------------- length 26 total ------------------------------)
Sp3000
fuente
Cracked
feersum
4

C, 87 bytes [cracked]

This is the complete program; no wrapper required. Accepts binary input via stdin, and outputs a hexadecimal hash to stdout.

c;p;q;main(){while((c=getchar())+1)p=p*'foo+'+q+c,q=q*'bar/'+p;printf("%08x%08x",p,q);}

This only calculates a 64-bit hash, so I'm taking a bit of a gamble here.

In case anyone's wondering, the two constants 'foo+' and 'bar/' are the prime numbers 1718578987 and 1650553391.


Examples:

Ignores leading zeroes:

echo -ne '\x00\x00\x00\x00' |./hash
0000000000000000

Single-byte inputs:

echo -ne '\x01' |./hash
0000000100000001
echo -ne '\xff' |./hash
000000ff000000ff

Multi-byte inputs:

echo -ne '\x01\x01' |./hash
666f6f2dc8d0e15c
echo -ne 'Hello, World' |./hash
04f1a7412b17b86c
squeamish ossifrage
fuente
How would it behave with 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa' and 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa'?
Ismael Miguel
1
foo| (d5c9bef71d4f5d1b) and foo\ (d5c9bef71d4f5d1b) produce VERY similar hashes.
Ismael Miguel
1
Broke it!!! \x00 and \x00\x00!
Ismael Miguel
1
Based on the chat comments, I believe this is still not cracked yet? Just double checking, because the upvoted comment might be confusing to those who are skimming for uncracked hashes.
Sp3000
3

J - 39 bytes - cracked

Function taking a string as input and returning an integer < 2128. I am assuming we have to name our function to be valid, so drop another 3 chars from the count if we can submit anonymous functions.

H=:_8(".p:@+5,9:)a\(a=.(2^128x)&|@^/@)]

For those of you that don't read hieroglyphics, here's a rundown of what I'm doing.

  • a=.(2^128x)&|@^/@ This is a subroutine* which takes an array of numbers, and then treats it as a power tower, where exponentiation is taken mod 2128. By "power tower", I mean if you gave it the input 3 4 5 6, it would calculate 3 ^ (4 ^ (5 ^ 6)).
  • (".p:@+5,9:)a This function takes a string, converts it to the number N, and then calculates the (n+5)-th and (n+9)-th prime numbers, and then throws the a from before on it. That is, we find p(n+5) ^ p(n+9) mod 2128 where p(k) is the k-th prime.
  • H=:_8...\(a...)] Perform the above function on 8-character subblocks of the input, and then a all the results together and call the resulting hash function H. I use 8 characters because J's "k-th prime" function fails when p(k) > 231, i.e. k=105097564 is the largest safe k.

Have some sample outputs. You can try this yourself online at tryj.tk, but I really recommend doing this at home by downloading the interpreter from Jsoftware.

   H=:_8(".p:@+5,9:)a\(a=.(2^128x)&|@^/@)]
   H '88'
278718804776827770823441490977679256075
   H '0'
201538126434611150798503956371773
   H '1'
139288917338851014461418017489467720433
   H '2'
286827977638262502014244740270529967555
   H '3'
295470173585320512295453937212042446551
   30$'0123456789'  NB. a 30 character string
012345678901234567890123456789
   H 30$'0123456789'
75387099856019963684383893584499026337
   H 80$'0123456789'
268423413606061336240992836334135810465

* Technically, it's not a function in and of itself, it attaches to other functions and acts on their output. But this is a semantic issue of J, not a conceptual difference: the program flow is as I described it above.

algorithmshark
fuente
Cracked
Sp3000
2

Python 3, 118 bytes [cracked]

def H(I):
    o=0;n=3;M=1<<128
    for c in I:i=ord(c);o=(o<<i^o^i^n^0x9bb90058bcf52d3276a7bf07bcb279b7)%M;n=n*n%M
    return o

Indentation is a single tab. Simple hash, haven't really tested it thoroughly yet.

Call as follows:

print(H("123456789"))

result: 73117705077050518159191803746489514685

tomsmeding
fuente
How should the input integer be converted to a string to use in your algorithm?
feersum
@feersum base-10 string is what I tested. It doesn't use anything but ord(c) though, so really, any string will do :) (except things like nul chars, I think those make hash collisions really easy. So stick with a 0-9 string.)
tomsmeding
1
Broke it: codegolf.stackexchange.com/a/51160/41288. Started out by observing that strings like "10000" and "20000" produce very close hashes. Started to play around with more and more zeroes, and after 128 or so, any digit + k*4 zeroes repeats returns the same hash regardless of k.
tucuxi
@tucuxi Already thought it shouldn't bee too hard; glad that is wasn't trivial but that someone broke it anyway. Good work.
tomsmeding
2

C++, 239 bytes

My very first code golf! [Please be gentle]

#define r(a,b) ((a<<b)|(a>>(64-b)))
typedef uint64_t I;I f(I*q, I n, I&h){h=0;for(I i=n;--i;)h=r(h^(r(q[i]*0x87c37b91114253d5,31)*0x4cf5ad432745937f),31)*5+0x52dce729;h^=(h>>33)*0xff51afd7ed558ccd;h^=(h>>33)*0xc4ceb9fe1a85ec53;h^=(h>>33);}

Ungolfed version:

I f(I* q, I n, I& h) // input, length and output
{
    h = 0; // initialize hashes
    for (I i=n;--i;)
    {
        q[i] *= 0x87c37b91114253d5;
        q[i]  = rotl(q[i], 31);
        q[i] *= 0x4cf5ad432745937f;

        h ^= q[i]; // merge the block with hash

        h *= rotl(h, 31);
        h = h * 5 + 0x52dce729;
    }
    h ^= h>>33;
    h *= 0xff51afd7ed558ccd;
    h ^= h>>33;
    h *= 0xc4ceb9fe1a85ec53; // avalanche!
    h ^= h>>33;
}

Not the best hash, and definitely not the shortest code in existence. Accepting golfing tips and hoping to improve!

Wrapper

Probably not the best in the world, but a wrapper nonetheless

I input[500];

int main()
{
    string s;
    getline(cin, s);
    memcpy(input, s.c_str(), s.length());
    I output;
    f(input, 500, output);
    cout << hex << output << endl;
}
SpelingMistake
fuente
2
Looks solid, but with 64 bits, it may be subject to brute-forcing. There is about a 50% chance to find a collision in ~sqrt(n) tests (from among n total outputs); 2^32 tries is not that much for a modern pc.
tucuxi
Wrapper lacks header inclusions and in general leads to many equal hashes.
Vi.
Provide some hash samples. For me both "3" and "33" lead to 481c27f26cba06cf (using this wrapper).
Vi.
Cracked: codegolf.stackexchange.com/a/51215/41288 . I suspect right before @Vi. found out why so many hashes were equal.
tucuxi
1
Proper collision (without bug using): printf '33333333\x40\xF3\x32\xD6\x56\x91\xCA\x66' | ./hash7_ -> a4baea17243177fd; printf '33333333\x77\x39\xF3\x82\x93\xDE\xA7\x2F' | ./hash7_ -> a4baea17243177fd. The bruteforcer finds collisions here much faster compared to in other 64-bit hash here.
Vi.
2

Java, 299 291 282 bytes, cracked.

import java.math.*;class H{public static void main(String[]a){BigInteger i=new java.util.Scanner(System.in).nextBigInteger();System.out.print(BigInteger.valueOf(i.bitCount()*i.bitLength()+1).add(i.mod(BigInteger.valueOf(Long.MAX_VALUE))).modPow(i,BigInteger.valueOf(2).pow(128)));}}

Does some operations on BigIntegers, then takes the result modulo 2128.

SuperJedi224
fuente
How do I run this? Ideone refuses to compile it.
Martin Ender
1
You can run it on Ideone by renaming the class to "Main" or removing the first "public" keyword (but NOT the second one). Either one will work.
SuperJedi224
Cracked.
Martin Ender
1
@SuperJedi224 Why not remove the first public yourself, saving 7 chars?
user253751
@immibis Because then I don't think it would work right on Eclipse. I'll try it though. EDIT: I guess it does. That's a surprise.
SuperJedi224
2

C, 128 bytes [cracked]

p;q;r;s;main(c){while((c=getchar())+1)p=p*'foo+'+s^c,q=q*'bar/'+p,r=r*'qux3'^q,s=s*'zipO'+p;printf("%08x%08x%08x%08x",p,q,r,s);}

This is more or less the same algorithm as my last effort (cracked by Vi.), but now has enough hamster wheels to generate proper 128-bit hashes.

The four prime constants in the code are as follows:

'foo+' = 1718578987
'bar/' = 1650553391
'qux3' = 1903523891
'zipO' = 2053730383

As before, this is a complete program with no need for a wrapper. The integer I is input via stdin as raw binary data (big-endian), and the hash O is printed in hex to stdout. Leading zeroes in I are ignored.

Examples:

echo -ne '\x00' |./hash
00000000000000000000000000000000
echo -ne '\x00\x00' |./hash
00000000000000000000000000000000
echo -ne '\x01' |./hash
00000001000000010000000100000001
echo -ne 'A' |./hash
00000041000000410000004100000041
echo -ne '\x01\x01' |./hash
666f6f2dc8d0e15cb9a5996fe0d8df7c
echo -ne 'Hello, World' |./hash
da0ba2857116440a9bee5bb70d58cd6a
squeamish ossifrage
fuente
Didn't your example show a collision right there (the first two)?
mbomb007
@mbomb007 No. The input is a number between 0 and 2^(2^30). 0x00 and 0x0000 are both equal to zero, so they produce the same output.
squeamish ossifrage
2

C, 122 bytes [cracked]

long long x,y,p;main(c){for(c=9;c|p%97;c=getchar()+1)for(++p;c--;)x=x*'[3QQ'+p,y^=x^=y^=c*x;printf("%016llx%016llx",x,y);}

Nested loops, half-assed LCGs, and variable swapping. What's not to love?

Here's a ungolf'd version to play around with:

long long x,y,p;

int main(int c){
    // Start with a small number of iterations to
    //   get the state hashes good and mixed because initializing takes space
    // Then, until we reach the end of input (EOF+1 == 0)
    //   and a position that's a multiple of 97
    for (c=9;c|p%97;c=getchar()+1) {

        // For each input c(haracter) ASCII value, iterate down to zero
        for (++p;c--;) {

            // x will act like a LCG with a prime multiple
            //   partially affected by the current input position
            // The string '[3QQ' is the prime number 0x5B335151
            x=x*'[3QQ'+p;

            // Mix the result of x with the decrementing character
            y^=c*x;

            // Swap the x and y buffers
            y^=x^=y;
        }
    }

    // Full 128-bit output
    printf("%016llx%016llx",x,y);
    return 0;
}

This is a fully self-contains program that reads from STDIN and prints to STDOUT.

Example:

> echo -n "Hello world" | ./golfhash
b3faef341f70c5ad6eed4c33e1b55ca7

> echo -n "" | ./golfhash
69c761806803f70154a7f816eb3835fb

> echo -n "a" | ./golfhash
5f0e7e5303cfcc5ecb644cddc90547ed

> echo -n "c" | ./golfhash
e64e173ed4415f7dae81aae0137c47e5

In some simple benchmarks, it hashes around 3MB/s of text data. The hash speed depends on the input data itself, so that should probably be taken into consideration.

Mr. Llama
fuente
1
Cracked: codegolf.stackexchange.com/a/51354/101
aaaaaaaaaaaa
1

PHP 4.1, 66 bytes [cracked]

I'm just warming up.

I hope you find this insteresting.

<?for($l=strlen($b.=$a*1);$i<40;$o.=+$b[+$i]^"$a"/$a,$i++);echo$o;

I've tried it numbers as large as 999999999999999999999999999.
The output seemed to be within the 2128 range.


PHP 4.1 is required because of the register_globals directive.

It works by automatically creating local variables from the session, POST, GET, REQUEST and cookies.

It uses the key a. (E.G.: access over http://localhost/file.php?a=<number>).

If you want to test it with PHP 4.2 and newer, try this:

<?for($l=strlen($b.=$a=$_REQUEST['a']*1);$i<40;$o.=+$b[+$i]^"$a"/$a,$i++);echo$o;

This version only works with POST and GET.


Example output:

0 -> 0000000000000000000000000000000000000000
9 -> 8111111111111111111111111111111111111111
9999 -> 8888111111111111111111111111111111111111
1234567890 -> 0325476981111111111111111111111111111111
99999999999999999999999999999999999999999999999999999999999999999999999999999999 -> 0111191111111111111111111111111111111111

(I assure you that there are numbers that produce the same hash).

Ismael Miguel
fuente
1

C, 134 bytes, Cracked

This is complete C program.

long long i=0,a=0,e=1,v,r;main(){for(;i++<323228500;r=(e?(scanf("%c",&v),e=v>'/'&&v<':',v):(a=(a+1)*7)*(7+r)));printf("0x%llx\n", r);}

What it does: The idea is to take input as byte array and append pseudo random (but deterministic) bytes at the end to make the length equal to about 2230 (a bit more). The implementation reads input byte by byte and starts using pseudo random data when it finds the first character that isn't a digit.

As builtin PRNG isn't allowed I implemented it myself.

There is undefined/implementation defined behavior that makes the code shorter (the final value should be unsigned, and I should use different types for different values). And I couldn't use 128 bit values in C. Less obfuscated version:

long long i = 0, prand = 0, notEndOfInput = 1, in, hash;

main() {
    for (; i++ < 323228500;) {
        if (notEndOfInput) {
            scanf("%c", &in);
            notEndOfInput = in >= '0' && in <= '9';
            hash = in;
        } else {
            prand = (prand + 1)*7;
            hash = prand*(7 + hash);
        }
    }
    printf("0x%llx\n", hash);
}
barteks2x
fuente
Cracked
squeamish ossifrage
1

Python 2.X - 139 bytes [[Cracked]]

This is quite similar to all the other (LOOP,XOR,SHIFT,ADD) hashes out here. Come get your points robbers ;) I'll make a harder one after this one is solved.

M=2**128
def H(I):
 A=[1337,8917,14491,71917];O=M-I%M
 for z in range(73):
  O^=A[z%4]**(9+I%9);O>>=3;O+=9+I**(A[z%4]%A[O%4]);O%=M
 return O

Wrapper (expects one argument in base-16 also known as hexadecimal):

import sys
if __name__ == '__main__':
 print hex(H(long(sys.argv[1], 16)))[2:][:-1].upper()
Puzzled
fuente
1
Also, I am not sure that this entry meets the OP's spec, since on my machine the function takes multiple seconds on large inputs. For example, H(2**(2**10)) took around 8 or 9 seconds, while H(2**(2**12)) took around 29 seconds and H(2**(2**14)) took over two minutes.
mathmandan
You are absolutely right, I obviously should have tested the timing for larger inputs. Also, I appear to have forgot to run my own test after that shift was added. The original version was without shift (before posting) and it was passing my "no collisions in the first 100000 integers" test :/
Puzzled
1

Python 2.7 - 161 bytes [[Cracked]]

Well since I managed to change my first hash function into an useless version before posting it, I think I will post another version of a similar structure. This time I tested it against trivial collisions and I tested most of the possible input magnitudes for speed.

A=2**128;B=[3,5,7,11,13,17,19]
def H(i):
 o=i/A
 for r in range(9+B[i%7]):
  v=B[i%7];i=(i+o)/2;o=o>>v|o<<128-v;o+=(9+o%6)**B[r%6];o^=i%(B[r%6]*v);o%=A
 return o

Wrapper (not counted in the bytecount)

import sys
if __name__ == '__main__':
 arg = long(sys.argv[1].strip(), 16)
 print hex(H(arg))[2:][:-1].upper()

Run example (input is always a hexadecimal number):

$ python crypt2.py 1
3984F42BC8371703DB8614A78581A167
$ python crypt2.py 10
589F1156882C1EA197597C9BF95B9D78
$ python crypt2.py 100
335920C70837FAF2905657F85CBC6FEA
$ python crypt2.py 1000
B2686CA7CAD9FC323ABF9BD695E8B013
$ python crypt2.py 1000AAAA
8B8959B3DB0906CE440CD44CC62B52DB
Puzzled
fuente
1
Cracked.
jimmy23013
Well done jimmy :)
Puzzled
1

Ruby, 90 Bytes

def H(s);i=823542;s.each_byte{|x|i=(i*(x+1)+s.length).to_s.reverse.to_i%(2**128)};i;end

A highly random hash algorithm I made up without looking at any real hashes...no idea if it is good. it takes a string as input.

Wrapper:

def buildString(i)
  if(i>255)
    buildString(i/256)+(i%256).chr
  else
    i.chr
  end
end 
puts H buildString gets
MegaTom
fuente
Could you please provide the wrapper the question requires?
Dennis
What's the input format? I tried with a number but it says comparison of String with 255 failed (ArgumentError).
jimmy23013
H takes a string, Build string takes the number required by the OP and transforms it to a string.
MegaTom
I think you need a gets.to_i in the wrapper.
jimmy23013
Cracked.
jimmy23013
0

Mathematica, 89 bytes, cracked

Last@CellularAutomaton[(a=Mod)[#^2,256],{#~IntegerDigits~2,0},{#~a~99,128}]~FromDigits~2&

Not the shortest.

LegionMammal978
fuente
3
How do you run this without Mathematica? "There should be a free (as in beer) compiler/interpreter that can be run on a x86 or x64 platform or from within a web browser."
Martin Ender
2
@MartinBüttner wolfram.com/mathematica/trial
LegionMammal978
Cracked.
Martin Ender
0

PHP, 79 Bytes (cracked. With a comment):

echo (('.'.str_replace('.',M_E*$i,$i/pi()))*substr(pi(),2,$i%20))+deg2rad($i);

This does alot of scary things via type-conversions in php, which makes it hard to predict ;) (or at least I hope so). It's not the shortest or most unreadable answer, however.

To run it you can use PHP4 and register globals (with ?i=123) or use the commandline:

php -r "$i = 123.45; echo (('.'.str_replace('.',M_E*$i,$i/pi()))*substr(pi(),2,$i%20))+deg2rad($i);"
Sebb
fuente
5
The hash's output value looks floating-point. And It's the same for 3000000000000000000000000000000000000000000001 and 3000000000000000000000000000000000000000000000.
Vi.
0

C# - 393 bytes cracked

using System;class P{static void Main(string[]a){int l=a[0].Length;l=l%8==0?l/8:l/8+1;var b=new byte[l][];for(int i=0;i<l;i++){b[i]=new byte[8];};int j=l-1,k=7;for(int i=0;i<a[0].Length;i++){b[j][k]=Convert.ToByte(""+a[0][i],16);k--;if((i+1)%8==0){j--;k=7;}}var c=0xcbf29ce484222325;for(int i=0;i<l;i++){for(int o=0;o<8;o++){c^=b[i][o];c*=0x100000001b3;}}Console.WriteLine(c.ToString("X"));}}

Ungolfed:

using System;
class P
{
    static void Main(string[]a)
    {
      int l = a[0].Length;
      l = l % 8 == 0 ? l / 8 : l / 8 + 1;
      var b = new byte[l][];
      for (int i = 0; i < l; i++) { b[i] = new byte[8]; };
      int j = l-1, k = 7;
      for (int i = 0; i < a[0].Length; i++)
      {
        b[j][k] = Convert.ToByte(""+a[0][i], 16);
        k--;
        if((i+1) % 8 == 0)
        {
          j--;
          k = 7;
        }
      }
      var c = 0xcbf29ce484222325;
      for (int i = 0; i < l; i++)
      {
        for (int o = 0; o < 8; o++)
        {
          c ^= b[i][o];
          c *= 0x100000001b3;
        }
      }
      Console.WriteLine(c.ToString("X"));
    }
}

I have never touched cryptography or hashing in my life, so be gentle :)

It's a simple implementation of an FNV-1a hash with some array pivoting on the input. I am sure there is a better way of doing this but this is the best I could do.

It might use a bit of memory on long inputs.

ldam
fuente
Cracked: codegolf.stackexchange.com/a/51277/101 On top of having faulty padding, this is not a cryptographic hash, there is so many ways to break it.
aaaaaaaaaaaa
0

Python 2, 115 bytes [Cracked already!]

OK, here's my last effort. Only 115 bytes because the final newline isn't required.

h,m,s=1,0,raw_input()
for c in[9+int(s[x:x+197])for x in range(0,len(s),197)]:h+=pow(c,257,99**99+52)
print h%4**64

This is a complete program that inputs a decimal integer on stdin and prints a decimal hash value on stdout. Extra leading zeroes will result in different hash values, so I'll just assume that the input doesn't have any.

This works by stuffing 197-digit chunks of the input number through a modular exponentiation. Unlike some languages, the int() function always defaults to base 10, so int('077') is 77, not 63.

Sample outputs:

$ python hash.py <<<"0"
340076608891873865874583117084537586383

$ python hash.py <<<"1"
113151740989667135385395820806955292270

$ python hash.py <<<"2"
306634563913148482696255393435459032089

$ python hash.py <<<"42"
321865481646913829448911631298776772679

$ time python hash.py <<<`python <<<"print 2**(2**19)"`
233526113491758434358093601138224122227

real    0m0.890s   <-- (Close, but fast enough)
user    0m0.860s
sys     0m0.027s
squeamish ossifrage
fuente
1
It didn't use the order of blocks... Cracked.
jimmy23013
Ugh. I give in :-(
squeamish ossifrage