Feeds

Factoring gains won't break strong crypto – Schneier

Serious number crunching

  • alert
  • submit to reddit

SANS - Survey on application security programs

Concerns that improvements in factoring technology might make it easier to break large key length encryption codes are misplaced, according to noted cryptographer Bruce Schneier.

Last year mathematician Dan Bernstein circulated a paper discussing improvements in integer factorization, using specialised parallel hardware, implying that encryption keys as long as 2048 bits can now be broken.

Schneier, inventor of the Blowfish encryption algorithm and founder of Counterpane Internet Security, believes the improvements described in Bernstein's paper are unlikely to produce the claimed speed improvements in practice.

The fastest factoring algorithm currently available is the Number Field Sieve (NFS) which works in two stages. The first phase of the process is to search for equations that satisfy certain mathematical properties. This is followed by a large matrix calculation, which eventually produces the prime factors of the target number.

Bernstein attempts to improve the efficiency of both steps, but Schneier believes the improvements are marginal for practical numbers and talk of "massive parallization" in number crunching is misleading.

For very large numbers (much bigger than would be used to deliver even a 2048 bit key), Berntein's algorithms might imply a key length three times as long needs to be used to give equivalent levels of security. But, as Bernstein himself acknowledges, it is unclear if this holds true for smaller numbers, or how practical his ideas are.

"Any practical implementation of these [Bernstein's] techniques depends heavily on complicated technological assumptions and trade-offs. Parallel computing is much easier to say than it is to do, and there are always hidden complexities," Schneier will argue in a paper to be published on Friday.

"I think when all the math is said and done these other complexities will even out his enhancements," he adds.

Despite his criticisms, Schneier credits Bernstein with undertaking useful research, which "is likely to open up new research directions in the design of more efficient sorting networks and sparse matrix algorithms". ®

External links

Bernstein's home page

High performance access to file storage

More from The Register

next story
Obama allows NSA to exploit 0-days: report
If the spooks say they need it, they get it
Samsung Galaxy S5 fingerprint scanner hacked in just 4 DAYS
Sammy's newbie cooked slower than iPhone, also costs more to build
Putin tells Snowden: Russia conducts no US-style mass surveillance
Gov't is too broke for that, Russian prez says
Snowden-inspired crypto-email service Lavaboom launches
German service pays tribute to Lavabit
Mounties always get their man: Heartbleed 'hacker', 19, CUFFED
Canadian teen accused of raiding tax computers using OpenSSL bug
One year on: diplomatic fail as Chinese APT gangs get back to work
Mandiant says past 12 months shows Beijing won't call off its hackers
Call of Duty 'fragged using OpenSSL's Heartbleed exploit'
So it begins ... or maybe not, says one analyst
prev story

Whitepapers

Top three mobile application threats
Learn about three of the top mobile application security threats facing businesses today and recommendations on how to mitigate the risk.
Combat fraud and increase customer satisfaction
Based on their experience using HP ArcSight Enterprise Security Manager for IT security operations, Finansbank moved to HP ArcSight ESM for fraud management.
The benefits of software based PBX
Why you should break free from your proprietary PBX and how to leverage your existing server hardware.
Five 3D headsets to be won!
We were so impressed by the Durovis Dive headset we’ve asked the company to give some away to Reg readers.
SANS - Survey on application security programs
In this whitepaper learn about the state of application security programs and practices of 488 surveyed respondents, and discover how mature and effective these programs are.