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.
Otherwise known as the encryption key? That's hardly a one-time-pad.
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
Actually, a correctly used one-time pad is unbreakable. The true randomness of the pad cannot be calculated, and if it's never reused, you have no clues as to how to calculate the encryption.
However, this scheme isn't a one-time pad. It's a function, with parameters encrypted with a standard encryption algorithm. If you break the algorithm used to exchange the parameters, you've broken the whole code. It's certainly no better than anything else out there.
Attempts to get around the fundamental limits of data encryption (and data compression, and a lot of other software fundamentals) remind me of all the pointless efforts to build a Perpetual Motion Machine. "Yeah, the smart guys say energy is "conserved", but anybody with any common sense can see if you just tweak this gearbox this way..."
I will use the secret powers of generating reproducable one-time pads to solve the equally overstated Bodacian challenge!
The world will be all mine, Pinky!
They have a program which generates new keys for each subsequent transaction, and they claim that this counts as a "one-time pad".
Nonsense -- a one-time pad is only secure because there is provably no way to figure out the keys without a copy of the codebook (assuming they were generated through appropriate random means).
As long as a program is producing the keys, they will exist in a particular sequence. All you need to do is figure out at which point in the random sequence you are, and then you can generate the rest of the sequence easily, allowing you to eavedrop on the conversation.
Admittedly, the article was fluff, but key-hopping doesn't significantly increase the difficulty of breaking encryption. Unless there is something else behind this that I'm missing, this is another "Compress random data by 99%! For real this time!"
ZFS: because love is never having to say fsck
So essentially they send the keys to the unbreakable cipher using a breakable cipher, sounds completely secure to me.
Cryptographically secure hash functions like SHA or MD-5 are often used to convert shorter, shared numbers (the key) into a long bit stream that can be xor'ed with the file in much the same way as a one-time pad. This is done all of the time.
Let k be your key. Let b1, b2, b3 be blocks of bits. Take as many as you need to encrypt the file:
b1=SHA(key)
b2=SHA(snip(b1)+key)
b3=SHA(snip(
etc....
In fact, you can use any encryption function instead of SHA with a few tweaks.
The Germans were using a variation on this in Cryptonomicon. The idea is that given an initial seed, you can generate a "key of the day" that appears random. In this case they're using an initial seed to generate a whole one-time pad.
However, it isn't secure. If you know the algorithm, you only(!) have to search the keyspace of the initial seed.
--
E_NOSIG
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/
no, a vernam cipher is the only form of unbreakable encryption. It happens like this: you have a stream of extremely random bits. And you have to make sure they are really really random, no pseudo random number generators. Say it's coming from a satelite up in space that measures radioactive particles(this was proposed in a paper not too long ago). Now the satellite streams these bits down to earth, so anybody can access them. Alice and Bob want to communicate securely over an insecure channel. So the agree on a series of bits to encrypt with. This can be anything from "every other bit" to a large polynomial function that says which bits to use. So every bit the function designates as an encrypted bit is used to XOR any message Alice and Bob use to communitacte. So, Alice computes bit random bit number x to encrypt bit y. She does XOR(x,y)->c and sends it to Bob. Bob also has this formula and performs the calculation to find which bit number x to use, then performs XOR(c,x)->y. The key is keeping the bit number function secret. Now, why is this secure? because anybody listening on the channel doesn't know the function(hopefully) and if your bits are truely random there is *no* way to distinguish whether any given bit can be 0 or 1. Try all the combinations for 0 or 1 in the message you want, but every permutation you want will look like the correct decryption.
- "Never let a computer tell me shit." - DelTron Zero
From the article:
Once the server is set up with E2Sec, anyone who logs on through a Web browser or Internet link will automatically be given an encrypted connection. A small 4- to 10-kilobit file, a bit like a Web cookie, is loaded into the client computer's memory. The file contains a program to generate random encryption keys, so that the keys themselves don't have to be sent over the network connection. The program is so tiny that even the low-powered processors in a cellphone can run it with ease, Mr. Kassam said.
This is really unbreakable. Unless you happen to intercept this program. Which wouldn't be that hard, and it may in fact be the same program for every client. And, they're touting this for wireless communications.
I found this next part interesting:
The client generates a series of random numbers to use as an encryption key. This is number is exchanged with the server through a secure process known only to Prescient, the server uses it to encrypt any information it sends back to the client, and then the key is destroyed and a new one is created. This process is repeated every time information is exchanged between the client and the server, making it virtually impossible for outsiders to decrypt the information.
It's a well established fact that non-open, secure processes are not secure. Cryptography is difficult, folks. The only way to even come close to proving that a particular process is secure is by exposing it to the scrutiny of the entire global community. Even then, its a case of proving that something is NOT true, which in this case involves incredibly complex mathematics that don't work for half of the proposed protocols out there; for instance, for a particular protocol to be 'provably' secure, it has to be time reversible (that is, if you apply any one step in reverse, the encryption key and cipher text each go back to their state before that step)
"We're 100-per-cent confident in our technology," Mr. Kassam said. "To give an idea of how difficult this is to crack, many organizations consider 128-bit encryption, which has a [cryptography level] of two to the power of 128, to be very secure. With e2Sec, we're talking about encryption in excess of 5,000 bits, and as much as two to the power of 10,000."
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. In asymmetric encryption, your security is in your keyspace... every bit doubles the time to search the keyspace. 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. 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.
I am disrespectful to dirt! Can you see that I am serious?!
Actually a one time pad is mathematically proven to be secure. The biggest problem is that a protocol using it is much tougher to find.
A one time pad is completely random therefor you could take any message, "Bob had a car" and it could decrypt to ANY message of the same length, given the right pad. The biggest problem with a true one-time pad is that as the name implies it can only be used once, and needs to be the same size as the message its encrypting.
The best practical example of one-time pads is probably the hotline between washington and moscow. The crypto course I took explained that a very very large random one time pad was created to encode the message, and new pads are periodically created and taken by curier to each site. I believe a similar method is also used for transmitting launch codes to Nuke site.
Then again its been over a year, and my memory of the course is a little fuzzy.
Note to author: If you are not in the know, don't write as if you are.
First off, the OTP is completely 100% unbreakable [in theory]. Even with infinite time an OTP is unbreakable.
No symmetric key system, even a really super-duper one can get that type of security. I mean sure, you could make it require 2^1000 time, but that isn't unbreakable. That is "not likely to be breakable", a strong difference.
Second, this is not the first company todo so. In fact the sci.crypt snake oil journal is full of similar companies. Any company that cites "unbreakable" and "OTP" when talking about their inhouse crypto is very suspect. Real credible companies don't play on such naive terms. RSA for example will play on the reliability of the code more than they will about the breakability of their ciphers they use [e.g. RC5/DES/AES]
Third, if it is not a OTP then its not a OTP. These "OTP-like" and "pseudo-OTP" phrases you read here and there are meaningless. Either its an OTP or it isn't. There is no half-way inbetween.
Fourth, as I read it you download a program that generates a stream? This is nothing new. What the heck do they think a stream cipher is [re: a block cipher in CTR mode is a good candidate]. What they don't say is if you make a 1000-bit pad with a stream cipher you're not supposed to think of that as a 1000-bit key for a message as in you have 1000 bits of entropy. If you use a 64-bit key to seed a cipher to make 1000-bits for a 1000-bit message than the key is still only 64-bits and you just stretched the entropy over 1000-bits.
e.g.
Entropy In >= Entropy Out
Fifth, everyone please laugh at the shameful cloakware people. Shameful! www.cloakware.com, they are an even bigger canadian joke.
Tom
Someday, I'll have a real sig.
..."unsinkable" is to "ship"
I have two things to say:
1024 bit, while not unbreakable, is still unbreakable in the lifetime of the universe. I have no doubt methodologies and processes will be developped in the future that will change this, but as of right now, for all intents and purposes, it's unbreakable
Secondly, many parts of quantum mechanical behaviour *are* random, especially at macroscopic scales. For example, when a particular radioactive isotope chooses to decay is completely random; I've seen military random number generators that depend on this or similar effects to create truly random number.
But, no purely software random number generator will ever even come close to approaching randomness.
I am disrespectful to dirt! Can you see that I am serious?!
decipher this:
kjashduyqwhasklasj
Underneeth each letter I put the row of the keyboard that the key belongs to.
kjashduyqwhasklasj
222222111122222222
Thus usuing me l33t 5kilz - I have determined that your keyboard is missing its entire thrid row of keys.
Moneyed corporations, non-working 'poor' and criminal prisoners are turning productive citizens into tax-slaves.
So the program is transmitted through breakable encryption.
So the keys are generated using a pseudo-random number generator, which makes them quite guessable.
Then the key is transmitted over the network via breakable encryption, which they just said they wouldn't have to do.
Working OTP encryption requires the random numbers to be truely random, a computer programm can't do that. You need a source of randomness in the computer like the user or a special hardware random generator. The user isn't a solution for random numbers for OTP because you need a lot of random numbers and the user will have to type or move his mouse for a very long time until he has produced enough random numbers for a OTP encryption of a short file.
Here the real problem of it. OTP encryption is only secure if no one can get his hand on the One Time Pad. If the OTP is transmitted over the internet, someone could easily get the OTP. If it is transmitted using a "secure process". The encryption is only as save as this "secure process". If this process is breakable, the whole encryption is breakable.
The "secure process" is also only known to Prescient. Everyone knows that "Security through Obscurity" doesn't work.
Jan
until your explanation, it was, in fact, not funny.
The Kruger Dunning explains most post on
"It's not a war on drugs, it's a war on personal freedom. Keep that in mind at all times." Bill Hicks
Dear Slashdot editors: A one-time pad is provably unbreakable provided you meet the very strict, precise definitions for what a one-time pad is.
Once you make the slightest change, it's no longer a "one-time pad", it's "a new unproven proprietary crypto system." There are NO exceptions to this rule. Any time you post a story that says, "Company X has a one-time pad system that is different than other one-time systems", they don't really have a one-time pad system, and you're just promoting their snake-oil for them. The OTP unbreakability is a mathematical proof, and you can't change the axioms and just claim the proof still holds!
Seriously, NO exceptions. Don't be tempted by their fancy footwork and wiley ways; they're trying to fool you
Can a company come up with a new cryptosystem that's cool? Yes, but they'll have to do a lot of hard work to prove it. This doesn't meet that standard.
The company is flat out lying. Or incompetent. They are *NOT* using one-time-pads, and they are *NOT* using a Vernam Cipher. If they were, then yes, it would be unbreakable encryption. But they aren't. They are generating a sequence of psudo-random numbers. Just like any streaming cypher. Generating a list of numbers and calling it a "pad" does not make a bit of difference.
Either (A) they do not understand cryptography, or (B) they are intenionally lying about their cryptography. Either case is a good reason not to trust their cryptography.
-
- - You can't take something off the Internet! That's like trying to take pee out of a swimming pool.
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.)
All computer programs in slot machines and such are submitted (source, *source*) to some state agency, who examine the code to make sure it has no backdoors. One enterprising examiner noriced that a certain blackjack game did not reinitialize its random seed. He copied the random number generator code to his laptop, sat in a bar with a cell phone listening to his buddy report what cards came up, and within a short time knew what to play to win.
Both went to prison, as I heard it.
Infuriate left and right
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
Doesn't matter, it's STILL 100% secure (again assuming the pad is truly random). The thing is you just DON'T KNOW what it is that I'm trying to say in the message. Even if you can guess, it doesn't help you. You don't know what is plausable or not ebcause you don't know what I'm trying to say. IF you did, you wouldn't need it decrypted. Even if you have a general idea, it doesn't buy you anything. Suppose you know I'm going to tell the guy on teh other end to meet me at certian coordiantes. Fine, you don't know how I chose to phrase that, so you have nowhere to start in the decoding. However for argument's sake say you even know the exact for of teh message. You know I will write it like this:
"I will meet you at the folowing location: XXX XX by XXX XX" where the Xs are the degrees and minutes of the two coridnates. Still buys you nothing, you can decode those into any combination of cordinates you want and yuo have no way of knowing which one is correct.
The problem is with a one time pad, like the orignal poster indicated, literally ANYTHING within that space is possable and since it is truly random (if done right) you just can't know when you have the right answer. You might decode something that you belive to be perfectly correct, it looks totally plausable, and still be dead wrong. You'd do just as well guessing at random with messages the same length as the encrypted document.
Further, you have no way of knowing or being able to tell if what I send was in the form you expected. Maybe it's all BinHExed, maybe it's gziped, maybe it's ROT-15'd. You just can't know.
If you want to try it I'd be happy to generate you a message encrypted with a one time pad and you can try to crack it. I'll even be generous and tell you the prices format it's in and tell you what the topic is. You'll still never crack it, and that's more information than you'd normally have when dealing with a message so encrypted.
And I didn't bother pointing out that because these folks have no clue what a mathematical proof is, they didn't bother showing how their system preserves the properties of a OTP algorithm.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks