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

Slack SAML authentication bypass

tl;dr  I found a severe issue in the Slack's SAML implementation that allowed me to bypass the authentication. This has now been solved by Slack.
Introduction IMHO the rule #1 of any bug hunter (note I do not consider myself one of them since I do this really sporadically) is to have a good RSS feed list.  In the course of the last years I built a pretty decent one and I try to follow other security experts trying to "steal" some useful tricks. There are many experts in different fields of the security panorama and too many to quote them here (maybe another post). But one of the leading expert (that I follow) on SAML is by far Ioannis Kakavas. Indeed he was able in the last years to find serious vulnerability in the SAML implementation of Microsoft and Github. Usually I am more an "OAuth guy" but since both, SAML and OAuth, are nothing else that grandchildren of Kerberos learning SAML has been in my todo list for long time. The Github incident gave me the final…

Bug bounty left over (and rant) Part III (Google and Twitter)

tl;dr in this blog post I am going to talk about some bug bounty left over with a little rant.

Here you can find bug bounty left over part I and II
Here you can find bug bounty rant part I and II
Introduction In one of my previous post I was saying that: 

"The rule #1 of any bug hunter... is to have a good RSS feed list."
Well well well allow me in this post to state rule #2 (IMHO)

"The rule #2 of any bug hunter is to DO NOT be to fussy with 'food' specifically with left over"

aka even if the most experience bug hunter was there (and it definitely was my case here, given the fact we are talking about no one less than filedescriptor) do not assume that all the vulnerabilities have been found! So if you want some examples here we go.
Part I - GoogleI have the privilege to receive from time to time Google Vulnerability Research Grant. One of the last I received had many target options to choose from, but one in particular caught my attention, namely Google Issue T…

How to try to predict the output of Micali-Schnorr Generator (MS-DRBG) knowing the factorization

The article was modified since its publication. Last update was 09/10/2017 

See  also Part II and Part III of this series

tl;dr in this post we are going to describe how to try predict the output of Micali-Schnorr Generator (MS-DRBG)  knowing the factorization of the n value. If this sounds like, "why the hell should I care?", you might want to give a look at this great post from Matthew Green about the backdoor in Dual_EC_DRBG. But In a nutshell, quoting Matthew Green : Dual_EC_DRBG is not the only asymmetric random number generator in the ANSI and ISO standards (see at the bottom).   it’s not obvious from the public literature how one would attack the generator even if one knew the factorization of the n values above. What I am NOT claiming in this post though is that there is a backdoor in one of this standard.

Introduction
The first time I heard about this problem is about couple of weeks ago via this Matthew's tweet: As a curiosity, the NSA didn’t just standardize Dua…