Crypt::OpenSSL::DSA bug

Karl Koscher mrsaturn at
Sat May 21 18:33:38 PDT 2005

One of the sites I'm testing OpenID is randomly failing to verify the 
signature, so I wrote a perl script that repeatedly gets an OpenID 
signature from LiveJournal and verifies it three ways:

* Using Crypt::OpenSSL::DSA
* Using the openssl binary
* Using a "homebaked" solution with code from Ben Trott's 
Authen::TypeKey module

Crypt::OpenSSL::DSA always says the signature is valid, but the two 
other methods also randomly fail. This made me suspect that there was a 
bug in Crypt::OpenSSL::DSA. As it turns out, it looks like there is.

I added some code that printed out the sha1 hash (in hexadecimal) of the 
"timestamp::assert_identity::idurl::returl" string, the timestamp, the 
signature (in base64), and the results of the three tests. The output 
was very interesting:

MCwCFAsx+GZWMht48+iuisu1FtfcXAFMAhRnvTXv6F18S+dbIElQvVFws40WXQ== ...
Crypt::OpenSSL::DSA says: Valid!
Verified OK
Homebaked: OK!

MC0CFDMwf90Bfyzi8vT2bsXWov5XtorxAhUAoHBY0m5AxcLlSS0kaT0wHeV/65s= ...
Crypt::OpenSSL::DSA says: Valid!
Verified OK
Homebaked: OK!

MC0CFQCkuTJbJPLbtVXwhwzqfW0Uy6rAggIUXCP7Hel4NyCcQoM6l4MyCTGdLac= ...
Crypt::OpenSSL::DSA says: Valid!
Verification Failure
Homebaked: Rotten!

MC0CFQCu8OdAIVnz+a52CoXrK356mWu0igIUQW0ek5gLZS7M8dWw+ps72V/o8fs= ...
Crypt::OpenSSL::DSA says: Valid!
Verification Failure
Homebaked: Rotten!

MC0CFH7D/oKTGLaWrXqE2BrAqJxMgE+dAhUA1qz/GJNw8QHqHf1Snj5NPW2OrcQ= ...
Crypt::OpenSSL::DSA says: Valid!
Verified OK
Homebaked: OK!

MC0CFBkaufjj/1pzkyPbxrQcgcoKZ0abAhUArARYypTfIh4SMLCADSy0onVDZ1A= ...
Crypt::OpenSSL::DSA says: Valid!
Verified OK
Homebaked: OK!

The hashes that failed to verify were 
d2bc5a4047f70033894bdb91eb3042f3df887e72 and 
6dbb6da9c56f91638c41a6d6fb0411216d00f8c1. Notice the 0x00 byte in there?

 From the Crypt::OpenSSL::DSA code:

        if (!(DSA_sign(0, (const unsigned char *)dgst, strlen(dgst), 
sigret, &siglen, dsa))) {
          croak("Error in DSA_sign: 
%s",ERR_error_string(ERR_get_error(), NULL));

strlen() finds the first NUL character in the string and uses that as 
the string length, so in effect, LJ is only signing part of the hash. 
Crypt::OpenSSL::DSA's verify function has the same bug, so since it's 
only verifying the same part of the hash, it returns success. I'm sure 
there's a better way for it to find out the actual string length, but my 
Perl ninja skillz aren't mad enough for me to know. ;)

Now, imagine you found an OpenID message that hashed to something that 
began with a NUL character. You could then get LJ (or any other identity 
server that uses Crypt::OpenSSL::DSA) to sign the message, and you have 
a signature that works for ANY message that also hashes to a string that 
begins with NUL. Theoretically, this would work as long as the public 
key remained the same -- you could use any timestamp you wanted, as long 
as the message hashed that way.

I'm not a crypto expert by any means, so I'm not sure how feasible that 
is in practice (I'm guessing "not likely"), but it might be something to 
be concerned about. However, as long as either the identity server or 
the consumer doesn't use  a vulnerable version Crypt::OpenSSL::DSA, this 
attack shouldn't be possible.

BTW, in case anyone is wondering why the other hash with a "00" in it 
verified, it's because those zeros straddled a byte boundary, so there 
weren't any NUL characters.

- Karl

More information about the yadis mailing list