McEliece original system broken
Daniel J. Bernstein,
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.
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
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
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
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)
TU/e international press release, October 31th, 2008 (in English)
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
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 break was reported on several sites and newspapers. Here is a