Slashdot Mirror
Professor Describes Unbreakable Cryptosystem?
split horizon writes: "The New York Times is reporting that
Professor Michael Rabin of Harvard
University claims to have developed a cryptosystem that is both
practical and provably unbreakable. It sounds to me like it basically uses a one-time pad that's generated on the fly very quickly." Good stuff, but don't expect to see this in the next version of gnupg - the logistical difficulties are high and the system you'll end up with won't be any more secure in practice than public-key encryption techniques already widely available.
This sentence is misleading for the following reasons:
- It has not been proven that the integer factorization problem is NP-complete. An NP complete problem by definition is both NP and NP-hard. Integer factorization is known to be NP but it is not known to be NP-hard.
- It has not been proven that RSA is equivalent to factoring. We know that if the factoring problem is solved then the RSA problem is solved, but we do not have a proof that factoring is the only way to solve the RSA problem.
Please try to avoid furthering the misconceptions that factoring is NP-complete or that RSA is equivalent to factoring. Both facts might very well be true, but they have not yet been proven.Speaking of true random number generators, check out SGI's Lavarand .
;)
"Lavarand... harnessing the power of Lava Lite® lamps to generate truly random numbers since 1996"
fun!
cpeterso
If the underlying assumption is true, this system provides perfect forward secrecy: the compromise of my 'key exchange' key at any point in the future does not reveal my previous messages, as the OTP material is long gone by that point.
The security hinges on the fact that by the time an attacker could decrypt my 'start here' instructions, so much of the public OTP stream will have gone by that he couldn't feasibly store it all and thus can never recover the OTP. This 'never' is a dangerous word. The OTP stream is public, and thus an attacker does have access to the OTP I used, if he can determine my 'start' point.
A brute-force attack on this system would seem to be linear in space which a huge constant dependent on your bitrate, bounded by an attack on your key exchange mechanism. In a system providing any sort of 'interactive' performance, the search space is limited greatly. Admittedly, for short messages the search space in the stream could rapidly exceed the an exhaustive search.
It's a clever idea. I'm not exactly sure how to evaluate the security of the system, and any implementation seems that it would be prone to an array of interesting attacks, but I like it.
--Jered
This is certainly a very nice result, now it has to be published and analyzed before we can say more. From the short description in the article, it seems that there is a stream of random number which comes in at very high speed and that to decipher, you have to know which part of the stream was used. Well, if you are "lucky", you can just store small parts of the stream from time to time and maybe you'll get the very right one. Of course, the probability is negligeable, but the probability to guess the key in a traditionnal cypher is too!
Naturally here, the nice thing seems to be that if you don't get the right part of the stream, you will never be able to decipher no matter how long you spend, whereas in traditionnal settings, you will be able to decipher after some time (say a few million years)...
What is meant by "provably secure" here is, I think, not what you are thinking. Rabin is not saying "there is no way for this system to ever be broken.". He is saying that from a mathematical standpoint, it is provable that this cannot be broken. Big difference. Almost all current algorithms are based on a NP-complete math problem- something like factoring, in the case of RSA. This is all well and good as long as P != NP. However, there is no proof that this is true. Therefore, no system based on this premise can be mathematically shown to be secure, because someone discovering a polynomial time algorithm for any NP complete problem breaks the system. Rabin's algorithm is provably secure from a mathematical standpoint, given certain assumptions, but without the assumption that P != NP. So from this respect, there is such thing as a provable true cipher. If you have a nice proof that the set p != the set NP, a number of other ones become provably true. As for the distribution of the one time pad, the question is answered in the article. The one time pad is the random number stream, which is available to anyone that wants to listen to it. But, you have to know what stream to listen to, and which numbers to pick out, a communication that can easily be made using existing cryptography. It relies on the fact that the random numbers are being generated too quickly to be stored on a computer, due to limits in memory.
The thing to remember is that Rabin is an academic, and not a "security guru". What is "unbreakable" to him is not a system that forces idiots to not make their passphrase "password". It refers to the mathematical consistancy of the system. Take away the side-attacks and the idiots with their mother's maiden name as a password, and the system is unbreakable. Take those away from any other existing cryptographic system, and the system is still not proven to be secure. So it's not snake oil, not only because he isn't selling anything, but also because it appears that his claims are, in the regime in which they are made, true. This is an article about an academic work, not a press release for "security blackbox 4000".
"Sweet creeping zombie Jesus!"
Who cares about breaking encryption algorithm. When it's far more easier to break protocol and implementation of protocol.
As long as there is social engineering and poor cryptosystems implementation, it will be relatively easy to break them.
While I'm not really qualified to comment on the details or the proof or anything, it certainly sounds like there are some major applied/practical limitations in the scheme to me. But for a subset of current encryption practices, this could be very useful, in particular for a lot of current applications of public key cryptosystems.
Frankly, I think Rabin is just pissed that the public key cryptosystem that bears his name never achieved wide commercial use and instead RSA became the standard. Now he wants to supplant public key cryptosystems with something entirely different. His ego is rather huge, and not entirely unrightfully so.
If the eavesdropper, for example, had a secret way to decode the message saying "start" and it took a minute to do the calculation needed to decode it, it would be too late by the time the eavesdropper got going. The sender and recipient would already have their string of numbers and that string of numbers, once broadcast, could never be retrieved. It would be infeasible to store the endless string of numbers in any computer and so they are essentially gone forever.
I don't understand how this system is unbreakable. The above paragraph seems to assume that the stream of numbers is too large to plausibly store on a computer - but that's not the same as saying that the system is "provably" unbreakable.
one time pads, as long as they are generated using true random numbers, and that each pad is used only once, are provably unbreakable.
The word unbreakable is meaningless in Cryptography, a message (or system) is secure or insecure.
It is impossible to *proven* that your conditions hold true, it is therefore impossible to *prove* that even a one-time pad is secure.
The way a one time pad is compromise is through the key (pad) production or distribution. Since is no way to *prove* this security even a One time pad cyrto system is not provable secure.
Finally read some crypto history before repeating this claim, because this FACT has cost people their liberty and lives.
Today, data storage is far, far cheaper. And broadcast spectrum is scarce. Consider DirecTV. The entire output, all 100+ channels, fits in under 500MHz of spectrum. And they work hard to manage that spectrum efficiently; each channel has a different data rate (sports are around 8Mb/sec, C-SPAN is probably a tenth of that.) Data (non video/audio services) over DirecTV uses about 30 Mb/sec. DirecTV is using about a billion dollars worth of spectrum at current prices.
So a very generous random data feed from orbit would be 100 Mb/sec. That would fill a DVD every five minutes or so, or an 80GB hard drive in an hour or so. (If it's random, compression is impossible, of course.) That's a lot of storage, but not an impossible amount. Storing it would be cheaper than buying the spectrum required to transmit it.
Hypothesis: You can't find a real number "x" such that x^2 < 0 .
Proof: Left as an excersise for the reader...
QED.
What you are thinking of is different -- for eg, if I were to say "Pigs can't fly", I couldn't prove this without finding _every_ instance of a pig, and making it try to fly. Even then, it would be a shaky proof, because how do I know how to make pigs fly? (I guess we'll have to wait for MS to release some good software)... and _even_ _then_, how do I know I have found all the pigs?
Interestingly, there is a whole set of problems in mathematics which are provably unsolvable. With many hypothesis, the first step is to prove that the problem is solvable, then work on the solution :)
rr
Quidquid latine dictum sit, altum videtur.
for (p=msg, i=msglen; i--;) *p++=0;
This system 'cannot be deciphered' either. The prof's idea is nice (yes, it is just a one-time pad. yes, it does just use cryptographically strong random number generator. old news) for secure communication channels, you can't store files on your hard disk like this. Any system that allows you to get back the plaintext, allows someone else to get back the plaintext.
Does my bum look big in this?
You've got Mr. Schneier's high-level message but you seem to be misquoting him in a way that ignores a very fundamental distinction.
"Acording to Bruce Schneier it is impossible to prove the unbreakability of a cryptographic algorithm. "
Find me that quote. It *is* possible to prove the breakability or unbreakability of an algorithm, as Bruce well knows but your quote of him denies. Proving the unbreakability of a product, of an *implementation* of that algorithm is practically impossible as Mr. Schneier has repeatedly said. (Although one could claim that NCSA/NSA-rated A1 products constitute a potential counter-example for highly-limited problem domains.)
I'm not claiming that you're a phony. But I sure as hell wouldn't trust your quote from Mr. Schneier just because you said it on Slashdot and it got a 5 rating.
--LP
Man, you guys think you're so smart because you read Applied Cryptography and some recreational mathematics books in high school.
Rabin is a bigshot in number theory, being the Rabin part of the very popular Rabin-Miller algorithm for probabilistic primality testing. Your favorite cryptography program almost certainly has an implementation of this in it.
If he says he has a proof, for god's sake, he has one! There's no way the NYT is going to publish enough information for you to seriously dissect his work. In fact, there's hardly enough information there to even get a start at reconstructing his results. Give the dude a break!
This seems a fairly reasonable assessment in my book.
A security product claiming that it's unbreakable has the same credibility es "GET RICH NOW!" e-mail subjects or time share salesmen.
I'm not claiming that the good prof is a phony. But I sure as hell wouldn't trust a new crypto scheme just because the NYT reports about it.
ich bin der musikant
mit taschenrechner in der hand
kraftwerk
The ugly part would be that a government agency could send such a pseudo-random key stream for public use, so that no one can decrypt the message except those who know how the pseudo-random stream works.
In any proof, you have to start with assumptions. If these assumptions are good (like the basic axioms of math) then your proof is good. Bad assumptions, and your proof is useless.
Here he has what is probably an ingenious proof of secure communications. But there is an assumption he makes that ruins it. Actually, several, but one is key.
He assumes that the two machines who want to talk have some "secret" way of agreeing when to start sampling the random number stream. What is this secret method? Is _it_ unbreakable? It can't use his unbreakable method, since it is required to implement his method. Thus it will have to depend on current techniques (public key crypto) to share the keys, and have the same vulnerabilities thereof. I mean, really. If we had a 'secret' way to safely exchange keys, we could just use that method to communicate in the first place!
There's more, though. He also assumes a finite limit to computational power. He claims that is the problem with current techniques, but then makes the same mistake himself. For two machines to agree on a sampling point, that point would have to be far enough in the future for the second machine to receive the data and then reply. If the code can be cracked in that time, then the conversation can be eavesdropped. Thus there is a window of vulnerability.
This really isn't so different than modern techniques, but with more required infrastructure (the RNG satellite). Now we use public keys to decide on a private key. If we take the window of vulnerability in his method to be X seconds, then this would be no better than using current techniques but issuing a new private key every Y X seconds (no satellite required).
There are other problems - like the fact that they can still get your data with the gun-to-head method just by recording the unencrypted data on your end. Aw, forget it. Another idealistic mathmatician who needs a little more of the engineer's bent toward practicality.
The enemies of Democracy are
The article states that the reason the system is 'absolutely secure' is because the datastrem of the 'public one-time pad' being streamed down from the satellite is coming at too high a bitrate to be captured for the time needed to decrypt the 'start' key.
This is hardly impossible to overcome. There are three fronts when, applied together, will over time increase the probability of cracking the message.
First, storage technologies improve. Just as there is now distributed computing, there could just as easily be distributed archiving, where 100, 1,000, or 1 million computers share the task of striping data from the cipherstream for later retrieval, once the start code is hacked.
Second, the start code itself is vulnerable. With quantum cracking, even a 128-bit key may fall within moments, in which case the resulting datastream will be insecure. (This is the 'weakest link' approach, as the whole system relies on the impracticality of decrypting a conventional crypto system in a given timeframe and is therefore not 'impenetrable')
Third, given that the sending and receiving computers will be using a relatively short piece of the cipher datastream (from the satellite, or wherever), it's feasable to combine the above two, simply storing the specific few seconds of cipherstream for later use in decryption.
Vulnerabilities abound. If you can create a man in the middle attack on the start key, both parties are fucked and you can read their messages in realtime, insert false messages, and take advantage of the fact that they believe that their communication is 'absolutely, provably secure.'
The argument that an arbitrarily fast datastream would eliminate the ability to record it is similarly bogus, as an arbitrarily large array of recording devices would be able to accomplish the task.
A little cryptography is a dangerous thing, and this represents only a little cryptography...
Kevin Fox
--
Kevin Fox
A Cipher and a Code are not the same thing, and this guy repeated say's code when meaning a Cipher. Also a Crypto system is only as strong as it?s weakest link and typically the weakest link of a Crypto system is the key production and distribution, and he offers no description on how this would be achieved securely.
There is also no such thing as a provable secure Cipher, you can prove it?s insecure, or it?s degree of insecurity, (by compromising it) but it cannot be *proven secure. Even a One-Time-Pad can be compromised, by compromising the key (pad) production or distribution.
This has all the hallmarks of silicon snake oil.
Anybody that does not believe this should read the Silicon Snake Oil FAQ from the news:sci.crypt