Hidden Math Flaw Jeopardizes Millions of Online Transactions

Mathematicians based in Switzerland and the United States have discovered a small but substantial flaw in some of the most commonly used digital encryption schemes, a flaw that could undermine the security of online retailing and communication.

Most encryption schemes rely on the random selection of large prime numbers to generate “public” and “private” keys that can authenticate online secure transactions. But in a paper released yesterday (Feb. 14), the researchers showed that among certain encryption schemes, a significant number of those large prime numbers are not random at all, placing public keys based on them at risk.

“This comes as an unwelcome warning that underscores the difficulty of key generation in the real world,” researcher James P. Hughes told the New York Times, which along with the Electronic Frontier Foundationwas the first to report the discovery.

The researchers did not speculate on the cause of the lack of randomness. At the moment, there is little the average person can do about the problem.

Undone by Arithmetic

The encryption schemes with the biggest flaws, the researchers found, were those based on the RSA 1024-bit algorithm, which uses two large prime numbers to generate a public key and a private key. As with all public-key encryption schemes, someone wishing to send a secret message to a recipient uses the recipient’s public key to encrypt the message, which can be decoded only by the recipient’s private key.

Using the ancient Greek mathematician Euclid’s simple but effective method of factoring numbers, Hughes and his fellow researchers proved that two out of every thousand RSA-1024-bit-based public keys shared one large prime number as a factor — far more than would occur if the numbers were truly random.

“We stumbled upon 12,720 different 1024-bit RSA moduli [out of 6.4 million studied] that offer no security,” the researchers wrote in their paper. “Their secret keys are accessible to anyone who takes the trouble to redo our work. … 1024-bit RSA provides 99.8 percent security at best.”

“Some people may say that 99.8 percent security is fine,” Hughes, who participated independently in the research from his home in Palo Alto, Calif., told the Times.

Not Good Enough

But 99.8 percent security is definitely not good enough for online transactions. Let’s assume that a major online retailer processes half a million purchase transactions per day. If one out of every 500 of those transactions were hijacked by cybercriminals, that would amount to roughly 10,000 compromised sessions — in which credit-card and personal data could be stolen — every single day.

“The lack of sophistication of our methods and findings make it hard for us to believe that what we have presented is new, in particular to agencies and parties that are known for their curiosity in such matters,” wrote the authors of the paper, which they half-jokingly referred to as a “sanity check.”

The researchers, who apart from Hughes were based at the École Polytechnique Fédérale de Lausanne in Switzerland, found that encryption schemes based on the 2048-bit RSA algorithm were also affected by the lack-of-randomness flaw, though to a smaller degree.

However, encryption schemes based on the Diffie-Hellman algorithm, which uses only one randomly generated number, were not affected by lack of randomness.  Hence the paper’s odd title, “Ron was wrong, Whit is right.”

Ron Rivest, along with Adi Shamir and Leonard Adleman, formulated the RSA algorithm at the Massachusetts Institute of Technology in 1978. (The three went on to found the RSA security company, which is still based near Boston.)

Email* (will not be published)
*Indicates required field
Submit Comments

All Product Types Accessories Cars Digital Camcorders Digital Cameras eReaders GPS Laptops MP3 & Video Players Projectors Smartphones Software Storage Tablets / MIDs VoIP Wi-Fi
All Subcategories
All Subcategories All-Purpose Budget Business Desktop Replacement Gaming Multimedia Netbook Nettop Rugged Student Tablet PCs Ultraportable
Acer Alienware Apple Archos ASUS Averatec BenQ CTL Corp. Dell Digital Storm eMachines Emtec Everex Fujitsu GammaTech Gateway General Dynamics Getac Gigabyte Hercules HP HTC iBuyPower Intel Lenovo MSI Nokia Nvidia OCZ OLPC OQO Origin Panasonic Sager Samsung Sony Sylvania Systemax TabletKiosk Toshiba Verizon Viewsonic Viliv VooDoo Workhorse PC ZT Systems
Minimum Rating
Any Rating 4.5 Stars 4.0 Stars 3.5 Stars 3.0 Stars
Screen Size
10 11 12 13 14 15 16 17 18 20 4 5 6 7 8 9
1024x576 1024x600 1024x768 1200X800 1280 x 720 1280x1024 1280x768 1280x800 1366x678 1366x768 1440x1050 1440x900 1600x768 1600x900 1680x1050 1680x945 1920x1080 1920x1200 800x400 800x480
Weight Range
10.1 - 12.0 pounds 12.1 - 14.0 pounds 14.1 - 16.0 pounds 2 lbs 2 pounds and under 2+ lbs 2.1 - 4.0 pounds 4.1 - 6.0 pounds 6.1 - 8.0 pounds 8.1 - 10.0 pounds Over 16 pounds Under 2 pounds
more options