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

mok-kong shen mok-kong.shen at t-online.de
Fri Mar 18 10:11:01 EDT 2016


Am 17.03.2016 um 21:39 schrieb david wong:
> To answer the title: no, we don't know. It was probably a developer who
> had no idea how crypto works. For the story, the guy who submitted the
> patch erased both his personal blog and his github account the day the
> security was publicly disclosed
>
>  > (1) Scientific: Almost certainly a probabilistic procedure (commonly
> involving the Miller-Rabin Test) was employed instead of Maurer's
> algorithm of provable prime generation. Hence with some, though
> practically very minute (depending on the parameter t of the
> Miller-Rabin Test), probability one could indeed have obtained a
> composite instead of a prime number
>
> Even with M-R you would have to know exactly what bases would be used to
> test the prime (so the test would have to use the deterministic version
> of M-R) to produce the prime in the first place. And this would have to
> be done maliciously. (cf.
> http://www.jointmathematicsmeetings.org/mcom/1995-64-209/S0025-5718-1995-1260124-2/S0025-5718-1995-1260124-2.pdf
> )
>
>  > (2) Human: Human errors of diverse genre and manipulation (backdoor).
>
> I've tried a bunch of things, and so have other people. Nothing works
> except if you append "f0" to the hexstring: you obtain a prime. It could
> mean it was truncated to reach 1024bits exactly but this doesn't mean
> anything as you will often be able to add a higher byte to a non-prime
> to make it prime. There was also some effort on the mersenne forum to
> factor the composite modulus but only two small factors were found (by
> trial division).
>
> I don't think this is a backdoor, but I found the idea interesting: how
> to change one value in your ephemeral Diffie-Hellman parameters to make
> it a backdoor. I've implemented ways to do it:
> https://github.com/mimoo/Diffie-Hellman_Backdoor and plan to release a
> paper whenever I'm done (if someone is interested to discuss about it
> ping me!).
>
> If there is something we can do, to react positively from this story, is
> check for similar potential backdoors in VPN implementations be them
> closed or open source. Good thing a list was released a few days ago:
> http://lifehacker.com/this-massive-vpn-comparison-spreadsheet-helps-you-choos-1764427219

The pdf-file you cited is exactly my point. If I don't err, one
commonly proceeds to generate a k-bit prime as follows: Generate a
k-bit odd number n. Use a set of small primes to do trial divisions to
eliminate it, in case it is thus found to be composite. If n survives,
apply M-R test for some practically reasonable value of the parameter
t of the test. If n still survives, consider n to be prime. If n fails
any of the above tests, then either increase n by 2 or generate a new
random k-bit odd number n and redo the above. M-R gives a security
guarantee of primality of a number n passing it only with a certain
probability depending on the chosen value of t and is classified as
a prbabilistic primarity test, see e.g. HAC. (I personally thus find
the term "deterministic version of M-R" somewhat confusing in this
context.)

To generate provable primes, one employs Maurer's algorithm. I have
done a runtime comparison between the common way of generation of
(highly probable) primes and the way via Maurer's algorithm and found
that, for higher values of t of M-R, Maurer's algorithm can be fairly
competitive. See s13.zetaboards.com/Crypto/topic/7234475/1/

Could you sketch how you implement the backdoor? From what I know from
the socat data, the backdoor for a k-bit number is done as follows:
Choose (one or) two small primes p1 and p2 (of one's desire) with their
product having k' bits. Generate (one or) two large primes p3 and p4
such that their product has k - k' bits. Then the "supposedly" prime
number n of k-bits is p1 * p2 * p3 * p4.

M. K. Shen





More information about the cryptography mailing list