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

Question on PGP

[Anonymous Coward]

I got PGP but it is important that people dont know that I got encryption let alone what I am talking about so I incrypted the program only now it wont uncrypt and it says bad command or file name. Did I discover some kine of unbreakable incryption cause I cant get it uncrypted.

Mixing the secret key with the public random bits

[Anonymous Coward]

Reading between the lines, I'm guessing that Rabin's scheme works like this (assume 1024 bit key for concreteness):

• Receiver uses secret key to pick a start bit in the public random bitstream.
• Receiver does not simply take the next 1024 bits from the public random bitstream.
• Instead, receiver uses secret key to pick 1024 bits out of the next N bits to arrive, where N is a lot larger than 1024.

So the attacker not only has to store N bits, they have to pick out the right subset. (N choose 1024) can be rather large.

There's another part where N is so large that the receiver's hardware can pick out 1024 bits of it as it goes by, but nobody can afford to store the stream. E.g., suppose that the random bitstream is 1000 gigabit/second (think thousands of parallel radio channels that the receiver chooses from). Then the attacker needs to spend $1000/second to record the keystream. Get people broadcasting at 1 gigabit/second on 100,000 channels and no attacker could afford to record the random bitstream today.

The economics change in any given year -- but the random bitstream gets faster and more parallel, while the attacker's storage cost go down about as fast as the random bitstream gets faster.

This can not work in practice

[Anonymous Coward]

So, the sending site sends a "start" message. I recieve the start message, and start grabbing numbers. at 10 million million numbers per second, and latency of ANY network communication, how are we to know that the client and server machines start their number strings at the same time? Do we send a partial number string to identify a common point, and start say... 10 billion after that? The "start" message is being sent with "normal" encryption... when you see the start message, start grabbing numbers. decode the start message to find the "tag" and start point... then go back to your number string and find it, GAME OVER. So... While, in theory, this sounds like it would work, I can see no way to impliment it in practice. --Doku (doku@yahoo.com)

Re:This can not work in practice

[sctprog]

I have to agree.. even if there was no latency in the network, you still have to account for the fact that most computers today simply cannot parse that sheer amount of numbers/second. That is assuming that the processor is dedicated to that task, and that task only.

I wonder what Waterhouse would think of it?

[Anonymous Coward]

Cryptonomicon, great book by Stephenson (author of Snow Crash). Although it's a novel, it explains crypography in very simple terms, and is a good introduction to the subject.

Re:I wonder what Waterhouse would think of it?

[hey]

In Cryptonomicon Waterhouse actually used something like this. He had a encrypted long distance phone call with his pal Allan Turning. They encrypted the conversion by using a long stream of random bits played from a record player. Both sides played the record and then (presumably) destroyed the record.

The problem with the professor's plan is that there would be lots of people using the same "record" and it wouldn't be destroyed. Oh yeah, its impossible to save it - really?

I don't thing Waterhouse would be impressed.

Re:provably unbreakable?

[Anonymous Coward]

Nope your wrong. Mathematicians do it all the time. Like they've proved that you can't solve an indefinate integral for e^x^2.

Another Assumption

[Tim Macinta]

You're also assuming the satellite transmission is secure. This would require that you fully trust everybody involved in building and launching the satellite - throw one rogue programmer in the mix and you could have the satellite spitting out pseudo-random numbers which could make this easily crackable.

You could also have a man-in-the-middle attack with a guy standing outside your house feeding you a bogus satellite signal so that you use a pseudo-random pad. Of course, maybe he worked out a way around this so you can verify that the stream is actually from the satellite - I haven't read his paper, just the NYT article.

Yeah, but is it practical?

[SeeFood]

encryption algorithem aside, what about the practicality of obtaining the key?

the way I see it you need a source that transmits obscene amounts of random numbers, it has to be fast enough to flood the adversery (drown him with numbers :), and it has to be easely available to both parties, that may be far in different corners of the world. If you're a government willing to keep an international OC-12 of random bytes for the occasional encrypted Email, it's fine, but what about the little guy? OK, so we need it on a sattelite like the article sugests, now the little guy needs the hardware to pick it up from the sattelite, this is a bit more expensive than compiling GnuPG.

Now I'll make another huge assumption. Even if the part of getting the sattelite transmission was solved and is real cheap, who sends up sattelites to space? usually governments or really big corporations. Do we trust them to use a real random engine? it's in their interest to have access to our messages. In fast the 24 GPS sattelites are owned by the US, they made it very clear that if a war ever breaks where the US army can use a blackout for its advantage, they change the signals and maybe even sattelite paths of that system so only their equipment stays tuned.

I say it's much simpler to build a 50 cent real random generator chip to be installed on every motherboard and PDA for use with our current style cryptosystems ("assume not enough computer power").

now THAT is a cute chalange. a tiny ADC sampling a noisy crude resistor or some other phenomenon. the white noise of radio reception when opening up to a wide band of frequency. to recreate that stream of numbers you have to record an unknown amount of radio noise within an unknown frequency range at the very same physical place as the original recorded stream and the same magnetic interference.

Re:provably unbreakable?

[lambda]

1 + 1 = 2 is not an axiom, is is the conclusion of various theorems that come from the construction of the natural numbers. The assumptions math is developed from are not very specific to numbers.

An interesting idea, but issues...

[Whip]

This is certainly an interesting idea, but it does not really solve any of the fundamental problems with cryptography. Modern cryptography itself is essentially unbreakable -- Grab one of the variable-key-length symmetric ciphers with a big key (256+ bits) and you have crypto that is, in and of itself, essentially unbreakable. The problem isn't the cryptography, really, it's the stuff around it -- The users, the software, and the key-exchange mechanism. In modern times, if you want to steal someone's secrets, a full frontal assault on the actual cryptography is almost certainly the worst possible way to attack.

This solution doesn't address any of those issues -- and, to some degree, it complexifies them. Key management, for example, becomes even more complex.

For this to work, you have to have a secure way to transmit the "keys" that tell you what parts of the random bitstream to use. Presumably, this would still make use of traditional cryptography and traditional key exchange mechanisms. This means, that if someone can break your key exchange, they can break the rest of your message.

There is one thing that makes this more complicated: Once you crack the key exchange, you still need to have the random bitstream for the relevant period of time on disk somewhere to decrypt the actual message. In a poorly designed system, this might be easy -- As soon as an attacker sees a message (presumably the key exchange) cross the wire, record the message and start recording the random bit stream. Record for an hour or so, and then crack the key exchange at your leisure -- You'll have the random bitstream on file for the propper period of time when you're done.

This can be avoided by temporally seperating the key exchange from the actual random data being used -- Exchange keys today, get your random data for encrypting tomorrow. This complexifies key management, though -- You can build up a 'cache' of keys to use (since you have to exchange the keys well ahead of time), but what happens if you run out of ready-to-go keys?

There's also nothing that would keep a well-funded attacker from recording the entire random bitstream for as long as they desire -- At a gigabyte a second (how do you even GENERATE that much truly random data?), that's only 600TB a week -- Split that between 600 recording systems, and you have 1Tb/system/week, which is not too far beyond the real of feasability. (This can scale as large as you like, limited only by real estate and money).

Basically what this proposal would do is make it more expensive to perform a direct attack on the cryptography guarding a communication ... Which, when you think about it, is prettymuch the point of cryptography. To gain this, though, you must deploy a very expensive infrastructure and software that is potentially more complex than current cryptosystems. The benefit you get from this is negligable -- Modern cryptography is essentially unbreakable, so going from "essentially unbreakable" to "more essentially unbreakable" doesn't really help you. ("You're stupid to infinity" ... "You're stupid to infinity times two!").

The real problems (people, software, key exchange), the ones that are the security problems in the real world, aren't addressed at all. This proposal is solving a problem that has already been solved and doesn't (currently, at least) need re-solving.

All that being said, I think this whole thing is a really nifty idea. I don't think it has a practical use, but it did make me stop and think. As an academic exercise, it's pretty durned neat.

Re:provably unbreakable?

[Bazman]

So there's no proof that you can't trisect an angle, or square a circle, or find integer solutions of x^n+y^n=z^n for n > 2 (and x,y,z != 0)?

Baz

How do they agree the start time?

[adamwood]

I've only scan read the NY Times article, but it seems to boil down to agreeing a start time to read from the one time pad. How is this done securely?

Re:How do they agree the start time?

[fatphil]

They have to do it via a "secure channel".
Namely, ordinary crypto.
"then you crack that channel first..." I hear you say!
Except by the time you've worked out where the in the random stream you should find the pad that's been used you've filled up every hard disk in the world two times over. Or something like that.

Personally I don't really buy it. How do you trust your random stream? What if someone pushes storage capacities up by 10^12? What if you want to _store_ the message?

I prefer to hide behind the strong crypto energy estimate - for a deterministic process, there's only so much computing that can be done due to energy requirements. Sure, as soon as ND systems become a reality then I'll rethink...

FatPhil
--

Re:Only secure when YOU generate the key/randomstr

[EJB]

Nah, that's not true. The only two things to be done in real-time in this proposed algorithm is sending the time at which the "snapshot" of the keystream must be made from Alice to Bob, and recording some part of the keystream at the time of the snapshot. Encrypting the message by Alice (XOR) with the snapshot taken from the keystream can be done later (but not much later or the snapshot on the harddisk may have been compromised), the ciphertext is then sent from Alice to Bob, and Bob can decrypt the message when he wants for as long as he keept the snapshot from the keystream on his disk.

So this is not your problem, there are way bigger problems if you want to introduce this algorithm in practice.

Like, if Carol is the one that's broadcasting a keystream, then Mallory could be trying to introduce noise (continuously) into the keystream to make it biased, and she could try to find the bias back in the ciphertext from Alice to Bob if she can intercept it. For example, if the bias allows Mallory to find out at what time the snapshot from the keystream was made, she could try to crack the private key that Alice used to encrypt the first message that contained the time of the snapshot to Bob, en then Mallory could decrypt any future communications between Alice and Bob because she knows when to listen and record the keystream.
Or the bias in itself could help Mallory to decrypt the ciphertext.

Or... Mallory could pretend to be Carol and use an algorithmic PRNG to generate a keystream that seems to be random. But if the algorithm has the right properties, Mallory could either recreate any part of the keystream if she knows at which time the snapshot was made by Alice and Bob, or even more advanced she could use some knowledge of the plaintext (like if it was in English) and determine at which point in time the snapshot must have been taken from her algorithmic PRNG.

Erwin

Somewhat related question

[Compuser]

Since crypto is mentioned, I'll ask a
question that bothered me for a while.
Say you had a message and a key, such that
both were identical. What encryption
algorithm today would be most secure
under this setting.
Example: store password encrypted with
itself. When user enters password, decrypt
encrypted message and compare with password
entered. Given that passwords are small
eficiency of algrotithm is unimportant.
What is the best encryption method (defined
as time to decryption on a predefined turing
machine) for this purpose?

Re:Seems a tad absolute (bzzzt)

[Slugbait]

One time pads are provably secure. Proof (as always) hold with respect to a collection of assumptions. In this case the assumptions include the existence of a publically readable source of random bits that is too copious to be stored. Other "provably secure" systems exist (e.g. Cramer- Shoup which assumes the Decision Diffie-Hellman assumption).

strange...

[cpeterso]

Your solution sounds a lot like the same solution I already proposed:

me: And what about satellite latency? The random number stream must use sequence numbers because I doubt the sender and receiver can syncrhonize their CPU clocks to run at exactly the same 10 million reads per second rate!

you: simple to solve, include a second syncronization number (which are sequential) with each random number sent.

Re:Yawn

[QuMa]

One time pads are completely unbreakable (read "Applied Cryptography" if you doubt me).
Yes, of course, I didn't claim they where.

The problem is, if you want to use a OTP, you can't have a key smaller than the plaintext. This does have a key smaller than the plaintext, hence it is not a OTP, hence it is not proven secure.

Yawn

[QuMa]

Read the sci.crypt threads on using a blum-blum-schub random generator for creating a one-time pad on dejanews... This is just more of the same. Sure, he might have found a better PRNG for doing it, but it's still just as breakable as anything, and certainly nothing new.

Re:Yawn

[Tim C]

One time pads are completely unbreakable (read "Applied Cryptography" if you doubt me).

That's just as long as you never reuse the pad, the pad is truly random, and you never reveal the pad to anyone else.

The biggest problem with OTPs, as with most crypto systems, is key distribution. That's basically what this guy thinks he's solved, but I'm not convinced. As others have also said, I don't think it's unfeasible for an attacker to intercept the "start" message, and synchronise their reading of the stream (the pad) with that of the correspondents.

IMHO, the only truly secure way to distribute an OTP is to write it down/burn it to CD/whatever, and hand it to the other party yourself (then hope that no-one ever steals/copies it...). Then, the "only" problem you have is generating the random sequence in the first place, which is non-trivial (especially if you're planning on encrypting large messages, where patterns are more likely to show up if the sequence repeats)

Cheers,

Tim

Re:Unbreakable - you mean like the comb?

[AstroJetson]

Exactly.

Enigma was about as unbreakable as you could get back then. The reason it was broken had nothing to do with the cypher itself being weak. It was broken because of sloppy procedures: easily discovered initial settings (like H-I-T-L-E-R), the use of common phrases within the cyphertext (aka cribs), not randomizing the wheels after encrypting a message, etc. And the reason they were sloppy is that they thought it was unbreakable. The irony is that if they had not believed that, it probably would have been unbreakable.

As someone else pointed out, a cypher system is as strong as its weakest link and that's usually the gray matter at either end of the encryption.

Re:Unbreakable ? Not possible.

[Kaa]

We certainly don't know if radioactive decay is truly random. It could well be governed by something else. Pick your FTL hidden-variable of the day...

Remember, we are talking about FBI/CIA/NSA reading people's mail. If FBI knows that radioactive decay isn't truly random, but is not telling anyone... Oh, I see. The aliens must have told them.

Kaa

Re:Seems a tad absolute

[Kaa]

AFAIK one-time pads are proven to be impossible to break. I don't think Bruce Schneider contests that.

Kaa

Re:Unbreakable ? Not possible.

[Kaa]

The mathematical formulaes involved in cryptographic equations rely on pseudo-complex number generation

Not necessarily. You can get true randomness by e.g. observing radioactive decay.

Kaa

Re:I have an unbreakable code:

[RovingSlug]

A. your code isn't unbreakable. With enough time something with so few of characters could be cracked by brute force methods alone.

Excuse me? Are we looking at the same C source code? Can you read C?

Because he just wrote over his message with zeros.

Do you maintain that given the message "000000000", you can determine that means "I'm cool!" instead of "You suck!" or any of the other, say, 1e18 possibilties?

And that's his point: it's nothing interesting and it's nothing new. If you can guarantee your stream of random numbers is truly random and only you and your recipient know those random numbers, then any one "decription" by an eavesdropper is no more likely than any other.

I'm too lazy to say more.

michael, since when are you a cryptographer?

[jbf]

"much-snake-oil,-few-insights?" I think anyone with a relatively strong background in crypto (I've had two grad level classes) and math (I'm a BS in pure math) understand that Rabin's got something to offer here.

Typically, breaking a code is compute-bound. That means you can store it, and wait a while for supercomputers to get faster, and then break it. Rabin has developed a system in which unlimited compute power in the future doesn't help you without unlimited storage power now.

You're wrong about insecurity being as bad as public-key. If you can securely trade keys once, you can chain (ie message 1 includes the key for message 2), since messages can't be remembered for decoding (otherwise you crack one message and get the rest for free)

The real challenge is finding a trusted source for random numbers at that high a rate.

It's not a one-time pad, since the pad can be public.

It's a lot like a Rip van Winkle cipher, as I pointed out before, and I doubt there are many people whi've thought of this very good idea before. If that's "few insights," perhaps you should start publishing in cryptography conferences.

Peer review

[AlpineR]

Any general audience newspaper is likely to have many errors and omissions when discussing a technical topic.

Has Rabin's scheme been published in a scientific journal? I didn't see any mention in the NYT article and couldn't find anything in a brief literature search. That would be the proper source to critique. And, I think many in the Slashdot audience have the background to review it intelligently.

Just because he says he has a proof doesn't mean that it's right. Nobody is infallible, and in my experience every scientific paper has at least one error. Peer review is a key feature of open source software, so it shouldn't be surprising that this article is getting so much constructive criticism here.

AlpineR

Re:Hey, people, show a little respect!

[Multics]

It doesn't help that they use as a 'credible source' Rich DeMillo. Dr DeMillo doesn't play well with others (ask the people at GA Tech or PU where he is unwelcome to return other than to visit) and his resume (at the HP web site -- search for his name) is that of one who takes his toys and plays elsewhere when he doesn't get his way.

He lacks the credentials to give a good or bad stamp on this scheme.

How he ended up at HP is anyone's guess, but I'll bet he's not there very long before Fiona gets a clue and gives him his walking papers.

Re:Does this work?

[AndrewHowe]

Heh, I guess you didn't read the article then...

Re:provably unbreakable?

[virve]

It is possible to prove the impossibility of something. An easy example is the impossibility of writing sqrt(2) as a rational number.
Mathematics is full of proofs of things being impossible. Don't mention Wiles' proof of Fermat's Last Theorem because that is way out of reach for the layman, whereas square root 2 is not rational is dead easy...

Re:oops.

[virve]

You are completely wrong here. They - mathematicians - do exactly know what real numbers are and no new magical _real_ numbers will be found. Remember that (real numbers/whatever) was invented by themselves. :-) When mathematicians makes statements to the effect that something cannot be done then it _is_ impossible.
In this case there are and cannot be any real number x such that x^2 < 0. Sometimes it is possible to make constructions that circumvent the rules but that does not invalidate proofs of impossibility. Such proofs are always carefully stated as to which assumptions they are build upon. (That's why the word _real_ is important in the statement about x^2.)

In the case of Rabin et al.'s results what they have actually shown is - as I understand it - in a sense much weaker since they only claim that their breaking their algorithm is as hard as solving a well known computationally hard problem. Perhaps somebody can expand on this.

Here I am,

[Godfree^]

right at the bottom of the article, with this key generation system that I came up with last year, and no one is ever going to see it. Oh well.

I'm prolly even going to get modded down where no one can see it. All because I like to stay in bed till 2PM...

Re:The Fatal Assumptions

[RussRoss]

I thought factoring was NP-complete, in which case all (all, he says ^_^) you should need to do is make the keyspace large enough such that it would take a hundred years to crack even if every elementary particle in the universe were used to crack it. But I'm quite possibly wrong (and we haven't gotten to NP-completeness in my algorithms class yet ^_^)

Actually, it's not known to be NP-complete, i.e., it hasn't been proved. You aren't alone in thinking it is; I've seen quite a few people make that assumption. One of the unsolved problems in complexity theory is the question of whether or not NP = co-NP. It turns out that if factoring is NP-complete then NP = co-NP (I can point you to more details if you are interested), so it's actually a little bigger question than many people realize.

- Russ

Re:The Fatal Assumptions

[RussRoss]

> He hasn't solved the key distribution problem.

True, but he doesn't claim to do so. He assumes that a reasonable distribution method exists that can resist attack for some relatively short period of time. I agree with you that he relies on assumptions, and this is one of them. However, I also think that this is a relatively safe assumption, and to say that his scheme falls apart because of this assumption is too strong a statement.

Existing key distribution protocols such as Diffie-Helmen work well enough for passing secret keys around, but they are only secure for a limited time (hopefully a long time, but finite nonetheless). An important stream of data transmitted using that secret key is then only secure for as long as it takes the opponent to either crack the secret key directly or to crack the key exchange protocol (which would yield the secret key). Large keys and a trusted protocol give us a good measure of assurance, but we are vulnerable to future advances in the field. If someone finds a fast factoring algorithm, then he could go back and easily decode lots of transactions whose 128 bit secret keys were transmitted using RSA for protection.

Rabin's proposal eliminates this future uncertainty, and that's the crux of his idea. The window of vulnerability is limited--if the attacker can't find the secret key quickly, then even if he finds it later it will do him no good.

> He's smart, so it must work? Yeah, right.

I agree with you on this as well. However, I do think that an argument by someone like Rabin deserves a little extra thought before a rebuttle is made. I've attended talks and classes by him, and also talks where he's been in the audience and asked questions of the speaker. He drills right to the weak points and very little gets past him. I'm not saying he's infallible, but I'd be pretty surprised if he missed any obvious points. He also atracts a high caliber of peers to review his work (people like Ron Rivest at MIT) and it's unlikely they'd let obvious errors slide by.

> I do have to at least be leary of the
> assumption that storage is a more finite
> resource than computing power.

I'd have to agree with you on this one. It's obviously not practical for any but a few applications. Still, I think it's interesting in that, given a few assumptions (which he does lay out clearly even if the NYT doesn't), he can prove that your data will be secure forever. If the secret key is safe for a given amount of time, then the rest of your data is secure forever. Pretty interesting, I think, even if it's not terribly practical for most users.

- Russ

p.s. I apologize if my tone was beligerent before.

Re:provably unbreakable?

[the_great_cornholio]

You obviously need to learn to understand sarcasam.

Re:I have an unbreakable code:

[eddeye]

>It is true that a one-time pad is not breakable.

That's not quite true. It's true that a one-time pad has a very low probability of being "broken", i.e. of recovering the message sent. You can always break any cryptosystem by simply guessing the message that was sent. If the original message was n bits long, you have a 1/2^n probability of being correct.

The difference between one-time pads and other cryptosystems is that with others you can conceivably recover the message with 100% certainty if you have access to enough computing resources (such as being able to brute-force the key). Of course any good cryptosystem makes it hard to enough to recover the message that it becomes impossible within the limits of available computing resources.

Re:Just break the protocol

[graniteMonkey]

Absolutely true. The interesting thing about this idea, though, is that, if true, it shifts the focus entirely and without a doubt beyond the algorithm. If you could actually prove an algorithm's unbreakability, then research could be spent elsewhere, and all the freaks/charlatans/conspiracy theorists can put this job next to their "work" in geometry.

Re:Seems a tad absolute

[MWright]

You can prove that certain systems are unbreakable, under certain conditions. For example, one time pads, as long as they are generated using true random numbers, and that each pad is used only once, are provably unbreakable. However, the difficulty in distributing the pads means that it's not too useful.


-----

This must be a hoax ...

[aCoder]

Did anyone else notice the quote from "Dr. Cipher Deavours, a professor of computer science and mathematics at Kean University"? His middle initial is surely N.

Re:This must be a hoax ...

[njyoder]

Did anyone else notice the quote from "Dr. Cipher Deavours, a professor of computer science and mathematics at Kean University"? His middle initial is surely N.

Actually it is "A". Search for "cipher deavours" on google.

Re:I have an unbreakable code:

[devjoe]

His biggest assumption seems to be that nobody can archive all the data coming from the random source. However, data storage capacity has long been increasing exponentially with time, while (if the data rate from the source is constant) the total amount of random data to be stored increases only linearly with time. Eventually (and probably quickly), you will need faster and faster sources of random data for this assumption to be true.

Provable Secure? Not at all!

[gweihir]

First it relies on the secure exchange of the starting point in the data stream. Breake that before the point is reached and you have broken the actual message.

Secondly it relies on the price of connection speed vs. the price of storage. Now my present connection actually has a speed of roughly 8MB/sec. If I stipulate at most 10% of my bandwidth for the random stream that is 800KB/sec. That is arounf 70GB/day. A onstream 15GB cartridge costs about 40 Euros. That makes about 200 Euros/day for the storage of the stream. This is less than 100.000 Euros/Year! And that is the promitive solution I could implement myself! O.K., I would need to share the Database with 10 or so others in order to be able to afford it, but this is a low cost approach! The one employee handling the system is probably as expensive as the system itself.

Now replace the low-cost system with a tape library for some million Euros (a _small_ investment) and you are done. For predictions of the future just scale bandwidth and storage size accordibngly, but do not scale the costs!

Ridicoulus. Theoretically secure, but practically not at all (with reasonable constraints). Arno

Wise-assed remarks enclosed. =)

[rakslice]

Heh... Law enforcement people who natter on about the dangers of encryption (or privacy in general), but who like to call irc channels full of anonymous kiddie pr0n traders "online pedophile rings" after they bust them to get more media attention, and who confiscate equipment when serving search warrants and then keep it indefinitely as punishment for _not_ having committed a crime, get more laughs than sympathy from me.

"Now I'm not saying that this technology should be stopped, but with all new technology, there has to be regulation to ensure it is not used."

With statements like that one, this guy should consider a career in politics.

Re:A MESSAGE FOR ABRAM

[rakslice]

Oh man... The funniest bad translation I've seen was the "do not leave in direct sunlight"-type note that came inside my case logic(tm) cd case. It's too bad that I didn't save it... Anyone know the one I'm talking about?

Re:provably unbreakable?

[rakslice]

You're on crack. Math isn't physics, fool. =)

Re:provably unbreakable?

[rakslice]

Ok, Signal 11: What is the highest prime number?

Re:provably unbreakable?

[rakslice]

WTF is a negative assertion?

Re:provably unbreakable?

[rakslice]

But that the statements are qualified does not make them any less part of the category that was identified.

Science: "all you can do is approximate the truth more and more closely." Please replace "truth" with "experimental results". Thank you.

What is an unqualified statement?
Your statement about reindeer is a qualified statement.. It depends on the definitions of "reindeer", "flying", etc. Is there such a thing as an unqualified statement?

Re:provably unbreakable?

[rakslice]

"do not exist independant of the human mind" -- was that what you meant to say? Obviously, they're independent of physics.

Re:provably unbreakable?

[rakslice]

Were you trying to respond?

"the plus operator '+'" is not an assertion. How could it be proven or disproven? That would be like me asserting "rubber chicken" or "walking to the store to buy a new package of razor blades" or "pink" or "five o'clock".

Please take an introductory algebra course before you go using the word "axiom". 1+1=2 is not an axiom, but is provable from axioms of the natural numbers, assuming the axiom symbolic "+" and "=", and assuming that "2" is the successor to "1" and that "1" is the unit value.

Re:provably unbreakable?

[jarran]

You can - proof by refutation. If you assume something can be done, and if that assumption leads you to a contradiction you have proved it cannot be done.

3 unbreakable systems

[renard]

The best you can do is to state I am not able to break it and then let the crypto community rip it apart.

I'll just run through the counterexamples:

1. A one-time pad is unbreakable;
2. Quantum cryptography, which is cryptographically the same as a one-time pad, but allows you to send the pad over an insecure channel, is unbreakable;
3. Rabin's proposal, which is cryptographically the same as a one-time pad, but allows you to share the pad over an insecure channel as long as you have the ability to communicate in a way that will not be immediately compromised by the eavesdropper, is unbreakable. This can be accomplished, i.e., via Diffie-Hellman key construction or conventional public-key cryptography.

Any particular implementation of these methods will, of course, be subject to numerous attacks. This point is made best in the article by Robert Morris, formerly of the NSA, who suggests "the three B's: burglary, bribery, or blackmail."

-Renard

This is a KNOWN cipher ( Rip Van Winkle )

[backslashdot]

He is using a cipher called Rip Van Winkle. Any cryptographer knows it. Go look it up! try google or any good cryptography book.

Re:Seems a tad absolute

[Martin S.]

Actually, one time pad crypto systems are provably secure.

I dispute that the it's *provably* secure. If you you have a proof, or a reference please post.

And I mean a real formal mathmatical proof, not just a description of WHY a OTP is secure, such as that found in Schineier's Applied Crypto.

Re:Clue: Cipher != Code

[Martin S.]

After reading other messages, It's probably worth me being explicit about the fact that this is essentially a One Time pad with several of the safety features compromised.

1) A OTP requires the secrecy of the key, this *unbreakable* system suggests broadcasting the key stream from a satellite, and completely ignores how it might be secured.

2) To remain secure (not uncrackable) a OTP, must be used only once, since the same key stream would be used globally this would not hold true.

Either of these are massive flaws; individually capable of compromising the whole system, together they make it worthless.

Re:One time pad is secure

[Martin S.]

You asked for it, you get it. First, I'll explain what a one time pad is:... This is a description not a Proof!

Re:provably unbreakable?

[MadX]

>So there's no proof that you can't trisect an angle, or square a circle, or find integer solutions of x^n+y^n=z^n for n > 2 Fermet's Last Therom .. proved in the mid 90's .. x^n+y^n != z^n where n > 2

Re:I have an unbreakable code:

[drnomad]

This is a trivial one... and a bit sneaky as well. An 'today's' problem of mankind is, that we can't define the characteristics of 'information', that's why you see all funny stuff in the MPAA vs 2600.org conflict (you know - painting pictures with DeCSS code, or making MP3's with DeCSS Lyrics).
Lacking the proof of 'what-is-information' does not mean that *erasing* and *encrypting* information is the same thing, you cannot prove that, not even when fundamental knowledge is missing. You can't confuse cold and heat, not even when you have not invented fire yet.

Re:provably unbreakable?

[drnomad]

Hypothesis: You can't find a real number "x" such that x^2 Proof: Left as an excersise for the reader

Easy, the plus operator '+' is something which can't be proven mathematically, this means that 1+1=2 is an axiom - an unprovable assumption, maybe we could call it 'rule'. Such is the case with negative and positive numbers, change the rules and you will find an X^2 number smaller than zero.

I must say that Mathematics is a very well researched science, we cannot prove that a super-mathematics does not exist. Is this a troll? I'm just comparing Boolean Logic with Fuzzy Logic; could a new science replace the maths we know today?

How misleading...

[masklin]

This story, and the system itself, is very misleading. Yes, the mathematics of the encryption scheme is provably secure. If you take a string of provably random numbers and combine it with the message text, the cipher text is totally unreadable without knowing the exact string of random numbers. This is trivially provable. But the whole scheme is made weak by how you share the exact string of random numbers with the recipient. (I'm going to assume that the numbers are truely random). Basically in this scheme it boils down having a continuous output of random numbers that the world can read - and a way of telling the recipient when to start reading the numbers (and possibly a steping factor - eg. read only every 3rd number). If anyone can break the system you use for communicating that information - or can work it out for themselves - then the message will be retrieved. Note that this is NOT a break of the encryption since the message was retrieved by someone who knew the entire key (the random string). This is why he can claim the provability of the mathematics, but it doesn't mean that the message couldn't be read by anyone else. In the report there are NO claims of the security of the initial "START" communication - and the only claim on the security of the random stream is that there would be too much information to store in order to retrieve the message - something which is NOT provable (especially when you consider that you only need a subset of the stream from between the START and the end of the message). The report actually gets this point entirely wrong when they claim "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.". This is untrue. If I have a technique that takes one minute to break the "start" message - then I only need to buffer 1 minute of the random data stream. This is trivial. In reality, you only need to buffer numbers from either: 1) When the "start" message is sent until you have decrypted the "start" message (1 minute in the example). 2) When the "start" message is sent until the end of the message transmission. The lesser of the two is the amount of data that needs to be buffered. In summary, the scheme is not weak in the mathematics, but is made much weaker by the way of obtaining the random numbers. And the claim that it is impossible to store that much data is unprovable and possibly false. Hence why the scheme and the report is soo misleading.

Re:Seems a tad absolute

[Tom7]

I'd trust Rabin before I trusted Schneier, actually. After all, Schneier writes about Rabin's algorithms in his book, not the other way around...

Can you prove that proving a cryptosystem unbreakable is impossible? I think it's pretty easy for something like the "one time pad", actually.

Re:I have an unbreakable code:

[Tom7]

I think he has probably proved that it is secure under some more useful assumptions. But, since the NYT has not really explained what kind of metatheory he used to prove it correct, we can hardly say here, right?

Re:Unbreakable cryptography

[belroth]

Exactly, so any encrypted messages that are intercepted are very likely to be concerning illegal activities. Therefore the FBI/CIA/MI5/MI6 etc will waste less time decoding emails from /. reader about a certain Star Wars actress.
It would be a net win for the cops because they can waste less resources on trivia - at least that's probably how they would see it.
----

Re:I have an unbreakable code:

[Thiarna]

So few characters where? Do you mean the size of the program?!?

Re:Does this work?

[pallex]

http://lavarand.sgi.com/

Re:Seems a tad absolute

[simon_cockle]

Check out quantum crypt.
Messages sent using time pads are impossibe to break.
Any system built on one time pads is unbreakable so long as the distribution of the pads (or equiv.) is secure.
These things are provable, you quoted Bruce out of context.
Check out quantum crypt.

Re:Unbreakable cryptography

[Hellburner]

If you have nothing to hide...you have nothing to fear.

Don't feed the trolls but...

Are you freaking serious? There is no factor that renders "government" free of criminal intent. It only varies in the amount in which the particular government is criminal.

Oh christ...just forget it. If you were kidding, you are a clever satirist. If you were not kidding, you are eloquently describing my need to colonize another planet.

Re:'Infeasable' [sic] decryption, not 'impossible'

[The Cookie Monster]

Surely the only storage requirement to break the scheme is:

BandwidthOfDataStream * (TimeTakenToDecryptStartKey + BreathingSpaceForHumans)

Unless the datastream keeps speeding up, that requirement of storage space is a constant, and not increasing at all. Also, as Kevin said, with quantum computers around the corner TimeTakenToDecryptStartKey may become insignificant.

I assume (and agree with you that I can't tell from the NYT article - so would appreciate your feedback) that what Rabin has proved is that it is not possible to decrypt every message encoded in this system, as opposed to proving it impossible to decrypt any message encoded in the system.

Having said this, I think a method like this getting lots of public exposure is excellent, as (regardless of practical security) I've been waiting for cryptogrphy to shift to a time based sytem where after t time, a message and all its copies will expire permenently. This is something he appears to have proved, and with the publicity, this thing might just happen.

Am I missing something?

[kill -9 $$]

Obviously his encryption system is based on the one time pad theory. And of course the weak point of this algorithm is keeping the pad secret. His suggestion is that sender and receiver initialize to some point in a transfer stream from a satellite perhaps. But my question is, if I capture the initial handshake encrypted by conventional means and crack that (to get the starting point), the stream of random numbers being generated over a period of time, preferably sometime before the handshake starts until the transmission is done, what's to stop me from cracking it?

A bit more brute force, skip cracking the initial handshake. What if I just listen to the random number generator and start a brute force search starting with the first number before the handshake takes place and stopping sometime after transmission has ended. When you can "read" the message, you've cracked it...

Anyway, in the end, the goal is keeping the pad secret. To sound like a textbook, if Bob is on the Earth and Alice is on the moon, you need a pad that the eavesdropper Trudy cannot access. I'm not convinced that he has done this...

Re:I have an unbreakable code:

[chinacat]

A. your code isn't unbreakable. With enough time something with so few of characters could be cracked by brute force methods alone. Not to mention that this could be done in less than exponential time.

But more importantly, you have to look at who is giving us this algorithm, Rabin of the Yao-Rabin-Simon Protocol. You know, that little thing that allows us to not only transfer enormous amounts of data over a far spaces in short time, but also allows us to buy our daily crap over the internet.

For sure this will be a very important algorithm in the future.

Re:Unexpected argument in favor of Open Source

[Grotus]

That is only good for the source code in general, who is to say that the compiled binary used on one particular voting machine was built from the unmodified source?

Forgive me...offtopic I know...

[clary]

But I couldn't resist this troll...

"Ordinary law abiding citizens" dramatically increase the chance of killing someone in their home if they own a gun.

This looks suspiciously like an adaptation of the bogus, but often repeated "A gun in the home is 43 times more likely to kill a family member than an intruder" statistic. Look here for some explanation and rebuttal. I suggest reading some of the arguments for and against the utility of owning firearms, and possibly reconsidering your position. The link above from the Cato Institute is obviously pro-gun-ownership. The NRA and Handgun Control, Inc. are good jumping off points for many other sites, both pro and anti.

Most people are unlikely to go out of their way to buy a handgun, but if it is readily available then they may well do so.

I don't know about most, but certainly 10s of millions of people in the US already own handguns. And guess what? The Brady Law, when in effect, applied to them as well as to people who did not own handguns! What possible good could a waiting period (beyond what is required for a criminal check) do in those cases?

The very phrasing of your comment shows that you view a waiting period as a way to discourage the lawful ownership of a handgun, rather than as a means of doing a legitimate criminal check, or as a (dubious) means of stopping "crimes of passion."

This is Bull s**t...

[X=X 0]

My first problem with this is that it seems as though this type of system is only workable in live communication situations and doesn't help when trying to store an encrypted message. How does that help? My second problem with this system is the fact that anyone could probably intercept the random number stream since it's being broadcast. It's probably true that someone who is intercepting the message can't decrypt it later but what about someone who tries to decrypt it right away? If they're listening to the random bit stream they could beat this encryption instantaneously....

Re:Unbreakable cryptography

[Ziest]

the fact that your email to your friend is insecure from the government should not bother you, since if you have nothing to hide, you have nothing to worry about.

You are a fool. Using your favorite search engine, look up COINTELPRO then tell me you have nothing to fear from this goverment.

Wake Up People

Re:Unbreakable cryptography

[boto]

Yoshi Have Big Tail wrote:
"...the fact that your email to your friend is insecure from the government should not bother you, since if you have nothing to hide, you have nothing to worry about."

It sounds like George Orwell`s book "nineteen eighty-four"

Do you really think the government should have unrestricted access to all you information?

Ok, then let's put "telescreens" in your home. Then your government can "protect" your country.

We don't need more laws about encryption, the usa encryption-export laws is already annoying stuff.

I hope there is no people who thinks like you in Brazil.

(sorry by the horrible english spelling)

Boto
--
Curitiba - PR - Brazil

Seems a bit flawed to me

[grahamsz]

First of all if I happen to know that communication was taking place at a certain time then I can quite feasibly capture a few minutes of the one-time-pad and this dramatically narrows the search field.

Secondly there is the obvious problem of generating a random and infinite one time pad, which is one hell of a problem.

Thirdly this assumes that you have tightly sychnorized communication - it's not a lot of use for emailing my encrypted 'thoughts' to my girlfriend.

Fourthly there's nothing new about one time pads - they have been in common use for the last 40 years and I dont really see how this method evades the problem of key distribution (except for the fact that it's transformed into "key sychronisation").

Fifthly if two pairs of parties start communicating at the same instant - wont they be using the same keys.

Sixthly he bases his hypothesis that computers have a limited amount of storage and power. Firstly consider 10 million bytes a second - i could quite happily store an hours worth of keys on my computer. As for computing power, we are reassured that quantum computing will be just around the corner and where will this fit in if computers can run an infinite number of simultaneous calculations...? It'll be dead just like rsa will be

Is this just a one-time pad?

[stain ain]

Could someone please post a link or an explanation on how the system works?
I have read the NYT article and cannot get the point unless this is nothing more than a one-time pad.
But if it is a one-time pad, then it is not big news, one-time pads have been around for quite a while.
But the problem with one-time pads is that you have to store the key some place, since afterall a cryptosystem that is useful must be able to recover the unencrypted message from the encrypted version (oh, really?) and to do that you need the key, I can't see how can "The key vanish" in a cryptosystem and still be possible to recover the message again.
I don't understand this "novel approach" at all. Will somebody help me understand?

Re:'Infeasable' [sic] decryption, not 'impossible'

[ajna]

I have a few comments in response to Kevin Fox's assertions, which although highly moderated, are as "bogus" as he thinks Rabin's views are.

Kevin writes that an "arbitrarily large array of recording devices would be able to accomplish the task [of recording an arbitrarily high bandwidth datastream]." This is incorrect, although I don't blame him considering that his only exposure to the scheme is through the NYTimes. Why this incorrect:

Consider the state of recording technology at a given moment: one might be able to record X TB at a bandwidth of Y GB/sec on one recording unit. No matter how many of this units one strings together in a RAID array or any other configuration, it is not possible to store an infinite amount of data. But since the satellites/random data source constantly stream random data, the amount of information that must be stored is effectively infinite.

So there must be a limit on the amount of data that can be stored by an adversary. Call this amount of data that can be stored D. For any D, it is possible to have enough satellites streaming data that the amount of data streamed over the time that it takes to break the (normally encrypted) key saying where to start looking in this stream is greater than D.

So Kevin, are you saying that D can be increased arbitrarily without end? Because that is the only way your argument would make sense. Also, regarding your second argument, that the start key is vulnerable as it is encrypted conventionally: that is the whole point of this scheme, that the key could be broken in some amount of time, a time in which, unfortunately for the adversary, the amount of data streamed by is too great to be recorded.

My background as it relates to this scheme: Rabin gave a lecture on this last spring to a class I attended, and I talked with him afterwards, and he confirmed that I understood it properly. Also, two of my roommates took Rabin's cryptography class last semester, in which this scheme was covered.

Non-technical rebuttal

[DigitalSorceress]

My only thought here, not being at all an expert on cryptography, but here goes...

The one problem I have with "Unbreakable" is that it sounds a lot like "Unsinkable"...

As Dr.Who once said: "... and what's wrong with 'unsinkable?'... `Nothing`, said the iceburg to the Titanic"

+++++++++++++++++++++

Ueli Maurer invented this cryptosystem

[Nr__9]

I think it's very important to point out that this cryptosystem was, in fact, first proposed by Ueli Maurer (see Conditionally-Perfect Secrecy and a Provably-Secure Randomized Cipher, Journal of Cryptology, vol. 5, no. 1, pp. 53-66, 1992).

Michael Rabin only came up with a (very obscure) proof that the system was secure under more general types of attacks.

Please also note that this cryptosystem, although it's very nice, has no practical use. Quantum cryptography propose a much more efficient solution for unconditionally secure cryptography (and quantum cryptography is no practical either).

Julien

My data is so secure. . .

[ishpeck]

. . . nobody get get it! Y'know why? Because I got sick of my fscking 56k connection and used it for target practice and I don't get any DSL/Cable service where I live.

Re:oops.

[CarrotLord]

No, you missed the point -- the point is that you _can_ _prove_ that there is no real number such that ... etc..., not that we can't find it. I can _prove_ that we can't find it by proving it doesn't exist.

Another eg is that I can prove that there is no largest natural number:

Axiom: Any natural number added to any other natural number gives a natural number
Assume there is a largest natural number, N.
therefore, N + 1 is a natural number, but seeing as N is the largest natural number, N > N + 1
But that implies that 0 > 1, which is false, hence there is no largest natural number.

Of course, yes, this is within the confines of mathematics as defined by the axioms, and so on, but this goes without saying... Removing the basic axioms (the natural number system, etc) renders the whole framework of mathematics unworkable.

BTW: Assumptions and axioms are different -- axioms are things that are always true, whereas assumptions are things that we assume to be true right now for the purpose of whatever we are doing.

Anyway, point is that it IS possible to prove that something can't be done. It's a common practice in mathematics, and can be done for simple or complex things.

rr

Re:funny story....

[touchstone]

The "limited memory but computationally unbounded" adversary model is not new. And neither is Rabin's scheme (as it is described in the NYT). In fact, Ueli Maurer proposed an almost identical scheme AND the limited memory adversary in "Conditionally-Perfect Secrecy and a Provably-Secure Randomized Cipher" in 1992. I'll be -very- surprised if this work ever sees print in the cryptographic literature, because the reviewers will (probably rightfully) classify it as unoriginal and unimportant.

Still nothing new...

[touchstone]

My biggest issue is that this is NOT new. The limited-memory adversary AND a scheme that is very similar to the one Rabin proposes (**as described by NYT**) appear in Ueli Maurer's "Conditionally-Perfect Secrecy and a Provably-Secure Randomized Cipher" (J. of Cryptology, vol 5, no 1, pp 53-66, 1992). Rabin's addition to Maurer's scheme seems to be the use of public-key encryption to set up a private key, i.e., the index into the random oracle stream. But that's not new, either.

Re:sender and receiver synchronization?

[njyoder]

simple to solve, include a second syncronization number (which are sequential) with each random number sent. It is incremented once for every number, and the sequence number is large enough (i.e. 64-bit) that when a rollover occurs the computers can take that into account. That way the computers could say "start with random number 10,000", instead of saying "start at 5:30:27.00023 PM GMT."

example of the transmission packets:
8723945:10,000
0123494:10,001
4873925:10,002
etc...

Can we say RAID?

[njyoder]

At a rate of 10MB/sec this can easily be stored on a RAID 5 system. With the advent of IDE RAID systems, one can build a 1+TB (terabyte) RAID system with ATA/100 drives for cheap. You can get them pre-built from vendors for a few thousand (U.S.) dollars or less. Or you can build your own for even cheaper. These systems not only have the necessary capacity, but also have more than enough speed.

To start with, you only need to record numbers for the beginning and end of each conversation, and note these systems can be expanded to many terabytes. If we have a 1TB system, we can store 104,857.6 seconds worth of data (1TB / (10MB/sec)). This is 1.21 days of continuous number recording.

You could also argue that you just increase the rate of generated random numbers until this becomes unfeasable, but then you encounter the limitations that the computer can recieve the numbers and process them to begin with. 10MB/sec is 10BaseT speeds, you could increase to 100MB/sec (fast ethernet). When you start getting into rates above this you start saturating the i/o bus, the equipment used to recieve data, and the cpu or other chip used to encrypt data, shy of spending tons more money, but even then you still get these limitations, just higher up.

So, prove that assertion ...

[joel.neely]

... since it claims that such proofs can't be done.

Re:So, prove that assertion ...

[Siqnal 11]

I can't.

--

Where's the paper?

[savoystyle]

Does anyone else think it's wierd that a Google search restricted to harvard.edu for Michael Rabin doesn't turn up a link to his paper? http://www.google.com/search?as_q=Michael+Rabin&nu m=10&btnG=Google+Search&as_oq=&as_epq=&as_eq=&as_o cct=any&lr=&as_dt=i&as_sitesearch=harvard.edu&safe =off With all of the problems with his system that everyone mentioned above, I wanted to get his take on it, not just NYT's version for the non-technical. But I couldn't find it anywhere! And there's no link to it in the NYT article... :(

It's just a high-speed, 1-time pad.

[perikalessin]

Other's comments relate here too. You have to trust the 3rd-party generator of the random numbers to not embed some non-random sync characters. If the ideal exists, and the random numbers are truly random and not compromised, then you're just talking about a 1-time pad.

Re:Practicalities

[swm]

(the NYT article mentioned millions of digits per second)

From the NYT article

The numbers can be coming by at an enormous speed -- 10 million million per second, for example.

They may come at that speed, but I can't receive them at that speed: I don't have terabit ethernet, and I don't know how receive infrared satellite transmissions, and my atomic clock only gives me 100 picosecond resolution, so I can't synchronize my decoder to a 10 THz bit stream.

Now if it is only a billion bits per second, I can probably manage, but then someone else can also capure them on disk and archive them on tape.

Re:Infeasible?

[SnapShot]

The assumption is, I think, that the shear volume of data being sent ("10 million million [random numbers] per second") would be too great to feasibly store enough data to decrypt the message. What does that work out to? 40 terabytes per second with each random number in the range of 0 to 4 billion? If you miss your evesdropping by 10 seconds, your've got a lot of work to do to recreate the message.

This, of course, begs the question of what kind of sattelite is availble to constantly stream 40 terabytes of data per second? It also doesn't seem to answer the question of how you and your friend manage to synchronize your watches closely enough to begin the creation of your "one-time pad" at the same point in the stream. But these are mere "technical" questions; the hard work has been done.

Question: has anyone closely monitored one of those DISH TV satelites to see if there is a constant stream of random numbers embedded in the information (perhaps the Game Show channel -- who would notice if the quality is degraded ;) perhaps the CIA is already using this system? It seems to me that even if the volume of random numbers was much smaller (maybe a megabyte a second) it would still be a useful system for short term messages. Hell, we could build a system right now by generating a stream of random numbers off of some public sattelite broadcast (maybe you and your friend build your one-time pad off of the number of red pixels in the Game Show TV channel from PST 02:23:23.0 to 02:23:24.0 )

The chipher is the least problem IMO...

[Kjella]

Flaws in the system (?!)

1. Look for applications that leak data. A very well known word-processor has an interesting bug that leaks parts of the raw contents of the disk when saving an OLE Compound Document.

2. Look for data that isn't deleted securely. Ok, everyone knows that you can undelete a file easily. Did you know that even a file that has been 'wiped' can potentially be recovered by looking at the surface of the disk. Deleted files should be securely wiped using an appropriate program (PGP v6+ contains a secure file wiping program).

3. Look for data that has leaked in other ways. Temporary files and the swap file spring to mind. These both need to be securely erased too.

4. Using Van Eck monitoring. Basically, electrical emissions from the monitor, hard drive and even keyboard can be detected and recorded from a distance away. This may allow an eavesdropper to see what's on your screen or detect your passphrase as you type it.

5. Brute Forcing. This can happen in a number of ways: they can try brute-forcing your passphrase (its important to use a large passphrase that isn't easily guessed, it helps to use both upper and lower case and numbers as well) or they can try to brute force the algorithm. This is hard work

6. Some ciphers may be susceptible to attacks not known about in public. The NSA/GCHQ *may* have a mechanism faster than brute-force of attacking the algorithms. Who can tell what the Intelligence Agencies can do with Blowfish, IDEA, 3DES et al?

7. Install an amended version on your computer which secretly stores your passphrase so that it can be later read by a CIA agent. (Or use a program like SKIn98 to do it!) Far fetched? Possibly, but you should be aware that this kind of attack exists. There is no real way to defend this attack.

8. Beating you until you spill your passphrase. Truth drugs also work, apparently.

Now *maybe* we can drop #6.. so? It's far from the weakest link in the chain already.

Kjella

Re:Slashdot hubris --Yes

[zigozago]

Agreed. Why most people can't conjecture this, --just this--, I don't understand. (Or maybe yes.)

But the NYT as the: Acta Informatica. This yes.

Re:Only secure when YOU generate the key/randomstr

[Bingo Foo]

OTP is certainly not new. And in fact it's only ever been governments who have the resources to put it into practice. Generating random numbers even at just enough rate to cover all your text is not cheap. No you can't use a cryptorandom number generator. Think about it, if it was an algorithmic generator, you could just give both parties copies of your unbreakable but deterministic generator

What if you use an algorithmic generator to generate a stream of 2048-bit pseudorandom numbers and then only use the 1024 most significant bits in your one-time pad? Then knowledge of the pseudorandom algorithm does no good. A cracker with full knowledge of your algorithm and access to some already used one-time pads still needs all of the lost bits to get an identical stream out of the pseudorandom algorithm to guess at future onetime pads.

Bingo Foo

---

Re:Mod this up

[caffeinated_bunsen]

Considering that light only goes that slowly in a certain Bose-Einstein condensates, you wouldn't have a signal for long. Light propagates through a millimeter of that about as well as it propagates through several meters of solid graphite.

Re:Only secure when YOU generate the key/randomstr

[YKnot]

The number and bandwith of available "random" number streams will increase just like processing power and storage grow. The assumption is that at any given time the amount of data that would have to be stored is massively bigger than what can be stored. If that assumption is true depends on several factors, including Alice's and Bob's laziness, geographic distance between Alice and Bob (streams have to be available unaltered to *both*), timeframe of communication (the longer the more secure), strength of the cryptography used for communicating the stream pointer and probably a lot more. I don't think that this assumption can be proven to be true. I think that factors like laziness of the stream-choosing side are probably a more important reason for failure of such an encryption effort than storage capacity growth.

Re:Only secure when YOU generate the key/randomstr

[YKnot]

No you don't. Well, theoretically, yes, computers are used to generate the streams. But the streams are *generated*, not replayed from storage. Overusing the satellite idea: TV-Streams are not played directly from "tape archives". They are composited from raw content and channel logos, brightness contrast and color are probably adjusted, ads are inserted. And after all that, the stream is compressed. These real time modifications happen all the time and are not stored. While there is limited "raw" content (even that isn't entirely true with live transmissions), the actual stream is always different. Huge streams of data are generated on the fly. In the end, it's of course up to you if you believe that it's too much to store.

Re:I have an unbreakable code:

[YKnot]

He's not describing a one-time pad, since the "pad" is public.

Technically you're right. The difference is in the secrecy of the pad. He substitutes the secure agreement on the pad with a semi-secure agreement on a selection, which is made from a pool of pads so big that it can't be stored. The secrecy of the pad is achieved by delaying the availability of information long enough to make it useless. The pad is lost (equivalent to secret) if the startpoint message can not be compromised before the pad is transmitted. Again, all of this is based on the assumption that the pad-pool can not be recorded.

Re:I have an unbreakable code:

[YKnot]

Yes, this can be compromised. What you think is gone isn't. Check http://slashdot.org/articles/00/07/17/049206.shtml #163

Re:Only secure when YOU generate the key/randomstr

[YKnot]

The key ideas are:

• Encryption is done via one-time-pad. That method is proven to be secure, if the pad is sufficiently random and unknown to attackers.
• The pad is not created by "Alice" or "Bob". Instead, they agree on a publicly available pad. This agreement, not the pad itself, is communicated through a standard cryptography channel, which ensures a reasonable delay before attackers can read the agreement.
• The attacker has to be able to store all possible random pads from the time the agreement was sent to the time when the attacker breaks the encryption of the agreement message.
• The number of available random number streams and the combined bandwith of these streams is high enough to ensure that noone can save these streams long enough to later select the right stream or combination of streams as the decryption pad.

Note that the pad does not have to be transmitted if Alice and Bob can agree on a stream which can be received by both and the set of streams available to both is big enough to ensure no one can store all of these streams. This should generally be possible because there is no reason why only raw streams can be used. Randomness can be created by algorithmically selecting parts of streams. Just like the lowest significant bit of a digitized image is more random than bits of higher significance, this kind of selection is practical for other streams, too.
The weakness is in the assumption that huge amounts of streamdata have to be stored to attack the encrypted link. This assumption is only true if communication is slow: Alice and Bob agree on streamdata from a long timeframe. When Alice and Bob are known to communicate in near real time then their one time pads can only be from a short timeframe and thus the attacker has to store only limited amounts of random streamdata. Security scales with availability of random streams which are available to both sender and receiver and timeframe after which a message must be received.

Re:Wrong

[fatphil]

The +5 is an anathema. The quote is a misrepresentation of what Bruce Schneier has said.
The one time pad, if all the preconditions are satisfied, is provably secure. It does however require a secure channel, which means that there's a possible man in the middle attack, namely if someone steals your pad!

FatPhil
--

Re:provably unbreakable?

[fatphil]

If it's true then it's because the problem was worded wrongly.

You _cannot_ trisect an arbitrary plane angle using only a compass and a straight edge.

Proven, mathematical truth. If you deny it then you deny the whole of maths.

However...

It's possible to construct a device which will permit to to trisect a plane angle but it requires the user to "find the position where point A touches line XY and arc BC is tangent to XZ.
i.e. you're getting the human to manually 'solve' an equally intractable (with straght edge and compass) problem, and then map that _approximately found_ solution onto a solution of the original problem.

FatPhil
--

Re:The Fatal Assumptions

[fatphil]

Grrr! I'm a mathmo, and I'm as cynical about this scheme as you are!

FP.
--

Re:Seems a tad absolute

[wren337]

Read Mr. Schneier's writings on One Time Pads, which this essentially is. They are provably secure, since the entropy is (at least) 1:1.

Like having a password the same length as the message you're encrypting, and only using it once. There's no way to know what the message is without the password.

Thanks for the enlightnment

[CaptainZapp]

OK, that makes sense.

And I appreciate, that you don't just yell *MISQUOTE*, but actually provide educational information.

Apologies to Mr. Schneier for oversimplifying...

Re:Practicalities

[kbeyer]

They may come at that speed, but I can't receive them at that speed: I don't have terabit ethernet, and I don't know how receive infrared satellite transmissions, and my atomic clock only gives me 100 picosecond resolution, so I can't synchronize my decoder to a 10 THz bit stream. Now if it is only a billion bits per second, I can probably manage, but then someone else can also capure them on disk and archive them on tape.

But there can be more than "one" channel to listen to. In a public-key encrypted message the communication partners decide on the channel to listen to and the time to start listening. Your "enemy" will have to record all channels, you only one. You can even agree to change the channels during the message.

The whole system depends on the amount of information sent (there may be even more than one source of information) and the time it takes to brake the information about channel and starting time.

Increasing the amount of information sent is more simple than increasing the amount of information your "enemy" can store.

Re:MODERATORS ON CRACK!!!!!!

[dynoman7]

Thanks. At least someone was paying attention...

-Dynoman7

Unexpected argument in favor of Open Source

[Ereth]

So, right there in the article they say:

"There is no guarantee that your vote actually goes into the computer the way it looks on the touch screen," Dr. Neumann said. "What does it take to buy a computer programmer? A couple of years' salary and a house in the Cayman Islands?"

Well, yes, but that's only true if the source is closed. If the source to that touchscreen application is open, then many other programmers will be able to look at it and SEE if it's compromised, or if the vote actually DOES go into the computer the way it appears on the Touch Screen.

Nice of them to be making our case for us, don't you think?

Re:Unexpected argument in favor of Open Source

[AMK]

PGN has been arguing all along that new voting systems must have their source code available; see comp.risks for the past few months. So why refer to some fearful "them"?

Unbreakable ? Not possible.

[Cliffton Watermore]

1. Here's why:

   The mathematical formulaes involved in cryptographic equations rely on pseudo-complex number generation - now, this in itself is not a problem, but the METHOD in which it is implemented is a big problem and will actually make or break encryption.

   Now, how do we know whether or not the numbers are reliable insofar as cryptographics are concerned? First, is the geometry of the integer table isomorphic? If not, you are in trouble.

   This is because one cannot have an operator that displays the properties of a value that is compact and admits a Kahler metric...and therefore does not project a non singular algebraic variety.

Sort of works

[CharmQuark]

The fact that /. is criticizing this work is not hubris, but a realization that there is a difference between a cryptographic design and cryptographic implementation. Those how have read Applied Cryptography know that we have secure protocols. Those that have even peripherally tried to implement those protocols know that the devil is in the details.

The details are what stink about this plan. For instance, if we use publicly transmitted random numbers, which is about the only way we can make sure that we have random numbers, there must exist a secure and trusted machine. This in itself is far from a trivial proof.

Furthermore, the idea that these numbers cannot be stored is poppycock. At realistic transmission rates, we are only talking about a terabyte a week. This is not beyond the means of dedicated cracker, especially since that person is not limited to local and legal resources. The pratical transmission speed will increase, but the cost of storage will also decrease.

The situation is worse. Alice must send Bob a message detailing when the sequence will start. This message is subject to all the normal attacks. Also, we cannot even guarantee that Alice and Bob receive the random numbers at the exact same time. This implies we must have synch information in the random data flow, which implies segmentation of the random data flow.

Finally, the actual encrypted message cannot be received instantaneously. We must allow for time for encryption, transmission, dropped packet, storage, etc. This implies that, in contradiction to the basic premise, the random numbers must be stored on the computer in anticipation of the message!

Re:Infeasible?

[micromoog]

Ha! Very good point. If only I had mod points, and hadn't posted to this thread . . .

Then again, if I hadn't posted to this thread, your post wouldn't be there to moderate.

Re:provably unbreakable?

[Siqnal 11]

Mathematics is full of proofs of things being impossible.

No, mathematics is full of proofs that we don't know how to do things, not that they're impossible.

--

Re:provably unbreakable?

[Siqnal 11]

Your argument, like all the others in this thread, is based on the assumption that we know and understand mathematics as a whole, that we are 100% correct about every aspect we think we understand, and that we haven't missed anything.

I realize this might come as a shock to some people, but we're just scratching the surface.

I don't disagree that we can't find a a real number "x" such that x^2 If I'm wrong, then there is no reason to continue studying math...we already know everything there is to know on the subject.

--

Re:provably unbreakable?

[Siqnal 11]

No, all they've proven is that it can't be done within the bounds of current human knowledge.

--

oops.

[Siqnal 11]

...I don't disagree that we can't find a a real number "x" such that x^2.

But, just because we can't find that number doesn't mean it can't be found....

--

Re:provably unbreakable?

[Siqnal 11]

Right. You can't prove a negative assertion.

--

Re:who owns the stream?

[agentZ]

Exactly! What good is a cryptosystem that you can only make telephone calls with? That is, because this stream of random bits is too big to store, whomever you're talking to has to be listening to the stream EXACTLY when you're sending your message, otherwise it's "gone forever." So if we're not on the phone, this thing sounds pretty useless.

Unbreakable - you mean like the comb?

[tenzig_112]

The Enigma was unbreakable, too. And if you've ever spent time reading the output of one of those things and then considered the millions of possible configurations, you'd quickly understand why they felt that way.

One-time pad cyphering has been around for quite a while. In Simon Singh's The Code Book (I happen to have it here at work), he mentions the Russian fondness for it during the Cold War. We never broke the code itself since there is no pattern or repeatable method to discern.

But anyone can steal and secretly photocopy one of the pads and render the encryption useless. I remember breaking the hell out of that comb in grade school. How dare they tell me that thing was unbreakable.

Today: Eco-Terrorism Wuss Bags

Re:Unbreakable - you mean like the comb?

[flounder99]

The Enigma was NOT unbreakable it was just hyped to be unbreakable.

This system is mathematicly proven to be unbreakable. That means it can't be broken without the key. It does not mean that it is secure, it is only as secure as the keys. If someone has the cyphertext there is absolutely no way they can recover the plaintext. All currently used cryptosystems are breakable, just not feasably breakable. This system is honest to goodness unbreakable, but like I said if the keys are not secure unbreakablity is meaningless.

Need a company Mission Statement?
Visit http://www.giantflounderpenis.com/

Re:Seems a tad absolute

[am 2k]

And then the password gets stolen. This is just as secure as if the data itself got stolen.

I must be missing something

[Stupendous Guy]

Ok I get a one-time pad and all. But isn't it true that, while the assumption that computers cannot store all the random data, all they need to store is the segment of random data that was used to encrypt a given message? Clearly you cannot encrypt a message with an infinite key on PC. Why not just archive 1 year's worth of the pad, and then you can decrypt 1 year's worth of messages?

But it DOES rely on computer power ...

[mr.nicholas]

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.

Ummm... doesn't this statement rely on the computing power of the eavesdropper? If so, they his entire argument is invalid.

Re:Actually, this code is broken...

[kyz]

... in the logical sense. It doesn't quite know how to end itself. *grin*

Well, I can testify that it works for all values of msglen, where msglen >= 0... best to declare msglen as an unsigned int... see my other stuff for more loops than you can shake a stick at.

Re:Unbreakable cryptography

[kyz]

Although it is nice to be able to protect your information, the fact that the technology is effectively unbreakable could mean bad news for all of us. Police intelligence and so on rely on being able to get information. For example, when a pedophile gang was smashed recently, it was done because the police could get the information.

Nice troll. BTW: the recent police bust was because some of the paedophiles gave away their secret keys. They only gathered evidence they could decrypt with those compromised keys, everything else was still locked up tight. The actual encryption on their kiddie porn was never broken, but the security of it was.

Re:Unbreakable cryptography

[riedquat]

businesses can still communicate securely, but criminals will be stopped since the government has their information.

I agree with your motives but when the government or some other 'authority' attempts to put restrictions on everyone to stop criminals from operating - in this case, privacy on the net - it's nearly always the criminals who find a way around it while legitimate businesses and citizens have to put up with the restriction. I get the feeling of Big Brother reading my emails, while the terrorists get completely secure communication.

If you try to suppress this encryption system, you can bet criminals will discover it and start using it while the general public aren't aware it even exists - and before the police are aware as well, knowing the standard of police in my country. Surely it's better to give everyone the technology so the balance can't be tipped in crimnal's favour?

Unbreakable code?

[morie]

The chain is as strong as it's weakest link. As long as users leave passwords and other stuff lying around the office, the vulnerability of the encription is not code crunching, but simnple snooping around. I can send encrypted mail to a collegue, but everybody will be able to read it, because it is on her screen even when she's not in the room.

Re:Unbreakable code?

[ConsumedByTV]

Thats true.

It might help to not even bother talking to people that stupid. Also it might help to not send them anything you wouldnt want passed on.


Fight censors!

Re:Unbreakable code?

[Heidi Wall]

Yes, however encryption id irrelevant to that purpose. Encryption is used to transfer data between two points secure, or to store data for a period of time securely.

It is nobodies fault but the user's if s/he is dumb enough to leave useful unencrypted data lying about.

Encryption doesn't solve such difficulties. Education about common sense does.
--
Clarity does not require the absence of impurities,

Re:Unbreakable code?

[H3lm3t]

but everybody will be able to read it, because it is on her screen even when she's not in the room.

Just use the next available security hole in Outlook to set the screensaver activation time to five seconds?

only direct communication

[morie]

It seems this type of encryption can not be applied to e-mail, since the transmitter and the reciever have to store the random numbers at the same time.

Also, if you want to store a message on your computer, you'll have to either decript it or store the key with it, or it will stay encrypted forever and can not even be decrypted by you yourself.

So, either half of the claims made by Rabin seem false: someone (police, FBI) can either force you to decrypt things or you can not read it yourself anymore. same goes for deleted items: once you (properly delete something, nobody has access to it anymore. Problem is, neither have you. That's not new.

Actually, this code is broken...

[ericvids]

... in the logical sense. It doesn't quite know how to end itself. *grin*

(Of course you probably meant it for effect, but I can't really tell...)

Re:provably unbreakable?

[Kharny]

Since math only uses a part of reality, and math is based on assumptions, within math you can prove negatives and positive theoretics. However, this will not hold in a real life situation. Theory consists of an very small setting in which something holds true.

Re:Unbreakable cryptography

[ConsumedByTV]

Government escrow makes sense, they wouldnt abuse it either. I was thinking in addition to giving them all of my private keys, I could let them fuck my wife... That would really prevent terrorism.


Fight censors!

Re:Unbreakable cryptography

[ConsumedByTV]

Suggest something better?


Fight censors!

Re:provably unbreakable?

[ConsumedByTV]

Prove otherwise.

But thats true, you cant prove a negative, oh wait... You can... Sometimes...


Fight censors!

cryptography exporting rules

[kipple]

does anybody know if that kind of cryptography will be defined as 'non exportable', and kept within the us?

I wonder if the fact that the nsa haven't blocked these news may be a proof that they already know how to decipher it, by mthematical way (not yet discovered by the academic world) or not orthodox way (intercepting the plaintext before, and so on).

quotes from the article, questions

[kipple]

"The coding starts with a continuously generated string of random numbers, say from a satellite put up to broadcast them or from some other source."

now that may be a good idea, but who assures me that the satellite is broadcasting truly random numbers? that supposed satellite is the weakest link of the chain. what happens if somebody spoofs the satellite? will all computers be shipped with the fingerprint of the satellite communications on a non-writable memory?

"The sender of a message and its recipient agree to start plucking a sequence of numbers from that string. They may agree, for example, to send a message, encoded with any of today's publicly available encryption systems saying "start" and giving instructions on capturing certain of the random numbers. As they capture the numbers, the sender uses them to encode a message, and the recipient uses the numbers to decode it."

what if an eavesdropper intercepts that series of random numbers? he could decipher the message without anybody knowing it. how would the two parties agree on which series of numbers without the enemy knowing it?

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

yes, but couldn't the eavesdropper record the stream of numbers broadcasted 'til he got the 'stop' message from one of the two parties? with a good range of approximation (we're talking about No Such Agencies with large amount of computing power) they can even try a brute force deciphering of the message until they got the right sequence.

I don't know, I'm sceptic about this kind of solutions, expecially those publicized as via ordinary media and not via more competent channels.

however, the impossible-to-retrieve thing is interesting.

assuming a random number generator?

[Skiamorphic]

Isn't assuming the existence of a random number generator as extravagent as, say, assuming the existence of God? Observe some quantum event you say? Well how do you logically prove that the quantum theory is correct? How do you prove that the equipment observing the event is infallible? How do you prove (contra Hume) the validity of induction? How do you prove (contra Godel) the consistency of you own reasoning? How do you prove (contra Descartes) that the whole thing wasn't an illusion. Oh that's right, it was the putative existence of God that saved Descartes.

academic, theory, and engineering

[plcurechax]

Rabin is an academic, and has proposed a theory which is provable secure. It is not a engineered software system, but academic paper-stuff.

The system appears to have more to do with a key distribution method (protocol), rather than a new encryption algorithm, but this is based on the NY Times article not the rigous description, so I am not certain.

One of the classic weaknesses historical in systems has been how to securely distribute the keys to all parties who want to communicate securely. This system is intended to address that troublesome problem.

I hope this clarifies a few things for readers.

Re:Here is the full story

[hughk]

I don't like to do this without seeing the official writeup, but if I am doing a Vignere (or any other transformation) using a random keystream delivered over a sat. link, I would need to be sure that my numbers were good, i.e. continuous entropy checking. Even then, I don't know that they were good during transmission until too late.

Key subversion is the easiest attack in cryptography. Sat. signals are very easily swamped.

One time pad is secure

[thomash]

I dispute that the it's[One time pad] *provably* secure. If you you have a proof, or a reference please post.

You asked for it, you get it. First, I'll explain what a one time pad is:

Assume, that I (Alice) want to send Bob the bit string "1001010110101...1", with length of a few million bits. Because it is secret, I remember the secret bit string of the same length we prepared a year ago. It was "0001010100101...1".

I never told anybout about this secret string. No one knows it, except Bob and me. Now, I just send the XOR of both strings to it: 1000000010000...0. (I nicely ordered the strings and showed the relationship, but I could not post it because of a stupid ./ filter)

When I only use the secret key once, I can call this one time pad, and it is completely secure. All an adversary can find is the length of the message.

If you still want a prove (most people belive that it is unbreakable now), then you can show it using Entropy and Information: The Information you have about the message when you know the encrypted message is: I(m; e). It equals the information about the Message if you know only the Key I(m; k) and this is 0 because the two strings are completely unrelated.

Re:Seems a tad absolute

[Random Walk]

On the other hand, there is still a remote chance that it might not be impossible to prove that Bruce Schneier is not God herself.

Logic

[The Grip Reamer]

So, by your logic, we should forfeit that freedom now so we can preserve it?

-B...

Perhaps if...

[rcs2]

someone came in with a gun, I'd like to be able to decrypt it.

"If someone walks into my office with a court order or if they put a gun to my head they still could not read my conversations," Dr. Lipton said.

Practical Calculations

[huima]

I think it is safe to assume that to transfer a relatively short message, one doesn't want to sample the public random bit stream for more than a minute. If the amount of bits receivable in one minute must exceed practical storage capacity, it must probably exceed 2^64 b/min, i.e. 2^58 b/s. Big optical fibre bunches carry less than 2^48 b/s, so one should be connected to more than 1024 state-of-the-art backbones to get it working!

Now I don't know of the capacity of satellite-to-ground link, but satellites have problems with (1) clouds, (2) radio interference and in general it is difficult for me to believe that the air link capacity here would exceed that of optical fibres.

This is really not as stupid as everyone thinks

[Little_Gnoll]

Heh. Now I wish I had taken better notes in Rabin's class. When I saw his presentation of this it was less than totally clear. I do get the feeling that this is not a practical system, but some objections that keep floating around here can be answered effectively. One thing to understand is that the thrust of this algorithm is towards making messages secure from breaking some time after they are transmitted. This is where all the unprovably secure (RSA, etc.) systems fail.

First of all, as many have commented (but to no avail as we still keep hearing the same old objections) this is a provable system within certain bounds. Of course if your system is compromised then the adversary will be able to read your messages. Duh. He'll also be able to blackmail you with all the porn on your hard disk. And of course if the gov't uses only a pseudo-random stream then they will be able to read it, etc... None of these are showstoppers that Rabin would be interested in.

Secondly, the security of the start signal should be able to be assured through smart protocols. Assuming that neither computer at the end of the transmission is compromised, it is obvious that secure transmission of the start signal can be made simply by sending the next start signal on the tail of the last message (unbreakably encrypted). Basically bootstrapping it. Of course, if one of the computers is compromised, then you will have to re-start the communication somehow. If you want a totally secure way to restart, then you get on a plane and pass on the new start signal in person on a piece paper that will self-distruct in 5 seconds. You can argue about the probability of your computer being compromised, but Rabin is not at fault in assuming a secure way to transfer this information.

Better still, even if he compromises your machine at some time, the adversary (even if he was following your communication) will not later be able to decipher what was said. The random bits making up the pad will be gone, so he must follow along concurrently.

As for the storage requirements, this is certainly only a practical concern. Rabin has shown that the unbreakability of the encryption holds up even of the adversary has an arbitrary function for storing some of the random bits (unfortunately I must have fallen asleep when he started to prove it). So since the adversary has to store all the bits, it does not seem that difficult to come up with a method spitting out random numbers that would soon exhaust the memory capability of Earth.

So maybe you won't be seeing this in your cel phones anytime soon, but if you want to make a message that you know will never be dug up, it is comforting that using this method, in only a year, month, or minute your message will be, under any inspection at all, just so many random bits.

F

Here is the full story

[Anml4ixoye]

A computer science professor at Harvard says he has found a way to send coded messages that cannot be deciphered, even by an all-powerful adversary with unlimited computing power. And, he says, he can prove it.

If he is right, and he does have some supporters, his code may be the first that is both practical and provably secure. While there are commercially available coding systems that seem very hard to break, no one can prove that they cannot be cracked, mathematicians say.

In essence, the researcher, Dr. Michael Rabin and his Ph.D. student Yan Zong Bing, have discovered a way to make a code based on a key that vanishes even as it is used. While they are not the first to have thought of such an idea, Dr. Rabin says that never before has anyone been able to make it both workable and to prove mathematically that the code cannot be broken.

"This is the first provably unbreakable code that is really efficient," Dr. Rabin said. "We have proved that the adversary is helpless."

Dr. Richard Lipton, a computer science professor at Princeton, who is visiting this year at the Georgia Institute of Technology, said, "It's like in the old `Mission Impossible,' where the message blows up and disappears."

Someone who uses one of today's commercially available coding systems, Dr. Lipton explained, uses the same key -- mathematical formulas for encoding and decoding -- over and over.

Eventually, they may be forced, perhaps by a court order, to give up the key. Or the key may be stolen. But with Dr. Rabin's system, the message stays secret forever because the code uses a stream of random numbers that are plugged into the key for encoding and decoding. The numbers are never stored in a computer's memory, so they essentially vanish as the message is being encrypted and decrypted.

"If someone walks into my office with a court order or if they put a gun to my head they still could not read my conversations," Dr. Lipton said.

In a sense, say some mathematicians and computer scientists, Dr. Rabin may have solved the ultimate problem in cryptography, one that has driven research for centuries: finding a provably unbreakable code that is also practical. But, they say, the paradox is that the discovery has come at a time of vigorous debate over whether such a code will make much difference in keeping communications private.

Some say that a provably unbreakable code could have profound effects, keeping secret messages secret forever. But others say that codes today are already so good that there is little to be gained by making them provably, rather than just probably, unbreakable.

For now, Dr. Rabin's idea is simply a scheme backed up by a mathematical proof that he has been presenting to scientists at seminars. No company is lurking in the background to sell it, and Dr. Rabin says he has no commercial interests in it.

"I never commercialize anything," Dr. Rabin said. "I am not in that business." Instead, he said, he did the work because it was a challenge.

Dr. Rabin's idea is simplicity itself, at least in the world of encryption. Previous coding methods rely for their security on the limitations of computing power. They assume that if breaking a code requires enough calculations, even the best computers will not be able to do it.

But, Dr. Rabin said, there is no proof that such codes are secure. Their security hinges on the belief that no one will find a shortcut to doing the calculations. It is always possible that such a shortcut exists, waiting to be discovered by a clever mathematician.

Dr. Rabin relies instead on the limits of memory banks in computers. No matter how powerful a computer is, no computer can store an unlimited amount of data. And yet that is what is required for an eavesdropper to break his code.

The coding starts with a continuously generated string of random numbers, say from a satellite put up to broadcast them or from some other source. The numbers can be coming by at an enormous speed -- 10 million million per second, for example.

The sender of a message and its recipient agree to start plucking a sequence of numbers from that string. They may agree, for example, to send a message, encoded with any of today's publicly available encryption systems saying "start" and giving instructions on capturing certain of the random numbers. As they capture the numbers, the sender uses them to encode a message, and the recipient uses the numbers to decode it.

An eavesdropper can know the mathematical formula used to encode and decode, but without knowing the exact sequence of random numbers that were used in the formula to send a particular message, the eavesdropper cannot decode the message. And the only way to have that sequence is to just happen to be storing numbers from the unending stream at exactly the right moment.

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.

Often, Dr. Rabin said, eavesdroppers will capture and store encoded messages hoping to decode them at later, either when computers have improved -- making it easier to do the calculations to break a code -- or when the method for encoding and decoding is known, perhaps because it has been stolen. But, he said, messages encoded with his system can never be broken by these means because the random numbers used in encoding and decoding are used once and are never stored.

"That is why I call it `everlasting security,' " he said.

Dr. Richard DeMillo, chief technology officer at Hewlett-Packard, said that what interested him about the scheme was that it "reshuffles the policy deck."

"Normally," he explained, "agencies put the burden of wiretapping on the carrier." A telephone company, for example, would have to allow an agency like the Federal Bureau of Investigation to listen in on coded material. But with this system, the agency would still have the burden of trying to capture the appropriate stream of random numbers, a task that would be technologically infeasible.

Dr. Lipton also said the scheme could thwart law enforcement agencies.

"If I'm saying to you, `Buy 1,000 shares of I.B.M., I'm sure it's going to go up,' " he said, "and if that was an insider trading situation, five years from now the F.B.I. could go after you."

If the agency had the encrypted message in hand, it could demand the key to read it, he said. But, Dr. Lipton said, if the random numbers used to encode were used once and never stored, the agency would be hamstrung. "It changes the ground rules," he said.

Dr. Lipton added that, as a computer scientist, he appreciated the proof that the code could not be broken. "Michael's big contribution has been the proof that the system actually works," he said. "It's one of those things that sounds obvious but the mathematics is quite hard."

Of course, what is good for those who want privacy may not be good for law enforcement. Even the cryptography systems sold today are a problem for the F.B.I. "Uncrackable encryption allows drug lords, terrorists and even violent gangs to communicate about their criminal intentions without fear of outside intrusion," the F.B.I. director, Louis J. Freeh, told the Senate in 1998, according to a transcript from the Federal Document Clearing House. "This type of encryption also allows these same people to maintain electronically stored evidence of their crimes beyond the reach of law enforcement."

Still, some computer experts said that while it might be interesting in theory to have a provably unbreakable code, the practical importance of Dr. Rabin's code may be minimal.

Some, like Dr. Dorothy Denning, a computer science professor at Georgetown, and Dr. Cipher Deavours, a professor of computer science and mathematics at Kean University in Union, N.J., said the code was simply impractical for large messages. The larger the message, the longer the string of random numbers needed to encode it, and the more difficult it would be to send.

"It's a cute idea, but it's simply unmanageable," Dr. Deavours said.

Others, like Dr. Lipton, disagreed. "I think it is quite practical," he said. And Dr. Rabin insisted that computers would have no problem with the encryption scheme, even with long messages that were sent among a large group of people.

Beyond the question of whether the system would work in practice, some question it because, they say, the role of cryptography in protecting privacy has been overblown.

"If you think cryptography is the answer to your problem, then you don't know what your problem is," said Dr. Peter G. Neumann, a computer scientist at SRI International in Menlo Park, Calif.

Dr. Neumann explained that there are always ways to get around cryptography barriers and that these methods have nothing to do with breaking codes.

"It's like the voting machines," he said. "You'd like to have some integrity in the electoral process and now folks are coming out of the woodwork saying, `We have this perfect algorithm for privacy and security.' "

But, he said, while the systems may use cryptography to make sure that when someone touches a screen to vote, that vote is transmitted with perfect security, who's to ensure the integrity of the person who programs the computer?

"There is no guarantee that your vote actually goes into the computer the way it looks on the touch screen," Dr. Neumann said. "What does it take to buy a computer programmer? A couple of years' salary and a house in the Cayman Islands?"

Bruce Schneier, who is founder and chief technical officer for Counterpane Internet Security in San Jose, said that, as a scientist, he liked the idea of a provably secure system. "Research like this should be encouraged," he said. "But research is different from engineering."

But in the real world, a burglar confronted by an impenetrable lock on the front door may well go round to the back and just smash a window. "I'm a cryptographer by trade," Mr. Schneier said. "And a provably secure cryptosystem doesn't do me any good. We're putting a stake in the ground and hoping the enemy runs into it and now we're arguing about whether it should be one mile tall or two miles tall. It doesn't matter. The enemy will walk around it," he added.

Dr. Robert Morris, a retired cryptographer who was chief scientist for the National Security Agency, the nation's code-making and code- breaking agency, also questioned the primacy of cryptography.

"As far as I can see, he seems to be correct -- it's a provably secure method," Dr. Morris said. "But does that mean no one can read it? Nah."

He explained: "You can still get the message, but maybe not by cryptanalysis. If you're in this business, you go after a reasonably cheap, reliable method. It may be one of the three B's: burglary, bribery or blackmail. Those are right up there along with cryptanalysis in their importance."

Dr. Rabin said that just because there are other weaknesses in communications systems, that did not mean that secure encryption was not important.

It is as though medical researchers started arguing that there is no need to find a cure for AIDS, Dr. Rabin said. After all, many more people die of heart disease, and if you cure people of AIDS, heart disease can still strike them.

"This is not a reason not to work on H.I.V.," Dr. Rabin said. "The problem of H.I.V. is still important."

Dr. Morris said that even though the actual breaking of codes might not be necessary to read encrypted messages, Dr. Rabin's method could have an effect. "In a sense, what it does is shift the emphasis from cryptanalysis to some other sort of attack," he said.

Here, cracked it already!

[captain_paranoia]

PROBLEM:

The article asks us to suppose that it takes one minute to decode the 'START' message, and that the amount of data which is streamed during that minute is too great to store in memory or on disk. But, an attacker still wants to be able to decrypt the encrypted message using the streamed OTP.

SOLUTION:

The attacker places a satellite in HEO about 5,000,000 miles from Earth (for sake of argument), and beams the OTP transmission to this satellite upon receipt. The satellite then beams the signal back, so the attacker can access the OTP signal with a one-minute delay. Or, the attacker can place 5 satellites in HEO about 1,000,000 miles from Earth, and zig-zag the signal among them. Or, the one satellite could multiplex! Alternatively, the attacker can run the signal through 10,000,000 miles of fiber-optic cable. Of course, this is all assuming that no analog or digital delay could be made to handle the extremely dense signal with fidelity...

MORAL:

Although implementing any one of these ideas would be expensive, it would be worth it to the attacker, because he could then decrypt any message from anyone who had been gulled into thinking that this scheme was foolproof.

Re:provably unbreakable?

[df1m]

Well, there is definitely no proof that you can't trisect an angle. At Carnegie Mellon the math studies professors used to give the freshmen the problem as a homework assignment. They stopped giving it as one when some guy outside of CMU figured it out and got published.

Re:Seems a tad absolute

[Bobo the Space Chimp]

To all doubters, it's very simple.

Remember those good old cryptograms in crossword puzzle magazines, where you mix up each letter of the alphabet, then substitute each letter in the message for it's corresponding letter in the table?

Well, you do that, but use a different random table of letters for every single letter in your message. Since each letter has its own mixed up derivation, you have a provably secure system. The cyphered text is absolutely indistinguishable from a random series of letters -- two letters next to each other (or any two letters in the encrypted message, for that matter) have no relationship whatsoever. The only crack might be if you didn't use a truly random method of mixing up letters.

Re:provably unbreakable?

[Bobo the Space Chimp]

A sin function is very well defined for, for example, 2-d angles. It makes no difference if you sit in a 2-d universe, a 3-d one, or a 6-d one, or a no-d one of a singularity.

That was one of the brilliant realizations thousands of years ago. Mathematics lives in its own pure world. It is up to humans to attempt to build abstract models of the real world using mathematics.

Re:provably unbreakable?

[Bobo the Space Chimp]

No, the mathematics would still hold true.

It's the physics that might not.

Re:provably unbreakable?

[Bobo the Space Chimp]

Besides, "you can't prove a negative" is usually in the context of proving that God or unicorns do not exist.

This is technically wrong, too. Proving that those things do not exist involves exhaustively and instantaneously searching all of reality. That's merely a practical problem, not a theoretical one. (Although God, if it existed, might be able to still hide from us, thus making it theoretically impossible, if it were of such a mind to hide from us. Still, that is, ironically, also just a practical problem.)

Re:sync the random stream

[vidarh]

The whole point of the algorithm is that the random data stream must be so huge that it is cost prohibitive, or "impossible", to store a large enough window of it that you can break encryption of the sync message fast enough.

The problem with this is that you can attack it in many ways: If you're after a specific message, you know that you can discard all parts of the stream that was sent before the sync message was received by the receiving party (since otherwise, the receiving party would also be unable to decrypt, and conceivably the message will be retransmitted). You can also attempt to feed the relevant parties with "forged" data streams, to make sure you have the datastream used as a pad.

However, both of those assume that the snooping party knows what the data stream being used as input is.

What if the sync message contains the frequency of a more or less randomly chosen radio band, or whatever other source that it would be hard, or impossible to obtain a copy of after the fact? In that case it would work (again provided that the sync message is sent in a way that ensures it is not compromised until after it's to late to get hold of the data). Of course, you'd have problems to overcome related to getting the correct stream of bits from the same radio band in two different locations (due to noise, broadcast range of the radio stations etc.), but the main point is:

There's nothing that limits this system to one transmitter, and nothing that limits this system to an intentional transmission of random bits, and nothing that limits it to a source of bits that the adversary knows about or have access to.

You could use anything which both parties can sample at the same time and get the same results for.

The whole point is to make the possible data set impossibly large and difficult to record long enough to break the sync message while you're still keeping the data set.

This isn't any more unbreakable than current algorithms. It just relies on scarcity of storage instead of scarcity of processing power. (that it isn't unbreakable doesn't mean that it couldn't possibly be a lot harder, however, if properly implemented)

Re:Infeasible?

[capologist]

Why is it infeasible to store the number stream along with timestamps, and when you decrypt the "start" message, just go back to the proper point in your stream? Even if you missed it by 10 or 1000 places, it's then just a matter of trying different keys until one makes sense.

Suppose the "start" message indicates the frequency on which the number stream is being broadcast. Then you can't record the number stream prior to decoding the start message, because you don't know what to record.

Re:Why unbreakable?

[capologist]

"The greatest boon, however is that if the FED requires you to give up your private key (that initiates a communications channel), it doesn't do them any good." We already have that, assuming PKE isn't practically broken any time soon. All you need to do is periodically generate a new public/private key pair, and discard the old private key when the other party begins using the new public key.

Re:What frequiency will these numbers be transmitt

[capologist]

Probably not just a single frequency. In principle, I suppose you could have 100,000 transmitters each transmitting 100 million bits per second on a unique frequency. The original synchronization message would indicate not only the time at which to start using the random numbers, but also the "channel(s)" from which to get the numbers.

Just don't ask me where you're going to get that kind of bandwidth. Perhaps there is already a natural source of such a collection of signals.

criminals don't follow the laws

[capoccia]

how is regulation going to keep criminals from using strong encryption on their data. if they're computer savvy enough to encrypt their stuff, they're also capable of getting it from an overseas site. the only people who will be kept from using strong cryptography will be the law-abiding citizens and the criminals who are to stupid to know about cryptography.

this argument is very similar to the arguments that led to the creation of gun laws like the brady bill here in the us.

Re:Does this work?

[whanau]

Yeah I can think of no better way to distribute an OTP than by broadcasting it to anyone with a sat reciever a telescope and a good physics book. Give me a break.

Re:provably unbreakable?

[whanau]

No, the mathematics would still hold true. It's the physics that might not.
What do you base this assumption on? Mathematics is not absolute, rather it applies in our own situation. It is quite possible that current mathmatics would not be useful at a singularity. eg how would sin function in 6 dimensions?

Does this work?

[whanau]

If the pad is generated on the fly, it must use computer entropy, which is not truely random. Use a bad source and it is breakable, though not in a timeframe that matters

Re:Does this work?

[peccary]

If the pad is generated on the fly, it must use computer entropy, which is not truely random. Use a bad source and it is breakable, though not in a timeframe that matters

That's not what Rabin proposes. He proposes (assumes) a good OTP generated, perhaps, by observing quantum irregularity, and then broadcasting that OTP. For instance, this might be a satellite in space observing cosmic rays.

Re:provably unbreakable?

[whanau]

Siqall is right. Current mathmatics may not hold true when the demensions wrapped around each other at a singularity.

Putting the Kabosh on Rabin's "Unbreakable" Crypt

[Si_Druid]

There are several assumptions in what I garner from Rabin's press release(s). And, as we all know, it is often the assumptions that are the holes in any plan. I'm not going to target the "secret forever" problem - i.e. a message is discovered in a house and it's encrypted with Rabin's code, but rather the real-time problem: The encrypted message is being intercepted via a man-in-the-middle attack. I target this because the only real use of this cryptographic scheme is real-time traffic; otherwise no one can ever translate the message (might as well just write over your message with the random stream) because they won't have access to a random stream from some time past. And if they DID, well, that would mean someone is storing the stream - expressly against the design of the algorithm and destroying it's one strength.

As a few others have pointed out (adamwood, KFury, etc), the start code is probably the weakest link...
Rabin Assumption 1: The start code cannot be cracked fast enough to locate the start of the random sequence.
Refutation 1A: The start code will need to be trivial enough that unequal computers can decypher it and start on time, thus a computer several magnitudes larger than either of these machines can likely decypher the key in an equal amount of time.
Refutation 1B: The start code would need to identify an "up-and-coming" sequence in the random stream. Therefore, either the stream needs to be partitioned (so much for a random start point), the start needs to be a frequently repeating random point (the next "A" in the stream), or the algorithm must be willing to wait for a less frequent random set (the next "ZZZ" in the stream) which would open it up to the problem from 1A.

Rabin Assumption 2: The random stream exists only in a single, linear time.
Refutation 2: Sorry if that sounded a bit trekky, but what if I set up a "reasonably" large computer that echoed the random stream with a 5 minute delay? And what if you did the same, but echoed my stream with a 5 minute delay? We could even do instantaneous echoes and use the slowdown rate of the internet to act as the time delay. I doubt this could go on infinitely, but it is entirely plausible that the net could act as a half hour repeater for all available random streams. This again opens up the problem from 1A. Refutation 2-corollary: If the streams are being slowly repeated, once the start code is decrypted by the rogue computer, it could pick up an ongoing conversation at the current point, even if it can't translate all of the previous-content.

Rabin Assumption 3: The key disappears instantly.
Refutation 3: No key disappears instantly. If a calculation was run on the start code, then there is a chance to target the code and clue in to the start sequence. Is it possible either of the communication machines can instantaneously translate the stream? Either part of the stream must remain temporarily in memory while the complete key is being gathered or the machine must be decrypting piece-by-piece. In either case, it would be possible to read some of the middle of the random stream, determine where it came from (see refutation 2) and then a bit of brute forcing could determine the start and stop of that key. Finally, the random stream (and it's location) could be determined by monitoring the source of incoming packets to the communicating computers; activity fingerprints (how quick the machine handles other requests, etc) could determine when the processing started and thus where the start sequence may have been.

Rabin Assumption 4: There is order in chaos.
Refutation 4 (not-so-sound): The only order in the disordered, random stream is that it is consistently random. As a result, it may be very difficult to carry out the high levels of math that current algorithms use; thus the computations would need to be trivial. Since (as described in my intro) the purpose of this crypt is real-time messages, it is likely it would be used for a streaming communication. Thus, a brute force attack using small random elements against small pieces of the message, piped through the simple algorithm, may well be a plausible decryption technique.

debunk away...

Si Druid
response to: The Key Vanishes: Scientist [Michael Rabin] Outlines Unbreakable Code
http://www.nytimes.com/2001/02/20/science/20CODE.h tml

Re:provably unbreakable?

[volsung]

Um. I think you've been the victim of an urban mathematical legend.

Pierre Wantzel proved that you could not double the cube and trisect an angle with a straight-edge and compass in 1837. Go read section 8.4 in _Abstract Algebra_, by John B. Fraleigh.

Gibberish?

[Paul Crowley]

What you've written makes no sense to me at all, and I'm a professional cryptographer and so not entirely ignorant about maths and computational complexity theory. If it's meant to be quasi-scientific gibberish, you've gone for some nice choices of words.

If you have a proof that unbreakable encryption is impossible, please write it up and submit it to one of the crypto conferences, and you will instantly become a world-feted mathematician.
--

But I am

[Paul Crowley]

I know crypto though - see my Web pages. Explain it to me.
--

Understanding Rabin's Scheme

[Effugas]

Rabin's method is...interesting, in its usage of implicit state. But it's not perfect, and as I hope to show, there are semi-serious attacks against it.
To understand his method, one must follow its evolution from the baseline. The most obvious launching point is the PRNG XOR technique: Essentially, two hosts agree to seed a Pseudo Random Number Generator* with the same originating seed, then XOR** their data against that stream of entropy. The unique material that separates the sender and receiver from the rest of the world that is to be kept in the dark is not the psuedorandom stream of data but rather the key that both sides used to establish and synchronize their identical streams of pseudorandom data. If anyone else was to receive this seed, they too would be able to decrypt the XOR'ed ciphertext stream actually sent from the sender to the receiver.

From here we get his shared interaction with a (pseudo, but we'll ignore that)random stream of data.

One major problem, of course, is that there's absolutely no doubt of the *size* of the encrypted message being sent. XOR doesn't increase nor decrease the amount of bytes in the messages "ATTACK" or "SURRENDER", let alone hide whether a message is being sent or not. One thing we can do is have the sender continually broadcast the output of his PRNG whether or not its being XORed against anything, and send a "PRNG differential"(in other words, the exact opposite of whatever the PRNG counter reads) when a ciphertext segment is to begin. Of course, anyone who doesn't have the seed for the PRNG can't know such a trigger occurred, so (as should sound familiar) in order to offline-analyze the cipherstream, they have to analyze all the chaff that its hidden with. The sender and receiver have to be *exchanging* all that cruft though, but that's what they pay to avoid exposure to traffic analysis. The key to the transmission remains, however, the seed to the pseudorandom transmission.

From here we get his asymmetric capture/ignore differential between the eavesdropper and the receiver.

The problem is, in the real world, it's unrealistic for each theoretical communication channel to simultaneously occupy all bandwidth that they might eventually use--especially since the number of possible connections in a network scales exponentially for each additional member! As always in computer science, we need to find a way to convert a high order problem into a fixed expense, O(1).***

So Rabin's solution was to centralize the entropy source. But a central entropy source has to be used differently--the PRNG key can't be used as the message key, because the sender with the message is no longer the generator with the seed. Furthermore, if XOR is be used, entropy cannot be continually shared among all the active sessions, since repeatedly XORing the same entropy against different data compromises the security of the entire system. So what Rabin did was presume the two sides could exchange, not the seed to the PRNG, but a set of "counter times" at which to extract a subset of entropy from the communal pile. Every individual stream would probabilistically negotiate a unique and separate random stream of entropy culled from the global shared pool. This shared key would grant the sender and the receiver the ability to communicate with eachother, but could never independantly decrypt the datastream. Without the "private" reduction from the
"public" shared entropy source, the key would provide no assistance in decrypting the data--and since the data was essentially XOR'ed against a unique set of random data, the data would indeed be uncrackable, because the eavesdropper didn't copy all the necessary pieces.

What's to prevent this copying? "The data stream for the shared entropy is too large."

This is apparently empirically untrue. Solar entropy was brought up as a possible source of shared entropy, with the immediate rejoinder that NASA et al. have no problem storing *vast* amounts of data from the Sun. I heard numbers as large as an exabyte a day of data storage, though I'm sure (I Hope!) that's a gross exaggeration. 24TB a day is easily within reason, however, and 24TB / 24 hours / 60 minutes / 60 seconds leads to a stream of data that reaches 266MB/s.

Standard hardware isn't exactly built to parse data quite that fast, even though that's well within the boundries of full-time recording capacity. But there's no actual need to continually record, since as long as an eavesdropper is looking for interesting things to pull off the wire, they can immediately begin recording from the global datastream whenever they see something being XORed through it.

Essentially, everyone's sharing the same chaff pool, which is moderately interesting.

What's most interesting is the fact that there's an asymmetric function buried in this, and that's Discrete Time. Standard analog time can be considered the "standard" clock; Discrete Time is the beat of the global entropy pool sending up a new value. If one knows the right data at the right time(which segments to use as XOR values), very little expense needs to be levied to discover the plaintext. If one eventually finds out the right data, but much later, a relatively extreme expense needs to be paid to determine the historical value of the cost.

A major possible attack, of course, is subversion of the central source of data. Implementations that use sequential chunks, instead of randomly plucked bits, would be pretty vulnerable to a central source that *looked* random but actually provided significant information to the end listener.

On the flip side, there's a very good question on what a pseudorandomly selected subset of a truly random bitstream qualifies as. Pseudorandom? No--there's no seed that will reveal those bits; one tenth of thermal noise is still thermal noise. Random? Well, they were selected by a predictable function from a non-secret source. Perhaps they're pseudo-pseudo-random?

Hope this analysis helped some of you understand.

Yours Truly,

Dan Kaminsky
DoxPara Research
http://www.doxpara.com

* Pseudo Random Number Generator: a function that converts a fixed set of bits into an infinitely large set of predetermined but statistically random numbers)

** XOR: Exclusive OR; a trivial and reversable operation that scrambles data on a bit by bit basis. XORing something with random data once results in random data; XORing it again with the same random data results in the original content.

*** O(1): Order 1 -- No matter how many items in set N, the task will only be done once.

Re:Only secure when YOU generate the key/randomstr

[aheitner]

This is the meat of the matter. Dead on, you saved me an identical post :).

This is the impracticability that Bruce Schneier is talking about: if factoring is secure enough that it would take Eve a year (or 1000 years) to break an RSA-encoded message --- if you need to go from public-key to extremely strong stream/block cypher, you can use RSA to exchange a secret, then use Blum-Goldwasser squaring, which is as strong as factoring (if computationally expensive) --- then the assaulter is going to look for another weak link. For 99.99% of all crypto applications (and maybe it really is 100%), being secret for a good period of time (which you can adjust with key length) is as good as perfectly secret, forever.

OTP is certainly not new. And in fact it's only ever been governments who have the resources to put it into practice. Generating random numbers even at just enough rate to cover all your text is not cheap. No you can't use a cryptorandom number generator. Think about it, if it was an algorithmic generator, you could just give both parties copies of your unbreakable but deterministic generator -- they'd exchange the secret start value by RSA, or when Alice and Bob meet in a dark alley -- and you wouldn't need any satellites, or to generate pad at 10^6^6 numbers a second. I guess to generate pad that quickly, you'd need to do some quantum observation with a 50/50 split or something -- you certainly can't have monkeys up on your satellite rolling dice that quick (believe it or not, during WWII, RAND Corp. used to produce the OTP sheets, generated by people rolling dice).

So yeah. I'm not impressed with this guy.

Oops, I think I broke it

[K-Man]

The method relies on the random number stream not being bufferable for the time it takes to crack the start-time message.

However the speed of light makes it easy to delay the RNG signal by reflecting it off of a suitably distant relay station a few light-minutes or hours away, say near Mars. By the time the signal makes it back, the start time can be cracked and ready for decryption.

Mod this up

[K-Man]

(because I just posted the same idea).

But you beat me by 22 minutes.

Also, you could pass the signal through one of those light-speed-reduced materials that people keep coming up with. I'm not sure what it would do to the signal quality, but you could get a heck of a lot of data into a pipe where light goes 42 mph.

Re:The Fatal Assumptions

[Chris Burke]

> He hasn't solved the key distribution problem.

True, but he doesn't claim to do so. He assumes that a reasonable distribution method exists that can resist attack for some relatively short period of time. I agree with you that he relies on assumptions, and this is one of them. However, I also think that this is a relatively safe assumption, and to say that his scheme falls apart because of this assumption is too strong a statement.

Well, the thing is that it isn't a short period of time. Presumably your public key doesn't change that often, so if someone can crack that key, then they can listen in on the start of your conversation, whenever that occurs Also, they can perform a man-in-the-middle attack at any time, and any transaction you make is then compromised.

Unfortunately there is no good solution to this problem, and therefore his assumption is false. So maybe I'm being harsh with his idea because it doesn't address what I see as the more essential problem. Sure, huge compute farms at the NSA and quantum computers scare me a little, but right now the system is vulnerable, and this isn't a solution to that vulnerability.

I really should have made the subject "The Fatal Assumption", because my other points were mostly just speculation about the algorithm itself.

If someone finds a fast factoring algorithm, then he could go back and easily decode lots of transactions whose 128 bit secret keys were transmitted using RSA for protection.

I thought factoring was NP-complete, in which case all (all, he says ^_^) you should need to do is make the keyspace large enough such that it would take a hundred years to crack even if every elementary particle in the universe were used to crack it. But I'm quite possibly wrong (and we haven't gotten to NP-completeness in my algorithms class yet ^_^)

Still, it is a neat idea for providing that future security.

However, I do think that an argument by someone like Rabin deserves a little extra thought before a rebuttle is made.

Well, as I continue to fall back, I'll say that it does seem like a good idea, and hopefully peer review will bear that out. I just wish someone would solve the key distribution problem.

p.s. I apologize if my tone was beligerent before.

Well, I didn't think it was, so no harm done. Maybe you didn't like me attacking someone you respect, eh? Normal, I'd say. ^_^

Re:The Fatal Assumptions

[Chris Burke]

This is missing the point--the secret only has to be secure for a short amount of time. If the listener cannot crack your secret key immediately, he has no chance of ever intercepting the data.

He hasn't solved the key distribution problem. He assumes that a solution exists, and then uses it. There are two methods obvious to me in which the secret key can be compromised immediately:

1) no solution to key distribution. How do you prevent man-in-the-middle attacks? A simple two-step process, and the enemy can listen in on the conversation with ease.

2) the enemy can apply brute-force methods to cracking the private key, and can then decode the secret message as rapidly as the client. Now the scheme does depend on the computational power of your enemy, which the scheme was supposed to get away from.

Again, not true. Using your scheme, a cryptanalyst with plenty of time could decode your message at his leisure. Using Rabin's approach, an analysis after the fact is useless. You're missing the whole point of this scheme.

Alright, you got me there. If we take his other assumptions to be true, then it will work.

Now, not counting the ones I already listed, then I do have to at least be leary of the assumption that storage is a more finite resource than computing power. If the enemy has computers than can crack arbitrary-length-keyed traditional encryption in a reasonable amount of time, why can't they store the random numbers for some period of time sufficient to encompass the transmissions they are interested in?

Still, barring that, and the public key front-end's vulnerability, it would work.

I'd be a little more careful when trying to poke holes in the work of one of the gods of the field.

He's smart, so it must work? Yeah, right. That's what my incredibly useless group member in the VLSI course I took said about my ALU when I asked him why he didn't test it thoroughly.

The thing is, I'm not trying to poke (many) holes in his encryption method. I'm poking holes in the protocol, which is usually the weakest link (like in this case). His key generator and encryption scheme can be perfect but if the protocol is flawed, then it doesn't matter if he's using the RNG-satellite method or XOR.

BAH!

[PD]

All your crypto are belong to us!

simple, breakable key

[peter303]

In this case the key is the start time of the
"infinite" encoding key. The start time has to
be agreed and transmitted between parties.

:-( :-( :-( :-(

OTP keystream

[griffjon]

It occurs to me that this method of key distribution is ill-thought out. While it is true that capturing the entire stream is impracticle in terms of storage, it's also unnecessary.

*traffic analysis will quickly reveal times of day/night that your targets are exchanging messages

*Depending on the protocol, if both parties have to be communicating in realtime, it's trivially easy to watch the traffic and see the channel being set up and capture the correct OTP bitstream.

*target parties must still communicate when to start using the stream--the OTP crypto here is only as strong as this link, which could rely on repetition or an algorithm for time-to-start, other encryption (which changes 'unbreakable' to 'impractical-like-breaking-RSA'), and can be determined by power analysis (Alice always flips on her sat. dish at 9:05:43...)

*MitM -- how is the bitstream authorized? Who would notice if some TLA changed it from a highly-random algorith to a deduceable algorithm?

*EVEN IF none of these work, storage remains cheap. write the bitstream--or, chunks of 5 characters of the bitstream, wait 5, store 5 more, etc.--to a tape.

OTPs remain very difficult to use and use correctly. This is nice, but it's not going to magically solve our problems.

Re:Seems a tad absolute

[griffjon]

Um, no accounting for Blowfish (used in hushmail) or TwoFish (NIST finalist for the AES standard, beating out 12 other algorithms from luminaries such as RSA). Don't forget Solitaire, either.

Schneier knows crypto.

sender and receiver synchronization?

[cpeterso]

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

How are the sender and receiver supposed to synchronize if the satellite is sending 10 million random numbers per second? The sender must wait as the receiver needs time to receive the start message. The sender can't start its OTP if the receiver is not perfectly sync'd.

And what about satellite latency? The random number stream must use sequence numbers because I doubt the sender and receiver can syncrhonize their CPU clocks to run at exactly the same 10 million reads per second rate!

The cracker in the middle knows to start recording the satellite's number stream when he first sees the sender's start message. He knows to stop recording the number stream when the sender's a message FIN (or whatever).

Re:I have an unbreakable code:

[mindstrm]

It is unbreakable. Is he not describing a one-time pad?

If he is, you can't break it, period.

You could generate every possible key and run it against the ciphertext.. but this equates to , for a ciphertext of 8 characters, generating every possible compbination of 8 characters and deciding which is the 'real' message, just like an infinite number of monkeys...

It is true that a one-time pad is not breakable.

Practicalities

[Kaa]

Theoretically the system is just a huge continuously generated one-time pad, so it probably is mathematically-proven-to-be-unbreakable. However most of its claims rest on the assumption that nobody would be capable of storing that OTP. In practice that is not necessarily true.

Consider traffic analysis. Mallory watches Bob and Alice exchange coded messages. Let's say Alice sends a message to Bob and Bob replies in five minutes. All Mallory needs to do is to store five minutes worth of the OTP stream and then he can spend as much time as he wants working on cracking the message.

Attempts to deal with this problem by increasing the rate of OTP generation (the NYT article mentioned millions of digits per second) will run into practical difficulties again, as Bob and Alice have to synchronize their reading of the OTP stream and the faster it goes, the harder it is to do.

So, yeah, OTPs are nice but the TLAgencies need not to lose (any more) sleep just yet.

Kaa

Re:This will lead to a loss of freedom

[Kaa]

Does anyone here really think that the FBI will let you have unbreakable encryption?

FBI may not have a choice. Besides, one-time pads are provably unbreakable, have been around for ages and are not illegal.

Simply put, if everyone is using unbreakable encryption, then Government agencies will be forced to use other methods to get the information that they want

So? This is a well-known problem, the so-called "rubberhose" method of decryption. Do you want to say that we should just roll over and die?

expect the FBI and the NSA to seek Government legislation allowing them to install "security features" in every computing device

They would want this anyway, encryption or not. However I see major problems with this idea, both technologically and politically.
Kaa

Re:Why unbreakable?

[karot]

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

More specifically, this is assuming that the eavesdropper is at a disadvantage. You cannot assume that an eavesdropper will take 1 minute to decode a start message if the real recipient is not doing to take a minute themselves. In fact, man-in-the middle attacks could a) catch the start message, and therefore decode the stream, and b) send his own start message etc etc... There is nothing in the article describing how this system will be implemented in any useful way.

...and on a general note, if my understanding of the technique described is correct, then the method will allow only realtime encoded transmission, not encryption, storage, and later decryption. While this is all very nice, it leaves you in a position that both the source and destination must store the message in cleartext, or in a "traditionally" encrypted form. So we have 2 ways to break the "unbreakable" system already :-)
--

To me it sounds like stream cyphers,

[Basje]

as decribed in applied cryptography (from snyder or something, if my memory serves me correctly). The problem of those is synchronizing them, as is it here. The only thing new to me here is making the stream publicly available.

----------------------------------------------

sync the random stream

[FonkiE]

the problem lies within syncing the stream. if two people can do that somehow through the net, a third one (= intruder) can do that too, because this communication uses conventional ("breakable" :-) algorithms.

also i can't follow the argument, that todays cryptosystems use large numbers to defend themselves, and this one does not. this is certainly true, BUT to sync the stream you depend on large numbers and the problem gehts just shifted to large memory needs.

i even wonder if its possible to generate near perfect random numbers that fast ... (fast enough to be not "storeable")

what will slow computers do anyway (like palmtops, etc.)

sounds like a revival of old tech, but i don't think its possible to use a one-time pad or in
this case a "none-time-pad" securely.

and even if all that is perfectly secure, who is transmitting the signal? the government?

sure :-)

Re:Slashdot hubris

[FonkiE]

You are right. Rabin is a great matematician.

BUT: most of the issues of the discussion are about the PRACTIAL outcome.

He may consider the whole matematics about that, but not if its practical to do that.

Don't be a jackass.

[TheDullBlade]

What you're saying is equivalent to saying that just because we can prove that 1+1=2 doesn't mean that taking 1 penny and taking 1 other penny means that we have taken 2 pennies. After all, someone might screw up the process, and not correctly take the pennies correctly, thus ending up with some other number of pennies.

It's just the old "Math only proves math" argument. You've been reading that jackass Ritter's page, haven't you? He's just cutting down methods that use math that he can't handle to promote his own (often patented) products with a blend of hand waving and cargo-cult nonsense.

What you're really doing is just screwing around with semantics to make other people's statements seem wrong. You merely betray your ignorance of how mathematics interacts with the real world, and how such interactions are discussed in common parlance.

Furthermore, a message isn't just "secure or insecure", it either leaks all bits, leaks some bits, or leaks no bits. There are special advantages to having a random key that grows with the message, such as security degrading gracefully: having one part of the message cracked does not mean that other parts are also cracked.
---

I'd wager the impracticality is axiomatic!

[TheDullBlade]

He's not going to prove that it's impractical to store all bits transmitted forever, he's going to assume it, just as the OTP security proof assumes a true random source and a perfectly secure early communication.

Anything like this always has some pretty sweeping assumptions.
---

Re:I have an unbreakable code:

[jbf]

He's not describing a one-time pad, since the "pad" is public. He's effectively describing a Rip van Winkle cipher, without the limitations of a Rip van Winkle cipher.

BTW Chinacat, I think you read the algorithm wrong. The unbreakable code is to zero the data. Depending on where the data's been stored before, it may be possible to break, but it's certainly not for lack of characters!

Re:Unbreakable cryptography

[MartinG]

Having government eskrow will not stop criminals at all. Criminals have an almost endless number of ways of communicating. If you introduce government or police snooping into a technology, the criminals will simply choose another method. They will see snooping as damage and route around it. All you will have achieved yet again is reducing the privacy of all the remaining law abiding citizens.

As for protecting children from paedophiles, all you do by decrypting their communication is scare them from that method of comminucation on to another. And even if you managed to snoop ALL their electronic communication what would that achieve? It's simple, they wouldn't communicate electronically, just how they used to before the internet.

Frankly, I am sick of hearing that its okay to invade our privacy for these sorts of reasons. It's not okay, it doesn't help in the long term.

Some people seem to have forgotten that peadophiles existed long before the nasty evil internet did. And the problem then was the same as the problem now. ie, there are some sick fucks in society. It's a social problem that desperately needs a solution. Please stop trying to solve it be technical means. It won't work.

Re:I have an unbreakable code:

[jovlinger]

Let me see if I have you right: the "difficulty" in this cipher is storing the right sequence of digits. As evesdroppers we either have to

1) break the symmetric cipher used to send the offset/length estimate of the pad to be used (est difficulty 128 bits)

2) or store all the random numbers from the time of reception + decoding (since no numbers before that time can be assumed to be in the possession of the recipient) until the message has been sent.

Now, the problem is that the bitrate of the broadcast OTP is limited by what can reliably be recieved -- say 100Mb/s -- and the sender and reciever want to send the message soonish. If I have a terabyte disk array, then I can store 80,000 seconds (~ 24 hrs) worth. That is only a keyspace of 40 bits.

The longer you delay sending the message, the better, but if the attacker can influence the situation by selectively disrupting the reception of the OTP, they can make it become abritrarily unreliable to send a message of either significant length or security. As soon as either sender or recipient is jammed during key recording, they have to start over.

Of course, Alice and Bob can start sending spurious (start/length,keyid) messages (and then select one of these keys at random) to make Eve's recording needs all the more difficult, but the fundamental problem is that Alice and Bob have to outwait my storage ability to be sure of message security. And then I can start storing snippets of the OPT randomly, so that I can probablistically try to decode partial messages.

Note that once I've managed to decode part of a message, I also have a plaintext/ciphertext pair to use to try to crack the symmetric encryption of the initial start message.

Re:factoring, NP-completeness, and RSA

[Spasemunki]

You definately have me on the first point. I wasn't aware that that had not been shown to be NP-hard. Thanks for the notice. However, even if it is only in NP, finding a solution for an NP complete problem would still provide a solution to factoring, even if finding a solution to factoring would not provide a solution to all other NP problems. On the second point, I agree, there may be other ways to break RSA. But finding an effecient algorithm for factoring would break RSA. My point was never that RSA was the same as factoring, but that it was "based on" factoring, in the sense that solving the factoring problem would defeat the encryption system. Even if there were a proof that factoring was the only way to beat RSA (which you claim, and I believe as well, that there is not), this would not prove RSA to be secure as long as it remained to prove that the factoring problem could not be solved. So I agree, you're correct in both cases. But I don't think that alters the main point of my argument. I will admit, however, to spreading misconception by having been a victim of it. Thanks!

"Sweet creeping zombie Jesus!"

some of the logistical problems include

[LinuxParanoid]

• random number stream must be so large and sent so fast that a third party must not have the resources to store it all
• yet both sender and recipient must have bandwidths large enough to read such a stream in realtime

This is not a technology for 56k modems or even current DSL bandwidths.

Perhaps a series of distributed random number generator servers around the net a la napster/gnutella could make this feasible, but even that seems a bit of a stretch.

--LP

Re:I have an unbreakable code:

[ZahrGnosis]

I don't even think this is one of his assumptions... you only need to store the stream during the time the transmission you want to decrypt is being sent. Even at 10 million million numbers per second, any conversation taking less than a few minutes results in a fairly reasonable amount of data to sift through. Especially if you can crack the first private message that describes how the sender/receiver decide what numbers to pull.

Even more than a few minutes is no problem, as you say, because storage is getting exponentially larger.

Re:Only secure when YOU generate the key/randomstr

[ZahrGnosis]

You hit on the other problem with this scenario, and that is that the encryption/decryption has to take place in real time. The joy of Public Key encryption (one of many) is that you can just create a message and send it for later decoding.

Not every computer that we want secure works in real time.

Re:Why unbreakable?

[maraist]

You cannot assume that an eavesdropper will take 1 minute to decode a start message if the real recipient is not doing to take a minute themselves.

I'm sure they are assuming some type of private keying communication to send the start sequence which designates a future exact time to start the decoding (considering network lag). Part of the proof probably involves the requirement of the secrecy of the private keys. If this is thwarted, then you might as well assume that your keyboard has key-strokes running. I don't believe it's possible for a middle man to fully hack into such a system (I'm not a cryptographer) without such a private key.

I also agree that this can only be used for communication channels, and not storage. Seemed obvious to me, actually. But I believe it's great strengths are in cell-phones, or encrypted versions of Messenger services. Two things that are regularly monitored (and some times stored for later encryption). I don't think this could work with traditional email for the reasons you've pointed out, so the practicality is obviously limited.

The greatest boon, however is that if the FED requires you to give up your private key (that initiates a communications channel), it doesn't do them any good. It only temporarily inconviniences you until you get a new one for future communications. This, I think is one of his main excitements.

-Michael

Re:Only secure when YOU generate the key/randomstr

[maraist]

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.

Sure there's a way you garuntee the right stream. The first part of the encrypted message is a simple validation check. If the recipient doesn't decode it properly, then they know something is wrong, and they can communicate this through un-secure channels (traditional public/private key). The worst that can happen is a denial of communication through either lack of a random-number feed, or by convoluting the feed at different locations.

I believe the suggested method is to have one or more satalite streams, intercepted either by the cell phones, or an IP source which rebroadcasts in multi-cast.

Both methods allow for disruptions in the random-number signal, but so long as the process allows for resyncing, then things are fine; in fact that helps make the channel even more encrypted (except that you could monitor for the breaks, which might possibly let you know which channel they're listening to, and possibly allow ease droppers to sync up as well).

-Michael

Re:The Fatal Assumptions

[RussRoss]

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

This is missing the point--the secret only has to be secure for a short amount of time. If the listener cannot crack your secret key immediately, he has no chance of ever intercepting the data.

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

Again, not true. Using your scheme, a cryptanalyst with plenty of time could decode your message at his leisure. Using Rabin's approach, an analysis after the fact is useless. You're missing the whole point of this scheme.

I should point out that Rabin has an excellent understanding of practical issues. RSA encryption would not be usable without his randomized primality testing algorithm (every RSA key generator relies on it) for which he won the Turing award in the 70's. I'd be a little more careful when trying to poke holes in the work of one of the gods of the field.

- Russ

Re:provably unbreakable?

[MobyDisk]

Ack! Stop moderating these posts up! That's not true! Go take discrete math!

The equation you listed there happens to be "Fermat's last theorum" which has been proven to have no solution. The proof was discovered in 1995 using the method of proof by contradiction, which is a common method for showing that an equation has no solution. You can get about his proof details here:

http://forum.swarthmore.edu/dr.math/problems/saleh 12.10.96.html

Some other famous ones in computer science are proofs that infinite compression is impossible, or Alan Turings famous disproof of "The Halting Problem" that is a basis for computer programming.

Re:Only secure when YOU generate the key/randomstr

[mOdQuArK!]

The first part of the encrypted message is a simple validation check.

The problem with this, is that the moment you put in a validation check, you violate the whole reason that a OTP is provably secure: that an eavesdropper can't tell whether they decrypted your message, or just happened to stumble across a key which generated some other kind of message.

For a true OTP system, there shouldn't be any kind of formal, automatible validation check.

Re:Seems a tad absolute

[Fnkmaster]

Uhh... This is not an unbreakable symmetric or assymmetric cipher. This is an unbreakable _cryptosystem_.

One Time Pad (OTP) is provably unbreakable. The weak links in an implementation may not be provably unbreakable, but an algorithm or a process most certainly _can_ be provably unbreakable, if that algorithm is reducible to an OTP encryption. Which is exactly what this is. I have no idea what Rabin's supposed "proof" contains in it, other than "proving" that distributing massive volumes of information makes storage over time unfeasible and therefore it is only probabilistically compromisable with vanishingly small probability (luck). If you can prove that your protocol reveals 0 bits of information about the message M and 0 bits of information about your One Time Pad, then you have just proved that you have an unbreakable _cryptosystem_, i.e. a protocol combined with an OTP system.

Re:Clue: Cipher != Code

[Tom7]

"There is also no such thing as a provable secure Cipher."

Why? Can you give me a proof? Under some (reasonable, I argue) assumptions, you can certainly prove that a cryptosystem or protocol meets certain properties that you deem (reasonably, I argue) sufficient for security.

Rabin is not just some crazy guy popping out of the woodwork. You probably use his algorithms if you use PGP or GPG or anything else which needs to generate large primes...

Re:Slashdot hubris

[Tom7]

I am not referring to skepticism, nor am I discouraging people to find his paper and really give it the go-over it deserves. That's how all of the other cryptosystems you point out were broken.

What I am complaining about is all the posts which say, "I read in a book that you can't prove a cryptosystem secure!" or "It's the same as a one-time pad!" or "His key assumption is wrong!" or whatever else. My point is that while his proof may have an error, or there may be subtle issues about him proving the wrong thing, the NYT article does NOT give anyone here enough information to start tearing his work apart. Cast doubt? Perhaps. But an outright claim that he is wrong, or that he is repeating work that's already done (based on the superficial Science Page treatment in the article)... ridiculous. Offensive, even.

How do you know?

[Tom7]

Rabin's claim is not unsupported, as far as we know. He says he has a proof, and others seem to agree...

As I understand it, the way you agree on where to start sampling can be much more complicated than you seem to imply. I can ask to start at a particular time, or as soon as a particular sequence of numbers show up, and then I can skip numbers based on any sort of algorithm I choose.

As for doing trial decryptions: This is a totally bogus argument. If the key stream is really random, then all possible decryptions are equally likely (assuming a typical XOR-like encryption). How will you know if you've got the right message?

Maybe we should wait to see a real, technical discussion of this before we discard it? Rabin is a pretty big name in cryptography.

Weakness: Statistics of the Random Generator.

[(void*)]

This does not impress me. Isn't this just a proof that the one-time pad is secure? Hasn't that be demostrated?

Suppose you can't store the stream of bits. No big deal. We'll just take large enough fragments of it, and find some way to statistically describe those fragments. If the source of the fragments is not provably random, then this gives us a way to restrict the space of keys to brute force.

So - am I wrong?

Surely this is flawed if you are being watched.

[garethwi]

Surely the key can be intercepted. If you are under constant surveillance, then can't your watcher act upon the start signal at the same time as the receiver (thus being in effect a second receiver). Then, acting in precisely the same way as the receiver, the watcher would be able to read the encrypted messages at the same speed as the receiver does.

Surely I have missed something here, because a child would have been able to spot this.

NYT link needed

[Animats]

Where's the usual "New York Times No Registration Required" link?

flawed

[peccary]

This scheme is provably unbreakable IFF: nobody stores the part of the OTP which is used to encipher your plaintext.

Rabin claims that it is "impractical to record the entire stream of endless bits", but anytime someone makes an unsupported claim of impracticality, consider that to be handwaving.

In fact, all I need to store is a subset of the entire stream: a buffer of sorts. I don't have to record a long enough subset that I have time to break the initial position negotiation, because I know two important details:
1. by the time you cease transmitting your message, you have stopped recording bits from the OTP.
2. you don't have an endless memory for past bits, so the start position can't be very old.

There's one more detail. Since I have access to the keystream and the ciphertext, all I have to do is a whole lot of trial decryptions until I find the plaintext. I don't even have to break the initial negotiation.

I disagree that this is no stronger than GPG, in fact, I think it's quite a bit weaker.

Re:Pad must LOOK random, not BE random.

[peccary]

Random numbers are not good enough if your need 100% all-the-time security. It's theoretically possible for a truly random number generator to spit out 10000 zeros in a row which could leave your message (or interesting parts of it) wide open.

False. Wrong. Incorrect. Pad must BE random to be provably unbreakable.

'Sides, it's equally likely that a true random sequence would contain precisely the bit sequence, which, when XOR'ed with your plaintext, yields the ciphertext "Th15 M322A63 C0n7A1N5 T0P-53CR3T N000Cl34R B0MB Pl4N5!!!"

Good God, the man's a communist!!!

[Dreyfus]

From the article:

Dr. Rabin says he has no commercial interests in it.

"I never commercialize anything," Dr. Rabin said. "I am not in that business."

Instead, he said, he did the work because it was a challenge.

The nerve of that man. He did it because it was a challenge?! My ancestors fought and died so we could have software patents in this country. Patents to provide us with the incentive to innovate. And he does this stuff for fun?

Because it was challenge?!!!

And he's just going to give this stuff away? Good God, the man's a communist. I'm writing my congressmen -- I want him deported immediately.

Re:Unbreakable cryptography

[gwjc]

Your last statement is the one that weak simple sheep like yourself always say: "...if you have nothing to hide..."
My mind boggles that some other moronic sheep stumbled across your brain fart and called it insightful.
Dictators and tyrants have used that line since the beginning..
Yes we need roadblocks so we can search you for weapons
(if you have nothing to hide...)
We need to be able to search your house at will
(if you have nothing to hide...)
We need to take your children to an inquisitor
(if you have nothing to hide...)
We need to give you a cavity search, bend over.
(if you have nothing to hide...)

People like you are the weak link who would freely surrender our long fought for liberties away because of your need to be a lamb...
BTW: One time pads are very very old and have always been considered the most secure crypto.. as long as the pad is long, random and not stolen.

who owns the stream?

[wren337]

Yes, OTP is provably secure. But in his example, who owns the "noise stream" you're encrypting against? How do you know THEY don't own it, and that THEY didn't use some repeatable formula for generating the noise stream, and that THEY can't recreate it? There is a huge trust issue with the stream generator.

Also, this is useless for stored messages. It enables secure stream communication, not the storage of secure data, and is therefore of limited practical use.

Re:Only secure when YOU generate the key/randomstr

[sulli]

The assumption is that at any given time the amount of data that would have to be stored is massively bigger than what can be stored.

Good point. But is this true even now? You need a computer to generate the keystream, right?

Re:Only secure when YOU generate the key/randomstr

[sulli]

The number of available random number streams and the combined bandwidth of these streams is high enough to ensure that no one can save these streams long enough to later select the right stream or combination of streams as the decryption pad.

That assumption seems very risky. As noted in other comments here, storage and memory keep getting cheaper. Wouldn't it be possible for an eavesdropper to get a massive number (beowulf cluster?!) of PCs with massive hard drives and just capture and store it all? Then the cryptanalyst, knowing approximately when the message is sent, would test the million (say) available, stored keystreams against the ciphertext using a similarly massive computing cluster. Moore's law hasn't failed us yet...

Think about what you're saying

[abe ferlman]

You are saying that criminals will communicate so we have to regulate communication.

What if we had the technology to perform surveillance on every conversation everyone had anywhere, ever? And to record them forever? The logic of your argument seems to indicate that this would be a good thing, lest we miss a pedophile or two. To prejudge the content of communications is to give up a lot of liberty for not very much security.

What if the governments are the only ones allowed to use cryptography? Do you really trust them that much?

Infeasible?

[micromoog]

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.

It sounded pretty cool, right up until the end of that paragraph. Why is it infeasible to store the number stream along with timestamps, and when you decrypt the "start" message, just go back to the proper point in your stream? Even if you missed it by 10 or 1000 places, it's then just a matter of trying different keys until one makes sense.

What frequiency will these numbers be transmitted?

[tonywestonuk]

He quotes 10 Million Million numbers per second.... Lets say these are just 1's and zeros, therefor - 10 Million Million (or 10^13) will need a frequency of 10 times that, or 100 Million, Million Herts - 100 Million Megahertz, or 100 Terahertz as a carrier..... 10^14 Herts lies in the visible spectrum!!! I suppose a satelight could beam 2 lasers both at the sender and receiver so that they could both read the random stream, but then any intruder wouldn't have access to the stream and therefor the communication will be secure by default!!

Proofs and such

[shakazulu]

OK, let's look at this carefully. What Rabin has demonstrated is something that is not quite obvious to the lay person. Namely, that if two individuals can have exclusive access to the same (non-reconstructable) random stream of data, then they can communicate securely. No biggie there.

How can both parties be sure they are looking at the same stream (i.e. are not being spoofed)? How can both parties be assured that no other party can reconstruct the stream (from stored results or because the stream is not that random)?

All we see here is a reduction of secure data exchange between two parties to secure access to data from a third party. If there is any novelty here it is the trade of LongTime for BigSpace (but its EXP(TIME) for P(SPACE)).

Harvard professors are such media pigs.

factoring, NP-completeness, and RSA

[David Jao]

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!

[cpeterso]

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! ;)

Perfect Forward Secrecy

[Jered]

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!

[JPS]

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

[Spasemunki]

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

[javatips]

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

[Fnkmaster]

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?

[gargle]

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

[Martin S.]

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

[Animats]

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?

[CarrotLord]

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:

[kyz]

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

[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