Slashdot Mirror
1024-bit RSA keys In Danger Of Compromise?
antiher0 writes "According to an email from Lucky Green that came across bugtraq yesterday, 1024-bit encryption should no longer be considered pristine. Bernstein released a proposal that outlines the creation of a machine capable of breaking 1024-bit crypto on the order of minutes or even seconds for the measly cost of ~$1B USD. For a more thorough discussion, check out the original email."
Update: 03/26 03:16 GMT by T : And don't forget to revisit Bruce Schneier's analysis of Bernstein's claims, which cast doubt on the practicality of breaking such large keys anytime soon.
for the measly cost of ~$1B USD.
Is the company you work for hirring? God I wish I could call a billion dollars measly!!
iRepairIT - iPhone, Mac, & PC Repair
Here?
The basis for this story was on slashdot almost a month ago. A repeat? something derived from the previous story's information? the key point here is Bernstein's paper on factoring huge numbers, about which some people have commented, and which appears to "work out" on a mathematical level.
Does this mean for $2B they could crack the 2048 bit key?
but the FBI cracked the 1024 bit encrytion on my box and I was being questioned all day about me using decss to search for (using cat recogniation aligrims (sp?)) those single frame ads in popular movies convincing that "Microsoft is not an monopoly".
At this rate I think this machine should be afordable in around 5 years...
That's okay.
I'm certain that qcrack will be poorly documented and require the addition of 5,000 users to whatever supercomputer it happens to operate properly on.
Then DJB will speak incessantly about how it differs from other encryption cracking techniques with its "modular design" (which is actually the application of many patches in order to obtain features found in most SMTP daemons, err cracking programs). Yeah.
(Disclaimer: I love qmail.)
You got a great machine to be built w/taxpayer dollars on the cheap and quick.
It is way easier for you to move up a few orders of magnitude of encryption than for them to build a machine that can crack it.
However, this will mean a bigger supercomputer for all kinds of numbering tasks - basic research and math, physics, and astronomy will eventually benefit.
Goat sex free since 2001
The point is, what's $1B to a major government?
Considered harmful.
Don't waste your money. I'll sell my company's secrets for a fraction of that.
Here's the link to their write up, commenting on Bruce Schneier's take No Big Deal .
Anyway, we all know they've been reading our sekrit kees by telepathy for years now, right?
Hexayurt - open source refugee shelter,
I felt like 4096 was too much so I went up to an almost weird number.
Get your Unix fortune now!
If you can come up with a brute force approach to common encryption schemes, could you not stay one step ahead of something like this by utilizing multiple layers of encryption, with differing methods of encryption at each level?
Give that a brute force attack is orders of magnitude more computationally intensive than the original encryption, would this allow you to stay ahead of the curve?
Also, although the papers seem to indicate that the proposed system could try multiple forms of attacks on the encrypted data, would modifying or customizing the encryption algorithm at each layer of encryption help? Computers are great at brute force attacks, but I highly doubt a system such as this proposed one can do much in the way of analysis or reverse engineering of the encryption algorithms used...at some point, you'd have to resort to good old (and slow) human deduction...
a $1Billion dollar machine does not mean that it is broken.
Sorry but theories does not equate broken. Until they actually do it I dont think anyone shoud even care. Hell eventually 1gigabit encryption keys will be broken.. Me? I plan on using a 12 terabyte key to GPG sign all my email.
I certainly am getting sick of the "tabloid news style" that Slashdot is using lately.
Do not look at laser with remaining good eye.
i think he's plural
if you were a government agency with $1b to invest in some kind of anti-terrorist encryption breaking scheme, would you invest it in this or would you invest it in quantum computing research?
would it be worth going for the brute force attack or would it be worth finding a different solution? not to mention how much money you could win and how much cancer you could cure with the idle time.
free (as in mp3s) electronic music
Everyone needs to host their own email system. You send someone a response by hosting the response on your machine. In doing so you can prevent more than 100 attempts a day.
This method is flawed. It's strong, but as CPUs get faster you have to increase the keylength ever more and you're fucked, basically. Hosting messages yourself means you can control access in a far smarter and more fine grained way.
--Giving to trolls for the benefit of us all
That would be roughly 200,000 nights of "Intimate Services"... and we're not talking about skanks, neither - not at those prices.
I think the Cryptic Seduction approach is looking pretty good, huh?
Hexayurt - open source refugee shelter,
1024 bit, of course, is 2^1024 (approx 1.797e308). If you add one more bit (2^1025), you double the possibility of the number of keys, which means you double the computation time... In theory. This assumes brute-forcing it, and that the time it takes equals the maximum theoretical time to break it.
:)
2^2048 is 2^1024 times more than 2^1024 (that is, it's 2^1024 squared). Meaning that to crack 2^2048 - in theory - it would take roughly 1.797e308 times as long to crack.
More numbers: If this $1B computer could crack a 1024-bit key in one second (consistently), it would take 5.7e300 years to crack a 2048-bit. That's much longer than the life of the universe.
All this stuff is theoretical, of course. That's why you don't try to break the encryption, but rather look for holes in the software, or post-it notes on the monitor
-Xyphoid
If you want something to be *really* secure, you gotta write it on a sticky note and hand it to the addressee.
RC5 is not a public-key algorithm and has nothing to do with factoring, so this is irrelevent. Factoring is of importance only to RSA and similar algorithms.
It's hard to be religious when certain people are never incinerated by bolts of lightning.
of this machine being utilised by ILM, pixar, or even id software..
computers that could crunch number that hard have just GOT to have a viable future in the entertainment industry.
surely these people can pull together to build me one.. um, I mean, build one to produce nice things for us to look at and play with.
it's make a hell of a chess player too.
The reason girls and Windows users don't understand UNIX is because all the documentation is in Man files.
Don't any of you bozos pay attention to prior articles? Security is about risk management. If you have something to protect that is worth $1bn for someone to steal and the only protection you have on it is 1024-bit crypto, you deserve to have it stolen.
Your homework for today is to (re)read Secrets and Lies. There will be a quiz.
The US government recently relaxed export regulation for public key cryptography to make it the same as the domestic restrictions. The reasonable implication that we can take from this is that they have a way to crack that length of key, or they know they can do it, if they really have to.
Either that, or the American government suddenly have benevolent feelings to the rest of mankind and a minority of their software community. Yeah right.
-WolfWithoutAClause
"Gravity is only a theory, not a fact!"I mean, it's getting to the point where the dang keys are gonna have to be longer than the message!
-- Alastair
I think the government (mainly NSA) had always had the upper hands in terms of encryption no matter how good it is. 1024 is probably nothing for those supercomputers and holes in various OS.
kawai
Why? For putting his revoked keys and new keys into his Bugtraq message. Okay, it's putting your money where your mouth is, in one sense... but it was also one damn big chunk of noise, much longer than his (reasonably long already) text.
Bad form. I'd expect more class from someone who's claiming to be clued.
"Ain't no right way to do a wrong thing."
That intro is deceptive at best and is, well incorrect. Remember DES and other symmetric ciphers that currently use about 128-bit or so encryption are unaffected by this. Certainly, 1024-bit symmetric encryption (your typical secret password encryption) is going to be unbreakable for centuries based on current predictions. The intro should read asymmetric or public key encryption at 1024-bits
Secondly, the advances being talked about are in factoring large numbers into their prime factors using the Number Field Sieve (NFS). This algorithm is the most advanced known factoring algorithm and if you believe the article improvements show that factoring 1024-bit length primes is doable for 1 billion dollars or so. (It was only a few years ago this kind of cost was attached to building a DES cracking machine... today I could probably crack DES on my uni computers given the software. 1024-bit factoring is only a matter of time before it is easy). However, not all public key schemes rely on the difficulty of prime factoring. Elliptic curves rely on a different hard problem
Conclusion, the intro should read "1024-bit asymmetric encryption that relies on the difficulty of prime factoring (e.g RSA) should no longer be considered pristine"
Guess I'd better stop using IPSec and SSL, now. Seriously... What are the implications of this? This is certainly not meant to disuade people or organizations from using RSA based exchanges, but rather to encourage them to increase the key sizes. As difficult as it is for modern servers to deal with high-loads of 1024bit RSA, does anyone really thing that 1536 or 2048 is going to catch on anytime soon? Saying it will cost a billion USD to crack 1024bit RSA is not much more prohibitively out of reach than suggesting businesses move to bring-them-to-their-knees 2048bit RSA. In moderation, not a problem, for hundreds of thousands of transactions day - better grab a heaping handful of Broadcom 5821's.
Think of it as an investment. It's not like the machine will explode after its first success, so you can recoup the cost over time.
For instance, if a major government or other well-funded entity not averse to a little corporate espionage managed to intercept and decode information regarding, say, bids on major contracts, it could pay for itself very rapidly.
Only the dead have seen the end of war.
I'll sell them my encrypted secrets for only 1 million dollars!
It's a win-win situation, I get a million dollars, and they save many many millions of dollars.
how much is Bill Gates worth now?
To whom?
-- Alastair
When it came up before, there was a significant question about whether the improvements would be seen in key sizes that we are using, or whether you needed larger numbers. The conclusion of Schneier etc was that it probably didn't affect factorization of numbers people are using, though it was good research.
What is new is that people have now gone out, implemented it, and found that it really does come up to a big factoring win in the ranges of numbers that are in use. Furthermore based on real factoring examples, 1024 bit keys are doable at costs within the reach of national security agencies.
There is a difference between theoretical improvements somewhere around a million bits, and demonstrated improvements at 512 and 1024.
Take a look at Lucky Green's new PGP public key at the end of his message. Geez, is that thing a key or a keystream? I have this funny feeling we may be taking a good idea too far...
Sigmund
Ah... the old security through obscurity notion. Someone else can carry the debate here but trying to get security by trying to hide what layers of algorithms you are using is defeating the point of security research. A "secure algorithm" is basically one such that it does not matter whether the hacker has access to the algorithm or not. Cracking a "secure algorithm" should be as hard as cracking by brute force. If your security relies on obscurity, then you are asking for trouble in general
As for layering in general. Well it works for the most part (e.g 3DES) although there are caveats (2DES would not be safe). But the real point is that layering is slow. Doing 1024-bit RSA encryption is slow. And try generating a 2048-bit key instead of a 1024-bit key. It takes ages (possibly minutes on some computers). You may be increasing security but decreasing performance.
Now going back to the first point about a "secure algorithm", you are better of say doubling your key size and exponentially increasing the keyspace on your existing algorithm then either inventing your own layering scheme that may or may not work AND will be slow nad memory wasteful by using many algorithms. The short answer is, you don't need layering, just make larger keys.
People seem to be forgetting that there is a known algorithm for factoring in polynomial time. This is the Shor algorithm for quantum computers. The governent has put billions of dollars in to this research, it would be entirely prudent to assume they have working machines that can crack any key length.
I can picture the scenario now:
<TELEPHONE CORRESPONDANCE>
SHADY GOVERNMENT OPERATIVE: So how much will this 1024 decryption system cost?
PIMPLY TEEN HACKER: $1B US dollars to be deposited into my secure off-shore bank account and safe passage to the Maldives.
SHADY GOVERNMENT OPERATIVE: Excellent. The money is being transferred as we speak. Begin work.
</TELEPHONE CORRESPONDANCE>
<PIMPLY TEEN HACKER INTERNAL MONOLOGUE>
Sweet! I've just charged the US government 1 billion dollars for a beowulf cluster of dreamcasts running home-brew linux.
</PIMPLY TEEN HACKER INTERNAL MONOLOGUE>
<SHADY GOVERNMENT OPERATIVE INTERNAL MONOLOGUE>
Sweet! We will retrieve the 1 billion dollars once we crack the secure off-shore bank account's 1024 bit encryption system
</SHADY GOVERNMENT OPERATIVE INTERNAL MONOLOGUE>
:)
--cut an paste from a random joke site---
Q: How many Bill Gates' does it take to change a light bulb?
A: 15 to develop a bloated software prototype, 8 to write a horribly designed and overly complex non-contextual help system. 34 to author the help text, 122 to write the various SDKs and interfaces so that the lightbulb will work in conventional sockets, 67 to create demeaning adds that belittle other's bulb-screwing attempts, and 4 to write a lengthy book on the process.
Buying a Dell computer is equivalent to dropping the soap in a prison shower.
Damn Moore's Law
I want my rights back. I was actually using them when our government stole them after 9/11.
Terry Ritter, a really cool guy on sci.crypt, who happens to be a cryptographer suggests using a known algo along with a new algorithm. The tested algorithm (such as blowfish, or DES) provides security against known attacks. The new algo (such as the AES candidates, or something your best friend coded while he was drunk.. joking) can provide an extra layer to thwart cryptanalysis. Just use different keys for each step.
I love crypto, too bad I'm going to wind up as a crypto-narc one day.
Yeah, very useful analogy.
I can't imagine how big 2^256 is, but somehow I can picture the number of electrons in the universe.
Okay, I've been hiding my idea, but who cares. I'm releasing it now and officialy proposing the creation of a machine capable of breaking 2048-bit crypto on the order of hours or even minutes for the measly cost of ~10B USD.
I'm currently soliciting offers from several major tech companies to fund this joint venture to be used only in the private sector.
Please call now.
Actually Bernstein says that he does not expect his factoring device to have any significant speed advantage over other factoring techniques for "short" keys, "short" being significantly more than 1024 bits.
The reason is that the speed up is asymptotic with a suspected slow convergence.
But I agree that for security critical application 1024 bits is too short, even if only because there is not enough safety margin.
Find the paper by D.J. Bernstein here.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted and ignored otherwise.
So THAT's what we've been imagining all those beowulf clusters of machines to do...
like the topic says... Shouldn't we be spending the money on more useful things rather then trying to prove 1024bit keys can be cracked? We know they can with enough horesepower.
Brielle
OK -
SUPPOSE there's a US Govt agency with $1B
SUPPOSE that $ is in a black budget
SUPPOSE they built this thing.
So...
Exactly WHAT is an agency of the US Gov going to crack
that will allow it to gain exactly WHAT money
to amortize it's $1B
that won't be missed?
"Win treats sysadmins better than users. Mac treats users better than sysadmins. Linux treats everyone like sysadmins."
Hey, I've got a much worse problem to report: Most people don't use encryption!!! Right now, we're all browsing slashdot, our credentials sent in plaintext, our sessions open for anybody to see! Almost everybody sends unencrypted e-mail!
Rather than freak out about the NSA being able to crack 1024-bit keys, maybe we should be doing more to actually get encryption used by people?
Only a billion dollars of the taxpayer's money to read other people's mail? The U.S. government will take 10.
Bush's education improvements were
he sais that the article referenced by slashdot has caused him to re-examine the CUMULATIVE effects of a number different recent development, not just the Bernstein paper
This is why I use 1025 bits. Suckers.
You mean the Google distributed computation feature enhancement to the search toolbar can do all that?
----- Whats wrong with this picture? http://www.revoh.org:1234/whatswrong
According to an email from Lucky Green
That key of his seems awfully long. Sure enough, when I pasted it into a text file it was 46 kilobytes!!!
There must be something else in there besides the 2048-bit key, but what? Is the first part the public key, and the rest the encrypted message?
For all intensive purposes, "whom" is no longer a word. That begs the question, "who cares"?
Where's the one that tells you to flip the light switch off and on a few times?
BILLION... well if you really want a 1025 bit haircut... 90K-140K which is about 2^16 soooooo your hair can be considered 16 bit... this means that your hair can be given a haircut in .0000000000000387142 of a second... btw that doesn't include the shave...
unzip; strip; touch; finger; mount; fsck; more; yes; unmount; sleep
$67 billion
at least someone got the reference.
(office space, of course)
free (as in mp3s) electronic music
For all you people who thought the plot of Sneakers (1992) was just silly and impossible... well, not so silly now is it?
unless you count those that order things online, use ssh, run encrypted VPNs...
----
All of whose base are belong to the what-now?
Why do people use small sized keys? Because encrypting with them is faster. Presumably, this ability to break small keys comes in part because of cheaper hardware. Well, guess what? Normal consumers (without a billion dollar budget) can buy faster computers for less money now too! Make bigger keys - it won't take so long now...
Before people go crazy like "Ooh my gosh, I need to use 8192 bit keys" you should read "Applied Cryptography: Protocols, Algorithms, and Source Code in C" It is hands-down the best book on the topic I have very found. Here is a link to it on amazon:
[here]
Oops, Mr. Smarty Pants! I can factor 1024-bit primes for $0!
But can you prove that they are prime?
Will I retire or break 10K?
Extra caution never hurts, does it. Esepcially when using a 4096 bit keys only takes an extra few seconds of computer time these days. If it isn't painfull to use, then the stronger the crypto the better.
---
the pen is mightier than the sword, the sword is mightier than the court, the court is mightier than the pen.
Prime factorization, last I checked, is not proven to be NP-complete. Thus, it is not known if it, along with elliptic curves (a whole different class of problems that I know just about nothing about) are reducible to each other.
NB: prime factorization has had algorithms published (Shor) which are polynomial time, with the caveat being that a quantum computer must be used.
Everyone here uses gpg or equiv for your email right?
As a member of several mailing list most people do not even have gpg signatures, those that do never upload their public keys.
Breaking 1024 bit encrytpion isnt that big of a deal for most people.
I guess they like running naked through public parks.
Get a free ipod.
The person who builds this machine may still underbid you. The machine doesn't just crack your secrets -- it's reusable. When you amortize the gigabuck over all the different people who need to be spied on, it may yet work out to be less than your minimum bribe.
As copyright owner of this comment, I authorize everyone to defeat any technological measure which limits access to it.
One thing to consider is that rigorous threat assesment is based on CAPABILITY, not INTENT. Clearly it seems that there now many organizations that may have the capability seriously compromise a significant and growing part of the world economy.
It doesn't cost the bad guys a billion dollars to steal your secret. It costs them a billion dollars to steal the secrets of everyone who uses the type of key the machine can crack. Your share might only be worth $10000 and it could conceivably still be worth their effort to buy/build the machine. Then you lose.
Your argument only makes sense if they have to dedicate their billion dollars to just cracking one key.
As copyright owner of this comment, I authorize everyone to defeat any technological measure which limits access to it.
- Good work agent ! Now, what did the message says ?
- Well it's.. *cough* a chocolate cake recipe *cough*
Well, a pricy recipe though... $1B USD for.. oh well.. :)
but if 1024 bit crypto only takes a minute to crack then theoretically during the 3 year life of this 200million to billion dollar machine. /60 minutes
$2e11 to 1e12 / 3 years / 365 days / 24 hrs
This means that all of your assets between 124,000 (if machine costs 200 million) and 634,000(for 1 billion) and above are all worthwhile "investments" of this machine's time.
Thank god I'm poor
Didn't he created his own proprietary version of the light socket and tries to make it "standard" as well as the light itself ?
We are facing some big challenges right now. Due to the crazy growth of computing power (despite the fact that new methods of calculation - factoring large number and stuff are constant being developed) Encryption standard are being obsolete faster than we can adapt to it.
Think about how long the US government will take to adopt AES.... Same encryption are going to get weaker and weaker as times goes by, we have to adapt to the rate it fades out. But apparently, encryption standards takes time to develop and get accepted. We are very likely going to change standards every 5-10 years. Government agencies, are you coming along?
What do you see in the post that is inconsistent with this view? It claims that the cost of breaking 1024 bit keys is lower than previously believed. This means that risks must be reassessed.
If you have something to protect that is worth $1bn for someone to steal and the only protection you have on it is 1024-bit crypto, you deserve to have it stolen.
Guarding a $1B asset with a 1024 bit key would be foolish, with or without this finding. (For starters, the enemy doesn't necessarily have to build a cracker, they just have to rent time on one.) But who says we were talking about a $1B asset? Trivially, there exists some scenario in which 1024 bits was a good risk prior to this finding, but is no longer. So this finding is entirely relevant to a risk management approach.
The evaluation of an action as 'practical' . . . depends on what it is that one wishes to practice.
Each bit that you add roughly doubles the amount of time it takes to crack. 2048-bit encryption, although slow, is possible.
What this means is that, assuming that a 1024-bit key can be factored in 1 second, it would take roughly
57004475357125694689539104223396268823502567825
5466151385601004275993538836
5721983584043465919703756942
8489528438551201241199355703
7710357939232321268887397337
years to crack 2048 bit encryption. I'm not all that worried.
"But really, I think life is just a game of Mao Nomic." -Purplebob
-- ;-)
Kuro5hin.org: where the good times never end.
Did anyone notice this: if you open up the original email linked in the post, then scroll down your browser really fast until the end of his PGP key block, you can make out the word I AM PARANOID -in his PGP key block- ??
The Wknd Sessions - Malaysian and South East Asia independent music
..., folks, to re encrypt yer private files, that floated around the net for years with larger keys, before they....
doh!
And how do you propose the recipient reads it from the sender's machine?
Send the message to the recipient in plain HTTP?
Get the recipient to walk all the way to your hosting site?
Your self host solution doesn't solve that problem. Or is incomplete at best.
Suppose some agency actually did build a machine that could crack 1024-bit RSA. How would they use it? The answer is, they would keep it very secret and use it only on very important stuff---nuclear threats, etc. They would certainly not risk revealing it's existence to crack small cases.
How many tyrants and dictators around the world would think NOTHING of squeezing their own countries $1B harder in order to crack the communications of dissidents, opposing political parties, and oppressed ethnic minorities?
ObDisclaimer: this isn't some pinko commie "FUCK YOU AMERIKKKA!" post... it's just an observation that I haven't yet seen made by another poster in the thread. I see a lot of people talking about the NSA, and breaking into banks, etc etc... but middle-class white male citizens of post-industrial western economies aren't the only people who have good reasons to use crypto, you know?
-----
PGP Key ID 0xCB8FF658
Take a look at the size of the key in the original e-mail! 46080 bits by my count (no, i didn't actually count, perl did). But if that isn't subtle irony, I don't know what is.
ha-HA!
__________________________________________
Take comfort in your ignorance.
Grandmaster Plague
point is, you can still crack public-key ciphers one at the time which doesn't give you much more security. however, for secret-key stuff it's a completely different issue as you need to break all of them at once.
I'll just pay Guido to torture your ass for $10,000. There are other ways of extracting information . . . ironically brute force is an option in both umm professions. . .
Sort of off topic, but honestly, the investment (for the machine) isn't worth it unless you plan on doing this a lot of times, and if somebody was going to do this on a case by case basis, it would be cheaper to hire one of Pol-pot's henchmen to do the job.
1q2w3e4r5t6y7u8i9o0pqawsedrftgthyjukilo;p'azsxdcf
However, in a follow-up post to the cypherpunks mailing list, Ian said that he did not agree with the calculations.
In fact he says that the physical properties of the factoring machine seem "implausible", and that there is no reason to believe that the result applies to "real" key lengths like 1024 bit keys.
The depressing thing is that probably a few goverments seriously would like to spend $1 billion to try to read something in an RSA encrypted format.
.DOC and produce software capable of reading it. A much, much easier problem but one that hasn't been done completely.
Yet despite all that money and zillions of man-years being blown on reading stuff in such a format, no one has managed to go out, and no one is willing to spend the money to try to crack
There are so many *smarter* things to blow money on than cryptography that it blows the mind. Cryptography is a fun mind game, but frankly when this much money is being spent on it it's just ridiculous.
You can bribe the people involved for less than $1 billion. Heck, buy up a private army and take over the building that has the information that you want.
May we never see th
2,048 bit encryption!!!
:-P
Anyway, I think people are being too paranoid about the guvament.(pronounce in brain as paraniod Idahoan KKK heavily armed militia seperatist guy)
You think they would use a 1 billion dollar machine to see your internet credit card transaction to purchase a gay beastial midget pr0n website subscription?
No, they aren't going to use this on weirdo perverts like yourself. They will use this to decrypt important things, like Taliban and PLO communications and whatnot.
Anyway, its not like crackers, with malicious intent, would go buy themselves a 1 B dollar supa-puter to intercept your midget pr0n transaction.
So quit being paranoid, and go back to jacking off to your gay beastail midget pr0n.
If you don't understand any of my sayings, come to me in private and I shall take you in my German mouth.
It is generally regarded that the NSA and the military have technology that is about 20 years, yes 20, ahead of what is publicly known.
The NSA has the budget to hire the best and brightest mathematicians money can buy. Whose to say that the NSA hasn't know about this for years? Sure, Bernstein could have simply "rediscovered" what the NSA has known for years.
There have long been rumrors of a $2-3B machine that the NSA has for breaking encryption. Taking time into account, that translates to that $1B machine now.
The NSA has likely been able to break these keys for years.
No, both you and the respondees are wrong.
The reason that 3DES works is that DES is not a group. That's a mathematical notion. I cannot explain it here. Read up on the lit. (Schneier, Applied Crypto is a really good start.)
Basically, most dumb encryption methods are additive - you cannot expect that encrypting once, and then again with a different method means the attacker will need to reverse the process. Many times, it is simple to defeat both in the same process. CF, again, why DES is not a group.
There are many methods that are _not_ additive, and still are a group. That is, you're not saved by making sure you're not a conjuction of mathematical ejaculate.
Crypto is _hard_. Really hard. Get used to it.
-j
I forget what 8 was for.
Even Bernstein's original paper is clear to point out that while his mathematical results are correct, and that his proposal does allow RSA keys of size n bits to be factored in the time we currently think it takes to crack keys of size n/~3.009, he proved this to be true *only in the asymptotic case*!!
This means that for very, very large n Bernstein's results are known to hold. His paper is actually a grant proposal requesting funding so that he can spend the next few years finding out if it's possible to apply the same techniques to practical-sized keys. As I understand it, what Bernstein wants to study will still be purely theoretical. He wants to calculate what the savings factor is for smaller keys. The reduction factor for smaller keys may be as large as 3, or it may be smaller but still worthwhile, or it may be negligible.
Even after Bernstein has done his calculations for smaller keys (which will take years) the results will still be purely theoretical, and there will likely remain a great number of practical challenges in building the rather unique kind of hardware Bernstein is proposing. It's possible that even if the theory holds for smaller keys, building a real machine may still be impractical.
For more detailed discussion than you're likely to be able to digest, go read sci.crypt.
From what I've read, I would say that if you have secrets you need to keep for more than 5 years, you might consider using a 2048-bit RSA key, or switching from RSA to ECC.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
Then I looked at it with Wordpad, and realized I generated the source code to Microsoft Windows!
I'm Rick James with mod points biatch!
Heh. You thought I was buying this to get your secrets. No, that's just the icing on the cake. This baby's for LAN parties. Nothing plays Quake quite like it.
And there's the occasional corporate secrets to bust into once in a while. Ahhh.
Did I mention Pac Man?
Donate background CPU time to fight cancer.
good one =)
i just climb trees, and look for rhythm everywhere.
Please see this posting:
2 25 829
http://slashdot.org/comments.pl?sid=30026&cid=3
(or scroll down and read it)
I wish that bum would get back to work and finish Qmail 2.0!!
Edith Keeler Must Die
I'm afraid that this story is altogether misleading.
:-)
When the paper first came to prominence, yes, it looked worrying.
However... the speedup factor appears only to apply to LARGE numbers, not necessarily to smaller ones. Exactly how much advantage one gets for smaller ones is unclear.
Note that this paper is a "research proposal", not a finished item of research. It's a very interesting read, nevertheless
However, if you're worried then you should be using 2048-bit original-style RSA PGP keys anyway (or 3072 or even 4096 bit new-style RSA keys). You might want to avoid the DH/DSS keys since the signature part cannot exceed 1024 bit....
This is the kind of story that could get huge exposure in "normal" news if there's nothing better to show. Just imagine the headlines: "Internet banking no longer safe"" "Anyone can steal your money when you shop online!" And noone would have an idea what's really going on.
Ciryon
At: $124,000 per secret.
In one hour I can crack 60 of those.
That's $7.4million worth of secrets each hour.
In a day I can crack 24 of those.
That's $178,560,000 worth in a day.
At your prices, the machine pays for itself in a little over a day.
The key to your problem is that $200 million is not $2e11 - it's $2e8
By my calculations, a $200 million machine could pay for itself in 3 years, if each secret was worth $126.
I'm poor - but I'm not that poor.
Read more of this story at Slashdot.Read more of this story at Slashdot.Read more of this story at Slashdot.
It'll really be interesting when they start to get to ~64-bits of resolution (at least if they don't run into Heisenberg uncertainty problems when the resolution approaches Planck's constant.) Will the resolution of this technology scale that far? But things don't get interesting for public-key crypto until you're at ~512 bits.
Also, there are some problems that quantum computers can accelerate and some that it can't. For instance, factoring is tractable, if you've got enough resolution, and there's a quantum computer that was able to factor the number 15 into 5 and 3. So RSA and Diffie-Hellman are toast, at least for 4-bit keys :-) Perhaps for much longer keys, if QC can be developed, but perhaps not. It's not clear whether elliptic curves can be cracked by quantum computers, but then, it's not clear that they can't be cracked by better mathematics.
Basically, if They can crack everything using public-key technology, you're back to private-key methodology like Kerberos, or traditional methods like one-time pads and guys with Kevlar briefcases handcuffed to their wrists.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
Is there any special reason all these key lengths are always powers of two? Does it have some sort of inherent advantage or is it just people's being geeky?
No, your children are not the special ones. Nor are your pets.
the commercial version of PGP (8.x something) defaults to 2048-bit keys.
What a coincidence.
Windows 2000 - from the guys who brought us edlin
Just a thought.
TWW
"Encyclopedia" is to "Wikipedia" what "Library" is to "Some people at a bus stop"
This is an attack on the web of trust. The author is spreading FUD to fool people into revoking their keys. If everybody follows his advice, the web of trust is gone, and it will take quite some time to reconstruct it. In the end, revoking keys based on such unsubstantiated threats will water the meaning of key revocation as a whole.
Actually, if the set and order of cryptology algorythms are chosen on the basis of the passphrase (like calculating a MD5 out of it and getting the info out of the number), it is not obscurity rather than a top level ordering algo.
Just a thought..
Another handy side-effect is that it may make the cracks themselves more difficult. It doesn't apply to breaking RSA (which is just factoring), but many of the best attacks for symmetric ciphers rely on having known plaintext - a file header, or whatever. Since the plaintext in this case would in fact be (hopefully) random ciphertext, the attacker's got a lot less to work with.
There are disadvantages, of course - you don't know that the two algorithms together are secure, and when considered as a whole, the chances are that they're not more secure. You're relying to a certain extent on the attacker sticking to the rules and considering the supciphers as subciphers, instead of just trying to cryptanalyse the whole mess. The other difficulty is that the more layers you add, the more key material you need - at a certain point, you begin to have trouble getting enough truly random data.
PenguiNet: the (shareware) Windows SSH client
~shiny
WILL HACK FOR $$$
See the archive.
I'll follow on although you sound like you know about the subject already. Firstly the cryptanalyst may well have more luck breaking the combined layered cipher than trying to break both individually The layered cipher may well be weaker! There is no law that says that if you perform two strong encryptions over a plaintext it is at least as hard as each encryption. This unknown is one reason against. (In practice, layering is "probably safe")
The next thing is that I strongly doubt that even DES will be "broken" ever. It has been under scrutiny for too long and the only successful attacks are based on brute force and require vast amounts of data for a known-plaintext attack. Brute force... what does that mean? 56-bit breakable today. 128-bit breakable tomorrow. 256-bit breakable... when there are more than 2^256 electrons in the universe! Which there aren't
We're talking about RSA here. RSA is a public key algorithm. One where you can give out your public key, keep your private key secret, and anybody can send encrypted messages to you, but only you can decrypt. If you keep your algorithm secret, it becomes totally pointless.
In general, layering can help, but doesn't always, and can make things worse if you are careless about it. But keeping the layering scheme secret doesn't help much - it's probably equivalent to only a few bits of key, and if it is cracked changing schemes is much tedious than changing keys (and that assumes you _know_ it has been cracked). Making up your own crypto is almost always a really bad idea.
rant
i thought of putting this in 'ask slashdot' to be honest, but here goes ... what kind of effort is required to invent a reasonably efficient language which of course only you and your confederates would be able to use. esperanto, es an example, required a mere *eight* years.
the advantage with this is that it requires practically no encryption, if any.
"jan? khlaz tuirt'kah dar gangan Mbou!"
any idea what it means? nope, me either. and if you want an example of how strong this kind of 'encryption' is, simply take a look at the puzzles linguistics has tried to crack over the years: Linear B, (Linear A is still a mystery), hieroglyphics, etc., etc. For an example of something which is *still in plaintext and not deciphered*, check out the Voynich Manuscript.
OK, I'm not saying that one can simply go off and invent a perfect language in a coupla weeks, but look at the pseudo-languages like Elvish, Klingon and whatnot. Ideas, criticisms, reactions??
Plus of course, if someone is holding a cattleprod to your crown jewels and you're standing in a bucket of water, it doesn't *really* matter whether u used gazillion-bit keys anyway...
nalfy
-- Despair is an operating system that ANY human being can run, sort of a psychological JAVA --
We keep 'discovering' that 56, 128, 1024bit encryption is 'not enough'. Well why don't we just go right on up to 16 megabit encryption and buy ourselves a few years of leeway before the US gov't finds enough money to catch up ?
-Billco, Fnarg.com
For those that would die defending it, Freedom
has a sweet taste that the protected will never know.
I use triple-4096 bit keys :)
So, if I'm trying to decipher something, I might well find it easier if I ran it through DES with an unknown key first? Why have I never seen that it any code-breakers handbook? (Of course, if the keys are non-indpendent, extra encrpytion may reduce security.)
Dan Bernstein has been yelling for the past few weeks since he published nfscircuit that his work does not yet apply to 1024 bit keys (or other "realistically" small key sizes).
In spite of that, stories like this one keep popping up, forcing him to defend himself from idiots who construct bogus straw-man analyses against points that he hasn't even made.
I would rather see Bernstein continue this work, and have knowledgeable people peer-review it, rather than see people waste their time discussing whether solar cells cost more money than AC power (an argument DJB had to get involved in on sci.crypt) and other such lunacy.
Correct!
:).
Also, if you think your privacy is worth $1B, just upgrade your key size
Regards
If you wanted to mask the fact that you were using 5ROT13 instead of 3ROT13, you could XOR the message after each application of ROT13. How would you write that?
5XORROT13?
Looks like something my old admin would have thought was a swell password....
I think it's likely that vulnerabilities will be discovered in some ciphers as better analytical tools become available. Layering ciphers can mitigate this problem, and it doesn't cost much.
-- ;-)
Kuro5hin.org: where the good times never end.
If the subciphers are independently keyed, the overall cipher is at least as strong as the weakest subcipher
;)
In almost all cases, yes. But not if the two ciphers are a group, for example.
Key length means nothing if you can find analytical attacks.
True also but one could just as well find an analytical attack in the combined layered cipher if a "poor" choice in ciphers is chosen
Basically, if I had to choose what cipher to use, I think it is more likely that I would make a mistake in choosing a poor combination of ciphers to layer than I would someone finding an analytical attack in a cipher that has been analysed for decades.
The fact is, both layering and key-growing are both valid and are both used. I just happen to prefer one over the other
5XORROT13
Damn... that's the combination on my luggage!
Buddy, don't forget about the dot-com crash. Property in London, England is now more expensive than in Tokyo, Japan, a few years ago this would have been unthinkable. So the pace of storage systems advancement has decreased. If you saturate an ADSL download pipe, then you can't fill a hard drive. 120Megabytes/hour ADSL download * 24 * 365 * 2 = 2,100,000 Megabytes if you constantly download for 2 years. So 2100 Gigs is the maximum hard drive size anyone would need unless there is an advance in technology and holographic 3D videos start to come to market, or ADSL speeds increase massively, which with Telcos screwed as they currently are and for the next few years with loads of dark fibre, and less than 1 percent of homes taking up high speed internet seems very unlikely.
A caveman dreams of being us, the incalculable power and riches. We dream of being Q, then what?