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.

Comments

Wrong

[LinuxParanoid]

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

Slashdot hubris

[Tom7]

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!

Re:Slashdot hubris

[Anonymous Coward]

Schneier wrote Applied Cryptography, developed Twofish and Blowfish, and has developed a number of protocols that are very useful and (assuming the software implementing them is good) secure.

But when he published McGuffin, an unbalanced Feistel cipher, somebody had the hubris to attack the system!

And they broke the goddamn thing. To pieces.

The fact of the matter is, even the best guys make mistakes. Andrew Wiles is one of the world's leading eliptic curve specialists-- he still made a mistake (slight as it may have been) in his proof of the Taniyama-Shimura conjecture. Sarah Flannery (16-year-old Irish cryptographer girl) had a proof that the Cayley-Purser algorithm that she developed was as hard to break as RSA-- it's completely insecure.

Are all of us at the level of Rabin? No. But that doesn't mean that we can't at least state what obstacles he has to overcome, and why there might be difficulties.

Skepticism, not hubris, is part of the Slashdot culture. If you want to blame somebody, blame the editors that have made it that way (Rob, Jeff: I'm kidding, of course...).

Seems a tad absolute

[CaptainZapp]

Acording to Bruce Schneier it is impossible to prove the unbreakability of a cryptographic algorithm. The best you can do is to state I am not able to break it and then let the crypto community rip it appart.

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.

Re:Seems a tad absolute

[ZanshinWedge]

Actually, one time pad crypto systems are provably secure. As you said, the main way to crack them is to hammer at the supposedly random pad generation, or to attack the physical security of the pad (which, btw, has nothing to do with the cryptosystem by itself, if you obtain any key, you'll be able to crack any code). Take a look at hotbits, it's a source of true random numbers generated from timing radioctive decays inside a nuclear reactor.

However, the main disadvantage of any one time pad based system (despite it's great cryptographic strength) is that the key (or pad) requires itself some amount of physical security. In contrast a system like RSA is much different because it is not even remotely symmetrical (encryption vs. decryption) and you can send out your public key for all to see and to use but still only you (with your private key) can decrypt what has been encrypted with the public key.

Personally, I don't see this new development as anything special, we already have methods of using extremely high security encryption where it's needed (spying and whatnot) and for other applications that require more convenience and can have more cpu power put behind them the systems we have now are really more than adequate (assuming your using the right systems, not all the systems in use now are cryptographically secure in any resonable sense, but we know which ones those are).

Only secure when YOU generate the key/randomstream

[tjansen]

This system can only work when you can be sure that the one-time-pad so large that the intruder cannot save it fast enough and the key stream(=one-time-pad) is truly random and not pseudo-random. As there is no 100% secure way to guarantee that you get the right stream, unless you do it yourself, this means that the sender of the message must send this infinite stream. So this is really unpracticable for most normal persons, but could be used by goverments..

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.

The Fatal Assumptions

[Chris Burke]

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.

'Infeasable' decryption, not 'impossible'

[KFury]

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
--

Clue: Cipher != Code

[Martin S.]

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