31
2
The Challenge
A simple "spy versus spy" challenge.
Write a program with the following specifications:
- The program may be written in any language but must not exceed 512 characters (as represented in a code block on this site).
- The program must accept 5 signed 32-bit integers as inputs. It can take the form of a function that accepts 5 arguments, a function that accepts a single 5-element array, or a complete program that reads 5 integers from any standard input.
- The program must output one signed 32-bit integer.
- The program must return 1 if and only if the five inputs, interpreted as a sequence, match a specific arithmetic sequence of the programmer's choosing, called the "key". The function must return 0 for all other inputs.
An arithmetic sequence has the property that each successive element of the sequence is equal to its predecessor plus some fixed constant a
.
For example, 25 30 35 40 45
is an arithmetic sequence since each element of the sequence is equal to its predecessor plus 5.
Likewise, 17 10 3 -4 -11
is an arithmetic sequence since each element is equal to its precessor plus -7.
The sequences 1 2 4 8 16
and 3 9 15 6 12
are not arithmetic sequences.
A key may be any arithmetic sequence of your choosing, with the sole restriction that sequences involving integer overflow are not permitted. That is, the sequence must be strictly increasing, strictly decreasing, or have all elements equal.
As an example, suppose you choose the key 98021 93880 89739 85598 81457
. Your program must return 1 if the inputs (in sequence) match these five numbers, and 0 otherwise.
Please note that the means of protecting the key should be of your own novel design. Also, probabilistic solutions that may return false positives with any nonzero probability are not permitted. In particular, please do not use any standard cryptographic hashes, including library functions for standard cryptographic hashes.
The Scoring
The shortest non-cracked submission(s) per character count will be declared the winner(s).
If there's any confusion, please feel free to ask or comment.
The Counter-Challenge
All readers, including those who have submitted their own programs, are encouraged to "crack" submissions. A submission is cracked when its key is posted in the associated comments section. If a submission persists for 72 hours without being modified or cracked, it is considered "safe" and any subsequent success in cracking it will be ignored for sake of the contest.
See "Disclaimer" below for details on the updated cracking score policy.
Cracked submissions are eliminated from contention (provided they are not "safe"). They should not be edited. If a reader wishes to submit a new program, (s)he should do so in a separate answer.
The cracker(s) with the highest score(s) will be declared the winners along with the developers of the winning programs.
Please do not crack your own submission.
Best of luck. :)
Leaderboard
Penultimate standings (pending safety of Dennis' CJam 49 submission).
Secure Lockers
- CJam 49, Dennis
- CJam 62, Dennis safe
- CJam 91, Dennis safe
- Python 156, Maarten Baert safe
- Perl 256, chilemagic safe
- Java 468, Geobits safe
Unstoppable Crackers
- Peter Taylor [Ruby 130, Java 342, Mathematica 146*, Mathematica 72*, CJam 37]
- Dennis [Pyth 13, Python 86*, Lua 105*, GolfScript 116, C 239*]
- Martin Büttner [Javascript 125, Python 128*, Ruby 175*, Ruby 249*]
- Tyilo [C 459, Javascript 958*]
- freddieknets [Mathematica 67*]
- Ilmari Karonen [Python27 182*]
- nitrous [C 212*]
*non-compliant submission
Disclaimer (Updated 11:15 PM EST, Aug 26)
With the scoring problems finally reaching critical mass (given two thirds of the cracked submissions are thus far non-compliant), I've ranked the top crackers in terms of number of submissions cracked (primary) and total number of characters in compliant cracked submissions (secondary).
As before, the exact submissions cracked, the length of the submissions, and their compliant/non-compliant status are all marked so that readers may infer their own rankings if they believe the new official rankings are unfair.
My apologies for amending the rules this late in the game.
6How are you going to verify that programs meet point 4? Do you expect people to edit their safe answers to add a proof? Are probabilistic submissions permitted on the basis of assuming that hash functions are ideal and the chance of a collision with another element of the 48-bit (according to your estimate above) space is negligible? – Peter Taylor – 2014-08-25T08:41:04.053
If a language does not have fine-grained control over its return value, if it OK, to exit with an error if the key is given, and not otherwise? – isaacg – 2014-08-25T09:20:52.710
Is Mathematica permitted? not everyone will be able to test it so it will have a big advantage over other languages. – rdans – 2014-08-25T10:27:16.497
I really think built-in cryptographic functions should be ruled out, as the only feasible solution is bruteforce, which is practically impossible. You will end up with several solutions in the form
return (hash(inputs) == myHashedKey)
, which are all 'unbreakable' as far as the scope of this competition runs. – stokastic – 2014-08-25T12:26:32.610@isaacg: I'm going to have to say "no" to allowing errors as output. The program/function should always terminate normally. However if a particular language doesn't have the ability to output integer 1 and 0 specifically, the program may output any two distinct values so long as they're documented along with the submission. – COTO – 2014-08-25T12:29:08.437
@stokastic: You're right. Ryan thought of the idea first, hence his entry can stay. I'll add the "no standard crypto hashes" rule to the OP. – COTO – 2014-08-25T12:30:59.013
@coto I don't mind my entry being disallowed. It will make the challenge more interesting i.e. i'm voluntarily withdrawing my submission. – rdans – 2014-08-25T12:47:11.570
@PeterTaylor: A proof would be nice, but we'll take it on good faith that each submission identifies one and only one input sequence. Probabilistic solutions that may return false positives with any nonzero probability are not permitted. – COTO – 2014-08-25T12:48:14.583
"Probabilistic solutions that may return false positives with any nonzero probability are not permitted" makes the problem a lot more interesting, since it effectively rules out both cryptographic hashes and the cheat I was going to do,
srand(input)
. – histocrat – 2014-08-25T14:19:30.020If you don't accept probabilistic methods, you don't have to rule out hashes. – Dennis – 2014-08-25T14:37:26.387
Are we allowed to use built-in random, provided the seed is available to the cracker? – stokastic – 2014-08-25T15:16:11.180
@stokastic: I would very much like to say "yes", but it opens up too many possibilities for abuse. For example, using the PRNG in $30K-a-license Exclusive Software X to hide constants where no one will ever find them. Hence the answer is "No". Using a PRNG to hide constants a clever idea, though, and you officially get credit for it. – COTO – 2014-08-25T15:34:21.870
2The scoring system seems to encourage crackers to ignore the shortest locks because they score better by cracking two long locks than two small ones. – Peter Taylor – 2014-08-25T17:37:23.823
@PeterTaylor: It was my thinking that (generally speaking) the longer a lock is, the more intractable the the problem of cracking it. I wanted the scoring system to reflect this in some way. I realize there are exceptions to the rule, and that there are other drawbacks. At this point it would be improper to amend the scoring rules. – COTO – 2014-08-25T17:44:30.750
3@COTO I think the problem is that you can only get 2 cracking scores, and only the shortest. So why not wait and hope and longer one shows up? For example, Martin now has no incentive to crack my (longer) lock, since he's already cracked two shorter ones. Anyone who cracks mine will now beat him without even having to do a second one. – Geobits – 2014-08-25T17:51:47.560
When should we post the answer if no-one has cracked it? After 72 hours after submission? Another deadline? – Tyilo – 2014-08-25T18:47:53.043
@Geobits: Actually, one of the reasons I put the rule in was to discourage a single reader from cracking all the entries, which I figured would discourage anyone else from attempting. When I post the day 1 leaderboard later this evening, Martin will get a special mention regardless of where he ranks according to official score. He's really going to town on people's entries. – COTO – 2014-08-25T18:48:07.787
@Tyilo: If you're still around after 72 hours, absolutely. The crackers will want to know how you stumped them. – COTO – 2014-08-25T18:49:04.017
1I think a better scoring system might be sum of total times between question and crack. That way, cracking a bunch of easy ones can be beaten, and the real reward comes from cracking the really hard ones. – isaacg – 2014-08-25T21:52:29.607
Neither the 128 byte nor the 175 byte submission I cracked were valid, so you shouldn't include them in the score, I think. – Martin Ender – 2014-08-26T07:45:55.263
1I'm new to golfing, so maybe it's a stupid question, sorry for that. Why is the code length measured in characters and not in bytes? The latter is literally the memory space that a program occupies, so for me it seems more logical. Eg. the CJam answer is the shortest in characters, but when looking at its size (326 because of unicode) it isn't even in the top 5. So I wonder, is it common convention in golfing to count chars instead of bytes? – freddieknets – 2014-08-26T13:30:12.343
@freddieknets: Honestly I don't know what the usual convention for bytes v. chars is. I'll stick with chars in this challenge, but if the convention is to count bytes, I'll use that in future. – COTO – 2014-08-26T13:48:15.333
@MartinBüttner: Will do. I'll update the leaderboard now. – COTO – 2014-08-26T13:50:02.030
@freddieknets, the default is bytes, as specified in the code-golf tag wiki, but some people prefer to count in characters.
– Peter Taylor – 2014-08-26T13:58:00.4901I think this contest would have been better without requiring a unique key. It's impossible to verify, probabilistic arguments require a long "hash" which takes up most of the characters, and additional keys only favor the cracker. – xnor – 2014-08-26T18:45:00.900
my version 1 is not valid as I know at least to keys for it, so @freddieknets should have a
*
. I can't disclose the key right now as it's the solution to my v2 script. – Tyilo – 2014-08-26T21:26:00.347@xnor: Probabilistic arguments are forbidden. That's what makes the challenge interesting (for me), as you cannot use a hash at all.
– Dennis – 2014-08-26T23:11:46.903@Dennis Thanks, I hadn't seen that ruling; that sadly disqualifies my solution. A bunch of answers fail uniqueness then, including some on the leaderboard. – xnor – 2014-08-26T23:35:45.380
@xnor: Yeah, that rule was a little buried. I've edited the question to make it more prominent. – Dennis – 2014-08-26T23:37:35.520
@COTO I feel like discrete logarithm and the RSA problem, which a lot of the answers use, should be disallowed for being "standard cryptographic hashes". – xnor – 2014-08-26T23:38:07.363
@xnor: RSA is asymmetric encryption, not hashing. As shown here, it can be used for message authentication codes, but it makes a terrible hash; anyone knowing the factorization of the modulus can easily reverse it. – Dennis – 2014-08-26T23:41:49.047
@COTO Then please change the wording "Please note that the means of protecting the key should be of your own novel design." Unless some of our golfers would like to reveal to be Professor Rivest, Professor Shamir, or Professor Adleman. – xnor – 2014-08-26T23:44:42.877
@Dennis That may be true for RSA, but discrete log is not known to have a trapdoor. What is then the distinction between one-way functions and hashes? – xnor – 2014-08-26T23:49:46.337
@xnor: There are different definitions of hash function. In crytography, one usually requires that you can't compute
H(M*X)
givesH(M)
andX
. With the discrete logarithm approach, that's perfectly possible, sinceG**(M+X)=G**M * G**X
andG**(M*X)=(G**M)**X
. – Dennis – 2014-08-27T00:20:22.3371@xnor: Truth be known, I added the "no cryptographic hashes" rule believing that RSA was an example of a cryptographic hash ("cryptographic hash" being a catch-all for "algorithm for generating a digital signature" in my ignorance). The goal was to rule out submissions relying on long-established algorithms that are (barring some world-changing advance in number theory) guaranteed to be unbreakable by anything other than brute force. The intent was to promote novelty. I unfortunately don't have the background to determine whether any given algorithm is a significant departure... – COTO – 2014-08-27T03:44:40.933
from an existing bulwark in the field of encryption, and thus "novel". – COTO – 2014-08-27T03:45:33.393