[Cryptography] DH non-prime kills "socat" command security

[Henry Baker]

At 02:14 AM 2/4/2016, mok-kong shen wrote:
>Am 03.02.2016 um 02:43 schrieb Henry Baker:
>> For the past year, the Linux command "socat" has been assuming that the
>> following number is prime; thus breaking its crypto security.
>
>[snip]
>
>Among possible causes I surmise that possibly Miller-Rabin test was used to find a prime, which however can't guarantee that the result is a prime (only highly likely a prime when a sufficient number of rounds of the test get passed).
>
>Anyway, I suppose one should in crypto replace prime generation with probability tests by provable prime generatión.
>
>I have coded Maurer's algorithm of generation of provable primes in Python and found that (at least in Python, which is interpreted and hence less runtime efficient) Maurer's algorithm is quite comparable in cpu time with the method that uses the Miller-Rabin test.
>
>See http://s13.zetaboards.com/Crypto/topic/7234475/1/

The purported prime in the socat news story doesn't pass any of the simple primality tests of the type that you describe, so it is obvious to include such primality tests in the QA for these socat algorithms.  After factoring out the two small factors 271 and 13,597, the resulting 1002-bit number *still doesn't pass* simple primality tests, but I wasn't able to further factor it in 15 minutes on my really old, really slow laptop.  So someone was criminally stupid, or else purposely installed this non-prime backdoor.

There is an outstanding problem: if we all use the same primes, large nation-states can build log (rainbow-like) tables for these primes; if we use different primes, we then have to prove to our correspondent that the "prime" we propose is really prime.  Generating such primes and generating such easily-checkable proofs appears to take too much time for normal HTTPS ecommerce.