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.
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
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/
"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.
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!"
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.)
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