Slashdot Mirror
One-Time Pad Encryption With No Pad?
thepooleboy writes: "The Globe and Mail has an article about a Toronto area company that has perfected 'Unbreakable Encryption' using the Vernam Cipher." The idea is to use as a one-time pad a large number generated by equations sent with an initial (proprietary) exchange which takes place when users connect to an equipped server. Since real one-time pads' numbers are by definition random and known in advance to both sender and receiver, though, the company seems to be playing fast-and-loose with their terms.
Depending on their "generator" function, they might have a decent cryptosystem or they might not, but IT IS NOT A ONE-TIME PAD by definition. Symmetric cyphers that aren't one-time pads can ALL be called "one-time pads" under that bogus definition, since generating a long sequence of random numbers to apply to the plaintext is pretty much what a cypher does.
And here I was just reminiscing fondly about ZeoSync the other day, when another scam pops up!
I read this right after the September Eleventh attacks on the WTC.
Thankfully, Google remembered exactly where the original article was at.
http://www.aspheute.com/english/20010924.asp
---
Partner Linux Site
An algorithmically generated sequence of pseudo-random numbers is not a one time pad. They are misusing the term "Vernam Cipher" in the description of their product. Vernam/One Time Pads require truely randomly generated data, not a sequence you can determine with a small seed value.
- AlanH
Um, no. A one-time-pad is unbreakable. The idea is that you have a purely random set of bits (the one-time-pad) the same length as the data you want to encrypt. If you decrypt it using every possible one-time-pad you just end up with every possible message of the same length. If your message is "Attack at dawn.", with the wrong key you could decrypt it as "Retreat ASAP !!"
The problems are the "random" bit and distributing the pad from the sender to the recipient.
These guys appear to have a pseudo-random key generation algorithm, which by defintion isn't random at all.
finding their website was non trivial on google
its here
http://www.prescient.net/
Actually, no. A one-time pad really is unbreakable if properly applied. One way of looking at it is that since the one-time pad is random and was not generated by algorithmic means, no algorithm can break it. Crypto folks use different terminology, but the result is the same: unless you compromise the pad itself, no decryption can do better than random chance.
These results are well established, and any decent text on information theory will fill in the details.
An interesting side-effect of this came up with some U.S. decrypts of Soviet espionage activity in the 1950s, which were decrypted when agents misused their one-time pads. The authorities didn't take any action, partly because they were concerned about proving in court that the decrypts were accurate...
...laura
One must assume that 'God' (Commonly defined as an all-knowing being) is capable of breaking one-time pad encryption systems.
I am not aware of any research into the creation of cryptosystems designed to resist compromise by supernatural forces, much less any system that can resist an attack by an omniscient, omnipresent, omnipowerful opponent.
I do not deploy Linux. Ever.
This system is using a pseudo-random number generation algorithm, albeit a changeable one, which means that with a very small amount of data it is possible to completely predict the entire key stream. That means that the "amount of information" really contained in that stream is very small, since a small algorithm completely defines it.
This is what one of the other posters was referring to as "key space". How much information must be guessed in order to decode the message?
For these snake-oil vendors, the amount of information that needs to be guessed to decode a message is only as big as the pseudo-random algorithm (or likely smaller, since these guys obviously don't know what they're doing). If you crack the beginning of a message, you've cracked the whole message no matter how large.
For a real one-time pad though, the amount of information which must be guessed is as big as the entire message. No matter how much of the message you "crack", you'll have no more advantage to cracking the rest than you did before. Each element is random. There is no "method" to predict random numbers and so there is no way to crack a true one-time pad.
"Anyone who considers arithmetical methods of producing random numbers is, of course, in a state of sin."
-John Von Neumann
This latest 'unbreakable encryption' and 'generated one type pad' crap is the same as all the rest. Please don't try to defend it. I predict it will be featured in the 'Snake Oil' segment of Bruce Schniers (sic?) next monthly mailing.
No, actually, a true Vernam cipher really is unbreakable. Check out the description of it in Bruce Schneier's "Applied Cryptography". The 'one-time pad' that was mentioned is a string of random numbers as long as the message that you want to send that is XORed with the message. Since XORing is a symmetric process (do it twice and you get back your original message), if you've got the random pad you can decrypt it easily.
That being said, the process they described in the article is not a Vernam cipher. It sounds like a variation on the Kerberos protocol, where the client and server machines exchange encrypted session keys.
There are also problems with the design, if you ask me. It looks like they are using the client computer to generate "random" numbers, which is a definite no-no. It also says that the keys are exchanged "through a secure process known only to Prescient". Sorry, but unless they have some sort of review by an independent party that proves it's
secure, it's an empty claim. Basically, this sounds like a lot of PR-hype that won't hold up to its promises.
cotodoso
Because both the sender and receiver must generate the same sequence of keys. If it were random, then receiver wouldn't be able to decrypt the message.
It could be that the "program" that is sent initially that generates the keys is different for each user. This would make it slightly more secure, but if that "program" were intercepted then every single key it generates would be compromised. It would also be vulerable if the program which generates the program which generates the keys was in any way predictable.
"Don't blame me, I voted for Kodos!"
This product certainly sounds like snake oil (does "a secure process known only to Prescient" inspire any trust?). However one-time pads could become practical using Quantum Key Distributions (mentioned in an earler /. story). QKD is a method of transmitting data in such a way that it is possible to determine whether the data has been intercepted (using the Uncertainty Principle) - if the key has been intercepted, simply throw it away and pick a new one.
AFAIK the problem with QKD at present (apart from distance) is that it is very slow; it's good for public key systems that only need a few hundred or thousand bits, but with a one-time pad cipher your key has to be the same length as the message.
Given infinite time, a monkey will eventually bang out the contents of the OTP.
Sure. The question is: How will you know it when you see it?
The monkey will bang out every possible n-bit sequence. Applying them all to the n-bit encrypted message will give you every possible n-bit message. So you'll get all of the following:
So, how, exactly, will you know when you've found *the* message?
That's why an OTP is provably unbreakable. Because every pad is equiprobable. And that's why no algorithmically-generated pseudo-random sequence can be used for a one-time pad.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
Ummmm... comparing asymmetric encryption to symmetric encryption (of which a one-time pad is a subset) with key-lengths is like comparing apples to oranges.
This much is right.
In asymmetric encryption, your security is in your keyspace... every bit doubles the time to search the keyspace.
This much is nowhere near right. According to our best estimates at the present time, it'll take on the order of 2**80 operations to factor out RSA-1024. It'll take on the order of 2**128 operations to factor out RSA-3072.
Adding two thousand bits doesn't increase the difficulty by 2**2048... only 2**48. Asymmetric crypto does not double in difficulty with each added bit.
In symmetric encryption, security is all about the keys; symmetric encryption is so easy to do that you can try millions of keys a second, as opposed to thousands or hundreds, so you HAVE to have a big keyspace.
This is not correct. In fact, it's downright astonishingly wrong. The problem is you're assuming symmetric and conventional, non-ECC asymmetric keyspaces are both flat (they're not). But if they were flat, then asymmetric crypto would have a keyspace multiple orders of magnitude larger. Which is the opposite of what you're asserting here.
Conventional, non-ECC asymmetric keys are so huge because most of the keys are weak. Let's compare DES to RSA. Is 0xFA810DD0 a legitimate 64-bit DES key? Yes. (Note: DES only uses 56 of those bits for key material; the other 8 are used for parity.) Is 0xFA810DD0 a legitimate 64-bit RSA key? No. Why? Because 0xFA810DD0 is an even number, which makes it much, much easier to factor.
Conventional, non-ECC asymmetric keyspaces are so huge partially (not exclusively) because most of the keys in that keyspace are unusable. Symmetric keyspaces are so small partially (not exclusively) because most of the keys in that keyspace are usable.
A keyspace in which all (or the overwhelming majority of) keys possess equal strength is called a "flat" keyspace. A keyspace in which some keys are stronger or weaker is... well, non-flat.
But, most symmetric encryption algorithms allow you to get it partly right; if the key is partly right, you get a partly decoded message, so the search algorithm is linear instead of exponential.
This is so wrong that it staggers the imagination. Claude Shannon established some principles back in the 1940s which still guide cipher development today. One of these is called the avalanche effect. The idea behind the avalanche effect is that a single one-bit error, anywhere in the enciphering/deciphering process, will affect the output of half the bits in the entire e/d process.
Go ahead. Use Blowfish with a 40-bit key. (There are lots of Blowfish implementations out there; if you want one, email me and I'll send you one.) Encrypt it with one 40-bit key, and then decrypt it with a key that's only one bit different. You'll get absolute, total, gibberish. You'll get gibberish because Blowfish is a well-designed cipher and avalanches properly.
But wait--it gets even worse. Only a chump runs a cipher in electronic codebook mode. Usually, ciphers are run in a block-chaining mode, where every subsequent block gets XORed with the prior block. So if you have a one-bit error in your process, that will affect half the bits of the block... which then create errors in half the bits of the next block... which avalanche... which propagate their error forwards, on and on and on... etcetera.
You get the idea.
(All of the above information can be found in either Bruce Schneier's Applied Cryptography, 2nd Ed or Menezes, Oorschot and Vanstone's Handbook of Applied Cryptography.)
This is not a one time pad. A really secure one time pad has the following properties:
1) It is never transmitted in the clear, shrouded or not. (The fact that this thing transmits a program which builds the key, just means that cracking it will boil down to building a virtual machine to execute the given program. Just reverse engineer the virtual machine that performs the execution on the client side.)
2) A one-time pad must be as long as the message (and be a cryptographically soundly generated random number -- no computer language in existence implements a cryptographically secure pseduo-random number generator.) In many cases 10K is way too small. RSA keys of 128bits or so don't have the same cryptographic properties as a one-time pad -- comparing the security by comparing the bit lengths is inappropriate (OTPs have to be arbitrarily long.)
--
OTPs must be used at most once. So this is not practical in usual circumstances, since a new key must be transmitted along with every message anyway. Thing like AES is far more efficient since only one (much smaller) key is required, and can be safely used for arbitrarily long messages.
Other problems -- this also doesn't deal with server interloping.
I really think this is some serious snake oil.
I remember the session on cryptography blunders at LISA last year. Two of the major blunders they listed were calling something unbreakable, and using a one time pad more than once. In addition to the problem you point out, from the description it sounds like they are using the pad more than once. If they client generates a key, uses it to encrypt data, sends it to the server, then the server uses it to encrypt data and send it back, it's not a one time pad. It's being used at least twice to encrypt and send data, which makes this much less secure.
Plus the fact that they are claiming it is unbreakable immediately puts it off my list
BZZT, wrong, but thanks for playing.
You're making the same mistake that Precident made: the belief that any mathematical function can generate a random series of bits. The best you can do is pseudo-random. And using pseudo-random and thinking you've got an OTP is a very, very bad thing.
I don't care if you're using a satellite to create a convolution matrix, you're still using a mathematical function to generate the bits.
The satellite idea is based, pretty much, on the theory that "nobody can store all those bits for analysis". I won't discuss the practical merits of that, since /. already has. But it gives you no theoretical gain. You're stil l trying to call the output of a PRNG an OTP, and that just ain't so.