synawk

Firstly, we will set up the testing environment. I have created a basic JSON-based API that stores information about products and users. I want to emphasize that, for the purpose of this discussion, I will solely concentrate on reducing the number of requests. It’s important to acknowledge that there are other considerations to take into account. By minimizing the number of requests, we can potentially enhance the efficiency of retrieving information, leading to faster results.

Nowadays, performing an SQL injection attack is quite easy. The only thing you need is knowledge of SQL and, in some cases, familiarity with the programming language used by the target application or you can use any open-source tool available. Many applications released today have built-in protections against SQL injections. Frameworks like Spring, Laravel, Django, and RoR already include measures to prevent these types of attacks. So it’s safe to say that finding and exploiting SQL injections has become more difficult nowadays. However, that doesn’t imply that SQL injections cannot be found. The reason is that some developers fail to utilize the framework properly, which introduces vulnerabilities in the code. Let’s see how it works.

In the provided example, there is a simple Flask application (too simple actually xd) that serves a JSON. This API receives two parameters: the id (which represents the vulnerable parameter) and the type that specifies the nature of the request being made. The resulting JSON contains two properties: result, a boolean value that checks for the existence of rows, and a basic timestamp.

As you can see, there is a vulnerability in the query. The payload parameter stores the product ID, but a malicious actor could potentially send a SQL injection attack. I will outline three different ways to exploit the vulnerability and retrieve the table names. The objective is to minimize the number of requests made. Also I added a simple counter table to register the number of requests executed. The complete schema is:

Tables
+----------------------+
| admin_posts          |
| admin_usermeta       |
| admin_users          |
| articles             |
| blog                 |
| cm_production        |
| products             |
| sqlite_sequence      |
| store                |
| store_order_itemmeta |
| store_order_items    |
| store_orders         |
| store_products       |
| tb_counter           |
| tb_dataset           |
| tb_users_company     |
| users                |
| wp_comments          |
| wp_posts             |
| wp_term_taxonomy     |
| wp_terms             |
| wp_url               |
| wp_usermeta          |
| wp_users             |
+----------------------+
220 letters

binary search

The first method I’m going to try is a simple binary search. Binary search is an algorithm with a time complexity of O(log n), and it aims to find an element by repeatedly dividing the search space in half and determining if the element is greater or less than the middle element in that portion

I follow the previous steps for each tablename. However, before proceeding, I should first calculate the length of the tablename. This is necessary to determine how many binary searches I have to perform efficiently. Knowing the length allows me to set the search boundaries appropriately and avoid unnecessary iterations.

The algorithm takes 1|/product-exists|``2028 steps to extract 220 letters (all the tables) which is a high number compared with the count of letters in the strings.

sqlmap

Now, lets take a look to sqlmap. SQLmap is an automated tool that generates payloads to exploit SQL injection vulnerabilities. It can be customized and scaled for more sophisticated attacks, but for this demonstration, I will use a basic approach.

sqlmap -u http://192.168.0.14:7001/product-exists --data '{"id":1, "type":1}' --random-agent --tables

Running the previous command and waiting a few seconds, the tool will generate a couple of successful payloads. These payloads include Boolean-based and time-based attacks. However, it’s important to note that these attacks can be more complex because the response only shows a Boolean result and a timestamp. Therefore, it may be challenging to directly retrieve any information on the screen.

Parameter: JSON id ((custom) POST)
    Type: boolean-based blind
    Title: AND boolean-based blind - WHERE or HAVING clause
    Payload: {"id":"1) AND 4123=4123 AND (2488=2488", "type":1}

    Type: time-based blind
    Title: SQLite > 2.0 AND time-based blind (heavy query)
    Payload: {"id":"1) AND 6134=LIKE(CHAR(65,66,67,68,69,70,71),UPPER(HEX(RANDOMBLOB(500000000/2)))) AND (7886=7886", "type":1}

So, the only way to extract information is by checking each character until we build a complete dataset. There are several ways to perform this; one of them is by checking all possible values for each character and based on the Boolean response. However, that will take a considerable amount of time, especially considering that table names could be long. Essentially, the number of attempts required would be max_chars^size_word, which is a significant amount of time.

In this case, sqlmap will be able to check for existing SQL injection and extract the table names in 2|/product-exists|``1496 requests. Although there are potential improvements I can make to increase the efficiency using sqlmap, the default method requires this number of requests to extract the table names. The tool utilizes a binary search technique, which operates with a time complexity of O(logn). Big-O notation provides insights into the algorithm’s performance, but it’s important to note that other factors and the context can influence it.

The payload for the SQL injection attack is as follows:

1) AND SUBSTR((SELECT COALESCE(tbl_name,CHAR(32)) FROM sqlite_master WHERE type=CHAR(116,97,98,108,101) LIMIT 2,1),3,1)>CHAR(96) AND (5327=5327

The query now reads the column tbl_name from sqlite_master, comparing the type with CHAR(116,97,98,108,101), which corresponds to the ASCII value for the word ‘table’. The LIMIT 2, 1 indicates an attempt to retrieve the second table. However, the intriguing part lies in CHAR(96), where it compares whether the retrieved value (substr 3, 1) is greater than CHAR(96). Internally, sqlmap implements a binary search by using the result of the query as the new mid value.

Lets see if we can minimize the number of requests.

binary_search + probability approach + optimization

But I am not satisfied with the result; there should be another way to further minimize the number of requests. While contemplating alternative approaches to reduce the requests, I came up with a solution that utilizes probability. It’s important to reiterate that this exercise aims to enhance coding skills and highlight the significance of understanding code, regardless of whether the solution itself is applicable in the real world.

Lets see how it works:

Let’s consider a word-guessing scenario with the word “armageddon.” Initially, you start by randomly selecting letters since you have no idea what the word might be. However, once you discover the letter “a,” you gain some valuable information. It’s common for any letter to follow after the letter “a,” but consonants are more likely, right? Let’s say you’re fortunate enough to guess “r” correctly. Now you have “ar,” which provides additional context. With this context in mind, you can create a prioritized list to make educated guesses based on the previous letters. This technique is similar to autocomplete, where you predict the next letter based on the preceding letters. However, it’s worth noting that this approach is most effective when the table names are not overly complex.

To build this efficient data structure, I opted for a Trie, which stands for “Retrieval.” A Trie is a specialized tree-like data structure that excels at storing and efficiently retrieving a large set of strings. It’s particularly useful for scenarios like autocomplete suggestions, word dictionaries, and handling prefix-based searches.

The Trie structure is organized with nodes, where each node represents a single character in the strings being stored. These nodes are interconnected, forming a tree-like hierarchy. The root of the Trie represents an empty string, and from there, each edge leading to a child node corresponds to a character in the strings. As you traverse down the Trie from the root to a specific node, you effectively build a string.

class TrieNode:
    def __init__(self, frequency):
        self.frequency = frequency
        self.children = {}
        self.is_end_of_word = False

    def __repr__(self) -> str:
        arr = []
        for key, val in self.children.items():
            arr.append(f"({key}: {val.frequency})")
        return "".join(arr)

As you can see, I store both the frequency and the children (next letters) for each node in the Trie. Now, I will create the Trie class that will allow me to inject new words and perform various operations.

class Trie:
    def __init__(self):
        self.root = TrieNode(0)

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode(frequency=0)
            node = node.children[char]
            node.frequency += 1
        node.is_end_of_word = True

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end_of_word
    
    def _softmax(self, arr):
        total = sum([val.frequency for _, val in arr])
        softmax = [(val, val.frequency / total, key) for key, val in arr]
        return softmax

    def bfs_search(self, partial, chars=5):
        if len(partial) > 8:
            partial = partial.split("_")[-1]
        current_node = self.root
        for char in partial[-8:]:
            if char not in current_node.children:
                return []
            current_node = current_node.children[char]
        queue = [current_node]
        prediction = []
        prob = 0
        level = 0
        while queue:
            if level == chars:
                break
            node = queue.pop(0)
            #get softmax from children
            softmax = self._softmax(node.children.items()) 
            #sort by probability
            softmax.sort(key=lambda x: x[1], reverse=True)
            top_value = softmax[:1]
            if len(top_value) == 0:
                break
            if top_value[0][1] < 0.657:
                break
            prob += top_value[0][1]
            let_node = top_value[0][0]
            #if let_node.is_end_of_word:
            #    break
            prediction.append(top_value[0][2])
            level += 1
            queue.append(let_node)
        return ("".join(prediction), prob/(1 if level == 0 else level))

For all the children, I apply a softmax function to standardize the weights. For example, let’s say I have this partial string: wp_u, and the Trie is something like this:

Having wp_u tell us that the next letter only could be s or n, so how the algorithm knows what is the best choice? Based on probability. Remember that i built the Trie based in a list of common tables, so based on the ferequency i will have weights. For instance

given: wp_u

next letter: s (frequency: 100)
next letter: n (frequency: 88)

So, after applying softmax to standardize the weights, I will have [0.5319, 0.4680]. This tells us that there is not too much difference between both numbers. Therefore, if the algorithm is not sure about the probability, it will discard it. On the other hand, if I have something like

given: wp_u

next letter: s (frequency: 120)
next letter: n (frequency: 11)

I will have [0.91603, 0.08396]. The algorithm will know that the next letter is the letter s based on frequency probability.

After running this code, the number of requests is significantly reduced, resulting in a final count of 1|/product-exists|967 steps to extract 220 letters.

Conclusion

The final results show that using the Trie data structure, I was able to significantly reduce the number of requests. This improvement was particularly noticeable when dealing with less complex and predictable strings.

By efficiently organizing the data and leveraging the Trie’s prefix-matching capabilities, the algorithm achieved better performance and minimized unnecessary requests. This optimization is particularly valuable in scenarios where the string patterns are relatively simple and follow predictable patterns.

With this exercise, I aim to demonstrate the significant impact that proficient coding skills can have on tasks like this. Understanding the code and employing efficient data structures, such as the Trie in this case, can lead to remarkable improvements in performance and resource utilization.

Although in this specific example, minimizing the number of requests may not have a real-world impact, it serves as a valuable illustration of how coding can optimize processes and algorithms. It highlights the importance of not only having a functional solution but also striving for efficiency and elegance in code design.

In real-world scenarios, the impact of efficient coding becomes even more apparent. Tasks that involve large datasets, complex operations, or real-time processing can be revolutionized by well-optimized algorithms. Performance gains can lead to cost savings, reduced energy consumption, and improved user experiences.

Moreover, proficient coding skills enable developers to identify and rectify potential bottlenecks and inefficiencies. It empowers them to design scalable and maintainable solutions that can adapt to changing requirements and growing datasets.

Overall, this exercise serves as a reminder that investing time and effort into mastering coding skills can be incredibly rewarding. As a developer, the more you know about code, data structures, and algorithmic principles, the more capable you become in crafting elegant and high-performing solutions to real-world challenges. Continuous learning and practice in coding will undoubtedly unlock new possibilities and elevate the quality and efficiency of your work.