×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Professor Describes Unbreakable Cryptosystem?

michael posted more than 13 years ago | from the much-snake-oil,-few-insights dept.

Encryption 241

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.

cancel ×
This is a preview of your comment

No Comment Title Entered

Anonymous Coward 1 minute ago

No Comment Entered

241 comments

Question on PGP (1)

Anonymous Coward | more than 13 years ago | (#418258)

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.

This can not work in practice (1)

Anonymous Coward | more than 13 years ago | (#418260)

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)

I wonder what Waterhouse would think of it? (1)

Anonymous Coward | more than 13 years ago | (#418261)

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:provably unbreakable? (1)

Anonymous Coward | more than 13 years ago | (#418262)

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.

Re:provably unbreakable? (1)

Bazman (4849) | more than 13 years ago | (#418267)

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? (1)

adamwood (5089) | more than 13 years ago | (#418268)

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:Seems a tad absolute (bzzzt) (1)

Slugbait (17229) | more than 13 years ago | (#418271)

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

Yawn (1)

QuMa (19440) | more than 13 years ago | (#418274)

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:Unbreakable - you mean like the comb? (1)

AstroJetson (21336) | more than 13 years ago | (#418275)

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

Kaa (21510) | more than 13 years ago | (#418276)

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

Kaa (21510) | more than 13 years ago | (#418277)

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

Kaa

Re:Unbreakable ? Not possible. (1)

Kaa (21510) | more than 13 years ago | (#418278)

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:provably unbreakable? (1)

virve (63803) | more than 13 years ago | (#418284)

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

Here I am, (1)

Godfree^ (67637) | more than 13 years ago | (#418286)

right at the bottom of the article, with this [thisisnurgle.org.uk] 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:Seems a tad absolute (1)

MWright (88261) | more than 13 years ago | (#418293)

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.


-----

Re:Clue: Cipher != Code (1)

Martin S. (98249) | more than 13 years ago | (#418309)

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:provably unbreakable? (1)

MadX (99132) | more than 13 years ago | (#418311)

>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: (1)

drnomad (99183) | more than 13 years ago | (#418312)

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? (1)

drnomad (99183) | more than 13 years ago | (#418313)

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?

Re:Seems a tad absolute (1)

Tom7 (102298) | more than 13 years ago | (#418315)

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:Unbreakable cryptography (1)

belroth (103586) | more than 13 years ago | (#418317)

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:Unbreakable cryptography (1)

Hellburner (127182) | more than 13 years ago | (#418321)

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:I have an unbreakable code: (1)

chinacat (137275) | more than 13 years ago | (#418324)

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:Unbreakable cryptography (1)

boto (145530) | more than 13 years ago | (#418329)

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

grahamsz (150076) | more than 13 years ago | (#418330)

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

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

perikalessin (169157) | more than 13 years ago | (#418344)

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

swm (171547) | more than 13 years ago | (#418345)

(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? (1)

SnapShot (171582) | more than 13 years ago | (#418346)

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 )

Re:How do they agree the start time? (1)

fatphil (181876) | more than 13 years ago | (#418356)

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:Wrong (1)

fatphil (181876) | more than 13 years ago | (#418357)

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? (1)

fatphil (181876) | more than 13 years ago | (#418358)

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:Seems a tad absolute (1)

wren337 (182018) | more than 13 years ago | (#418360)

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.

Unexpected argument in favor of Open Source (1)

Ereth (194013) | more than 13 years ago | (#418364)

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?

Unbreakable ? Not possible. (1)

Cliffton Watermore (199498) | more than 13 years ago | (#418365)

  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.

Re:provably unbreakable? (1)

Siqnal 11 (210012) | more than 13 years ago | (#418368)

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? (1)

Siqnal 11 (210012) | more than 13 years ago | (#418370)

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? (1)

Siqnal 11 (210012) | more than 13 years ago | (#418371)

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

--

oops. (1)

Siqnal 11 (210012) | more than 13 years ago | (#418372)

...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:who owns the stream? (1)

agentZ (210674) | more than 13 years ago | (#418374)

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? (1)

tenzig_112 (213387) | more than 13 years ago | (#418375)

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 [comindex.php]

Re:Seems a tad absolute (1)

am 2k (217885) | more than 13 years ago | (#418376)

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

Re:Unbreakable cryptography (1)

riedquat (226343) | more than 13 years ago | (#418381)

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? (1)

morie (227571) | more than 13 years ago | (#418382)

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.

only direct communication (1)

morie (227571) | more than 13 years ago | (#418383)

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.

Re:This can not work in practice (1)

sctprog (240708) | more than 13 years ago | (#418386)

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.

Re:Unbreakable cryptography (1)

ConsumedByTV (243497) | more than 13 years ago | (#418387)

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:provably unbreakable? (1)

ConsumedByTV (243497) | more than 13 years ago | (#418389)

Prove otherwise.

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


Fight censors!

Re:Unbreakable code? (1)

ConsumedByTV (243497) | more than 13 years ago | (#418390)

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!

cryptography exporting rules (1)

kipple (244681) | more than 13 years ago | (#418391)

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

kipple (244681) | more than 13 years ago | (#418392)

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

Re:Here is the full story (1)

hughk (248126) | more than 13 years ago | (#418395)

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.

Re:Seems a tad absolute (1)

Random Walk (252043) | more than 13 years ago | (#418397)

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.

Here is the full story (1)

Anml4ixoye (264762) | more than 13 years ago | (#418402)

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.

Re:provably unbreakable? (1)

df1m (301007) | more than 13 years ago | (#418404)

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.

criminals don't follow the laws (1)

capoccia (312092) | more than 13 years ago | (#418413)

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? (1)

whanau (315267) | more than 13 years ago | (#418414)

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.

Does this work? (1)

whanau (315267) | more than 13 years ago | (#418416)

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:provably unbreakable? (1)

whanau (315267) | more than 13 years ago | (#418417)

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

Re:Unbreakable code? (1)

Heidi Wall (317302) | more than 13 years ago | (#418418)

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:provably unbreakable? (2)

volsung (378) | more than 13 years ago | (#418420)

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.

Re:Only secure when YOU generate the key/randomstr (2)

aheitner (3273) | more than 13 years ago | (#418425)

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.

Re:Yawn (2)

Tim C (15259) | more than 13 years ago | (#418434)

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

Practicalities (2)

Kaa (21510) | more than 13 years ago | (#418437)

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

Kaa (21510) | more than 13 years ago | (#418438)

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? (2)

karot (26201) | more than 13 years ago | (#418439)

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, (2)

Basje (26968) | more than 13 years ago | (#418440)

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

FonkiE (28352) | more than 13 years ago | (#418441)

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:Unbreakable cryptography (2)

MartinG (52587) | more than 13 years ago | (#418446)

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:Unbreakable - you mean like the comb? (2)

flounder99 (64090) | more than 13 years ago | (#418449)

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/ [giantflounderpenis.com]

some of the logistical problems include (2)

LinuxParanoid (64467) | more than 13 years ago | (#418450)

  • 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:provably unbreakable? (2)

MobyDisk (75490) | more than 13 years ago | (#418456)

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 [swarthmore.edu]

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.

Weakness: Statistics of the Random Generator. (2)

(void*) (113680) | more than 13 years ago | (#418462)

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

garethwi (118563) | more than 13 years ago | (#418463)

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.

flawed (2)

peccary (161168) | more than 13 years ago | (#418465)

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:Does this work? (2)

peccary (161168) | more than 13 years ago | (#418466)

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:Unbreakable cryptography (2)

gwjc (181552) | more than 13 years ago | (#418469)

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? (2)

wren337 (182018) | more than 13 years ago | (#418470)

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.

Think about what you're saying (2)

abe ferlman (205607) | more than 13 years ago | (#418473)

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? (2)

micromoog (206608) | more than 13 years ago | (#418474)

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.

Re:Unbreakable code? (2)

H3lm3t (209860) | more than 13 years ago | (#418475)

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?

What frequiency will these numbers be transmitted? (2)

tonywestonuk (261622) | more than 13 years ago | (#418476)

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

shakazulu (315787) | more than 13 years ago | (#418477)

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.

Re:Clue: Cipher != Code (3)

Spasemunki (63473) | more than 13 years ago | (#418482)

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

javatips (66293) | more than 13 years ago | (#418483)

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.

Why unbreakable? (3)

gargle (97883) | more than 13 years ago | (#418485)

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

Martin S. (98249) | more than 13 years ago | (#418486)

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.

Re:provably unbreakable? (3)

CarrotLord (161788) | more than 13 years ago | (#418488)

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: (3)

kyz (225372) | more than 13 years ago | (#418489)

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

LinuxParanoid (64467) | more than 13 years ago | (#418490)

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

Seems a tad absolute (4)

CaptainZapp (182233) | more than 13 years ago | (#418492)

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.

Only secure when YOU generate the key/randomstream (5)

tjansen (2845) | more than 13 years ago | (#418494)

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

Chris Burke (6130) | more than 13 years ago | (#418495)

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

KFury (19522) | more than 13 years ago | (#418496)

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

Martin S. (98249) | more than 13 years ago | (#418497)

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

Load More Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Sign up for Slashdot Newsletters
Create a Slashdot Account

Loading...