Slashdot Mirror
Weak Elliptic Curve Cryptography Brute-Forced
thegrommit writes "It seems one implementation of elliptic curve cryptography has been broken. It took four years to break a 109 bit key, but the contest sponsors (who provide encryption products for Cisco, Nortel and Palm among others) believe it's still impossible to break their 163 bit keys. The real question is, for how long?" Update: 11/07 01:59 GMT by T : Dan Kaminsky wrote to point out that the key here was really brute forced, and not broken -- that is, no fundamental flaw was discovered in the algorithm.
4 years for the 109 bit version (and that's with a massive, dedicated attack).... I'm willing to believe (barring some unknown theoretical advance, which is always something you have to worry about with all real-world usable cryptography) that the 163 bit keys are good enough for my data considering the exponential difficulty in attacking the longer keys.
It wasn't broken, it was brute-forced.
--
.... well I'd say itll be a long time - I have never even heard of elliptic curve security - and i am sure many others havent as well
If the NSA doesn't throw a fit and complain if you try to export/import it out/into the US, then it's probably breakable already. Notice how the US government tolerance level floats up pretty consistently a few years ahead of publicised code cracking?
To ka kar iko ogik dhako ma youre dhi omo pi e aora gi dapi; to dapigni oting'o gi dier wiye lilo.
Yuoreno olo pi e tago to yuoche mamoko omake ka gikete e thigo mar dhood dhako maduong' kanyo ema mon go luokoe kitundu.
Giluoko lwetene gi tiendene; giluoko fuondege e oigla, oswaro kata tawo, to ka ojadwar giluoke e agulu bende. To ka giseluoke, yuochego lute ebur.
Kiluto ng'ato e bur moro amora ok nyal ywak kata goyo koko nikech gikowe gi kwe.
Ji okuyo ka gikulo wigi piny, to jo mochungo osiro lew tong' piny.
To ka dhok pod ok odonjo e kul ok ginyal ike; gipero lowo, kata giumo bur gi pien kata thigo. Ka dhok osedonjo eka giike e kar saa apar ga ariyo ka chieng' podho.
Impossible seems like a pretty weird word to ever use in this sort of situation. "Very, very difficult" or "requiring technology or techniques in advance of what is presently available" might be more accurate.
Every year during my review, I just pray the words "slashdot.org" aren't mentioned.
by calling it Weak from the outset!
judging by your post, not very long at all
We've seen time and time again as encryption gets stronger and better that breaking the 'impossibility' of breaking it merely depends on the computing power available.
I wonder what they really mean by 'impossible'?
Oh yea! (insert Slashdot grumblings here)
Apple made use of NeXT's Fast Elliptical Encryption in their "personal security" element of OS 9, allowing basically any document to be encrypted and decrypted by the OS. Apparently they planned this for OS X as well, but I see no mention of it except as a future feature on their scientific papers page. I wonder if this will force them to reconsider such a relatively insecure approach to OS security?
Mrs. Peacock with a metal pipe in the kitchen
http://mathworld.wolfram.com/EllipticCurve.html
It was also use by Anrew Wiles in 1993 to prove Fermat's famous last thereom.
http://mathworld.wolfram.com/FermatsLastTheorem.ht ml
Enjoy!
It is nice to see that Monico is donating the majority of the prize money to the FSF.
/<en
The winner is giving 8 grand to the FSF. Monico, who took up the challenge to "raise awareness of cryptography", will donate the bulk of his prize money to the Free Software Foundation and the remaining $2,000 to two men whose computers helped solve the problem.
Basicly, it's just a delay mechanism that will let you transfer messages securely at a later time assuming you've transmitted equally much information securely already. So the question is, why don't you use the secure medium in the first place? Ok granted, you can send an agent out on a mission with an WEC and he can communicate securely with home base, but I mean for everyday use?
The typical idea about cryptography is to use a secure medium to provide the key, while using the insecure medium to send the data, because the insecure medium is much faster/better/easier to use. So I can meet you in person and get the key, or call you on the phone and verify your PGP (or GPG if you please) fingerprint (assuming you're not being wiretapped as well), and then use the Internet as a medium from then on.
The WEC "solution" would be to say a random sequence of 1s and 0s, then use those to decrypt the irc converation later, not really an option. You'd "run out" of the curve rather quickly. Oh, and quantum computing does as far as I know not affect encryptions based on elliptic integrals (which by theorem can't be solved analytically, but I suppose there could be approximations).
Since a 163-bit key is 2^54 times more complex than a 109-bit key, and it took 4 years for the 109-bit key, aren't we looking at at least 4 * 2^53 years, not even figuring in the elliptical complexity (which I admit I would need to read up on)?
According to calc.exe, 4 * 2^53 years is 36,028,797,018,963,968 years. Anybody want to start working on that one?
There is no such thing as a crypto key that is impossibile to crack. What it comes down to is how improbably it is to crack it. In this example, it took 10,000 computers 549 days to crack it and it's only 109 bits. At 163 bits, that's a doubling in difficulty for ever additional bit.
Just add a bit, and suddenly you've pushed off the efficiencies gained by moore's law for another 18 months. By going to 163 bits, you've got a good 80 years before the that key can be broken in the same time as this 109 bit key. Frankly I wouldn't be too worried about that problem.
As long as your crypto is good enough to make it too expensive to crack for those who might want to crack it, you've got no worries. And I don't see a lot of people out there able to throw together the 10K computers to crack a key who also don't mind wasting almost two years on the effort.
This sig has been temporarily disconnected or is no longer in service
The time is the most significant factor here. If this was military use, the 500+ days it took to break wouldn't worry anyone since any message more than a few days/hours old is pretty much worthless. If someone where more concerned about long term security, they could setup a system to refresh the keys on any encrypted data, say every year or every quarter.
We already covered this on slashdot. This is just Yahoo picking up on it now.
The truth about Scientology, Xenu, and you: Operation Clambake
What about their 163-bit encryption makes it harder to brute force than any lesser bit encryption? Why is is "impossible" to break whereas the 109-bit encryption is only difficult?
However, it wasn't cracked open. There wasn't a shortcut, a tragic flaw in the algorithm. Just time and computer power tossed at it.
I don't understand how people can trust their data to a simple cubic polynomial in x and y. This stuff isn't tangible. It's like hiding data in the 4th dimension or something.
Encryption is not a permanent thing; encrypted data is *always* vulnerable after a time. The question is how long the data is protected for, and this is a functino of time. Either an elegant method will be revealed, or a system (software and/or hardware) will be powerful enough to break it using a brute-force method. Note that for the brute-force method to matter, it has to be within a given time frame. (e.g. decoding a VISA number sent over the web within microseconds is useful; within days it is not)
cheers,
Andrew
Just because brute-force is an inelegant method of breaking encryption doesn't mean it isn't valid.
Brute force just gives a baseline against which other attacks can be measured. With a brute-force break, it takes the same amount of time to break one key that it takes to break any other. With a cryptanalytic attack, on the other hand, you only need to successfully attack one key as a proof of concept; once you've expended the effort to break one key cryptanalytically, you've broken the system and probably reduced the effort to break a key by a couple dozen orders of magnitude relative to the baseline.
Will I retire or break 10K?
Cryptography is (and I assume will likely always be) an arms race of sorts... You create a new cryptographic cypher and instantly there are people out there whom are willing (some for the potential prize money, most simply for the pleasure) to spend a great deal of time and effort to crack the encryption. The advent of quantium computers however is an interesting problem for cryptographers, as a cypher that now takes years to break will only take seconds/minutes with a quantium computer, once again the arms race is on, and I don't beleve that one side will ever prevail as the absolute end-all solution. As computers get more powerful and people become more savvy there will always be a new way to encrypt data, and a new way to break the encryption. As for me? I enjoy it, and I hope you do too!
Ji okuyo ka gikulo wigi piny, to jo mochungo osiro lew tong' piny.
That's just silly.
I'm just waiting for the dude in SWORDFISH to crack 4096 bit encryption.
"Not knowing when the dawn will come, I open every door." - Emily Dickinson
Slashdot is an English language board. When posting in a language other than English, please give the common name of the language you are using, and remember that very few readers will understand you.
4 years?? My bird broke all 104 keys on my keyboard in just one day when I mistakenly left the cage door open.
...because no system is uncrackable or unbreakable, given enough time. The question isn't "will anyone ever be able to see my data?". The question a user should ask "how long would it take someone to get into my data and will it matter if they finally do get into it?".
Purists will argue against that idea, but I am being realistic here.
Please mod this post only if you think others should/n't read this. I have enough ego^H^H^Hkarma. Thanks!
I would moderate this +1 hore-yrrg-rapelcgrq, but noone would be able to break my uber-leet-encryption to read it ;P
would be much more effective.
64-bit computing with very large RAM (and possibly bandwidth) becomes as commom as the current PC configurations, IMHO
C|N>K
(or unfeasible to be exact) The study of elliptic curves - as a branch of mathematics is not very old one. And as Elliptic Curve Cryptography originates from this theory .... I think this is one of the main reasons why it has not yet been commonly approved for mission critical tasks. Currently, yes, we do know that it is pretty(very) strong against brute-force attacks - but there is still a significant chance that a fundamenta flaws or new discoveries are achieved in ECC theory - leading to easy compromise of previous implementations based on it.
http://www.nd.edu/~prinfo/news/2002/10-29c.html http://www.nd.edu/~cmonico/eccp109/ This thing was solve on 10-15.. Kinda old news
Why oh why not just give the bit count in hexadecimal? This just made me angry. It's like shit on a Picasso.
He used the 109 bit elliptic encryption. Since it has been broken, you should be able to read it, no problem.
With a brute-force break, it takes the same amount of time to break one key that it takes to break any other.
Not strictly true. It is possible that a brute-force attack will hit upon the right key at its first attempt. Or indeed, not until the last possible key in all of the keyspace. On average, though, the correct key will be found 0.5 way through the keyspace search.
Call me old fashioned, but I like a dump to be as memorable as it is devastating - Bender
Weak eliptic curve is great. SSH2 uses weak eliptic curve with digital signatures to prevent a "man-in-the-middle" attack. That being said, this article made some goofs. I understand that they were just trying to show off bc's MP arithmatic. However, it just gets a little old to see poorly implemented crypto as the standard way to show off MP arthmatic. Don't get me wrong, I have Applied Crypto on my night stand and all, but it would be nice to see an arbitrary binomial expansion program or a program to search for Merseme primes. Maybe just a nice Miller-Rabin primality tester or a Blum-Blum-Shub pseudorandom number generator.
The public number "n" they refer to should be a generator mod q. Primality does not guarantee that n is a generator mod q.
They mention needing to use larger numbers, but they don't scale it up enough. q should be at least 1024 bits, which is a little more than 16e306, which looks like a couple of lines of digits. The secret parameters xa and xb should be at least 64 bits, more safely 128 or 256 bits. Luckily, as long as xa and xb are large enough, the generator (n) can be pretty small. 2 often works as a generator. (I think the eassiest test for n bein a generator is for each prime factor p of (q-1), n ^((q-1)/p) % q != 1.) One of the main reasons you want (q-1)/2 to be prime is that it makes testing candidate generators easy.
Also, weak eliptic curve is not an encryption algorithm. It is a key agreement algorithm. Those numers they "sneaked past" Mallory (ka and kb) connot be predicted or controlled without actually calculating them. The whole point is that it's computationally infeasable to calculate discrete logarithms in a large finite field generated by modular arithmatic. If Bob gets ya and can feasably compute xb such that ka= kb = m for some chosen value m, then the whole crypto system is broken. weak eliptic curve is great for generating shared secrets (usually used as crypto keys for encryption algorithms), but cannot be used directly for encryption itself. The simplest way to use weak eliptic curve as part of an encryption algorithm is to generate a shared one-time-pad that is xor'd with the plaintext. The ElGamal encryption algorithm does basically this, the only differece is that it uses modular multiplication instead of xor'ing to do the encryption once it has the shared one-time-pad.
Furthermore, the article doesn't say how much of the total keyspace was searched (I'm assuming it was a simple exhaustive search algorithm). The time to search 50% of the keyspace, and 100% of the keyspace (corresponding to average and max time to "break" another 109 key, at the same average key checking rate) would be very useful to know.
But yes, this isn't breaking the algorithm, by any means. In fact, the contest is meant to show how infeasible a brute-force attack is against larger key sizes.
"It's overkill, of course. But you can never have too much overkill." - Anonymous Slashdot Coward
If Moore's law holds up that long, I'll eat my hat.
It took 4 years... How slow were computers 4 years ago, how slow are they now?
How long would it have taken if they just started this year on today's hardware?
With the introduction of faster chips and memory, it might only take another 4 years.
The man who trades freedom for security does not deserve nor will he ever receive either. - Benjamin Franklin
Why should I listen to you when you are clearly too stupid to understand number bases. Your use of decimal shows your lack of any sort of intelligence.
I already posted in this topic so I can't mod right now.
The man who trades freedom for security does not deserve nor will he ever receive either. - Benjamin Franklin
Relatively insecure? Forgive my ignorance, but didn't it take over 10,000 computers blasting away to defeat this thing?
;)
Personally, I feel that if the CIA or NSA wishes to spend that kind of processing power just to break in my research paper notes, let them. Hell, I'll even donate my computers to the project to help them.
/dev/random
Clearly your brain cannot comprehend number bases, so why are you talking about bits? Let me clue you in, a bit is a digit that can take either the value of zero or one. Ok, you learned something today. Your use of decimal indicates your inferiority.
How does it feel to be stupid? To be totally unable to comprehend anything other than decimal? I'm wondering what you mean by "bit" here since you are cleary too stupid to know what it is. Learn that first, then you can move to hexadecimal, you idiot.
As brute force will open it, even if that means making every possible shaped key or just the mundane big enough hammer.
There are places where the networks are not touching,and there are places where they are-Boeing's Lori Gunter
I haven't done calc in such a long time ...
:)
assuming the key is 54 bits longer and therefor 2^54 times harder to brutforce. How long would it take to solve if you started now and included moore's law?
even with moores law... if computing capacity doubles every 1.5 years.... then the equation for it would be something like 0,x integral (4 years * 2 ^ 54)/ (x/1.5)^2
where x= time taken to brut force this based on current standard
I think
anyone know if that is right and if so is has anyone taken calc in the last 10 years to help me figure that one out?
sorry for the terrible notation but it has been a while
It's interesting to see graphs of cracking power.
RC5 took almost 5 years to crack, but take look at the graph. At the beginning of 1998 there were about 15 GigaKeys/sec. Then look at the increase.
Sure, a fair portion of the increase was also the addition of new computers, but 261 days to double is comfortably below Moore's Law. If the whole project had run continuously at 200 GigaKeys/sec, it would have taken under 2.5 years, and under two years at their reported peak rate of 270 GigaKeys/sec.
So, if we follow the 261 day doubling statistic they had, all these encryption methods seem weaker than reported. The big issue is if it's 4 years now, it's 1 year soon, and 3 months, soon after.
If the cracking power scales nearly linearly, shouldn't we make some projections on how fast we can crack this encryption in a year? In two years?
If your data is very time sensitive, then most "strong" encryptions currently available will do. If your data is, however, of a continuously sensitive nature (some corporate or government info), maybe you should be looking at the 1000+ bit keys now.
That what was all this school was for... to teach us how to solve our own problems. -- janeowit
Your use of decimal indicates your stupidity. Stupid people shouldn't be allowed to post. Use hexadecimal. Idiot.
It is my understanding that with quantum cryptography.. it's not that the message is unbreakable, but that it is not possible to intercept the data without leaving a trace.
So you can break it, but everyone will know you did, ie: you can't eavesdrop.
God,
:)
:)
With all the bullshit and nonsense those editors are posting from very valid articles everyday, I think it's time for the community to either
1) pay these guys a degree
2) hire someone who can actually read technical stuff and FIGURE OUT WHAT IT MEANS before they write headlines about it
3) Complain here anonymously to keep your karma
Really editors, if you don't want most people to believe you're long haired teenagers with no clue whatsoever, please read the articles before you post
--
SELECT * from editors where clue > [...]
you know
OK, I didn't explain very well. The thought was that if I use the same key to encrypt all my data, doing the key refresh would prevent someone who got a hold of a piece of my data from cracking it, discovering my key, and then being able to subsequently decode all my data. This was assuming that they wouldn't get their grubby hands on all the data at once anyway, more that they might capture some data as it was being transmitted.
Elliptic encryption is not broken. FEE is still secure, as are all the other well-implemented versions of the encryption out there (unless the NSA has some big news they're not telling us...). Geez.
/. claims the algorithm is broken.
What happened is they brute-forced a 109-bit key. That's a small key. The minimum used in this company's product is 163 bits. While I wouldn't call this "impossible," it certainly is computationally secure for several years, and that's the minimum size.
When distributed.net cracked the 64-bit RC4 key, you didn't hear anyone saying "Oh no! OFB stream ciphers are broken!" That's about what this article amounts to: they brute-forced a small key, and
I hereby place the above post in the public domain.
Actually, you're almost right. But so very wrong. There is one cryptosystem that is IMPOSSIBLE(!!) to break: the One Time Pad. With that exception, it just becomes very hard. Another thing to realize about these codes is that *none* of them are provably hard. They are thought to be hard, but some mathematical genius might come out tomorrow with a fast method of computing discrete logs, or factoring primes, or figuring out elliptic curves. For now, it is practically impossible, but it might very well be trivial should such a breakthrough occur.
Okay, let's do some math here. The guy used 10,000 computers and he won $10,000. It took 549 days to crack it. Okay, well, that's $1.00 per computer, so that works out to a little under 0.2 cents per day per computer. Now subtract the cost of electricity, and how much did he make? Hmmm, that was worthwhile.
I mean, it's one thing if you don't know if it can be done, then you get the thrill of proving it can be done, but if you're just brute-forcing the damn thing, which it sounds like what happened here, then all I can say is, what a waste.
To ka kar iko ogik dhako ma youre dhi omo pi e aora gi dapi; to dapigni oting'o gi dier wiye lilo . Yuoreno olo pi e tago to yuoche mamoko omake ka gikete e thigo mar dhood dhako maduong' kanyo ema mon go luokoe kitundu. Giluoko lwetene gi tiendene; giluoko fuondege e oigla, oswaro kata tawo, to ka ojadwar giluoke e agulu bende. To ka giseluoke, yuochego lute ebur. Kiluto ng'ato e bur moro amora ok nyal ywak kata goyo koko nikech gikowe gi kwe. Ji okuyo ka gikulo wigi piny, to jo mochungo osiro lew tong' piny. To ka dhok pod ok odonjo e kul ok ginyal ike; gipero lowo, kata giumo bur gi pien kata thigo. Ka dhok osedonjo eka giike e kar saa apar ga ariyo ka chieng' podho.
This is the first and only person to break their 109-bit key. They took over 500 days with 10,000 computers worth of power. This is by no means an average time or even the upper limit of the time necessary.
You *could* crack the 109-bit key tomorrow if you started in the morning and your 10th inputs were somehow lucky enough to be the right ones. Or, you could start tomorrow and have it take 10 years instead of 2. The more important thing is: of the 109-bit possibilities (2^109?), how many did the 10,000 computers have to go through in 500+ days to finally reach the correct inputs?
Until we truly do have *impossible*-to-beat encryption, we still have to rely on making higher and higher improbabilities to reduce the chance that someone could stumble onto the correct input to break even 1024-bit encryption in a day.
Mordor...a magical, mythical land where women are more rare than dragons--but where every man would rather find a dragon
It may be computationally infeasable, but that claim is made using certain assumptions which may be wrong.
An example of such an assumption is that it takes n log(n) time to sort a list of n elements, using the best sort possible. The proof of this is based on the compare statement. However, there are sorts that work in O(n) time, not O(n log(n)) such as a radix sort which does not use the comparison operator (a/k/a "if-then-else").
The assumptions made are that brute-force is the only way to break this code.
I don't know of any attacks on elliptic curve crypto, when implemented correctly. That doesn't mean they don't exist using different assumptions, different number systems, or different computer hardware. (Quantum computing looks very promising to destroy our complacent attitude toward "computationally infeasable" problems.)
So now we know distributed efforts can solve great big math problems. Don't get me wrong, that's good to know and all, but.. aren't there any math problems that would be of more use than giving people with 210 IQs something else to bicker over during Star Trek conventions? Really, I'm an engineer, and sometimes I actually have to use math to do things like MAKE A FRIGGIN CAR OR SOMETHING.
There are plenty of nontrivial engineering problems out there, especially when you take a trip into thermodynamics and fluid flow. Let's solve those. Or sequence the human genome to grow an extra arm or something. Or better yet, let's put the computing power of mankind to work to randomly generate a script for Episode 3 that won't make us want to beat Lucas senseless with our plastic lightsabers. Why can people scrape together all these prizes for pointless pseudo-intellectual drivel but nobody can get some money behind something worthwhile, or at least interesting?
Here's an idea: Instead of using distributed computing for all this junk science, let's start a central distributed network. This network would have a basic interface element for all the major OS configurations, and would be able to update from the web with whatever mathematic formula and trial space it was supposed to run at a given time. Everyone everywhere could download the client, and set it up to run with whatever processor load they wanted, update on a schedule, maybe vary processor load on a schedule so it works extra hard when you're not using the system. Not much of an interface really. Then some organization, say the NSF or better yet an international science conglomerate, could alot portions of the system load to projects they deemed worthy, depending on complexity and value. The cost is basically nothing, in fact since you could get somebody on the planet to write the code for free one weekend, and the bandwidth would likely be rather low, you would most likely not be talking about the cost of funding a minor research project. Users could still run other distributed clients if they wanted, and the system would be completely voluntary. But it would attract a lot of attention and users, do some good for mankind, and direct our computing power in positive directions.
When I was little, I loved to write computer programs that would count. They'd start at one and count upward, and I'd keep track of when it gained decimal places.
Pointless, right? Well, does this cryptography cracking have a point? We know that the algorithm will be cracked when the right key is hit. It's just as much electrowanking as jumping up and down when your computer counts to a million, with a bit of cryptography politics thrown in.
I don't get why people are drawn to these projects over more significant problems like OGM or protein folding.
I don't even know why I'm dignifying this with a response....but after 01 in binary is 10.
I even use a binary clock, smartass. At the tone, the time will be 111 : 000 PM EST....ding.
Mordor...a magical, mythical land where women are more rare than dragons--but where every man would rather find a dragon
While it might be possible that a certain algorithm can be cracked exponentially faster with a quantum computer, you still have to find that algorithm. RSA is dependent on factoring large numbers, and is weak against quantum computers due to Shor's algorithm, but that doesn't imply all public key cryptography is.
As far as I'm aware nobody has conclusively determined whether or not quantum computers will be able to break elliptic curve cryptography any faster than classical computers, but there are algorithms (based on coding theory) which have been proven to be just as secure against quantum computers as they are against classical computers.
A good cause would be to get you a brain transplant so we'd have one less decimal infected brain around. Moron.
We do have perfect (i.e., impossible to break) encryption. It's called the one time pad, and is a very old idea.
I have a question about brute-force attacks on encryption: How do you know when you've found the right key? Suppose I encrypted my data twice. A brute-force attacker could test *every* possible key (to the outer encryption) and get trash every time.
Hm...sorry to be ignorant, but what exactly does 109-bit eliptic encryption mean? Does that mean there are 2^109 possibilities, or what? And if it does mean that, how long exactly would it take for a computer to try a possibility? One per second? Sorry if I'm completely off with my estimations.
And regarding the fact that it took four years to crack: even if it took three days to crack, couldn't somebody just change around the key every couple of days? That seems like a much more effective way of guarding data. Anything that can still be fresh in four years can easily have the key changed!
Back in the day when we worked on EMP shielding, no matter the elegance of the solution it all came down to raw force. If you wanted to shield to 100 MEV then all your opponent has to do is create 110 MEV. *Poof*
"Give me a big enough hammer and a place to stand and I can break practically anything"
-Archimediocrates
Just change keys every three years and you'll be fine.
so it TOOK 4 years to break a 109 bit key. does this mean that it will take less than 2 years if we start now considering the increases in computer speed?
and should we be using 218 bit keys for data that should be secure for more than 4 years?
<HUMOR>maybe we should have the cia encrypt and submit to public the domain all of thier classified information. said info would be encrypted with key lengths appropriate for the amount of time they wish the data to be hidden. that would ensure that we all get to know what really happened, safely after those who are at fault have retired and entered hiding somewhere us courts can not punish (like winona ryder's house.
Though the charges can carry a prison term of up to three years, it is unlikely that Ryder will be sentenced to jail time.)</HUMOR>
fear is the mind killer
IANAC (I am not a Cryptographer)
every time you increase the bit length by 1, it doubles the brute processing time it takes to crack it. A 219 bit key is 109 bits longer then a 109 bit key, therefore it would take 2^109 = 6.4903710731685345356631204115251e+32 times as long to crack it. If I recall correctly, the reason why you sometimes see huge keys that are 1024 or 2048 bits long is the possibility that a weakness is found in the encryption technique that makes it a lot faster to brute force the key.
Lawyers, MBA's, RIAA? A jedi fears not these things!
but there are algorithms (based on coding theory) which have been proven to be just as secure against quantum computers as they are against classical computers
I am a bit curious as to how they proved this exactly since AFAIK no quantium computer (to date) has ever achevied stability.
Otherwise though great comment, and thank you for pointing out the fact that quantum computers are not the end all point, as your conclusions and speculations prove my point wonderfully- cryptography is nothing more than an arms race, there will always be someone, somewhere that will take the next step forward, be it creating a nifty new algorithm or figuring out how to break the latest nifty algorithm.
Most people have ten fingers. That's why we use the decimal number system. Maybe we should examine why you don't have ten fingers. Is your father extremely hairy? Does he bark frequently, and answer to "Fido"? Are your kissin cousin and your mother the same person? Inbreeding IS a major cause of genetic mutation...
The article cites 132 million CPU hours over 18 months. At one time my computer center used to charge $30 a CPU hour.
I don't know much about encryption and am curious to know why we don't just choose some arbitrarily high key-length like 500 bits. What is the rational for slowly increasing key size every year? Is there some kind of computational limitation that makes longer lengths undesirable?
'Impossible' is the wrong word to use when it comes to cryptography.
Perhaps that's why that word is nowhere in the text linked to.
It's exactly the attitude not to have, if you care about security.
One-time pads are uncrackable- mathematical proof exists. That assumes (and it's a rather large assumption) that the rules of using a one time pad are followed.
Messages encrypted with a OTP have been deciphered in the past, but not from any mathematical failing- people simply failed to correctly follow the rules.
1. You need a random process to generate the pad. This means random, not pseudorandom. Admittedly, modern pseudorandom number generator algorithms are very complex, and trying to reverse engineer (hey!) a PRNG from just a stream of outputs would be a mammoth task. Rules are rules, however complex- if your pad is pseudorandom, your cipher will only be pseudo-uncrackable. The Enigma produced vey complex keys with a convoluted series of rules, but if you know how an Enigma works, as the Brits did, you can use the ciphertext to help find the key, and then dechiper the entire message. This is one area where quantum mechanics fits in- lots of nice random phenomena arise naturally from quantization- I'll get back to that. Also, the key on the pad must be as long as the message you wish to encode- if you try to encode a 2000-character message by using a 1000-character key two times, your security is no longer guaranteed.
2. Only use each key on the pad once. That's why it's a one-time pad. If you use the same key more than once, you remove the randomness, and create a pattern that can help the cryptanalyst. Deciphering will still be difficult- but if you wanted difficult, you could have just used triple-DES or RSA or elliptic curve crypto- those are all varying degrees of difficult. You want impossible.
OTP is unbreakable, if you follow the rules- but the rules are really hard follow. You need random processes, and once you have these neat pads, you face the Key Exchange Problem- if you have an agent out in the field that you'd like to communicate with, and you must communicate in an absolutely secure fashion, you must get a copy of the one-time pad to the agent- it's the only thing that will decipher your messages. However, you can't just pick up the phone and relay the contents of the pad to your agent- the enemy might be bugging your phones- and hilarious hijinks will no doubt ensue when the enemy uses their new your insecurely transmitted pad to read your secure encrypted messages. Encrypting transmission is a good idea, but you can't use OTP to send the first OTP to the agent- how will the agent decrypt his encrypted pad? The classic analogy is that you're trying to send a key (think physical, lock-opening key) in a locked box that only the key inside the box can open. You could encrypt the key with hardass public key crypto, say 1024-bit RSA, but that isn't unbreakable in the same now-and-forever sense as OTP. It would be vulnerable to quantum computers, and vulnerable to any computer if someone discovered a polynomial time algorithm for prime factorization of really gigantic numbers, or if I win a Clay Mathemtics Prize for proving P=NP. You could of course do what the government does for secure key distribution- send couriers carrying OTPs directly to the agent in the field. This is an expensive, difficult, dangerous method, so better ways were searched for.
This is of course where Quantum Cryptography comes in. Photons all have specific polarizations. You can send a stream of randomly polarized photons through a polarizing filter, and photons with the same polarization angle as the filter will pass, while those with a polarization rotated 90 degrees with respect to the filter are blocked. What then happens to photons that have some intermediate angle? On the macroscale, we can say that the intensity of the light is a function of the angle, and infer that at a 45 degree tilt, 1/2 of the light is blocked, and 1/2 passes through. Enter Quantum Mechanics. It is fairly obvious to see the effect that polarizing filters have on a large scale quantity of light, but what about individual photons? Since the intensity of light at a 45 degree angle is 1/2 its normal value, one can infer that one half of the photons with a 45 degree polarization pass through, while one half are blocked. Simple enough. But if you send just one photon through with a 45 degree polarization, can you determine whether it will pass through? The answer, surprisingly enough, is no. You cannot determine whether a photon will pass through, and you will not know whether it passed through until it hits (or fails to hit) a detector on the other side. Can't determine? That makes it a random process, perfect to set up a OTP. It happens to have some interesting side benefits as well. Since the possibilities are pass and blocked, two possibilities- a string of photons sent at the filter produces a random binary sting of 1's (passed) and 0's (blocked). There is another fascinating benefit- if someone tries to sit in the middle of the photon stream and determine photon polarization, their eavesdropping will be evident- by checking the polarization of a photon in transit, they change the value of the polarization. All two people using quantum crypto need to do is confirm a few values that were sent (this can be done insecurely, since these values will not actually be used in the cipher pad)- if they match up, then send the message, encoded with the OTP, if not, someone is eavesdropping, and so discard the pad. It's a lot more complex than that, of course, but that's the general idea- you can use QC to generate a one-time pad, and then send it in such a way that you know whether or not you're being spied on.
"FDA staff reviewers expressed concern about the number of patients who were left out of the study because they died."
Factoring primes? Um, by definition add a "1 x" and you are done.
Re: your sig
I haven't seen a geek code since about 1996.
Hence, if it doubles in 261 days, that is indeed below the time specified in Moore's law.
What's your point?
Ummm...
Wouldn't a 24 hour H:M:S clock require 16 bits not 9?
4 for the 24 hours or 12 hours + sign, 6 for 0-60 minutes and 6 for the 0-60 seconds?
The good thing about CreditCard numbers is they remain vaild for an amazingly long time - you have a few years in some cases to break the encryption and grab the number - you even have a nice checksum to verify the number you retrieved is valid.. To make it even better they transmit a nice validity date to ensure you dont accidently try and use an expired card.
I believe your parent referred to the fact that its parent said "1000+" rather than "1024+" bits. Because 1024 seems more "round" to him/her than 1000 does.
I'll rot13 you!
-Nuke the moon
It took the power of 10,000 computers running around the clock for 549 days, coupled with the brain power of a mathematician at Indiana's University of Notre Dame, to complete one of the world's largest single math computations.
Maybe we should tell these guys to use modern computers instead of the network of Altair 8800, C-64, VIC-20, ZX81, TI-99/4A and MicroBee computers.
Assume that in order to break a 109-bit keyspace you need to try half of the keys. In other words, you need to try 2^108 keys. They managed to do this in 4 years. This gives a base rate (rate as of now) of 8.11e31 keys/year.
Since we assume computing speed increases exponentially, doubling every 18 months, we need to multiply this base rate by 2^(t/1.5), where t is the time in years from the present date. This gives a keyrate of 8.11e31*2^(t/1.5) keys/year at time t.
Now, we want to break a 163-bit keyspace. Again, we assume we need to try half the keys, so we need to try a total of 2^162 keys. We integrate the rate from time t=0..x on the left, and equate that to 2^162. This gives the equation:
1.76e32*exp(0.462*x)-1.76e32 = 5.85e48.
Solving this for x yields x = 82.33 years.
Quite close to the original estimate.
If you are exceedingly lucky you might get the key right with your first guess in a brute force attack. The bigger the keyspace the less likely that is. On average a bigger key will take longer to brute force than a smaller key but it is feasible to get lucky and find a particular 163 bit key in less time than it took for that particular 109 bit key. It's just somewhat unlikely.
Boffoonery - downloadable Comedy Benefit for Bletchley Park
In 4 * 2^54 years!!!
That's 72,057,594,037,927,936 years.
Give or take a few of course.
The one-time pad is impossible to break, but possible to brute-force. The big difference between the one-time pad and other systems is that the key is never reused, so that even if you manage to crack that key, the system keeps its integrity, since that key is never used for another message.
Now, just because it's "possible" doesn't mean it's feasible... but I don't exactly call 10,000 computers x 549 days feasible for one message, either. Depending on how the one-time pad is implemented, it may be more or less feasible to crack a single message than this key was, but it's not impossible.
Don't you wish your girlfriend was a geek like me?
No, no, no.
...
Take two primes. Multiply them together. Give that number to someone else. Ask them to tell you the primes you multiplied together.
Sounds easy? Well, try using prime numbers which are tens of digits long
I was too lazy to type out the extra zeros. Be happy I put 3 for the minutes. My binary clock (same as ThinkGeek, same as the gnome tool) does it by the decimal digits anyways (i.e. 12:45 is 0001 0010 : 0100 0101).
Mordor...a magical, mythical land where women are more rare than dragons--but where every man would rather find a dragon
Yeah, yeah, the above poster isn't refuting that prime factorization is hard- just that it's not the same as "factoring primes." To say "factoring primes" to many people implies that it is a prime number you are factoring, which is of course easy, since the factors of a prime are 1 and the number itself. You speak of finding the prime factorization of a number, which is ideally a composite, so you break it down into a product of primes. The composite numbers used in public-key cryptography are a little unusual, since they generally have precisely 3 factors- 1, a very large prime, and another very large prime.
"FDA staff reviewers expressed concern about the number of patients who were left out of the study because they died."
5%, 50%, 100%? For all we know they could have gotten plain old lucky. After all, there's a 2^-109 probability that I can crack this key by brute force using 1 attempt. Doesn't make much sense to base any judgement on that though.
Kjella
Live today, because you never know what tomorrow brings
For instance, many algorithms (not elliptic curves though) depend on factoring being much harder than multiplying. If you've factored it, you also know the only solution that works, because that is the only factoring.
You might only get trash, but it was the trash you encrypted, not some random trash...
I don't know enough about elliptic curve crypto to know about that one, but it's very possible that once you have the right key, you will know that that key is the right one.
There are algorithms that will accept any key, and not give you any clue that you have failed. For instance you can just XOR the text with the password repeatedly. However in my experience that trade-off usually comes with bad protection against known plain-text attacks.
Kjella
Live today, because you never know what tomorrow brings
You wouldn't by any chance work for intel, do you? I mean 2+2 = 3.99999998673 is close enough ;)
Kjella
Live today, because you never know what tomorrow brings
For everyone interested in cryptographic stuff, I always suggest to read the publications of Bruce Schneier (http://www.counterpane.com). His monthly newsletter "crypto-gram" is very interesting and really fun to read (at least most times) and he produced several books I like very much (especially "secrets and lies", or "Applied Cryptography", if you are interested in mathematics of cryptography)
Don't underestimate cryptanalysts ability in this area, either. The Soviet Union made the mistake of reusing some of their One Time Pads a few decades ago; as a result, Project Venona, was able to decode enormous amounts of archived (but still useful) secret traffic.
Don't think traffic that old is useful? Tell it to the spies who were still in place when Venona broke those old communications.
Actually, it *is* impossible to break if it's truly a one time pad. Since the is no repetition over the length of the message, all keys are the same length as the message and therefore trying all possible keys will yield all possible combinations of messages of that length and you have no way of knowing what the message is. i.e. Is 46adab8bd51c187c7cab9e = ATTACKATDAWN or ATTACK TODAY With a proper OTP you *can't* know.
he ate your Dell!
I'll be coming 'round Nottingham to brute force your front door some evening soon. I'm sure you'll find that it is broken after I do that.
attacks on RSA and Diffie-Hellman with a quantum computer can use Shor's algorithm, giving an exponential speedup. Nobody's got a quantum algorithm to attack ECC yet, at least not that I've heard about.
#define X(x,y) x##y
Peter Cordes ; e-mail: X(peter@cordes ,
Why do I act like it is? Where did I act like it was?
The guy said that 260 days was below moore's law, and you told him he was wrong.
He was right.
I was responding to that.
I wasn't saying anything about how relevant Moore's law was to what he was describing.
I'm not sure when we started talking about magic dust, but maybe you better quit snorting it just to be safe.
VMS Beer: Requires minimal user interaction, except for popping the top
and sipping. However cans have been known on occasion to explode, or
contain extremely un-beer-like contents.
- this post brought to you by the Automated Last Post Generator...