Publish primes with seeds, so we know there are no backdoors
Researchers with at the French Institute for Research in Computer Science and Automation (INRIA) and the University of Pennsylvania have called for security standards-setters to publish the seeds for the prime numbers on which their standards rely.
The boffins also demonstrated again that 1,024-bit primes can no longer be considered secure, by publishing an attack using “special number field sieve” (SNFS) mathematics to show that an attacker could create a prime that looks secure, but isn’t.
Since the research is bound to get conspiracists over-excited, it’s worth noting: their paper doesn’t claim that any of the cryptographic primes it mentions have been back-doored, only that they can no longer be considered secure.
“There are opaque, standardised 1024-bit and 2048-bit primes in wide use today that cannot be properly verified”, the paper states.
Joshua Fried and Nadia Heninger (University of Pennsylvania) worked with Pierrick Gaudry and Emmanuel Thomé (INRIA at the University of Lorraine on the paper, here.
They call for 2,048-bit keys to be based on “standardised primes” using published seeds, because too many crypto schemes don’t provide any way to verify that the seeds aren’t somehow back-doored.
Examples of re-used primes in the paper include:
Many TLS implementations use some form of default, and as a result, “in May 2015, 56 per cent of HTTPS hosts selected one of the 10 most common 1024-bit groups when negotiating ephemeral Diffie-Hellman key exchange”;
In IPSec, “66 per cent of IKE responder hosts preferred the 1024-bit Oakley Group 2 over other choices” for their Diffie-Hellman exchange; and
OpenSSH implementations favour “a pre-generated list that is generally shipped with the software package”.
If any of the “hard-coded” primes were maliciously produced – something that’s happened before, for those who remember RSA’s NSA-funded Dual EC Deterministic Random Bit Generator – it would be hard to spot by looking at the numbers, but factorisation would be feasible.
It might not necessarily be easy, however: the paper describing the SNFS computation notes it needed “a little over two months of calendar time on an academic cluster” (using between 500 and 3,000 cores in different phases in the operation – a total of around 400 core-years).
Their experiments ran on France’s Grid’5000 testbed, the University of Pennsylvania’s Cisco UCS cluster, the University of Waterloo’s CrySIP RIPPLE facility, and Technische Universiteit Eindhoven’s Saber cluster.
Earlier this year, INRIA researchers turned up the Sweet32 birthday attack against old Blowfish and Triple DES ciphers, and in January the group warned the world that the zombie MD5 and SHA1 hash protocols live on in too many TLS, IKE and SSH implementations. ®