[RogueCoder]

In this tutorial I will show how you can utilize binary search algorithm when hacking. It's not a very long tutorial, but it is an extremely helpful method to use when hacking.

What is the binary search algorithm?

In computer science, a binary search or half-interval search algorithm finds the position of a specified value (the input "key") within a sorted array. In each step, the algorithm compares the input key value with the key value of the middle element of the array. If the keys match, then a matching element has been found so its index, or position, is returned. Otherwise, if the sought key is less than the middle element's key, then the algorithm repeats its action on the sub-array to the left of the middle element or, if the input key is greater, on the sub-array to the right. If the remaining array to be searched is reduced to zero, then the key cannot be found in the array and a special "Not found" indication is returned.

Source: http://en.wikipedia.org/wiki/Binary_search_algorithm

How to utilize it?

I will be using a fictional SQL injection attack to explain this, so let's imagine we have found a vulnerable website http://www.domain.com/product.php?id=5. The id parameter is vulnerable to union injection and we're going to use order by to find out how many columns it has.

One method would be to start at 1 and count up, but this isn't very efficient if we're working with a lot of columns. This is when we utilize the binary search algorithm.

We start with a high number, in this case 100. If 100 fails we have determined that the correct number will be somewhere between 1 and 100

We will most likely now see an error like Unknown column '100' in 'order clause'

Code:

http://www.domain.com/product.php?id=5 order by 100

Next we try 50. If we get the same error we now know it's also less than 50.

Code:

http://www.domain.com/product.php?id=5 order by 50

Then we try with 25. Again we get the same error. So it's between 1 and 25 as well.

Code:

http://www.domain.com/product.php?id=5 order by 25

We then try with 12, and the error is gone. No errors means that we are not exceeding the total column count. So now we know that it is equal to or higher than 12 and less than 25

Code:

http://www.domain.com/product.php?id=5 order by 12

Since 12 is successful we reverse a little bit and we try 15. If this causes the error to return, the number is between 12 and 15

Code:

http://www.domain.com/product.php?id=5 order by 15

When you are this close you can increase or decrease by one to find the answer

This might look difficult, but when you get the hang of it you will notice that this approach is far more efficient than increase or decrease by one.

Final words

I hope you found this tutorial helpful, and as always, if you have any comments or questions don't hesitate to reply. I will try to answer the best I can.

[Psycho_Coder]

I won't tell that this is exactly an application of binary search as this is a kind of manual testing, also binary searches for an element in both the sides of the middle element or index of a range but here it is just being tested with lower values. I would say that this a bit of manual testing that saves time. In short optimized hacking.

EDIT: The thread title is also misleading it will appear to the user that he will get some thing related to binary search that is codes explanation and algorithmic analysis but he will find something which is completely different. I request you to change the thread title to something else like Application of Binary search in SQLi

Thank you,
Sincerely,
Psycho_Coder

[RogueCoder]

Thanks for your comments :-)

the idea behind the post was to utilize the idea behind the algo used by the binary search.

regarding the title you are absolutely right. i will change it when i get home.

[Deque]

The only thing missing is a source code that does exactly what you did manually.

[Psycho_Coder]

The only thing missing is a source code that does exactly what you did manually.

Here it is :-

Code:

private static int binarySearch(int[] arr, int ele) { int start, end, mid; start = 0; end = arr.length - 1; while (start <= end) { mid = (start + end) / 2; if (arr[mid] == ele) { return mid; } else if (arr[mid] < ele) { start = mid + 1; } else { end = mid - 1; } } return -1; }

[RogueCoder]

Thanks for editing the title while I was away @Snipa

[RogueCoder]

I'll share some code as well then

PHP

Code:

<?php function binarySearch(array $haystack = array(), $needle) { $low = 0; $high = (sizeof($haystack) - 1); echo "{$low} - {$high}<br />\n"; while ($low <= $high) { $mid = (($low + $high) >> 1); if ($haystack[$mid] == $needle) { return $haystack[$mid]; } elseif ($haystack[$mid] > $needle) { $high = $mid-1; echo "{$low} - {$high}<br />\n"; } elseif ($haystack[$mid] < $needle) { $low = $mid+1; echo "{$low} - {$high}<br />\n"; } } return false; }

Python

Code:

def binarySearch(haystack, needle): low = 0 high = (len(haystack) - 1) while (low <= high): mid = ((low + high) >> 1) if (haystack[mid] == needle): return haystack[mid] elif (haystack[mid] > needle): high = mid-1 elif (haystack[mid] < needle): low = mid+1 return False

[Psycho_Coder]

I think in the title must end with sqli

[Deque]

The only thing missing is a source code that does exactly what you did manually.

Here it is :-

Code:

private static int binarySearch(int[] arr, int ele) { int start, end, mid; start = 0; end = arr.length - 1; while (start <= end) { mid = (start + end) / 2; if (arr[mid] == ele) { return mid; } else if (arr[mid] < ele) { start = mid + 1; } else { end = mid - 1; } } return -1; }

It doesn't help with SQLi, does it?

[RogueCoder]

I think the entire thread was misunderstood

The idea was to show how the binary search algorithm worked and how the method could be utilized in hacking scenarios where you're blindly looking for a specific value. I only used the SQL injection approach to show how to apply this.
This approach can be used in many other scenarios than just the one shown here.