McEliece original system broken

Daniel J. Bernstein, Christiane Peters and I improved an attack on the McEliece cryptosystem which made it feasible to attack the original parameters (from the 1978 paper). We wrote an optimized implementation and used our computers and quite a few more machines worldwide to actually execute the attack; thanks to everybody who contributed! The attack succeeded in decrypting a challenge ciphertext in 8000 core-days. The paper describing the background appeared at the second PQCrypto workshop.
Christiane gave the presentation, her slides give more details about the actual attack and the computation power used. We intend to put more material online once we find the time.

Our press release, October 20th, 2008:

Cryptographers crack internet encryption of the future
A cryptosystem proposed in 1978, one of the leading candidates for "post-quantum cryptography," has been broken by researchers at TU/e.
Physicists have been racing to build quantum computers that would break the public-key cryptosystems used to protect Internet commerce today, such as RSA and elliptic-curve cryptography. However, quantum computers are not believed to affect the "McEliece cryptosystem" published thirty years ago.
Professor Tanja Lange (EIPSI), in a joint paper with her Ph.D. student Christiane Peters and with Professor Daniel J. Bernstein visiting from the University of Illinois at Chicago, described a way to speed up attacks against the McEliece cryptosystem. The researchers wrote software that would decrypt a McEliece ciphertext in just 14 days on a cluster of 100 computers.
The software was run on many computers in the Coding and Cryptography Computer Cluster (C4) and the SAN Distributed and Parallel Integrated Terminal (SANdpit) at TU/e, along with cooperating computers in Amsterdam (CWI), France (Loria), Ireland (DCU/ICHEC), Taiwan (NTU), and the United States (UIC). A lucky computer in Ireland found the ciphertext.
The successful attack was announced Saturday at a conference in Cincinnati on Post-Quantum Cryptography. The researchers said that the McEliece cryptosystem, when scaled to larger key sizes to avoid their attacks, remains a leading candidate for post-quantum cryptography.

TU/e press release, October 23th, 2008 (in Dutch), Link. :

TU/e kraakt internetbeveiliging van de toekomst
TU/e-onderzoekers zijn erin geslaagd de code van het zogeheten McEliece-encryptiesysteem te kraken. Dit systeem is een kandidaat voor de beveiliging van internetverkeer in het tijdperk van de kwantumcomputer -de voorspelde supersnelle computer van de toekomst. Tegelijk met de kraak presenteerden de wetenschappers een nieuwe sleutel.
De aanval is afgelopen weekeinde gelukt met hulp van een groot aantal gekoppelde computers in de hele wereld. Dit laat TU/e-hoogleraar Tanja Lange weten. Zij en haar promovenda Christiane Peters presenteerden vervolgens een nieuwe sleutel waarmee de McEliece-code wél tegen kwantumcomputers bestand is.
De gebruikte software kan het McEliece-encryptiesysteem met de rekenkracht van honderd computers binnen veertien dagen kraken. De kraak werd onlangs uitgevoerd met behulp van enkele tientallen computers, verspreid over de hele wereld, aldus Lange.
Momenteel gebruiken banken de RSA-code uit 1977 voor het beveiligen van bijvoorbeeld elektronische transacties. Een kwantumcomputer zal echter weinig problemen hebben om deze code te kraken, iets waarvoor een PC nu nog minimaal drie weken nodig heeft. Daarom zijn onderzoekers, vooruitlopend op de introductie van de kwantumcomputer (die volgens Lange nog minstens tien jaar op zich laat wachten), op zoek naar betere versleutelingsystemen. Professor Lange doet haar onderzoek in de groep Coderingstheorie en Cryptologie van de faculteit Wiskunde & Informatica.

TU/e press release, October 27th, 2008 (in English) Link:

TU/e international press release, October 31th, 2008 (in English) Link:

Researchers crack Internet security of the future
Researchers at Eindhoven University of Technology (TU/e) in The Netherlands have managed to crack the so-called McEliece encryption system. This system is a candidate for the security of Internet traffic in the age of the quantum computer - the predicted superpowerful computer of the future.
The attack succeeded this month by means of a large number of linked computers throughout the world, says TU/e professor Tanja Lange. Earlier this year she and her PhD student Christiane Peters, together with visiting professor Daniel Bernstein (University of Illinois, Chicago), had discovered a way to speed up attacks against the 30-year-old McEliece cryptosystem. The researchers wrote software that would decrypt a McEliece ciphertext in just 1 week on a cluster of 200 computers.
The software was run recently on several dozen computers in Eindhoven, Amsterdam, France, Ireland, Taiwan and the United States. A lucky computer in Ireland found the ciphertext.
The successful attack was announced recently at a conference in Cincinnati (US) on Post-Quantum Cryptography. The researchers said that the McEliece cryptosystem can be scaled to larger key sizes to avoid their attacks and remains a leading candidate for post-quantum cryptography. At present, banks use the RSA code from 1977 for securing matters such as electronic transactions. For RSA the currently used key sizes are significantly larger than initially thought: a single PC would need only 3 weeks to break the parameters from the original paper. Yet a quantum computer will have no problems cracking even the improved current version. For this reason, anticipating the introduction of the quantum computer (which Lange thinks will take at least ten more years) and to deal with long-term confidentiality such as health records, researchers are trying to find better encryption systems.
Professor Tanja Lange conducts her research within the Coding theory and Cryptology group of the Department of Mathematics & Computer Science at Eindhoven University of Technology in The Netherlands.

DCU press release, October 18th, 2008 (in English) Link:

Mike Scott and Neil Costigan (DCU) ran our software on the ICHEC Walton cluster. One of their computers was lucky to try a good combination and finished the attack. Their university issued a press release about the attack.

Media coverage

The break was reported on several sites and newspapers. Here is a short list:

ANP news release, e.g. in Eindhovens Dagblad and Volkskrant (in Dutch).
Slightly extended report (in Dutch).
Report by Patrick Wiercx in Eindhovens Dagblad from 24 October 2008, scanned version (in Dutch).
Same article electronically (in Dutch).
Report by Brenno de Winter in Webwereld.nl (in Dutch).
ZDNet report by Rowald Pruyn (in Dutch).
Sven de Jong reported about our attack and the cryptosystems RSA and McEliece for Kennislink (in Dutch).
Science Daily posts essentially our press release as Quantum Computers? Internet Security Code Of The Future Cracked (in English).
The Cursor (Informatie- en opinieblad van de Technische Universiteit Eindhoven) has a report by Tom Jeltes (in Dutch).
Tech Radar (in English).
The Quantum Pontiff reports on our work as Original McEliece Cracked (in English).
The Hindu titles New internet security system no longer secure; Thaindian news reports Computer scientists crack Internet security of the future and then news.google.com finds many differently titled copies of the press release, e.g. newsguide.us (in English) webinida123.com (in English).
Rowald Pruyn interviewed us for ZDNet and wrote a longer article which can be found on here (in Dutch).
Wolfgang Gruener reported on our attack on tgdaily (in English).
United Press International reports about our attack as McEliece Quantum Encryption System Cracked (in English).