Welcome again challenger!!

Our Young Mario was dreaming about Xors when he was struck with a question. Help him solve his question.

139.59.28.4:1352

Let’s connect to the server and see what’s going on.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
$ nc 139.59.28.4 1352 Question: Given x , we need to find the numbers less than x such that (p xor x) > x where 1<=p<x Constrict time as much as possible as the solution given here takes (t * log n) time , where t is the number of test cases. Input Format: Line 1 : No of test cases (t) Next t lines are the values of x Output Format: Single line stating the count of numbers where than p xor x > x 12587 91427 |

So, we need to find the total numbers of p such that (p xor x) > x where 1 <= p < x for all test cases. Also, there is a time limit which means that we need to be fast. Therefore, we need a good algorithm to calculate the result.

Let x be 11011010. We can find a number 111XXXXX where X’s can be either 0 or 1 and for all of them are greater than x. There exists 2^5=32 numbers for this scenerio. We can also find a numbers such that 110111XX and we have 2^2=4 numbers that are again greater than original x.

What I’m doing here is to find a bit whose value is 0 and change it to 1. Then, all the bits rightside of it can either be 1 or 0 and we can get these numbers with XOR operation.

Here is my script to solve the challenge.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
#!/usr/bin/env python from pwn import * r = remote('139.59.28.4', 1352) r.recvlines(13) t = int(r.recvline()) for i in xrange(t): print 'testcase {}/{}'.format(i + 1, t) x = int(r.recvline()) k = 0 count = 0 while x > 0: if x & 1 == 0: count += 2 ** k k += 1 x >>= 1 r.sendline(str(count)) print r.recvline() |

Notice that the number of testcases are random. So, we will try a few times until we get lucky and small amount of tests.

Let’s execute the script.

1 2 3 4 5 6 7 8 9 10 11 12 |
$ python solve.py [+] Opening connection to 139.59.28.4 on port 1352: Done testcase 1/1692 testcase 2/1692 testcase 3/1692 testcase 4/1692 . . . testcase 1691/1692 testcase 1692/1692 Success, the flag is xiomara{link_lists_are_cool_btw} |

We got the flag xiomara{link_lists_are_cool_btw}.