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.