Bug #88564 for CryptX: DSA is being done on message contents

Mon Sep 09 20:08:22 2013 DANAJ [...] cpan.org - Ticket created

Subject:

DSA is being done on message contents

I was trying to see which has was being used, when I discovered that Crypt::PK::DSA is using the message itself rather than the hash. libtommath's dsa_sign_hash expects a hash as the input, not the message. This is either an issue with the code or documentation. libtommath doesn't properly implement DSA according to FIPS 186, but we can still use that as a reference. From section 4.6 of FIPS 186-4: z = the leftmost min(N, outlen) bits of Hash(M). s = (k^-1(z+xr)) mod q so the documentation should either note that the input needs to be a truncated hash of the appropriate size and strength (from SP 800-57), or the code will need to perform the hash and truncation. A minor suggestion is that for people familiar with FIPS 186 and most of the rest of the world, some translation of the libtommath variables might be nice. "group size" is the 'q' size in octets, and "modulus size" is the 'p' size in octets. From section 4.2 of FIPS 186-4 (L and N are the bit lengths of p and q respectively): L = 1024, N = 160 => generate_key(20, 128) L = 2048, N = 224 => generate_key(28, 256) L = 2048, N = 256 => generate_key(32, 256) L = 3072, N = 256 => generate_key(32, 384) There's also the problem with libtommath's broken primality tests, but that's a tougher issue to solve.

Mon Sep 09 20:12:22 2013 DANAJ [...] cpan.org - Severity Normal added

Mon Sep 09 20:12:22 2013 DANAJ [...] cpan.org - Broken in 0.013 added

Wed Sep 11 06:27:36 2013 MIK [...] cpan.org - Correspondence added

Dne Po 09.zář.2013 20:08:22, DANAJ napsal(a): Show quoted text

> I was trying to see which has was being used, when I discovered that > Crypt::PK::DSA is using the message itself rather than the hash. > libtommath's dsa_sign_hash expects a hash as the input, not the > message. This is either an issue with the code or documentation. > > libtommath doesn't properly implement DSA according to FIPS 186, but > we can still use that as a reference. From section 4.6 of FIPS 186-4: > > z = the leftmost min(N, outlen) bits of Hash(M). > s = (k^-1(z+xr)) mod q > > so the documentation should either note that the input needs to be a > truncated hash of the appropriate size and strength (from SP 800-57), > or the code will need to perform the hash and truncation.

You are right, there is a mess in my library with dsa_sign/dsa_sign_hash (unfortunately not only with DSA). What functions/methods do you suggest for DSA? Do you think it is a good idea to provide both? 1/ sign_message('SHA256', $message); 2/ sign_hash($message_hash); Show quoted text

> A minor suggestion is that for people familiar with FIPS 186 and most > of the rest of the world, some translation of the libtommath variables > might be nice. "group size" is the 'q' size in octets, and "modulus > size" is the 'p' size > in octets. From section 4.2 of FIPS 186-4 (L and N are the bit > lengths of p and q respectively): > > L = 1024, N = 160 => generate_key(20, 128) > L = 2048, N = 224 => generate_key(28, 256) > L = 2048, N = 256 => generate_key(32, 256) > L = 3072, N = 256 => generate_key(32, 384)

I have fixed this in our git, I expect the next release this week (not only with this small doc fix :) Show quoted text

> There's also the problem with libtommath's broken primality tests, but > that's a tougher issue to solve.

You probably mean that 8 rounds of Miller-Rabin is not good enough? (I am not saying it is; I am just curios)

Wed Sep 11 06:27:36 2013 The RT System itself - Status changed from 'new' to 'open'

Wed Sep 11 10:48:46 2013 MIK [...] cpan.org - Correspondence added

I have just released 0.013_1 Please have a look at: https://metacpan.org/source/MIK/CryptX-0.013_1/lib/Crypt/PK/DSA.pm#L75 Now it seems to be more or less interoperable with Crypt::OpenSSL::DSA Thanks in advance for any feedback.

Wed Sep 11 13:06:49 2013 DANAJ [...] cpan.org - Correspondence added

On Wed Sep 11 10:48:46 2013, MIK wrote: Show quoted text

> I have just released 0.013_1 > > Please have a look at: > https://metacpan.org/source/MIK/CryptX-0.013_1/lib/Crypt/PK/DSA.pm#L75 > > Now it seems to be more or less interoperable with Crypt::OpenSSL::DSA > > Thanks in advance for any feedback.

I haven't tested it, but that looks good. I like that there is an option to just sign the hash (so they can do whatever they want) as well as a message with optional hash choice. The documentation is nice in that I can take the idea of "I want a 2048/256-bit DSA key" and see what arguments I should give to generate_key. I'll definitely be looking at it in the future when testing my DSA changes, as we really should be able to have people sign with one package and verify with another.

Wed Sep 11 14:41:27 2013 DANAJ [...] cpan.org - Correspondence added

On Wed Sep 11 06:27:36 2013, MIK wrote: Show quoted text

> Dne Po 09.zář.2013 20:08:22, DANAJ napsal(a):

> > There's also the problem with libtommath's broken primality tests, > > but > > that's a tougher issue to solve.

> > You probably mean that 8 rounds of Miller-Rabin is not good enough? (I > am not saying it is; I am just curios)

There are two issues. One is doing only 8 tests, which doesn't bother me quite so much as the next. At 160 bits, 8 tests should give us a better than 1e-15 chance of failure on random inputs (using Damgård/Landrock/Pomerance calculations, which based on their table 1 are conservative). If the input is chosen by an adversary, then only 1.5e-5. That seems high to me. But this is just being lax with the probability, which I wouldn't claim is "broken". My main issue is that it uses the first k prime bases for its tests. If I have a random number from 1 to 1M and ask you to guess it, your chances are 1 in 1 million. But if I never change my number, and you're allowed to keep guessing and talk to everyone else who's played, then the chances are no longer 1 in 1M, and once you know my number then you can guess it every time. That's essentially what using a fixed set of bases is doing. There are known numbers that pass the first 168 prime bases. Arnault in 1994 wrote a paper showing how to construct numbers that pass many given bases. This is a big issue if you're exposing the is-prime function to anything that can select its number (e.g. a user like Perl 6 does). For DSA use it doesn't seem obviously as bad since the input numbers are not user-chosen, but cryptography is a bad place to say "I can't think of how the known weakness can be exploited, so I guess it's ok." We could: - prove the primality. Fantastic for security, but requires a non-trivial implementation (For Crypt::DSA::GMP I'm using Math::Prime::Util::GMP) and is always going to be a performance concern. With MPU:GMP, it's almost free for < 256-bit, but gets quite noticeable after 1024 or so bits, and probably too slow for this application once in the 4096-bit range. WraithX has a nice APRCL implementation that looks promising also. Both are in GMP however, and would be quite a bit of work to put in libtommath. - BPSW + optional number of random [2, n-2] M-R bases. In my opinion the best solution, meets FIPS requirements, and good performance. This is what I'm doing in Crypt::DSA::GMP when not proving primality. See next item. - BPSW. Requires adding a Lucas test to libtommath, which isn't too hard (~40-100 lines of code), but you have to get it integrated into libtommath. ltm is kind of built around the idea of multiple M-R tests, which is a very 1980's way to do things. By itself BPSW isn't FIPS compliant, though it is what almost all math packages use now. FIPS wants some extra M-R tests. - M-R with random (in range [2,n-2]) bases. FIPS compliant, though they want a huge number of bases if you're not using a Lucas test. While random bases prevent a lot of crytographic attacks, it makes debugging more of a problem since you can't reproduce any failure. Since the BPSW test has no known counterexamples, it's unlikely to ever come up if you do that first.

Wed Sep 11 19:42:29 2013 DANAJ [...] cpan.org - Correspondence added

I believe the issues in this RT are fixed with the changes in 0.14, however you probably should add tests for the new functions. Feel free to close.

Sun Sep 15 15:39:39 2013 MIK [...] cpan.org - Correspondence added

Thanks for your explanation on primality testing. I have added missing tests in 0.016 and now closing this RT.

Sun Sep 15 15:39:40 2013 MIK [...] cpan.org - Status changed from 'open' to 'resolved'

Bug #88564 for CryptX: DSA is being done on message contents

Preferred bug tracker