Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I have just read about the perfect security of an OTP encryption and what came to my mind was that what if the Pad used for encryption/decryption did not have to be transported separately from the message, but instead together with it?

And what if it was computed using an algorithm from the message itself (from all the characters in an 1:1 way so that it had the same size) providing a random-looking pad for encrypting the message, and after encrypting the message would be stored in an interwoven way in the message itself, expanding the file size by a factor of 2. The encrypted file itself would have double size of the original one but no-one would be able to find out what is the message and what is the key since it would be interwoven using a secret algorithm, perhaps the same one as was used for generating the pad.

Would this be a good encryption comparable to real OTP with the pad transferred and generated separately? Did I just invent the wheel, or is this a breakthrough thing (I mean storing the pad inside the file in a secret way preventing others to extract it)?

I know calculating the pad from the message itself would perhaps break the real randomness so this could be avoided and the pad simply taken from a real random key number generator.

share|improve this question
    
What "secret algorithm" would you use to interleave the pad with the ciphertext? What entropy source would it use, where would you store the key? Would it still be unconditionally secure? Your scheme is far too vague at the moment, and to be fair, I think it's safe to say you invented a broken wheel for now. Could you detail some of the aspects of the algorithm, such as how would you mix the pad into the ciphertext, and how would the encryption/decryption work? Then we'll be able to say something. –  Thomas Oct 29 '12 at 8:08
    
Any combination of mathematical functions would work, like sinus, log, etc. The user would just enter some formula for every message/file to be encrypted using an OTP which would be buried inside the file using this one-time function. The final file would be double size of the original since it would include the OTP, too (with the same size as the encrypted content). Encryption would be standard XOR, as used in standard OTP. –  Lubo Oct 30 '12 at 6:01
    
Those functions are defined on reals. How do you plan to restrict them to integers (e.g. bit, or byte, whatever positions to interleave)? Floor function? And can you estimate the entropy of any one formula? (hint: it is quite hard and the overall entropy is quite low because, precisely, the functions are continuous and smooth) –  Thomas Oct 30 '12 at 6:34
    
Hint: you can roughly estimate the entropy of the function by considering every possible "interleaved pad" configuration, and seeing how many of these are reachable by the function over its parameters. You can immediately see that for a simple sine wave, almost every configuration will be unreachable, thus the entropy is extremely low and thus the pad is easily recovered. Also note the difficulty of such an analysis in the general case, compared with the relatively straightforward proof of "standard" OTP. –  Thomas Oct 30 '12 at 6:40
    
You may want to consider reading Bruce Schneier's Memo to the Amateur Cipher Designer. –  Stephen Touset Oct 30 '12 at 6:53
add comment

4 Answers

What you're proposing is an algorithm, which is very much not a one-time pad. This is frequently a source of confusion. People have even sold commercial "one-time-pad encryption" software based on this flawed idea.

In cryptography, a one-time pad has a very specific meaning. Each byte/character/whatever of plaintext is individually modified by a corresponding byte of key material such that each byte has an equal possibility of having any possible value in its range. Each byte of the key material must be completely random, meaning the value of one key byte is not dependent on any of the previous or following key bytes or message bytes. (Interpreting this last requirement means the key material must never be reused, even for a different message.) That's the entirety of a one-time pad.

Historically the modification function was a simple alphabetic substitution cipher. Each character of the plaintext was added to its key letter, and deciphering subtracted each key letter from the corresponding letter of the ciphertext. Digital implementations of OTPs use XOR for both operations because it's invertible - the same operation works for both encryption and decryption. But in both cases, the algorithm is extremely simple. All security resides solely in the key.

A OTP is secure only because the key material bytes don't relate to each other. If the bytes are related in any way, the attacker might be able to figure out the relationship. For example, if you use a code phrase instead of random letters for the key, an attacker can try different phrases, and when he stumbles upon "WHENINTHECOURSEOF" he might expect the next letters to be "HUMANEVENTS". See how the relationship makes them guessable?

The randomness has to be truly random. The output of the C rand() function is not random - if you run it three times, each time starting with the same seed, you get the same numbers out three times. Computers are deterministic state machines, and as such are horrible sources of randomness. Attackers and cryptanalysts already know this from several well publicized flaws. That's why we argue endlessly about what constitutes a "cryptographically secure random number generator", "true entropy sources", and the like.

Similarly, if you come up with your own "random" algorithm like "add one to the first letter, subtract two from the next, add three to the third, etc.," the attacker might spot the pattern and try subtracting four from the fourth.

You might get slightly more clever, and say "I'll keep these numbers +1, -2, +3, -4 secret, and only tell them to my friend who is decrypting them." Your solution is now exactly a secret key algorithm (albeit an unproven one).

These are all deliberately simple examples. I'm sure you can think of a "pattern" that you're sure we could not guess, and I'd equally promise we probably wouldn't try too hard. The reason is that it's not a OTP, it's an algorithm, and it's likely not worth the trouble. These have been proposed hundreds of times before, and all are built on the same misconceptions.

share|improve this answer
add comment

There have been a few designs along this idea (transmitting the pad together with the message), see for instance Diffie's cipher and the likes. The problem with these designs is that the secret key can only be used once as (for instance) a simple known plaintext attack would reveal it, so that it does not fulfill the highest requirements in terms of security of an encryption scheme.

As other have pointed out, the alternative you suggest, that is keeping the details of the extraction from the information sent, is something cryptographers avoid. Additionally, it likely won't meet the requirements in terms of security of an encryption scheme (I foresee that chosen paintext attacks would allow the reconstruction of the underlying allegedly secret scheme).

share|improve this answer
add comment

Your "secret algorithm" is now effectively the key.

If the algorithm stays fixed for all messages, you now no longer have a one-time pad. So let's make your algorithm be tweakable by, say, accepting as input a string that describes its exact operation. Now we have the benefit of being able to publicize the "secret algorithm", since the actual secret details are contained in this input string. Except now that input string is the key, and now you have to find a way to transmit it... which is the problem you were trying to solve in the first place.

share|improve this answer
2  
And if the "secret algorithm" is shorter than the message, then you no longer have a One Time Pad. If the "secret algorithm" is longer than the message, then why not use a plain OTP? –  rossum Oct 29 '12 at 21:06
    
The perfectly random OTP would be buried in the message, the algorithm to bury it in there would change with every message (the user would input it) and as such would be much shorter that the OTP (which will be exactly same size as the message) so much easier to transfer securely (one could just tell someone else and he would just remember the function in his/her memory) –  Lubo Oct 30 '12 at 5:58
    
<code></code> does not work, I would insert a code sample. –  Lubo Oct 30 '12 at 6:11
1  
As I said in my answer, now that input is actually the key. And since it's shorter (by your own words), it is by definition no longer a one-time pad, nor does it any longer provide perfect secrecy. –  Stephen Touset Oct 30 '12 at 6:49
add comment

Security by obscurity ( your security algorithm to compute the pad from the message itself) will not be secure for longer time .

Through the ages what worked in cryptography is , Making the algorithm (i.e the crypto system ) public and just keeping the key secret Kerckhoff's principle .

share|improve this answer
    
The "secret algorithm" to interleave the pad with the ciphertext would be entered by the user (e.g. 25*$i*sin($i)/124) and would serve as the only password in this case. Let's forget about the computing of the pad from the message itself, and suppose it would come from a real RNG. Would this be secure enough (i.e. interleaving the pad using a secret function withing the source previously encrypted with the same function)? How could someone guess what is the encrypted content and what is the pad then? –  Lubo Oct 29 '12 at 11:04
    
That would not be tough using cryptanalytic techniques, its dangerous assumption that no body might understand your secure function –  sashank Oct 29 '12 at 12:05
    
Is it really possible to separate the truly random pad from the encrypted content by some cryptanalytic technique? I can not imagine how could this work in case the interleaving function is fairly complicated, or even if it is simple since the text is already encrypted by truly random pad and the pad is random, too. Interleaving them together further increases the randomness of the whole data. –  Lubo Oct 29 '12 at 14:53
    
I did it in Perl, the basic idea is this:i=i=filesize-1;while(i>=0) {i>=0) { iPos=int(i∗sin(eval(i * sin(eval(sEncFunc))); sKeyFragment=substrsKeyFragment = substr sDataFromFileTemp, iPos,1,′′;iPos, 1, ''; sEncryptionKey .= sKeyFragment;#pridaj do kluca# print OUTFILETEMP "sKeyFragment;#pridaj do kluca# print OUTFILETEMP "sDataFromFileTemp\tsKeyFragment\tsKeyFragment\tiPos\n"; $i--;} –  Lubo Oct 30 '12 at 6:03
    
OMG, this got all corrupted, how do I paste a code snippet properly? –  Lubo Oct 30 '12 at 6:09
show 5 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.