Solving Natas 15 using binary search
Solving Natas 15 requires brute forcing . But, there are some efficient ways to go about it.
Loading up the webpage, we’re shown a single input field in which we can enter a username along with a button labeled: “Check existence”. Entering “natas16” into the username field results in a page that returns “This user exists.” That’s promising.
Viewing the source code, we can see that the username input field feeds directly into a SQL query on the server. Looks like a good candidate for another SQL injection attack. We’re also shown that the database consists of a users table with two columns: username and password. So, perhaps we can somehow extract natas16’s password by injecting some SQL into the username field.
The complication is that while we can input arbitrary SQL into the username field, we can’t directly observe the result. We can get only two responses: A page that returns “This user exists” or a page that returns “This user does not exist” . Essentially, we have an oracle that will tell us if a username / password combination does or does not exist in the database. If, for example, we enter in the username field the following:
natas16" AND password = “p@ssw0rd
We’ll get back a page that says “This user exists” if natas16’s password is, in fact, “p@ssw0rd”.
How do we go from that knowledge to natas16’s actual password? By brute forcing it one character at a time using some basic SQL commands.
Here’s a python script I wrote to automate the process :
In a nutshell, this script re-constructs natas16’s password one character at a time using a binary search over all ascii letters and digits.
We know previous level passwords (Natas 1–14) were all 32 characters long and were composed of lowercase ascii letters, uppercase ascii letters and digits. So, we create a string, charset, that encapsulates all of those characters and sort them. Then, for each character of natas16's 32 character password, we use SQL’s STRCMP and SUBSTRING commands to run a binary search over charset to find a match (which runs in O(log(n)) as opposed to O(n) ).
There were two awkward / painful parts to this process. The first was getting STRCMP to work as intended — its default behavior is to compare two strings in a case insensitive manner, which is not helpful when running a binary search over lowercase and uppercase characters. To allow for case sensitivity in the comparison, it is necessary to use the BINARY operator on one of the strings in the comparison.
The second was figuring out the right termination condition for the binary search. As I could not directly access the result of STRCMP in the SQL query, I had to let binary search run through a full pass of the search space even if it found the right character earlier. Assuming the correct character is, indeed, in our search space, then after a full pass of binary search, the index to the correct character will be stored in the lowIndex variable in the script above. If that doesn’t make sense to you, I wouldn’t worry about it.
Anyway, running the script above should, within a minute, produce the password for natas16:
…(many other characters)
 Natas is a wargame meant to teach people about and how to exploit web security vulnerabilities. After solving a level, I usually look up other solutions to compare strategies. I haven’t written any solutions to levels 1–14 of Natas because there are already great write ups for those levels. But, I thought I’d share my solution to Natas 15 because I haven’t come across a full solution for using binary search.
 Technically, there is a third possibility: a page that returns a SQL error in case you entered a malformed query.
 I don’t speak fluent Python, so there may be more perfomant and terse ways of writing this script. But, I’m trying to up my Python game in my spare time because of its wide use in data science and machine learning applications.
 To be totally honest, this optimization doesn’t really matter with such a small search space. So…maybe the whole premise of this post is misleading.