Skip to main content

Posts

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 factori…
Post a Comment
Read more
Recent posts

The Ugly Duckling in factoring aka the filtering steps part I

People that knows me well are well aware that prime numbers have been my obsession since my childhood andtheyare source of continue interest for me. Actually thanks to cryptography they are a relevant part of my everyday life. One of the most important problem in cryptography since the discovery of RSA is factoring. The factoring problem consists of finding the prime numbers p and q given a large number , N = p x q.
Unless you are still convinced that factoring is an easy peasy problem, you should know that, while probably not NP-complete, factoring is indeed reaaally hard.
The faster known method for factoring is currently NFS (Number Field Sieve) and if you are interested in the topic I suggest you to read  this beautiful article from the great Carl Pomerance titled "A Tale of Two Sieves" . But it is not what I wanted to talk about today, mainly because the complete algorithm and all its shades go well beyond my current knowledge.
Today instead I want to talk you about one…
Post a Comment
Read more

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…
Post a Comment
Read more

Il (triste??) stato della crittografia (applicata) in Italia

Ho appena finito di scrivere a proposito dei miei 3 giorni trascorsi al Real World Crypto 2018 (il blog post per chi legge inglese e' qui) e mi sono accorto che non c'e' traccia di nessuna Universita' (ma anche azienda) italiana. Tutto cio' non puo' che rendermi un po' triste. L'Italia aveva una posizione di rilievo nell'"antica" crittografia. Non ci dimentichiamo dell'ormai super obsoleto (ma storicamente rilevante) Cifrario di Cesare per non parlare di volumi come "La crittografia diplomatica, militare e commerciale ossia l'arte di cifrare e decifrare le corrispondenze segrete" di Luigi conte Gioppi di Türkheim!! L'Italia ha tutt'ora crittografi di primo livello, basti pensare a Silvio Micali co-inventore delle Zero Knowledge Proof e vincitore della massima onoreficienza nel campo dell'informatica cioe' il Turing Award. Ora, scusate il mio sfogo, ma considerando che RWC e' di gran lunga la conferenz…
Post a Comment
Read more

Real World Crypto 2018 (RWC 2018) brain dump

The 2018 edition of Real World Crypto (RWC) was in Zurich (you can find the conference full program here.). I live in Switzerland so I was extremely happy about it. RWC is basically the best conference I ever attended and it will probably be so for a while. I almost risked to skip it due to flu but I eventually managed to attend :)

Current status: -1 to #realworldcrypto . Me sick in bed :( — Antonio Sanso @ RWC (@asanso) January 9, 2018 This short blog post is my brain dump of the event. If you want to know more you can find all the videos of the presentations in this youtube channel. The event lasted 3 days and every day was great. Event like this allowed me to meet personally many people I have interacted previously in a way or the other  and it turns out that a big percentage of people that do (applied) crypto was indeed attending. FWIW I was even able to shortly  ask to the great Prof Boneh about the now legendary Coursera Crypto II :D
Day I The first day could not start any bette…
2 comments
Read more

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

See  also Part I and Part III  of this series

tl;dr In the previous article of the same series we tried to predict the output of Micali-Schnorr Generator (MS-DRBG) knowing the factorization. In this blog post we continue the effort started in part I showing different strategies.  If you want to skip all my failures and go directly to the (in my humble opinion) most promising approach you can read directly the Solinas Prime and Generalized Mersenne Numbers section below.

If you actually wonder what is MS-DRBG and why I am trying to do it I'd suggest to go back and read the first article.
What I am NOT claiming in this post though is that there is a NSA's backdoor in the ANSI and ISO standards. Introduction and Failure #1 So let's start from were we actually finished the last post. We focused on an easier version of the problem directly extracted from the original Micali Schnorr paper


where the known output is up to 3/4 of the RSA computation and secret state is only 1/4 o…
Post a Comment
Read more