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.
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..."
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.
My 26,740 Turkish Lira,
~ravyn
___
I'm an exhibit on the mounted animal nature trail.
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
Actually, it is possible to make unbreakable encription. At least in terms of text
Step 1: Generate a rather lengthy list of non repeating, as random as possible numbers.
Step 2: take the list and asign the letters of the alphabet in order along the list, (eg numbers in places 1 - 26 are assigned letters A - Z then 27 - 56 A - Z again.. and so on.)
Step 3: Make a duplicate of said list.
All communications are done with this code, using the numbers to represent letters, starting from the top, and use the number assigned to the fist instance of the letter, and proceed down the list for each use of the letter. (eg the first a would be the number in place 1, the second a would be the number in place 27)
As there's no pattren to it, it can't be broken. However, such a thing is so cumbersom to use, plus, there's the factor of how to get the list to the other party... Not a new idea, or even close to my own... read it in a book.
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?!
Lighten up. It's a story. I agree that it's a load of shit but that is why it was probably posted.
Your Lord, Jebus Christ
You have to read a 600 page book
http://www.cryptonomicon.com IMNSHO the best funniest geekiest book ever written. Basically during the WW2 part of the book they are using one time pads and one of the ways they are producing the random numbers is by having a Vicar's wife pull balls out of a bingo machine. Well she starts to peek and then the numbers are not quite random and so a German is able to crack their one time pads.
Cypherpunks: Civil Liberty Through Complex Mathematics. Those who live by the sword die by the arrow.
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.
You are naive. You really should read David Kahn's Codebreakers book, or at least the first several chapters.
A one time pad is unbreakable. What this means is that if you have the encrypted message, and all keys are equally likely, there is no information that can possibly be gleaned from it -- all possible un-encrypted messages (of that length) are equally likely. You can hypothesize that the message is "Osama - be sure to wear the black lacy stuff when we meet at four to masturbate while talking about blowing up Americans!" and there is a key which would decode it that way, but there is no reason to believe it any more than any other message.
The scheme the article suggests is snake oil because not all keys are equally likely (among other faults). You can only have as many keys as there are seeds to this super-duper equation deal. Not to mention that this scheme like all one time pads is only as strong as the system used to distribute keys, which in this case seems to happen over the same channel as the encrypted message.
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 "book" method cannot be cracked by intercepting the message, true. How to solve this method? Steal the book. As has been pointed out in several previous stories of this genre, encoded data at some point has to be decoded and that makes it vulnerable.
The client generates a series of random numbers to use as an encryption key.
There's no such thing as a truely random number. There will be a way, no matter how difficult, to predict pseudorandom numbers. Especially if you've got a copy of the random number charts already. (Perhaps stolen the book?)
Exceptionally difficult to break, this encryption may be. But it is not unbreakable.
What's in a Sig?
Eh, except that some encryption is unbreakable. See HardEncrypt, for example.
Every once in a while I like to masturbate a new word into my vocabulary, even if I don't know what it means.
That paper puts things in a completely different light. There is no mention of "one time" pads in there, instead they're claiming that they have a way to encrypt that "is not structured and uses no algorihtms", and therefore can't be reversed. The question then becomes, what the Hell is it?
They discuss pseudocode randomly chosen from "millions" (which would be, what, 20 bits?) of possible choices. "External factors" are then mixed in so one message gets multiple outputs. That seems to be it, basically.
It seems to me that they're relying on the unique version of their "non-deterministic" code for the security. This is security through obscurity in its most basic form. Without more information on this wondrous core engine, I cannot say any more.
No - Counter intuitive as it may seem, picking a pseudo random function at random to generate random numbers is only as secure as picking a random seed for *a* defined pseudorandom function and generating random numbers. This and more fascinating crypto stuff in "Foundations of Cryptography" - Some portions of it are also accessible here http://theory.lcs.mit.edu/~oded/ln89.html .
-Dracken
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