Doing it the hard way...

The other week I took a moment to play Gh0st Network CTF at RVASec 2017. I decided to write about solving that problem the hard way. The problem was as follows:

da Vinci Crypto, LLC 400
There is a hi-tech cryptex at the organizer's table that might have some valuable information, but we do not know the pin to open it. The manufacturer provided us with a page that simulates (https://metactf.com/metactf2017/cryptex.html) the lock by generating random pins, and it checks whether or not the code is correct. Their simulator has more rings than ours, but they said that the pin to the cryptex we have is the first 5 digits of the cryptex on the webpage. Can you reverse engineer the page and unlock the cryptex? (To make sure that everyone gets a chance, you may not spend more than a minute with the lock if there are people waiting for it.)

The solution:

The long story short, looking at the code there's a function validate_lock() that takes a number and checks for quite a few constraints...

Having a limited time and only a laptop with me (no fancy GPUs), I wrote a  for-loop in JS to solve the combination for the lock. I figured that I should start from the end of the key space, and reducing the search space as much as possible, trying to skip unnecessary computations. Here's a glorified for-loop in JavaScript.

for(n=999999999999;n>=109+59;n--){
    if (n%109==59){
        if (n%83==70){
            if (n%71==45){
                if (n%59==15) {
                    if (n%41==14) {
                        if (n%13==6) {
                            if (n%11==1) {
                                if (n%7==4) {
                                    document.write("hit:" +n + "<br>\n");
                                    break;
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

After running it for a bit, it came back with the solution...


791459570661


P.S. The solution for the real cryptex is right on the picture... look at the very bottom... 79145...