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.
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
Actually, I guess that's not entirely true... it's not really a brute force keyspace, so you'd get more than 1 bit for the doubling in cpu, but you wouldn't get double the bits.
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,
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...
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
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
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.
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!"Wow! So if I only need to crack 128-bit keys I only need to spend something like $1.93831e-258! I can't wait to get started.
"Prefiero morir de pie que vivir siempre arrodillado!"
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"
The importance here is that if your company is guarding, say $10 billion worth of data using 1024 bit encryption, you should be worried whether there might be competitors capable of spending $1 billion to steal that $10 billion. There are drug companies, banks, and research organizations for whom this is not an imaginary threat.
Also, I think that putting a price tag on breaking 1024 bit encryption definitely qualifies as news for nerds. Who else would want to know?
"Who is the Journal of Quantum Physics going to believe?" --Stephen Hawking
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.
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.
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>
:)
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.
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.
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?
$67 billion
If you've been properly trained in US politics, the phrases "Won't someone please think of the children" and "National Security" should pop into your head immediately.
Why are we worrying about one billion dollars when having the capability to factor 1024-bit RSA keys could save children's lives?!
Yes. Use Euler's Theorem, with the extensions by Miller and Rabin. Sorry for being so humorless today.
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.
First, it's not that the gov't is cracking encryption of bank systems so they can steal money. The cost of cracking encrypted messages from terrorists, countries they don't like, etc. using this technology would be less than the cost of other intel methods, i.e. getting someone on the inside, not to mention the intangible cost of a human life if an agent were compromised.
Second, if you'd read the e-mail on Security Focus, the estimated price range is several hundred million dollars to about 1 billion dollars, lower if they have access to a chip fab. It also mentions that the NSA and several other countries' intelligence agencies have their own fabs. So it's not as prohibitively expensive as it sounds. The e-mail's author goes as far as saying The NSA would have to be derelict of duty to not already have built such a decryption device.
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.
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
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.
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
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
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.
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.
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.
SUPPOSE there's a US Govt agency with $1B
The Department of Defense gets $303B a year.
See the official budget of the United States Government for 2003.
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?
IIRC, each Stealth bomber costs about a billion dollars. Given the tradeoff between buying a new Stealth fighter, and knowing where to put my current Stealth fighters before my opponent has got a chance to move his armies, I'd pick the latter.
I wish that bum would get back to work and finish Qmail 2.0!!
Edith Keeler Must Die
MR does not prove primality. If you assume GRH, then by running MR O((log n)^2) times you can prove primality, but that is impractically slow even for 1024-bit primes.
All large provable primes are constructed in special forms in order to allow use of one of several fast proving algorithms.
Tarsnap: Online backups for the truly paranoid
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....
In this case you would not.
What Schneider has overlooked that the machine in question is not a general purpose parallel machine. It is a specialised simple numerical unit matrix with flat memory architecture. Such beasts with up to 2^16 CPUs have already been designed and have been used for more then 10 years in processing of satellite data. All that is needed here is to up the numerical capabilities of the singele unit, up the number and up the memory interface bandwidth. It is something that can realistically be done in 3-5 years.
Still, it will remain a relatively specialised beast. The specialised 2^16 parallel hardware used for sat image processing has not depreciated over the last 10 years. Neither will this hardware because it will not become a commodity.
What is more worrying is that bernstein's model is close to the hardware model of the latest cray proposal (large number of CPUs on flat memory). And this is a commodity machine that money can buy now to be delivered tomorrow. It will not give you as much as the 1B price tag specialised hardware but it is sure worth a try.
Baker's Law: Misery no longer loves company. Nowadays it insists on it
http://www.sigsegv.cx/
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
While it's not going to be on the same price curve as high-volume PC production, there are still Moore's Law effects here - the price/performance of FPGAs and ASICs keeps decreasing as technology improves, and the price of smaller-width chip design keeps improving. The real question is whether the development of this sort of machine can piggyback on other hardware development, plus how motivated is the NSA to build it as further research indicates whether or not it will be really useful...
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
Your Visa number probably isn't worth spending a $1B to crack, so you don't need to worry. Visa, on the other hand, has to worry about millions of credit card numbers getting stolen, though it's still much easier to crack into most of the machines on the web that absorb credit card numbers, and if there's one master key that lets you steal all of Visa (I doubt there is), it's probably easier to find the people who have parts of that key and bribe them (if you're the Mafia), or subpoena them, if you're the sleazy bunch of thugs at the DoJ who just filed a "Go Fish" subpoena on Visa and American Express.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
Diffie-Hellman and El-Gamal are closely enough related to RSA that you don't get much diversity by picking them. Elliptic Curve is a nice possibility, though it's possible somebody will find the math to crack that. NTRU is a lot different - I don't know that any of the academic cryptographers are calling it really secure yet, but the people who've looked at it don't seem to be calling it "snake oil" either.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
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.
Until they actually do it I dont think anyone shoud even care
How will you know when someone builds this machine and starts actually cracking the encryption? Do you really think 'they' will advertise the fact that they can factor keys in minutes? I find it more likely that 'they' will just quietly read the encrypted messages they want to read - from their point of view the longer people stick with key lengths they can crack, the better.
The general point is - the safest thing to assume is that once something is theoretically breakable in a practical timeframe, it is broken. Assuming that we will find out when a practical implementation is available seems a little naive.
Dan.
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
Yes! The machine doesn't attack RSA per-se but is a speed up related to the more generic NFS algorithm. NFS similarly works against DLP based problems (e.g. Diffie-Hellman, Elgamal etc).
"Mary had a crypto key, she kept it in escrow, and everything that Mary said, the Feds were sure to know."
Diffie-Hellman, El Gamal and other similar DLP based algorithms will also be affected by this NFS improvement.
"Mary had a crypto key, she kept it in escrow, and everything that Mary said, the Feds were sure to know."
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 --
Yes I can prove they are prime. Well, I can prove they are Newton primes anyway. Meaning if I say it is prime, I'm right most of the time. When I wrong, it won't affect the quality of my encryption (that we know of, though someone that is newton prime, but not prime is belived the reduce security, nobody has proved that to my knowledge)
For those that would die defending it, Freedom
has a sweet taste that the protected will never know.
I don't quite understand your question there (running through DES with unknown key... extra encryption reducing security) but I'll try to say something helpful
Ok, I'd better disclaim IANACE (crytography expert). I've studied the subject at university level so I know the defintions and have read the facts but have done no analysis myself.
Cracking DES-64 is "easy". Now which is harder to break of these two? DES-64 performed twice with two different keys or DES-128? As it turns out, both are using 128bits worth of key. I would rather use DES-128 on principle since 2^128 is a big key space and current DES breaking difficulty is in the order of brute force as far as I know.
Now what about DES-64 twice? Well, as it turns you might be safe with DES (because I think some people have found it is not a group) BUT suppose we weren't using DES but a symmetric algorithm that *is* a group. Then the hacker could just do a brute force attack on your code with a *64* bit key.
The thing is, I am just touching the surface here. In this case, I have showed that layering using the same cipher that is a group is BAD. Now you could argue, different ciphers etc. etc. but that *may* introduce weaknesses. To know, you would need to analyse it! But why bother when DES and the like have already been analysed to death so you can be fairly sure you are safe at larger key lengths
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.
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!