Math Advance Threatens Computer Security

DISCOVER ^ | 12.28.2007 | Stephen Ornes

[neverdem]

An international team of mathematicians announced in May that they had factored a 307-digit number—a record for the largest factored number and a feat that suggests Internet security may be on its last legs.

“Things are becoming less and less secure,” says Arjen Lenstra, a computer scientist at the École Polytechnique Fédérale (EPFL) in Switzerland, who organized the effort.

Messages in cyberspace are encrypted with a random 1,024-bit number generated by multiplying two large primes together. But if hackers using factorization can break the number into its prime multipliers, they can intercept the message. Factorization currently takes too long to be a serious threat, but that may soon change.

Lenstra and his colleagues chose the number (2^1,039 – 1), which weighs in at 1,017 bits—slightly less than the 1,024-bit numbers used to secure Internet messages. His team used the special number field sieve, a filtering method first suggested by John Pollard in 1988, to find the factors.

For a hacker using a single computer, the job would have required a hundred years of processing time. By sharing the load over about 500 computers, however, Lenstra and his collaborators reduced that time to six months.

Although Lenstra’s number is close in size to those used for online security, he estimates that it would be more than a thousand times as difficult to crack a random 1,024-bit number. He says it could happen in the next decade, though, in light of rapidly accelerating technology.

[js1138]

One hopes that within a decade, we can up the bit size of keys again.

[saganite]

I guess I’m missing something here but using 500 computers and cracking a code in 6 months that’s only 1/1,000 as difficult as the typical internet encrypted message doesn’t seem like a serious immediate threat. Certainly not worthy of the headline.

[hiredhand]

I’m pretty sure they’re talking about asymetric (public key) encryption. What about symetric? How about asymetric for the sole purpose of exchanging symetric keys?...then using the symetric keys for stream encryption...such as the alphabet angencies do now? :-) The only truly effective way to crack that is with somebody willing to hand over the key tapes!

[farlander]

And, of course, if we go to 2048 bit keys, that’d take well into the next millenia (unless they get those quantum computers up).

Bottom line, there is no perfect or ‘forever’ security. It’s only for ‘how long’. Usually that is something that can be made long enough. The article’s primary interest, really, is that they made some guy’s theory from 1988 work.

[JoJo Gunn]

It might take a while, but as the old saying goes, "if one man can make it, another man can break it".

[PeterFinn]

On the Tuesday after someone posts their hack for the 1,024 bit key Microsoft will send out the 2,048 bit patch. Most of our computers will then die. MS will, of course, point out that if we upgrade to Vista everything will be just dandy...for a while.

[js1138]

Actually the government is the agency that limits encryption key length.

[vbmoneyspender]

don’t most ssl sites (e.g. paypal) use 128 bit encryption and/or 256 bit encryption?

[rabscuttle385]

By sharing the load over about 500 computers, however, Lenstra and his collaborators reduced that time to six months.

Botnets are significantly larger, with 20,000 or more zombie hosts (source). That six months time span could be shortened dramatically by using a botnet...

[CarrotAndStick]

Elcomsoft turns your PC into a password cracking supercomputer (gulp)

Posted Oct 24th 2007 9:16AM by Thomas Ricker
Filed under: Misc. Gadgets

 

You know all that talk about GPUs being the new CPUs? Well it's not just a lot of hot, ventilated air. Thanks in large part to the launch of development kits like nVidia's CUDA, Russian outfit Elcomsoft has just filed for a US patent which leverages GPUs to crack passwords. Their approach harnesses the massively parallel processing capabilities of modern graphics cards to make minced-meat of corporate-strength password protection. An NTLM-hashed Microsoft Vista password, for example, can now be cracked in 3 to 5 days (instead of two months) using a simple, off-the-shelf, $150 graphics card -- less complicated passwords can take just minutes. Dial the GPU up to an $800 GeForce 8800 Ultra and Elcomsoft's approach will crack passwords at a rate some 25 times faster than existing CPU-only approaches. Yippee?

[Via NewScientist, thanks Sultan]

Read [warning: PDF]

http://www.engadget.com/2007/10/24/elcomsoft-turns-your-pc-into-a-password-cracking-supercomputer/

[guitarist]

Ha, ha. They’ll decrypt my e-mail, and gain this secret, “Sorry I couldn’t come last night. I was tired after messing with the kids all day. Shall we meet tomorrow instead for lunch?”!

[Gideon7]

Lenstra and his colleagues chose the number (2^1,039 – 1)

That is called a Mersenne number, a special class of numbers 2ⁿ-1. The mathematics for searching for Mersenne primes among these special numbers is well known. They have found primes up to n=32,582,657.

No RSA knapsack algorithm is going to use a Mersenne number as a factor in computing a totient function.

That is not to say that a fast general factorization method won't be discovered tomorrow, but this ain't it.

[neverdem]

New Route For Heredity Bypasses DNA

Egypt: 4 Women Die of Bird Flu

Judge Imposes Stricter Rules on Navy to Protect Marine Life (limits Navy use of medium-range sonar)

FReepmail me if you want on or off my health and science ping list.

[rmlew]

I gues it won’t only be gamers using Nvidia new nforce 780i chipset. Nothing like a having 3 GeForce 8800 GXT or Ultras, 8 Gigs of Ram and a Intel Core 2 Extreme QX9650 overclocked from 3 to 4GHZ. Of course this will cost at least $5000. Then again if you can break into banks...

[AmericaUnited]

Actually the government is the agency that limits encryption key length.

Hehehe... because they don't like waiting 6 months...

[Scutter]

I’m pretty sure they’re talking about asymetric (public key) encryption. What about symetric? How about asymetric for the sole purpose of exchanging symetric keys?...then using the symetric keys for stream encryption...such as the alphabet angencies do now? :-) The only truly effective way to crack that is with somebody willing to hand over the key tapes!

This is how SSL works, so it's what is done for every HTTPS connection you make with your browser. There is a validation of the server's certificates, followed by a key exchange phase using asymmetric encryption, followed by the actual SSL data connection which uses symmetric encryption. During the key exchange phase a shared secret is exchanged, which is then used as the key in the symmetric encryption. The primary reason for this is that the symmetric encryption is less computationally expensive than asymmetric.

[The Duke]

We're probably AOK until Diffie-Hellman bites the dust.

The ultimate form of encryption is the good, old-fashioned lie. :)

[LurkedLongEnough]

An international team of mathematicians announced in May

curious as to this timing - The government is more heavy-handed with controlling computer encryption than just about anything else imo.

Anyone wanting to know the background behind computer "keys" and history of government intervention should read Steven Levy's entertaining book, "Crypto: How the Code Rebels Beat the Government - Saving Privacy in the Digital Age".

[SunkenCiv]

Thanks neverdem. Also of interest:

Free Software Brings Affordability, Transparency To Mathematics
ScienceDaily | Dec. 7, 2007 | ScienceDaily and University of Washington.
Posted on 01/05/2008 12:28:08 AM EST by Ernest_at_the_Beach
http://www.freerepublic.com/focus/f-chat/1948617/posts