Kuro5hin.org: technology and culture, from the trenches
create account | help/FAQ | contact | links | search | IRC | site news
[ Everything | Diaries | Technology | Science | Culture | Politics | Media | News | Internet | Op-Ed | Fiction | Meta | MLP ]
We need your support: buy an ad | premium membership

[P]
"Unbreakable" encryption method developed by Harvard Professor

By Anonymous 242 in MLP
Tue Feb 20, 2001 at 12:47:03 PM EST
Tags: Technology (all tags)
Technology

Today's New York Times is carrying a fascinating article on a new encryption algorithm mathematically proven to be unbreakable. The article The Key Vanishes: Scientist Outlines Unbreakable Code outlines Dr. Michael Rabin's work in producing an encryption algorithm that uses a decaying key. His Ph.D. student Yan Zong Bing provided the mathematical proof that the code is unbreakable. Dr. Richard Lipton of Princeton, Dr. Richard DeMillo, chief technology officer at Hewlett-Packard, Dr. Dorothy Denningof Georgetown, Bruce Schneier, and Dr. Robert Morris (among others) give commentary on the new method.


Sponsors

Voxel dot net
o Managed Hosting
o VoxCAST Content Delivery
o Raw Infrastructure

Login

Poll
How often do you use encryption?
o hg897GGFIHEG*#%)))__ 8%
o 0000111011100011100001111 12%
o Mama bear is in the kitchen with the gray kettle 63%
o Never 15%

Votes: 57
Results | Other Polls

Related Links
o New York Times
o The Key Vanishes: Scientist Outlines Unbreakable Code
o Also by Anonymous 242


Display: Sort:
"Unbreakable" encryption method developed by Harvard Professor | 53 comments (36 topical, 17 editorial, 0 hidden)
Less practical use than public key cryptography (4.25 / 8) (#2)
by streetlawyer on Tue Feb 20, 2001 at 09:15:23 AM EST

So our esteemed professor has, in effect, managed to exchange the problem of securely exchanging one-time pads, for the problem of securely exchanging a synchronisation signal against what is effectively a publicly accessible one-time pad. I don't think that this is a breakthrough of any sort. If the two parties have a secure communication channel through which to exchange the synchronisation signal (the "now!"), then why don't they just use it for communication? If they hope to exchange this signal on public channels, there is no security.

And the professor doesn't appear to have thought (or to be charitable, hasn't explained properly to the journalist) about the practical issues of synchronisation between two parties between whom there is an interesting problem of secure communication. You certainly couldn't have "tens of millions" of bits of one-time pad being transmitted if you hoped to communicate over TCP/IP, and not over any other telecoms protocol of which I am aware either.

--
Just because things have been nonergodic so far, doesn't mean that they'll be nonergodic forever

Drives the science of filtering (3.50 / 2) (#6)
by slaytanic killer on Tue Feb 20, 2001 at 09:56:14 AM EST

This method of encryption is based on having so much data that the finite resources of the attacker are overloaded by nearly infinite ones.

Therefore attacking it becomes a problem of narrowing information. This method comes into its own when there are hundreds of thousands of users, each tapped into various random streams, sending out false "start" messages.

So you want to limit the amount of information you need to collect. You tag people whom your filters identify as potentially troublesome. You watch the side-effects of their communications, such as the impulses generated by keyboards or using trojans. Anything to intercept the non-encrypted message transfer, since it will likely be less resource-costly than anything else.

The main limited and valuable resource an attacker has remains human. This cryptography advance has only made that fact more evident. So the entire problem seems to be one of preemption; statistical, partly predictable, and resource-efficient actions. Britain and the US have the two strongest intelligence agencies, and so the world police will get stronger just because fingers have to be put into enough pies.

If this sounds terribly paranoid, it's not. I just find it interesting and probably important to understand.

[ Parent ]
I think.... (4.00 / 1) (#9)
by retinaburn on Tue Feb 20, 2001 at 10:05:26 AM EST

If the two parties have a secure communication channel through which to exchange the synchronisation signal (the "now!"), then why don't they just use it for communication?

A person of ill repute could store the communications and then brute force them at a later date. If only the synchronization signal is sent in this 'regular encryption' method then the only person that could [read: should ] be able to decode it quickly is the inteded party. Thus both intended parties began using the key from the source ( a satellite system is proposed by the gentleman ). A party of ill repute will be seeing scores of fake signals going back and forth, and will have to crack each one to determine which is the real one. This takes time. After the thirdy party has cracked the real start message they have already lost the beginning (if not the entire) key. To believe that the person would grab all the signals from the source from the first fake start message to the last fake start message and use them to try to crack each message is (believed) to be impossible. Thats where the infinite storage would be required.

I think that we are a young species that often fucks with things we don't know how to unfuck. -- Tycho


[ Parent ]
not convinced (4.00 / 1) (#15)
by streetlawyer on Tue Feb 20, 2001 at 10:29:16 AM EST

Since this is intrinsically a real-time communication channel, the attacker can just dedicate a channel to decrypting the entire traffic as it goes back and forth. I don't see how the demands on him are obviously greater than those on the intended recipient unless you start making unwarranted assumptions about relative processing power.

Furthermore, the synchronisation signals themselves have to be plaintext; you can't have a signal whose role is to begin the decrypting process which itself requires decryption. So, you decrypt every instance of traffic following a start signal, and all this solution really achieves is to attempt to drown the signal in noise. That's steganography, which is a known weak method of protection.

--
Just because things have been nonergodic so far, doesn't mean that they'll be nonergodic forever
[ Parent ]

Im convinced (4.00 / 1) (#41)
by retinaburn on Tue Feb 20, 2001 at 01:53:11 PM EST

I think the problem for the attacker lies in he cannot determine where the start of the key the intended recipients are using. Im sure that this issue was addressed but perhaps not discussed in the article (at least not the one I read). Also false data could be started at the beginning of the sequence (ie before the real start synchro signal is sent). The cracker would have to save the message as well as all the data from the key generator ([m/b]illion bits/sec ??) and try to match it up...this would be the size limitation as I understand it.

The synchro signal could be any sequence of letters defined by the intended parties encoded with some commerical (PGP ??) method. I'm not sure where I got the idea of multiple fake message...im not sure if the article described it. But the idea is even if there was only one start message encrypted by the time it is cracked (not decoded) the key sequence has long been started to be captured by the intendeds, thus it is lost. The cracker would have to have a large buffer to capture all the data.

Why can you not have a signal which needs to be decoded to start ?

I think that we are a young species that often fucks with things we don't know how to unfuck. -- Tycho


[ Parent ]
Key-Exchange. (5.00 / 1) (#38)
by Parity on Tue Feb 20, 2001 at 01:38:42 PM EST

You can securely exchange keys, I think, in a way that you cannot securely exchange messages, because of the shortness of keys. A one-time-use public key exchange should be unattackable because the message length of a key (say 32 or 64 bits of 'seconds since the epoch' to indicate when to start encoding from) will not provide enough data to definitively calculate the key.

Alternatively, if you don't like that, you can exchange a
small one time pad, and instead of using 1k of key to calculate a 1k message, you use a small handful of bits to decrypt the sync point. This enables someone to have, say, a floppy disk, or a single frame of microfilm, or whatever, and exchange thousands upon thousands of messages without being given new pads all the time.

Anyway, if we don't yet have a proveably secure key exchange (regardless of how impractical the calculations are for exchanging actual messaging data), that's something that should definitely be worked on.

As to why you send messages with a different algorithm than the key-exchange one, it's for the same reason we do it now; generating a new private/public key pair, on both ends, for every 64bits (or whatever tiny amount) of data is going to be impractically slow; for now, anyway.

Parity None


[ Parent ]
not a theoretical solution, but... (none / 0) (#47)
by Estanislao Martínez on Tue Feb 20, 2001 at 10:13:12 PM EST

You could use public-key cryptography to exchange the syncronisation signals just before the method proposed is used to encrypt the message. If you use freshly generated key pairs for each exchange, and you minimize the amount of time between the sync exchange and the start of the transmission, so that the time is too short for the sync exchange to be cracked, the communication is secure forever.

Sure, this is not theoretically unbreakable, but, it improves upon other methods in that it gives you a very small window of time in which you can crack the message. If only manage to crack the code for the key exchange *after* the transmission has started, you're too late.

--em
[ Parent ]

aaargh... (none / 0) (#52)
by Estanislao Martínez on Thu Feb 22, 2001 at 03:11:09 PM EST

attack: if the attacker knows the transmission will happen soon after the key exchange, he just saves what comes on the key channel between the moment of the key exchange and the end of transmission, and uses it after he's broken the sync exchange to decode the main message...

--em
[ Parent ]

Yeah (none / 0) (#49)
by kubalaa on Wed Feb 21, 2001 at 05:50:18 AM EST

This article reads like Onion satire to anybody who knows anything about cryptography: "University Professor Rediscovers One-time Pad, Declares Cryptography Solved!"

Aside from your observations, another thing I'm curious about is how he proposes to create a truly random bitstream at such a high rate. My understanding was that all "random" number generators are still periodic, just with a very long period.

[ Parent ]

Quote (2.66 / 3) (#7)
by Ludwig on Tue Feb 20, 2001 at 09:56:28 AM EST

"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.
Sounds like trouble for Dr. Lipton...

Typical Journalistic Foolishness (3.50 / 2) (#8)
by kipster on Tue Feb 20, 2001 at 09:58:09 AM EST

This is the typical thing you see from the New York Times. They go to Harvard or Princeton and fall in love with some professor's idea. Notice how every other person she quoted dismisses the notion? But she leads with the Princeton guy and keeps talking about Rabin may have created an unbreakable cipher. Yeah.

We had one-time pads before. It's been done.

Nothing is unbreakable (2.50 / 4) (#12)
by unstable on Tue Feb 20, 2001 at 10:24:41 AM EST

We just dont know a way to crack it ...yet

this is always happening.... some new crypto scheme come out..everyone oohh and aahh.. then some bright lad breaks it wide open.

Take what Bruce Schneier said during defcon about one crypto scheme developed for the AES (Advanced Encryption Standard) by the germans... they thought it was good.... they brought it out and and presented it at the NIST (national Institute of Standards and Technology) confrence... During the question and answer phase someone cracked it.

For more info on crypto check out these sites (please add sites if you think they are helpful... )





Reverend Unstable
all praise the almighty Bob
and be filled with slack

not really (2.66 / 3) (#18)
by dze27 on Tue Feb 20, 2001 at 10:39:16 AM EST

This guy thinks he's *proven* that his system is unbreakable. There certainly are unbreakable ciphers, like the one-time pad, which are *provably* unbreakable. This would be just another such method.

Other encryption methods like RSA admittedly depend on supposedly (but unprovably, so far) hard mathematical problems, but this one is a different kettle of fish (and by the sound of it there is still some debate).

"Luck is the residue of design" -- Branch Rickey


[ Parent ]
Did you read the entire article? (4.33 / 3) (#19)
by Anonymous 242 on Tue Feb 20, 2001 at 10:45:36 AM EST

First, one of the interesting attributes of this encryption method is that it is mathematically proven to be unbreakable. Assuming that the math behind the proof is correct, then this is indeed an uncrackable cipher.

Second, as Bruce Schneier pointed out in the article, an unbreakable method of encryption won't necessarily result in unpenetrable security.

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, formerly with the NSA and (IIRC, father of the author of the Morris internet worm) also had some pretty good points.
"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."
The NY Times certainly did their homework on this article. This was one of the reasons I submitted it as an article. They took a lot of time to present a wide variety of views on the new method. The list of crypto and security experts quoted in the story read's like a Who's Who of modern cryptanalysis.

[ Parent ]
Don't be too sure (2.00 / 2) (#22)
by slaytanic killer on Tue Feb 20, 2001 at 10:55:05 AM EST

To construct a mathematical proof without handwaving, you need a set of assumptions. So quite possibly this method is unbreakable only for certain kinds of unbreakability.

I personally don't think so; it's probably unbreakable in a strong sense. But it's always good to have the light of suspicion on these things, since people attacking your methods certainly will be seeing things that way.

[ Parent ]
I agree (3.50 / 2) (#24)
by Anonymous 242 on Tue Feb 20, 2001 at 11:07:10 AM EST

But it's always good to have the light of suspicion on these things, since people attacking your methods certainly will be seeing things that way.
Did you catch the quip from Dr. Peter G. Neuman of SRI International?
"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.
I about laughed out loud when I read that one. Given the scope of the method, I have every reason to believe that when they say proven to be uncrackable, they do mean such in a strong sense. It had me confused at first until they got to a brief discussion of the way the new method is supposed to work. And as pointed out in the article, just because it is unbreakable in the research phase does not mean that it will be unbreakable in its implementation. We've seen before how a good cipher can be wasted because of a poor implementation.

[ Parent ]
yes i did... (1.50 / 2) (#43)
by unstable on Tue Feb 20, 2001 at 03:34:03 PM EST

you said

First, one of the interesting attributes of this encryption method is that it is mathematically proven to be unbreakable. Assuming that the math behind the proof is correct, then this is indeed an uncrackable cipher.


you say yourself that we have to assume that the math is correct.... well.. is it? we cannot be sure.... as I read it there is only one source of proof that it is unbreakable. to prove this theory we need not to try and prove its unbreakability. but we have to disprove its breakability. something that as of yet is impossible

this method is the way that scientists prove their theories.. they do not prove them... but they prove that they cannot be disproved. (if that makes any sense).




Reverend Unstable
all praise the almighty Bob
and be filled with slack

[ Parent ]
mathematics and proof (4.00 / 1) (#44)
by Anonymous 242 on Tue Feb 20, 2001 at 04:00:16 PM EST

you say yourself that we have to assume that the math is correct.... well.. is it? we cannot be sure.... as I read it there is only one source of proof that it is unbreakable. to prove this theory we need not to try and prove its unbreakability. but we have to disprove its breakability. something that as of yet is impossible
Assuming that Dr. Rabin publishes this (a reasonable assumption and one that ought be quickly proved correct or incorrect) anyone that understands the math can do the work for him or her self. If the math is correct for the limited domain of the system, then yes it can be proved to be unbreakable. As I've gleaned from other comments, if this system reduces to a OTP, it is mathematically unbreakable.
this method is the way that scientists prove their theories.. they do not prove them... but they prove that they cannot be disproved. (if that makes any sense).
This makes perfect sense when one is dealing with empiracle sciences instead of math and logic. Mathematical formulas, however, can be proven. Mathematicians do not believe that 1 = 1 because they have tried to disprove it and have failed. Mathematicians believe that 1 = 1 because, given the axioms of number theory, 1 = 1 can be proven.

[ Parent ]
1=1 (5.00 / 1) (#48)
by plastik55 on Tue Feb 20, 2001 at 10:22:23 PM EST

Actually a = a is an axiom of number theory, if I remember my Godel, Escher, Bach correctly. Still, as you pointed out, statements of proof in mathematics are much stronger than inferences in the physical sciences. If it were possible to prove a thing in mathematics that was not actually true, then at least one of the axioms would necessarily have to be false.

So if the math behind the proof is consistent, but the code is not unbreakable (using the definition of "unbreakable" used in the proof,) then the axioms are wrong.

Deciding whether an axiom is true or false is another whole can of worms entirely--most would say that the statement makes no sense at all, and that you can only say whether given set of axioms is consistent or inconsistent with itself. Whether mathematical axioms actually mean anything in the real world is another issue. We know that the universe contains objects which seem to operate by mathematical laws--but if we ever find a counterexample, we change our theory of physics, not mathematics. By resting on axioms mathematics insulates itself from te physical world.
w00t!
[ Parent ]

Mathematical truth... (none / 0) (#50)
by Estanislao Martínez on Wed Feb 21, 2001 at 06:30:44 AM EST

Actually a = a is an axiom of number theory, if I remember my Godel, Escher, Bach correctly.

eh... having read GEB does not you a number theorist make.

It is well possible to have many different axiomatizations of the very same theory; thus talk about some given formula being an axiom or not of a theory is sloppy talk for the formula in question being an axiom in a particular axiomatization of that theory. That is, "a=a" does not have to be an axiom of number theory; you can set up things differently.

And indeed, I think one could get away with the following pair of axioms to replace it: "0=0", "a+1=a+1". These allow for any number "a" to prove "a=a" in a+1 steps.

Of course, in any self-respecting logical language with identity, "a=a" is taken to be axiomatic, since "=" is taken to be an equivalnce relation (i.e. a=a, a=b<->b=a, a=b&b=c->a=c)

If it were possible to prove a thing in mathematics that was not actually true, then at least one of the axioms would necessarily have to be false.

Outside of having an inconsistent theory, how could you show that the conclusion of a proof was not true?

Deciding whether an axiom is true or false is another whole can of worms entirely--most would say that the statement makes no sense at all, and that you can only say whether given set of axioms is consistent or inconsistent with itself.

This is a tough question of philosophy. Take the axiom of continuity in number theory, which is independent of the other axioms: both the theory with the axiom and that with its negation are consistent. If take a very strong platonist view of mathematics, and you assume that there are mathematical objects, that mathematical statements are statements about mathematical objects, and that all mathematical statements are either true or false, then you have to conclude that one of these theories is true, while the other one is false, but that you can't know which one is which.

On the other hand, if you take a completely different approach, and deny that there are mathematical objects, and thus that statements about mathematical objects are either trivially false or lack a truth value, you then take on the burden of explaining how come theories which seem make reference to mathematical objects and/or use mathematical statements as premises (e.g. pretty much all of modern science) can be true or false.

So, this *is* a mess, indeed.

--em
[ Parent ]

No encryption algorithm is unbreakable (2.20 / 5) (#20)
by tnt on Tue Feb 20, 2001 at 10:49:18 AM EST

(First let me say that I did not read the article. I do not have a subscription, and do not intend to get one. I hate it when they force you to register. But anyways,....)

No encryption algorithm is unbreakable. They should maybe say highly unlikely to be broken. (But not unbreakable.) But I guess it does not have the same ring.

Just look at all these encryption algorithms that use almost prime numbers -- two (usually very large) prime numbers multiplied together. (I think the ones for PGP, https, GnuPG use this sort of algorithm... but don't quote me on it :-) ) They are considered good encryption algorithms because the time it would take to figure out what the two prime numbers (that make up the almost prime number) is O(n!) -- factorial time -- if I remember correctly. (And if the almost prime number has enough digits, and thus n is very large, then...) it will take a very long time to make the calculation (and thus break the code). And when I say long, I mean like longer than the neutrons in this universe are expected to remain stable! But the problem is, when the algorithm was measured to have a computation complexity of O(n!), they assumed we'd be using computers like most people use today... turing machine computers.

Turing machine computers have a certain computational complexity for each algorithm. (Some are basis computational compexities; some are derived from the basis computational complexites.) And these computation complexites were used when measuring how good -- unbreakable -- the encryption algorithms are. But what if we have a computer which is not a turning machine?... Like quantuum computers? Then we would need a new measurement!!! And if I understand quantuum computers correctly, the measurement for figuring out the two prime numbers (that make up the almost prime number) is O(n) -- linear time! Which is considered breakable!

(And if I'm correct in saying that PGP, https, and GnuGP use encryption algorthms based on almost prime numbers, then these algorithms will be broken as soon as quantuum computers are created that have enough bits to do these calculations. And all the data everyone thought was safe will be opened.) (You know, if there was anyone storing all these encrypted communications, even though they weren't able to read them before, they will soon be able to see it all. Does anyone know any organizations in any countries that have been doing this?!)

Disclaimer: I am not an expert on encryption algorithms, or quantuum computers. So it is possible that I've made some errors.



--
     Charles Iliya Krempeaux, B.Sc.
__________________________________________________
  Kuro5hin user #279

different in kind (4.00 / 1) (#23)
by Anonymous 242 on Tue Feb 20, 2001 at 11:00:58 AM EST

No encryption algorithm is unbreakable. They should maybe say highly unlikely to be broken. (But not unbreakable.) But I guess it does not have the same ring.
This article alleges that Dr. Rabin has a mathematical proof that his method is actually unbreakable and not merely unlikely. Obviously, the NY Times is not a peer-reviewed journal so the mathematics behind the proof were not presented. If the article is to believed, the new method is indeed unbreakable. The difference is that this method uses a randomly generated key. If the key is random (in the sense of being non-repeatable, not in the sense of being truly random) and not stored (as it isn't in this method) then there is truly no way for an outsider to recover the key.

I can understand your relectance to register with a site. In this case, however, your reluctance prevents you from reading a very interesting article. It may be worth you while to pick up the paper edition.

[ Parent ]

Re: Different In Kind (3.50 / 2) (#29)
by trust_no_one on Tue Feb 20, 2001 at 11:20:58 AM EST

I am not a cryptographer, although I am interested in the subject. What this sounds like is a continuous one time pad generator. One time pads are provably unbreakable, as long as they are truly not reused and truly randomly generated (pseudo random numbers won't work).

As a practical matter I don't see how this could work. The article talks about the random numbers coming "10 million million per second, for example" eg. 10^13 bps. My DSL connection only is 640K (ie. 6.4 x 10^6 bps), so I'm not sure how I can receive such a stream. Secondly, the synchronization of the "start" signal would be a huge problem. Being off by a nanosecond would cause sender and recipient to receive completely different streams, causing the decryption to fail.

Also, the theory assumes that the attacker cannot store the random stream for any length of time. This may be true if you are generating 10 trillion random bits per second and streaming them, but as I noted above, this seems impractical. If you reduce the bandwidth requirement you reduce the storage requirement as well. Storage is cheap and getting cheaper.

In the end, I don't think this will have any practical application.

--
I used to be disgusted, now I try to be amused
[ Parent ]

millions of bits isn't really that much anymore (3.00 / 1) (#33)
by Anonymous 242 on Tue Feb 20, 2001 at 11:45:53 AM EST

Sure, for your DSL connection 10 Gb of random numbers would be impossible. But for many applications, this amount of bandwidth is child's play. Given that the people most interested in using this tool will be well-heeled corporations and government agencies, this large amount of data isn't that insurmountable of a problem.

Also, unless I misunderstood the article, the sender and receiver of the message do not need the entire 10Gb of streaming noise. They only need an agreed upon method by which to pick out a key from that 10Gb of streaming noise. Attackers, however, would need to store the entire stream to reconstruct the key.

Perhaps you personally don't have any application for this type of technology, but I can think of many situations for individuals, groups, corporations and governments where this type of breakthrough could be extremely practical.

[ Parent ]

Bandwidth is an issue (5.00 / 1) (#34)
by trust_no_one on Tue Feb 20, 2001 at 12:49:58 PM EST

It's not millions of bits, but trillions of bits per second (terabits?).
  • T-1 1.5 Mbps
  • T-3 43 Mbps
  • OC3 155 Mbps
  • OC12 622Mbps
  • OC48 2.5 Gbps (2500 Mbps)
  • OC192 10 Gbps (10,000 Mbps)

Looking over UUNet's route map, I see only one OC-192 and a lot of OC12 and OC48. Basically, this theoretical stream would pretty much saturate all of UUNet's bandwidth right now, and then some. Yes, bandwidth is getting cheaper, but I still don't see this as a practical scheme any time soon.

I'm still unsure if the synchronization issue is a major stumbling block. As long as both parties have Cesium Atomic clocks (or would Hydrogen Masers be better?) the synchronization issue might be able to be overcome. I'm assuming the random stream would have to carry some kind of timestamp information as well, so that both sender and recipient could be sure of being in sync.

--
I used to be disgusted, now I try to be amused
[ Parent ]

My mistake (none / 0) (#35)
by Anonymous 242 on Tue Feb 20, 2001 at 12:59:34 PM EST

It's not millions of bits, but trillions of bits per second (terabits?). </blockqoute> *Ahem*

A Gb typically signifies a Giga-bit which is a billion bits, not a million bits. And the article specifically mentioned millions of bits. Regardless, the random number generator does not have to be stream over the internet. Once could use any source of bits from levels of solar radiation to analog broadcast television converted to digital. All that matters is that level of data in the stream be extremely high. An attacker must essentially record everything that could possibly contain portions of the key in order to duplicate the key at a future point in time.

[ Parent ]

no; at least one is (4.50 / 2) (#25)
by streetlawyer on Tue Feb 20, 2001 at 11:08:52 AM EST

So it is possible that I've made some errors.

'fraid you did. At least one commonly used cryptographic system is unbreakable -- the one time pad. Without the pad, there's no way to crack the cryptogram, and there's no way to extract the pad from the message. And this guy's system looks to me like a version of one-time pad, with a continuously distributed "pad" coming from the satellite. I personally don't think it's all that great a system, but the weakness is unlikely to be mathematical.

--
Just because things have been nonergodic so far, doesn't mean that they'll be nonergodic forever
[ Parent ]

Has anyone found any more detail on the web? (none / 0) (#36)
by SIGFPE on Tue Feb 20, 2001 at 01:01:43 PM EST

He's given at least one talk last December so there must be a description out there somewhere.
SIGFPE
You can always ask him. (none / 0) (#37)
by Anonymous 242 on Tue Feb 20, 2001 at 01:33:22 PM EST

Dr. Michael Rabin's contact info at Harvard's Division of Engineering and Applied Sciences contains his email address.

[ Parent ]
He's probably inundated right now... (none / 0) (#39)
by SIGFPE on Tue Feb 20, 2001 at 01:48:05 PM EST

...but if I get a response I might post some more detail here.
SIGFPE
[ Parent ]
No response (none / 0) (#53)
by SIGFPE on Fri Feb 23, 2001 at 01:01:51 PM EST

Even though I signed myself Dr. (I have a PhD) to feign respectability.
SIGFPE
[ Parent ]
Stream Size (3.33 / 3) (#40)
by paulT on Tue Feb 20, 2001 at 01:51:19 PM EST

In the discussions about this there seem to be some debates regarding the proposed size of the random stream of numbers that would be used for determining the key. This is important because the weak link of this system is size of this stream. If the stream can be recorded then the system falls apart.

From the article:
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.

Two things:

1. If a satellite is used to stream the numbers then such an implemenation could rely on the users receiving the stream via satellite rather than via their Internet connection. The syncing data may be transmitted any available method including the Internet.

What this means is that while current Internet bandwidth could not handle the stream current satellite technology may. If anybody knows how much data could be recieved on small dish. . .

2. 10 million million bits is 125 GigaBytes per second.

10,000,000,000,000,000,000 Bits / 8
equals 125,000,000,000 Bytes or 125 Gigabytes
(If I've screwed up the math please correct me.)

This would require someone to record 125 Gigabytes per second. I frankly do not know if this is possible or not but it would require 7.5 Terabits per minute or 450 Terabits per hour. Perhaps such storage capacities are possible, I don't know.


What confuses me is that this is considered mathematically significant. What it appears Rabin has done is not so much mathematics as come up with a gimmick for a distributed one time pad. One time pads are old and are still a staple of secure communications AFAIK.



--
"Outside of a dog, a book is probably man's best friend; inside of a dog, it's too dark to read." - Groucho Marx
Implementation (4.00 / 2) (#42)
by zephiros on Tue Feb 20, 2001 at 02:09:02 PM EST

So, from my 5-minute cryptanalysis, the largest problem I'm seeing is trust in the key stream. In order for this whole thing to work, both clients must rely on having a key stream with a certain level of entropy. If the key stream consists of, say, the number "7" over and over, a middleman could easily crack the encryption. The problem comes from the key stream being, you know, big. Like real big. Because the bigger the key stream is, the more difficult it is to brute force the system.

So how do you handle verifying that the 10 million numbers you're getting per second really do come from your trusted source? You can't encrypt them; that defeats the entire purpose. I suppose you could have an out of band CRC exchange that used async crypto, but then you're back to doing piles of async algorithm processing. And if you miss a number (or a number gets garbled), your CRC/hash will be off, and you'll need to resync. And even if you can verify that the numbers are from Verisign, how much do you trust Verisign? Enough to hand over the keys to all data encrypted by their stream (remember, the key stream provider can always muck with the numbers)?

The other problem I'm seeing is timing. The issue of secure time synchronization is a big one. It'll get bigger if you have to be accurate to within one ten millionth of a second. Since this system is entirely real time (eg. the sender can't store the message and send it later), if the clients are not using an identical starting number, the message will be lost.

In theory, really interesting stuff. I'd love to read the proof. In practice, I'm not sure how useful something like this would be (over and above other ciphers), since the implementation sounds pretty tricky.
 
Kuro5hin is full of mostly freaks and hostile lunatics - KTB

If you don't have an NY Times registration, (none / 0) (#45)
by Global-Lightning on Tue Feb 20, 2001 at 08:47:35 PM EST

or if you're like me and forgot it, Here's a free link from Infowar

sounds like private key cryptography (none / 0) (#46)
by nickp on Tue Feb 20, 2001 at 10:10:07 PM EST

This sounds so much like private key cryptography, except a little twisted... so I have three questions:
  1. How do two parties securely agree on the key?
  2. Why is this better than using a one-time pad (e.g. pages in a book, tear a new one out each time)?
  3. If an eavesdropper continually monitors the random key stream and knows the time of the transmission, can't he figure out which keys to use?

"Gravitation cannot be held responsible for people falling in love." -- Albert Einstein

Answers. (5.00 / 1) (#51)
by Parity on Wed Feb 21, 2001 at 04:22:54 PM EST

First, it is -a- private key protocol, of sorts.

1. How do two parties securely agree on the key?

By pre-arrangement or a separate key-exchange protocol.

2. Why is this better than using a one-time pad (e.g. pages in a book, tear a new one out each time)?

A single key ('start-time') can encrypt an unlimited amount of data. To send a 5 megabyte message by one-time pad, you need a 5 megabyte pad. And then it's gone. OTOH, you could use one-time pad for key exchange; take 64 bits at a time as seconds since the epoch (or more bits as milli, micro, or nano-seconds since the epoch, depending on the rate of your stream.)

3. If an eavesdropper continually monitors the random key stream and knows the time of the transmission, can't he figure out which keys to use?

Suppose the key-exchange takes place 24 hrs before the message is sent. The eavesdropper would need to record and store 24 hrs worth of keystream, and then any single bit of the stream could be the start-bit.
More importantly, if the key-exchange takes place out-of-band from the data exchange, the eavesdropper does not know when to start recording, and would essentially have to have the entire recording of the keystream from the inception of the broadcast source. (This is the case that was mathematically proved 'unbreakable' because breaking requires infinite storage of the keystream.)
OTOH, if you exchange keys a known, finite amount of time before sending the message, then yes, the attacker might be able to break your message.

Nobody, btw, is saying that this is a huge practical breakthrough that will revolutionize cryptography; it's just a mathematically interesting piece of work in the field that may or may not lead to a practical system.

Parity Odd


[ Parent ]
"Unbreakable" encryption method developed by Harvard Professor | 53 comments (36 topical, 17 editorial, 0 hidden)
Display: Sort:

kuro5hin.org

[XML]
All trademarks and copyrights on this page are owned by their respective companies. The Rest © 2000 - Present Kuro5hin.org Inc.
See our legalese page for copyright policies. Please also read our Privacy Policy.
Kuro5hin.org is powered by Free Software, including Apache, Perl, and Linux, The Scoop Engine that runs this site is freely available, under the terms of the GPL.
Need some help? Email help@kuro5hin.org.
My heart's the long stairs.

Powered by Scoop create account | help/FAQ | mission | links | search | IRC | YOU choose the stories!