[Cryptography] Generating random values in a particular range

[Sidney Markowitz]

Ray Dillinger wrote on 7/08/16 7:30 AM:
> This is dumb, and if they ever try to extort money from anyone based
> on this classic algorithm, shooting them down will be horribly easy.

Looking at it more, this looks like a submarine patent originally filed by
Certicom soon after Bleichenbacher announced the vulnerability, aimed at
catching out anyone using their obvious fix that ended up in common
implementations of DSA. FIPS 186 says "The algorithms in the Standard may be
covered by U.S. or foreign patents" but doesn't call out anything specific.

I just did a quick check of source code for DSA parameter generation in
OpenSSL and at least in the version I glanced at they seem to use the second
method that is specified in FIPS 186-4, which is the variation on the first
fix for Bleichenbacher's vulnerability that was specified in FIPS 186-2 Change
Notice 1. This was in
http://osxr.org:8080/openssl/source/crypto/bn/bn_prime.c#0243 where the first
step in checking for primality is to check if the random number (which is the
hash of the output of a PRNG) is greater than p. The call to it in
dsa/dsa_gen.c does loop until the primality test returns true, and so does
what the patent claims describe.

This means that it is irrelevant that there are prior examples of rejection
sampling. This is not a patent on rejection sampling. It is a patent on using
rejection sampling to eliminate the bias when generating a series of candidate
random numbers between 0 and L-bit prime p by getting an initial random number
(the seed) from a PRNG, hashing it to get a number of length L, rejecting it
if it is greater than p before checking it for primality, then if it is
rejected doing any transformation of the seed including simply incr4menting
it, hashing that new value, and trying again.

Challenging this patent would probably involve trying to convince the PTO or
the courts and/or a jury that once you know that the problem is that a simple
mod p introduces bias, the solution is obvious to anyone who has any expertise
in random number generation that you can solve the problem by using rejection
sampling in this way. Considering that the original algorithm was "1) take
H(seed) mod p to ensure a value less than p; 2) check if it is prime; 3) if it
isn't prime, increment or otherwise get a new seed to hash and loop back,
otherwise exit" and the new patented algorithm is identical except that
instead of taking the hash mod p in step 1 you instead make step 2 "check if
it smaller than p and is prime", there should be a good case for it being
obvious. However that makes the patent lawsuit something unpredictable. It is
not the slam dunk that it would be if it were an attempt to patent rejection
sampling itself.

This does actually look worse, though, as it means that Blackberry might be
going after anyone who is using OpenSSL and likely some other common libraries
for DSA. To work around the patent you would have to generate a hash at least
L+64 bits long, not too convenient when you are using a standard hash that is
the same length as the prime p.

Again, the patent is not relevant to the uniform random number generator in
the library that started this thread.

 Sidney