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