Este concurso ha terminado.
Debido a la naturaleza de los desafíos de policías y ladrones , 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
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>
Respuestas:
CJam, 21 bytes
Toma una cadena de bytes como entrada.
En pseudocódigo:
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.
fuente
Python, 109 bytes [ agrietado , y de nuevo ]
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
Ejemplos
fuente
C ++, 148 bytes
__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
a
son 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:
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).
fuente
o
Parece no haber sido inicializado. ¿Dóndeoutput
se declara? O tal vezo
esoutput
?n
. ¿Realmente has verificado el código "des-uglified" para ejecutar?U i=81;i-=3
podría haber sido aún más vil, sin costos de ejecución significativos.CJam, 44 bytes [ agrietado ]
La entrada está en la base 10.
CJam es lento. Espero que se ejecute en 1 segundo en alguna computadora ...
Explicaciones
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
fuente
C++, 182 characters (+ about 51 characters of boilerplate)
Boilerplate:
Runnable program with a golfed function
fuente
__uint128_t
only after implemeting this.Pyth, 8 Cracked
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:
fuente
Python 3, 216 bytes [cracked]
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
Examples
Code explanation
An example of the padding for
f(6)
:fuente
C, 87 bytes [cracked]
This is the complete program; no wrapper required. Accepts binary input via stdin, and outputs a hexadecimal hash to stdout.
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:
Single-byte inputs:
Multi-byte inputs:
fuente
foo|
(d5c9bef71d4f5d1b) andfoo\
(d5c9bef71d4f5d1b) produce VERY similar hashes.\x00
and\x00\x00
!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.
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 input3 4 5 6
, it would calculate3 ^ (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 thea
from before on it. That is, we findp(n+5) ^ p(n+9)
mod 2128 wherep(k)
is thek
-th prime.H=:_8...\(a...)]
Perform the above function on 8-character subblocks of the input, and thena
all the results together and call the resulting hash functionH
. I use 8 characters because J's "k
-th prime" function fails whenp(k)
> 231, i.e.k=105097564
is the largest safek
.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.
* 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.
fuente
Python 3, 118 bytes [cracked]
Indentation is a single tab. Simple hash, haven't really tested it thoroughly yet.
Call as follows:
result:
73117705077050518159191803746489514685
fuente
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.)C++, 239 bytes
My very first code golf! [Please be gentle]
Ungolfed version:
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
fuente
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.Java,
299291282 bytes, cracked.Does some operations on BigIntegers, then takes the result modulo 2128.
fuente
public
yourself, saving 7 chars?C, 128 bytes [cracked]
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:
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:
fuente
C, 122 bytes [cracked]
Nested loops, half-assed LCGs, and variable swapping. What's not to love?
Here's a ungolf'd version to play around with:
This is a fully self-contains program that reads from STDIN and prints to STDOUT.
Example:
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.
fuente
PHP 4.1, 66 bytes [cracked]
I'm just warming up.
I hope you find this insteresting.
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 overhttp://localhost/file.php?a=<number>
).If you want to test it with PHP 4.2 and newer, try this:
This version only works with POST and GET.
Example output:
(I assure you that there are numbers that produce the same hash).
fuente
C, 134 bytes, Cracked
This is complete C program.
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:
fuente
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.
Wrapper (expects one argument in base-16 also known as hexadecimal):
fuente
H(2**(2**10))
took around 8 or 9 seconds, whileH(2**(2**12))
took around 29 seconds andH(2**(2**14))
took over two minutes.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.
Wrapper (not counted in the bytecount)
Run example (input is always a hexadecimal number):
fuente
Ruby, 90 Bytes
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:
fuente
comparison of String with 255 failed (ArgumentError)
.gets.to_i
in the wrapper.Mathematica, 89 bytes, cracked
Not the shortest.
fuente
PHP, 79 Bytes (cracked. With a comment):
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:
fuente
C# - 393 bytes cracked
Ungolfed:
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.
fuente
Python 2, 115 bytes [Cracked already!]
OK, here's my last effort. Only 115 bytes because the final newline isn't required.
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, soint('077')
is 77, not 63.Sample outputs:
fuente