Talk:One-time pad

Padding as a form of authentication?

I've removed the following claim, because it is not backed up by a reference.

The classical pencil and paper techniques of padding and Russian copulation can block such a substitution attack by denying the attacker knowledge of where to modify the cipher text.

The problem here is that both methods are heuristical and the arguments are mainly based on unproven assumptions. This looks rather odd compared to the information theoretical secrecy of the one-time pad and the security guarantees of the universal hashing. In particular, the supposed strength of adding some padding seems to assume that there is some variable length padding that is prepended to the message. I.e., this is an implicit assumption not made clear in the text. Without a clear definition of what the supposed countermeasures are it is not possible to make claims about the strength of those countermeasures. Hence the text is vague and does not add content to the article. Without a reliable reference it is unclear whether these countermeasures provide significant strength. 62.203.12.206 (talk) 17:15, 26 December 2008 (UTC)

First of all, the entire section on authentication is unreferenced. One time pads were used for decades at the highest security levels and I am not aware of any authentication problems encountered. The substitution attack described in the section is common to all stream ciphers and depends on an adversary knowing the exact offset from the start of the ciphertext to where the characters to be altered lie. It is obvious that random length padding or Russian copulation at a random offset prevent an attacker from knowing this. The best an attacker can do is guess the position, which has a likelihood on the order of 1/n, when n is the length of the padding or the message respectively. While that is not as strong a protection as what can be achieved with modern methods, it makes it much more likely that an attack will be detected than succeed. Also the security guarantees of universal hashing depend on the availability of a trusted computer, something hard to achieve in the real world. We can remove the entire section as unreferenced, but if not, I beleive the comments I added are needed for balance. --agr (talk) 20:31, 26 December 2008 (UTC)

There are two main claims in the contested section: (1) The one-time pad does not provide authentication. Several of the references given for this article talk about this problem. (2) Universal hashing can be used to provied information theoretical authentication. Universal hashing has its own wikipedia article an is reliably source. Furthermore just because something else is not referenced doesn't mean you have a free pass to add whatever you like to wikipedia. Regarding you proposal: a success probability of 1/n (assuming for the moment that this is indeed the correct result) for an authentication scheme that has length O(n) is a weak result, as the success probability is not negligible. Hence such a result is of no interest. A slightly different matter is, if the authentication you proposed was used in the pre-computer age. But again in this case some reliable reference would be necessary and the addition would would probably be better in the history section. 81.62.44.149 (talk) 11:22, 27 December 2008 (UTC)

link back and forthing

An external link to a Javascript implemntation o fa one-time pad has been included, and then deleted and then included again. We're verging on the 3RR rule here, so I thought some discussion would be well. The link is to a dark site (lots of dark gray with lither gray text) which is actually otherwise reasonably well designed.

The trouble is with the underlying design of the program. It is in Javascript, which is touted as an advantage, since it runs on client-side and so doesn't depend on the Internet or any server thereon while it runs. Well, that's perhaps good, but Javascript has a very dodgy history of design security issues, and much history of implementation squabbles (the language specification being somewhat "variable"), nearly all of which is bad from a security perspective, and so from a cypher implementation perspective. But still worse, the program design simply avoids the central issue of the one time pad, to wit, randomness. The programs user is left with finding a source of randomness, and given a few pointers to websites which might help.

This is inadequate and reduces the supposed program's relevance to an article on one-time pads to nullity. A virtuous stance of not attempting to (questionably at best) generate random data programmatically leaves the offered software without any virtue whatsoever.

This should not be a link in this article. It fails any reasonable test of link quality. It should not be allowed to be added anytime in the future as well. There is no reason to believe it will ever become anything like a reasonable link, as the significance of the one-time pad is fundamentally linked to the base concepts of communication and information theory. Don't bring this link back. ww (talk) 21:31, 30 March 2009 (UTC)

superencryption scheme

Shouldn't this "the combination would be at least as strong as the strongest layer." be "the combination would be at least as strong as the weakest layer." The strongest layer is OTP can you achieve the strength of OTP if you combine with another weaker encryption system? To me it looks like the encryption would be at least as strong as the weakest link, but not as strong as OTP, right? Or I totally missed the idea... man with one red shoe 22:09, 30 April 2009 (UTC)

Makes perfect sense to me... If a given message is encrypted using the Caesar cipher, and then with OTP, being able to break the Caesar cipher layer alone doesn't give you the plaintext -- you also have to break the strongest (OTP) layer. -- intgr [talk] 19:10, 1 May 2009 (UTC)

Well, I thought like this, if one-time pad is theoretically unbreakable a combination of one-time pad and another method cannot be "at least as strong as" because you can't have anything stronger than "unbreakable". But I guess in case of the discovery of the one-time pad the cypher would still have the strength of the weakest link... (the difference between "theoretically" unbreakable and the real-life) I still find that sentence a bit awkward... man with one red shoe 23:48, 15 May 2009 (UTC)

I think you have a point here. The statement is unclear and possibly incorrect. It reminds me of the paper by Maurer and Massey "Cascade Ciphers: The Importance of Being First". There the authors show that a superencryption with two ciphers and idependent keys is at least as strong as the first cipher, but not necessarily as strong as the second cipher. If two stream ciphers are used then the order is exchangeable and hence the cascade is at least as the stronger stream cipher used in the cascade. Note they are talking about stream ciphers not OTPs. On the other hand assume that the first cipher in the cascade uses compression. Then the encryption of n random letters is distinguishable from the encryption of n letters 'a', if the latter results in a shorter ciphertext. Hence the cipher is not semantically secure. Adding a layer using a OTP doesn't change the length of the ciphertext and therefore the cascade isn't semantically secure either. Since the statement is confusing, potentially incorrect, unreferenced and simple just doesn't make sense I'm removing it from the article. 92.106.132.178 (talk) 04:56, 16 May 2009 (UTC)

man with one red shoe: Your reasoning is logically inconsistent. "at least as strong as" means "strength is equal to or greater than"; the cascade needn't be stronger than OTP to satisfy the condition; it suffices if it's just as strong. I can't see what's unclear here.

I don't have time right now to digest the paper though. -- intgr [talk] 11:40, 17 May 2009 (UTC)

don't know about that, it might be logically valid but not linguistically correct, for example nobody says "at least as strong as God" you'd say "as strong as God". But I think my confusion here was between theoretical strength and practical (while OTP is theoretically unbreakable, it might still be breakable if somebody recovers the pad, so yes, superencryption would offer more protection, but I would still not call it "stronger than OTP" because it sounds weird in the context) man with one red shoe 15:10, 17 May 2009 (UTC)

Use cases, advantage, etc.

The article talks about the advantage and lack there of of OTP, particularly that to implement OTP you need to securely transport something just as big as the plain text. However it doesn't (or didn't last I checked) bring in the point that the constraints on transporting the key are much more relaxed: 1) It has very relaxed latency constraints in that the next key taking weeks to arrive is not a problem as long as the last key isn't used up yet. 2) Security failures are acceptable as long as they can be reliably detected before the key gets used. In effect, OTP trades one set of constraints for another, sometimes easier, set of constraints.

I attempted to add that in a while back but never really liked what I ended up with (and someone else yanked it back out again) so if someone who is a better writer than I could figure out how to work it in somewhere... —Preceding unsigned comment added by 99.72.154.66 (talk) 20:10, 6 July 2010 (UTC)

How it is impossible if one can check if the final grammar of a text is simply linguistically sane?

I don't get that from the article. --Athinker (talk) 11:30, 7 January 2011 (UTC)

I assume you mean "why can't someone try all the keys and figure out which give a sane output"

The answer is partly given in the "Attempt at cryptanalysis" section. With one time pads, every fitting-length outcome is possible. By applying this proposed cryptanalysis, you will get a list of all possible linguistically sane constructions, but you still don't know which one was intended to be transmitted. Thus you aren't any wiser regardless of whether you have the ciphertext or not. -- intgr [talk] 17:40, 7 January 2011 (UTC)

Error in example?

The example says "If a number is larger than 25, then the remainder after subtraction of 26 is taken in modular arithmetic fashion". Should this not be 26? Paul Magnussen (talk) 18:46, 10 April 2011 (UTC)

The example is correct. The result of the modular operation should be in the range 0 .. 25, since 0 corresponds to A and 25 corresponds to Z. Thus any result up to 25 is in the correct range and any result 26 or higher must be reduce modulo 26. Also, since the addition of two integers <= 25 can be at most 50 it is possible to do the modular reduction with a single subtraction. 85.1.93.222 (talk) 21:26, 10 April 2011 (UTC)

So ... how may pads do you have to use in sequence to beat the best super computer. (answer later) — Preceding unsigned comment added by 71.232.252.76 (talk) 20:25, 25 May 2011 (UTC)

Phony Message

This is about the "Dubious" tag I added to the following sentence: "The straightforward XORing with the keystream creates a potential vulnerability in message integrity especially simple to exploit—for example, an attacker who knows that the message contains "Meet Jane and me tomorrow at 3:30 pm" at a particular point can replace that content by any other content of exactly the same length, such as "3:30 meeting is cancelled, stay home", without having access to the one-time pad."

Something seems wrong. If the assumption is that the key is simple "mod 26," maybe, but the paragraph needs to be more clear, especially for non-experts, like myself.

Take ENABLE, the correct message from BOB, and DEFEND, the phony message Charlie wants Alice to get. For simplicity, everything's just plus one (but Chariie doesn't know that). Therefore, the code is FOBCMF. Charlie can send EFGFOE, which Alice will see as DEFEND, thus being fooled.

But Charlie cannot afford to get the phony message wrong. He must have 3 things: the real encrypted message, the real unencrypted message, and certainty that simple mod 26 substitution was used. He has no way of being certain of this last (unless he has a copy of the key). Just because FOBCMF gets ENABLE, does not mean EFGFOE gets DEFEND.

If Bob and Alice just agree on a different ordering of the alphabet, Charlie is stumped. He might make educated guesses, but the message is too short to be certain of the substitution key.

Different substitution is not universal hashing or message authentication.

This is a very important paragraph in this article. Would someone with expert knowledge please rewrite it so that it is clearer and less ambiguous. Anthony717 (talk) 10:00, 30 July 2011 (UTC)

It's standard in analyzing any crypto system to assume the attacker knows the details of the system used, in this case how the key is combined with the plaintext to encode the message. Also there is no requirement that the attacker knows the unencrypted message, just it's exact format. --agr (talk) 15:22, 31 July 2011 (UTC)

I added the dubious tag to this and came in here to create a section and I find there is already this one. The assertion "an attacker who knows that the message contains "Meet Jane and me tomorrow at 3:30 pm" at a particular point can replace that content by any other content of exactly the same length, such as "3:30 meeting is cancelled, stay home", without having access to the one-time pad" seems plainly wrong to me and needs to be either removed or very convincingly supported. GS3 (talk) 17:23, 30 October 2011 (UTC)

I added a reference to the article. This is very standard stuff; the technical term is malleability. There is a worked out example there and at stream cipher attack. Do a google search on "one time pad malleability " and you'll find lots of other references.--agr (talk) 19:29, 31 October 2011 (UTC)

I am still not seeing it and it goes contrary to everything I know. I would say the opposite is "very standard stuff". The reference link you added just leads me to the cover of a book and I would need to see what it says. Can you cite the exact text and examples which support the assertion? At stream cipher attack I cannot see any "worked out example"; only a bare assertion. Can you please provide a clear supporting citation and a worked out example? For instance, there is a simple example in this article where Alice encrypts the plaintext "HELLO" using the key "XMCKL" which results in cyphertext "EQNVZ". Suppose an attacker wants to change the message to something else *and does not know the key*, how can he do it? I believe there is no way. Please show us how "malleability" allows this to be done because I am not seeing it. I think it is pretty well established and accepted that one time pad keys are an uncrackable system. Thanks.GS3 (talk) 16:31, 3 November 2011 (UTC)

I'm not Arnold, but no, this is a legitimate flaw if you use an invertible function (as stated in the lines leading up to this), and the attacker knows your plaintext. Without looking at your key (except for verification) at the end - if the key is A + B % 26. , I take H (7) + ?? = E (4) (mod 26). Therefore, 7 - 4 = - ?? mod 26. -3 == ?? mod 26. Therefore -3 + 26 = ?? mod 26, which means ?? == 23 mod 26 - which is X. Which should be the key. I've derived the key for the position from the function, ciphertext and plaintext. Similarly, E (4) + ?? == Q (16) % 26.  ?? == 16 - 4 % 26. ?? = 12 (M). etc. Now I know the key and function, so if I want to change the first character to F, I just do F (5) + X (23) == C (2 mod 26). Etc. etc. An OTP is uncrackable in the sense that if all I have is the ciphertext, even if know the algorithm, but without the OTP or the plaintext, I cannot possibly generate one or the other. As any result is possible. This is of course useless for all further messages, since the OTP key is not reused, but if I intercept the message and know a portion of it, I most certainly can manipulate it. — Preceding unsigned comment added by 24.5.145.245 (talk) 00:24, 6 November 2011 (UTC)

A Google search for "one time pad malleability" (including the quotation marks) leads to class notes for a single class, nothing else. If I understand this phenomenon, a person who knew the exact format of messages, but not the key, could change a value in a message, but not know what it would be changed to. For example, if the symbol set for the key were only upper case letters, the space, and numerals, and the plain text were "PAY_ALICE_______5" and the name field was known to be 6 characters, then a space, then a six character payment field, an adversary could alter the message to read "PAY_ALICE__5T_8QP", and would have no idea what the recipient would see in the payment field after decryption. Jc3s5h (talk) 17:01, 3 November 2011 (UTC)

See my above comment, if you know what it said before, you can decipher that portion of the key, and then you're able to change it at will. Also, it's not one time pad specific - it can apply to many stream ciphers - http://en.wikipedia.org/wiki/Malleability_(cryptography) — Preceding unsigned comment added by 24.5.145.245 (talk) 00:26, 6 November 2011 (UTC)

Nope. That is not what is being asked. The assertion is "an attacker who knows that the message contains "Meet Jane and me tomorrow at 3:30 pm" at a particular point can replace that content by any other content of exactly the same length, such as "3:30 meeting is cancelled, stay home", without having access to the one-time pad". That is what is being asked. Just corrupting the message without being able to determine what the corrupted message will be is not the same thing at all. GS3 (talk) 19:31, 3 November 2011 (UTC)

I have added the "dubious" tag again to the phrase in question. Please do not remove it until this matter is convincingly settled. After some time if the phrase is not proven I will remove it. It just seems very obviously wrong to me. The XORing operation is extremely simple and is done on characters one by one. You have the plaincharacter, the key-mask character and the cyphercharacter. If you know two of the three you can obtain the third. If you know only one you have no way of obtaining the other two because each depends on the other. No way. This is true for one or for a million characters as they are encoded and decoded one by one. That is the basic principle underlying the one time pad. GS3 (talk) 13:03, 5 November 2011 (UTC)

You seem to be missing the fact that in order to manipulate a portion of the ciphertext to a known value, I would generally need to have the ciphertext value in the first place. Otherwise I wouldn't be able to replace one section of it in the first place (I wouldn't know the rest of the message). If I know the message contains "foo" at a given point, and I know the cyphertext says "bar", then I do in fact know two of the three, and can work out the third- like add key mod 26, I can most certainly compute b - f (mod 26) a - o (mod 26) and r - o (mod 26) to get that particular portion of the OTP. (4, 14, -3). Now I can apply the key to my new message ZIP, (25 + 4, 8 + 14, 14 + -3) to get CWJ. See above for a worked out example of this (from my same IP) 24.5.145.245 (talk) 00:00, 6 November 2011 (UTC)

serious drawback ?

Why is the need of a "careful treatment to make sure that it continues to remain secret from any adversary" listed as a serious drawback of one-time pads? This problem seems common to every cryptosystem known, whether it is based on symmetric cryptography (the key must remain secret) or asymmetric cryptography (the secret key must remain... secret). — Preceding unsigned comment added by 82.121.127.28 (talk) 20:24, 2 November 2011 (UTC)

Some cryptographic protocols prevent an attacker from reading earlier messages even if the secret key is compromised. See perfect forward secrecy--agr (talk) 02:22, 6 November 2011 (UTC)