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.

factoring, NP-completeness, and RSA

Almost all current algorithms are based on a NP-complete math problem- something like factoring, in the case of RSA.

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.

Random numbers from Lava Lite® lamps!

Speaking of true random number generators, check out SGI's Lavarand [sgi.com].

"Lavarand... harnessing the power of Lava Lite® lamps to generate truly random numbers since 1996"

fun! ;)

Perfect Forward Secrecy

The word "unbreakable" is overused. This is not "unbreakable" in the sense that a traditional OTP is unbreakable, however it is clever, and has some interesting properties.

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

Hey, people, show a little respect!

I can't believe the number of people who claim this cypher is bullshit without even seeing it. I mean, this is not coming from some random guy. Michael Rabin is one of the best cryptologist ever. Furthermore, he does not actually claim that his scheme is "unbreakable". He claims that in standard schemes the security relies on an assumption on the limitation of the computing power of the adversary and that in his scheme, the security relies on the assumption on the limitation of the storage of the adversary, independantly of his computing power, which may be infinite.

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

Re:Clue: Cipher != Code

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

Just break the protocol

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.

funny story....

I invited Michael Rabin to dinner with me at a House dinner at Harvard last year. I (a physics student taking a class with Rabin) and a math major sitting across the table were listening to Rabin describe this exact cryptosystem at the time and we were going through the probabilistic analysis of this simultaneous, time synchronized OTP key distribution system (that's basically what this is). Frankly, we thought he had sort of, well, lost it a bit over the years if he thought this was a "real" cryptosystem. But we just kept nodding. What's interesting is that it modifies the difficulty of compromising the encryption scheme by moving it into space-domain rather than time-domain (it's storage space limited). And he knew this was provably secure a year ago, so I don't really think this is news (although perhaps he hadn't published or formally presented his results yet).

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.

Why unbreakable?

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.

Re:Seems a tad absolute

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.

The economics don't work

I thought of something like this when I was an undergrad in the 1960s. I was thinking of using broadcast TV signals as the shared key source, and combining key and data in some analog way. (I later found out that Turing had proposed something similar during WWII; he figured how to do modular addition in the analog domain, and proposed this as a simpler alternative to SIGSALY) In the 1960s, video recorders were very expensive and ate tape at a huge rate, so saving the output of the TV networks in bulk looked hopeless. But I never did anything with the idea.

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.

Re:provably unbreakable?

That statement is provably wrong... All I need do is prove there is something that I can prove can't be done.

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

I have an unbreakable code:

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.

Wrong

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

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!

Seems a tad absolute

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:Slashdot hubris

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

Only secure when YOU generate the key/randomstream

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

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'

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

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

Re:Seems a tad absolute

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 [fourmilab.ch], 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).