34
\$\begingroup\$

This contest is over.

Due to the nature of challenges, the cops challenge becomes a lot easier when the interest in the associated robbers challenge has diminished. Therefore, while you can still post hash functions, your answer will not get accepted or form part of the leaderboard.

This challenge is a search for the shortest implementation of a hash function that is collision resistant, i.e., it should be infeasible to find two different messages with the same hash.

As a cop, you try to invent and implement a hash function finding the best compromise between code size and collision resistance. Use too many bytes and another cop will outgolf you!

As a robber, you try to foil the cops' attempts by cracking their functions, proving that they are unsuitable. This will force them to use more bytes to strengthen their algorithms!

Cops challenge

Task

Implement a cryptographic hash function H : I -> O of your choice, where I is the set of all non-negative integers below 2230 and O is the set of all non-negative integers below 2128.

You can either implement H as an actual function that accepts and returns a single integer, a string representation of an integer or an array of integers or a full program that reads from STDIN and prints to STDOUT in base 10 or 16.

Scoring

  • H that it has to resist the robbers challenge defined below.

    If a robber defeats your submission in the first 168 hours after posting it, it is considered cracked.

  • The implementation of H should be as short as possible. The shortest uncracked submission will be the winner of the cops challenge.

Additional rules

  • If you implement H as a function, please provide a wrapper to execute the function from within a program that behaves as explained above.

  • Please provide at least three test vectors for your program or wrapper (example inputs and their corresponding outputs).

  • H can be your novel design (preferred) or a well-known algorithm, as long as you implement it yourself. It is forbidden to use any kind in-built hash function, compression function, cipher, PRNG, etc.

    Any built-in commonly used to implement hashing functions (e.g., base conversion) is fair game.

  • The output of your program or function must be deterministic.

  • 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.

  • Your program or function should be reasonably efficient and has to hash any message in I below 2219 in less than a second.

    For edge cases, the (wall) time taken on my machine (Intel Core i7-3770, 16 GiB of RAM) will be decisive.

  • Given the nature of this challenge, it is forbidden to change the code of your answer in any way, whether it alters the output or not.

    If your submission has been cracked (or even if it hasn't), you can post an additional answer.

    If your answer is invalid (e.g., it doesn't comply with the I/O specification), please delete it.

Example

Python 2.7, 22 bytes

def H(M):
 return M%17

Wrapper

print H(int(input()))

Robbers challenge

Task

Crack any of the cops' submissions by posting the following in the robbers' thread: two messages M and N in I such that H(M) = H(N) and M ≠ N.

Scoring

  • Cracking each cop submissions gains you one point. The robber with the most points wins.

    In the case of a tie, the tied robber that cracked the longest submission wins.

Additional rules

  • Every cop submission can only be cracked once.

  • If a cop submission relies on implementation-defined or undefined behavior, you only have to find a crack that works (verifiably) on your machine.

  • Each crack belongs to a separate answer in the robbers' thread.

  • Posting an invalid cracking attempt bans you from cracking that particular submission for 30 minutes.

  • You may not crack your own submission.

Example

Python 2.7, 22 bytes by user8675309

1

and

18

Leaderboard

Safe submissions

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

Uncracked submissions

You can use this Stack Snippet to get a list of not yet cracked answers.

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>

\$\endgroup\$
  • \$\begingroup\$ If a hash function erroneously returns numbers greater than 2^128-1, does that invalidate the submission, or would we simply take the result modulo 2^128? \$\endgroup\$ – Martin Ender May 31 '15 at 14:51
  • \$\begingroup\$ @MartinBüttner: Yes, you'd have to take the result modulo 2^128. \$\endgroup\$ – Dennis May 31 '15 at 14:56
  • 1
    \$\begingroup\$ @Scimonster Doesn't meet the requirements (up to 2^30 bits of input, 128 bits of output) \$\endgroup\$ – CodesInChaos May 31 '15 at 18:47
  • 1
    \$\begingroup\$ Doesn't cops and robbers usually go the other way around? \$\endgroup\$ – haneefmubarak Jun 1 '15 at 1:02
  • 2
    \$\begingroup\$ Perhaps we could have a rule that submissions must include example hashes, it is quite annoying to have to run the submitters chosen programming language in order to have a result to compare ones cracking implementation against. \$\endgroup\$ – aaaaaaaaaaaa Jun 4 '15 at 17:21

23 Answers 23

6
\$\begingroup\$

CJam, 21 bytes

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

Takes a string of bytes as input.

In pseudocode:

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

Example hashes:

"" (empty string) -> 1
"Test" -> 2607833638733409808360080023081587841
"test" -> 363640467424586895504738713637444713

It may be a bit on the simple side, the output range is only a little more than 122 bits, the triple iteration strengthening is already a bit broken as it does exactly the same thing every time, so input that hash to 1 in the first iteration will be a full break. But it is short, and there is no fun in being too safe.

\$\endgroup\$
  • \$\begingroup\$ Is there an accompanying C version like in the other CJam post? \$\endgroup\$ – Vi. Jun 3 '15 at 12:40
  • \$\begingroup\$ @Vi. No, not yet at least. I never dabbled with bigint in C, is there a standard library for that? \$\endgroup\$ – aaaaaaaaaaaa Jun 3 '15 at 12:44
  • \$\begingroup\$ GMP? \$\endgroup\$ – Vi. Jun 3 '15 at 13:16
  • 3
    \$\begingroup\$ Here: pastebin.com/SDzA3JK4 \$\endgroup\$ – squeamish ossifrage Jun 3 '15 at 14:01
  • 1
    \$\begingroup\$ @Agawa001 You are getting your terminology mixed up. It is a triple-pass sponge function hash algorithm. A Caesar cipher is one specific encryption algorithm with no inner state. \$\endgroup\$ – aaaaaaaaaaaa Jun 15 '15 at 18:08
7
\$\begingroup\$

Python, 109 bytes [cracked, and again]

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

I tried implementing Jenkins' one-at-a-time function as-is, with the only difference being the seed and the number of bits.

Fun fact: Apparently Perl used the Jenkins' hash at some point.

Wrapper

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

Examples

>>> 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
\$\endgroup\$
6
\$\begingroup\$

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 is a GCC extension, and works as expected. The hash is based on iterating FNV hash (I've borrowed their prime, although a is the first digits of Pi in hex) with a sha1-like rotation at the start of each iteration. Compiling with -O3, hashing a 10MB file takes under 2 seconds, so there is still margin for upping the iterations in the inner loop - but I'm feeling generous today.

De-uglified (changed variable names, added comments, whitespace and a pair of braces) for your cracking pleasure:

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
}

Golfing suggestions are welcome (even if I don't get to improve the code based on them).

edit: fixed typos in de-uglified code (golfed version remains unchanged).

\$\endgroup\$
  • \$\begingroup\$ o seems to be uninitialized. Where output is declared? Or maybe o is output? \$\endgroup\$ – Vi. Jun 2 '15 at 13:03
  • \$\begingroup\$ The same for n. Have you actually checked the "de-uglified" code to run? \$\endgroup\$ – Vi. Jun 2 '15 at 13:05
  • \$\begingroup\$ Started the bruteforcer... \$\endgroup\$ – Vi. Jun 2 '15 at 13:07
  • \$\begingroup\$ Even 3-round version is not easy. \$\endgroup\$ – Vi. Jun 2 '15 at 13:16
  • \$\begingroup\$ @Vi. Fixed de-uglified version -- sorry for not checking it better. I'm proud of that inner loop; U i=81;i-=3 could have been even more vile, without significant runtime costs. \$\endgroup\$ – tucuxi Jun 2 '15 at 16:02
5
\$\begingroup\$

CJam, 44 bytes [cracked]

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

Input is in base 10.

CJam is slow. I hope it runs in 1 second in some computer...

Explanations

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.

Well, the two dimensional things seemed to be a weakness... It was intended to make some slow calculations faster at the beginning. But it cannot run in a second no matter what I do, so I removed the slow code finally.

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);
}
\$\endgroup\$
  • \$\begingroup\$ Could you please add a description? Not everyone knows CJam. \$\endgroup\$ – orlp Jun 1 '15 at 2:51
  • \$\begingroup\$ @orlp Edited... \$\endgroup\$ – jimmy23013 Jun 1 '15 at 3:21
  • \$\begingroup\$ This takes 0.4 s on my computer, so it's well within the allowed range. \$\endgroup\$ – Dennis Jun 1 '15 at 5:19
  • \$\begingroup\$ What is A, B, C and so on? Some matrices? Which dimensions? Can it be easily implemented in C? \$\endgroup\$ – Vi. Jun 1 '15 at 11:16
  • 1
    \$\begingroup\$ Cracked, I believe. \$\endgroup\$ – Sp3000 Jun 2 '15 at 11:03
5
\$\begingroup\$

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);
}
\$\endgroup\$
  • 2
    \$\begingroup\$ I think the function declaration etc. counts towards the character count. \$\endgroup\$ – Ypnypn Jun 1 '15 at 4:12
  • \$\begingroup\$ @Ypnypn, counted characters in a golfed down function declaration. \$\endgroup\$ – Vi. Jun 1 '15 at 6:59
  • \$\begingroup\$ What is the output hash? I am assuming it is ((h<<64)|j). \$\endgroup\$ – tucuxi Jun 1 '15 at 15:20
  • \$\begingroup\$ Yes. Or just a pair of 64-bit numbers. I found out about __uint128_t only after implemeting this. \$\endgroup\$ – Vi. Jun 1 '15 at 16:41
  • 1
    \$\begingroup\$ @Dennis, Done.󠀠 \$\endgroup\$ – Vi. Jun 9 '15 at 16:52
4
\$\begingroup\$

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)))
\$\endgroup\$
  • \$\begingroup\$ Cracked? \$\endgroup\$ – Sp3000 May 31 '15 at 16:19
4
\$\begingroup\$

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 ------------------------------)
\$\endgroup\$
  • \$\begingroup\$ Cracked \$\endgroup\$ – feersum Jun 1 '15 at 16:36
4
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ How would it behave with 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa' and 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa'? \$\endgroup\$ – Ismael Miguel Jun 1 '15 at 20:36
  • 1
    \$\begingroup\$ foo| (d5c9bef71d4f5d1b) and foo\ (d5c9bef71d4f5d1b) produce VERY similar hashes. \$\endgroup\$ – Ismael Miguel Jun 1 '15 at 20:47
  • 1
    \$\begingroup\$ Broke it!!! \x00 and \x00\x00! \$\endgroup\$ – Ismael Miguel Jun 1 '15 at 21:10
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Sp3000 Jun 2 '15 at 12:14
  • 2
    \$\begingroup\$ Cracked: codegolf.stackexchange.com/a/51174/7773 \$\endgroup\$ – Vi. Jun 2 '15 at 14:48
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Cracked \$\endgroup\$ – Sp3000 May 31 '15 at 22:53
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ How should the input integer be converted to a string to use in your algorithm? \$\endgroup\$ – feersum Jun 1 '15 at 19:35
  • \$\begingroup\$ @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.) \$\endgroup\$ – tomsmeding Jun 1 '15 at 19:37
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – tucuxi Jun 2 '15 at 0:36
  • \$\begingroup\$ @tucuxi Already thought it shouldn't bee too hard; glad that is wasn't trivial but that someone broke it anyway. Good work. \$\endgroup\$ – tomsmeding Jun 2 '15 at 6:25
2
\$\begingroup\$

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;
}
\$\endgroup\$
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – tucuxi Jun 2 '15 at 16:57
  • \$\begingroup\$ Wrapper lacks header inclusions and in general leads to many equal hashes. \$\endgroup\$ – Vi. Jun 3 '15 at 12:06
  • \$\begingroup\$ Provide some hash samples. For me both "3" and "33" lead to 481c27f26cba06cf (using this wrapper). \$\endgroup\$ – Vi. Jun 3 '15 at 12:08
  • \$\begingroup\$ Cracked: codegolf.stackexchange.com/a/51215/41288 . I suspect right before @Vi. found out why so many hashes were equal. \$\endgroup\$ – tucuxi Jun 3 '15 at 12:13
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Vi. Jun 3 '15 at 12:24
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ How do I run this? Ideone refuses to compile it. \$\endgroup\$ – Martin Ender May 31 '15 at 20:27
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – SuperJedi224 May 31 '15 at 20:31
  • \$\begingroup\$ Cracked. \$\endgroup\$ – Martin Ender May 31 '15 at 20:38
  • 1
    \$\begingroup\$ @SuperJedi224 Why not remove the first public yourself, saving 7 chars? \$\endgroup\$ – user253751 Jun 1 '15 at 4:56
  • \$\begingroup\$ @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. \$\endgroup\$ – SuperJedi224 Jun 1 '15 at 10:10
2
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Cracked codegolf.stackexchange.com/a/51216/101 \$\endgroup\$ – aaaaaaaaaaaa Jun 3 '15 at 12:35
  • \$\begingroup\$ Didn't your example show a collision right there (the first two)? \$\endgroup\$ – mbomb007 Jun 5 '15 at 19:16
  • \$\begingroup\$ @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. \$\endgroup\$ – squeamish ossifrage Jun 5 '15 at 19:18
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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).

\$\endgroup\$
1
\$\begingroup\$

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);
}
\$\endgroup\$
1
\$\begingroup\$

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()
\$\endgroup\$
  • \$\begingroup\$ Cracked: codegolf.stackexchange.com/a/51180/36885 \$\endgroup\$ – mathmandan Jun 2 '15 at 19:38
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – mathmandan Jun 2 '15 at 19:40
  • \$\begingroup\$ 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 :/ \$\endgroup\$ – Puzzled Jun 2 '15 at 20:17
1
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Cracked. \$\endgroup\$ – jimmy23013 Jun 2 '15 at 22:42
  • \$\begingroup\$ Well done jimmy :) \$\endgroup\$ – Puzzled Jun 2 '15 at 23:22
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Could you please provide the wrapper the question requires? \$\endgroup\$ – Dennis Jun 3 '15 at 22:35
  • \$\begingroup\$ What's the input format? I tried with a number but it says comparison of String with 255 failed (ArgumentError). \$\endgroup\$ – jimmy23013 Jun 4 '15 at 4:02
  • \$\begingroup\$ H takes a string, Build string takes the number required by the OP and transforms it to a string. \$\endgroup\$ – MegaTom Jun 4 '15 at 4:06
  • \$\begingroup\$ I think you need a gets.to_i in the wrapper. \$\endgroup\$ – jimmy23013 Jun 4 '15 at 5:57
  • \$\begingroup\$ Cracked. \$\endgroup\$ – jimmy23013 Jun 4 '15 at 6:38
0
\$\begingroup\$

Mathematica, 89 bytes, cracked

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

Not the shortest.

\$\endgroup\$
  • 3
    \$\begingroup\$ 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." \$\endgroup\$ – Martin Ender May 31 '15 at 17:27
  • 2
    \$\begingroup\$ @MartinBüttner wolfram.com/mathematica/trial \$\endgroup\$ – LegionMammal978 May 31 '15 at 17:28
  • \$\begingroup\$ Cracked. \$\endgroup\$ – Martin Ender May 31 '15 at 17:34
0
\$\begingroup\$

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);"
\$\endgroup\$
  • 5
    \$\begingroup\$ The hash's output value looks floating-point. And It's the same for 3000000000000000000000000000000000000000000001 and 3000000000000000000000000000000000000000000000. \$\endgroup\$ – Vi. Jun 1 '15 at 16:47
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ It didn't use the order of blocks... Cracked. \$\endgroup\$ – jimmy23013 Jun 5 '15 at 9:39
  • \$\begingroup\$ Ugh. I give in :-( \$\endgroup\$ – squeamish ossifrage Jun 5 '15 at 10:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.