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.

-
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

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.

-
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
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

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 .

-
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
@Lubo: If you really think you need code, put it in the question or an answer (indented by four spaces), not into a comment. Though normally on crypto.SE code examples are not needed, it is better to describe an algorithm with words or formulas. – Paŭlo Ebermann Oct 30 '12 at 21:23

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).

-

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.

-
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. What nonsense! A one-time pad is called OTP because the Key is only used one time. That is all and nothing more to it. All the other conditions you refer to are only requirements to fulfil the need for perfect security as described by Shannon in his 1940 papers, published in 1949. – user27844 Sep 21 '15 at 16:01
@WandeeThaweetham: "A one-time pad is called OTP because the Key is only used one time." If by "only used one time" you mean each individual element (bit or character offset) is only used to encrypt one same sized bit of the message, then yes that's a OTP. But that seems perfectly aligned with John's answer. If you are trying to imply that a key shorter than the message, used only once, is a OTP, then that is incorrect. I'm not sure what that is called, but it is not a OTP. – Neil Slater Sep 22 '15 at 8:11
@WandeeThaweetham, the key has to be used in a particular way to be a one-time-pad, with a bit-for-bit / digit-for-digit / character-for-character matching of key material to plaintext material. You're claiming a "One Time Key" is the same as a "One Time Pad", but that's simply not true - any key shorter than the plaintext will necessarily require some form of key stretching, where one bit of key material will influence more than one bit of output. The key bit is therefore not used only once. I recommend you do some more research on Vernam ciphers, instead of quoting Shannon out of context. – John Deters Sep 23 '15 at 21:18