**Introduction**

It was a bloody rainy day in the mid of 2013, when my teacher went over the term “**Big O Notation**” during the data structure class, back then in LIU university in Lebanon. I didn’t know that I’d fancy use it in my career, and I haven’t had the guts to use it then.

**Big O Notation**

**Big O Notation** is used in data structure and computer science to describe the complexity of the a piece of code or an algorithm. Basically, it’s used for describing the worst-case of algorithms execution time. Through out this write-up, the Big O Notation will be referred as “O([complexity])”, as it’s usually used.

The Complexity, would vary from O(1) to O(n!), O(1) goes to the algorithm that executes on the spot which is always 1, e.g., declaring a variable, printing a string. O(n) goes to the algorithm that has a linear proportional growth to the size of input data type such as looping through an array. O(n^2) represents the directly proportional growth to the squared size of the input data type or for the nested iteration and so forth.

**Token Dissecting**

JWT is a JSON Object that is defined in RFC 7519 as a safe way to represent a set of information between client and server. The token is composed of a header, a payload, and a signature in a nutshell.

Few days ago, and during an exploitation phase of a blind MySQL injection, I’ve noticed that the exfiltration process of the JWT tokens is really slow since I wanted to exfiltrate multiple users JWT tokens. Hence, I started to work in a way to optimize this process.

It’s important to understand the structure of the JWT token or the data that you’re fetching before optimizing the exfiltration process, since a single character would costs thousands of requests times the SLEEP() time, could be bypassed or handled by a few lines of code, unless there is way to figure it out, e.g., content-length, header and so forth.

The header component contains information about how the JWT signature should be computed. The header is a JSON object in the following format: `{ "typ": "JWT", "alg": "HS256" }`

and the hashed data in base64 encoding would be “`eyJ0eXAiOiJKV1QiLCJhbGciOiJIUzI1NiJ9`

“. In this example, the value of the “typ” key specifies JWT object, while the value of the “alg” specifies which hashing algorithm is being used to create the JWT signature component. In this JWT, it’s HMAC-SHA256 algorithm.

There are 3,384 (number of chars x ascii chars range) requests required to exfiltrate the header `eyJ0eXAiOiJKV1QiLCJhbGciOiJIUzI1NiJ9`

and 14,570 requests for the entire **HS256** JWT token. However, this header is almost fixed and could be reduced to just two requests in order to identify which hashing algorithm is being used.

Among all JWT Header hashing algorithms, the first 11 characters are identical. The character at the index 11 specifies which hashing algorithm is being used, e.g., I for **HMAC**, S for **RSA** **PKCS**, F for **ECDSA** and Q for** RSA PSS.** And the character at the index 14 specifies the secret key bits, as shown in the figure below, the characters I,M,U are 256, 384, 512 respectively. Hence knowing what these characters are would save thousands of requests during the exfiltration process.

## O(n(m)) to O(n(log(m)))

While numbers and the alphabet are always the same, our JWT is not! Thus, I’ve came up with a way to create 3 sorted arrays, numbers, upper case characters and lower case ones, [0-9], [A-Z], [a-z] respectively. Instead of iterating throughout all ascii characters to get a single character now we could only iterate through a single array, which gives us a complexity of O(n). However, the “n” now is the size of a single input data type size (array in our example) instead of all the ascii characters.

In order to understand the gravity of O(log(n)) complexity, you need to have a look at the below binary tree figure. Binary Tree is just another data structure type, the complexity of the left tree is O(n) since if you want to search for the number 6, you have to iterate through all the numbers first. However, it’s O( log(n)) in the right tree, since we’re halving the size of the tree and the maximum steps needs to get the number 6 are 3.

## Blind MySQL Injection

Blind SQL injection is a type of SQL Injection attack that asks the database true or false questions and determines the answer based on the applications response as defined in OWASP page. I’ve wrote a trivial vulnerable script in PHP to demonstrate this kind of attack as shown in the figure below.

Since there is difference in the response content, then there is no need to use time-based blind injection attack, which will slow our exfiltration process for every fetched character. Hence, the ascii along with the substring MySQL function fit our criteria.

The above payload, will oblige us to iterate throughout all ascii characters -which is the traditional way to exfiltrate the JWT token also it’s complexity is the the length of the JWT token (n) times the length of the ascii characters (m), O(n(m)). Hence, in order to pick up a single character/pattern, I’ve used rlike along with Binary casting MySQL functions.

## Putting All the Pieces Together

The steps of this write-up is pretty straightforward. The complexity of of the optimized way is O(n(log(m)). While n is the size of the JWT token times the logarithmic (log (m))) of iterating through the matched tree only.

Whether attempting to exfiltrate JWT token or any other data format, the complicating factor is to minimize this process with the minimal number of requests. I believe that it’s not a new way to do so but it’s an optimized way I’ve used to accelerate the exfiltration process of the JWT tokens.

## Resources

- Exploit: https://github.com/Leoid/MySQL-Injection-Exfiltration-Optimization
- https://portswigger.net/web-security/sql-injection/blind
- https://en.wikipedia.org/wiki/Big_O_notation
- https://en.wikipedia.org/wiki/JSON_Web_Token
- https://www.geeksforgeeks.org/binary-tree-data-structure/
- https://www.w3resource.com/mysql/string-functions/mysql-rlike-function.php
- http://www.sqlinjection.net/time-based/

B1twis3 | Hamid Mahmoud