Let’s start with another challenge from pwnable.kr called coin1.
Firstly let’s connect to this service using nc.
So we get a set of coins, with only one counterfeit one that weights 9, rest of them weight 10 each. As we have limited tries and limited time to find 100 counterfeit coins, we have to find a quick algorithm that will do it for us.
What helped me find out the solution was illustrating the problem on a piece of paper.
Let’s sum up the weight of first half of these 10 coins.
Here we see that the sum is not divisable by 10, so that means that 9 in somewhere in this half. Let’s repeat this operation once more, but after dividing this half.
This set’s weight is equal to 30, so the counterfeit must be in the other part.
This time weight is equal to 19, so one of these 2 coins is counterfeit. If we choose to weight the first one, we’ll know that it’s real, and the counterfeit is the other coin.
Easy, right? That’s binary searching and now we’re ready to implement it in Python. I’ll be using pwntools library which makes communication with servers much easier.
If you don’t understand this code, follow my lead. Firstly we will set the connection variable, to the address 0, as we’ll run this code inside one of the pwnable.kr servers - response time will be much faster.
After that we’re ready to get the bytes from the introduction with conn.recv(10024). We will not need it on our challenge. After that, the loop will will iterate for each of the coin sets that we’re assigned to check.
Next lines will decode the line, get the values of n and c, with left and right variables that will be helpful for the binary search.
After that there’s a loop that will iterate for the number of tries we have. In each iteration we’re doing our binary search procedure - weight the first half of coins, if the weight is divisable by 10, then try the other half. If not, then cut in half the part that we’ve been using. Easy, right?