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.
Didier Stevens 
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
@oldami Yes, this is a pure tautology.
Comment by Didier Stevens — Tuesday 2 February 2010 @ 14:45
GreenSQL will also detect the attempt of quasi-tautologies with ‘or’ token
Comment by xanda — Tuesday 2 February 2010 @ 16:13
I think the chances are unknown, because it’s random.
Comment by dblackshell — Wednesday 3 February 2010 @ 7:33
@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
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
As specified in the MySQL documentation for function RAND():
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
@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