Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

The Challenge

I present to you another spy vs. spy challenge pitting obfuscators versus crackers. In this case, however, the datum to be protected is not an input but an output.

The rules of the challenge are simple. Write a routine with the following specifications:

  1. The routine may be written in any language but may not exceed 320 bytes.
  2. The routine must accept three 32-bit signed integers as inputs. It can take the form of a function that accepts 3 arguments, a function that accepts a single 3-element array, or a complete program that reads 3 integers from any standard input.
  3. The routine must output one signed 32-bit integer.
  4. Over all possible inputs, the routine must output between 2 and 1000 (inclusive) unique values. The number of unique values a routine can output is called its key.

As an example, the C program

int foo( int i1, int i2, int i3 ) {
    return 20 + (i1^i2^i3) %5;
}

has a key of 9, since it (hopefully) can only output the nine values 16,17,18,19,20,21,22,23, and 24.

Some additional limitations are as follows:

  1. The routine must be fully deterministic and time-invariant, returning identical outputs for identical inputs. The routine should make no call to pseudorandom number generators.
  2. The routine may not rely on "hidden variables" such as data in files, system variables, or esoteric language features. For example, routines should generally not refer to constants unless the constants are clearly defined in the code itself. Routines that rely on compiler quirks, outputs from mathematically undefined operations, arithmetic errors, etc. are also strongly discouraged. When in doubt, please ask.
  3. You (the coder) must know precisely how many unique outputs the routine can produce, and should be able to provide at least one input sequence that produces each output. (Since there can potentially be hundreds of unique outputs, this set would only ever be requested in the event your key is contested.)

Since this problem bares far less resemblance to classical encryption than the previous one, I expect it will be accessible to a broader audience.

The more creative, the better.

The Scoring

The shortest non-cracked submission(s) per byte 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 routines, 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.

Only one cracking attempt per submission per reader is permitted. For example, if I submit to user X: "your key is 20" and I'm wrong, user X will disclaim my guess as incorrect and I will no longer be able to submit additional guesses for that submission.

Cracked submissions are eliminated from contention (provided they are not "safe"). They should not be edited. If a reader wishes to submit a new routine, (s)he should do so in a separate answer.

A cracker's score is the number of submissions (either compliant or not) (s)he cracks. For crackers with identical counts, the ranking is determined by total byte count across all cracked submissions (the higher, the better).

The cracker(s) with the highest score(s) will be declared the winners along with the developers of the winning routines.

Please do not crack your own submission.

Best of luck. :)

Leaderboard

Last Updated Sept 2, 10:45 AM EST

Immovable Barriers (non-cracked submissions):

  1. CJam, 105 [Dennis]

Unstoppable Forces (crackers):

  1. Dennis [Java, 269; C, 58; Mathematica, 29]
  2. Martin Büttner [Java, 245]
share|improve this question
11  
May I suggest [cops-and-robbers] as the tag for these challenges? I think it's a fairly established name for such games in security and it will probably provoke more interest then [adversarial]. –  Martin Büttner Aug 31 at 9:01
    
Sure. I'll change it now. –  COTO Aug 31 at 9:02
    
What kind of output is acceptable? STDOUT, return, etc... –  Ypnypn Aug 31 at 21:01
2  
Your example is incorrect; its signature is 9. %5 can return anything from -4 to 4, inclusive. –  Keith Randall Sep 1 at 5:07
1  
@Dennis I would be fine with you trying again. It was my fault that it was messed up. –  Stretch Maniac Sep 1 at 22:25

7 Answers 7

up vote 7 down vote accepted

CJam, 105 bytes

1q~]4G#b2A#md"M-k^XM-WHM-n^GM-0%M-uwM-gM-^XeM-kM-^VO^Ph,M-^MM-^PM-qM-!M-8M-AM-OM-~tM-^FM-cM-h^AM-0M-0M-lM-@M-^[MF=M-^Z^SM-1M-KM-T2M-9M-UmSM-N
M-8M-^^M-n$4M-^M^SM-x M-OM-^@^?"256b@D#Y256#%2+md!A3#*)%)%

The above uses caret and M notation, since it contains unprintable character. After converting the byte stream into an integer (256b), the following code gets executed:

1q~]4G#b2A#md
12313030820310059479144347891900383683119627474072658988524821209446180284434934346766561958060381533656780340359503554566598728599799248566073353154035839
@D#Y256#%2+md!A3#*)%)%

You can try this version online in the CJam interpreter.

How it works

This submission uses number theory instead of obfuscation. The program will return 0 for almost all inputs. From the few inputs that result in a non-zero output, a secret modulus is derived that is applied to the 10 least significant bits of the third integer.

The most efficient way of solving this challenge (that I can think of) would be factorizing the 512 bit integer, which I hope won't be achievable in 72 hours.

" Prepend 1 to the numbers read from STDIN and convert the resulting array into an integer
  (“N”) by considering them digits of a base 2**32 number.                                 ";

1q~]4G#

" Compute “N / 1024” and “N % 1024”.                                                       ";

2A#md

" Push a carefully selected 512 bit semi-prime (“S”).                                      ";

12313030820310059479144347891900383683119627474072658988524821209446180284434934346766561958060381533656780340359503554566598728599799248566073353154035839

" Compute P = (N / 1024) ** 13 % 2 ** 256 + 2.                                             ";

@D#Y256#%2+

" Compute “S / P” and “S % P”.                                                             ";

md

" Compute “M = (S / P) % (1000 * !(S % P) + 1) + 1”.

  “M” is the key if P is a divisor of S; otherwise, “M == 1”.                              ";

!A3#*)%)

" Compute the final output: “N % 1024 % M”.                                                ";

%

Example run

$ base64 -d > outputs.cjam <<< MXF+XTRHI2IyQSNtZCLrGNdI7gewJfV355hl65ZPEGgsjZDxobjBz/50huPoAbCw7MCbTUY9mhOxy9QyudVtU84KuJ7uJDSNE/ggz4B/IjI1NmJARCNZMjU2IyUyK21kIUEzIyopJSkl
$ wc -c outputs.cjam
105 outputs.cjam
$ LANG=en_US cjam outputs.cjam < outputs.secret; echo
1
$ LANG=en_US cjam outputs.cjam <<< '1 2 3'; echo
0
share|improve this answer
    
You're just too darn good with the encryption stuff. ;) –  COTO Sep 1 at 6:54
8  
"This submission uses number theory instead of obfuscation." Looks at code "Hmm, right." –  ɐɔıʇǝɥʇuʎs Sep 1 at 16:34

Java - 269

Thanks for everyone's patience, this should now be fixed.

shortened:

int a(int a,int b,int c){double d=180-360.0/(int)(Math.abs(Math.sin(a*60))*50+2),e=180-360.0/(int)(Math.abs(Math.cos(b*60))*50+2),f=180-360.0/(int)(Math.atan2(c*60, a*60)*51+2);if(Math.abs(d+e+f-360)<.1)return Integer.valueOf((int)d+""+(int)e+""+(int)f);else return 1;}

Not shortened:

int a(int a, int b, int c) {
    double d = 180 - 360.0 / (int) (Math.abs(Math.sin(a * 60)) * 50 + 2);
    double e = 180 - 360.0 / (int) (Math.abs(Math.cos(b * 60)) * 50 + 2);
    double f = 180 - 360.0 / (int) (Math.atan2(c * 60, a * 60) * 51 + 2);
    if (Math.abs(d + e + f - 360) < .1)
        return Integer.valueOf((int) d + "" + (int) e + "" + (int) f);
    else
        return 1;
}
share|improve this answer
    
You can save four characters by changing double e,f,d=...;e=...;f=...; to double d=...,e=...,f=...; –  Ypnypn Sep 1 at 0:17
    
@Ypnypn Thanks! added to golfed version. –  Stretch Maniac Sep 1 at 0:28
1  
Second attempt (with explicit permission): 122 –  Dennis Sep 1 at 23:18
1  
@Dennis nice job! (That's it) –  Stretch Maniac Sep 1 at 23:46
1  
@Dennis In that case, you're forgetting 1 and your answer is incorrect as well ;) (123 being correct... someone come along and grab the cracking score...). And I guess Stretch Maniac didn't account for sin == 1.0 when he said that 122 is correct. –  Martin Büttner Sep 2 at 15:00

Java - 245

Cracked by Martin Büttner

int a(int[]_$){return $($($_(_$[0],0)))+$_(_$[1],1)*11+$($($_(_$[1+1],0)))*(1+1);}int $_(int $,int $_){int OO=0,o=1,O=1;for($=$<0?-$:$;++O*O<=$;OO+=$%O<1?O:0,o+=$%O<1?1:0,$/=$%O<1?O--:1);return $_>0?o:OO+$;}int $(int $){return(int)Math.sqrt($);}

Feed the input as an int array: a(new int[]{1,2,3}). I'm not expecting it to go 72 hours, but have fun with it.

Here it is with line breaks, to make it a bit more readable:

int a(int[]_$){return $($($_(_$[0],0)))+$_(_$[1],
1)*11+$($($_(_$[1+1],0)))*(1+1);}int $_(int $,int
$_){int OO=0,o=1,O=1;for($=$<0?-$:$;++O*O<=$;OO+=
$%O<1?O:0,o+=$%O<1?1:0,$/=$%O<1?O--:1);return $_>
0?o:OO+$;}int $(int $){return(int)Math.sqrt($);}
share|improve this answer
    
Just from bruteforcing... 90? –  bitpwner Sep 1 at 6:23
9  
Thank you so much for the "readable" version... –  Martin Büttner Sep 1 at 8:01
1  
I deobfuscated it a bit: pastebin.com/8pvvfFYB (I hope I didn't make any mistakes while replacing variable names.) –  Martin Büttner Sep 1 at 10:44
3  
Okay, here is my attempt: 965? –  Martin Büttner Sep 1 at 11:35
1  
@MartinBüttner Correct. Thanks for the obfuscated version :D –  Geobits Sep 1 at 15:18

A Sampler

Not an official entry of course, and the character count is too high, but I figure if anyone wants a mind-numbing challenge, they can try to determine how many unique outputs the following function produces (given three inputs as described in the OP):

function z(y,_,$){M=[];N=[];O=[];C=1792814437;P=72;r=t=0;(f=function(a,k,L){if(k<a.length){for(L=a[k],a[k]=0;a[k]<L;a[k]++)f(a,k+1)}else
if(!t){f([P-1,P-1],0,++t);N=M;while(t<2*P){s=!(t&1);f([P,P,P,P],0,++t);r=r||(s?0:t);t&1&&(N=O);O=[]}}else
((t<2)&&(((d=P*a[0]+(P+1)*a[1]+P)<(P<<6))&&(M[d]=(((y^~_)>>a[0])+((_^~$)>>(a[0]-32)))&1),((a[1]<P-a[0])&&
(M[a[1]+(P+1)*a[0]]=(($^C)>>a[0]+16-a[1])&1))||1))||((t&1)&&((O[P*a[2]+a[3]]|=M[a[1]+P*a[2]]&N[P*a[0]+a[3]]&&
!(a[0]-a[1]))||1))||(s|=N[(a[0]+1)*a[1]+a[3]]);})([],0,0);return r;}

In fact, I'm so confident that it's uncrackable, I'll award anyone who cracks it the "Supreme Unstoppable Force of Nature Award".

Because really, they deserve it.

share|improve this answer
1  
You should put up a bounty for it! –  Orby Sep 1 at 3:37
1  
@Orby That would be nice, but it's hard to award a bounty to a comment. –  Geobits Sep 1 at 4:29
    
    
@COTO is this challenge still on? –  Soham Chowdhury Sep 15 at 18:55
    
@SohamChowdhury: Absolutely. If you figure it out, I'll expound your victory in the OP. If not, let me know and I'll post the solution. –  COTO Sep 15 at 22:08

C, 58 bytes (Cracked)

A simple one:

f(a,b,c){return(long long)a*b*c-0x1d21344f8479d61dLL?0:a;}
share|improve this answer
2  
7 (-15485867, -1299721, -104287, 0, 104287, 1299721, 15485867). –  Dennis Sep 1 at 5:55
    
That was fast :) –  Orby Sep 1 at 5:56

Mathematica, 29 bytes, Key: 715, Cracked by Dennis

This is just a fixed version of my initial answer, which didn't work for non-positive inputs.

f=Plus@@Mod[NextPrime@#,240]&

Takes a list of integers like

f[{1,2,3}]
share|improve this answer
    
I found 349 unique outputs. The range was from 3 to 717. –  PhiNotPi Sep 1 at 11:57
    
@PhiNotPi Wrong. (I double-checked) –  Martin Büttner Sep 1 at 12:00
    
Well, I found my mistake and the right answer. Too late though. –  PhiNotPi Sep 1 at 12:25
1  
If the stuff I pieced together from the Mathematica documentation and WolframAlpha is correct, the key is 715 (3 ... 717). –  Dennis Sep 1 at 16:18
2  
Mathematica looks like a nice language, but it's either too darn expensive or I'm too darn cheap... –  Dennis Sep 1 at 16:23

207 characters, in C/C++, not yet obfuscated:

int x(int a, int b, int c) {
    int d, e, f;
    for (int i=0; i!=1<<31; ++i) {
        d=10*(b-a);
        e=a*(28-c)-b;
        f=a*b-2.7*c;
        a += d;
        b += e;
        c += f;
    }
    return ((a%5+5)*10+(b%5+5))*10+c%5+5;
}
share|improve this answer
    
Just trying my luck... 729. –  bitpwner Sep 1 at 8:14
    
@bitpwner Damn, I was just gonna say that. :D ... If that's wrong, that's the upper bound though. –  Martin Büttner Sep 1 at 8:15
2  
This is not a valid submission. All assignments inside the loop may result in signed integer overflow, which has undefined behavior. –  Dennis Sep 1 at 23:26

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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