Factoring Breakthrough?

An anonymous reader sent in: "In this post to the Cryptography Mailing List, someone who knows more about math than I do claimed "effectively all PGP RSA keys shorter than 2k bits are insecure, and the 2kbit keys are not nearly as secure as we thought they were." Apparently Dan Bernstein of qmail fame figured out how to factor integers faster on the same cost hardware. Should we be revoking our keys and creating larger ones? Is this "the biggest news in crypto in the last decade," as the original poster claims, or only ginger-scale big?"

Comments

For the PostScript-impaired

[Hew]

Try viewing the postscript file using the online viewer here instead.

Re:For the PostScript-impaired

[rjamestaylor]

Thanks for the link. Very helpful.

Re:For the PostScript-impaired

[Anonymous Coward]

I read it, but I just don't understand it. It looks like just a bunch of exponential numbers. SHOW ME THE CODE! =) (Or at least pseudo-code)

Re:For the PostScript-impaired

[Unknown Bovine Group]

Heh. Heh. He said "rump-session".

After that I didn't understand much....

Re:For the PostScript-impaired

[killmenow]

Or view it as this PDF.

Now let's see how well RR's server can handle the /. effect. :^)

Re:For the PostScript-impaired

[Cy Guy]

Or you can (try to) view in plain text via the Google archive here. Here's the Preface:

Preface
This paper is an excerpt from a grant proposal that I submitted to NSF DMS at the beginning of October 2001.

The same techniques can be applied to other congruence-combination algorithms for factoring, discrete logarithms, class groups, etc. See [3] for a bibliography.

Priority dates. I realized on 13 September 2000 that special-purpose hardware would change the exponent in the cost of integer factorization. I announced the exponent reduction from 3 + o(1) to 2:5 + o(1) for real (two-dimensional) circuits in a seminar at Butler University on 23 March 2001, a rump-session presentation at Eurocrypt 2001 on 7 May 2001, and a talk at the Algorithms and Number Theory conference at Dagstuhl on 14 May 2001. I realized on 9 August 2001 that the sieving exponent could easily be reduced from 2:5 + o(1) to 2 + o(1).

Re:For the PostScript-impaired

[ncc74656]

Now let's see how well RR's server can handle the /. effect. :^)

It appears to be taking it better than cr.yp.to, at least. :-)

Re:For the PostScript-impaired

[flufffy]

plus, it'll avoid the /.ing of tonga ...

Re:For the PostScript-impaired

[Anonymous Coward]

...Better than the cr.yp.to one

Re:For the PostScript-impaired

[Old Wolf]

Since RR.com is the most common source (in my xperience) of DDoS attacks, I'd guess they could easily handle a slashdotting.

AES?

[NortonDC]

What's the impact of this news on the security of the newly accepted AES (DES replacement)?

Re:AES?

[Hizonner]

The Rijndael/AES cryptosystem does not depend on the difficulty of factoring. This is a big deal mostly for RSA.

Re:AES?

[chtephan]

AES and DES are symmetric ciphers

Factoring prime numbers isn't the problem here.

Re:AES?

[Anonymous Coward]

Not a problem. AES is symm key. The factoring problem affects only public key.

Re:AES?

[Ronin Developer]

None at all when considered by itself. AES (ala Rijndael) does not depend upon prime numbers. Hence, it is not subject to factoring. It is a symmetric cipher with key lengths up to 256 bits.

Where it could be susceptible, however, is during a key negotiation session (say via Diffie-Hellman Key Exchange) or a naive approach of simply encoding the session key using the recepients RSA key.

Where I would be truly frightened is in the realm of digital signatures where somebody could forge a digital signature simply by knowing the sender's public key and factoring it. With digital signatures almost as legally binding as handwritten signatures, identity theft may increase using these methods.

The resulting impact may be less acceptance of digital signatures and more reliance on antiquated methods.

RD

Re:AES?

[jdegre]

None. AES is a _simmetric_ cypher (private key known to both, sender and receiver), while integer factoring is used in _asimmetric_ cryptograhpy: each party has a private key (only known by him) and a public key. An asimmetric cypher is RSA, for instance.

Re:AES?

[warkda rrior]

RSA is an asymmetric (public key) algorithm, while AES is symmetric crypto algo. There is no point in comparing the two.

Re:AES?

[Snafoo]

AES is secure, as is DES, as is almost any other symmetric cryptographic protocol. AES, for instance, is based on Galois Fields (and associated chicanery), whereas DES is based on drop-dead simple permutations that are so elegant and inexpensive that I find it difficult to resist *not* implementing them on an 8-bit PIC (although someone else has of course beaten me to the punch!). Neither one is reducible to anything like factoring.

Many public-key algorithms, and many public-key-based authentication protocols, however, *are* reducible to factoring, even if they don't appear to involve such darkness the first time you read them.AFAIK, for public key algs the deep magic is either factoring or the knapsack problem; however, almost all of the latter kind have been proven insecure. One notable exception of the latter variety is the Diffie-Hellman (sp?) algorithm, which is incidentally also the first public-key alg ever invented, and the underlying muscle behind the NSA's DSA signature scheme (although ElGamal did some strengthening work and got to rename the bugger ;). However, don't make the switch to DH just yet -- IIRC, the ciphertext is effectively doubled in length (over RSA). So you can either make a bigger RSA, or you can make a bigger message every time you encrypt -- either way, you email just got longer :)

Re:AES?

[Anonymous Coward]

When the NIS and other security agencies stopped fussing about crypto use in the public domain, it was clear to me that they have a way to crack these factoring based algorithms...

DES is a different matter, but the security agencies have special hardware to decode that as well.

Re:AES?

[Anonymous Coward]

Rijindael/AES is a symmetric algorithm. RSA is a public key (aka asymmetric) algorithm. Different beasts, different uses.

Re:AES?

[Mark J Tilford]

Because symmetric encryption is much faster than asymmetric encryption, when public keys are used, the method generally goes like this:

1) Randomly generate a key (called the session key) for a private-key algorithm.
2) Encrypt the session key with the public key algorithm and send that.
3) Send everything else encrypted with the private key.

So increasing the size of the public key message doesn't matter much.

Re:AES?

[Anonymous Coward]

"I'm a little teapot" brought to whole new levels!

Re:AES?

[Archie Steel]

That's true, but don't most AES/DES implementations depend on public-key encryption for key exchange? IIRC, the disadvantage of symmetric key schemes is that both parties need to have the same private key. While these can be easily exchanged using public-key encryption, that part might have suddenly become the weak link in the process...

Re:AES?

[inri]

Diffie-Helman is not based on the knapsack problem (which is roughly: given a bunch of sack of various sizes (say, all of size 100) and a bunch of objects, what's the most efficient way of packing the objects into the (least number of) sacks?); DH is based on the discrete logarithm.

Note: people are interested in the knapsack problem because it is NP-complete to solve in general; the problem is that many (many!) specific cases are very easy to crack, and it's hard to tell a priori if you are generating such an example (a similar thing occurs in factor, in that there are some numbers that are much easier to factor than they may appear).

The discrete logarithm is as follow: recall that computing the logarithm (base b=10, say) of a number n is determining a number a such that 10^a=n. If you're working over the real numbers, this is easy to solve, and any calculator can do it quickly. On the other hand, suppose you are working in the integers modulo a prime p (imagine you're on a clock with p hours); then it's still possible to raise an integer b to a power a, getting a number n, and this is very quick. Say, given p=7 and b=5, and a=4, we get that 5^4 = 25*25 = 4*4 = 2 (modulo 7), so the discrete log base 5 mod 7 of 2 is 4. This is what Diffie-Helman relies on. Note that there are variants that work in different groups than this (a group is a mathematical object where you can add and subtract, roughly), particularly with elliptic curves, and these last are much touted as being possibly more secure than RSA or DH.

Re:AES?

[Anonymous Coward]

What is the name of the generic compresion algorithm that states that you take an item that has the highest occurance, and assign it a token, then take the second highest occurence and assign it a second token, so that no token, in a stream of tokems could every be confused with any other.

I.e.:

e = 0
s = 10
t = 110

Since there is no 1, 110 will not be confuse for a 1 and a 10.

Doesn't this have a name?

Re:AES?

[SpamapS]

However, don't make the switch to DH just yet -- IIRC, the ciphertext is effectively doubled in length (over RSA). So you can either make a bigger RSA, or you can make a bigger message every time you encrypt -- either way, you email just got longer :)

The public key algorithm in PGP(Not sure about S/MIME or other protocols, but it would be most logical this way) is only used to encrypt a symmetric key, that is then used to encrypt the payload(email). So using DH would only enlarge a very small portion, which is the key.

After that a symmetric algorithm like IDEA, AES, or Blowfish is used.

Re:AES?

[Anonymous Coward]

Huffman compression

Re:AES?

[Destoo]

My username has been DESTOO for various services since around 1989, when I first got a modem.
And a few years ago at univ, I was secretary of the student association there, AESSUQAM (association etudiante .

It always cracks me up to see AES and DES stuff.

Studying in physics may have been a factor.

Re:AES?

[alech]

Where it could be susceptible, however, is during a key negotiation session (say via Diffie-Hellman Key Exchange)

Don't I remember correctly that DH uses the discrete log problem rather than the factoring one?

Re:AES?

[Anonymous Coward]

This is wrong. D-H is based on public key exchange. El Gamal, adopted in a shorter exponent form for DSA (the DSS standard), is based on the problem of discrete logarithms.
Incidentally, there's a patent claim on DSS, even though it's an open standard. (Long running dispute.)

I'm surprised you find DES inexpensive. Rijndael is actually faster than DES, and much more secure (2^128 key space instead of 2^56 key space for DES). But then again, that must be some rev'd up 8 bit PIC you have there.

Re:AES?

[spinlocked]

...Diffie-Hellman (sp?) algorithm, which is incidentally also the first public-key alg ever invented...

*cough*GCHQ*cough*

Re:AES?

[matrix29]

Note: people are interested in the knapsack problem because it is NP-complete to solve in general; the problem is that many (many!) specific cases are very easy to crack, and it's hard to tell a priori if you are generating such an example (a similar thing occurs in factor, in that there are some numbers that are much easier to factor than they may appear).

Yep and some things are IMPOSSIBLE to crack.
Would you like to make your own unlimited transcendental number? You know how to do long division? Take the divisor then divide it into the number and continue until it repeats.

Okay, to get the result in any base divide exactly the same number into the other number. But instead of multiplying by 10, multiply by that base until you get a number larger than a multiple of the divisor's base (and smaller than the multiplying base). If you understand that then let us continue...

Transcendental numbers are EASY to make mathematically. This time multiply by a NON-INTEGER base (say 9.6). Go ahead, it's easy, but the decimal results increase with each decimal point. Don't worry, it will NEVER become a repeating decimal but the long division becomes increasingly difficult over standard integer base division.

Now consider using this resulting transcendental number to encrypt a string of numbers. Can you imagine anyone decrypting it without knowing the three keys (divisor, the divided number, and the non-integer base)? Elliptic curves... BLAH! I can top that in 30 seconds. That's only ONE of my bags of tricks. I also have a TURING acceptable infinite base numbering system created very simply with little extra memory indexing overhead.

Re:AES?

[Anonymous Coward]

What do you mean by "D-H is based on public key exchange?" I thought it's a method for doing so?
Like I give you y^x1, you give me y^x2, and we'll both have y^x1x2 or something?

Re:AES?

[Prothonotar]

The resulting impact may be less acceptance of digital signatures and more reliance on antiquated methods.

You mean like hand-written signatures? Yeah.. those are hard to forge...

Re:Ginger scale big?

[medicthree]

don't tell me you haven't converted your judgments of magnitude to the ginger scale. everybody's doing it.

not surprising...

[lyapunov]

Cryptography is going to be a perpetual game of "measure, counter-measure" as computing power increases and people develop more clever ways of doing things.

Does anybody have good sources about this? Ones based on historical encryption and decryption that lead into modern times would be ideal.

Re:not surprising...

[monkeydo]

You are right, and this is a major stumbling block to widespread acceptance of encryption in the civilian world. The military and other organizations with a strong need to keep secrets are used to playing these games, but corporate America just isn't. Current applications aren't flexible enough to plug-and-play cryptography, changing crypto systems often means a complete redeployment of the application, or worse yet a new application.

Imagine the conversation with the CIO when you tell him he has to throw out his 1 year old meesaging platform because some guy figured out how to factor very large numbers effeciently and your current platform doesn't support eliptical curve cryptography.

Re:not surprising...

[Plutor]

Read the book The Code Book by Simon Singh. It's a fantastic mix of technical cryptography and historical perspectives.

Re:not surprising...

[Anonymous Coward]

One of the main reason for the NON-availability
of plug-and-play solution in security was/is the
US policy for crypto stuff and export policy.

If you allow a system/software where crypto can be
upgraded just by plugging another crypto library.
Then it is dangerous because peaple could start
replace broken/back-door/weak implementation by
strong free/open version of them.

This mean it is less easy for 3 letters acronym
organisation to monitor what you do.

Just my 2 Euro cents.

Re:not surprising...

[lyapunov]

Thanks. I will check it out.

Re:not surprising...

[cduffy]

Imagine the conversation with the CIO when you tell him he has to throw out his 1 year old meesaging platform because some guy figured out how to factor very large numbers effeciently and your current platform doesn't support eliptical curve cryptography.

I can't conceive of a design so bad one would have to throw the whole thing out to change the cryptosystem -- absolutely cannot. If someone did manage to write such a poorly designed piece of software, the app would conceivably require rewriting on other grounds as well.

Re:not surprising...

[Anonymous Coward]

Aren't they used to throwing everything away once per year anyway? "Whoops, we thought MS Word was safe." "Whoops, we thought MS Outlook was safe." "Whoops, we thought MS XP was safe."

Re:not surprising...

[monkeydo]

Lotus Notes, Microsoft Exchange

Most large companies use one or the other for messaging. Both make it fairly easy to encrypt all of your traffic, but neither has good support for third party encryption. Your best hope right now would be some third party plugin on the client, but that makes it less likely to be used. It also make administration in a large environment very difficult.

We aren't just talking about changing algorithms here. If this "discovery" is all they are claiming it could very well mean that all public key crypto is insecure. Companies like Cisco, Verisign, and MS have encouraged enterprise customers to spend a lot of money on PKI as an enabling technology for everything from secure email to remote access. That may be down the drain if in fact, "Everything you know about public key cryptography is wrong."

Re:not surprising...

[Old Wolf]

Not entirely. Cryptography has a mathematical basis (unlike things like CPU speed, which has a technological basis, so is subject to Moore's Law). RSA rests squarely on the (presumed) fact that factorising a large prime number has a time complexity of O(n^3). Today's discovery doesn't change this, it just "inches" towards the best possible case of O(n^3). It would be a gigantic and revolutionary step for mathematics if even an O(n^2 log n) algorithm were found, and it is by no means inevitable.

Re:not surprising...

[tomstdenis]

This is wrong on several levels.

1. RSA's security comes from the inability to find the e'th root modulo a composite. Its *conjectured* to be as secure as factoring is hard but thats not what the security comes from. The security comes from the inability to find the decryption function from the encryption function.

2. Current factoring algorithms take via the GNFS

e^(1.923 * (ln(n)^1/3 * ln(ln(n))^2/3))

Time not n^3 time as you suggest.

Finally, the new result appears to just be a more efficient implementation of the GNFS, its not a new algorithm.

Given all that the new results certainly are worth taking a look at.

Tom

Re:not surprising...

[Anonymous Coward]

Check out "The Code Book" by Simon Singh - it's chock full of info, as well as actually showing you how to go about some of the more simple methods of cryptanalys/cryptography.

Re:not surprising...

[Anonymous Coward]

Yeah, until the hackers earn enough credits to get Decypher 4.0...

Re:not surprising...

[cduffy]

Plugins exist to add support for 3rd-party crypto to Exchange; I'd expect that if such isn't immediately possible for Notes, a sufficiently large customer could push it in quickly. Even adding some frontend hacks is a long way from having to "throw out [a] 1 year old messaging platform".

On another note... This "discovery" doesn't make all public key crypto insecure, just significantly less secure; triple your key lengths and yer fine.

Re:not surprising...

[Anonymous Coward]

Interesting history/introduction to crypto
David Kahn - The codebreakers

Re:not surprising...

[Anonymous Coward]

While you make an intriguing point, I think lack of standards and apathy probably has a little more to do with it.

it's a cool method

[Frothy Walrus]

basically what DJB has done is found ways to incorporate extra hardware to eliminate redundant operations when performing number field sieve (NFS). he's implemented NFS in a non-linear way, which results in a threefold increase in speed from linear NFS implementation.

it's a wonder no one thought of it before. oh, wait, i think a three-letter agency might have...
better update those keys!

Re:it's a cool method

[Ed Avis]

Only a threefold increase in speed? That would make hardly any difference, you'd get a threefold speed increase just by waiting a few years for Moore's law to deliver.

My understanding is that keys of three times the length can be cracked in about the same time - which is an _exponential_ increase in speed.

Re:it's a cool method

[Anonymous Coward]

Way to quote the article for points you whore.

Re:it's a cool method

[Anonymous Coward]

Not knowing much about this... Isn't three times linear still linear?

Re:it's a cool method

[Anonymous Coward]

Three times faster doesn't seem *that* much faster to me. I mean, we have heard about how many years/centuries it would take to factor these numbers so what if it only that a third of hundreds of years.

Re:it's a cool method

[Fulcrum of Evil]

which results in a threefold increase in speed from linear NFS implementation

Three times? That's what, 1.5 bits? surely there's something more to it than that.

Re:it's a cool method

[Anonymous Coward]

not three times faster.

He means, if its correct, that you can factor a number three times as big.

Since the algorithm is exponential time in the size of the number, this algorithm is exponentially faster.

Re:it's a cool method

[Anonymous Coward]

Maybe when its combined with Moore's law you'd consider it a big deal?

Re:it's a cool method

[Mr Z]

Or more correctly, the new algorithm operates in the cube-root of the time of the original. (I'm pretty sure factoring is still an exponential search problem. Would someone who knows this algo better than I comment?)

At any rate, it's not quite as impressive as if an exponential search had been made polynomial. Rather, the exponent in the exponential search's runtime has been divided by 3. (Still a very big deal.)

In terms of big-Oh, it went from O(x^N) to O(x^(N/3)).

--Joe

Re:it's a cool method

[gweihir]

In terms of big-Oh, it went from O(x^N) to O(x^(N/3)).

Exactly. That means we have to make N three times as large as we thought we had to. This is not a catastrophe, except in high-security applications. But these should use something like "make absolute sure its enough bits and then quadruple the number" anyway...

Were they even secure yesterday?

[Carmody]

The NSA factors numbers, and their work is top-secret. When I read stories like this, I wonder if people are just discovering things that the NSA has known about for years. If the NSA could factor 2 Kbit keys, would they tell people? Probably not.

So when you ask "Are our keys secure" the logical follow-up question is, "From who?"

From me? Yes. I probably couldn't factor a 1000 digit number.

From your boss? Yes. You could use rot-13 and your boss would probably be baffeled.

From your boss' lawyers? From the police? Here is where we get into the gray area; where the article becomes relevant

From the government? I think you were kidding yourself when you thought it was secure in the first place. I find it easy to believe that the NSA is far ahead of the public in the encryption arms-race.

Re:Were they even secure yesterday?

[Anonymous Coward]

You could use rot-13 and your boss would probably be baffeled.

Especially if you misspell everything!

Re:Were they even secure yesterday?

[georgeb]

Well, since important figures high up there wish so hard for control over hardware and software, maybe, at least once upon a time, crypto was secure even from the government....
Just a guess.

Re:Were they even secure yesterday?

[mlk]

Considering the past cryptos & gov. "openeness", I would guess this has been about sence it was released.

Re:Were they even secure yesterday?

[monkeydo]

From the referenced post:

Note that there have been rumors of an RSA cracker built by a
three-letter agency in custom silicon before this, but until
analyzing Bernstein's paper I had always dismissed them as
ridiculous paranoid fantasies. Now it looks like such a device
is entirely feasible and, in fact, likely.


There has always been speculation that the NSA could break RSA, but it was dissmised as paranoid by most "in the know." Most of the mathematicians didn't believe that they were that much ahead of the rest of us. Now that this technique is known it explains how the spooks may be able to break crypto everyone else believed was "unbreakable" if they had previously made this discovery.

Re:Were they even secure yesterday?

[JordoCrouse]

From the government? I think you were kidding yourself when you thought it was secure in the first place. I find it easy to believe that the NSA is far ahead of the public in the encryption arms-race.

Exactly! One of the most lucid posts I have ever seen on /. The alphabet soup agencies spend millions of dollars and hire the most brilliant minds in the world (not just the US), and their whole existance is based on the premise that they need to be able to find out what every human on earth is doing at any point in time.

I have never thought that I could put one by the government, and I have never encrypted my documents because I was worried that some spook might read it. If they want my password, credit card number or DNA bad enough, they're going to get it no matter what I do. I encrypt my data because I'm more worried about script kiddies and regular old fashioned crooks.

Re:Were they even secure yesterday?

[Syberghost]

Remember what happened with DES. The NSA said "make these changes. We can't tell you why." IBM made the changes.

20 years later, when differential cryptography was "discovered", it turned out those changes made it more resistant to differential cryptography...

Re:Were they even secure yesterday?

[Steve B]

No data security is really secure against a government focused on you -- if they can't break the crypto, they'll Trojan the machine, plant a spy camera to capture the passphrase, or squeeze the information out of you and/or your correspondents.

The realistic target is making it cost too much to target you. (Note that cost != money -- the usual government policy in that regard is "spend all you want; we'll tax more". Real costs to governments are man-hours of specially trained personnel, risk of exposure and embarassment, or risk of exposure and loss of ability to use the same trick again.)

Re:Were they even secure yesterday?

[Tackhead]

Re: your .sig

> So when you ask "Are our keys secure" the logical follow-up question is, "From who?"

Well-put. Use the amount of security you need for the threat you face.

> God is real unless declared integer

...so the doctrine of the Trinity was just the result of NSA factoring an integer God? ;)

Re:Were they even secure yesterday?

[Fulcrum of Evil]

From the government?

Forget encryption. Piss them off and they'll come after you directly.

Re:Were they even secure yesterday?

[Anonymous Coward]

Security doesn't equal encryption.
Your stuff may be easily available even if it was protected by 4096-bit keys - and taking advantage of this is where they are even better at (than in breaking the laws of physics or something).

Re:Were they even secure yesterday?

[Anonymous Coward]

Love the .sig. Stuart rules.

Re:Were they even secure yesterday?

[Anonymous Coward]

The interesting part is that they can't use their knowledge without disclosing that they can factor large numbers, unless they can silence all who are involved.

Re:Were they even secure yesterday?

[Eagle7]

Can you provide some sort of link for this? Sounds interesting...

Re:Were they even secure yesterday?

[rbeattie]

20 years later, when differential cryptography was "discovered", it turned out those changes made it more resistant to differential cryptography...

Wait, I don't understand that. Is this good or bad? Resistant meaning that you couldn't use DES for this type of new and better cryptography or the opposite that the DES was made stronger by the NSA changes... I'm confused.

-Russ

Re:Were they even secure yesterday?

[Anonymous Coward]

It shows how ahead of the "state of the art" many people beleive the NSA to be. I this case they helped us to make DES stronger since having secure bank transactions was in the public interest, but it leaves one wondering what else they can do 20 years before we can.

Re:Were they even secure yesterday?

[Skuto]

>Wait, I don't understand that. Is this good or bad?
>Resistant meaning that you couldn't use DES for this
>type of new and better cryptography or the opposite
>that the DES was made stronger by the NSA changes...
>I'm confused.

It was made stronger. Differential cryptanalysis is a technique to break ciphers. It's applicable to DES, but just barely, and is not really pratical. However, most DES variants made by people who didn't like using the NSA-modified DES could be broken very easily, because they did not know of the attack and consequently didn't defend against it.

--
GCP

Re:Were they even secure yesterday?

[Zathrus]

Ok, I'm paraphrasing stuff I previously read on /.

Which, of course, means that this is the absolute truth, so please repeat it as such.

DES has a large space of possible keys to use. At some point in time (I don't know that it was 20 years prior to the general knowledge about differential cryptography, but it was numerous years prior at lest) the NSA quietly told everyone that a certain portion of that keyspace should not be used. Ever. They didn't say why. They just said that it shouldn't be used for secure applications.

Eventually someone discovered differential crypto. It revealed that the keyspace that the NSA said not to use for DES was very, very weak and could be cracked rather trivally. The rest of the keyspace was still secure though (within the scope of the original security on DES at least).

What he's saying is that the NSA knew about this a long, long time before anyone else had figured out why. It is not unreasonable to believe that they've figured out other "magic" to make crypto either harder or easier to crack, despite claims otherwise.

The NSA exists to protect US national secrets. Crypto is their business. Knowing how to crack crypto tells you how safe your own crypto is. They have a very large, very undisclosed budget. Contrary to popular belief, not everyone in the government is incompetent. You may put together your own conclusions from there. Please wait in line for your aluminum foil beanie though.

Re:Were they even secure yesterday?

[Ralph Wiggam]

For the first time I know of, the NSA is actually the good guys in a Slashdot post.

The NSA recommended changes to DES that made it a better, less crackable, scheme. Years later, when a new type of code breaking was publicly discovered, people looked back and noticed the changes the NSA had made were directly influenced by this "new" type of code breaking. The bottom line is that the NSA is, and always has been, leaps and bounds ahead of all non-classified "state of the art" cryptography.

Could the original poster give a link? I would love to read the story.

-B

Re:Were they even secure yesterday?

[harshaw]

Hmm... I am pretty sure that the IBM researchers stated quite clearly that the NSA did not directly interfere with the DES development (in particular, the S-boxes).

Additionally, the IBM guys knew about differential cryptography but never published. If someone is really interested, they can check out one of the sources in the biography located here. I researched this issue a number of years ago and can't remember some of the details!

Re:Were they even secure yesterday?

[HiredMan]

Wait, I don't understand that. Is this good or bad? Resistant meaning that you couldn't use DES for this type of new and better cryptography or the opposite that the DES was made stronger by the NSA changes... I'm confused.

It's good - the NSA changes (S-Box design specifically) DID make DES stronger.

But if you read between the lines it means that the NSA knew about Differential Crypt _at least_ as early as the early1970s while the public didn't know about it until many years later.

We went through this "good/bad" debate on /. here as part of this thread on quantum computing.

=tkk

Re:Were they even secure yesterday?

[Suppafly]

> God is real unless declared integer

...so the doctrine of the Trinity was just the result of NSA factoring an integer God? ;)


No its an old joke that goes back to fortran where variables named a-h were reals (floats) and i-z were integers unless you specifically declared them otherwise.

Re:Were they even secure yesterday?

[broter]

I found a brief mention of it here in the Differential Cryptanalysis section. Also, in "Applied Cryptography, 2nd ed." (Schneier) on page 290, it quote IBM's Don Coppersmith as saying:

• The design took advantage of certain cryptanalytic techniques, most prominently the technique of "differential cryptanalysis," which were not known in the published literature. After discussions with NSA, it was decided that disclosure of the design consideration would reveal the technique of differential cryptanalysis, a powerful technique that can be used against many ciphers. This in turn would weaken the competitive advantage the United States enjoyed over other countries in the field of cryptography.

I've heard about it in other places, but I can't remember where at the moment.

Re:Were they even secure yesterday?

[gweihir]

Wait, I don't understand that. Is this good or bad?

It supposedly improved DES. But it also implies that the NSA might have knowen about differential cryptoanalysis 20 years before public research discoverd it. The implication is that they might know a lot of other things that are not yet knowen in the public crypto research community. On the other hand, they might only have had a hunch, or there might have been other weaknesses in the old design (they changed the s-boxes, as far as I remember), that they could find and the effect on differential cryptoanalysis is accidental.

But there is also another limiting factor: If they can break, e.g. AES or RSA far easier than the public suspects, they don't want the public to know! After all when it is knowen a cipher is insecure, people will stop using it or improce its security. This is analog to not exposing a highly placed intelligence source.

If you plan a major terrorist attack and use email for the related communication, you might have to worry. Otherwise, as long as you use cipthers that are belived to be secure for the near future by current published research, you should not need to worry.

Re:Were they even secure yesterday?

[perky]

The NSA exists to protect US national secrets.
and to perform industrial espionage on behalf of US corporations.

Re:Were they even secure yesterday?

[Anonymous Coward]

Check out Steven levy's book, "crypto" pp.37-66.

Re:Were they even secure yesterday?

[jonathan_ingram]

Here is the paper showing that DES is secure from differential cryptanalysis, but many related schemes were insecure:

Biham, Shamir - Differential Analysis of DES-Like Cryptosystems.

It contains one of my favourite passages in a crypto paper: "Cryptanalysis of GDES... The special case of q=8 and n=16, which is suggested in [16,18] as a faster and more secure alternative to DES is breakable with just six ciphertexts in a fraction of a second on a personal computer." [and that was a personal computer from 1991 :)].

Re:Were they even secure yesterday?

[baka_boy]

I think that government agencies are more interested in having the potential to know whay any single person or group is doing, rather than literally needing to know what everyone is doing, all of the time.

What worries me is the possibility that corporations could have effectively the same amount of power, with none of the public scrutiny, accountability, or mission to "protect" (at least in theory) those they watch. As you say, individuals can (and do) protect their privacy in dealings with each other, with or without the threat of government intervention. Massive corporations, OTOH, are effectively immune to any power less than the largest national governments.

Re:Were they even secure yesterday?

[Anonymous Coward]

actually... the logical follow-up question is "From whom?"

-andy (posting anonymously to spare the karma)

Re:Were they even secure yesterday?

[Liquid(TJ)]

One time last semester, I was slumming around the math building, waiting for my ride, and I read an article someone tacked to one of the boards. It was about how the US Government was by far the #1 employer of US citizens that finished advanced degrees in mathmatics. It included some quotes from some NSA math recruiter guy, essentially noting that a classified NSA paper is usually distributed to more mathmatitians than one published in a journal.

Re:Were they even secure yesterday?

[Anonymous Coward]

I have never thought that I could put one by the government, and I have never encrypted my documents because I was worried that some spook might read it. If they want my password, credit card number or DNA bad enough, they're going to get it no matter what I do.

Well, ok but another idea is to encrypt *everything* thereby increasing the workload for those doing the snooping, and making privacy more likely. If everyone implemented encryption on email it would be much harder to know what to decrypt, making something on the scale of eschelon less possible.

Re:Were they even secure yesterday?

[Anonymous Coward]

For WHOM, not for who.

Re:Were they even secure yesterday?

[jovlinger]

But on the other hand, IIRC, the NSA also "requested" that the key length be reduced from 64 to 56 bits.

The reason being that their budget could allow them to bruteforce such a key if they really wanted to, while it took until just a few years ago for that to be feasible for a well funded public entity, and until last year for this to be affordable to Joe Public (affordable = ~ US$2K for a machine to do it in about a day)

Re:Were they even secure yesterday?

[AnotherBlackHat]

The NSA factors numbers, and their work is top-secret. When I read stories like this, I wonder if people are just discovering things that the NSA has known about for years. If the NSA could factor 2 Kbit keys, would they tell people? Probably not.

The trouble with this game is that you can just as easily play it the other way. Does the NSA ever do anything besides suck money out of congress and take credit for things they never did? (Oh, the NSA has know that for years...)

This may be a significant advance in factoring, but I notice that rsa-576still hasn't been factored.
Until someone does that, I'm not going to lose any sleep over 1024 bit keys.

-- 10 bits, 3 digits, it's all the same.

Re:Were they even secure yesterday?

[Old Wolf]

Which part of the keyspace, exactly?

Are you saying that if DES keys are generated randomly, they might fall into the bad keyspace and be insecure?
Does this go for 3DES too?

Re:Were they even secure yesterday?

[zmower]

There has always been speculation that the NSA could break RSA, but it was dissmised as paranoid by most "in the know." Most of the mathematicians didn't believe that they were that much ahead of the rest of us. Now that this technique is known it explains how the spooks may be able to break crypto everyone else believed was "unbreakable" if they had previously made this discovery.

You know, this is exactly what the Germans thought about the enigma codes. I remember seeing an article in Byte ages ago about holographic computing. They were talking about using light to do massively parallel (SIMD?) computations. Never heard anything more about it...

Hmm, isn't google a wonderful tool. Now I am scared

Re:Were they even secure yesterday?

[cc_pirate]

Resistant means that differential cryptography was much less likely to break it.* In all likelyhood the reason the NSA did this was to prevent the USSR from being able to routinely crack financial transactions and play havoc with our banks and markets.

*See Applied Cryptography by Schneier.

Re:Were they even secure yesterday?

[Anonymous Coward]

So what your really saying is that, in the case of cryptography, the closed source guys are 20 years more advanced than the open source ones?

Odd that no one has mentioned this yet...

Re:Were they even secure yesterday?

[Captn Pepe]

Close, but not quite. Part of the DES algorithm includes a step in which hardcoded bit-pattern substitutions are made; the tables describing these substitutions are called S-boxes (for their appearance in a flowchart, I believe).

Anyway, the NSA discovered that the S-boxes could be used to tune the algorithm's resistance to differential cryptanalysis. In 1991, Adi Shamir et al discovered that the resistance of DES to this procedure makes it almost exactly as hard to break DES this way as by brute force, indicating that the S-boxes had been tweaked for this (improbable) result.

I'm afraid I can't find an online reference for this at the moment; you could probably search for Shamir's papers on differential cryptanalysis, and it is also summarized in Schneier's Applied Cryptography.

Re:Were they even secure yesterday?

[crawling_chaos]

And foreign agencies don't??!!

When I was contracting at a Fortune 50 ten years ago, there was a strict company policy that no company confidential information was to pass through the French public telephone network. They had it on very good authority that the French equivalent of the NSA was handing information to French companies to enable them to underbid.

Where did they get this information? I don't know, but I've always surmised that the NSA found out about it while bugging the French.

Get off your high horse. The NSA is no more evil than the spook agencies of every other country in the world. It's just better funded.

Re:Were they even secure yesterday?

[JabberWokky]

Quite a few of us love the NSA and what they do. They watch the neighbors quite nicely, and don't generally poke around in our own closets. I'm sure that there's plenty of domestic intercept done in order to get the job done, but by and large, they ignore it. They are also the badass muthaf-ers of the math and computation community. Picture Samuel Jackson and Robert De Niro with slipsticks and mainframes. I am also absolutely sure that several people in their employ read Slashdot... not for some nefarious purpose, but simply because they're into Legos and Star Wars too.

--
Evan "Geeks like us" E.

Re:Were they even secure yesterday?

[marphod]

This is not, however, a 'break' in RSA. There is neither a theoretical flaw in RSA (or other factoring-based encryption methods), nor has factoring been shown to be an P problem.

This is an increase in algorithmic speed. Its a jump on moore's law, but this is hardly unexpected.

In order for there to be a break of RSA or another factoring-based algorithm, the there needs to be a flaw shown in the algorithm, that makes solving it easier than factoring large primes, or factoring primes needs to be shown to be a low-cost non-hard problem.

Re:Were they even secure yesterday?

[cicadia]

The alphabet soup agencies spend millions of dollars and hire the most brilliant minds in the world (not just the US)

I don't know about the rest of the Three Letter Agencies, but the most important of them for this topic will only hire Americans.

From the NSA's employment FAQ,

3. Do I have to be a U.S. citizen to work at the NSA?
Yes. Only U.S. citizens are eligible for NSA Employment.

The most brilliant minds outside of the US need not apply.

Re:Were they even secure yesterday?

[Anonymous Coward]

... hasn't been factored that we know of... just because something hasn't been published doesn't mean that it hasn't happened... and the folks who are most likely to have factored it certainly would not publish the fact that they have.

Re:Were they even secure yesterday?

[Paul Crowley]

That's not quite right.

The mysterious tweak was not restricting a portion of the keyspace; it was the choice of "S-boxes". In DES, the S-boxes are a set of 8 functions that take 6-bit inputs and return 4-bit outputs. They're not specified algorithmically; the standard just says "S-box 1: 0 -> 14, 1 -> 4..." and so on: eight tables, each of which contains 64 4-bit numbers. The S-boxes are central to DES's security; the only other operations in the cipher are bit shuffles and XOR.

When DES was launched, people noticed pretty quickly that these tables had not been filled randomly; they did not pass randomness tests. But IBM (who designed DES) and the NSA (who approved it) were tight-lipped; not only about their design, but about the whole design of DES. Naturally, people suspected a back door.

When differential cryptanalysis was discovered, it was shown that the S-boxes had been specifically hardened against it, and that this was the souce of the pattern seen. Don Coppersmith of IBM had independently discovered DC, calling it the T-attack (T for "tickle"), and had worked out how to defend DES against it.

However, when Mitsuru Matsui discovered linear cryptanalysis, it was found that DES was not specifically hardened against it, and indeed the best academic attack against DES is a linear attack. Since the NSA approved DES, perhaps they did not know about linear cryptanalysis either.

Of course the real NSA back door was always the 56-bit key, and the best practical attack is still brute-force key search.

Re:Were they even secure yesterday?

[Anonymous Coward]

Don't call us, well call you :-)

I suspect the NSA has the means to hire anyone they want in any country in the world.

Re:Were they even secure yesterday?

[rho]

What worries me is the possibility that corporations could have effectively the same amount of power, with none of the public scrutiny, accountability, or mission to "protect" (at least in theory) those they watch.

What public scrutiny? Do you know what the NSA is doing? Do you thing your drunk, philandering senator knows? Or even cares?

This is a dangerous attitude--whereas a corporation could learn all about you, the worst they'll do with the information is use it to sell you more bric-a-brac, and if you discover that they're invading your privacy, you can at least sue them.

If the government is gathering this data, it can use it to take, with force, everything you own because you smoked a joint in 1963. Plus, if you find out the government is invading your privacy, you can only... well... you can only grease up your sphincter to help with the penetration. And, depending on how you find out what the government is doing, they can shoot you.

Corporations do bad things, but the worst things are done by governments, not corporations. Even the worst things done by corporations are done by the government at the corporations' behest (vis. DMCA).

Re:Were they even secure yesterday?

[Lord Ender]

The US Government has always been willing to fight for the interests of US businesses overseas. There is nothing wrong with this in princible, that's what governments do. It is even mentioned in the constitution that the government should have power to protect US merchang ships from pirates. This is protecting business interests overseas with military action, btw. In fact, the war of 1812 was mainly about protecting US business interests abroad with military force. English military ships were routinely stopping or stealing from US trade vessels. The US decided to go to war over this. What's the big deal? Protecting the interests of our businesses is in the interests of all of us.

Of course that doesn't mean everything the government has done to benifit our businesses was moral (depending on your definition), but in princible, it is the right thing to do. We can't just let whoever wants to hijack our businesses metaphorical trade vessels as soon as they leave our ports.

Re:Were they even secure yesterday?

[T3kno]

I could not agree more. What really makes me mad is that for some reason many people in the U.S. believe that corporations are inherintly evil, and the government is here to help you and is your friend.

When was the last time a corporation took away a persons right to speak, or to practice the religion of their choice? If you have a hard time answering this question go look at the situation of the people in China.

Most corporations are not evil, they're out there trying to make a buck off of you, and there is nothing wrong with that. Yeah advertising sucks, especially in it's current form, but if you ask me taxes suck a lot worse. If I dont like advertising there are things that I can do about it, turn off the T.V. and read a book for example. If I don't like taxes, or agree with where that money is going, there is really nothing I can do about it because the people in authority don't need or have to listen to me, and they have control of the laws. You can argue about lobbyists and special interest groups, but congress is slowly taking that away from us in the form of campaign finance reform.

There are also laws that protect a countries citizens from a badly behaving corporation, the laws do not work well because the corporations can buy what they need to get around them, but the principal is there. The principal is also there to protect a person from their government (I am speaking primarily about the U.S. here because that is the only experience I have. So I apologize for being U.S. centric.) in the form of the constitution, but that is slowly being eroded by the very people we elect to uphold it. To me at least there is a sort of spider web safety net that protects me from a bad corporation, and I have a choice in which ones I support, but there is no such apparent safety net when it comes to the government.

This is just my $0.02 worth, but it's the government being able to read my email that scares me a hell of a lot more than some "evil" corporation wanting to sell me the latest widget.

Re:Were they even secure yesterday?

[Anonymous Coward]

Citizenship is bestowed by the government.

Re:Were they even secure yesterday?

[dumpster_d]

I find it easy to believe that the NSA is far ahead of the public in the encryption arms-race

In 1998 Distributed net used ~100000 PCs to break a 56bit DES key.

40 years earlier, the NSA decreed that DES keys should be limited to 56 bits because they were "readily accessible".

Think about it.

need to be able to find out what every human on earth is doing at any point in time.

Except Heisenberg
!RimShot

Re:Were they even secure yesterday?

[cicadia]

True, they would just have to agree to become a US citizen first.

Allegiance to the flag, defend the constitution, fealty to the president, and all that

Re:Were they even secure yesterday?

[Goldsmith]

Yes, and becoming a US citizen when the NSA wants you to work for them would be very difficult.

It makes sense that you should be a citizen of a country (any country) if you are working for that countries "Security Agency".

Of course, a German crypto expert who wants to work in Germany won't apply to work for the US NSA, but it doesn't mean the NSA can't (or won't) try to recruit him.

Re:Were they even secure yesterday?

[drix]

On the other hand... it has been claimed that OBL et al were using good old PGP (probably version 2.6.2i) to encrypt their communications, and then sending them out over public forums and/or e-mail. Here we have an Al Qaida training manual with instructions for using PGP (unfortunately it must be fed through clumsy translator, but search the page for "PGP" and you'll get the gist.) It's well known that we were listening to Al Qaeda satellite phone conversations, spying on them with drones, etc., so I'd be more than willing to be that we were intercepting a fairly large portion of their e-mails, Usenet posts, and Yahoo! forums messages, or whatever else they were using. And I'd be more than willing to bet that said communications contained a least a few morsels about 9/11, and probably many many more.

Yet, by all accounts, this one caught the intelligence community completely by surprise. They literally had no idea that anything at all out of the ordinary was going on on September 10.

Let's get to the point: there's no way the NSA has the capacity to break strong crypto at will. Here was their golden opportunity, the situation for which the NSA was formed in the first place ... and they blew it. I suppose the paranoid could argue that passed to opportunity up for fear of showing their hand. I doubt that; that really stretches the limits of plausibility for me. Let's face it: for a large enough keysize nobody is going to be decrypting your communications who isn't supposed to be. Of course, when the FBI can implant a hardware keylogger on your PC pretty much at will, I suppose that's kind of a moot point.

Re:Were they even secure yesterday?

[xanthan]

You can become a US citizen by applying for it. All you need to do is have a green card and live in the country for five years.

Re:Were they even secure yesterday?

[acb]

Some have claimed that the NSA is 200 years ahead of the rest of the world in mathematics. Even if this is an exaggeration, it's something to think about.

Re:Were they even secure yesterday?

[Anonymous Coward]

A conservative? On slashdot? *gasp*

Re:Were they even secure yesterday?

[rjamestaylor]

This is just my $0.02 worth

And $0.0175 of that goes to the government's Free Speech Protection tax. Pay up.

Re:Were they even secure yesterday?

[JDizzy]

yup, so how do we fight against hardware key loggers? If I found one in my PC, what could I do about it? Post pictures on Slashdot, hope the goverment doesn't get mad that I stole their hardware? I duno.

Re:Were they even secure yesterday?

[gaspyy]

If someone has a "brilliant mind", don't you think he/she will be granted citizenship right away?

Re:Were they even secure yesterday?

[ediron2]

3. Do I have to be a U.S. citizen to work at the NSA?
Yes. Only U.S. citizens are eligible for NSA Employment.

So, you're bright, you're dedicated, but you were born poor and in India. One day, after yet another Algebra lecture at the community college you work at, you have a visitor:

"Hello, Mr. Gurdeep? How would you like to fast-track through all the bureaucracy, become a US citizen, get paid 25 times what you currently make, have state-of-the-art tools and a huge budget, and work with the best and brightest on encryption issues for the US Government?"

You choose:

A: "Nah, I like the crappy teaching assignments and third-world Ambiance."
B: "Thanks, but I've almost got tenure here."
or
C: "When's our flight!?"

Seriously. It freaks out the bureaucrats when they do it, but the best scientists and mathematicians have routinely held enough power to step right over the top of little niggling details like place of birth. Politics and psychology will be watched hawkishly by the 'crats involved, but they can't stop one genius demanding a benign foreign-born genius be hired. Citizenship isn't THAT hard to bestow on desirable talent.

My favorite story about the power the top researchers hold was when researchers at the Tokamak (the original big toroidal fusion device) met the new facility manager. He announced sweeping changes including a strict adherence to a 9-to-5 schedule and the elimination of 2-month-long sabbatical/vacations that were common. Understand these were both a byproduct of the Tokamak: it took half a day to start and stop, so on active days researchers were often there for 14 hours or more, and it had a couple months annually of upgrades and maintenance when nothing ran.

He finished his speech, asked if there were any questions, and one of the Nobel-caliber research heads stood up and asked him "Where will you be finding your next job?"

Re:Were they even secure yesterday?

[T3kno]

Actually no, a Libertarian. Big difference.

Re:Were they even secure yesterday?

[osolemirnix]

However, the fun starts when companies become multi-national. I find it quite amusing to watch how the FTC and it's other national counterparts struggle when they try to apply their national viewpoint logic to international mergers.

NSA liaison officer 1: Dude, so is Daimler-Chrysler still an american company now, or what? They're asking for some info on those frenchies.

NSA liaison officer 2: Aehm, dunno man. But I thought the germans are the bad guys. Oh wait no, that was back in WW2. I think now they're our friends.

Re:Were they even secure yesterday?

[Peter Harris]

Of course, you can know what Heisenberg is doing, or where he is, but not both :-)

Re:Were they even secure yesterday?

[perky]

Why don't /. add a new negative moderation - Critical of the American way or of something done in or primarily by Americans. That way you wouldn't have to mod me a troll or as flamebait when I mention that the NSA doesn' exist soley for the protection of American national security. Essentially you don't like it that America isn't loved and adored by the rest of the world and admired for the polluting, bullying, obese nation that it is. As a result you mod down rather than reply. Think about it: is the above post really a troll? Is it flame bait?

I thought the USians here might have a more enlightened opinion about their nation essentially breaking laws for the protection of US multinationals. I thought you might think it was morally dubious, especially given the amount of you that hate government interference in your own lives. But I guess that it doesn't matter if they are spying on foreigners. After all, it's their own fault for not being American.

Re:Were they even secure yesterday?

[Syberghost]

Yeah, the US is so hated and reviled. That's why we have to heavily restrict immigration every year...

If the US had unrestricted borders we'd have 3 billion people living here. The US is hated and reviled by a very vocal minority, most of whom are jealous that our television is so much cooler than theirs.

Re:Were they even secure yesterday?

[Bartmoss]

And you don't think they could naturalize a foreigner if they wanted to hire them?

Re:Were they even secure yesterday?

[Syberghost]

Hmm... I am pretty sure that the IBM researchers stated quite clearly that the NSA did not directly interfere with the DES development (in particular, the S-boxes).

Yep, at the time, they sure did.

Then later some of them admitted they were lying, including Dan Coopersmith.

Re:Were they even secure yesterday?

[Anonymous Coward]

It's hard to believe that people so smart that the NSA would like to hire, will stay poor for all there life and wait for NSA to make there life comfortable.

In fact I think that no smart guy (Non US Citizen) would want to work for the NSA, against his home country, it's more likely to stay where he is and help make the world better there.

After all what can NSA really offer except money?

Re:Were they even secure yesterday?

[cperciva]

This may be a significant advance in factoring, but I notice that rsa-576 still hasn't been factored.

That's not security; that's apathy. RSA-576 is quite factorable right now, as soon as anyone gets around to it. The largest cause for it still standing unfactored is that GNFS requires rather more background knowledge than something like cracking DES.

If either RSA-576 or RSA-640 are both still standing three years from now I'll be very surprised; I'd be surprised if even RSA-704 is unfactored three years from now.

Re:Were they even secure yesterday?

[Anonymous Coward]

RSA is offering $10,000, if you think it's so easy to factor, factor it and collect.

Re:Were they even secure yesterday?

[rjamestaylor]

Actually no[t a conservative], a Libertarian. Big difference.

Yep. A conservative is beholden to an ideal while a Libertarian is beholden to a party. BTW, have you noticed that the Libertarian philosophy is little known among the masses, but it seems every knows about the Libertarian party -- the Party that knows how to party...the other Greens (Drop Kemp, Vote Hemp!), etc... It's a shame that an entire political philosopgy has been reduced to a single off-beat issue.

Conservatives are mainly associated with the Republican Party these days, but historically there have been conservatives in both (and I mean "both" as inclusive of all the major parties in the US) parties. Great conservative thinkers and icons include well-known names such as Winston Churchill, William F. Buckley, Jr., and Ronald Reagan. But can a person on the street name a great Libertarian thinker? They should be able to name Thomas Jefferson, but, unfortunately, the message of Libertarianism has been limited to a stand on legalizing drugs and TJ doesn't spring to mind when discussing getting high (and if he does, you're too far gone to help :^).

The Libertarian Party is in great need of a libertarian thinker to promote libertarian ideals among the populace -- and to distance the movement from single-issue-itis.

Re:Were they even secure yesterday?

[Zygo]

In my country we get 340+ TV channels (minimum) from a number of competing cable & satellite providers.

_Not one_ of these channels is the Sci-Fi Channel.

Damn the US!

Re:Were they even secure yesterday?

[v1z]

While NSA is one of (if not the) worlds biggest employer of mathematicans, one should not forget MI5 completly. After all they discovered RSA long before R, S and A did, and they kept it secret until AFTER most of the people discovering it was dead -- even though the algorithm becomae publicly know with (or soon following) the anouncement of RSA.

But would you tell?

[Anonymous Coward]

It's always been my dream to figure out how to factor big, big numbers. But I always pondered, if I did figure it out, would I tell? ie, How many companies/gov'ts would kill for that exclusive info?

Re:But would you tell?

[alkali]

It's always been my dream to figure out how to factor big, big numbers. But I always pondered, if I did figure it out, would I tell? ie, How many companies/gov'ts would kill for that exclusive info?

This is the premise for what could be the most boring thriller ever sold at an airport newsstand.

Re:But would you tell?

[Anonymous Coward]

You mean like the movie Sneakers?

Whew - I'm safe

[Dolph]

I use a 4096-bit GPG key. It may take a day to encrypt a message, but at least the encryption can't be broken (yet).

Re:Whew - I'm safe

[Hieronymus Howard]

can't be broken (yet).

Not until we get quantum computers, that will break it almost instantly :-)

Re:Whew - I'm safe

[Anonymous Coward]

You are just kidding yourself. There are many ways to get info, *without* the bother of breaking the encryption and RSA never was secure. The fact that the government allows it is sufficient proof of its insecurity...

Re:Whew - I'm safe

[Tackhead]

> I use a 4096-bit GPG key. It may take a day to encrypt a message, but at least the encryption can't be broken (yet).

Ah, but what of the Great Unwashed, who figured "PGP? Too complicated! I can't be bothered! They'll just decrypt it anyways."

If this math turns out to be real, the Great Unwashed was right for anyone with less than a 4096-bit key ;-)

Re:Whew - I'm safe

[Anonymous Coward]

...which is probably sitting on your computer, encrypted with RSA. It has at least some impact on you.

Re:Whew - I'm safe

[Jonny Ringo]

Yeah,

I just have a super long passphrase. its

supercalifragilisticeexpalidosious

or somthing like that.

HTML Version of Paper

[BigBadAssMonkey]

http://cr.yp.to/papers.html

Re:HTML Version of Paper

[Cy Guy]

Handy link for those who can't handle the PS files, but unfortunately its just as Slashdotted as the PS version.

Here's a link to a very unformatted plain text version thanks to Google's archive which one can assume will suffer only minimally under the SlashDote effect.

Re:HTML Version of Paper

[Anonymous Coward]

This mod is proof that moderators don't read the stories.

Re:HTML Version of Paper

[Anonymous Coward]

Since when is a web page of DVI and PS files considered an HTML "version" of a paper?

Mod the parent down.

Re:My stupidity is reaching new heights.

[Anonymous Coward]

Overruled, I'll allow it.

No wonder NSA was okay with 128 bit encryption.

[bigpat]

I think that given that the NSA has allowed stronger encryption to be exported supports the idea that "they" have much more powerful algorithms than "they" have let on.

Re:No wonder NSA was okay with 128 bit encryption.

[fremen]

Using 128 bits is fine for symmetric key algorithms like IDEAS and Blowfish. It's not ok for public/private key algorithms like RSA. You're comparing Apples to Oranges.

Re:No wonder NSA was okay with 128 bit encryption.

[Anonymous Coward]

Comparing apples and oranges. 128 is a symmetric key length, where every bit in the key is (potentially) a bit of entropy in the key space. 2048 bit keys are public keys, where not every number less than 2^2048 can be used as a key.

Re:No wonder NSA was okay with 128 bit encryption.

[Anonymous Coward]

> Using 128 bits is fine

Right now, maybe. Not if you want your secrets to remain safe in the future. This is why AES can use key sizes of 128, 196, or 256 bits. Obviously, these are still much shorter than required for public-key algorithms.

Re:No wonder NSA was okay with 128 bit encryption.

[Anonymous Coward]

> not every number less than 2^2048 can be used as a key.

This is not the reason for the longer key length. There are /lots and lots/ of numbers with 2 prime factors in this range. The reason is that you never have to brute-force the key, you only have to factor the modulus.

OMFG

[Anonymous Coward]

this is indeed astonishing. I too thought the rumors of the big RSA cracker at the NSA was a rumor. I guess it's not. This is huge. it not only makes pgp's current implementations useless, but it also makes decrypting all that "secure" RSA-based ssl and ssh traffic eminently readable (probably not realtime though, it probably took a day to break all that traffic the nsa logs for you)

the tinfoil hat set is going to go nuts.

/me changes everything to blowfish and aes

'scuse me, must run, out of tinfoil!

Re:OMFG

[mindstrm]

This is about a threefold increase in factoring speed.. not an order of magnitude.

The NSA can afford huge hardware.. REALLY huge hardware, for breaking crypto... was there ever any doubt?

Re:OMFG

[Anonymous Coward]

Who cares? If you're really that paranoid that the NSA cares what you are encrypting then perhaps it SHOULD be broken. You're probably a criminal or international terrorist or something. Frankly, if the NSA wants to spend their computer and human resources on decyphering my porn collection, go right ahead. In fact, I'll stick it on a CD and send it to them unencrypted if they prefer.

Re:OMFG

[Anonymous Coward]

No, this is NOT a threefold increase in factoring speed. This is a threefold decrease in bit strength.

Suppose I have a 1024-bit key. The new algorithm makes it essentially take the same time to break as a 341-bit key using the old algorithm.

Since each bit makes it take twice as long, this means that the new algorithm is 2^683 times faster at cracking the code. This is a bit different than 3 times...

Re:OMFG

[archen]

I think some people miss this point. With specially designed dedicated hardware, I'm sure the NSA can break encryption much faster than the threefold increase this yeilds...

Re:OMFG

[Hieronymus Howard]

Even if the NSA has *really* big hardware, even 1024 bits is a serious challenge. About 5 years ago, it was estimated that with current hardware, 1024 bits could not be cracked before heat-death of the Sun occurs. Even with today's hardware and (perhaps) improved factoring algorithms, it's still a pretty big challenge. The NSA is only going to devote serious computing power to very, very few things (e.g. terrorism).

Unless they've already got quantum computers. IBM's best effort so far is cracking a 4 bit(!) number using quantum, but expect huge budgets to be devoted to quantum factorising now.

HH

Re:OMFG

[egomaniac]

No, it isn't. RTFA.

For very large keys, where the definition of "very large" is not yet known, this is a 3x decrease in the (for lack of a better term) 'effective key length'.

In other words, it might be possible to crack a 1536 bit key in the amount of time it currently takes to crack a 512 bit key.

Since the 1536 bit key is 1024 bits longer, that means that it *should* take 2^1024 (1.79e308) times as long to crack.

So, for that specific example, assuming that this works it's actually cracking the key 179 million trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion trillion times faster.

Sounds like a few orders of magnitude to me.

Re:OMFG

[Anonymous Coward]

On one CD? Small collection.

Re:OMFG

[FreeUser]

This is about a threefold increase in factoring speed.. not an order of magnitude.

No. This is wrong. Read the paper.

For large keys, this method reduces the difficulty of factoring keys by a factor of ~3.009, i.e. the diffuclty of factoring a 90,000 byte key is now comparable to factoring a 30,0000 byte key using traditional methods.

It is unknown if this applies to smaller keys currently in widespread use, i.e. if your 2048 key will now have a factorization cost equivelent to that of a 683 byte key using traditional methods. That is what they guy wants funding for ... to find out.

So yes, this makes cracking keys orders of magnitude easier and faster.

Re:OMFG

[Guignol]

No. It's a threefold increase in crackable key-size.
If you could crack a 10 digits key, it will now cost you the same to carck a 30 digits one.
So, as the cost does grow exponentially with the key size, it is correct to talk of "order of magnitude".
Read well: *cost*.
If I understood well the article (ok, I probabily didn't), then it's not such a big deal (I think).
You are not cracking any faster than before. it is not an improvement so that now everybody is going to crack easily huge keys.
It's about making special purpose hardware in order to crack something more eficiently.
For instance, in the article it presents a wonderful sort algorithm that sorts N values in N "steps". Cool :) but you have to see what are the steps. on a regular computer, each of those steps costs you N caculations. so this is an O(N^2) algorhitm for you and me. By redefining the "unit of caculation" or "step" (which isn't just an ugly trick, it is meaningful with special purpose hardware) you can transform this very bad algorhithm into a very good O(N) one.
But the article is even less interesting than that (on my point of view) because it doesn't come with such a trick for factorizing integers. instead, it comes with an observation on overall cost. (which you and me generaly translate as time, but not everybody else)
The thing is, not only do you need O(f(N)) time to compute, with f *nasty* :) but you also need O(g(N)) memory, with g similarily nasty. the cost involves the computing time but also the hardware itself. If you find a way to make the algorithm parrallel, you divide it in 10 computers, so it will be 10 times faster, but 10 times as expensive and the cost is the same.
In this article, he proposes a different special purpose circuit that will allow you to have a somewhat less nasty g, so the O(g(N)) cost will be much more affordable. In the end, it will cost you the same for keys now with 3 times more digits.
That's nice and all, but I'm sure it would be much more significant on general purpose hardware, even if not so wonderful at first sight, because something that is not considered in the article is 'real life cost of hardware'.
I mean, spcecific hardware, because of its specificity if of course much more expensive than general purpose hardware. There is also the availability problem, so in the end I don't find it a so interesting achievment.
It would be much more effective if for instance, you could easily maximize parrallelism with aceptable latency, so that you could build an Internet wide cracker, that would be much cheaper (I think).

Re:OMFG

[-brazil-]

Wrong, a bit of key lenght does NOT equal doubling the cracking time for RSA, since factoring (with or without the new algorithm) has a much lower complexity than the brute force "try all possible keys" that is necessary with symmetric ciphers.

Re:OMFG

[Anonymous Coward]

No, this is NOT a threefold increase in factoring speed. This is a threefold decrease in bit strength.

Suppose I have a 1024-bit key. The new algorithm makes it essentially take the same time to break as a 341-bit key using the old algorithm.

Since each bit makes it take twice as long, this means that the new algorithm is 2^683 times faster at cracking the code. This is a bit different than 3 times...

That's not quite correct either. The algorithm isn't "three times better" than the worst-possible algorithm, it's "three times better" than the current best algorithm [1].

Say you have an n-bit key k. Even a very simple algorithm can factor it in O(2^(n/2)) = O(k/2) time (around k/2 steps), since to factor a number k you only need to check values in the range 1..sqrt(k). A slightly more complicated algorithm that's still based on simple number theory takes O(2^(n/4)) = O(k/4) time (around k/4 steps). This is a substantial speedup, as you say: for instance on a 1024-bit key instead of taking ~2^512 steps it will only take ~2^256, a speedup of 2^256.

The fastest factoring algorithm is faster still. I'm not sure just how fast (I do remember the expression isn't quite so pretty as these), but say it's O(2^(n/8)) = O(k/8). This means for a 1024-bit key we could be talking about ~2^128 steps. The "new" algorithm is "3 times better", meaning it's O(2^(n/24)) = O(k/24) [1]. Now we're talking about ~2^50 steps. This is a sizable speedup, but only about 2^80. (Note that 2^80 is still one trillion trillion, but is a far cry from 2^683.)

[1] But remember, the author only claims that the algorithm is faster for large values of n. It could be "three times better" when n=1,000,000 but be the same speed or slower than current algorithms when n=1024.

Too many secrets...

[KodaK]

Circut for integer factorization?

Reminds me of a certain movie...

Re:Too many secrets...

[Xandu]

Didn't you know that Dan Bernstein now works for some toy company......PlayTronics, I think.

Hmm....

[Greyfox]

I wonder how long the NSA has know about this. I'm betting a decade...

I haven't hit a top limit on the GPG key yet. I had an obnoxiously long 4096 bit one I was testing with for a while and PGP was able to encrypt messages to it but was unable to import the private key. Oh well, time to move to an obnoxiously obnoxious 8096 bit one.

Suddenly the 128 bit netscape encryption isn't looking so good (Not that it was before...)

Re:Hmm....

[Clay Mitchell]

obviously PGP keys are bloatware. down with PGP!

Re:Hmm....

[jkujawa]

The 128 bits Netscape uses are for a symetric key. It takes considerably less bits for a symetric key to be secure, than an asymetric key. (I forget the equivalency, but ISTR that 128 bits symetric is roughly equivalent of 2048 bits asymetric.)
And the symetric keys netscape uses don't depend on factoring primes to be secure ...
Although the key exchange that netscape uses to send the session key probably does.

Re:Hmm....

[RussGarrett]

The upper limit of PGP 7 is 4096 currently, which is currently looking quite insecure...

Re:Hmm....

[LordKronos]

Suddenly the 128 bit netscape encryption isn't looking so good (Not that it was before...)

Actually, you are comparing 2 different types of keys: public assymmetric keys, and private symmetric keys. Public assymmetric keys (like the ones talked about here) require a longer key for equal security (when compared to private keys) because some additional information is already known (the public part of the key). This information can be used to break the encryption faster, thus you use larger keys to offset this.

When using 128-bit SSL on a web site, you actually use a 128-bit RC4 key (which is a symmetric private key). In order to exchange the key between client and server, a secure channel is first created using 1024-bit RSA (public) key.

So yes, the 1024 bit part isnt as secure as what this artice talks about (2048-bit keys), but the 128-bit SSL key isnt quite as bad as it sounds.

Re:Hmm....

[Hieronymus Howard]

The 128 bit DES key is then encrypted using RSA (I think). Not sure how many bits the RSA key is.

HH

Re:Hmm....

[Hieronymus Howard]

You don't need more than ~700 bits for personal use. Cracking 1024 bits is reckoned to take millions of years with current hardware. No-one is going to devote that amount of computer power to cracking your messages (unless you happen to be Bin Laden).

And if the NSA do have quantum computers that can crack 1024 bits in a fraction of a second, then don't feel safe even with 8192.

HH

Re:Hmm....

[Anonymous Coward]

128 bit symmetric encryption for dummies course:

Breaking it requires n*2^128 operations where n>1.
This is: For a cluster of billion mainframes with billion processors each breaking 100 billion keys per second it would take at about 30 years to crack.

that's quite a bit even for nanotech.

Re:Hmm....

[yomahz]

The 128 bits Netscape uses are for a symetric key. It takes considerably less bits for a symetric key to be secure, than an asymetric key. (I forget the equivalency, but ISTR that 128 bits symetric is roughly equivalent of 2048 bits asymetric.)


This is a bit dated but there is a section on the key length equivelants between symetrical and asymetrical methods.

http://www.interhack.net/people/cmcurtin/snake-oil -faq.html#SECTION00043000000000000000

Re:Hmm....

[shimmin]

I wonder how long the NSA has know about this. I'm betting a decade...

Perhaps, but the time lapse between the NSA knowing something and its publication in open press is less than it used to be, based on the two data points we have from the last decade.

First, the case of SHA-0. NSA / NIST published SHA in 1993, and replaced it thanks to a then-undisclosed weakness in 1995. In 1998, open-press cryptographers announced a break against it. It appears that in attacks against MD4-family hash functions, the public is less than 5 years behind the TLA's.

Also in 1998, impossible differential cryptanalysis hit the open press, and this form of analysis proved effective against 31-round Skipjack. (The version published by the NSA has 32 rounds.) It seems absurd to believe the NSA would release a cipher that they knew to be only one round more than a vulnerable one, and honestly, the most likely explanation is that impossible differential analysis was not known to the NSA.

Of course, one might counter that the TLA's do such things deliberately in order to appear less advanced than they are. However, both these breaks occurred in NSA products designed for public consumption -- that is, with the intent that government agencies using non-classified information and corporations would actually use them to protect sensitive data. And protection of such data against foreign and industrial espionage definitely is part of "national security." It would be foolishness to promote a cipher you knew to be broken under the assumption that no one else would figure it out simply becuase

you never know when the public might figure out your techniques

you never know if intelligence organizations in other nations have already figured out your techniques

you want to maintain a public image of competence

Re:Hmm....

[Old Wolf]

During the SSL handshake, the server and client say which keysizes they want to support, and it then uses the most secure one available. Usually it turns out to be 512bit or 1024bit. I think Verisign will not even issue SSL certificates for higher than 1024bit RSA.

Re:Hmm....

[sludg-o]

And the symetric keys netscape uses don't depend on factoring primes
to be secure ...

Good, because here's a script I wrote that factors any prime number in constant time:

#/usr/local/bin/perl5 -w

print "Please enter a prime number";

chomp($prime = <STDIN>) ;

print "The factors of $prime are $prime and 1";

exit(0);

Of course, you really DO need to input a prime for it to work.

Re:Hmm....

[nusuth]

It works great with non-primes too. The list is accurate, yet not complete. At least it is open source; I'm sure somebody will improve it.

Re:Hmm....

[Big Diluth]

And for snail mail, you don't need to actually seal the the envelope more than halfway for personal use. Cracking the seal is reckoned to take the strength of a small child. No-one is going to devote that amount of strength to realing your personal mail (unless you happen to be Bin Laden).

And if the NSA do have tea kettles that can steam them open in a fraction of a second, then don't feel safe even with scotch tape.

Funny, it sounds different when your statements are rephrased.

Sometimes just using the Honor System isn't enough.

Re:Hmm....

[Anonymous Coward]

No one who can crack said 128 bit encryption gives a shit about your credit card number.

Re:Hmm....

[vil]

This is it! The breakthrough we've all been waiting for!

There was a quote in Bill Gates' book, The Road Ahead, which went something like:

"One of the next big advances in computer science will be the discovery of a fast way to factor large prime numbers."

You've done it, and it's such a simple elegant solution... :-)

Just wait...

[JohnBE]

Shouldn't we all hang on until crypto experts validate this? Is it theoretical? How much does the attack cost? etc. etc.

I wouldn't start sending those revocation certificates just yet.

Re:Just wait...

[EddydaSquige]

I guess it depends on who your trying to protect your stuff from. If this approch does have a high cost and your interest is just in keeping you boss, girlfriend, or random h@K3rZ from getting in. Then your probably pretty safe where you are now. On the other hand, maybe your the uber-paranoid type, the NSA has the resources to put this system into use, in which they have rendered your keys unsafe.

Re:Just wait...

[nomadic]

Crypto experts? Don't you realize the average slashdot poster is an expert on all technical and mathematical subjects, no matter how esoteric? Come on, get with the program...

Re:Just wait...

[TheAwfulTruth]

And miss foaming at the mouth at the earliest oppourtunity? Hardly! :) But yeah, like Mr. infinate compression in Fl. Prove it or shut up. In fact I wish these people would actually construct a working model before opening thei mouths. Would save us all a lot of time.

Re:Just wait...

[JohnBE]

Oh gosh, I'm sorry, I didn't realise that ;-). I'll have to ask them for a combined hang-glider skateboard I've been thinking about for some time...

Re:Just wait...

[JohnBE]

Another point I'd like to raise is that major international companies are as well funded as government and maybe have as much influence. If a big international were to intercept and decode a rivals mail it could give them an advantage (or even customers mail, if the customer's info is of enough value). The other point is that as equipment becomes cheaper and faster the attack will be within reach of so many more people.

Re:Just wait...

[GSV NegotiableEthics]

If you're relying on crypto for normal purposes, don't get worried because even Dan Bernstein doesn't know if cracking your private key is feasible, yet.

If you're really worried that someone could crack your crypto and do great harm, you should probably switch to a more secure form, such as one-time pad if this is practicable in your environment. The main attractions of public key crypto are the ease of use and the readily available implementations. It isn't the only game in town.

Re:Just wait...

[Anonymous Coward]

DJB *is* a crypto expert.

Re:Just wait...

[JohnBE]

That may be the case, but peer review is very important in these matters.

Re:Just wait...

[JohnBE]

It also depends on the context of the messages transmitted, troop movements are good when they are moving, but not as helpfull to your troops when the information is old. [Not to say that the message structure isn't helpfull] So how long the attack takes is also very important (in some circumstances, not as important in others)

One-time pads are feasible but difficult to manage and of course have other limitations. Although they have been the mainstay of numbers stations etc. for the last 40 years.

Re:Just wait...

[Xerithane]

The difference is Bernstein supplies the math. By that logic, Einstein should have never released the theory of relativity, because he couldn't prove it at the time.. Good idea!

Re:Just wait...

[Anonymous Coward]

One-time pads are feasible but difficult to manage and of course have other limitations. Although they have been the mainstay of numbers stations etc. for the last 40 years.

Yes, it's all down to how much you can trust your first line of communication. It helps if your runners know they are more expendable than the information they carry. <g>

Re:Just wait...

[anonymous_wombat]

You could use a one-time pad for encryption/decryption, but not for digital signatures, which is probably more important, because the useful lifetime of a digital signature is much longer than that of an encrypted piece of information sent over the net.

Re:Just wait...

[GSV NegotiableEthics]

It depends how significant the signature is. Any legal investigation would take probably into account the current knowledge of decryption software and hardware. Either way, if it's important enough, you can consider making bipartisan manuscript endorsements of electronic signatures--witness one another's signatures.

Re:Just wait...

[Anonymous Coward]

DJB is a crypto expert. More accurately he is a number theory expert, but nevertheless...

Re:Just wait...

[JohnBE]

I am aware of this, but I am still skeptical of both the ramifications and overall meaning to users. Untill this has been put to extensive peer review and other cryptographers have vented their spleens I cannot be sure of the consequences.

Known about for years

[wiredog]

I read somewhere that the RSA public key algorithm was invented at GCHQ, and kept secret, years before RSA invented it.

Re:Known about for years

[gowen]

Correct, it was invented in 1973 by Ellis, Cocks and Williamson at GCHQ.

Re:Known about for years

[disappear]

Not exactly. They developed the _idea_ of public key cryptography, but couldn't figure out quite how to do it.

Re:Known about for years

[Jon Chatow]

From what I can remeber of the reporting at the time this was 'uncovered', (i.e. under the 30 year rule of the FOIA it was de-classified), the people who came up with the idea were ordered to stop playing around with such off-topic ideas and get back to 'serious' work (presumably breaking the Russian's latest code, or whatever).ICBR, though.

Re:Known about for years

[mindriot]

From what I read in Simon Singh's "Code Book" (which I really recommend), James Ellis and Clifford Cocks discovered the math that permitted RSA-like cryptography, but did not yet have the computing power for a practically working system. Malcolm Williamson contributed by discovering the key exchange mechanism that Whitfield Diffie and Martin Hellman discovered at about the same time.

Since they worked for the British Government Communications Headquarters (GCHQ), they were confined into silence about their achievements.

You can expect that organisations such as the NSA are far ahead from the public when it comes to cryptography and things like factoring, for they too will obviously rather die than reveal their discoveries to the public. That's why I am not really surprised about 2048-bit keys being insecure. Heck, if public science is on its way to developing usable quantum computers, who says the NSA isn't yet cracking RSA keys with a far more advanced one?

OT: Your sig

[rjamestaylor]

God is real unless declared an integer.

Orthodox Christians believe God is irrational (triune: an irrational number meaning 3 yet 1, 1 yet 3). Got Faith?

Re:OT: Your sig

[namespan]

Orthodox Christians believe God is irrational (triune: an irrational number meaning 3 yet 1, 1 yet 3). Got Faith?

Or God could be complex.... (part real, part imaginary!).

1+3i?
3+1i?

Or perhaps, some complex number which under different norms yields 3 and 1....

:)

Re:OT: Your sig

[Anonymous Coward]

Actually, it should be 1 + 2i. Only one of the Three in the Trinity was human.

Or somethinglikethat.

Re:OT: Your sig

[TheGreenLantern]

No no, God is in the square root of the second time dimension. The proof is here.

Re:OT: Your sig

[rjamestaylor]

As one can readily tell, I'm no mathmatician (heck, I'm barely an arithmatician!)...Yes, I majored in Informtion System to avoid the math requirements in the CS program...

Re:OT: Your sig

[Reikk]

If God were all powerful, could he create a stone that he was not strong enough to break?

Re:OT: Your sig

[rjamestaylor]

If God were all powerful, could he create a stone that he was not strong enough to break?

Yes, but he'd probably try to break it over your head...

Re:OT: Your sig

[Anonymous Coward]

You might as well ask god to make a four-sided triangle. It doesn't make sense.

Re:OT: Your sig

[trayl]

We live in a place were there is a rule equivalent to - you cannot make something do thing and !thing simultaneously.

Maybe God applied that rule. Maybe he could remove it to demonstrate. It might be a little confusing though. I'd rather he didn't.

Re:OT: Your sig

[Anonymous Coward]

>>you cannot make something do thing and !thing simultaneously.

Schrodinger's cat will be happy to hear the news. (Unless it's dead, of course)

Really Unique Crypto

[SGDarkKnight]

I saw an article once (not sure if it was here or not) about someone using random pictures from a lava lamp to encrypt whatever he wanted. Last i heard was everyone that tried to break the encryption failed... the only way to decode it was to use the orignal picture that was taken of the lave lamp. If anyone else has heard about this or has any other information if this worked or not I would love to hear about it.

Re:Really Unique Crypto

[J'raxis]

Isnt this just a creative variation on the one-time pad technique?

Re:Really Unique Crypto

[Anonymous Coward]

I remeber hearing about this. Apparantly it didnt work, because the reason we think lava lamps are cool is that the movement of the bubbles isn't random.
Now if you could take random pictures of the lamps
it would be, but I think they were getting the randomness from the lamps not the sampling.

Re:Really Unique Crypto

[Lukey Boy]

Actually that was a university experiment (MIT maybe?) on actual random number generation. The images from the lava lamp were used as the random number seed, since apparently the lamp is the easiest way to observe "true" randomness.

Silicon Graphics took this farther and made a sellable package of this called lavarand. Check out this article for more.

Re:Really Unique Crypto

[Anonymous Coward]

That was probably a vernam cipher applied to the sgi lava lamp output. It's a provably secure technique. But you have an enormous key problem with the lamp's output. It's secure, but not practical.

Re:Really Unique Crypto

[arkanes]

The photos of the lamp are just a clever way of generating random keys (often the hard part of a crypto system), it has nothing to do with the crpyto algorithm itself.

Re:Really Unique Crypto

[SGDarkKnight]

But now could you increase the randomness by simply getting a larger lave lamp with more bubbles?

Re:Really Unique Crypto

[Eccles]

Isn't this just a creative variation on the one-time pad technique?

And all of these, really, are just techniques that split up the message, and then assume the decrypters can only get one part. So essentially you could do this with any encryption algorithm, just send part by the internet, and part by carrier pigeon, attack stoat, etc.

Re:Really Unique Crypto

[2Bits]

Well, of course, if the picture is unique, this is the one-time-pad encryption. In order to decrypt, you have to use the same picture (i.e. the same key).

One-time-pad is so-far the most secure, but it is not very practical in daily use. And make sure you don't use the same key more than once, otherwise, it falls into the same weakness as other encryption.

Re:Really Unique Crypto

[kippy]

i've never heard of this but this doesn't sound all that unique when you think of it.

The picture of the lava is just a key. if he used it as a one-time-pad or the middle 256 bits as a Blowfish key, it's just as secure as any other key. The lava lamp is a "random" number generator.

in fact, i'd question its security if it's a one-time pad. there's probably a lot of regularity to be seen from one picture to the next.

Re:Really Unique Crypto

[SpaceLifeForm]

I can't find the lavalamp page at sgi anymore, probably due to budget restraints.
Another interesting random number generator is Hotbits.

Re:Really Unique Crypto

[Anonymous Coward]

"in fact, i'd question its security if it's a one-time pad. there's probably a lot of regularity to be seen from one picture to the next."

Which is why the commercial approach uses six of them (different colours) and takes a shot of all six. The camera adds noise as well. Then a hash of the resulting image is used to generate the resulting random number.

Re:Really Unique Crypto

[puck13]

Sounds like the old LavaRand program at SGI. These days the project has almost been moved to http://www.lavarnd.org

IIRC, they had an array of lava lamps which they took digital images of every 30 seconds or so, and then ran through some form of diff. Turns out the diffs were pretty random, or near enough to seed a good random generator.

Cheers, Noah

Re:Really Unique Crypto

[yomahz]

Well, of course, if the picture is unique, this is the one-time-pad encryption. In order to decrypt, you have to use the same picture (i.e. the same key).

One-time-pad is so-far the most secure, but it is not very practical in daily use. And make sure you don't use the same key more than once, otherwise, it falls into the same weakness as other encryption.


More info on OTP's:

http://www.interhack.net/people/cmcurtin/snake-oil -faq.html#SECTION00057000000000000000

Re:Really Unique Crypto

[yomahz]

I saw an article once (not sure if it was here or not) about someone using random pictures from a lava lamp to encrypt whatever he wanted. Last i heard was everyone that tried to break the encryption failed... the only way to decode it was to use the orignal picture that was taken of the lave lamp. If anyone else has heard about this or has any other information if this worked or not I would love to hear about it.


You're in big trouble when the light blows out though ;)

Re:Really Unique Crypto

[hornet@ch]

As many have pointed out, it is just a nice random number generator. There are other ways (for example you can use radioactive materials and take the time steps between relase of various radiation).

The One-Time-Pad is information-theoretically proved as a safe method (the proof is even easy :) ), that is without the key, the encrypted text does not give you any information about the real text. For example, with a bitmap of the lava lamp, you can use the single bits as a key, and with a simple xor-operation you encode/decode the text...

There *must* of course be a safe method to transmit the key (and right now quantum cryptography is giving us some nice methods to do that)

But the One-Time-Pad isn't new at all ... and still about factoring: oh well, there's already a nice algorithm to compute Eluer's phi function in polynomial time (and this would break RSA ..), we just a need a quantum computer to use it ... (see: Schor's Algorithm)

Re:Really Unique Crypto

[Anonymous Coward]

THere was an Economist article about this a few years ago. Apparently they took pictures of the lava lamps with a digital camera (early model) to further the randomness of the image (taking the camera's register of light, etc. into the image)

Re:Really Unique Crypto

[Jon Chatow]

Umm, yes. Actually, there was a great big huge flaw in this - the lamps had harmonics at 60Hx (well, duh), and apparently the random genereation was based on the change in the picture at a particular point and another a time after it... Oh well, never mind, back to the this-mainframe-has-a-cosmic-ray-detector ideas...

Re:Really Unique Crypto

[Anonymous Coward]

Hmmm..I always use the brownian motion from a nice cup of warm tea. (Apparently tea substitute will work too.)

Doesn't affect AES

[Cadre]

There is no impact. AES is a symmetric system that is not based on factoring. This apparent discovery only affects algorithms that are based on the difficulty factoring large numbers.

PGP with 2048 bit RSA keys

[Anonymous Coward]

The PGP version the article mentions that had
larger keys (at the expense of compatibility)
was PGP 6.x-CKT (Cyber Knights Templar). AFAIK
they stopped development on their branch a good
while ago, maybe google can dig something up.

To quote another:

[PureFiction]

"Holy shit. The math works. Bernstein has found ways using additional hardware to eliminate redundancies and inefficiencies which appear in any linear implementation of the Number Field Sieve. We just never noticed that they were inefficiencies an redundancies because we kept thinking in terms of linear implementations. This is probably the bigest news in crypto in the last decade."

Yeah, this is big news. It also sheds new light on the relaxation of the export constraints. The NSA has dedicated hardware performing this same procesing, and probably for the last 5-10 years...

"Note that there have been rumors of an RSA cracker built by a three-letter agency in custom silicon before this, but until analyzing Bernstein's paper I had always dismissed as ridiculous paranoid fantasies. Now it looks like such a device is entirely feasible and, in fa ct very likely."

Time to make new keys...

Go Dan!!!

[Anonymous Coward]

This is cool news. Glad to see discoveries like these published instead of hushed up.

So more hardware = linear improvement?

[mmca]

So is this saying that x number of linear-algebra circuits will factor a large number x times faster?

So how much hardware are we talking about to factor a 2k bit key in a day? week? month? year?

Someone w/ the math break this down for us.

-M
0xF824782C the finger print for my (soon to be obsolete?) key.

NSA, et. al.

[jacobcaz]

I find it funny and interesting that because the NSA and other TLA agengies are *so* tight lipped we assume their skills and abilities are far ahead of current "joe-sixpack" tech.

I suppose this very well could be the case, but it sure lends itself to great conspiracy theories.

I suppose the TLA agengies don't really need strong crypto to invade on my privacy. They just need a court order.

Sure I use a 2048bit key (soon to be 4096bit I guess), but will that really stop them from making me give up the goods if faced with jail when they come asking for my data?

Nope, because I have nothing really to hide. Maybe I keep my cache of pr0n encrypted so my fiancee doesn't discover it, but I will sure-as-shooting give that information up to keep me out of jail.

I'm to pretty for jail!

Re:NSA, et. al.

[Anonymous Coward]

Simple... you have the right against self incrimination. They can't throw you in jail because you refuse to give them information which could lead to your own incrimination.

Re:NSA, et. al.

[dvdeug]

I suppose the TLA agengies don't really need strong crypto to invade on my privacy. They just need a court order.

It's interesting. The TLA agencies which most likely can crack large encryption (NSA, CIA) have no authority to get a court order - they have no authority within the US. Also, it seems unlikely they'd reveal that they have this advanced technology for a mere murder trial or the like - more important to keep it hidden from their foreign enemies.

will that really stop them from making me give up the goods if faced with jail when they come asking for my data?

The US can't force you to give up your encryption keys - it would be a violation of your 5th amendment rights to keep silent, or at least your 1st amendment rights. Unless it was evidence to be used to convict someone else, then they could subpoena it.

Re:NSA, et. al.

[Strange Ranger]

"(NSA, CIA) have no authority to get a court order

They no longer need it if you are suspected of any "terrorist activities". whatever that means.

"The US can't force you to give up your encryption keys "

See above and see Patriot Act and Homeland Security Act. They can force you if its for the good of the state, oops, I mean if its for the "security" of the state.

Re:NSA, et. al.

[Anonymous Coward]

Nothing to hide?

What's your REAL name (and why aren't you using it on /.? And why don't you list your email address? And why do I get the feeling that's not your real website listed?)? Where do you live? Phone number?

Good. Now I want:

• Your credit card #'s.
• All of them.

• Checking acct number and PIN for the ATM.

Further, I want to know about all the women you screwed back in college -- you know, the ones you didn't tell your wife/gf about...

Say, where do your kids go? I'll bet they would go for a good price on the black market as sex slaves or labor slaves in a foreign country (like China).

Still have nothing to hide? I didn't think so. You're like all the other lying, hypocritical anti-privacy people I've ever met...

Re:NSA, et. al.

[Tackhead]

> I find it funny and interesting that because the NSA and other TLA agengies are *so* tight lipped we assume their skills and abilities are far ahead of current "joe-sixpack" tech.

For the past 50 years, that's been the case.

> I suppose this very well could be the case, but it sure lends itself to great conspiracy theories.

For the past 50 years, that's also been the case ;-)

Most of us older /.ers grew up believing that the mods to the S-boxes in DES were probably backdoors. Turns out they were to secure the algorithm against differential cryptanalysis, which didn't get discovered outside of NSA until recently.

NSA is still reputed to be the largest employer of mathematicians on the planet. They're reputed to have more supercomputing power than any organization on the planet. Both allegations are reasonably well-substantiated.

> I suppose the TLA agencies don't really need strong crypto to invade on my privacy. They just need a court order.

Correct. NSA's got two missions - secure American computing and communications, and 0wn every one else's ;-)

Not only is it easier to get a court order to make you give up your keys (or to eavesdrop/keylog you while you enter them), it's a hell of a lot safer.

The funniest part of Cryptonomicon is where the Brits are busy sending bombers to "see" German shipping but not bomb it. (If they just bombed the Germans, the Germans would realize that their crypto had been broken.) One of the protagonist's jobs, as an information theorist, was to figure out just how often they could get away with "just bombing them" and how often they had to make it look like they "got lucky" with a chance overflight or other observation.

The hardest part of crypto isn't breaking your opponent's codes, nor is it securing your own secrets. It's securing the big secret, namely not acting in a way that proves you've broken your opponent's codes.

Knowing your enemy's "A" team plans to attack tomorrow at dawn is good, but if you take out the "A" team 5 minutes before dawn, you run the risk of losing your ability to monitor the "B" team.

Re:NSA, et. al.

[MadHobbit]

I tend to subscribe to the theory that with any fairly well-known encryption standard, with a relatively large key size, the encryption is -not- going to be the weakest link in your security. If it takes a month instead of forty years to decrypt my data (yes, I made those numbers up), and that's using specialized hardware, I don't consider it a problem. I think anyone seriously interested in my data would be better off using key logging, packet sniffing of my unencrypted stuff, physically stealing or modifying my computer, installing a hidden video camera in my basement, tapping my phone, or any number of other options.

It's still not gonna help your local h4x0r steal your credit card number when you buy somthing online. And if some shadowy agency wants my data, breaking my encryption isn't necessarily the easiest way to do it.

"Weak" encyrption (like, according to this guy, 1k PGP) is going to keep my data out of the hands of anyone that doesn't really, -really- want it. And if I lived in fear of the type of group that has the hardware to pull it off, I'd be worried about more things than just data integrity.

Maybe I'd need to buy a tinfoil hat :-)

Re:NSA, et. al.

[Anonymous Coward]

For now. Isn't it the case in Britain that you can be legally required to divulge keys, or that there are motions to make it so? Isn't it also the case that in many countries the fear is not jail, but torture or death?

Re:NSA, et. al.

[Anonymous Coward]

making me give up the goods if faced with jail when they come asking for my data

They can't put you in jail for not giving them a password. Not that they'd want to. They will just get a judge to sign off on a covert search warrant, and next time you and your fiance go out to dinner, they'll pay your computer a little visit. Do you open up your computer and look around every time you're away from it? I know I don't. That little black box just told them what your encryption keys are.

Re:NSA, et. al.

[hornet@ch]

Ok, guys, let's suppose NSA can crack big RSA keys, then they would have:

1. proved the P = NP, and break keys in a decent time, or
2. managed to build a quantum computer, or
3. found a big mistake in the whole mathematical logic theory, so that most of the proofs in complexity theory are somehow wrong, or
4. let a linux cluster crack rsa and in the meanwhile acclerated the whole universe to the speed of light, and let it come back ...

Please guys, trust open research!!! A mathematical proof stays the same for everyone!

Re:NSA, et. al.

[richmultijoy]

If I remember correctly, you can be jailed for failing to provide the keys/ password if the police suspect that you may have encrypted something illegal. And don't think that forgetting the password is a defence! It's been law for a while now-
Thanks Jack 'I'm a Nazi' Straw

Re:NSA, et. al.

[Anonymous Coward]

If the NSA or the CIA want any of this information, why would they go through the trouble of breaking your keys?

Wouldn't they just use good old fashioned espionage methods.

Also, do you keep a list of people you had sex with encrypted on your hard drive?
Why?
If you ever read it, isn't it stored in memory unencrypted? Oops, hope no one knows how to access that...

Re:NSA, et. al.

[skybird0]

Factoring has never been shown to be NP.

Re:NSA, et. al.

[xenotrope]

The funniest part of Cryptonomicon is where the Brits are busy sending bombers to "see" German shipping but not bomb it. (If they just bombed the Germans, the Germans would realize that their crypto had been broken.) One of the protagonist's jobs, as an information theorist, was to figure out just how often they could get away with "just bombing them" and how often they had to make it look like they "got lucky" with a chance overflight or other observation.

I like the part where they send soldiers to spend a couple weeks at a remote listening post in German territory with the intent of making it appear as though they've been there for over a year. The soldiers don't quite understand why they're being ordered to scatter a year's worth of empty bottles and cigarette butts around the camp, and why the radioman is in such a high-visibility location, but it's all part of the ploy to keep the Germans ignorant of how else the Allies could get vital information.

I think various government organizations do the exact same thing. There's no way I can believe these directors whine about how terrible their budgets are, and how they can't keep up with overseas intelligence. For all we know, there's an enormous amount of theatrics involved in interviews and reports like those. I feel as contradicted as the soldiers in the book: if my government can't keep up with their intelligence needs, I'm discomforted. If they're just lying to me because they don't feel like letting me know the best crypto I can throw at them is like a child's plaything, well, I suppose I'd better start wearing a tinfoil hat and writing crazed, rambling letters to the OpenBSD team telling them to "quit p_ssying around with security and start making it *really* good." You know. Before the aliens take me home.

Re:NSA, et. al.

[Happy go Lucky]

The US can't force you to give up your encryption keys - it would be a violation of your 5th amendment rights to keep silent, or at least your 1st amendment rights. Unless it was evidence to be used to convict someone else, then they could subpoena it.

Wrong.

The Fifth Amendment prohibition on compelled self-incrimination applies only to statements to police. It does not apply to non-testimonial evidence.

For example, you get stopped while driving. The officer develops probable cause to believe that you're drunk. He can legally force you to take a chemical test for alcohol/drugs. If you refuse, then the judge will tell the jury that you refused to surrender evidence in your possession, and that they can draw their own conclusions about what it means.

And I'm not sure what the First Amendment has to do with this anyway.

Re:NSA, et. al.

[Liquid(TJ)]

The fact is, the NSA and others DO have more advanced, classified mathmatical stuff than us. But just saying they're (for example) ten years ahead doesn't really mean anything. If Joe Civie Mathguy finds a specificneet new algorithm, who's to say if Suzie Spook Mathchick found it before or not?

The fun stuff is application. Since according to the official line none of this is being used against US citizens (except "terrorists" and other enemies). And if they do use it against you, and find out you're not a terrorist after all but you happen to be the East Coast's biggest Disney DVD pirate, then in theory they're supposed to ignore you.

But is that how it happens? How "controlled" are these agencies? How much control do they have over themselves (will my high school buddy Agent Smith crack my GF's email as a personal favor to me)?

Answer: I have no idea. Don't worry to much or you'll have a stroke.

But was it a natural stroke, or did "they" slip you a pill????

Re:NSA, et. al.

[Jon Chatow]

Indeed - the RIPA (Regulation of Investigatory Powers Act) of 2000 has sections under which one can be imprisoned on failing to 'hand over' keys to the authorities on request; the burden of proof of lack of ability to hand over said keys lies with the defendent; to quote:

53
(1) A person to whom a section 49 notice has been given is guilty of an offence if he knowingly fails, in accordance with the notice, to make the disclosure required by virtue of the giving of the notice.
(2) In proceedings against any person for an offence under this section, if it is shown that that person was in possession of a key to any protected information at any time before the time of the giving of the section 49 notice, that person shall be taken for the purposes of those proceedings to have continued to be in possession of that key at all subsequent times, unless it is shown that the key was not in his possession after the giving of the notice and before the time by which he was required to disclose it.[emphasis mine]

The act also makes it an offence to give notice that one has been given notice to divulge a key.

However, it should be noted that although this act came in to force in 2000, the code of conduct has yet to be released by the HO (presumably because they're having difficulty working out when to release it so as to best avoid a fuss in the media; maybe they should consider hiring Jo Moore), so no-one will have been prosecuted under this act yet (assumedly).

Oh, BTW, IANAL and all that #include stddsclmr etc...

Re:NSA, et. al.

[Cadrys]

Isn't it a true story that Churchill had to decide whether to protect Coventry from a heavy bombing raid, or keep it secret that we had broken ENIGMA?

(According to the story, he chose to keep the secret...and wept when visiting Coventry after the raid)

Re:NSA, et. al.

[Espresso_Boy]

Protagonist? that's the character from snow crash, not cryptonomicon.

Re:NSA, et. al.

[Tackhead]

> Protagonist? that's the character from snow crash, not cryptonomicon.

(+5, Funny). I now have to clean coffee off my monitor ;-)

Quamtum Computing

[mrd98]

Once they get a real quantum coputer working (if the NSA hasn't got one tucked away already) most of the encryption schemes known today will be able to be broken in less than a second - big factors are no match for quantum.

Re:Quamtum Computing

[Anonymous Coward]

While it's true quantum computing can (and eventually will) make all curent encryption algorithms obsolete, there is another much more promising aspect to quantum computing.

Qubits have randomness inherent within themselves which is why Quantum computers are so damn hard to build. But for the cryptographer, this randomness is the literal *Holy Grail* of cryptography -- the one time pad.

By using a stream of qubits passing through filters to detect the spin of the bit two people can establish a TRULY RANDOM one time pad. Better yet, the instability of the qubits also makes it mathematically impossible for a third party to eavsedrop without affecting the transmission stream? The checks in the alhorithm verify this. Simon Singh's book "The Code Breakers" analyizes the algorithm in sufficient detail.

So don't worry about the advent of quantum computers. Relish in the thought they bring truly secure communications along with their ability to make obselete all current forms of cryptography.

In short -- technological progress as usual. Film at 11.

Re:Quamtum Computing

[dngrmouse]

With quantum computing, it's only public-key cryptography which falls apart. The AES system, which is a block cipher scheme, would still work fine - provided the number of possible keys are squared.
Quantum computing has a squareroot effect. So, if it takes some computer time T to break AES, it'll take the quantum computer sqrt(T) time.
So all we have to do is increase our key lengths.
For example, to get security comparable to 128-bit security today, we'd have to increase the key length from 128-bit to 256-bit.

Re:Quamtum Computing

[SIGFPE]

That square root thing is only for the most naive type of search using Grover's algorithm. It doesn't apply to many other kinds of searches. For example integer factorisation is much faster that sqrt time using Shor's algorithm. It may be there's also a sub-sqrt time algorithm for AES if someone actually looks for it - and AFAIK nobody has.

Re:Quamtum Computing

[astroboscope]

Cryptography is not in danger, it's public key exchange.

How can you sign anything with quantum computing? The only way I can think of is to transmit a shared secret over the secure channel, but this is much more inconvienient than a "web of trust" or certificate system. Far too many laypeople think that encryption is only for terrorists and other people who keep secrets (everyone, but they forget that) because they don't know about signing. I hope I'm wrong.

Wait for verification?

[mattvd]

I don't mean to say that this isn't true, but doesn't something like this come up every few months? Some one thinks they broke some highly respected crypto system, then an expert shows that it is invalid or only valid for a small percentage of keys.

Re:Wait for verification?

[Anonymous Coward]

Except that DJB is one of those experts.

Don't Panic

[SiliconEntity]

I am a co-author of RFC 2440, the OpenPGP standard. It's important to put this result into perspective. Dan Bernstein is the first to say that it is too early to tell whether his design for a factoring machine would be practical for keys of the size in commmon use today. See for example this recent Usenet posting, where he says,

Protecting against the http://cr.yp.to/papers.html#nfscircuit speedup means switching from n-bit keys to f(n)-bit keys. I'd like to emphasize that, at this point, very little is known about the function f. It's clear that f(n) is approximately (3.009...)n for _very large_ sizes n, but I don't know whether f(n) is larger than n for _useful_ sizes n.

Bernstein's paper is excerpted from a grant proposal where he is requesting funds to answer the question of whether the design is applicable to useful key sizes. At this point it is far too early to assume that 1024 to 2048 bit keys can be attacked by his proposed machine more efficiently than with known methods.

Re:Don't Panic

[Anonymous Coward]

So, this could just prove to add a law of diminishing return to key sizes.

Re:Don't Panic

[eXtro]

It'd add a law of diminishing returns to key size in the short term, in the long term it'd bound how long encryption based on factoring large numbers would be viable. As computer speeds increase it takes a longer key length to maintain the same security you had yesterday, if lengthining the key increases security slowly with respect to how fast speeds increase then RSA and company become flawed.

Re:Don't Panic

[Anonymous Coward]

Don't panic???
Don't panic???
At this point it is far too early to assume that 1024 to 2048 bit keys can be attacked by his proposed machine more efficiently than with known methods.
Yeah, but what about those of us still clunking along at, oh I don't know 128 bits...?
Last I checked, PGP didn't default to 1024 bits! Maybe we should go for 5,000 bit keys. Or 50,000. Hell, I'll just append a 2 MB sig to each email. (That's not the public key: that's the fingerprint.)

Re:Don't Panic

[remande]

Would this allow a machine built ten years from today to crack keys of today's size? If so, this will become a risk for those who use crypto to store sensitive information for long periods of time.

Re:Don't Panic

[osgeek]

It seems like betting on long-term strength of a particular type of cryptography is about as useful as predicting the imminent demise of Moore's law.

AES impact? NONE!

[Anonymous Coward]

The paper talks about constructing a computer optimized for factoring large numbers. Part of the RSA public key is the product of two large prime numbers. If you can factor that, you can get the private key, and then do whatever.

AES is a symmetric key algorithm -- the same key is used for both encrypting and decrypting. Factoring numbers has nothing to do with any part of the algorithm, so this has no impact at all.

That said, most of the stuff encrypted these days with AES uses a public key algorithm to send along the AES key. If the public key is broken, then out pops the AES key and the message is cracked. So, just because you're using AES doesn't mean you are safe. You have to ask if there is any public key key exchange, and if so, what it is. El-gamal, DSA, Diffie-Hellman are OK, RSA is just weaker than we thought it was.

SSH Implications????

[Temkin]

Anyone care to guess what the implications for SSH key exchange is?

Temkin

Re:SSH Implications????

[Skapare]

Depends. Are you already using an 8k bit key?

Math

[Anonymous Coward]

I checked the math.
Everything appears correct.
However, the application of discrete calculus on page 4 is a bit strange --- I'm not too sure that Euler's theorem could be applied like that.

--BW

1.5 bits lost?

[nagora]

If this new method speeds the calculation by a factor of three, and each extra bit in the keys doubles the amount of time needed then surely this "breakthough" amounts to everyone losing less than 1.5 bits of security, doen't it?

The poster seems to think speeding the calculation by 3x means reducing the strength of 300bits to that of 100bits. I know this is plain wrong but I'm not sure of the correct value.

TWW

Re:1.5 bits lost?

[Anonymous Coward]

Ah, but the new method doesn't speed the calculation by a factor of three (if it did, you would be quite correct).

Rather, it effectively reduces the bit strength by a factor of a bit more than three for large keys. The author is not sure if the factor of three holds for the size of keys currently in use.

Sources sources sources

[Anonymous Coward]

I love how one persons perception of a paper is suddenly a news worthy event. Espically a usenet post. Creating dedicated hardware to do anything isn't really a big deal. ASIC designs (custom ICs) can be created by anyone with a little VLSI know how, in fact students can make their own ASIC chips in 2months for about $3k. The fact that someone figured out that, hey, I can implement this directly in hardware and optimize it a bit, isn't anything new. Up until about 2 years ago everyone made their own ASICs to get their 4x-400x speed increase with custom memory, caching schemes, etc.. Having a working prototype might be interesting. But, just saying you've got the basic idea down is really laughable.

Reward

[suso]

Is he going to pay someone $5000 if they can prove him wrong? (qmail joke)

Re:Reward

[Anonymous Coward]

I don't get it

What about Image Base and Static Encrypts?

[Anonymous Coward]

I was under the impression that you could theoretically build an infinite number of quantum computers and that they could never break a random sample static encrypted data stream.

And random image encryption should be pretty much the same story.

How does this effect PGP?

Re:What about Image Base and Static Encrypts?

[anonymous_wombat]

The biggest problem with quantum computers is pressing the little tiny keys.

Post script viewers...

[Spatch3]

You could view this post script file online here, or you could use the Windows, OS/2 or Linux viewers available here.

Re:A word about Dan.

[Disoculated]

Because he's gay we should question his math? That's not relevant at all. And learn to spell. Sorry, couldn't help that. Guess that wasn't relevant either.

Re:Really Unique Crypto = one-time pad?

[Anonymous Coward]

That would basicly be like a one time pad would'nt it? It's my understanding that one-time pads are secure, but the problem is in the distribution of the key.

Speaking as a computing DPhil...

[cperciva]

This isn't really a big deal, nor is it surprising.

Basically, what DJB has done is translated the GNFS from its normal implementation on serial computers (where there is a great deal of available memory, but only one operation is performed at once) into a parallel implementation, where the number of processors more closely matches the available memory.

The "decreased cost" is misleading here, since it is calculated on the assumption that sieving would have been done by a single processor with access to a huge memory... this quite simply was never the case.

There is nothing here to suggest that factoring can be performed using any fewer FLOPS; all that is demonstrated is that by using several processors, each with a smaller memory, you can do better than with a single processor and a giant memory. Which we already knew.

To summarize: DON'T PANIC!

Re:Speaking as a computing DPhil...

[Anonymous Coward]

D Phil in da blanks?

Re:Speaking as a computing DPhil...

[Anonymous Coward]

I've usually dismissed the disturbingly slow growing GNFS curve in crypto books as "not yet reality". Well, this means just that now it is. That's life, time to go to elliptic curves.

Re:Speaking as a computing DPhil...

[The Pim]

The "decreased cost" is misleading here, since it is calculated on the assumption that sieving would have been done by a single processor with access to a huge memory... this quite simply was never the case.

There is nothing here to suggest that factoring can be performed using any fewer FLOPS; all that is demonstrated is that by using several processors, each with a smaller memory, you can do better than with a single processor and a giant memory. Which we already knew.

Hold on. A parallel implementation would normally just give an N times speedup. But the Berstein method (reportedly) does much better than that: it reduces the base of the exponential complexity by about a third (in the asymptotic case). This is far more significant than "merely" parallelizing the algorithm.

Re:Speaking as a computing DPhil...

[Alsee]

To summarize: DON'T PANIC!

If you are trying to protect your data from organizations that can throw of hundreds of thousands of $ at custom hardware, then "Bzzzt! Wrong answer!".

The analysis is based on keylength per $ of hardware. It theoretically triples the keylength you can attack per $ spent. He's not talking about simply throwing more CPU's in your typical box.

Example with random figures:
Old method: $1,000,000 + 1 day break 1000 bit key

New method: Custom hardware is more expensive, buy "smaller" machine that lose 100 bits cracking ability, but new method triples the attackable length: $1,000,000 + 1 day break 2700 bit key.

The only question is where does the cost-benefit ratio kick in? Is it at 500 bit keys? 1,000 bit keys? or 5,000 bit keys?

Government security angencies have custom codebreaking hardware. We just need someone outside the government to figure out and announce the price tag. Then we'll know what's currently breakable. Shouldn't take long.

P.S.
His anaylsis was related to one (important) catagory of encryption. He also notes that it will work against other catagories of encryption, and prossible even more effectively.

-

Re:Speaking as a computing DPhil...

[Anonymous Coward]

I thought the method was old news. Just that you couldn't use it in massively parallel machines.

Re:Speaking as a computing DPhil...

[cperciva]

Hold on. A parallel implementation would normally just give an N times speedup.

Only for a fixed amount of parallelism. DJB is supposing that as the problem gets larger he is increasing the number of FPUs at the same rate as the amount of memory. Which is eminently reasonable, and hardly new.

Re:Speaking as a computing DPhil...

[cperciva]

The analysis is based on keylength per $ of hardware. It theoretically triples the keylength you can attack per $ spent.

It triples the keylength at the same cost, compared to a serial machine with a huge address space. But nobody was ever considering loading down a Pentium 4 with a few petabytes of memory; instead, people would stick a few gigabytes of memory on each of 10^6 Pentium 4 processors.

All DJB has done is reinvent the idea of scaling processors at the same time as scaling memory when attacking large problems.

Government security angencies have custom codebreaking hardware. We just need someone outside the government to figure out and announce the price tag. Then we'll know what's currently breakable.

If you use an RSA modulus smaller than 768 bits, I will laugh at you. If you use an RSA modulus smaller than 1280 bits, the Russian mafia will laugh at you. If you use an RSA modulus smaller than 1536 bits, the NSA will laugh at you.

Above those points, you're safe, because even if memory were free the cost of the necessary FPUs would be too high.

Re:Speaking as a computing DPhil...

[The Pim]

DJB is supposing that as the problem gets larger he is increasing the number of FPUs at the same rate as the amount of memory.

Ok, I read as much as I could of the paper now (was slashdotted). I understand the simple examples: The idea is that, if your memory grows as N, then you can grow your number of processors as N "for free". But a factor of N, or any polynomial, doesn't help you with problems of exponential complexity, right? (I assume the memory required grows polynomially in these algorithms. Am I wrong?) So there much be some other trick I didn't grasp.

Re:Speaking as a computing DPhil...

[cperciva]

I assume the memory required grows polynomially in these algorithms. Am I wrong?

Yes, you are wrong. The memory traditionally "necessary" grows with the same O( exp(c (ln n)^(1/3) (ln ln n)^(2/3)) ) rate as everything else (except with a different constant c).

Re:Speaking as a computing DPhil...

[The Pim]

Thanks. Now that I get the basic idea, you're right that it's not so exceptional (though neat).

Re:Speaking as a computing DPhil...

[Alsee]

cost of the necessary FPUs would be too high.

To repeat myself:
"He's not talking about simply throwing more CPU's in your typical box."

As a matter of fact, I don't think it even uses an FPU at all. No floating point math.

I read the paper, and actually understood some of it. One of the things the custom hardware is doing is sorting data in linear time. X data items sorted in X clock tics.

You want to attack a key 10 times longer? Slap 10 more chips on the end and still sort in linear time.

I think some of the improvements he suggests can improve cracking speed on a generic single processor desktop box.

He is talking about algorithmic improvements. Changing the order O() of an algorithm can swamp out the effect of more or faster processors.

-

Re:Speaking as a computing DPhil...

[D. J. Bernstein]

Let's look at this ``Pentium 4 processor'' with ``a few gigabytes of memory.'' We've spent a thousand dollars on that hardware. We can use it to sort a billion 32-bit integers in a matter of minutes, a few hundred billion clock cycles. That's high-speed computation, right?

Wrong. Schimmler's algorithm sorts a billion numbers on a 32768x32768 mesh in only a few hundred thousand parallel compare-exchange steps between adjacent numbers.

Of course, compare-exchange circuitry is more expensive than traditional memory, and a compare-exchange step could be slower than a Pentium-4 clock cycle. But these factors grow only logarithmically with the problem size. Meanwhile, there's a cycles/steps ratio of one million, and that grows as a power of the problem size, roughly the square root.

My paper explains how mesh circuits provide a similar speedup for the linear algebra in the number field sieve, and an even larger speedup for the sieving. (Identifying the asymptotic cost exponent is, obviously, much easier than working out the exact costs for particular input sizes; I simply don't know yet whether the new algorithm will be cost-effective for, say, 1536-bit factorizations.)

Contrary to the comments from Mr. Computing DPhil, this mesh-circuit parallelization is completely different from the standard parallelization of sieving, in which a billion independent billion-number problems are run on a bunch of separate machines. In particular:

• The switch from standard computers to mesh circuits reduces the cost exponent. The standard parallelization does not reduce the cost at all.
• The processors inside a mesh circuit are constantly talking to each other. The processors in the standard parallelization are practically silent.
• The switch from standard computers to mesh circuits drastically reduces the amount of memory per processor and the cost per processor. The standard parallelization does not.

I have no idea how Mr. Computing DPhil arrived at the idea of putting vastly more memory than necessary into a single-processor computer: for example, using a million gigabytes of memory to sort a billion numbers. He is incorrect in claiming that such silly computers are the base for comparison in my paper.

Re:Speaking as a computing DPhil...

[cperciva]

I have no idea how Mr. Computing DPhil arrived at the idea of putting vastly more memory than necessary into a single-processor computer: for example, using a million gigabytes of memory to sort a billion numbers. He is incorrect in claiming that such silly computers are the base for comparison in my paper.

I never suggested that you were comparing against a machine with excessive amounts of memory; I suggested that you were comparing against a single processor which addressed the same amount of memory as would normally be distributed among thousands. In the case of "using a million gigabytes of memory", that was in order to sort a million gigabytes of data; by splitting the petabyte of memory into a million pieces and attaching a cpu to each, one speeds up the sorting by a factor of a million.

Perhaps my argument could best be summarized as this: You're saving memory, but you're not saving MIPS. This technique of yours may make machines cheaper to build because you need less memory per processor, but you still need just as many processors (in fact, slightly more, the way you've described it).

You still need just as many floating-point operations, and the cost of those floating-point operations is enough to put anything beyond 1536 bits out of reach of the NSA for now.

Re:Speaking as a computing DPhil...

[D. J. Bernstein]

When Schimmler's algorithm splits a huge sorting problem across one million processors, each processor of one millionth the size, it gains a factor of roughly one thousand in speed, without much increase in hardware cost.

Mr. Computing DPhil now claims that the factor is actually one million (and that everyone knows this already). In fact, such algorithms are not only unknown, but also guaranteed not to exist, by the Brent-Kung area-time theorem.

What's important is communication cost. You can see this even for a small number of processors. Exercise: If you have 16 processors, each with a billion numbers, how do you sort all 16 billion numbers? Each processor can easily sort its own numbers, but how do you merge the 16 lists?

Re:Speaking as a computing DPhil...

[cperciva]

Each processor can easily sort its own numbers, but how do you merge the 16 lists?

Using a parallel merge-exchange, perhaps?

Seriously, I've always avoided non-oblivious algorithms as much as possible; I'll admit that you can play games to reduce the communication and memory costs; but even without any memory or communication costs, you still have to pay for your FLOPs.

Re:Speaking as a computing DPhil...

[D. J. Bernstein]

Merge-exchange is a hypercube algorithm. Every embedding of a size-n hybercube into real three-dimensional space has wires of average length at least proportional to n^(1/3+o(1)), and time proportional to n^(1/3+o(1)) for signals to traverse the wires, so the cost exponent is 5/3+o(1). In contrast, a three-dimensional mesh achieves a cost exponent of 4/3+o(1).

Mr. Computing DPhil's claim of an exponent of 1 (``by splitting the petabyte of memory into a million pieces and attaching a cpu to each, one speeds up the sorting by a factor of a million'') is simply wrong.

Of course, even 4/3+o(1) is overly optimistic, because tightly packed three-dimensional machines have all sorts of nasty heat-dissipation problems. My paper focuses on two-dimensional circuits, such as FPGAs. The exponent 3/2+o(1) for Schimmler's algorithm on an easy-to-build two-dimensional mesh is still better than the exponent 5/3+o(1) for merge-exchange on a hard-to-build three-dimensional hypercube.

The bottom line is that traditional computers, such as Mr. Computing DPhil's network of Pentiums, are not the right way to do extremely large factorizations. They're not even competitive. However, figuring out the ``extremely large'' cutoff requires a more detailed analysis.

Re:Speaking as a computing DPhil...

[cperciva]

and time proportional to n^(1/3+o(1)) for signals to traverse the wires

Please. We can pipeline the bits; latency is not a critical issue here. I'll conceed that I hadn't considered the asymptotic cost of long wires, but I didn't claim to either. Using a million processors *does* increase the cost, but we still get a linear speedup.

The bottom line is that traditional computers [...] are not the right way to do extremely large factorizations.

And I never disputed that. Indeed, I'd say that, for a fixed (large) budget, custom silicon can probably perform factorizations 10^5 times faster than a system built out of commodity hardware.

But as long as the your FPUs constitute a fraction of the total price tag bounded away from zero, and you require the same number of FLOPs, you only get a constant factor improvement.

Re:Speaking as a computing DPhil...

[D. J. Bernstein]

Yet another blatant error. In fact, it is not possible to pipeline the communication in merge-exchange sort. Each processor needs to see a response from one of its neighbors before deciding what to do next. Latency is a critical issue here.

I must admit to some curiosity at this point. Exactly which university grants a doctorate in computing to someone who doesn't know how the fundamental hypercube algorithms work, doesn't understand the difference between hypercubes and VLSI, and doesn't even understand the difference between a CPU and an FPU?

Let's see if I can boil the news down to something that Mr. Computing DPhil will understand.

The conventional wisdom is that each processor needs, asymptotically, a huge amount of memory for the number-field sieve. The amount of memory grows steadily with the computation time. The cost of the processor is eventually dwarfed by the cost of memory.

(These effects can already be seen to some extent in today's factorizations. You might think that the cost is about evenly balanced between processors and memory; however, the processors are constantly stalled waiting for random access to memory. A much less expensive processor could easily do the same job.)

My paper shows how to get away with, asymptotically, far less memory per processor (and, furthermore, very simple processors), while keeping the computation and communication costs under control.

These are asymptotic results: theorems saying that there is a huge cost improvement for extremely large factorizations. More work is required to figure out the exact cost of the new algorithms for, say, 1536-bit factorizations. It might turn out that the new algorithms are very helpful in practice. It might turn out that the new algorithms are useless in practice. At this point, nobody knows.

Get a grip, people!

[coyote-san]

I've seen a lot of comments about how this means that all SSL and PGP encryption is transparent, etc.

Please, get a grip.

Most "transient" connections still use 512 bit keys. If this effectively reduces the key size by 3, that's still 170 bits. That's far larger than the RSA key that took years to crack a few years back.

Technology improves, algorithms improve, and the TLAs can certainly afford to build cracking engines, but it will probably still take a substantial amount of time to crack a key. (Substantial = days.) Well worth the effort if you're looking at suspected terrorists or double agents inside of the FBI, but hardly worth it for anyone reading this comment.

What we *do* need to worry about is the effect on long-term keys. E.g., root CA keys often have 20-year lifetimes, something that now seems foolish with 1k bit keys.

Re:Get a grip, people!

[pentalive]

How do you know suspected terrorist or double agents inside the FBI are not reading this comment?

: ^ )

(oops should I have posted as Anonymous Coward?)
(Hey NSA guy... it's just a joke.)

Re:Get a grip, people!

[Anonymous Coward]

Um, a 512-bit key was cracked a few years ago:
http://slashdot.org/articles/99/08/29/021323 0.shtm l

Re:Get a grip, people!

[Anonymous Coward]

A/S/L pls.

Re:Get a grip, people!

[QuMa]

please learn the difference between symmetrical and asymmetrical encryption

The trick is to find the shortcut

[beej]

Any key can be cracked--you just have to search through all of them. Phew! Now, for 128 bits, that's a lots of numbers to search. For 2048 bits, it's more than you can possibly imagine.

So the trick is to find a shortcut or a flaw in the algorithm that allows you to get the data without searching all the keys.

In the case of RSA, the shortcut is factoring the product of two primes. It's way way easier to factor a 128-bit product than it is to search through a 128-bit keyspace. So RSA bumped the size of the product up and up and up until it was as impossibly hard to factor it as it was to search a 128-bit keyspace.

Other algorithms have other shortcuts, too. Remember when a weakness was found in the session key choosing algorithm for Netscape? The keyspace was reduced from 128 bits to 24 bits or something like that, and then a search could be made on it.

Anything you can do to avoid trying all the keys is the name of the game. Unless you're some kind of quantum computer freak. ;-)

Re:The trick is to find the shortcut

[gowen]

For 2048 bits, it's more than you can possibly imagine.

"I don't know. I can imagine quite a bit"

Re:The trick is to find the shortcut

[mgblst]

For 2048 bits, it's more than you can possibly imagine.

I don't know, i can imagine quite a lot.

sorry, obligatory sw quote, i'll be queit now.

Re:The trick is to find the shortcut

[matrix29]

So the trick is to find a shortcut or a flaw in the algorithm that allows you to get the data without searching all the keys.

In the case of RSA, the shortcut is factoring the product of two primes. It's way way easier to factor a 128-bit product than it is to search through a 128-bit keyspace. So RSA bumped the size of the product up and up and up until it was as impossibly hard to factor it as it was to search a 128-bit keyspace.

There is a simpler method. Divide a random number of 1000 digits ending in 1,3,7, or 9 into 1. If the number repeats only when reaching (random 1000 digit number)-1 then it is prime. It will ALWAYS be prime. This set of prime numbers accounts for 1/3 of all prime numbers. If it isn't prime advance to the next number ending in 1,3,7, or 9. Keep going until you find one (hint, you can stop with the current number the instant it repeats).

Would you like a 10000 digit prime number?
Just do the above procedure for a random 10000 digit search space. It's easy if you think about it (my signature is not just for show alone).

Over-estimate

[Anonymous Coward]

I think you all over estimate the NSA. I can think of only one historical instance when the NSA was thought to know something that the general public didn't about cryptograpy. It was then proven later that the discovery happened almost simultaneously in the public and private sectors. I am, of course talking about the Diffie-Hellman Public-key invention itself. To give the NSA a 10 year advance in this technology is a little ridiculous (as someone suggested in an earlier post).

http://cypherpunks.venona.com/date/1994/01/msg00 50 3.html

Re:Over-estimate

[afidel]

What about the S-box modifications to RSA that the NSA did that strengthened it from differential cryptoanalysis. That was 20 years before the public sector re-invented differential cryptoanalysis.

Re:Over-estimate

[Anonymous Coward]

Enigma was not cracked in the private sector. It was only announced to the public that Enigma was cracked in the 1960's. But the system of cracking it was devised in the 1930's. This was kept secret for a long time. In fact some countries were buying Enigma machines from the Brits until the sixties. They had no idea the British already knew how to crack them.
I am sure the same is true of the other codes used in the war.

Nothing about a government agency can be declared an overestimate. Be informed.

It's obviously been insecure for quite some time.

[Anonymous Coward]

When PGP five came out, from RSA, a company owned by a defense contractor, without export restrictions to speak of, with a different algorithm, it was obvious that PGP had been broken by the TLAs if you were paying even scant attention.

If your personal security has, in any way, been resting on any derivative of the RSA algorithm since that time you forgot the most important part of playing the security game: PAY ATTENTION TO WHAT IS HAPPENING.

The environment is not static: "security" comes from being in the part of the environment which is currently "safe", and from nothing else. Look up the term "revolution in military affairs" for more details.

That is all

I don't care about n-bit encryption

[weird mehgny]

.deen uoy noitpyrcne eht all is sihT

Re:I don't care about n-bit encryption

[Anonymous Coward]

.seineew era noitpyrcne esu ohw elpoeP

Re:I don't care about n-bit encryption

[Anonymous Coward]

isn't that:
.deen uoy noitpyrcne eht all si sihT
?

sorry
:)

Re:I don't care about n-bit encryption

[Anonymous Coward]

:gnorw eb olpoep ynam os nac woH

.deen uoy noitpyrcne eht *lla* si sihT

-Ansel.

Re:I don't care about n-bit encryption

[Anonymous Coward]

.noitseuq dooG

*?*gnorw eb *e*lpoep ynam os nac woH

Re:I don't care about n-bit encryption

[Anonymous Coward]

nope, it's ".deen uoy noitpyrcne eht lla si sihT"

You still needed to flip around the "all".

Re:I don't care about n-bit encryption

[Anonymous Coward]

holy cow, that joke is getting really old, the moderators must be on crack because they always mod it up

dnetc

[AdTropis]

so when can i get a distributed.net client that makes use of this?

Re:dnetc

[Ashran]

rtfa (Read the fucking article)

Re:dnetc

[AdTropis]

it's a joke... you know... ha, ha... funny, funny.

gafsoh (get a fucking sense of humor)

google cache version

[Anonymous Coward]

The math is of course garbled, but the abstract and some of the explanations are in tact:

http://www.google.com/search?q=cache:cr.yp.to/pape rs/fastgcd.ps

Does this mean that the movie Sneakers....

[mbourgon]

is now viewed as technically sound? :)

Re:Does this mean that the movie Sneakers....

[Sabby]

I was waiting for someone to mention that movie. Watched it last night, come in and see the Slashdot story about being able to break previously unbreakable codes.

Of course, all the other technological gaffes are still there. (For now.) My future roommate was mocking me because she thought it was funny that I was pointing out little holes. I imagine she'll mock me more when it turns out that at least one of them is possibly not a hole. (Though, screens that morph from garbled text into clear text via graphics is still funny.)

not less than a second...

[agilen]

Quantum computers, using Shor's algorithm, will be able to factor numbers in polynomial time, as opposed to the exponential time that a traditional computer takes. It may still take a quantum computer a week to factor a key, but it may take a traditional computer a hundred years to factor that same key.

But then again, quantum cryptography may be even closer than working quantum computers, which means secure private key cryptography, meaning you can factor all you want, you aren't gonna find anything unless you get that private key.

Re:not less than a second...

[Hieronymus Howard]

Didn't Shor say that quantum computers would be able to decrypt faster than convention computers could encrypt?

Re:not less than a second...

[jazmataz23]

Definately. But what your parent is saying that Quantum encryption techniques will be available sooner than quantum cryptanalysis tools will be.

...built by a three-letter agency...

[sdo1]

From the referenced post...

Note that there have been rumors of an RSA cracker built by a three-letter agency in custom silicon before this, but until analyzing Bernstein's paper I had always dismissed them as ridiculous paranoid fantasies. Now it looks like such a device is entirely feasible and, in fact, likely.

Now let me guess...

It's disguised to look like an answering machine, right?

-S

Re:...built by a three-letter agency...

[Anonymous Coward]

Only if you're blind... :)

Will it allow us to factor large prime numbers?

[the_olo]

If so, then it comes out Bill Gates was right !

Re:Will it allow us to factor large prime numbers?

[donglekey]

Is that a real quote from the book?

Re:Will it allow us to factor large prime numbers?

[Anonymous Coward]

Factoring a prime number, lol

And they said I was paranoid...

[agent0range_]

It's a good thing I've been using 4k keys for years. Excessive? It would seem not.

Re:And they said I was paranoid...

[Anonymous Coward]

They probably said you were an idiot as well...
Excessive? Probably not.

a question about the paper

[Anonymous Coward]

Just reading the paper now, there is something I dont understand.

Top of page 5, talking about the cost of parallel computation. He claims that for the mesh sorting example, there is a genuine reduction in the cost, by comparing a machine with m^2 processors (which can sort m^2 numbers in O(m) time), with a single machine with m^2 memory.

Ok, as far as this goes, this is OK, the single machine will take O(m^2) time to sort m^2 numbers (actually O(m log m), but lets round it up :-), versus the O(m) for the parallel machine.

The fallacy, as I see it, is that he is assuming a single machine with m^2 memory will cost the same amount of money as m^2 machines. Therefore the cost (money * time) is m^4 versus m^3.

Surely this is wrong? The cost of a computer is not purely memory. If you spend X times more on a computer, you expect X times more memory AND X times more computation.

I havn't finished reading the rest of the article yet, but this point seems to be basis for the 'improvement' ?

cr.yp.to mirror

[Xanni]

See also my Australian mirror at: http://www.glasswings.com.au/cr.yp.to/papers.html# nfscircuit Share and enjoy, *** Xanni ***

There are alternatives

[Glock27]

Are there open-source elliptic curve cryptosystems available? It is thought that these are more difficult to brute-force than crypto based on factors.

Well, to answer my own question, on Freshmeat there appear to be one or two.

Have fun!

299,792,458 m/s...not just a good idea, its the law!

Re:There are alternatives

[frankie]

elliptic curve cryptosystems available? It is thought that these are more difficult to brute-force

Well, I know an easy example, but you're going to be disappointed. WEP encryption uses elliptic curve cryptography. However, WEP's weakness is due to bad implementation rather than a general failure of elliptic theory.

Re:There are alternatives

[Anonymous Coward]

Yeah, in Uplink the software that you buy to crack elliptic curve, is much more expensive. Thus, it is safer, since the script kiddies cannot afford it.

Re:There are alternatives

[chongo]

Yes, there are alternatives. However I would not jump into Elliptic Curve (EC) crypto at this point.

Brute force EC does not require the memory size and bandwidth needed for things such as factoring in the Number Field Sieve (NFS). See:

Robert D. Silverman's paper

for more details. In short: Given two equivalently hard keys, one EC and one RSA, the EC key will require memory and less memory/CPU bandwidth and will be cracked for less cost using the state of the art methods we known today. NOTE: These art includes: THINKLE and NFS improvements including those discussed in the paper (on which this discussion thread hangs).

Worse for EC: It is an active field of research. Every so often somebody publishes yet another eliptic curve special class that can be cracked much faster than brute force. In some cases it is very hard to determine if a given EC belongs to a weak key class. While these are mostly theoritical, the smart cryptologist will view them as troubling for EC key securiy at best.

Re:There are alternatives

[Anonymous Coward]

You have some correct points, but you say:

> Given two equivalently hard keys, one EC and one RSA, the EC key will require memory and less memory/CPU bandwidth and will be cracked for less cost using the state of the art methods we known today.

Then I guess they weren't equivalently hard. At present it /appears/ that shorter EC keys offer the same protection as longer RSA keys (about 160 bits to 256 bits, IIRC.)

Re:There are alternatives

[Anonymous Coward]

Hmmm.
"Thus, the best known attack is purely exponential in the size of the key. The time complexity is: T(k) = sqrt(pi/2) * 2^(k/2)"

To me this seems to be suggesting that 256 bits would be enough for the foreseeable future.

Re:There are alternatives

[chongo]

Sorry for the confusion! Allow me to clarify:

A common mistake that some people make is to assume that one only needs to count CPU cycles. The so-called "MIPS years" measurements.

Consider two keys that require the same number of CPU cycles to crack, one Elliptic Curve (EC) and one RSA. The EC key crack requires only a modest amount of memory, even for large EC keys. The RSA key (by factoring) requires a larger and larger working sets as the key size increases.

Consider the cracking a 256 bit EC key and the cracking of a 1620 bit RSA key by factoring:

Both efforts require about the same number of CPU operations.

The EC crack requires only a modest amount of memory (a handful of Megabytes) and can be performed in parallel over many machines with nil communication between them.

The RSA crack requires a working set of about 120 TBytes (120*1024 GBytes)! On a single machine, you will need ~2^47 bytes of ram in order to not to swap to death. Worse yet, you are evaluating a Matrix. You could try and split it over many machines but them the communication between them (as you perform row/col matrix ops) will kill you.

So when I said two equivalently hard keys I should had said: two keys that require the same number of CPU operations to crack.

Two keys can require the same number of CPU ops to crack. However, a 256 bit EC key needs only a modest amount of memory and can be cracked on many machines running in parallel. A 1620 bit RSA requires a HUGE 120 TByte matrix sitting in a single address space where swapping and/or inter-processor communication become a major problem.

Re:There are alternatives

[Anonymous Coward]

So you are saying EC is vulnerable due to that it requires "only" 2^128 ops to crack and it can even be parallelized?
(hinthint: 2^128 is FUCKING LOT. 2^47 bytes of ram etc seems pretty insignificant if you have magical powers to get that many cpucycles)

Re:There are alternatives

[Anonymous Coward]

WEP uses RC4. There's no public key encryption going on at all.

Re:There are alternatives

[chongo]

So you are saying EC is vulnerable due to that it requires "only" 2^128 ops to crack and it can even be parallelized?

No, that is not what I am saying. EC is more vulerable than RSA for a given key size where the CPU ops to perform the best known cracking algorithm are the same.

CPU-op equivalent EC searches require only a modest amount of memory and can be run in parallel with nil communcation requirements. CPU-op equivalent RSA searches require large working sets with matrix operations that do not lend themselves to parallel operations once the initial sieve is performed.

Even if you deploy a TWINKLE device in an RSA key crack that reduces the initial loading of the matrix to nil, the working set size of the matrix, the swap and/or system communication requirements become non-trivial for an CPU-op equivalent RSA key.

Re:There are alternatives

[D. J. Bernstein]

One way to view the linear-algebra algorithms in my paper is as follows: it's possible to split that 120-terabyte matrix across a huge number of tiny computers with surprisingly small communication costs.

There's still more overhead here than in the sieving. The analysis shows that it's worth spending more time sieving to reduce the matrix size.

Not a threefold increase in speed!

[PylonHead]

The post about the article claims a threefold decrease in effective key length. This is much greater than a three fold increase in speed.

If factoring a number is proportional to the size of a number, then a number that would take 280 years to factor might take 46 days.

It also says that the technique might not be effective on keys as short as the ones currently used.. so the speedup may be theoretical.

Yes, key exchange is asymmetric.

[brad.hill]

The symmetric key used by SSL (usually for the RC4 algorithm) is negotiated using an asymmetric public key cryposystem. (usually RSA) If that can be broken easily, the keys to the symmetric algorithm are right there.

The real reason a symmetric algorithm is used for the bulk of an SSL session is that it is much less computationally intensive than an asymmetric algorithm with a similar degree of security.

Note that these algorithms are independently pluggable, so a more secure or larger key size asymmetric algorithm could be used alongside the same old 128 bit RC4.

The big problem here is for systems using browser managed certificates for authentication would have to be upgraded and new certs issued. This is not the most common usage of SSL, but where it is in place the systems tend to be large and expensive.

lol

[Anonymous Coward]

revetahW

MOD Parent Up!

[elliotj]

Right on. The result of parallelising computational tasks that are currently done in serial has been known for ages. The whole concept of a quantum computing key search has been to try all the keys at once. This is essentially implementing that concept using non-quantum hardware - to a certain extent.

This is a big deal in the sense that we may be moving toward the point where our ability to process in parallel can crack any keys generated by computers without that capability. But it is analagous to my abilty to encrypt using a computer what you would be unable to decrypt using as handheld calculator. If both sides are equipped with the same computing technology, the security remains intact.

It was used to ...

[purduephotog]

... create random noise to be used in a 'one time key' / 'one pad key'. Totally unbreakable. Especially if the message is short.
I remember the post you are referencing. There are cameras that photograph a number of lava lamps. Thru a couple of data munging operations, out pops a length of completely random data.

This was posted on some crypto/compression list awhile back about compressing totally random data. The guy was able to do so by underspecification of the problem. It was slashdotted, I believe.

Anyways, the same thing can be applied to picking up atmospheric noise/wind. Anything that cant be predicted or known at any other location should work for random data, thus you could use to encrypt. It is a "One Time Key" - no way to recreate the data without the data.

Re:It was used to ...

[HeschelsGyrus]

The folks over at Random.org use atmospheric noise to generate true random integers. I use their numbers all the time, although not for anything as complicated as cryptography...

Re:It was used to ...

[Ratbert42]

This was posted on some crypto/compression list awhile back about compressing totally random data. The guy was able to do so by underspecification of the problem.

If I recall, the guy asked if he could break the compressed data into several files as long as their total file size was smaller than the uncompressed data. Sure, said the judge. So he broke the data into thousands of files and used the "free" storage from the filenames to end up with a smaller total file size than the uncompressed data.

Re:It was used to ...

[mother_superius]

unless atmospheric noise has minute patterns, of course...

Did I miss something?

[Anonymous Coward]

http://cr.yp.to/papers.html

Is it just me, or did I totally miss Tonga's rise to a leadership position in the crypto community? I didn't see it on their website...

You naive fool

[Anonymous Coward]

"CNN and Network World detailed how the NSA openly strong arms companies, "leaning on software, switch and router vendors" to make them "add a government-approved back door into network gear." Companies working with the NSA, however unwillingly, include Netscape, Sun, and Microsoft. Chris Tolles of Sun says, "Everyone in Silicon Valley, including us, has to have specific staff -- highly paid experts -- to deal with them." If everyone's dealing with them, are any products secure?

Taher Elgamal, who wrote Netscape's so called "data-recovery plan" as demanded by the spooks, said they didn't have a choice. Exports are about half the income for these businesses. In practice companies need NSA's permission to export security products, except for "export grade" junk. NSA only gives permission if the security is crippled in some way.

Duncan Campbell reported in Interception Capabilities 2000 that NSA succeeded in compromising browsers from both Microsoft and Netscape, as well as Lotus Notes. The browsers' security was openly gutted by NSA's insistence on reducing key sizes to whatever the NSA can easily crack at the time. In the case of Lotus Notes the keys appeared to be longer, but just enough of each key was secretly given to the NSA.

According to Network World the NSA "forced MasterCard International, Inc. to dumb down the Secure Electronic Transaction (SET) credit-card encryption standard." NSA insisted that most of every transaction not be encrypted at all. When someone steals a lot of money using SET we'll know why.

Sabotaging friends and foes isn't new for the NSA. It's life long behavior. In Crypto AG: The NSA's Trojan Whore you'll find the intriguing but very disturbing story of how 50 years ago NSA rigged the crypto systems sold by Crypto AG so that NSA could read the supposedly secret messages. Customers of Crypto AG include embassies, military, banks, and rogue nations such as the Vatican. "

I pasted that selection from this Cryptome article. Secure from who? It is probably hard to crack for private persons, but the NSA apparently can crack it since they force companies to install backdoors. If you search around Cryptome you will learn that the NSA forces companies to use crypto that is weaker than most companies want to use, so that it is easier for them to crack.

512 bit keys obsolete

[fava]

If I recall correctly the banking industry uses 512 bit RSA keys. If with this hardware its computationally equivalent to a 512/3 or 170 bit key then I imagine that the bankers are getting very very nervous.

I hope that the banks can update their infrastructure fast enough or we are going to have massive problems as soon as someone builds a illicit factoring machine.

Re:512 bit keys obsolete

[donglekey]

This is rediculous and no one is getting nervous. A 512 bit key is such overkill and for this very reason. If it was brought down to the equivilent of a 170 bit key, I would still trust it. 170 bits is still so fuckin huge that it would take forever to brute force. Lets say that you could somehow try 100 trillion keys a second. It would still take 474,561,668,133,829,461,009,821,559 milleniums to try every 170 bit key. That is a lot to me, and I am not too worried. You would have to have some algorithm that found MAJOR weaknesses before even the 170 bit key could concievably be broken. An attack on the way the keys were generated is much more likly to be succesful at that point.

Re:512 bit keys obsolete

[carleton]

Wrong... in 1999, a group in Australia factored the RSA-140 challenge (140 decimal digits). This effort took roughly 3 months of calendar time using roughtly 300 computers (300MHz PC's and slower megahertz wise suns/sgi) for the seiving portion (parallizable) and then 1 cray (don't know specs) for the final step (which took less that 1 month). The RSA-155 challenge (512 bits) is estimated to only be 7.2 times harder CPU wise (versus the 1024 bit one, which is estimated at 40 million times harder). If I understand how this enhancement works, the algorithm is still not polynomial, but it should cut down the growth from 140 digits to 155 digits.

Re:512 bit keys obsolete

[roybadami]

No one has any intention of trying every 170-bit key.

What they want to do is factor a 170-bit key (well, actually, a 512-bit key in your example).

Re:512 bit keys obsolete

[fava]

If the only way to factor a number was trial division then you would be correct. However the modern algorythms for factoring are much better than that, perhaps you are confusing symetric cryptography such as DES or AES with RSA.

I am unable to find a table online but in 83 a cray factored a 71 digit number in 0.1 Mips-year (1 million instructions per second for 1 year) Since the numbers are talking about are much smaller (50 digits vs 71 digits) and cpu's are much faster (> 1 billion ips) it would not be unresonable that a 50 digit prime could be factored in a few hours on a machine with suffecient memory.

Re:512 bit keys obsolete

[Anonymous Coward]

NO, not at all. RSA is not a flat keyspace, not all permutations of bits are valid RSA keys. You can reverse the encryption by factoring the RSA public key, that's the problem. Factoring a 512 bit key is MUCH easier than trying all possible combinations. In fact, the difficulty of factoring is roughly linear with keylength. Twice as long of a key makes it twice as hard. (This isn't exactly true, but it's closer to linear than to tru exponential).

Tyler

Re:512 bit keys obsolete

[inkey string]

it would not be unresonable that a 50 digit prime could be factored in a few hours on a machine with suffecient memory.

I can factor 50 digit primes in my head...

Who cares

[wk633]

The TLAs will just install a wiretapper on your keyboard anyways.

Re:Ginger scale big?

[Thing 1]

don't tell me you haven't converted your judgments of magnitude to the ginger scale. everybody's doing it.

I was always partial to the maryann scale, myself.

Re:1.5 bits lost? - not quite

[oomcow]

No, someone has been spreading around an erroneous interpretation of the paper. From the abstract:

"This reduction of total cost from L^(2.852...+o(1)) to L^(1.976...+o(1) means that a ((3.009...+o(1))d)-digit factorization with the new machine has the same cost as a d-digit factorization with previous machines."

In plain terms: A factorization of a number that has 3 times as many digits will have the same cost as a the number did before.

Hope this clarifies why this is a breakthrough (that may be important).

One word: Asymptotics.

[DontUThinkImPretty]

Bernstein's results are asymptotic. That is, he states that a key of length n is about a secure on his special hardware as a key of length 3n on standard hardware. But this is an approximation for very large n. It is completely possible that for n near the length commonly used, his hardware could actually take longer than other equiptment.

Bernstein's result isn't the RSA killer you hotheads are making it out to be. It's a very cool result, but it's not the biggest and the baddest in the last decade.

Re:One word: Asymptotics.

[PureFiction]

True, perhaps I worded my reply too strongly.

But I am not content with possibilities and maybes. He has shown an effective way to greatly increase the capability of simple hardware to attack large integer factorization. This alone is enough to make me nervous. Do you really want to bet your security on possibilities?

I already use a 4096bit ElGamal key. I would suggest others do the same.

And regarding the rather tame developments in the crypto field (this is becoming old, well explored territory, not much new happens these days) I still think this is signifigant.

Looking through the paper...

[SIGFPE]

...it's not clear this has any impact on crypto security today. There are lots of O(1)'s and nobody can be sure just how big they are for the real keys that are used today. Still, it can't do any harm to keep on your toes and make your keylength as long as your hardware will allow.

RSA already cracked a few months ago?

[Anonymous Coward]

While browsing low modded posts I found an intriguing post titled: "RSA cracked. Get over it.". It looks like someone somewhere can factor large integers and posted the proof anonymously on Slashdot on November 2nd, 2001.

Re:RSA already cracked a few months ago?

[Dahan]

Eh, it's just a troll... the number that was factored isn't RSA-500; it just looks like it at both ends. The middle 250 digits or so are different.

KARMA WHORE

[Anonymous Coward]

quoting link...mod down please

the biggest news XXXX in the last decade,

[Anonymous Coward]

It's amazing how many events are the biggest news of the decade when they occur (or are publicized), but somehow 10 years later they're long forgotten.

NSA-sponsored Cray 4 development now makes sense.

[Thagg]

A friend of mine worked for Cray Computer Corporation until the untimely death of Seymour Cray. The last machine they were working on was a monster, that might make more sense in terms of today's developments.

In the early nineties, CCC was working on the Cray 3, a new gallium arsenide computer. It was to have a cycle time of about 1ns (shockingly fast back then.) It was cooled by a high-pressure very high-speed mist of Flourinert suspended in helium. It was built as a series of wedges much like the Cray 1 and 2, although somewhat smaller. They built working prototype wedges, and were debugging them, while looking over their collective shoulders at the ground being gained on them by arrays of microprocessors.

One thing led to another, and it was clear that the Cray 3 would never be a commercial success. They were then given a contract to build what was called the Cray 4. The Cray 4 was a one-off machine using PIM (processor in memory) chips. These were 1-bit computers, but there were 262,144 of them in the box. The idea was that the gallium arsenide chips, wiring, and cooling system that made up the Cray 3 were just the networking system for these PIM chips, which would do the actual work.

Anyway, Cray died, and then CCC quickly died, and I don't believe that the machine was ever finished.

thad

Don't over-react

[DJFelix]

If you notice, the paper he published was part of a proposal for a research grant to see if this is even possible. Right now, this is all theory and conjecture. DJB is trying to get financing to pay for this little research project. My guess is that in a post Sept. 11 world, the government will most likely look at this project as dangerous and borderline terroristic. I don't see it getting off the ground.

Mirror of paper on citeseer

[Andrew Lockhart]

Well i couldn't get to the original site, but i see that NEC's citeseer has it.

AES IS ALSO PARTIALLY COMPROMISED

[Anonymous Coward]

aes and des do not rely much on factoring. however, the transmission of keys, which must be done before people can communicate using any sort of private key encryption(AES, DES, take you pick) is usually done with public key encyption.

other words: this doesnt help people break aes, but it does make it easier for them to intercept the key ahead of time

+4??!? LEARN CRYPTO BASICS BEFORE MODDING

[Anonymous Coward]

Factoring 170-bit numbers is childs play. Anyone can do it.
170-bit symmetric crypto would be a whole different matter.

Re:+4??!? LEARN CRYPTO BASICS BEFORE MODDING

[Alsee]

Factoring 170-bit numbers is childs play. Anyone can do it.

::Alsee whips out pencil and paper and starts scribbling furiously::

-

in regards to recent polls

[Pope]

How many sides are on a dPhil?

Of course not...

[Anonymous Coward]

Why do you think the Gov't Agencies have been interested in machines that are essentially huge banks of FPGAs? I know of such machines that existed in certain places for at least 12 years now. A few years back there was a huge push for commoditized embedded (VME/etc) cards that were just cards packed with FPGAs with a general purpose CPU on it to drive them.

Re:1.5 bits lost? - not quite

[spiffy_guy]

This certainly doesn't look like 3 times, but 3.009 digits. So a 59 bit key instead of a 56 bit key. I'm still confident that a 2048 bit key just doesn't make sense to attack directly.

DSA ?

[morcego]

Any impact on DSA, as used by ssh and GnuPG ?

RSA Factoring Challenge Prizes

[Anonymous Coward]

Does this mean the RSA Factoring Challenge Prizes will all be claimed very soon?

http://www.rsasecurity.com/rsalabs/challenges/fa ct oring/numbers.html

Googlized...

[Anonymous Coward]

You guys could of atleast posted this:
http://www.google.com/search?q=cache:HNDY5d p49LAC: cr.yp.to/papers/nfscircuit.ps+&hl=en

Mirror/Cached papers here

[bodin]

(as djbs koobera-server seems to be under hard pressure)

Here you will find mirrors of the original file as well as the document in pdf-format etc:

http://citeseer.nj.nec.com/462633.html

You never know...

[Anonymous Brave Guy]

Reminds me of a certain movie...

Heh. Not so long ago, there was a thread around here about Swordfish. Some smart alec came along and claimed that it was not realistic at all, just the usual Hollywood-overdone glamour, because it featured the best (still alive) hacker in the world cracking a 128-bit encryption system in about one minute...

The scary thing about the whole cryptography field is that the maths behind most cryptographic algorithms is really very simple (in "professional mathematician" terms, at least). You can obviously never know when a new technique is going to be uncovered within mathematical research that will undo years of "secure" communications in a heartbeat.

Hey, there are guys alive who can do incredible arithmetic feats in their head. Many of them can't explain how they do it, they just see things differently to the rest of us. What happens if someone comes along who can "just see" a large number as the product of a couple of prime factors...?

Re:You never know...

[KodaK]

What happens if someone comes along who can "just see" a large number as the product of a couple of prime factors...?

He gets a high paying job with the NSA.

Or a nice dark cell.

Old News

[Anonymous Coward]

My brother figured out this factoring problem a long time ago. I'd say he spent about 30 years in the basement working on it. He only came out for coffee and cigarettes. I told him he should post it on the Internet, but he doesn't seem to know what that is. Come to think of it, he doesn't seem to know much about the outside world anymore.

You're all missing one thing...

[Anonymous Coward]

The comment is 3-FOLD, not a factor of 3. 3-fold is an exponential change - it means the strength is roughly the CUBE ROOT of what it formerly was. e.g.: 512^(1/3)=*8* bit security equivalent. How long does it take to crack 8-bit encryption? Not very long. Scale to 2048-bit: 2048^(1/3)=~12.7-bit equivalent. Ok, let's go whole-hog ... 16384-bit key... 16384^(1/3)=25.4-bit equivalent ... does this begin to make sense as how major a breakthrough this is?

Re:You're all missing one thing...

[-brazil-]

You're just as wrong as those claiming that it means a difference in keylenght of 1.5 bits, just in the other direction. It's not 512^(1/3), it's (2^512)^(1/3) = 2^170.66...

Re:You're all missing one thing...

[Anonymous Coward]

Have you any clue how to do math? 2^170 is tremendously larger than 512=2^9.

Re:NSA, et. al. Correction

[skybird0]

That's not quite what I meant, since P is a (possibly improper) subset of NP. Factoring has never been shown to be not P (i.e. not solvable by a polynomial-time algorithm.)

Re:PGP with 2048 bit RSA keys

[pmsr]

http://www.ipgpp.com/ for the lazy among you. PGP 6.5.8ckt Build 06 is the last version, i believe.

/Pedro

Straight from the NSA web site (nsa.gov)

[alcohollins]

Seems you are right about the NSA employing more mathematicians than anyone else in the world. They believe this too. From a page on their web site:

NSA employs the country's premier codemakers and codebreakers. It is said to be the largest employer of mathematicians in the United States and perhaps the world. Its mathematicians contribute directly to the two missions of the Agency: designing cipher systems that will protect the integrity of U.S. information systems and searching for weaknesses in adversaries' systems and codes.

The real fun...

[watchmaker1]

will come when Bernstein puts a restrictive license on his algorithm that nobody can get binaries of it except from him. And of course, don't forget the obligatory mailing list carrying 30% messages of merit and 70% messages of people bitching about djb and his licensing.

Re:NSA, et. al. Correction

[hornet@ch]

Yes, sorry, in fact you are right (I got lost in writing something ironic). As far as I know it is just *feared* that factoring is not P.

Sorry! :)

A big part of a security solution is knowing WHO.

[Fencepost]

Knowing who you're trying to keep secrets from is a big part of deciding how (and whether) to secure any data.

The needed approaches are radically different depending on whether you're trying to keep secrets from highly-skilled groups with plenty of resources (e.g. government agencies investigating you in particular), skilled groups with some resources (corporate espionage, small countries), snoopy ISPs (e.g. Comcast), skilled interested parties (IS groups), the casually curious (repair techs), and the unskilled (your grandmother). At the top end, you have to do all sorts of things that make using computers much more of a pain in the ass to keep them from adding keyboard sniffers, monitoring emissions, etc. At the low end, you have to learn how to hide files (using a .prefix or "hidden" flag, who cares) to keep your grandmother from being shocked by all that hot monkey lovin' in your porn archive. In between there are tradeoffs - how important is the information (do you need to keep it at all?), how important is it that it not be seen by others, how much inconvenience are you willing to go to to ensure that nobody else sees it?

Keep in mind that encryption isn't security. Encryption isn't even close to security. Encryption is a tool.

Alternatives such as EC may be vulerable as well

[chongo]

Some have suggested that people should move away from RSA crypto and start using Elliptic Curve (EC) crypto. In fact the paper, if appicable to "useful" key sizes, suggest that the opposite is true.

The methods described in the paper can be used to improve the cost of cracking EC discrete logs as well. The author, in a recent Usenet posting, points out that the paper's methods are likely to reduce the cost/effort of EC key cracking as well ... perhaps even more than RSA key factoring.

The paper, combined with other other EC strength concerns suggests that EC is not the technology to turn to at the moment.

In other words, if this paper has you concerned about the security of RSA keys by factoring, then you should be even more concerned about the safety of Elliptic Curves as well.

But as others, including the author, have stated (in large friendly letters): DONT PANIC! It is not known if the ideas expressed in the paper are applicable to key sizes that are in common use.

About this Dan Bernstein guy...

[Anonymous Coward]

Every year he prepared a fully texed solution of Putnam Math competition and post it to the newsgroup sci.math. I found his solution to Putnam 1995 B6 better than the ones given by Kiran Kedlaya and Dave Rusin (two other guys who post Putnam solution on the internet). However I prefer Kiran's solution because they are in Pdf format, easier to read because I'm too lazy to download a tex viewer.

That doesn't work:

[Anonymous Coward]

Backwards writing

aargh.

[Anonymous Coward]

That recent usenet post is speaking about benefits of specialized hardware in brute-force approach, not about algorithmic breakthrough.

[OT] Re: your sig

[Cid Highwind]

Pacifism is objectively pro-Fascist..."he that is not with me is against me." - George Orwell

I wonder if Orwell appreciated the irony of trying to transmute a political opinion to fact by putting the word "objectively" in it.

DMCA?

[Anopheles]

Does this violate the DMCA in some way?

Speaking as a hacker

[Anne Thwacks]

In cases of exhaustive search, it is well known that parallelism reduces the total amount of work done, as poor solutions are abandoned with less processing.

This is not news. Its been well known at least since the 1970's.

This applies to factorising and block cyphers, which probably explains why ICL built a military version of the DAP.

Why does everyone asume TLA agencies know the most? If you knew how to factorise products of large primes, who would you tell? (If you want to live to tell the tale!)

Re:Speaking as a hacker

[pslam]

In cases of exhaustive search, it is well known that parallelism reduces the total amount of work done, as poor solutions are abandoned with less processing.

But parallel machines can be simulated by sequential ones with the same amount of work done. Therefore any parallel algorithm can be done with the same amount of work on a sequential machine by simulating a parallel one.

But in terms of clock cycles, it's at most P (processors) times faster on a real parallel machine. Or am I missing something here?

the government knew about his all along...

[mozkill]

actually, the CIA hasnt told us, but they have known about this decryption method for sometime now... how do you think they knew you didn't take a shit this morning?

Well duh

[CodeMonky]

According to dictionary.com Link Thus the entire security of RSA depends on the difficulty of factoring; an easy method for factoring large prime numbers would break RSA. So it looks like we've been going about it all wrong. We should be concentrating on factoring large prime numbers. :)

Talk about luck

[WinstonSmith]

Good thing I have a 4k key.

It's also a good thing that I'm a total loser and don't have friends sending me anything in the first place.

Crypto - Stephen Levy - Read It

[xipho]

Good history. Excellent for the layman. On Amazon

Re:Alternatives such as EC may be vulerable as wel

[chongo]

To clarify and avoid confusion:

The paper suggests a way to improve some of the steps required (such as some of the linear algebra work) to factor using the Number Field Sieve (NFS) for large keys.

The paper does NOT give a method to improve the speed of cracking EC keys.

Special purpose hardware could reduce the cost of cracking an RSA key. However: The same could be said of cracking an EC key. Using different special purpose hardware and different performance tuning, one should be able speed up cracking of EC keys as well.

So ... If the existence of ideas to improve the speed of cracking sufficiently large RSA keys scares you and you worry about that might come next, then you should be even more worried about EC.

Why? Not because of the exact idea outlined in the paper. The paper does not apply to EC. Because EC is subject to special purpose hardware improvements: perhaps even more than RSA.

... and because while two keys, one EC one RSA may require the same number of CPU cycles to crack, the key crack requires only a modest amount of memory, even for large EC keys. The RSA key (by factoring) requires a larger and larger working sets as the key size increases.

It's an interesting idea, but...

[Anonymous Coward]

Looked at another way, he hasn't changed anything.

He's observed that current factoring algorithms use asymptotically more memory than CPU. For a sufficiently big problem, all of the cost of the machine goes into buying memory, which spends most of its life waiting for the CPU to get around to it.

It's the same idea that motivated the Connection Machine.

He's observing that if you use the right (low-memory) algorithms, you can trade off memory for CPU and get something for which the total cost, memory+CPU, grows more slowly with problem size.

But it's not clear that's we've reached the CPU bottleneck yet. RAM is really cheap these days, so it's quite possibly premature to worry about the growth rate of that term.

Remember, the paper is part of a grant application. "I have this neat idea, and I'd like to study how practical it is."

More concretely, if all his ideas pan out, he can factor a 3*n+k-bit number for the same cost*time that GNFS can factor an n+k-bit number. What's k? Nobody knows! That's what he wants to study. If it's 1024, there are no immediate security issues. If it's 128, we need to deal with it.

(The claim in the abstract, (3.009...+o(1))*n, is more accurate, but the casual reader might not notice that o(1) can be significant and negative for currently interesting problem sizes.)

So while it deserves careful attention, let me add, in large, friendly letters: Don't Panic .

HOWTO factor the products of large prime numbers

[cpeterso]

Why does everyone asume TLA agencies know the most? If you knew how to factorise products of large primes, who would you tell? (If you want to live to tell the tale!)


I'm glad you asked. I just finished my latest CVS checkin over at Source Forge. Please check it out! If you have any questions or bug fixes, please let me know: http://sourceforge.net/projects/factor_the_product s_of_large_prime_numbers .

Wrong cryptosystems

[himi]

128 bit keys almost always refers to a /symmetric/ algorithm - this is things like AES, Twofish, IDEA, etc. And for good symmetric ciphers, 128 bits of key is fairly secure - to brute force, you have to try out all 2^128 possible keys, which is a very hard problem (assuming, of course, that there aren't other problems with the cipher).

This article is referring to /assymetric/ ciphers - public key cryptosystems, and in particular RSA. RSA keys are made up of two large primes multiplied together (IIRC - it's been a while since I read this part of Applied Cryptography): finding the two primes breaks the key, and so its security is based on the difficulty of factoring really large numbers into prime constituents.

The research referred to here is a way to speed up the factoring of large numbers, apparently by a factor of about 3 - it doesn't break the algorithm, it just speeds up a brute force attack. If it took 3000 years to break a 2048 bit RSA key before, now it'd take 1000 years. Barring more such discoveries . . .

Don't panic is a very good response to this - it's a serioius discovery, and it changes the risk factors involved with using RSA crypto, but it doesn't throw everything out the window.

Finally, I'd really suggest reading at least the interesting bits of Applied Cryptography, by Bruce Schneier. It explains a lot of this stuff, and gives you a good framework within which to put this kind of thing.

himi

Re:It's obviously been insecure for quite some tim

[Simon Garlick]

PGP 5 binaries were released by PGP, Inc, and accompanied by a full source release. Put the tinfoil hat back on.

Dan and the government

[rcw-work]

Dan Bernstein is fairly used to the government looking upon his work as illegal.

I don't think it'll be an issue.

This does /not/ break RSA.

[himi]

All it does is speed up a brute force attack.

If it /did/ break RSA completely - ie, by indicating that factoring is in fact a P problem rather than NP complete - then it would have made infinitely more of a splash than it did. That kind of breakthrough is Nobel Prize type stuff.

himi

Re:This does /not/ break RSA.

[Miniluv]

No, it's not Nobel Prize type stuff. Alfred Nobel hated mathematics, which is why there still isn't a Nobel Prize in math and prime factorization isn't a physics or economics problem which is where the math geeks usually get their prizes from.

Re:This does /not/ break RSA.

[Anonymous Coward]

But if you prove you can't do cryptography... that would put a lot of mathematicians out of jobs, and old Alfred would have liked that, right?

Re:This does /not/ break RSA.

[spook brat]

Alfred Nobel hated mathematics

From what I've heard, Alfred Nobel hated mathematicians because his wife ran off with one. Of course, I heard this in High school from one of my teachers, so who knows if it's reliable info. A fun rumor, nevertheless...

Re:This does /not/ break RSA.

[bakes]

Solving factoring wins a Nobel Prize? Is that why it's called NP-complete?

Re:This does /not/ break RSA.

[Traxton1]

Actually, it's not a Nobel Prize type thing, it's a Million Dollar Prize type thing.

Re:This does /not/ break RSA.

[Jonathan the Nerd]

A fun rumor, but not a true one. http://www.snopes.com/science/nobel.htm

Symetric/Public Key Equivalence

[Taboo]

Copied from a Snakeoil Doc:

Symmetric and Public-Key Lengths With
Similar Resistance to Brute-Force Attacks

Symmetric Key Length Public-key Key Length
56 bits - 384 bits
64 bits - 512 bits
80 bits - 768 bits
112 bits - 1792 bits
128 bits - 2304 bits

Inaccurate summary of the research . . .

[himi]

It doesn't speed up the factoring by a factor of three, it increases the keylength it can break by a factor of three . . . In other words, this version of the NFS algorithm runs in the cube root time of previous versions.

This is more significant than a simple three times speedup, but it still doesn't change the fact that it /doesn't/ break RSA, it merely speeds up the attack.

himi

I love sharing scuttlebutt

[DaveWood]

I'm happy to rumormonger with you all for a little while...

I hear things from various people that I shouldn't hear, not often, but occasionally. These are people who are rather credible - not totally, but rather. I feel pretty confident in this particular "rumor," because I've heard basically the same set of facts from three different people with three different kinds of intelligence community experience.

What I hear is that your assertion is true. The NSA has had the ability to break RSA cyphertext "for some time." Even extremely large key sizes are said to be vulnerable, and they can do it "reasonably quickly."

This, of course, flies in the face of all accepted non-defense conventional wisdom in the field - at least until today - but, as I said, three sources. So I believe it.

This may be the result of harrowing secret advances in factoring techniques, or it may simply be brute force. This is an agency that has historically measured its computing power in acreage.

So, "reasonably quickly." The other part of this "rumor" is that reasonable is not reasonable enough to do RSA decryption on a large scale, and hence, while they can break open a particular piece of data, they haven't necessarily integrated RSA see-thru into their global signals intelligence regimine. That, for the uneducated/head-in-the-sand types, is Echelon - and yes, the NSA does listen to, and data-mine, almost all of the world's information traffic.

Final piece of this particular story: the NSA is apparently fastiduous about not sharing this technology, even with other federal agencies. Kevin Mitnick's infamous laptop, rife with PGP-encrypted documents, was impenetrable to the FBI, and despite numerous, desperate appeals for help, the NSA refused to assist them in decrypting the data. That suggests the NSA is abiding by their charter, which basically forbids them from becoming involved in domestic law enforcement (i.e. they're not supposed to spy on Americans) - a necessity if you consider consitutional guarantees about "search and siezure" applicable (by no means a universally held view, unfortunately).

Something similar at the recent RSA conference???

[Robber Baron]

Wasn't somebody doing something similar at the recent RSA conference...Blasting through multiple rounds of DES and factoring RSA keys on smart cards with some magic boxes?

I use a 2049 bit key - I'm safe!

[Anonymous Coward]

suck on that!

7h3Y C4N7 Cr4cK D15 C0de!

[Anonymous Coward]

H4 H4 H4!

2k bits. i'm secure enough.

[j1mmy]

i already use 2kbit rsa for my webmail. so i can read my spam securely. whee.

Re:It's obviously been insecure for quite some tim

[Anonymous Coward]

No you dope, they changed from RSA to DH, changed the file format, introduced bugs like the one which allowed an unsigned key to be added to your keyring (causing all outgoing trafic to a given key to be decryptable with the unsigned key also) and so on: basically backdoored the shit out of it in ways which were sufficiently sneaky not to be obvious.

Dimwit.

PGP with really big RSA keys

[Bob_Robertson]

I recompiled PGP back in 1994, after looking through the source code and finding a variable called (I kid you not) "MAX_KEY_LENGTH=1024".

I changed it to 8080 or some such strange number, and it ran just fine.

On a 386-33 it was *slow* to generate the keys, and of course no one was compatable, but it was trivially easy to do.

I wonder why the keysize limits on GPG still demand only 2048 or smaller. Why bother?

Bob-

cr.yp.to

[Anonymous Coward]

cr.yp.to is not slashdotted. All the qmail, ucspi stuff comes up instantly. The crypto-links
all come up 'file does not exist', publicfile's version of 404. The files have been removed or 'chmod o-r''d. If they are not back up in a few days I will be greatly saddened.

don't be fooled

[Anonymous Coward]

To me at least there is a sort of spider web safety net that protects me from a bad corporation, and I have a choice in which ones I support, but there is no such apparent safety net when it comes to the government.

I think you have it backwards.

Public apathy is the greatest problem with keeping government under control. There are many groups specifically designed to raise public awareness (ACLU, Greenpeace, you name it...). Why? Because they know that when the public gets pissed, things can change. Citizens in the U.S. can vote and this is the bottom line for keeping Congress and the President in check. When people get pushed around too much, they want a change. Look at the last senator race in WA - Slade Gorton, a LONG time incumbent got kicked to the curb.

On the other hand, you have no say about what a corporation does. You have to rely indirectly on the government to keep them in check, or "vote" with your dollars.

Unfortunately, economics sometimes make things worse. For example, let's say people stop buying products from a manufacturing company (oh let's say GE) and they need to cut costs. Maybe it's cheaper for them to dump in the Hudson river instead of cleaning up responsibly.

Worse yet, is when corporations redirect their money towards things that go against the grain of public interest. They usually don't tell you about these things. Did you ever realize that some of the money you spend on Ben & Jerry's ice cream gets donated to the anti-gun lobby in the U.S.? Maybe that suits you, maybe it doesn't, but the fact is that they aren't TELLING you about it. When it comes to a senator or representative's voting record, though, it is open for the public to see.

Or go one step further to multinational corporations who may not even be based in the U.S. Sony is one such beast. Their participation in the MPAA lobby has resulted in some horrific laws being passed in the U.S.

Corporations are definitely something to be wary of. Government may be corrupt, but at least you still have a method of participation in it.

Re:don't be fooled

[Anonymous Coward]

When people get pushed around too much, they want a change. Look at the last senator race in WA - Slade Gorton, a LONG time incumbent got kicked to the curb.

Yeah, look what happened to him. He's laughing all the way to the bank with the fat cat pension he's getting and all the boys club connections he made. Boy, he must be really affraid now.

Really, he got exactly what he wanted out of his terms. It was time for him to kick it back in the Carribean and smoke some Cuban cigars.

Re:don't be fooled

[Anonymous Coward]

Yeah but we don't have to worry about his votes and special committee influence anymore (which was clearly tainted by Microsoft). Voting does work. It's a shame more people don't get off their asses and do it.

NSA 2020

[Anonymous Coward]

1 u133r |33+ n54 #4>0r
\/\/3 53+ U5 uP Jo0R k3y5?!11??!1
4|| j0or pR1/\/\35 4R3 83|OnG +O U5!!!!!11

Re:Wouldn't take hours

[Anonymous Coward]

Actually, to factor a 50-digit composite number on modern hardware would take under a minute. Go to http://indigo.ie/~mscott/ for a program that does it; the link for a precompiled Windows version is on the bottom of the page.

Re:It's obviously been insecure for quite some tim

[Simon Garlick]

> No you dope, they changed from RSA to DH

For good reason. If you don't KNOW the reason, then you're not exactly equipped to comment.

> introduced bugs like the one which allowed an unsigned key to be added to your keyring

Bugs which were discovered by peer review -- discovery made possible by the Open Source code release.

> backdoored the shit out of it in ways which were sufficiently sneaky not to be obvious

Your inability to actually name any of these ways shoots you down far more eloquently than I ever could. Put the tinfoil hat back on, sit down, and STFU.

Crack this message...

[blitz77]

'¥F×ÁÄg_̱é==^{íií/ðLÇW"FgÑçRHC~èÛq' 'x!OEÅ'õ(TM)úNa÷yi(p}Wúsñ±òn^0ÆéÁ`EÇ[@ß@'Ê CÔúk&¾Ê'-zb|ïXY0ÜOîGÈrfè½x(M3®%'à½ÂS pËsQ£z7óó®0ÏÕFÝrS'Q7aüÐ p8Ã$î'ÉNsÕxvcûûêPÒT'TÐdÐ8MsØÔJݼ`Ö[ÊqÎ 61oer'f},©ÐíÖÆÕÀÁòr EA3×íN29JâçÛ¥G--zÇZléÁ½l©f'í|=noÚhmZ0ÚvpLÌ sâg@L@îAsKõôfv,já(ãÐs>ESuÄLûõj ëíðqDoeo...½RÐÑÅa] 'ÈjõooWæ\#$ØÇM0Âr¼

Corporations ARE the government

[inKubus]

I hope everyone's been paying attention to the whole Enron/GlobalCrossing/etc. affair--seems to me this thing is just getting bigger every day. One thing about the NSA being so secretive is that all they are doing is getting/gathering data. They can't really do anything with it. And I don't think they would, if they could. They are professionals just like the rest of us. It's who they give the information to that's scary.

Questions for Those that Understand

[Phil Gregory]

I'm a person who has quite an interest in crypto and often a good understanding of the base concepts behind crypto systems, but I don't understand much of the math that goes into proofs like this. Thus, I'd like to put some questions out to those who are more experienced than I am.

First, does this work? Have people independently verified that DJB is correct? (I went looking for some peer review via Google and didn't turn up anything that looked conclusive.)

Secondly, what's vulnerable? As I understand it, what DJB has discovered is a more efficient method of factoring numbers (on custom hardware) such that keys three times longer can be factored in roughly the same time. RSA is based on the product of two relatively prime numbers, so it's vulnerable. Aren't most public key systems based on this principle, though? How vulnerable is, for example, DSA to this new factoring technique?

--Phil (This article went up yesterday; hope someone's still around to read my post...)

Re:NSA-sponsored Cray 4 development now makes sens

[Isao]

Interestingly, much of the hardware design done to accomodate cryptographic work is finding a new life in bioinformatics, where some of the same problems exist (pattern matching, sieves on huge amounts of data, etc.).

Re:Something similar at the recent RSA conference?

[Thagg]

No, what was being done at the RSA conference was completely different, wonderfully practical, and available today. It's a way of cracking RSA and DES implementations in smart cards using Differential Power Analysis and Differential Fault Analysis.

There was a company at the conference that was cracking these codes by very carefully watching the power levels on the input traces to the chip. By careful analysis, you can see exactly what is happening, what numbers are being sent to the various S-Boxes in DES for instance. From this, you can determine the DES keys. They said that single DES took a couple of minutes, triple-DES only three times as long. They claimed to be able to crack RSA as well.

Differential Fault Analysis involves giving the wrong voltages to the chip, and seeing how, and when, it fails. Again, this provides clues to what numbers are being processed within the chip.

Neither of these flaws point to problems with the algorithm, but to problems with its implementation. In fact, creating inexpensive physical hardware to do secure cryptography may be impossible.

What was remarkable at the RSA conference is that most of the other booths at the trade show were selling these same smart cards, in abject denial of their flaws.

thad

Re: Number of PIM... modules?

[Raetsel]

262,144 didn't make a lot of sense to me, so I figured it as a power of 2 -- 2^18th. Odd. It also counts for 512^2, or 4 banks of 2^16th. Only somewhat more logical... but it still doesn't make much sense to me.

The choice of number seems... unusual. Is there some special signifigance or particular reason for that number? Any ideas on how this particular approach would be applied? (Am I missing something, or was it just that point where the economy of scale was most favorable?)

It wouldn't /win/ a Nobel Prize . . .

[himi]

But it'd be a discovery at the same kind of level that /would/ win one in a field where a Nobel was offered. Which is what I meant - "Nobel Prize type stuff" doesn't mean it'd win a Nobel Prize, just that it's roughly equivalent.

himi

My boss said rot-13 might be crackable!

[Skapare]

My boss said he heard that rot-13 might be crackable! So I told him to switch to triple-rot13.