shared secret alternative to DSA

Jean-Luc Delatre jld at club-internet.fr
Sat Jun 4 11:42:04 PDT 2005


Paul Crowley wrote:

>
> Sure.  But the dependencies are quite a bind, and you really can't 
> escape them - rolling your own DSA implementation is really out of the 
> question, because even if you're prepared to put up with the very poor 
> performance that a naive bignum-based implementation would give you, 
> rolling an ASN.1 parser and parsing out the public key is quite 
> painful enough by itself.  

Sorry, entirely untrue,  you need only a *subset* of ASN1.
Here is the code, PHP sigh... crappy but everywhere:

 ============================================================================

// standalone PEM decoding

function splitkey($key,$pass) {
    //echo  "KEY " . $key . "<br>";
    $raw = array();
    $foo = preg_match("/-----BEGIN 
([^\n\-]+)-----\n(.*?\n\n)?(.+)-----END .*?-----\s*$/s",$key,$raw);

    $headers = array();
    if ($raw[2]) {    // some headers
        foreach (explode("\n",$raw[2]) as $line) {
            $words = explode(":",$line,2);
            if ($words) $headers[$words[0]] = $words[1];
        }
    }

    $buf = base64_decode($raw[3]);

    //if ($headers["Proc-Type"] == "4,ENCRYPTED" && $headers["DEK-Info"]) {
    //    $ciph = explode(",",$headers["DEK-Info"]);
    //    $buf = decrypt($buf,$ciph[0],pack("H*",$ciph[1]),$pass);
    //}

    //echo  "BUF '" . $raw[1] . "' " . bin2hex($buf) . "<br> M=" .$foo 
." " . $raw . "<br>";

    $res = array();
    asndecode($buf,$res);

    if ($raw[1] == "DSA PRIVATE KEY")
        $res = fieldsremap($res[0], 
array('version','p','q','g','pub_key','priv_key'));
    else
        $res = fieldsremap($res, array(array('objId', 
array('p','q','g')),'pub_key'));
    return     $res;
}

function fieldsremap($raw,$tree) {
    $flat = array();
    walkremap($raw,$tree,$flat);
    return $flat;
}

function walkremap($raw,$tree,&$flat) {
    foreach ($tree as $key => $val) {
        if (is_array($val)) {
            if (is_array($raw[$key])) walkremap($raw[$key],$val,$flat);
        } else
              $flat[$val] = $raw[$key];
    }
}

// 
============================================================================

// ASN1 subset

// tags
define("ASN_INTEGER", 0x02);
define("ASN_BIT_STR", 0x03);
define("ASN_OBJECT_ID", 0x06);
define("ASN_SEQUENCE", 0x10);

//length encoding
define("ASN_LONG_LEN", 0x80);
define("ASN_EXTENSION_ID", 0x1F);

$asntag =  array();
$asntag[ASN_INTEGER] = "asn_int";
$asntag[ASN_BIT_STR] = "asn_bitstr";
$asntag[ASN_OBJECT_ID] = "asn_obj";
$asntag[ASN_SEQUENCE] = "asn_seq";

function asndecode($str,&$res) {
    global $asntag;
    //echo  "DECODE "  .strlen($str). "<br>";

    $i = 0;
    while ($i < strlen($str)) {
        $tag = ord(substr($str,$i,1)); ++$i;
        $len = ord(substr($str,$i,1)); ++$i;

        // end of "cIL" constructed indefinite length (must have been 
recursively called)
        if ($tag == 0 && $len == 0) return i;

        if ($len & ASN_LONG_LEN) {
            $k = $len & 0x7f;
            $len = 0;
            while (--$k >= 0) { $len = $len * 256 + 
ord(substr($str,$i,1)); ++$i;}
        }
        $func = $asntag[$tag & ASN_EXTENSION_ID];
        //echo  "ASN "  .  bin2hex(chr($tag)) . " " . $len . " '" . 
$func . "'<br>";
        if (!$func) {
            if ($DEBUG_DSA) echo "unexpected ASN tag " .  
bin2hex(chr($tag)) . "<br>";
            break;
        }
        $i = $func($str,$i,$tag,$len,$res);
    }
    if ($i != strlen($str)) {    // garbled
        if ($DEBUG_DSA) echo "garbled ASN at " . $i . " " .  
bin2hex($str) . "<br>";
        return array();
    }
    //echo  "GOT " ; print_r(array_values($res));
    return $res;
}

function asn_int($str,$i,$tag,$len,&$res) {
    $sign = ord(substr($str,$i,1));
    if ($sign & 0x80) {
        $sign = -1;
        for ($k = $len; --$k >= 0; ) $sign = bigmul($sign,256);
    } else
        $sign = 0;
    $k = 0;
    while (--$len >= 0) {
        $k = bigmul($k,256);
        $k = bigadd($k, ord(substr($str,$i,1)));
        ++$i;
    }
    $res[] =  bigadd($k,$sign);
    return $i;
}

function asn_bitstr($str,$i,$tag,$len,&$res) {
    $res[] = substr($str,$i,$len);
    return $i + $len;
}

function asn_obj($str,$i,$tag,$len,&$res) {
    $obj = array();
    $obj[] =  ord(substr($str,$i,1)) / 40;
    $obj[] =  ord(substr($str,$i,1)) % 40; ++$i;
    while ($len > 1) {
        $k = 0;
        do { $k = $k * 128 + (ord(substr($str,$i,1)) & 0x7f); ++$i; --$len;
        } while (!(ord(substr($str,$i-i,1)) & 0x80));
        $obj[] = $k;   
    }
    $res[] = $obj;
    return $i;
}

function asn_seq($str,$i,$tag,$len,&$res) {
    $seq = array();
    if ($len) {
        asndecode(substr($str,$i,$len),$seq);
        $i = $i + $len;
    } else {
        $i = $i + asndecode($str,$seq);
    }
    $res[] = $seq;
    return $i;
}


// 
============================================================================

There is still a bug in 'fieldsremap' but it does parse both public and 
private keys.
The 'bigxxx' functions are wrappers to either BCMath or GMP bignum 
packages depending on availability
which *are* implemented already for BCMath (I don't have yet access to a 
host with GMP).

The decryption of the private key by DES-EDE3-CBC seems unrealistic but 
the DSA itself is not.
An implementation by Daiji Hriata exists and is used by Phillip Pearson 
and I am rewriting it to make it standalone, not depending  on any fancy 
packages but BCMath/GMP which are unavoidable.

The performance of the bignums is quite ugly of course but for the 
consumer side it matters much less than ease of installation.

Overall, that means that we can switch *or not* to HMAC or even to RSA 
if needed (if this is cheaper/safer than DSA)

> A completely stateless design is still possible, but you need to be 
> cunning about it.  You have to have a consumer secret, then 
> encrypt/MAC the HMAC-SHA1 secret with the consumer secret, and include 
> that in the return_to URL.

Yes,  I would very much like a completely stateless consumer if  that 
can be done safely, i.e. safe from spoofing of the forwarded/returned 
"state" values.

> > What pros/cons and counter arguments am I missing?
>
> The big PRO argument that doesn't get a mention here is performance. 
> People who take a lot of SSL connections spend real money on SSL 
> accelerators to do the public key math in reasonable time.  HMAC-SHA1 
> is a thousand times faster.  It makes it possible to host the world's 
> most popular OpenID server on an old Pentium under the stairs.  A 
> three millisecond calculation is a noticeable burden; a two 
> microsecond HMAC-SHA1 one really isn't.
>
The server is an entirely different story from the consumer, performance 
wise.
However, for using HMAC, I would use Tiger hash rather than SHA1 which 
is known to be "broken":
http://lists.danga.com/pipermail/yadis/2005-May/000272.html

For  those worried about AJAX stuff, JAVA and Javascript crypto 
libraries are available under BSD license:

http://pajhome.org.uk/crypt/index.html

And I *do have* a Tiger hash implementation in Javascript which is 
faster (20%) than Paul Johnston's SHA1

I understand that this level of concern may be irrelevant for shielding 
teen girls from their ex-boyfriends
but it may not be so irrelevant to the *fame* of OpenID which would be 
significant a factor for its wider adoption.

If it looks like a toy for teen girls weblogs, then...

>
> If I really can't convince people here that it's no worse to send the 
> MAC secret in the clear, then let's move to an HMAC-SHA1 + DH protocol. 

I am not convinced by "secrets in the clear"...

> That will address people's concerns, while still preserving the 
> performance advantages, and avoiding the implementation complexity of 
> DSA.   But to be honest I'm still far from convinced.  If you think 
> there's a real risk your consumer connection to the ID server will be 
> snooped, you should be just as worried about the risk it'll be 
> tampered with, and in that case the only thing that will save you is SSL.


What about adding some kind of key in the <link re=...  key='... 
base64..."  with which one could authenticate the server replies?
Because there are really only *two* parties from the very beginning: the 
consumer and the ID url issued thru the browser and each of those is 
implicitely trustworthy to the other.

Cheers,

JLD




More information about the yadis mailing list