Skip to main content

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

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.



Comments

Popular posts from this blog

OpenSSL Key Recovery Attack on DH small subgroups (CVE-2016-0701)

Usual Mandatory Disclaimer: IANAC (I am not a cryptographer) so I might likely end up writing a bunch of mistakes in this blog post...

tl;dr The OpenSSL 1.0.2 releases suffer from a Key Recovery Attack on DH small subgroups. This issue got assigned CVE-2016-0701 with a severity of High and OpenSSL 1.0.2 users should upgrade to 1.0.2f. If an application is using DH configured with parameters based on primes that are not "safe" or not Lim-Lee (as the one in RFC 5114) and either Static DH ciphersuites are used or DHE ciphersuites with the default OpenSSL configuration (in particular SSL_OP_SINGLE_DH_USE is not set) then is vulnerable to this attack.  It is believed that many popular applications (e.g. Apache mod_ssl) do set the  SSL_OP_SINGLE_DH_USE option and would therefore not be at risk (for DHE ciphersuites), they still might be for Static DH ciphersuites.
Introduction So if you are still here it means you wanna know more. And here is the thing. In my last blog post I was …

All your Paypal OAuth tokens belong to me - localhost for the win

tl;dr  I was able to hijack the OAuth tokens of EVERYPaypal OAuth application with a really simple trick.
Introduction If you have been following this blog you might have got tired of how many times  I have stressed out the importance of the redirect_uri parameter in the OAuth flow.
This simple parameter might be source of many headaches for any maintainer of OAuth installations being it a client or a server.
Accepting the risk of repeating myself here is two simple suggestions that may help you stay away from troubles (you can always skip this part and going directly to the Paypal Vulnerability section):
If you are building an OAuth client,   Thou shall register a redirect_uri as much as specific as you can
i.e. if your OAuth client callback is https://yourouauthclient.com/oauth/oauthprovider/callback then

DO register https://yourouauthclient.com/oauth/oauthprovider/callbackNOT JUST https://yourouauthclient.com/ or https://yourouauthclient.com/oauth If you are still not convinced here…

Critical vulnerability in JSON Web Encryption (JWE) - RFC 7516

tl;dr if you are using go-jose, node-jose, jose2go, Nimbus JOSE+JWT or jose4j with ECDH-ES please update to the latest version. RFC 7516 aka JSON Web Encryption (JWE) hence many software libraries implementing this specification used to suffer from a classic Invalid Curve Attack. This would allow an attacker to completely recover the secret key of a party using JWE with Key Agreement with Elliptic Curve Diffie-Hellman Ephemeral Static (ECDH-ES), where the sender could extract receiver’s private key.

Premise
In this blog post I assume you are already knowledgeable about elliptic curves and their use in cryptography. If not Nick Sullivan's A (Relatively Easy To Understand) Primer on Elliptic Curve Cryptography or Andrea Corbellini's series Elliptic Curve Cryptography: finite fields and discrete logarithms are great starting points. Then if you further want to climb the elliptic learning curve including the related attacks you might also want to visit https://safecurves.cr.yp.to…