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 at LIU university in Lebanon. I didn’t know that I’d 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 piece of code or an algorithm. It’s used for expressing the worst-case of algorithms execution time. Throughout this write-up, the Big O Notation will be referred to 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.

The exfiltration process of the JWT tokens is prolonged since I wanted to exfiltrate multiple users JWT tokens. Hence, I started to work in a way to optimize this process.

It’s essential 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 JWT 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 an 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 we could reduce it to just two requests to identify which hashing algorithm is used by the application.

Among all JWT Header hashing algorithms, the first 11 characters are identical. The character at index 11 specifies which hashing algorithm the application is using, 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.

Mapping JWT header hashing algorithms.
Two arrays for identifying the hashing algorithm of the JWT token.

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

While numbers and the alphabet are always the same, our JWT is not! Thus, I’ve come up with a way to create three 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.

Creating Tree for every Data Set.
Tree Creation Function.

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 need to get the number 6 is 3.

Non Balanced Tree vs Balanced Binary Tree
Find out which tree matches the pattern to iterate only through it.
Fetch a Character Function.

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 response of the application as defined in the OWASP page. I’ve written a trivial vulnerable script in PHP to demonstrate this kind of attack, as shown in the figure below.

The “pid” GET parameter is vulnerable to Blind SQL Injection.

Since there is a difference in the response content, then there is no need to use a 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.

Blind MySQL Injection Payload.

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 length of the JWT token (n) times the length of the ASCII characters (m), O(n(m)). Hence, to pick up a single character/pattern, I’ve used rlike along with Binary casting MySQL functions.

Using rlike & Binary Casting MySQL functions.
In case of Time-Based Blind Injection.

Putting All the Pieces Together

The steps of this write-up are pretty straightforward. The complexity 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.

Exfiltrating Steps.
Traditional Exfiltration Way vs The Optimized One.


B1twis3 | Hamid Mahmoud