[Cryptography] Is the real cause of the recent socat error now known?

[david wong]

> I personally thus find the term "deterministic version of M-R" somewhat
confusing in this context.

  

The paper shows how to build a "fake" prime that passes the deterministic
version of the Rabin Miller test. To test Rabin Miller you can take random
bases OR you can always run it with the same set of bases (which is the
deterministic version of the test). They show that you can choose a number n =
p * q, where p and q are somehow related and they will pass the test for every
base b if b is coprime to p and b is a square modulo q.  
As I said this method works if you know in advance the bases that will be used
(which is rarely the case I suppose). Also it seems like you are really
limited in the number of witness you fool, but this is an old paper and we
might be able to do better now.

  

> Could you sketch how you implement the backdoor? From what I know from

  

I have two techniques so far: hiding a subgroup in a composite modulus or
hiding a smooth order in a composite modulus.

  

In both you generate your modulus n = pq with two fairly strong primes (to
avoid any factorization algorithms).

  

In the first technique p and q both hide a small subgroup for your generator,
so by taking a public key modulo p and q you only have a small discrete
logarithm to compute (so you can use Pollard Rho)

  

The second technique has p-1 and q-1 both B-smooth, with B large enough to
avoid the p-1 factorization algorithm (so >10^15 according to the records
of p-1). This way you can use Pohlig-Hellman.

  

The implementation/exploitation of TLS is a bit more verbose, gotta extract
some information, recompute the premaster key, derive the master key, derive
the keys, decrypt

  

David

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20160318/507c6b95/attachment.html>