Crypt::OpenSSL::DSA bug

[Karl Koscher]

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:

91fc60125a3bcf13b6078c103eef6d785609e4f5
2005-05-22T00:58:57Z 
MCwCFAsx+GZWMht48+iuisu1FtfcXAFMAhRnvTXv6F18S+dbIElQvVFws40WXQ== ...
Crypt::OpenSSL::DSA says: Valid!
Verified OK
Homebaked: OK!

8fbb6c4eb1bc1fa00612a1293ca109d742cfef6e
2005-05-22T00:59:09Z 
MC0CFDMwf90Bfyzi8vT2bsXWov5XtorxAhUAoHBY0m5AxcLlSS0kaT0wHeV/65s= ...
Crypt::OpenSSL::DSA says: Valid!
Verified OK
Homebaked: OK!

d2bc5a4047f70033894bdb91eb3042f3df887e72
2005-05-22T00:59:22Z 
MC0CFQCkuTJbJPLbtVXwhwzqfW0Uy6rAggIUXCP7Hel4NyCcQoM6l4MyCTGdLac= ...
Crypt::OpenSSL::DSA says: Valid!
Verification Failure
Homebaked: Rotten!

6dbb6da9c56f91638c41a6d6fb0411216d00f8c1
2005-05-22T00:59:34Z 
MC0CFQCu8OdAIVnz+a52CoXrK356mWu0igIUQW0ek5gLZS7M8dWw+ps72V/o8fs= ...
Crypt::OpenSSL::DSA says: Valid!
Verification Failure
Homebaked: Rotten!

d0ef0168b0b93230cd127d8385d3545b1b86594e
2005-05-22T00:59:45Z 
MC0CFH7D/oKTGLaWrXqE2BrAqJxMgE+dAhUA1qz/GJNw8QHqHf1Snj5NPW2OrcQ= ...
Crypt::OpenSSL::DSA says: Valid!
Verified OK
Homebaked: OK!

9cddcc617c381fbccf6fb2b96333fbdb359aa671
2005-05-22T00:59:57Z 
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