
ROR!
Popular admin tool Socat has issued a patch for an error that's been in the code for 12 months and is so egregious some fear it could be a backdoor. The problem, revealed here, is simple: the Socat SSL implementation uses a non-prime number as its Diffie-Hellman p parameter. Socat is akin to the famous *nix cat command, but …
Definitely not obvious - at least it didn't end in a 5 - but at the same time, any decent factorizing program would have reached 271 fairly quickly, so it's clear they didn't double-check the number in the code for primeness. Since one of the factors is so small, my guess is there was a typo of some sort; if I wanted to backdoor an encryption routine, I'd use a semiprime whose only two factors are roughly equal in length (~150 digits in this case), so it would take some significant number crunching to discover that it's not prime.
it would take some significant number crunching to discover that it's not prime.
Not at all:
(Ok, it's still O(log(n)^12) and the AKS algorithm is not used in practice, but still...)
Given that various researchers have done some serious crunching using Amazon web services for just a few dollars, checking a 1024 or 2048 bit number for primality should be relatively cheap and only needs doing once.
The big problem is not individual numbers but when an entire algorithm has been back doored by a state level actor. That requires the sort of informed scrutiny most of us simply aren't qualified to supply.
Just using BSD's command line factor, within a second (on a VAX, nonetheless) one already gets two factors:
factor 143319364394905942617148968085785991039146683740268996579566827015580969124702493833109074343879894586653465192222251909074832038151585448034731101690454685781999248641772509287801359980318348021809541131200479989220793925941518568143721972993251823166164933334796625008174851430377966394594186901123322297453
143319364394905942617148968085785991039146683740268996579566827015580969124702493833109074343879894586653465192222251909074832038151585448034731101690454685781999248641772509287801359980318348021809541131200479989220793925941518568143721972993251823166164933334796625008174851430377966394594186901123322297453: 271 13597
Nobody should ever take something like this on faith, unless the source is well known and in direct contact via secure communications. Even if you don't know how to set up the software to factor larger numbers, some sanity checking really isn't hard. It took me longer to copy and paste than the actual test took.
I tried that on my puny little Ubuntu box, and the factor command choked pathetically on a number of that size (actually, I think it has problems with anything larger than three digits...*)
Anyone know if the University of York still has a VAX? They did when I was there 20+ years ago and I think that's the only one I've ever used. I miss it.
(*feel free to insert mental "That's what SHE said!" here if so inclined)
I tried that on my puny little Ubuntu box, and the factor command choked pathetically on a number of that size
I just checked the source code for the FreeBSD version of factor and it uses the openssl bignum library to handle its arguments, so has no limit to size of input. The time to get the factors is another matter.
I don't think any malice was intended, I'm pretty sure this was just a programmer without much understanding of anything much just messing up.
It would've helped if the patch said how the dhparams had been generated. Someone would have noticed that it said "wild guess" instead of "openssl dhparam 1024". A lesson for anyone accepting patches in good faith.