Crypt::OpenSSL::DSA bug

[Brad Fitzpatrick]

Karl,

Nice detective work!

I'll fix the Crypt::OpenSSL::DSA code (easy now that you've found the bug)
and try to get the maintainer to make a new release, or push one myself.
I've been helping/pushing Ben make a pure-Perl release of his Crypt::DSA
so we could easily rely on that, but it has a few shortcomings I'm still
working on fixing up.  In the end I'd like all three options
(Crypt::OpenSSL::DSA, Crypt::DSA, and openssl) to work and be options for
the Perl modules.

- Brad


On Sat, 21 May 2005, Karl Koscher wrote:

> 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
> _______________________________________________
> yadis mailing list
> yadis at lists.danga.com
> http://lists.danga.com/mailman/listinfo/yadis
>
>