Didier Stevens

Tuesday 2 February 2010

Quickpost: Quasi-Tautologies & SQL-Injection

Filed under: Hacking,Quickpost — Didier Stevens @ 9:54

Last OWASP/ISSA Belgian chapter meeting was the location of an interesting discussion. For a full report of the meeting, read Xavier’s excellent blogpost.

Many SQL-injection techniques rely on tautologies: adding an expression that is always true to the where-clause of a select statement. Like OR 1=1. 1=1 is a tautology, it’s an expression that always yields true.

So if SELECT * FROM USERS WHERE USERNAME = ‘ADMIN’ and PASSWORD = ‘UNKNOWN’ doesn’t select any rows because the password is not correct, injecting ‘ OR 1=1 — gives SQL statement SELECT * FROM USERS WHERE USERNAME = ‘ADMIN’ and PASSWORD = ” OR 1=1 –‘ which will return all rows, because the where-clause is always true (OR 1=1).

There are several security applications (WAFs, SQL firewalls, …) designed to monitor the stream of SQL statements and reject statements with tautologies, i.e. the result of a SQL-injection. Some are very simple and just try to match pattern 1=1. Bypassing them is easy: 1>0 is also a tautology. Others are more sophisticated and try to find constant expressions in the where-clause. Constant expressions are expressions with operators, functions and constants, but without variables. If a constant expression is detected that always evaluates to true, the firewall assumes it’s the result of a SQL-injection and blocks the query.

This is all classic SQL-injection, but now comes the interesting part.

What if I use an expression that is not a tautology in it’s mathematical sense, but is almost one… Say I use expression RAND() > 0.01 ? The RAND function is a random number generator and returns a floating point value in the range [0.0, 1.0[. Expression RAND() > 0.01 is not a tautology, it’s not always true, but it is true about 99% percent of the time. I call this a quasi-tautology.

A firewall looking for tautologies will not detect this, because it is not a tautology. But when you use it in a SQL-injection, you stand a 99% chance of being succesful (provided the application is vulnerable to SQL-injection)!

There are other functions than RAND to create quasi-tautologies. An expression comparing the seconds of the current system time with 59 is also a quasi-tautology.

The GreenSQL firewall will detect SQL statements with quasi-tautologies, not because it looks for them, but because it builds a whitelist in training mode.

Quickpost info


  1. how about comparing the current seconds != 99?
    Always true and the system would have to know the valid range for anything that might be compared to detect this.

    Comment by oldami — Tuesday 2 February 2010 @ 13:13

  2. @oldami Yes, this is a pure tautology.

    Comment by Didier Stevens — Tuesday 2 February 2010 @ 14:45

  3. GreenSQL will also detect the attempt of quasi-tautologies with ‘or’ token

    Comment by xanda — Tuesday 2 February 2010 @ 16:13

  4. you stand a 99% chance of being succesful (provided the application is vulnerable to SQL-injection)!

    I think the chances are unknown, because it’s random.

    Comment by dblackshell — Wednesday 3 February 2010 @ 7:33

  5. @dblackshell No, I assume the PRNG produces random numbers following a uniform distribution (http://en.wikipedia.org/wiki/Pseudorandom_number_generator), so on average, the injection will succeed around 99% of the time.

    Comment by Didier Stevens — Wednesday 3 February 2010 @ 10:08

  6. This is a nice twist on the concept – and its equally true that just looking for tautologies isn’t going to be a reliable measure as you can find something that will return true most of the time. I’m more of a fan of something that learns the syntax of the SQL code itself, and then notes where it deviates. GreenSQL does this to some extent, however I did see a fascinating talk at BlackHat USA a few years ago on using formal grammars for detecting SQL Injection – this would be a good example in that having a tautology (or even near one) would change the grammar tree generated and allow you detect tampering. Haven’t heard anything on anyone trying this approach since then – its a bit of a challenge as you need a grammar for each dialect of SQL, unfortunately.

    Comment by Justin Clarke — Wednesday 3 February 2010 @ 23:53

  7. As specified in the MySQL documentation for function RAND():

    Returns a random floating-point value v in the range 0 <= v < 1.0. If a constant integer argument N is specified, it is used as the seed value, which produces a repeatable sequence of column values.

    So to produce a Pseudo-random number, a parameter should be specified; and in that case would you have a 99% success rate

    Comment by dblackshell — Thursday 4 February 2010 @ 9:30

  8. @dblackshell: Actually, when you provide a constant as seed value, you can predict the next numbers and thus achieve 100% (or 0%) success rate.

    Comment by Didier Stevens — Thursday 4 February 2010 @ 23:43

RSS feed for comments on this post. TrackBack URI

Leave a Reply (comments are moderated)

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Blog at WordPress.com.