Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!

 



Forgot your password?
typodupeerror
Encryption Security

Professor Describes Unbreakable Cryptosystem? 241

Posted by michael
from the much-snake-oil,-few-insights dept.
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.
This discussion has been archived. No new comments can be posted.

Professor Describes Unbreakable Cryptosystem?

Comments Filter:
  • by Anonymous Coward
    I got PGP but it is important that people dont know that I got encryption let alone what I am talking about so I incrypted the program only now it wont uncrypt and it says bad command or file name. Did I discover some kine of unbreakable incryption cause I cant get it uncrypted.
  • Reading between the lines, I'm guessing that Rabin's scheme works like this (assume 1024 bit key for concreteness):

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

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

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

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

  • by Anonymous Coward
    So, the sending site sends a "start" message. I recieve the start message, and start grabbing numbers. at 10 million million numbers per second, and latency of ANY network communication, how are we to know that the client and server machines start their number strings at the same time? Do we send a partial number string to identify a common point, and start say... 10 billion after that? The "start" message is being sent with "normal" encryption... when you see the start message, start grabbing numbers. decode the start message to find the "tag" and start point... then go back to your number string and find it, GAME OVER. So... While, in theory, this sounds like it would work, I can see no way to impliment it in practice. --Doku (doku@yahoo.com)
  • Cryptonomicon, great book by Stephenson (author of Snow Crash). Although it's a novel, it explains crypography in very simple terms, and is a good introduction to the subject.
  • by Anonymous Coward
    Nope your wrong. Mathematicians do it all the time. Like they've proved that you can't solve an indefinate integral for e^x^2.
  • You're also assuming the satellite transmission is secure. This would require that you fully trust everybody involved in building and launching the satellite - throw one rogue programmer in the mix and you could have the satellite spitting out pseudo-random numbers which could make this easily crackable.

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

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

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

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

    now THAT is a cute chalange. a tiny ADC sampling a noisy crude resistor or some other phenomenon. the white noise of radio reception when opening up to a wide band of frequency. to recreate that stream of numbers you have to record an unknown amount of radio noise within an unknown frequency range at the very same physical place as the original recorded stream and the same magnetic interference.
  • 1 + 1 = 2 is not an axiom, is is the conclusion of various theorems that come from the construction of the natural numbers. The assumptions math is developed from are not very specific to numbers.
  • This is certainly an interesting idea, but it does not really solve any of the fundamental problems with cryptography. Modern cryptography itself is essentially unbreakable -- Grab one of the variable-key-length symmetric ciphers with a big key (256+ bits) and you have crypto that is, in and of itself, essentially unbreakable. The problem isn't the cryptography, really, it's the stuff around it -- The users, the software, and the key-exchange mechanism. In modern times, if you want to steal someone's secrets, a full frontal assault on the actual cryptography is almost certainly the worst possible way to attack.

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

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

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

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

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

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

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

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

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

    Baz
  • I've only scan read the NY Times article, but it seems to boil down to agreeing a start time to read from the one time pad. How is this done securely?
  • Nah, that's not true. The only two things to be done in real-time in this proposed algorithm is sending the time at which the "snapshot" of the keystream must be made from Alice to Bob, and recording some part of the keystream at the time of the snapshot. Encrypting the message by Alice (XOR) with the snapshot taken from the keystream can be done later (but not much later or the snapshot on the harddisk may have been compromised), the ciphertext is then sent from Alice to Bob, and Bob can decrypt the message when he wants for as long as he keept the snapshot from the keystream on his disk.

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

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

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

    Erwin
  • Since crypto is mentioned, I'll ask a
    question that bothered me for a while.
    Say you had a message and a key, such that
    both were identical. What encryption
    algorithm today would be most secure
    under this setting.
    Example: store password encrypted with
    itself. When user enters password, decrypt
    encrypted message and compare with password
    entered. Given that passwords are small
    eficiency of algrotithm is unimportant.
    What is the best encryption method (defined
    as time to decryption on a predefined turing
    machine) for this purpose?
  • One time pads are provably secure. Proof (as always) hold with respect to a collection of assumptions. In this case the assumptions include the existence of a publically readable source of random bits that is too copious to be stored. Other "provably secure" systems exist (e.g. Cramer- Shoup which assumes the Decision Diffie-Hellman assumption).
  • Your solution sounds a lot like the same solution I already proposed:

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

    you: simple to solve, include a second syncronization number (which are sequential) with each random number sent.
  • by QuMa (19440)
    One time pads are completely unbreakable (read "Applied Cryptography" if you doubt me).
    Yes, of course, I didn't claim they where.

    The problem is, if you want to use a OTP, you can't have a key smaller than the plaintext. This does have a key smaller than the plaintext, hence it is not a OTP, hence it is not proven secure.
  • by QuMa (19440)
    Read the sci.crypt threads on using a blum-blum-schub random generator for creating a one-time pad on dejanews... This is just more of the same. Sure, he might have found a better PRNG for doing it, but it's still just as breakable as anything, and certainly nothing new.
  • Exactly.

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

    As someone else pointed out, a cypher system is as strong as its weakest link and that's usually the gray matter at either end of the encryption.
  • We certainly don't know if radioactive decay is truly random. It could well be governed by something else. Pick your FTL hidden-variable of the day...

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

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

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

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

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

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

  • 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.
    --
  • I know crypto though - see my Web pages. Explain it to me.
    --
  • 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.

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

  • > 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. ^_^

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

  • by PD (9577)
    All your crypto are belong to us!
  • 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.
  • 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.
  • by Tim C (15259)
    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
  • 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).
  • 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
  • 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
  • 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 :-)
    --
  • 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 problem lies within syncing the stream. if two people can do that somehow through the net, a third one (= intruder) can do that too, because this communication uses conventional ("breakable" :-) algorithms.

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

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

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

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

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

    sure :-)
  • 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.
  • 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!"
  • The Enigma was NOT unbreakable it was just hyped to be unbreakable.

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

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

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

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

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

    Some other famous ones in computer science are proofs that infinite compression is impossible, or Alan Turings famous disproof of "The Halting Problem" that is a basis for computer programming.
  • The first part of the encrypted message is a simple validation check.

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

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

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

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


  • "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.
  • This does not impress me. Isn't this just a proof that the one-time pad is secure? Hasn't that be demostrated?

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

    So - am I wrong?

  • Surely 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.
  • 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!!!"
  • From the article:
    Dr. Rabin says he has no commercial interests in it.

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

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

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

    Because it was challenge?!!!

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

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

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

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

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

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

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

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

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

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

  • If the eavesdropper, for example, had a secret way to decode the message saying "start" and it took a minute to do the calculation needed to decode it, it would be too late by the time the eavesdropper got going. The sender and recipient would already have their string of numbers and that string of numbers, once broadcast, could never be retrieved. It would be infeasible to store the endless string of numbers in any computer and so they are essentially gone forever.

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

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

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

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

    Harvard professors are such media pigs.

  • by David Jao (2759) <djao@dominia.org> on Tuesday February 20, 2001 @09:23AM (#418478) Homepage
    Almost all current algorithms are based on a NP-complete math problem- something like factoring, in the case of RSA.

    This sentence is misleading for the following reasons:

    • It has not been proven that the integer factorization problem is NP-complete. An NP complete problem by definition is both NP and NP-hard. Integer factorization is known to be NP but it is not known to be NP-hard.
    • It has not been proven that RSA is equivalent to factoring. We know that if the factoring problem is solved then the RSA problem is solved, but we do not have a proof that factoring is the only way to solve the RSA problem.
    Please try to avoid furthering the misconceptions that factoring is NP-complete or that RSA is equivalent to factoring. Both facts might very well be true, but they have not yet been proven.
  • by cpeterso (19082) on Tuesday February 20, 2001 @11:38AM (#418479) Homepage
    Speaking of true random number generators, check out SGI's Lavarand [sgi.com].

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

    fun! ;)

  • by Jered (32096) on Tuesday February 20, 2001 @09:34AM (#418480) Homepage
    The word "unbreakable" is overused. This is not "unbreakable" in the sense that a traditional OTP is unbreakable, however it is clever, and has some interesting properties.

    If the underlying assumption is true, this system provides perfect forward secrecy: the compromise of my 'key exchange' key at any point in the future does not reveal my previous messages, as the OTP material is long gone by that point.

    The security hinges on the fact that by the time an attacker could decrypt my 'start here' instructions, so much of the public OTP stream will have gone by that he couldn't feasibly store it all and thus can never recover the OTP. This 'never' is a dangerous word. The OTP stream is public, and thus an attacker does have access to the OTP I used, if he can determine my 'start' point.

    A brute-force attack on this system would seem to be linear in space which a huge constant dependent on your bitrate, bounded by an attack on your key exchange mechanism. In a system providing any sort of 'interactive' performance, the search space is limited greatly. Admittedly, for short messages the search space in the stream could rapidly exceed the an exhaustive search.

    It's a clever idea. I'm not exactly sure how to evaluate the security of the system, and any implementation seems that it would be prone to an array of interesting attacks, but I like it.

    --Jered

  • by JPS (58437) on Tuesday February 20, 2001 @05:33AM (#418481) Homepage
    I can't believe the number of people who claim this cypher is bullshit without even seeing it. I mean, this is not coming from some random guy. Michael Rabin is one of the best cryptologist ever. Furthermore, he does not actually claim that his scheme is "unbreakable". He claims that in standard schemes the security relies on an assumption on the limitation of the computing power of the adversary and that in his scheme, the security relies on the assumption on the limitation of the storage of the adversary, independantly of his computing power, which may be infinite.


    This is certainly a very nice result, now it has to be published and analyzed before we can say more. From the short description in the article, it seems that there is a stream of random number which comes in at very high speed and that to decipher, you have to know which part of the stream was used. Well, if you are "lucky", you can just store small parts of the stream from time to time and maybe you'll get the very right one. Of course, the probability is negligeable, but the probability to guess the key in a traditionnal cypher is too!


    Naturally here, the nice thing seems to be that if you don't get the right part of the stream, you will never be able to decipher no matter how long you spend, whereas in traditionnal settings, you will be able to decipher after some time (say a few million years)...

  • by Spasemunki (63473) on Tuesday February 20, 2001 @04:33AM (#418482) Homepage
    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!"
  • by javatips (66293) on Tuesday February 20, 2001 @03:45AM (#418483) Homepage
    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.
  • by Fnkmaster (89084) on Tuesday February 20, 2001 @05:37AM (#418484)
    I invited Michael Rabin to dinner with me at a House dinner at Harvard last year. I (a physics student taking a class with Rabin) and a math major sitting across the table were listening to Rabin describe this exact cryptosystem at the time and we were going through the probabilistic analysis of this simultaneous, time synchronized OTP key distribution system (that's basically what this is). Frankly, we thought he had sort of, well, lost it a bit over the years if he thought this was a "real" cryptosystem. But we just kept nodding. What's interesting is that it modifies the difficulty of compromising the encryption scheme by moving it into space-domain rather than time-domain (it's storage space limited). And he knew this was provably secure a year ago, so I don't really think this is news (although perhaps he hadn't published or formally presented his results yet).

    While I'm not really qualified to comment on the details or the proof or anything, it certainly sounds like there are some major applied/practical limitations in the scheme to me. But for a subset of current encryption practices, this could be very useful, in particular for a lot of current applications of public key cryptosystems.

    Frankly, I think Rabin is just pissed that the public key cryptosystem that bears his name never achieved wide commercial use and instead RSA became the standard. Now he wants to supplant public key cryptosystems with something entirely different. His ego is rather huge, and not entirely unrightfully so.

  • by gargle (97883) on Tuesday February 20, 2001 @03:30AM (#418485) Homepage
    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.

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

    Today, data storage is far, far cheaper. And broadcast spectrum is scarce. Consider DirecTV. The entire output, all 100+ channels, fits in under 500MHz of spectrum. And they work hard to manage that spectrum efficiently; each channel has a different data rate (sports are around 8Mb/sec, C-SPAN is probably a tenth of that.) Data (non video/audio services) over DirecTV uses about 30 Mb/sec. DirecTV is using about a billion dollars worth of spectrum at current prices.

    So a very generous random data feed from orbit would be 100 Mb/sec. That would fill a DVD every five minutes or so, or an 80GB hard drive in an hour or so. (If it's random, compression is impossible, of course.) That's a lot of storage, but not an impossible amount. Storing it would be cheaper than buying the spectrum required to transmit it.

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

    Hypothesis: You can't find a real number "x" such that x^2 < 0 .

    Proof: Left as an excersise for the reader...

    QED.

    What you are thinking of is different -- for eg, if I were to say "Pigs can't fly", I couldn't prove this without finding _every_ instance of a pig, and making it try to fly. Even then, it would be a shaky proof, because how do I know how to make pigs fly? (I guess we'll have to wait for MS to release some good software)... and _even_ _then_, how do I know I have found all the pigs?

    Interestingly, there is a whole set of problems in mathematics which are provably unsolvable. With many hypothesis, the first step is to prove that the problem is solvable, then work on the solution :)

    rr

  • by kyz (225372) on Tuesday February 20, 2001 @03:20AM (#418489) Homepage
    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.
  • by LinuxParanoid (64467) on Tuesday February 20, 2001 @04:16AM (#418490) Homepage Journal
    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
  • by Tom7 (102298) on Tuesday February 20, 2001 @05:11AM (#418491) Homepage Journal
    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!
  • by CaptainZapp (182233) on Tuesday February 20, 2001 @03:24AM (#418492) Homepage
    Acording to Bruce Schneier it is impossible to prove the unbreakability of a cryptographic algorithm.
    The best you can do is to state I am not able to break it and then let the crypto community rip it appart.

    This seems a fairly reasonable assessment in my book.

    A security product claiming that it's unbreakable has the same credibility es "GET RICH NOW!" e-mail subjects or time share salesmen.

    I'm not claiming that the good prof is a phony. But I sure as hell wouldn't trust a new crypto scheme just because the NYT reports about it.

  • by Anonymous Coward on Tuesday February 20, 2001 @06:08AM (#418493)
    Schneier wrote Applied Cryptography, developed Twofish and Blowfish, and has developed a number of protocols that are very useful and (assuming the software implementing them is good) secure.

    But when he published McGuffin, an unbalanced Feistel cipher, somebody had the hubris to attack the system!

    And they broke the goddamn thing. To pieces.

    The fact of the matter is, even the best guys make mistakes. Andrew Wiles is one of the world's leading eliptic curve specialists-- he still made a mistake (slight as it may have been) in his proof of the Taniyama-Shimura conjecture. Sarah Flannery (16-year-old Irish cryptographer girl) had a proof that the Cayley-Purser algorithm that she developed was as hard to break as RSA-- it's completely insecure.

    Are all of us at the level of Rabin? No. But that doesn't mean that we can't at least state what obstacles he has to overcome, and why there might be difficulties.

    Skepticism, not hubris, is part of the Slashdot culture. If you want to blame somebody, blame the editors that have made it that way (Rob, Jeff: I'm kidding, of course...).

  • by tjansen (2845) on Tuesday February 20, 2001 @03:34AM (#418494) Homepage
    This system can only work when you can be sure that the one-time-pad so large that the intruder cannot save it fast enough and the key stream(=one-time-pad) is truly random and not pseudo-random. As there is no 100% secure way to guarantee that you get the right stream, unless you do it yourself, this means that the sender of the message must send this infinite stream. So this is really unpracticable for most normal persons, but could be used by goverments..


    The ugly part would be that a government agency could send such a pseudo-random key stream for public use, so that no one can decrypt the message except those who know how the pseudo-random stream works.

  • by Chris Burke (6130) on Tuesday February 20, 2001 @03:49AM (#418495) Homepage
    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.
  • by KFury (19522) on Tuesday February 20, 2001 @04:02AM (#418496) Homepage
    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
    --
  • 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

  • by ZanshinWedge (193324) on Tuesday February 20, 2001 @05:36AM (#418498)
    Actually, one time pad crypto systems are provably secure. As you said, the main way to crack them is to hammer at the supposedly random pad generation, or to attack the physical security of the pad (which, btw, has nothing to do with the cryptosystem by itself, if you obtain any key, you'll be able to crack any code). Take a look at hotbits [fourmilab.ch], it's a source of true random numbers generated from timing radioctive decays inside a nuclear reactor.

    However, the main disadvantage of any one time pad based system (despite it's great cryptographic strength) is that the key (or pad) requires itself some amount of physical security. In contrast a system like RSA is much different because it is not even remotely symmetrical (encryption vs. decryption) and you can send out your public key for all to see and to use but still only you (with your private key) can decrypt what has been encrypted with the public key.

    Personally, I don't see this new development as anything special, we already have methods of using extremely high security encryption where it's needed (spying and whatnot) and for other applications that require more convenience and can have more cpu power put behind them the systems we have now are really more than adequate (assuming your using the right systems, not all the systems in use now are cryptographically secure in any resonable sense, but we know which ones those are).

Never try to teach a pig to sing. It wastes your time and annoys the pig. -- Lazarus Long, "Time Enough for Love"

Working...