Researchers in Japan have successfully cracked a next-generation pairing-based cryptography standard, setting a world record earlier this month in the process. Fujitsu Laboratories, the National Institute of Information and Communications Technology, and Kyushu University took 148.2 days to analyze the 278-digit, 922-bit standard, which was previously thought to require several hundred thousand years.
To achieve this, the team used 21 personal computers totalling 252 cores, which was several hundred times the computing power used to achieve the previous world record, combined with techniques including parallel programming methods to increase efficiency. The team also notes that such a task would have been impossible if they had been working with public key encryption.
Public key encryption is more secure than pairing based encryption because, unlike pairing-based cryptography, it avoids the key distribution problem entirely. A message can be encrypted and sent to a user by anyone with the user’s public key. However, only that user can decrypt the message with the private key. Because the private key is ideally not shared with anyone else, there is no chance that anyone can intercept the private key to decrypt the message.
However, not all applications are suitable for public-key encryption. Pairing-based encryption, on the other hand, uses a third key generator to obtain a relationship between the public and private keys of two users.
While Fujitsu’s feat is more an accomplishment of raw computing power and algorithmic innovation than the discovery of any flaw in pairing-based cryptography, it still shows that such a system, when properly implemented, would take less time to crack than previously expected.
Pairing-based cryptography is not the only method of encryption to have unexpected weaknesses revealed. Quantum cryptography, long-touted to herald the next generation of encryption techniques, has perhaps been superseded by a system based on far simpler physical principles.
Quantum cryptography entails encoding a message using a key generated by photons – massless packets of light. If passed through a polarizing filter, the photon will become polarized and exhibit spin only in the direction of the filter. Different directions of spin can be assigned to different binary digits. The spin of a polarized photon can be measured by the recipient using another polarizing filter.
The primary advantage of quantum cryptography is that any interception will alter the message intended for the recipient, allowing either the sender or recipient to cotton on to the fact that something is amiss.
This is not the first time that a weakness in quantum cryptography has been exposed. In 2010 it was discovered by researchers at the Norwegian Centre of Science and Technology. (Incidentally, one of the leaders of the group, Vadim Makarov, has shifted operations to the Institute of Quantum Computing in Waterloo). They found that it was possible to intercept a message by fooling the human recipient into thinking that the machine is misreading photons. It can be achieved by introducing a laser to “blind” the machine to any errors introduced while eavesdropping, allowing the attacker to intercept the message without anyone being any the wiser.
A new encryption system published earlier this month by Laszlo Kish’s research group at Texas A&M University that uses the Second Law of Thermodynamics and a simple electrical connection has been proven to be more secure against passive listening. It works on the principle that if an eavesdropper attempts to acquire more information about a message by sending signals of their own through the circuit through which two users are communicating, the amount of of current will increase. Normally this is impossible, as according to the Second Law of Thermodynamics, the entropy in a system will always decrease. The method will be secure until the Second Law is proven invalid, such as after the invention of a perpetual motion machine.
I wouldn’t be too sure that such a method is also infallible, because its implementation – indeed, the implementation of any security system – will pit a machine against human oversight and ingenuity. And Einstein did say that both stupidity and imagination were forces to be reckoned with. While I don’t relish the thought of being subject to shoddy encryption, the rapid changes in technology this prompts is undeniably exciting.
Leave a Reply