34
7
This contest is over.
Due to the nature of cops-and-robbers 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
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>
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? – Martin Ender – 2015-05-31T14:51:54.157
@MartinBüttner: Yes, you'd have to take the result modulo 2^128. – Dennis – 2015-05-31T14:56:26.443
I may have been unclear with my first question. I mean if someone actually submits code that doesn't take the modulo, is that acceptable (and the robbers condition becomes "H(M) = H(N) (mod 2^128) and M ≠ N") or is it the cop's responsibility to ensure output is in range (which would mean submissions that don't ensure this are invalid). – Martin Ender – 2015-05-31T15:02:24.483
I understood, but I didn't express myself very well. The cop submission has to provide an integer in O, so you'd have to take the result modulo 2^128 in your code. – Dennis – 2015-05-31T15:04:15.293
Can I implement a function which takes in a string representing the argument in base 10 or 16, or am I required to accept it as a number argument if I use a function? – algorithmshark – 2015-05-31T16:57:50.330
@algorithmshark: String representations are fine. – Dennis – 2015-05-31T17:05:59.390
Is it cheating to just return I? – Scimonster – 2015-05-31T18:05:51.793
1@Scimonster Doesn't meet the requirements (up to 2^30 bits of input, 128 bits of output) – CodesInChaos – 2015-05-31T18:47:20.360
So you cannot compete with a language does not support 128 bit (even more 2^30 bit) integers? – flawr – 2015-05-31T21:04:36.657
@flawr: As stated in the question, you can represent I and O as arrays of integers, For O, you can choose 1 128-bit integer, 128 1-bit integers or anything in between. – Dennis – 2015-05-31T21:18:58.360
1Doesn't cops and robbers usually go the other way around? – haneefmubarak – 2015-06-01T01:02:12.513
Where is some Python2 answer I was trying to crack (about circular bitshift)? It suddenly disappeared. – Vi. – 2015-06-01T07:26:41.487
@Vi. I deleted it because it doesn't conform to the runtime requirements. In fact, I can't compete at all because the runtime requirements are way too strict. Both Pyth and Python are too slow for this challenge. Having to process 130 kilobytes byte-by-byte in less than a second in a slow language is just not possible. – orlp – 2015-06-01T08:24:22.997
@haneefmubarak This interpretation of cops and robbers is sort of my fault (because I wrote the first challenge assigning the roles this way round). I've first come across the phrase in internet-security capture-the-flag games, where the cops secure a machine (and the flag in the form of some secret) and the robbers break in to steal it. The metaphor I had in mind was along those lines. – Martin Ender – 2015-06-01T10:07:53.920
@orlp: Byte-by-byte being the key here. A block size of 16 bits should solve the speed problem. A block size of 128 bytes would even work with your exec statement. But I don't want the challenge to be too restrictive, so I've changed the speed rule. It only requires integers below
2^(2^19)
under one second now. – Dennis – 2015-06-01T13:57:46.750Surely if you want to win this, you should be writing in APL? en.wikipedia.org/wiki/APL_(programming_language) – Alexx Roche – 2015-06-02T18:47:22.230
2Perhaps 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. – aaaaaaaaaaaa – 2015-06-04T17:21:39.570
@eBusiness: I had that rule in the original draft, but since the crack has to work only on some computer, I edited out. The question now requires at least three test vectors. – Dennis – 2015-06-05T04:10:41.743
@Dennis Thank you for organizing this, it was great fun! (And a big time sink.) – aaaaaaaaaaaa – 2015-06-15T16:18:11.127