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

2018-07-01T15:54:00

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

Description

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! *

{"id": "INTOTHESYMMETRY:368A7C96755FFC70F0032CD74A267E4A", "hash": "4e97529127251434551d722769404889", "type": "intothesymmetry", "bulletinFamily": "blog", "title": "Micali-Schnorr Generator (MS-DRBG) Part III - Zero Knowledge Proof Wanted!!", "description": "[![](http://i.imgflip.com/2d9fqx.jpg)](<http://i.imgflip.com/2d9fqx.jpg>)See also [Part I](<https://blog.intothesymmetry.com/2017/10/how-to-try-to-predict-output-of-micali.html>) and [Part II](<https://blog.intothesymmetry.com/2017/12/how-to-try-to-predict-output-of-micali.html>) of this series \nThis is going to be a short blog post about the (in)famous Micali-Schnorr Random Number Generator (MS-DRBG). See [Part I](<https://blog.intothesymmetry.com/2017/10/how-to-try-to-predict-output-of-micali.html>) and [Part II](<https://blog.intothesymmetry.com/2017/12/how-to-try-to-predict-output-of-micali.html>) of this series for more information about this topic.**** ****\n\n**** \n****\n\n[![](https://3.bp.blogspot.com/-j-PczypuJGM/WdeBiRfwLsI/AAAAAAAAC4o/1F-jpSt1dIYZJojZ0xzlDJDUupyuehTGQCPcBGAYYCw/s640/Screen%2BShot%2B2017-10-06%2Bat%2B3.13.23%2BPM.png)](<https://3.bp.blogspot.com/-j-PczypuJGM/WdeBiRfwLsI/AAAAAAAAC4o/1F-jpSt1dIYZJojZ0xzlDJDUupyuehTGQCPcBGAYYCw/s1600/Screen%2BShot%2B2017-10-06%2Bat%2B3.13.23%2BPM.png>)\n\n**** \n****\n\n \n\n\n****WHO: ****NIST published the specification for Micali-Schnorr Random Number Generator (MS-DRBG) in ~~[NIST Special Publication 800-90](<http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf>)~~ 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 \u2013 1)-bit primes.\n\n \n****\n\n[![](https://4.bp.blogspot.com/-q2KGX88lLM8/Wzj019Y7PjI/AAAAAAAADCw/wNkleHFX0Yk0ipzQJK7pN6VFQMOli9I0ACLcBGAs/s640/Screen%2BShot%2B2018-07-01%2Bat%2B5.32.28%2BPM.png)](<https://4.bp.blogspot.com/-q2KGX88lLM8/Wzj019Y7PjI/AAAAAAAADCw/wNkleHFX0Yk0ipzQJK7pN6VFQMOli9I0ACLcBGAs/s1600/Screen%2BShot%2B2018-07-01%2Bat%2B5.32.28%2BPM.png>)\n\n****\n\n**N.B. **a prime of the form p = 2p1 + 1 where p1 is also a prime goes under the name of [Safe Prime](<https://en.wikipedia.org/wiki/Safe_prime>) and they are often used in cryptography for both RSA and DH.** **\n\n \n\n\n**WHAT: **Now we can look at the ~~[NIST Special Publication 800-90](<http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf>)~~ 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](<http://www.brics.dk/RS/98/29/BRICS-RS-98-29.pdf>). \n****\n\n \n\n**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](<https://blog.cryptographyengineering.com/2013/12/28/a-few-more-notes-on-nsa-random-number/>) where the presence of a backdoor is now a certainty make us at least raise an eyebrow. \n**** \n \n**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 \n \n**WHERE: **I wonder where/how this could ever happen.... any idea ? \n \n****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! \n**** \n \n\n\n#### _****That's all folks. For more crypto goodies, [follow me on Twitter](<https://twitter.com/asanso/>).****_", "published": "2018-07-01T15:54:00", "modified": "2018-07-02T10:53:53", "cvss": {"score": 0.0, "vector": "NONE"}, "href": "http://blog.intothesymmetry.com/2018/07/micali-schnorr-generator-ms-drbg-part.html", "reporter": "ll (noreply@blogger.com)", "references": [], "cvelist": [], "lastseen": "2019-04-05T14:03:04", "history": [{"bulletin": {"id": "INTOTHESYMMETRY:368A7C96755FFC70F0032CD74A267E4A", "hash": "", "type": "intothesymmetry", "bulletinFamily": "blog", "title": "Micali-Schnorr Generator (MS-DRBG) Part III - Zero Knowledge Proof Wanted!!", "description": "This is going to be a short blog post about the (in)famous Micali-Schnorr Random Number Generator (MS-DRBG). See [Part I](<https://blog.intothesymmetry.com/2017/10/how-to-try-to-predict-output-of-micali.html>) and [Part II](<https://blog.intothesymmetry.com/2017/12/how-to-try-to-predict-output-of-micali.html>) of this series for more information about this topic.**** ****\n\n**** \n****\n\n[![](https://3.bp.blogspot.com/-j-PczypuJGM/WdeBiRfwLsI/AAAAAAAAC4o/1F-jpSt1dIYZJojZ0xzlDJDUupyuehTGQCPcBGAYYCw/s640/Screen%2BShot%2B2017-10-06%2Bat%2B3.13.23%2BPM.png)](<https://3.bp.blogspot.com/-j-PczypuJGM/WdeBiRfwLsI/AAAAAAAAC4o/1F-jpSt1dIYZJojZ0xzlDJDUupyuehTGQCPcBGAYYCw/s1600/Screen%2BShot%2B2017-10-06%2Bat%2B3.13.23%2BPM.png>)\n\n**** \n****\n\n \n\n\n****WHO: ****NIST published the specification for Micali-Schnorr Random Number Generator (MS-DRBG) in [NIST Special Publication 800-90](<http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf>). 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 \u2013 1)-bit primes.\n\n \n****\n\n[![](https://4.bp.blogspot.com/-q2KGX88lLM8/Wzj019Y7PjI/AAAAAAAADCw/wNkleHFX0Yk0ipzQJK7pN6VFQMOli9I0ACLcBGAs/s640/Screen%2BShot%2B2018-07-01%2Bat%2B5.32.28%2BPM.png)](<https://4.bp.blogspot.com/-q2KGX88lLM8/Wzj019Y7PjI/AAAAAAAADCw/wNkleHFX0Yk0ipzQJK7pN6VFQMOli9I0ACLcBGAs/s1600/Screen%2BShot%2B2018-07-01%2Bat%2B5.32.28%2BPM.png>)\n\n****\n\n**N.B. **a prime of the form p = 2p1 + 1 where p1 is also a prime goes under the name of [Safe Prime](<https://en.wikipedia.org/wiki/Safe_prime>) and they are often used in cryptography for both RSA and DH.** **\n\n \n\n\n**WHAT: **Now we can look at the [NIST Special Publication 800-90](<http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf>)'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](<http://www.brics.dk/RS/98/29/BRICS-RS-98-29.pdf>). \n****\n\n \n\n**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](<https://blog.cryptographyengineering.com/2013/12/28/a-few-more-notes-on-nsa-random-number/>) where the presence of a backdoor is now a certainty make us at least raise an eyebrow. \n**** \n \n**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 \n \n**WHERE: **I wonder where/how this could ever happen.... any idea ? \n \n****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! \n**** \n \n\n\n#### _****That's all folks. For more crypto goodies, [follow me on Twitter](<https://twitter.com/asanso/>).****_", "published": "2018-07-01T15:54:00", "modified": "2018-07-01T15:54:45", "cvss": {"score": 0.0, "vector": "NONE"}, "href": "http://blog.intothesymmetry.com/2018/07/micali-schnorr-generator-ms-drbg-part.html", "reporter": "Antonio Sanso (noreply@blogger.com)", "references": [], "cvelist": [], "lastseen": "2018-07-01T16:28:07", "history": [], "viewCount": 48, "enchantments": {"score": {"value": 5.0, "vector": "NONE", "modified": "2018-07-01T16:28:07"}}, "objectVersion": "1.4"}, "lastseen": "2018-07-01T16:28:07", "differentElements": ["description", "modified"], "edition": 1}, {"bulletin": {"id": "INTOTHESYMMETRY:368A7C96755FFC70F0032CD74A267E4A", "hash": "c667c972a32f4450c0e6e7abf4295bb2", "type": "intothesymmetry", "bulletinFamily": "blog", "title": "Micali-Schnorr Generator (MS-DRBG) Part III - Zero Knowledge Proof Wanted!!", "description": "[![](http://i.imgflip.com/2d9fqx.jpg)](<http://i.imgflip.com/2d9fqx.jpg>)See also [Part I](<https://blog.intothesymmetry.com/2017/10/how-to-try-to-predict-output-of-micali.html>) and [Part II](<https://blog.intothesymmetry.com/2017/12/how-to-try-to-predict-output-of-micali.html>) of this series \nThis is going to be a short blog post about the (in)famous Micali-Schnorr Random Number Generator (MS-DRBG). See [Part I](<https://blog.intothesymmetry.com/2017/10/how-to-try-to-predict-output-of-micali.html>) and [Part II](<https://blog.intothesymmetry.com/2017/12/how-to-try-to-predict-output-of-micali.html>) of this series for more information about this topic.**** ****\n\n**** \n****\n\n[![](https://3.bp.blogspot.com/-j-PczypuJGM/WdeBiRfwLsI/AAAAAAAAC4o/1F-jpSt1dIYZJojZ0xzlDJDUupyuehTGQCPcBGAYYCw/s640/Screen%2BShot%2B2017-10-06%2Bat%2B3.13.23%2BPM.png)](<https://3.bp.blogspot.com/-j-PczypuJGM/WdeBiRfwLsI/AAAAAAAAC4o/1F-jpSt1dIYZJojZ0xzlDJDUupyuehTGQCPcBGAYYCw/s1600/Screen%2BShot%2B2017-10-06%2Bat%2B3.13.23%2BPM.png>)\n\n**** \n****\n\n \n\n\n****WHO: ****NIST published the specification for Micali-Schnorr Random Number Generator (MS-DRBG) in ~~[NIST Special Publication 800-90](<http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf>)~~ 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 \u2013 1)-bit primes.\n\n \n****\n\n[![](https://4.bp.blogspot.com/-q2KGX88lLM8/Wzj019Y7PjI/AAAAAAAADCw/wNkleHFX0Yk0ipzQJK7pN6VFQMOli9I0ACLcBGAs/s640/Screen%2BShot%2B2018-07-01%2Bat%2B5.32.28%2BPM.png)](<https://4.bp.blogspot.com/-q2KGX88lLM8/Wzj019Y7PjI/AAAAAAAADCw/wNkleHFX0Yk0ipzQJK7pN6VFQMOli9I0ACLcBGAs/s1600/Screen%2BShot%2B2018-07-01%2Bat%2B5.32.28%2BPM.png>)\n\n****\n\n**N.B. **a prime of the form p = 2p1 + 1 where p1 is also a prime goes under the name of [Safe Prime](<https://en.wikipedia.org/wiki/Safe_prime>) and they are often used in cryptography for both RSA and DH.** **\n\n \n\n\n**WHAT: **Now we can look at the ~~[NIST Special Publication 800-90](<http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf>)~~ 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](<http://www.brics.dk/RS/98/29/BRICS-RS-98-29.pdf>). \n****\n\n \n\n**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](<https://blog.cryptographyengineering.com/2013/12/28/a-few-more-notes-on-nsa-random-number/>) where the presence of a backdoor is now a certainty make us at least raise an eyebrow. \n**** \n \n**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 \n \n**WHERE: **I wonder where/how this could ever happen.... any idea ? \n \n****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! \n**** \n \n\n\n#### _****That's all folks. For more crypto goodies, [follow me on Twitter](<https://twitter.com/asanso/>).****_", "published": "2018-07-01T15:54:00", "modified": "2018-07-02T10:53:53", "cvss": {"score": 0.0, "vector": "NONE"}, "href": "http://blog.intothesymmetry.com/2018/07/micali-schnorr-generator-ms-drbg-part.html", "reporter": "Antonio Sanso (noreply@blogger.com)", "references": [], "cvelist": [], "lastseen": "2018-07-02T12:29:39", "history": [], "viewCount": 56, "enchantments": {"score": {"value": 5.0, "vector": "NONE", "modified": "2018-07-02T12:29:39"}, "dependencies": {"references": [], "modified": "2018-07-02T12:29:39"}}, "objectVersion": "1.4"}, "lastseen": "2018-07-02T12:29:39", "differentElements": ["reporter"], "edition": 2}, {"bulletin": {"id": "INTOTHESYMMETRY:368A7C96755FFC70F0032CD74A267E4A", "hash": "06dc5c94ffd8c85550964bb633f91cfc", "type": "intothesymmetry", "bulletinFamily": "blog", "title": "Micali-Schnorr Generator (MS-DRBG) Part III - Zero Knowledge Proof Wanted!!", "description": "[![](http://i.imgflip.com/2d9fqx.jpg)](<http://i.imgflip.com/2d9fqx.jpg>)See also [Part I](<https://blog.intothesymmetry.com/2017/10/how-to-try-to-predict-output-of-micali.html>) and [Part II](<https://blog.intothesymmetry.com/2017/12/how-to-try-to-predict-output-of-micali.html>) of this series \nThis is going to be a short blog post about the (in)famous Micali-Schnorr Random Number Generator (MS-DRBG). See [Part I](<https://blog.intothesymmetry.com/2017/10/how-to-try-to-predict-output-of-micali.html>) and [Part II](<https://blog.intothesymmetry.com/2017/12/how-to-try-to-predict-output-of-micali.html>) of this series for more information about this topic.**** ****\n\n**** \n****\n\n[![](https://3.bp.blogspot.com/-j-PczypuJGM/WdeBiRfwLsI/AAAAAAAAC4o/1F-jpSt1dIYZJojZ0xzlDJDUupyuehTGQCPcBGAYYCw/s640/Screen%2BShot%2B2017-10-06%2Bat%2B3.13.23%2BPM.png)](<https://3.bp.blogspot.com/-j-PczypuJGM/WdeBiRfwLsI/AAAAAAAAC4o/1F-jpSt1dIYZJojZ0xzlDJDUupyuehTGQCPcBGAYYCw/s1600/Screen%2BShot%2B2017-10-06%2Bat%2B3.13.23%2BPM.png>)\n\n**** \n****\n\n \n\n\n****WHO: ****NIST published the specification for Micali-Schnorr Random Number Generator (MS-DRBG) in ~~[NIST Special Publication 800-90](<http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf>)~~ 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 \u2013 1)-bit primes.\n\n \n****\n\n[![](https://4.bp.blogspot.com/-q2KGX88lLM8/Wzj019Y7PjI/AAAAAAAADCw/wNkleHFX0Yk0ipzQJK7pN6VFQMOli9I0ACLcBGAs/s640/Screen%2BShot%2B2018-07-01%2Bat%2B5.32.28%2BPM.png)](<https://4.bp.blogspot.com/-q2KGX88lLM8/Wzj019Y7PjI/AAAAAAAADCw/wNkleHFX0Yk0ipzQJK7pN6VFQMOli9I0ACLcBGAs/s1600/Screen%2BShot%2B2018-07-01%2Bat%2B5.32.28%2BPM.png>)\n\n****\n\n**N.B. **a prime of the form p = 2p1 + 1 where p1 is also a prime goes under the name of [Safe Prime](<https://en.wikipedia.org/wiki/Safe_prime>) and they are often used in cryptography for both RSA and DH.** **\n\n \n\n\n**WHAT: **Now we can look at the ~~[NIST Special Publication 800-90](<http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf>)~~ 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](<http://www.brics.dk/RS/98/29/BRICS-RS-98-29.pdf>). \n****\n\n \n\n**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](<https://blog.cryptographyengineering.com/2013/12/28/a-few-more-notes-on-nsa-random-number/>) where the presence of a backdoor is now a certainty make us at least raise an eyebrow. \n**** \n \n**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 \n \n**WHERE: **I wonder where/how this could ever happen.... any idea ? \n \n****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! \n**** \n \n\n\n#### _****That's all folks. For more crypto goodies, [follow me on Twitter](<https://twitter.com/asanso/>).****_", "published": "2018-07-01T15:54:00", "modified": "2018-07-02T10:53:53", "cvss": {"score": 0.0, "vector": "NONE"}, "href": "http://blog.intothesymmetry.com/2018/07/micali-schnorr-generator-ms-drbg-part.html", "reporter": "Unknown (noreply@blogger.com)", "references": [], "cvelist": [], "lastseen": "2019-04-04T07:56:53", "history": [], "viewCount": 56, "enchantments": {"score": {"value": 5.6, "vector": "NONE", "modified": "2019-04-04T07:56:53"}, "dependencies": {"references": [], "modified": "2019-04-04T07:56:53"}}, "objectVersion": "1.4"}, "lastseen": "2019-04-04T07:56:53", "differentElements": ["reporter"], "edition": 3}], "viewCount": 60, "enchantments": {"score": {"value": -0.2, "vector": "NONE", "modified": "2019-04-05T14:03:04", "rev": 2}, "dependencies": {"references": [], "modified": "2019-04-05T14:03:04", "rev": 2}, "vulnersScore": -0.2}, "objectVersion": "1.4", "_object_type": "robots.models.rss.RssBulletin", "_object_types": ["robots.models.rss.RssBulletin", "robots.models.base.Bulletin"]}