Micali-Schnorr Generator (MS-DRBG) Part III - Zero Knowledge Proof Wanted!!

Type intothesymmetry
Reporter ll (noreply@blogger.com)
Modified 2018-07-02T10:53:53


See also Part I and Part II of this series
This is going to be a short blog post about the (in)famous Micali-Schnorr Random Number Generator (MS-DRBG). See Part I and Part II of this series for more information about this topic.* *

*WHO: *NIST published the specification for Micali-Schnorr Random Number Generator (MS-DRBG) in ~~NIST Special Publication 800-90~~ ISO 18031. Along with the explanation of the core algorithm the documents contains the specification's moduli with the claim to be of the form n = pq with p = 2p1 + 1, q = 2q1 + 1, where p1 and q1 are (lg(n)/2 – 1)-bit primes.

N.B. a prime of the form p = 2p1 + 1 where p1 is also a prime goes under the name of Safe Prime and they are often used in cryptography for both RSA and DH.

WHAT: Now we can look at the ~~NIST Special Publication 800-90~~ ISO 18031's moduli and simply believe that those modulis are of the claimed form but maybe is not a great idea (see the WHY section). Going to N(SA)IST and just asking for the factorization is not a great idea either. In the first instance because this will never happen, secondly even if there is not even a single hint that let believe so, having the factorization of the moduli might jeopardize the security of the DRBG. So WHAT?. Well it turns out there is a really beautiful paper from 1998 by Camenisch and Michels where is possible to Proving in Zero-Knowledge that a Number is the Product of Two Safe Primes.

WHY: So why we should not trust a priori the aforementioned claim? Well let's say that what happened in the Dual_EC_DRBG case where the presence of a backdoor is now a certainty make us at least raise an eyebrow.

WHEN: Well ideally this should had happened already when the specification (that includes the modulis) was redacted (let's remember that the Camenisch/Michels's paper predates the spec by many years) but Hey is never too late for a nice Zero Knowledge Proof :p

WHERE: I wonder where/how this could ever happen.... any idea ?

*Having such a ZK proof would be a really win-win in an ideal World. I know this will never happen for this specific case but in my humble opinion this should be the way to go for future specifications!

*That's all folks. For more crypto goodies, follow me on Twitter.*