Slashdot Mirror
Professor Describes Unbreakable Cryptosystem?
split horizon writes: "The New York Times is reporting that
Professor Michael Rabin of Harvard
University claims to have developed a cryptosystem that is both
practical and provably unbreakable. It sounds to me like it basically uses a one-time pad that's generated on the fly very quickly." Good stuff, but don't expect to see this in the next version of gnupg - the logistical difficulties are high and the system you'll end up with won't be any more secure in practice than public-key encryption techniques already widely available.
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.
What you've written makes no sense to me at all, and I'm a professional cryptographer and so not entirely ignorant about maths and computational complexity theory. If it's meant to be quasi-scientific gibberish, you've gone for some nice choices of words.
If you have a proof that unbreakable encryption is impossible, please write it up and submit it to one of the crypto conferences, and you will instantly become a world-feted mathematician.
--
Xenu loves you!
I know crypto though - see my Web pages. Explain it to me.
--
Xenu loves you!
Rabin's method is...interesting, in its usage of implicit state. But it's not perfect, and as I hope to show, there are semi-serious attacks against it.
To understand his method, one must follow its evolution from the baseline. The most obvious launching point is the PRNG XOR technique: Essentially, two hosts agree to seed a Pseudo Random Number Generator* with the same originating seed, then XOR** their data against that stream of entropy. The unique material that separates the sender and receiver from the rest of the world that is to be kept in the dark is not the psuedorandom stream of data but rather the key that both sides used to establish and synchronize their identical streams of pseudorandom data. If anyone else was to receive this seed, they too would be able to decrypt the XOR'ed ciphertext stream actually sent from the sender to the receiver.
From here we get his shared interaction with a (pseudo, but we'll ignore that)random stream of data.
One major problem, of course, is that there's absolutely no doubt of the *size* of the encrypted message being sent. XOR doesn't increase nor decrease the amount of bytes in the messages "ATTACK" or "SURRENDER", let alone hide whether a message is being sent or not. One thing we can do is have the sender continually broadcast the output of his PRNG whether or not its being XORed against anything, and send a "PRNG differential"(in other words, the exact opposite of whatever the PRNG counter reads) when a ciphertext segment is to begin. Of course, anyone who doesn't have the seed for the PRNG can't know such a trigger occurred, so (as should sound familiar) in order to offline-analyze the cipherstream, they have to analyze all the chaff that its hidden with. The sender and receiver have to be *exchanging* all that cruft though, but that's what they pay to avoid exposure to traffic analysis. The key to the transmission remains, however, the seed to the pseudorandom transmission.
From here we get his asymmetric capture/ignore differential between the eavesdropper and the receiver.
The problem is, in the real world, it's unrealistic for each theoretical communication channel to simultaneously occupy all bandwidth that they might eventually use--especially since the number of possible connections in a network scales exponentially for each additional member! As always in computer science, we need to find a way to convert a high order problem into a fixed expense, O(1).***
So Rabin's solution was to centralize the entropy source. But a central entropy source has to be used differently--the PRNG key can't be used as the message key, because the sender with the message is no longer the generator with the seed. Furthermore, if XOR is be used, entropy cannot be continually shared among all the active sessions, since repeatedly XORing the same entropy against different data compromises the security of the entire system. So what Rabin did was presume the two sides could exchange, not the seed to the PRNG, but a set of "counter times" at which to extract a subset of entropy from the communal pile. Every individual stream would probabilistically negotiate a unique and separate random stream of entropy culled from the global shared pool. This shared key would grant the sender and the receiver the ability to communicate with eachother, but could never independantly decrypt the datastream. Without the "private" reduction from the
"public" shared entropy source, the key would provide no assistance in decrypting the data--and since the data was essentially XOR'ed against a unique set of random data, the data would indeed be uncrackable, because the eavesdropper didn't copy all the necessary pieces.
What's to prevent this copying? "The data stream for the shared entropy is too large."
This is apparently empirically untrue. Solar entropy was brought up as a possible source of shared entropy, with the immediate rejoinder that NASA et al. have no problem storing *vast* amounts of data from the Sun. I heard numbers as large as an exabyte a day of data storage, though I'm sure (I Hope!) that's a gross exaggeration. 24TB a day is easily within reason, however, and 24TB / 24 hours / 60 minutes / 60 seconds leads to a stream of data that reaches 266MB/s.
Standard hardware isn't exactly built to parse data quite that fast, even though that's well within the boundries of full-time recording capacity. But there's no actual need to continually record, since as long as an eavesdropper is looking for interesting things to pull off the wire, they can immediately begin recording from the global datastream whenever they see something being XORed through it.
Essentially, everyone's sharing the same chaff pool, which is moderately interesting.
What's most interesting is the fact that there's an asymmetric function buried in this, and that's Discrete Time. Standard analog time can be considered the "standard" clock; Discrete Time is the beat of the global entropy pool sending up a new value. If one knows the right data at the right time(which segments to use as XOR values), very little expense needs to be levied to discover the plaintext. If one eventually finds out the right data, but much later, a relatively extreme expense needs to be paid to determine the historical value of the cost.
A major possible attack, of course, is subversion of the central source of data. Implementations that use sequential chunks, instead of randomly plucked bits, would be pretty vulnerable to a central source that *looked* random but actually provided significant information to the end listener.
On the flip side, there's a very good question on what a pseudorandomly selected subset of a truly random bitstream qualifies as. Pseudorandom? No--there's no seed that will reveal those bits; one tenth of thermal noise is still thermal noise. Random? Well, they were selected by a predictable function from a non-secret source. Perhaps they're pseudo-pseudo-random?
Hope this analysis helped some of you understand.
Yours Truly,
Dan Kaminsky
DoxPara Research
http://www.doxpara.com
* Pseudo Random Number Generator: a function that converts a fixed set of bits into an infinitely large set of predetermined but statistically random numbers)
** XOR: Exclusive OR; a trivial and reversable operation that scrambles data on a bit by bit basis. XORing something with random data once results in random data; XORing it again with the same random data results in the original content.
*** O(1): Order 1 -- No matter how many items in set N, the task will only be done once.
PGN has been arguing all along that new voting systems must have their source code available; see comp.risks for the past few months. So why refer to some fearful "them"?
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.
The method relies on the random number stream not being bufferable for the time it takes to crack the start-time message.
However the speed of light makes it easy to delay the RNG signal by reflecting it off of a suitably distant relay station a few light-minutes or hours away, say near Mars. By the time the signal makes it back, the start time can be cracked and ready for decryption.
---- "If we have to go on with these damned quantum jumps, then I'm sorry that I ever got involved" - Erwin Schrodinger
(because I just posted the same idea).
But you beat me by 22 minutes.
Also, you could pass the signal through one of those light-speed-reduced materials that people keep coming up with. I'm not sure what it would do to the signal quality, but you could get a heck of a lot of data into a pipe where light goes 42 mph.
---- "If we have to go on with these damned quantum jumps, then I'm sorry that I ever got involved" - Erwin Schrodinger
> He hasn't solved the key distribution problem.
True, but he doesn't claim to do so. He assumes that a reasonable distribution method exists that can resist attack for some relatively short period of time. I agree with you that he relies on assumptions, and this is one of them. However, I also think that this is a relatively safe assumption, and to say that his scheme falls apart because of this assumption is too strong a statement.
Well, the thing is that it isn't a short period of time. Presumably your public key doesn't change that often, so if someone can crack that key, then they can listen in on the start of your conversation, whenever that occurs Also, they can perform a man-in-the-middle attack at any time, and any transaction you make is then compromised.
Unfortunately there is no good solution to this problem, and therefore his assumption is false. So maybe I'm being harsh with his idea because it doesn't address what I see as the more essential problem. Sure, huge compute farms at the NSA and quantum computers scare me a little, but right now the system is vulnerable, and this isn't a solution to that vulnerability.
I really should have made the subject "The Fatal Assumption", because my other points were mostly just speculation about the algorithm itself.
If someone finds a fast factoring algorithm, then he could go back and easily decode lots of transactions whose 128 bit secret keys were transmitted using RSA for protection.
I thought factoring was NP-complete, in which case all (all, he says ^_^) you should need to do is make the keyspace large enough such that it would take a hundred years to crack even if every elementary particle in the universe were used to crack it. But I'm quite possibly wrong (and we haven't gotten to NP-completeness in my algorithms class yet ^_^)
Still, it is a neat idea for providing that future security.
However, I do think that an argument by someone like Rabin deserves a little extra thought before a rebuttle is made.
Well, as I continue to fall back, I'll say that it does seem like a good idea, and hopefully peer review will bear that out. I just wish someone would solve the key distribution problem.
p.s. I apologize if my tone was beligerent before.
Well, I didn't think it was, so no harm done. Maybe you didn't like me attacking someone you respect, eh? Normal, I'd say. ^_^
The enemies of Democracy are
This is missing the point--the secret only has to be secure for a short amount of time. If the listener cannot crack your secret key immediately, he has no chance of ever intercepting the data.
He hasn't solved the key distribution problem. He assumes that a solution exists, and then uses it. There are two methods obvious to me in which the secret key can be compromised immediately:
1) no solution to key distribution. How do you prevent man-in-the-middle attacks? A simple two-step process, and the enemy can listen in on the conversation with ease.
2) the enemy can apply brute-force methods to cracking the private key, and can then decode the secret message as rapidly as the client. Now the scheme does depend on the computational power of your enemy, which the scheme was supposed to get away from.
Again, not true. Using your scheme, a cryptanalyst with plenty of time could decode your message at his leisure. Using Rabin's approach, an analysis after the fact is useless. You're missing the whole point of this scheme.
Alright, you got me there. If we take his other assumptions to be true, then it will work.
Now, not counting the ones I already listed, then I do have to at least be leary of the assumption that storage is a more finite resource than computing power. If the enemy has computers than can crack arbitrary-length-keyed traditional encryption in a reasonable amount of time, why can't they store the random numbers for some period of time sufficient to encompass the transmissions they are interested in?
Still, barring that, and the public key front-end's vulnerability, it would work.
I'd be a little more careful when trying to poke holes in the work of one of the gods of the field.
He's smart, so it must work? Yeah, right. That's what my incredibly useless group member in the VLSI course I took said about my ALU when I asked him why he didn't test it thoroughly.
The thing is, I'm not trying to poke (many) holes in his encryption method. I'm poking holes in the protocol, which is usually the weakest link (like in this case). His key generator and encryption scheme can be perfect but if the protocol is flawed, then it doesn't matter if he's using the RNG-satellite method or XOR.
The enemies of Democracy are
All your crypto are belong to us!
If tits were wings it'd be flying around.
In this case the key is the start time of the
:-( :-( :-(
"infinite" encoding key. The start time has to
be agreed and transmitted between parties.
:-(
It occurs to me that this method of key distribution is ill-thought out. While it is true that capturing the entire stream is impracticle in terms of storage, it's also unnecessary.
*traffic analysis will quickly reveal times of day/night that your targets are exchanging messages
*Depending on the protocol, if both parties have to be communicating in realtime, it's trivially easy to watch the traffic and see the channel being set up and capture the correct OTP bitstream.
*target parties must still communicate when to start using the stream--the OTP crypto here is only as strong as this link, which could rely on repetition or an algorithm for time-to-start, other encryption (which changes 'unbreakable' to 'impractical-like-breaking-RSA'), and can be determined by power analysis (Alice always flips on her sat. dish at 9:05:43...)
*MitM -- how is the bitstream authorized? Who would notice if some TLA changed it from a highly-random algorith to a deduceable algorithm?
*EVEN IF none of these work, storage remains cheap. write the bitstream--or, chunks of 5 characters of the bitstream, wait 5, store 5 more, etc.--to a tape.
OTPs remain very difficult to use and use correctly. This is nice, but it's not going to magically solve our problems.
Returned Peace Corps IT Volunteer
Um, no accounting for Blowfish (used in hushmail) or TwoFish (NIST finalist for the AES standard, beating out 12 other algorithms from luminaries such as RSA). Don't forget Solitaire, either.
Schneier knows crypto.
Returned Peace Corps IT Volunteer
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
It's official. Most of you are morons.
the start code itself is vulnerable. With quantum cracking, even a 128-bit key may fall within moments, in which case the resulting datastream will be insecure. (This is the 'weakest link' approach, as the whole system relies on the impracticality of decrypting a conventional crypto system in a given timeframe and is therefore not 'impenetrable')
How are the sender and receiver supposed to synchronize if the satellite is sending 10 million random numbers per second? The sender must wait as the receiver needs time to receive the start message. The sender can't start its OTP if the receiver is not perfectly sync'd.
And what about satellite latency? The random number stream must use sequence numbers because I doubt the sender and receiver can syncrhonize their CPU clocks to run at exactly the same 10 million reads per second rate!
The cracker in the middle knows to start recording the satellite's number stream when he first sees the sender's start message. He knows to stop recording the number stream when the sender's a message FIN (or whatever).
cpeterso
It is unbreakable. Is he not describing a one-time pad?
If he is, you can't break it, period.
You could generate every possible key and run it against the ciphertext.. but this equates to , for a ciphertext of 8 characters, generating every possible compbination of 8 characters and deciding which is the 'real' message, just like an infinite number of monkeys...
It is true that a one-time pad is not breakable.
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
Kaa
Kaa's Law: In any sufficiently large group of people most are idiots.
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
Kaa
Kaa's Law: In any sufficiently large group of people most are idiots.
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
--
Enjoy Y2K? Roll-on Year 2037!
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.
----------------------------------------------
the pun is mightier than the sword
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.
... (fast enough to be not "storeable")
:-)
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
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
You are right. Rabin is a great matematician.
BUT: most of the issues of the discussion are about the PRACTIAL outcome.
He may consider the whole matematics about that, but not if its practical to do that.
What you're saying is equivalent to saying that just because we can prove that 1+1=2 doesn't mean that taking 1 penny and taking 1 other penny means that we have taken 2 pennies. After all, someone might screw up the process, and not correctly take the pennies correctly, thus ending up with some other number of pennies.
It's just the old "Math only proves math" argument. You've been reading that jackass Ritter's page, haven't you? He's just cutting down methods that use math that he can't handle to promote his own (often patented) products with a blend of hand waving and cargo-cult nonsense.
What you're really doing is just screwing around with semantics to make other people's statements seem wrong. You merely betray your ignorance of how mathematics interacts with the real world, and how such interactions are discussed in common parlance.
Furthermore, a message isn't just "secure or insecure", it either leaks all bits, leaks some bits, or leaks no bits. There are special advantages to having a random key that grows with the message, such as security degrading gracefully: having one part of the message cracked does not mean that other parts are also cracked.
---
He's not going to prove that it's impractical to store all bits transmitted forever, he's going to assume it, just as the OTP security proof assumes a true random source and a perfectly secure early communication.
Anything like this always has some pretty sweeping assumptions.
---
He's not describing a one-time pad, since the "pad" is public. He's effectively describing a Rip van Winkle cipher, without the limitations of a Rip van Winkle cipher.
BTW Chinacat, I think you read the algorithm wrong. The unbreakable code is to zero the data. Depending on where the data's been stored before, it may be possible to break, but it's certainly not for lack of characters!
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.
-- MartinG To mail me: echo kewyjlcxyzvjfxbqwh | tr bcefhjklqvwxyz
Let me see if I have you right: the "difficulty" in this cipher is storing the right sequence of digits. As evesdroppers we either have to
1) break the symmetric cipher used to send the offset/length estimate of the pad to be used (est difficulty 128 bits)
2) or store all the random numbers from the time of reception + decoding (since no numbers before that time can be assumed to be in the possession of the recipient) until the message has been sent.
Now, the problem is that the bitrate of the broadcast OTP is limited by what can reliably be recieved -- say 100Mb/s -- and the sender and reciever want to send the message soonish. If I have a terabyte disk array, then I can store 80,000 seconds (~ 24 hrs) worth. That is only a keyspace of 40 bits.
The longer you delay sending the message, the better, but if the attacker can influence the situation by selectively disrupting the reception of the OTP, they can make it become abritrarily unreliable to send a message of either significant length or security. As soon as either sender or recipient is jammed during key recording, they have to start over.
Of course, Alice and Bob can start sending spurious (start/length,keyid) messages (and then select one of these keys at random) to make Eve's recording needs all the more difficult, but the fundamental problem is that Alice and Bob have to outwait my storage ability to be sure of message security. And then I can start storing snippets of the OPT randomly, so that I can probablistically try to decode partial messages.
Note that once I've managed to decode part of a message, I also have a plaintext/ciphertext pair to use to try to crack the symmetric encryption of the initial start message.
You definately have me on the first point. I wasn't aware that that had not been shown to be NP-hard. Thanks for the notice. However, even if it is only in NP, finding a solution for an NP complete problem would still provide a solution to factoring, even if finding a solution to factoring would not provide a solution to all other NP problems. On the second point, I agree, there may be other ways to break RSA. But finding an effecient algorithm for factoring would break RSA. My point was never that RSA was the same as factoring, but that it was "based on" factoring, in the sense that solving the factoring problem would defeat the encryption system. Even if there were a proof that factoring was the only way to beat RSA (which you claim, and I believe as well, that there is not), this would not prove RSA to be secure as long as it remained to prove that the factoring problem could not be solved. So I agree, you're correct in both cases. But I don't think that alters the main point of my argument. I will admit, however, to spreading misconception by having been a victim of it. Thanks!
"Sweet creeping zombie Jesus!"
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/
I don't like
- 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
I don't even think this is one of his assumptions... you only need to store the stream during the time the transmission you want to decrypt is being sent. Even at 10 million million numbers per second, any conversation taking less than a few minutes results in a fairly reasonable amount of data to sift through. Especially if you can crack the first private message that describes how the sender/receiver decide what numbers to pull.
Even more than a few minutes is no problem, as you say, because storage is getting exponentially larger.
You hit on the other problem with this scenario, and that is that the encryption/decryption has to take place in real time. The joy of Public Key encryption (one of many) is that you can just create a message and send it for later decoding.
Not every computer that we want secure works in real time.
You cannot assume that an eavesdropper will take 1 minute to decode a start message if the real recipient is not doing to take a minute themselves.
I'm sure they are assuming some type of private keying communication to send the start sequence which designates a future exact time to start the decoding (considering network lag). Part of the proof probably involves the requirement of the secrecy of the private keys. If this is thwarted, then you might as well assume that your keyboard has key-strokes running. I don't believe it's possible for a middle man to fully hack into such a system (I'm not a cryptographer) without such a private key.
I also agree that this can only be used for communication channels, and not storage. Seemed obvious to me, actually. But I believe it's great strengths are in cell-phones, or encrypted versions of Messenger services. Two things that are regularly monitored (and some times stored for later encryption). I don't think this could work with traditional email for the reasons you've pointed out, so the practicality is obviously limited.
The greatest boon, however is that if the FED requires you to give up your private key (that initiates a communications channel), it doesn't do them any good. It only temporarily inconviniences you until you get a new one for future communications. This, I think is one of his main excitements.
-Michael
-Michael
As there is no 100% secure way to guarantee that you get the right stream, unless you do it yourself, this means that the sender of the message must send this infinite stream.
Sure there's a way you garuntee the right stream. The first part of the encrypted message is a simple validation check. If the recipient doesn't decode it properly, then they know something is wrong, and they can communicate this through un-secure channels (traditional public/private key). The worst that can happen is a denial of communication through either lack of a random-number feed, or by convoluting the feed at different locations.
I believe the suggested method is to have one or more satalite streams, intercepted either by the cell phones, or an IP source which rebroadcasts in multi-cast.
Both methods allow for disruptions in the random-number signal, but so long as the process allows for resyncing, then things are fine; in fact that helps make the channel even more encrypted (except that you could monitor for the breaks, which might possibly let you know which channel they're listening to, and possibly allow ease droppers to sync up as well).
-Michael
-Michael
> I mean, really. If we had a 'secret' way to
> safely exchange keys, we could just use that
> method to communicate in the first place!
This is missing the point--the secret only has to be secure for a short amount of time. If the listener cannot crack your secret key immediately, he has no chance of ever intercepting the data.
> If we take the window of vulnerability in his
> method to be X seconds, then this would be no
> better than using current techniques but issuing
> a new private key every Y X seconds (no
> satellite required)
Again, not true. Using your scheme, a cryptanalyst with plenty of time could decode your message at his leisure. Using Rabin's approach, an analysis after the fact is useless. You're missing the whole point of this scheme.
I should point out that Rabin has an excellent understanding of practical issues. RSA encryption would not be usable without his randomized primality testing algorithm (every RSA key generator relies on it) for which he won the Turing award in the 70's. I'd be a little more careful when trying to poke holes in the work of one of the gods of the field.
- Russ
Ack! Stop moderating these posts up! That's not true! Go take discrete math!
h 12.10.96.html
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/sale
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.
The problem with this, is that the moment you put in a validation check, you violate the whole reason that a OTP is provably secure: that an eavesdropper can't tell whether they decrypted your message, or just happened to stumble across a key which generated some other kind of message.
For a true OTP system, there shouldn't be any kind of formal, automatible validation check.
One Time Pad (OTP) is provably unbreakable. The weak links in an implementation may not be provably unbreakable, but an algorithm or a process most certainly _can_ be provably unbreakable, if that algorithm is reducible to an OTP encryption. Which is exactly what this is. I have no idea what Rabin's supposed "proof" contains in it, other than "proving" that distributing massive volumes of information makes storage over time unfeasible and therefore it is only probabilistically compromisable with vanishingly small probability (luck). If you can prove that your protocol reveals 0 bits of information about the message M and 0 bits of information about your One Time Pad, then you have just proved that you have an unbreakable _cryptosystem_, i.e. a protocol combined with an OTP system.
"There is also no such thing as a provable secure Cipher."
Why? Can you give me a proof? Under some (reasonable, I argue) assumptions, you can certainly prove that a cryptosystem or protocol meets certain properties that you deem (reasonably, I argue) sufficient for security.
Rabin is not just some crazy guy popping out of the woodwork. You probably use his algorithms if you use PGP or GPG or anything else which needs to generate large primes...
I am not referring to skepticism, nor am I discouraging people to find his paper and really give it the go-over it deserves. That's how all of the other cryptosystems you point out were broken.
What I am complaining about is all the posts which say, "I read in a book that you can't prove a cryptosystem secure!" or "It's the same as a one-time pad!" or "His key assumption is wrong!" or whatever else. My point is that while his proof may have an error, or there may be subtle issues about him proving the wrong thing, the NYT article does NOT give anyone here enough information to start tearing his work apart. Cast doubt? Perhaps. But an outright claim that he is wrong, or that he is repeating work that's already done (based on the superficial Science Page treatment in the article)... ridiculous. Offensive, even.
Rabin's claim is not unsupported, as far as we know. He says he has a proof, and others seem to agree...
As I understand it, the way you agree on where to start sampling can be much more complicated than you seem to imply. I can ask to start at a particular time, or as soon as a particular sequence of numbers show up, and then I can skip numbers based on any sort of algorithm I choose.
As for doing trial decryptions: This is a totally bogus argument. If the key stream is really random, then all possible decryptions are equally likely (assuming a typical XOR-like encryption). How will you know if you've got the right message?
Maybe we should wait to see a real, technical discussion of this before we discard it? Rabin is a pretty big name in cryptography.
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 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.
Find funky gifts
Where's the usual "New York Times No Registration Required" link?
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.
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.
Random numbers are not good enough if your need 100% all-the-time security. It's theoretically possible for a truly random number generator to spit out 10000 zeros in a row which could leave your message (or interesting parts of it) wide open.
False. Wrong. Incorrect. Pad must BE random to be provably unbreakable.
'Sides, it's equally likely that a true random sequence would contain precisely the bit sequence, which, when XOR'ed with your plaintext, yields the ciphertext "Th15 M322A63 C0n7A1N5 T0P-53CR3T N000Cl34R B0MB Pl4N5!!!"
The nerve of that man. He did it because it was a challenge?! My ancestors fought and died so we could have software patents in this country. Patents to provide us with the incentive to innovate. And he does this stuff for fun?
Because it was challenge?!!!
And he's just going to give this stuff away? Good God, the man's a communist. I'm writing my congressmen -- I want him deported immediately.
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.
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.
Good point. But is this true even now? You need a computer to generate the keystream, right?
sulli
RTFJ.
That assumption seems very risky. As noted in other comments here, storage and memory keep getting cheaper. Wouldn't it be possible for an eavesdropper to get a massive number (beowulf cluster?!) of PCs with massive hard drives and just capture and store it all? Then the cryptanalyst, knowing approximately when the message is sent, would test the million (say) available, stored keystreams against the ciphertext using a similarly massive computing cluster. Moore's law hasn't failed us yet...
sulli
RTFJ.
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?
microsoftword.mp3 - it doesn't care that they're not words...
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.
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?
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!!
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.
This sentence is misleading for the following reasons:
- It has not been proven that the integer factorization problem is NP-complete. An NP complete problem by definition is both NP and NP-hard. Integer factorization is known to be NP but it is not known to be NP-hard.
- It has not been proven that RSA is equivalent to factoring. We know that if the factoring problem is solved then the RSA problem is solved, but we do not have a proof that factoring is the only way to solve the RSA problem.
Please try to avoid furthering the misconceptions that factoring is NP-complete or that RSA is equivalent to factoring. Both facts might very well be true, but they have not yet been proven.Speaking of true random number generators, check out SGI's Lavarand .
;)
"Lavarand... harnessing the power of Lava Lite® lamps to generate truly random numbers since 1996"
fun!
cpeterso
If the underlying assumption is true, this system provides perfect forward secrecy: the compromise of my 'key exchange' key at any point in the future does not reveal my previous messages, as the OTP material is long gone by that point.
The security hinges on the fact that by the time an attacker could decrypt my 'start here' instructions, so much of the public OTP stream will have gone by that he couldn't feasibly store it all and thus can never recover the OTP. This 'never' is a dangerous word. The OTP stream is public, and thus an attacker does have access to the OTP I used, if he can determine my 'start' point.
A brute-force attack on this system would seem to be linear in space which a huge constant dependent on your bitrate, bounded by an attack on your key exchange mechanism. In a system providing any sort of 'interactive' performance, the search space is limited greatly. Admittedly, for short messages the search space in the stream could rapidly exceed the an exhaustive search.
It's a clever idea. I'm not exactly sure how to evaluate the security of the system, and any implementation seems that it would be prone to an array of interesting attacks, but I like it.
--Jered
This is certainly a very nice result, now it has to be published and analyzed before we can say more. From the short description in the article, it seems that there is a stream of random number which comes in at very high speed and that to decipher, you have to know which part of the stream was used. Well, if you are "lucky", you can just store small parts of the stream from time to time and maybe you'll get the very right one. Of course, the probability is negligeable, but the probability to guess the key in a traditionnal cypher is too!
Naturally here, the nice thing seems to be that if you don't get the right part of the stream, you will never be able to decipher no matter how long you spend, whereas in traditionnal settings, you will be able to decipher after some time (say a few million years)...
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!"
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.
While I'm not really qualified to comment on the details or the proof or anything, it certainly sounds like there are some major applied/practical limitations in the scheme to me. But for a subset of current encryption practices, this could be very useful, in particular for a lot of current applications of public key cryptosystems.
Frankly, I think Rabin is just pissed that the public key cryptosystem that bears his name never achieved wide commercial use and instead RSA became the standard. Now he wants to supplant public key cryptosystems with something entirely different. His ego is rather huge, and not entirely unrightfully so.
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.
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.
Today, data storage is far, far cheaper. And broadcast spectrum is scarce. Consider DirecTV. The entire output, all 100+ channels, fits in under 500MHz of spectrum. And they work hard to manage that spectrum efficiently; each channel has a different data rate (sports are around 8Mb/sec, C-SPAN is probably a tenth of that.) Data (non video/audio services) over DirecTV uses about 30 Mb/sec. DirecTV is using about a billion dollars worth of spectrum at current prices.
So a very generous random data feed from orbit would be 100 Mb/sec. That would fill a DVD every five minutes or so, or an 80GB hard drive in an hour or so. (If it's random, compression is impossible, of course.) That's a lot of storage, but not an impossible amount. Storing it would be cheaper than buying the spectrum required to transmit it.
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
Quidquid latine dictum sit, altum videtur.
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.
Does my bum look big in this?
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
Man, you guys think you're so smart because you read Applied Cryptography and some recreational mathematics books in high school.
Rabin is a bigshot in number theory, being the Rabin part of the very popular Rabin-Miller algorithm for probabilistic primality testing. Your favorite cryptography program almost certainly has an implementation of this in it.
If he says he has a proof, for god's sake, he has one! There's no way the NYT is going to publish enough information for you to seriously dissect his work. In fact, there's hardly enough information there to even get a start at reconstructing his results. Give the dude a break!
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.
ich bin der musikant
mit taschenrechner in der hand
kraftwerk
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.
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.
The enemies of Democracy are
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
--
Kevin Fox
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