PlaidCTF 2014 - halphow2js writeup

This task was for 200 points, and it took us quite a lot of time to figure out. We still managed to get the breakthrough bonus on it, so I guess we were not alone with this.

The task description

When we visit the site, we are greeted with some ugly JS and a bunch of prompts. Chrome dies a miserable death once we enter the fifth number, and some processing starts. 

Let's look at the source. I mirrored it here: https://gist.github.com/balidani/b29dc38658efca998f5b

function client_side() {
 var x,y,z,w,ww;
 while(1) {
  x = prompt("#1",'1'); if(!x) return;
  y = prompt("#2",'2'); if(!y) return;
  z = prompt("#3",'3'); if(!z) return;
  w = prompt("#YOLO",'420'); if(!w) return;
  ww = prompt("#PPP",'123'); if(!ww) return;
  
  // The best solutions run FAST!
  // So, skip the slow self test if you've got a solution
  if(filter(x,y,z,w,ww) == FLAG) break;
  
  if(!self_test()) {
   alert("Sanity check failed! ...");
   return;
  }
  alert("Pick better numbers, man.");
 }
 call_server(x,y,z,w,ww, function(x) { alert(x); });
}

So if filter returns the flag, we are good. Otherwise, we start running the self_test, which calls the mystop function and takes forever to complete. Our next step (and mistake) was trying to figure out why mystop is slow and optimize it. I think this is a very common mistake I make - forgetting what category a task is and trying stupid things. Let's say that mystop is complicated and move on. I wasted an hour here.

Our next idea was to find all the 1000 values, except those that take forever to compute. We did this with a little script using Worker threads. We ended up with ~750 values. Needless to say, this was unnecessary work, but hey, it was 4AM. Let's (finally) look at the filter function that validates the key.

function filter() {
 var args = [].slice.apply(arguments).sort().filter(function(x,i,a){return a.indexOf(x) == i;});
 if(args.length != 5) return "uniq";
 
 var flag = false; args.map(function(x){flag |= x >= 999;});
 if(flag) return "big";
 
 var m = args.map(mystop);
 
 if(m.filter(function(x,i){return m[2]+3*i == x;}).length < 3) return "unsexy";
 if(m.filter(function(x,i){return x == args[i];}).length < 3) return "hippopotamus";
 if(m.filter(function(x,i){return x > m[i-1];}).length > 3) return "banana phone";
 
 return FLAG;
}

Oh, look, there are some checks that exclude a lot of values.

• The keys have to be unique and under 1000
• For each number in the key, mystop is called (array m)
• At least 3 items have to follow the formula: m[2] + 3*i == x
• At least 3 items have to be equal to the key itself
• The keys cannot be in increasing order

Edit: that last part is a lie, they are sorted by the filter function first. Thanks to @mathias for the clarification, here is his write-up too.

The strongest limitation seems to be number 4, since we hadn't seen many numbers that would map to themselves, only 6 and 1. So how can we have 3? This is were it starts becoming a web task. Look closely at the filter. It uses ==, which is vulnerable, since it doesn't check type. Bingo. One tiny problem is that the values we pass to filter will all be strings, since prompt returns a string. All we have to play with is parsing now. During testing, I found the following weird issue with mystop:

> mystop("2")
1
> mystop("2e0")
2
> mystop("2e00")
2

So this is how we can make a value map to itself, though this only seems to work for 2. The rest is easy, we can arrange our (mystop mapped) values like this:

2, 2, 2, 11, 14

Then the formula we need to satisfy will apply for 3 elements (0, 3, 4). All we needed now was to find 2 numbers that map to 11 and 14. Final payload:

["2e0", "2e00", "2e000", "497", "944"]

The flag