Talk:One-time pad/Archive 1

Archive 1

Distinction between OTP and stream ciphers? nONE!

Pulling this out because it's confusing and probably wrong:

One should also note that even the best cryptographically secure random number generator cannot be used to implement a secure one-time pad without first being initialized with true random data of at least the same length as the one-time pad itself.

The problem is that if a RNG has small state, it doesn't matter how large a seed you use; it still doesn't give you a one-time pad. So I suspect it's better just to keep the distinction between one-time pads and stream ciphers clear.

That is certainly correct. And there are lots of other problems with using any form of PRNG for making OTPs. However in the current form the article seems to imply that Blum-Blum-Shub can be used to implement OTPs that are 'good enough in practice'. While correct in some convoluted sense, I think it could confuse some people.

Perhaps discussion about stream-ciphers and CSPRNGs should be moved from this page...

Rasmus Faber 16:23, 5 Dec 2003 (UTC)

It can be "good enough," if you can find primes large enough, and make sure not to use it after its periodicity. The problem is the rather low numbers of commercial crypto companies that know how to do that properly - or care. Block cyphers (as in PGP session keys) are generally a better idea. --Pakaran 16:29, 5 Dec 2003 (UTC)

But well, "good enough" isn't really that good when you are comparing with provably secure. By interjecting a CSPRNG step you really only hide the problem of finding enough entropy to seed the algorithm. After all, if you generate the |M| bits necessary for the CSPRNG step to be ok, why not just use them directly as the OTP...

Rasmus Faber 16:42, 5 Dec 2003 (UTC)

I agree that having too much about stream ciphers on this page is just plain confusing. I am going to try to pull it out and replace it with something that will encourage people to read the stream cipher article instead, while mentioning enough detail to try to keep people from confusing stream ciphers with one-time pads. Populus 17:39, 5 Dec 2003 (UTC)

Sounds good to me. The problem is the use of OTP as an advertising buzzword. -- Pakaran 17:42, 5 Dec 2003 (UTC)

Pulling sentences below out because determinism explanation is incorrect. Cryptographically secure PRNGs are also deterministic (you couldn't use them in a stream cipher otherwise); the difference is they can't be predicted from a sample of their output. Populus 05:01, 10 Jan 2004 (UTC)

In particular, the Mersenne twister algorithm, while "random" for almost any research or simulation use, cannot be used to generate a one-time pad. One reason this, and similiar algorithms, are useful in research is that they are deterministic - and therefore an independent researcher can seed the algorithm with the same values and get the same result. This is a severe weakness for cryptographic use.

---

Rasmus, Thanks for the warning about browser limitations. I've noted it at the external link. Indeed the browser I'm now using (under Win 2000) fails to display anything beyond a large blank space. ww 17:45, 6 Apr 2004 (UTC)

Rasmus, Still fails for my browser. I've copied the nr into the text, so those with problems can try to figure something else out. The warning at the link may be enough to fulfill our obligations as authors, pending sanity/greater uniformity amongst browser capabilities. Other than that, I'm out of ideas. You? ww 20:02, 6 Apr 2004 (UTC)

Intro

The intro to this article is somewhat confusing. The only exposure I've had to one-time pads is when reading Cryptonomicon, so I'm not an expert, but I think one must assume that someone reading an encyclopedia article might not be an expert. I think a clarification of how the length of the message matters, and what, physically, a one-time pad looks like might really help. —siroχo 05:15, Jul 29, 2004 (UTC)

Thanks for your observations, they are most welcome, and indeed, a layperson's comments are just as valuable as an expert's (this page is currently being polished up for inclusion in a general-readership "WikiReader Cryptography", so even more so: see also Template:WikiReaderCryptographyAOTD-Verbose). Hopefully we can fix things to make it less confusing. As to what it looks like, it can vary wildly from actual sheets of paper, to tiny hidden books, to CDROM-- the medium isn't as important as the concept. Here's an actual Russian OTP, captured by MI5: here — Matt 05:30, 29 Jul 2004 (UTC)

Matt, 'Teeny tiny' is too much for you? Oxymoronically? :) ww 19:09, 29 Jul 2004 (UTC)

Heh, a "little" too much for me, yes ;-) — Matt 19:55, 29 Jul 2004 (UTC)

In reading this article, I flagged "teeny tiny" in my mind even before reading this Talk page. I've substituted "minuscule". JamesMLane 00:23, 19 Aug 2004 (UTC)

Length of spurious message

I'm confused by this passage:

However, an active attacker who knows the plaintext can recover the pad then use it to encode whatever he chooses. If he can get his version delivered instead of yours, disaster may result. If you send "attack at dawn", the delivered message can be anything of the same length -- perhaps "retreat to east" or "shoot generals".

It seems to me it should say that the attacker's message can be anything of the same length or shorter. It also seems that the examples given don't qualify (spurious messages of thirteen letters after intercept of a genuine one of twelve). Am I missing something? JamesMLane 00:23, 19 Aug 2004 (UTC)

jml, Yup, shorter works. However, if Mallory's padding (cryptography) scheme is different than expected, a rat will be smelled. "Thought we agreed on all "a" for any required padding, but I find mixed letters instead." Oops. For greatest generality, we should probably leave out the 'or shorter' as it requires explaining about other issues such as padding patterns. As for the example given, yup again. 15 letters is too many; bad example. Can Wikipedians actually count? How about 'retreat to ENE' instead? 'Shoot generals', works though (except for the generals). ww 16:53, 20 Aug 2004 (UTC)

I didn't realize padding would figure into it at all. Presumably the one-time pad is large enough to accommodate any anticipated message, so virtually all genuine messages will be shorter than the pad. Why can't the attacker substitute a message that's shorter than the original, without adding any padding? Also, a minor point, the explanation refers only to letters, but your count includes the spaces. I assume modern electronic methods allow the full range of characters (so spies can argue about en-dashes versus hyphens). If the new examples are all to be of the same length, I suggest using the same number of words in each, so that the character count will be the same either way. That way it won't confuse people who count only the letters. The generals will like that solution. We could substitute "march to river". JamesMLane 03:20, 21 Aug 2004 (UTC)

jml, In the real world padding is in fact important, though you're right in this case, the one time pad key material is required only to be as long as the message for the provable security (assuming all other conditions are met). Thus length of key is (nominally) exactly as long as the message; in practice, this may be modified (see the world wonders for an example, though I have no idea whether that was a one time pad). The reason for a shorter message being substituted is that, as I attempted to note, it might give a clue that good old Mallory has had his mitts in the stew. Not a clue Mallory would like to leave for the other side.

As for only alpha but no spaces, well... word spacing is a substantial clue in some cryptanalytic attacks and on general principle one should avoid anything which might give Mallory any information, including hints about word length. And, in modern character codes (a misnomer, of course) 'space' is a character just as much as "Q" or "r". Your thought that the 'full range of characters' should be accomodated is troublesome. I am presuming you have in mind such things as, for instance, MS Word ".doc" format. If so, the message to be encrypted will be the MS Word .doc file and this is, I suggest, an outstandingly dubious approach. Those files contain large amounts of stereotyped data, nearly all of which will be a crib for a cryptanalyst. Too little entropy in the message being sent. Not Good.

As for the same number of words, you have a point. On the other hand, I can imagine that it would be well for Readers to realize the point about spaces being characters not just empty place holding to separate things. Two houses, alike in dignity, ... Not clear there's a best way to do both at the same time. Two examples, perhaps? ww 20:23, 24 Aug 2004 (UTC)

Padding: I was assuming that, with the one-time pad, Alice and Bob generally wouldn't know in advance how many characters would be in the legitimate message. It might be "attack at dawn" or it might be "shoot the generals and then retreat to the northeast". Would it be customary, in practice, to agree on a set length for each message, with an agreed-upon padding scheme? If so, then this practice, and the padding issues you've explained here in Talk, should probably be addressed in the article. I, for one, found your comments quite illuminating.

jml, There is the Platonic ideal one-time pad, and then there are the real world practical one-time pads. In the real world, because of the way the key material is distributed and managed it may be necessary to use, then discard, integral numbers of sheets (see the picture in the article of the teeny tiny pads issued by Moscow Centre to at least one spy -- the 'Krogers'?). So I send a message of 273 characters, which uses only 33 characters from the last sheet. The use protocol may include plaintext padding so as to use up the last 17 characters on that last pad sheet. If so, padding difficulties would come up for Mallory when attempting to spoof. None of this is relevant for the Platonic ideal pad. But your thought that a preset, or even fixed, length for one-time pad messages seems unlikely is probably so. I have no direct knowledge (being neither a present nor past employee of NSA nor Moscow Centre nor GCHQ nor ...), but the Platonic one-time pad certainly includes no such requirement. However, I can easily imagine user protocols which might, mostly in order to make Mallory's life more difficult. ww 17:40, 30 Aug 2004 (UTC)

Characters: I had in mind just the basic typographic characters, not MS Word codes for italics and whatnot. If the decrypting is being done by computer anyway, there's no reason to risk confusion between resume and resumé. Even punctuation could make a difference. (A superfluous comma in a tariff statute once cost the U.S. government millions of dollars. A list of exemptions was supposed to include an entry for fruit plants but in its place included what looked like two entries -- fruit, plants -- expanding the exemption greatly.) With a one-time pad, can't characters like commas and asterisks be available for use in the encrypted text to represent letters? And their occurrence in the plaintext could be reflected in the encrypted text?

jml, You are correct. A character is a character and if some mapping combining two characters (one from the plaintext and one from the key material) into a cyphertext character is defined, any character including punctuation can be easily accomodated. In practice, for a long time, this mapping has been a bit-wise XOR of a plaintext character and the relevant (eg, usually 'next') key pad character. As long as that combining function is defined for this or that (or all) punctuation, punctuation can be managed without a problem. ww 17:40, 30 Aug 2004 (UTC)

As for the examples, my only problem was that the explanation earlier in the article referred only to encrypting letters. Perhaps that explanation should note that preserving word divisions is to be avoided, and that blank spaces are therefore to be treated as characters and encrypted.

jml, With the one time pad (properly implemented and used) spaces probably can be retained with negligible loss of confidentiality, even though they theoretically retain information which might be of use to Mallory. What I really had in mind were such things as lots of spaces used to provide page layout in the plaintext (eg, address block indentation, or margins), or all that stuff MSWord puts in all its files (eg, the path to the printer on the originating computer, the registered owner of the Word copy, ...). All of this is stereotyped, will be well known to Mallory (we always assume Mallory to be competent!), and therefore increases redundancies in the cyphertext. Mallory will be pleased which is, I assume, not what we (and Alice and Bob) would like.

For ease of transmission (if done by hand, or received manually) and breaking up hints about word terminations, cyphergroups will usually be a fixed 5 or 4 or 6 characters in any case. For instance, JN-25 was sometimes called '5-num'.

JamesMLane 15:38, 25 Aug 2004 (UTC)

Under the heading of "no good deed goes unpunished": ww, your responses to my questions have been very informative. If you get the chance, I hope you'll consider incorporating some of this material into the article. Although we're enjoined to be bold in editing, I confess I feel out of my depth here. JamesMLane 11:30, 1 Sep 2004 (UTC)

jml, is this enough :? Don't feel out of your depth. Be bold, just try to be right too. Your comments have been perfectly sensible and quite alert. The problem comes in that this is a WP article and is not supposed to be comprehensive, thus leading to the odd misleading bit a few of which you picked up on. To the extent that some of all this should be in the article, I suggest that you have at it, as I'm likely to leave something out by inadvertence, since 'everyone knows that'. You are likely to serve the Average Reader in this instance better than I. ww 20:28, 9 Sep 2004 (UTC)

Images

I have uploaded some images, which we can use in this article:

/* images moved down to table */

could someone good with tables make the formatting?

-- ato 04:38, 21 Aug 2004 (UTC)

Ato, At first blush (I'm in a hurry and can't look in detail) these fill the bill. I would observe however, that the visual key+message data mechanism is not easy for the non-visual to follow. No ideas how to manage that though. ww 20:27, 24 Aug 2004 (UTC)

a character:
an example pad:
result of encryption:		XOR		=
decryption:		XOR		=
a false pad:
decryption with false pad:		XOR		=

Is this format OK? -- Nihil86 23:54, 31 October 2005 (UTC)

Error

The following under OTP disadvantage is not correct: "Even if a one-time pad is implemented and used correctly, it is normally vulnerable to a substitution attack."

This does not apply as the key length is identical to the plaintext length. Please correct.

It's not an error, it's true. If you know the content of a message that is transmitted using a one time pad, and you can mount a man in the middle attack, you can easily replace that message with any other of equal length and it will decrypt properly. This is a property of all stream ciphers that do not employ some separate authentication checks. It does not, however, recover the key. See Stream cipher attack for an explaination. --agr 02:01, 19 Jun 2005 (UTC)

Confusion between randomness and entropy

Successive edits have blurred this critical point. As an unrealistic example, consider this. If it is not possible for any attacker to discover that the source of key material being used in a particular OTP implementation is the digits of pi (3.1416...), than for all attackers, that key material has maximum entropy and is perfectly suitable for OTP use. If, to modify the example slightly, some attacker is a bit brighter (or more suspicious than the rest), this source of key material would be discovered and instantly cease to have any entropy at all -- for that attacker. Nevertheless, it would still retain its usefulness, and highest possible entropy, for the others, they being somewhat slow on the uptake.

Since this is a rather unrealistic example (for instance, some pattern in pi's digits may yet be discovered, and one can't count on all one's attackers remaining molasses slow), we must add a little real world to it. Attackers may talk to each other, or hire some smarter than the rest minion, and you can't know whether they do or have. So counting on pi's digits retaining their entropy against whatever (unknowable) attackers there may be is foolish. Thus one's best resort is to a source of key material which is random (ie, unpredictable for anyone -- including all attackers). Such a source would retain its high entropy value for all the Enemy and so be satisfactory. It is for this reason (and a preference for shortcut, shorthand, elliptical, abbreviated, accounts that random is usually used in place of 'high entropy for all attackers' in discussions of OTP.

This distinction is the one that has become blurred in this article. However, like Pascal, I haven't the time to make this shorter and knit it into the article. Volunteers?

ww 18:29, 7 Dec 2004 (UTC)

We need a page on cryptographic randomness, since this is an endless source of confusion and wrongheadedness judging by the endless discussions on sci.crypt. For cryptographic purposes, randomness is entropy. A bit is random if, at the time that it is generated, a computationally unbounded attacker cannot guess it with probability of success greater than 1/2.

This gets complex, though. For example, if I then use the bit to encode a message, it is no longer random from the attacker's point of view! Suppose 1 means "attack" and "0" means "retreat", and I generate one random bit which is used to encrypt my message with the one-time pad. Suppose you're the attacker, and you know I'm much more likely to retreat than attack. You eavesdrop the message, and find it's "0". You now know it's much more likely I generated a 0 than a 1 - you have information about my random bit, making it less random from your point of view. However, because the bit was randomly and fairly generated, you don't know any more about whether I might attack or not than you did when you started.

It is, of course, generally true that receiving a message encrypted with OTP gives you information about the pad, but not the content of the message. This is why you must never reuse the pad.

dubious claim

A recent edit by Edgaar claims that use of two cypher algorithms in sequence is always as strong as the strongest one. As strength varies wildly according to attack used, keeping the algorithm and plaintext and key constant, strong in these contexts presents some considerable conceptual difficulty. However, aside from that, his point is incorrect. It is possible that the use of two algorithms in sequence could introduce what are called 'compositional weakenesses', making the combination quite different in vulnerability to this or that attack than either alone. The difference could be an increase or decrease in vulnerabilty.

An example is DES, which when used twice is more vulnerable than when used only once. This was the reason for Tuchman's Triple DES design, which avoids that particular problem.

I will try to remember to come back and revise this in the near future. In the meantime, comments from anyone on this point? A better example of a compostional weakness? A start on an article for compositional weakness? ... ww 22:48, 30 Mar 2005 (UTC)

Hmmm...well, Eddgar's statement is indeed correct: if you use several independent algorithms in series, then yes, it is always at least as strong as the strongest algorithm (because any attack on the cascade can be converted into an attack on a component cipher). (And you're not quite right about DES: the reason 3DES was used rather than 2DES is certainly not that 2DES is weaker than single DES, but that it's not dramatically stronger: there's a meet-in-the-middle attack that means its not as strong as you would hope). However, I haven't previously heard Edggar's argument that an OTP and a "conventional" cipher be used in parallel: is this a widespread suggestion? It's very strange, because an OTP is unbreakable: there's no point in trying to increase its security. I suggest the addition be removed unless this has been seriously proposed in the literature somewhere. — Matt Crypto 23:15, 30 Mar 2005 (UTC)

The problem with superencryption with "independent" algorithms is proving that they are indeed independent. That is comparable in dificulty to proving ciphers are secure. The one exception is the one time pad. If superencryption could weaken OTP, that would be a way to crack it, which is provably impossible. To the extent OTP is still used, it is probably superencrypted fairly often. OTP messages are likely sent over links secured with ciphers, to achive traffic flow security, for example. That said, I agree Eddgar's comments are not appropriate to the article. It's his idea on how to solve a problem that essentially does not exist. The point of the rest of the section is that there really isn't controversy about OTP itself, but about its practicality relative to cipher-based systems and misuses of the term to give cachet to snakeoil. --agr 11:49, 31 Mar 2005 (UTC)

Proving independence isn't a problem — "independent" here means that the ciphers are keyed with keys that are statistically independent. I've done a little more reading since my previous post:

• S. Even and O. Goldreich, “On the power of cascade ciphers,” ACM Transactions on Computer Systems, vol. 3, pp. 108–116, 1985.
• M. Maurer and J. L. Massey, “Cascade ciphers: The importance of being first,” Journal of Cryptology, vol. 6, no. 1, pp. 55–61, 1993.

The first reference gives the result that if you have a cascade of independent ciphers, it is always at least as strong as the strongest algorithm. However, today I read the second reference by Maurer and Massey. They point out that the result doesn't hold if you're considering ciphertext-only attacks. In that situation, the cascade is at least as strong as the first cipher. — Matt Crypto 13:43, 31 Mar 2005 (UTC)

---

OK. I'm puzzled by these 2 contradictory papers (one must be wrong !) Someone has a link to read them online?

I found them both via Google. They're not contradictory, but they assume different definitions of the word "strength" (that is, ciphertext-only vs chosen-ciphertext attacks). — Matt Crypto 11:31, 1 Apr 2005 (UTC)

I'll revise my statement then: If you use 2 independent (using independent RNGs) cryptosytems, one of them being OTP, then the result is at least as strong as the strongest cryptosystem.

Obviously, when OTP adds some random to an already made ciphertext, it can't make it less secure. And adding some random to a plaintext, before it is encrypted, can't make it less secure too.

Quite, but an OTP is already unbreakable; why would you try to make it more secure? Your scheme simply makes it less efficient. — Matt Crypto 11:31, 1 Apr 2005 (UTC)

OTP is not practically secure, given no always perfectly practically secure RNG are known (every harware device, even quantum RNGs, can have malfunctions) Edggar

If your RNG malfunctions, then it's not really an OTP any more. If you're at risk of your RNG malfunctioning, then you might as well simply use a conventional cipher. — Matt Crypto 12:40, 1 Apr 2005 (UTC)

How can you be sure that your oh-so-secure current RNG will never have a malfunctiun ? Edggar

Proving this statement, using keys that are statistically independent, is so obvious that nobody should think it deserves a research paper ! I guess stating obvious claims is allowed in Wikipedia.

Stating obvious claims is, of course, fine. However, this idea is not (as far as I'm aware) a widespread suggestion for OTPs. An encyclopedia article should only include notable facts and concepts, and not original thinking. — Matt Crypto 11:31, 1 Apr 2005 (UTC)

That's so obvious for a cryptographer that none would make a paper out of it. But an encyclopedia is not meant for specialists only, and this information is important for non specialists. Edggar

I'm not saying it needs to have been published in a journal paper, but you need to make a case for why this information is notable in the first place: why is this information important for non-specialists? Otherwise, it just seems like an idea you've had. — Matt Crypto 12:40, 1 Apr 2005 (UTC)

The case is simple: after reading this controversy the non cryptographers will say: damn, I have to choose between 2 solutions, and each has a major security failure. And most non cryptographers don't know about cascading ! Edggar

Conventional ciphers have a major security failure? What, exactly? But my point was this: is this just your idea, or has this ever been a serious, notable suggestion in the field of cryptography? — Matt Crypto 13:08, 1 Apr 2005 (UTC)

Conventional ciphers can't be proven to be secure (only OTP can). And each year, some of them are found to be broken. That's what I call a major failure. Please, I don't want to read all popular books about crypto to find one with such an obvious statement. But Bruce Schneier already has a more complicated but not-so-different statement in his book "applied crypto" http://friedo.szm.sk/krypto/AC/ch15/15-05.html (read the end of this link)

I don't dispute that it's obvious, but rather that it's not a serious and notable suggestion in the field. I've read most of the popular books on cryptography, and I've never come across this suggestion before. Regarding the section in AC: Schneier is not describing combining an OTP with a conventional cipher, but rather a way of combining multiple block ciphers — Schneier's use of the phrase "one time pad" is unfortunate (used presumably for didactic reasons rather than being precise) and does not mean the same thing as the system under discussion here. (For example, this construction is not provably secure like the OTP). Regarding "major failure" of conventional ciphers: the vast majority of the cryptographic community regard conventional ciphers to be practically secure (and we're talking about well-studied, standard, publicly-specified algorithms here). — Matt Crypto 14:21, 1 Apr 2005 (UTC)

Each year a new flaw is found in a conventional cipher. And it's no suprise given Shannon theorems about OTP. I still find unfortunate that a common reader won't find a hint about cascading in this controversy. Because they may ask themselves this question: why can't I use both ? If there is no hint about it after such a long controversy, they may think it's not possible to use both. OK i got it. I think answering to this question could do it. I'm writing a the following twice revised version:

here is a twice revised cascading hint, to be put at the end of the controversy

At the end of this controversy one may ask "why can't I use both ?" (i.e. use a conventional cipher and then add an OTP layer). It is easy to prove that, provided you use keys that are statistically independents for each layer (e.g. independent RNGs), this combination would be at least as strong as the strongest layer. But we have not found sources talking about this combination.

What you are describing is usually called superencryption and it I think it deserves an article of its own. It's application not unique to OTP. There is another (I would argue better) way to do what you are suggesting for OTP which is combining the random pad bits with the output of a good stream cipher prior to use. This is mentioned in the hardware random number generator article: "Another method for improving a near random bit stream is to exclusive-or the bit stream with the output of a high-quality cryptographically secure pseudo-random number generator such as Blum Blum Shub or a good stream cipher. This can cheaply improve decorrelation and digit bias." It can also serve as a security backstop incase the random bit generation process is compromised in some way. You are, of course, free to use any method or combination of methods you wish. The main reason most cryptographers do not recommend using superencryption is that the likely benefit is small and adding layers of complexity discourages people from actually using encryption at all. --agr 16:21, 1 Apr 2005 (UTC)

Third revision: At the end of this controversy one may ask "why can't I use both kinds of cipher ?" (i.e. use a conventional cipher and then add an OTP layer). You can. Using 2 ciphers is called superencryption. OTP is a special case where it is easy to prove that, provided you use keys that are statistically independents for each layer (e.g. independent RNGs), this combination would be at least as strong as the strongest layer.Edggar

XOR vs modular arithmetic

I'm removing the edit that says "XOR is generally preferred to modular arithmetic." First of all, XOR is modular arithmetic (mod 2 addition). Second, XOR has no cryptographic advantage over addition with higher moduli. Implementing it hardware is simpler and this was important through much of the 20th century, but it is inconsequential today. It might be worth changing the term "modular arithmetic" to "modular addition" throughout. Multiplication with non-prime moduli would not be a good way to combine key and plaintext.. --agr 19:05, 8 Apr 2005 (UTC)

It's a fact XOR is widely used for stream ciphers and OTP. Thus XOR should at least be mentioned. Modular is more error-prone too.Edggar

Clarifications to the text

In the "Historical uses" section:

An example seems to have been the (used only once) message sent to President Truman at an end of WWII conference announcing the success of the Trinity test in New Mexico.

This sentence is confusing, and I'm not sure what it means. Could somebody clarify it?

I agree. It's an example of a one time code, not an OTP. --agr 09:25, 10 July 2005 (UTC)

The last paragraph in "Achieving Shannon Security" suggests only using new blank media for storing your pad. Is there are particular reason for this? The suggestion makes no sense to me at all.

Some of the earliest computer viruses spread via floppy disk. Use of only new media is a cheap way to eliminate this risk (however small). --agr 09:25, 10 July 2005 (UTC)

Again, under Shannon Security: "To minimize the risk of virus infection, a computer used to generate one-time pad key material should never be connected to any computer network and preferably should not be used for any other purpose."

It would seem that 'virus infection' is not quite the right way to phrase this danger, but perhaps something more along the lines of avoiding a comprimise of the system.

Good point. I rewrote the paragraph.--agr 15:23, 17 May 2006 (UTC)

It might be sensible to merge the "History" and "Historical uses" sections, as they both discuss similar material. At the very least, they should be placed next to each other, rather than almost at opposite ends of the document as they currently are. JulesH 9 July 2005 18:48 (UTC)

Open source advocacy/NPOV?

The last sentence in "Achieving Shannon Security" reads:

This is a good use for an older laptop, purged and rebuilt with a fresh, traceable copy of an open source operating system such as Linux or BSD.

This seems to imply that non-open source OSs cannot be trusted, which is arguably a POV assertion. JulesH 9 July 2005 18:48 (UTC)

The observation that use of closed source software requires one to trust its authors isn't necessarily POV. Also up-to-date open source operating systems run on obsolete computers that don't meet the performance requirements for, say, WindowsXP SP2, but which would be very suitable for OTP generation. --agr 09:25, 10 July 2005 (UTC)

Trusted cryptographic algorithms are peer-reviewed before deployment. Closed-source software cannot be peer-reviewed, therefore there is no trusted closed-source cryptography. End of debate; if you don't agree, I'll call you a Microsoft-fanboi and Steve Job's private cockwhore.

P=NP

I don't think this problem has any relevance for cryptografy. Suppose P=NP. That only means there must be a way to quickly crack the code. But it doesn't automatically give you the algorithm to crak it (that algorightm may never be discovered). Likewise, if P!=NP, that means there may be problems for which the solution is easy to check but hard to find. But there's no guarantee your crypto problem really is such a problem. In other words: your problem is an NP problem until proven otherwise.

"random"

Should we replace the word "random" with "unpredictable" as per randomness? I think that this is what we really mean. MisterSheik 04:37, 11 August 2005 (UTC)

I'm not sure I buy the distinction that the randomness article is trying to make. However, in cryptography, the term used is "random" and the provable security of the one time pad rest on its contents being chosen by a truly random process. --agr 16:16, 11 August 2005 (UTC)

Quantum Crypto to send pads!?

From the article:

"The recent development of quantum cryptography has provided a way, theoretically, to securely transmit key material between two locations in such a way that no eavesdropper can determine their contents without the eavesdropping being both detectable and destroying the information being transferred." ... "If practicable, this may eventually provide a better way to distribute one-time pad key material than anything known before."

Sounds a little silly to me, if you already have a (%100 secure) Quantum crypto connection why would you bother using OTP's???

-James C

The quantum crypto scheme most commonly described is a key exchange system. Once you've agreed on a sufficiently large amount of key-material, you can then encrypt your data, presumably using a one-time pad if you're going for the 100% secure label. — Matt Crypto 17:20, 17 August 2005 (UTC)

The only unbreakable encryption system

I have a concern about asserting that the one-time pad is the only unbreakable system. A one-time pad is always presented as a symbol-by-symbol addition of the plaintext message with the key material. But might there be other systems that are unbreakable that don't use this approach? The definition of "unbreakable" used by Shannon was "perfect secrecy": that the amount of information you have about the plaintext after seeing the ciphertext is the same as you had before seeing the ciphertext. He then showed that to achieve perfect secrecy it is necessary (although not sufficient) for the keyspace to be larger than the message space. He identified the Vernam cipher as one such system, but did not say that that was the only scheme.

I would suggest we weaken our assertion to "an unbreakable system", and mention that any other system that provides perfect secrecy has to have a key as long as the plaintext, and so shares the limitations of the Vernam scheme. — Matt Crypto 14:52, 18 August 2005 (UTC)

It's my memory, possibly shaky, that he also proved that any such scheme (ie, with perfect secrecy) would be homologous with the one-time pad, which you almost note. If my recollection is correct, we would be safe in saying that "...OTP or any homologous scheme..."; with sufficient clarity on the limited meaning of unbreakability in this context, I suspect that doing so would be surplusage though. Anyway, OTP is a 'threshold scheme', but I think that's a post Shannon term.

But in any case, as far as I'm aware, this is the only general encryption algorithm unbreakability proof (re any attack technique other than rubber hose or purchase key or cat burglary) in existence. If it is not, please enlighten me (and perhaps others also in delusional states (which is not to say only in USA, of course). ww 23:12, 6 September 2005 (UTC)

I'll dig out Shannon's paper again and have a look. What does it mean for two cryptosystems to be "homologous"? — Matt Crypto 08:35, 7 September 2005 (UTC)

It's something of a topological concept at heart. A coffee cup is homologous to hula hoop and not to homologous to a frisbee because there is a topological property conserving transformation in one case and not in the other. In this case, homologous would be with regard to information theoretical properties as between encryption transformations.

As in, a precise, mathematical definition? — Matt Crypto 12:40, 8 September 2005 (UTC)

I probably should note that I recall that J Massey of ETHZ (and others?) came up with something called the Rip van Winkle algorithm which is also provably unbreakable, but only under some rather humorous conditions, to wit waiting a very long time for receipt in the ordianry case (millions of years, I recall, or perhaps billions -- either BE or AE sense). So there are some other unbreakable (if even more unworkable) algorithms, but I've no information on the homologuity in this pair. I doubt that they would be as the underlying attack difficulty would at first thought be of a different flavour altogether. But of any practical algorithm, Shannon's homologuity result would apply. Wouldn't it? Or do I disremember something here? ww 11:22, 8 September 2005 (UTC)

I've just dug out my copy of Communication Theory of Secrecy Systems; could you tell me where Shannon proved this result that any scheme with perfect secrecy would be "homologous" (definition pending) with the one-time pad? — Matt Crypto 12:40, 8 September 2005 (UTC)

I think you will find that Shannon's definition of unbreakable is stronger that what would be common usage. A cipher is Shannon unbreakable if no information about the plaintext can be obtained even if all possible keys are tried. The random one time pad has this property and it is pretty easy to see that any cipher with this property must have a key length as long as the information content of the message. AES256 is not Shannon unbreakable (if the ciphertext is long enough) since if you could try all 2^256 possible keys, only one will reproduce a plaintext in, say, a natural language. This does not render AES256 weak in the ordinary sense since it is not feasible to try that many keys. Shannon breakablity would have practical significance where someone accused of a crime is proven to have sent a particular ciphertext of modest, but not too short, length. The prosecution could legitimately convince a court that the ciphertext decrypted to a particular English message merely by producing a key for some strong standard algorithmic cipher that converted the ciphertext into that message, without having to tie the key to the defendant or explaining how it got the key or, indeed, how it knew the defendant used that algorithm. The same argument would not be valid for a one time pad, since it is possible (and easy) to create a pad that converts any given ciphertext into any message of the same length. --agr 13:19, 8 September 2005 (UTC)

Yes, I understand all this. What I was asking about originally is a different matter, namely, can we say that the one-time pad is the only system with Shannon's property of perfect secrecy? Someone went around a little while ago changing various articles to say that the OTP is the only unbreakable system. But there are encryption schemes that have perfect secrecy but which aren't really the traditional one-time pad/Vernam cipher. For example, set the key space to be the same size as the message space. To encrypt, combine the plaintext message with the key using a quasigroup operation. — Matt Crypto 14:06, 8 September 2005 (UTC)

You are right; any invertible function from message space to ciphertext space will do. One can compress the message before it is sent, so the key does not have to be as long as the message. Here's an example. Spys could be trained to memorize up to 52 possible messages, each associated with a playing card. Each spy sent on a mission would be provided with a shuffled card deck whose sequence had been recorded by his handler. A coded message would be a number from 1 to 52. The spy counts that many cards from the top of the deck to decode (or encode) the message. If threatened with capture, the spy simply shuffles the deck to destroy the code. Of course messages could not be sent more than once. --agr 14:51, 8 September 2005 (UTC)

By "any invertible function from message space to ciphertext space will do", I presume you mean that the key is used to select one invertible function from amongst a predefined set? The problem with this is that not every set of invertible functions will provide perfect secrecy. You also need the property that, for any fixed plaintext, there's an absolutely uniform distribution of the ciphertexts when encrypting it with all possible keys. If the keyspace is the same size as the message space, this is equivalent to saying that the key is combined with the plaintext using some quasigroup operation (the combination table forms a Latin square). — Matt Crypto 16:34, 8 September 2005 (UTC)

Common consumer items that can be used to transport one-time pad data.

There is a picture with an Ipod, usb stick, flash memory, and a camera with the statement: “Common consumer items that can be used to transport one-time pad data.”. I hate to be picky, but first off. Why is relevant? Do people not know that you can carry data on electronic devices? It appears to have a POV that these common house hold products are dangerous to security. It isn't like we could have a pen and paper one time pad with in our backpack and do it the old fashion way as it is and even a hammer can become a deadly weapon so why do we need to have a picture of this. And lastly can we really carry a one time pad on a quarter? ;) At least say, quarter shown for reference or something. I'd say pull the picture though.--208.253.80.123 00:42, 10 February 2006 (UTC)

The picture illustrates a point made in the text "The key material must be exchanged securely between the users before sending a one-time enciphered message. Advances in data storage make this more manageable than in the past. Devices like CD-Rs, DVD-Rs, USB keydrives, digital cameras, and personal digital audio players all can hold large amounts of one time pad material, yet attract little suspicion." One could add "Quarter shown for size reference" to the caption, but it seems a bit pedantic; it's a common enough practice and the quarter is identified as such in the image's description. --agr 03:27, 10 February 2006 (UTC)

Requirement of one time use

I am a layman, so perhaps I am just being entirely dense, but I don't think I understand the need for the OTP to be used only once. It seems to me that as long as the pad and plaintext messages are never made known to the "enemy" then you could use the same pad multiple times. Are these conditions not sufficient? I understand that the more you use the same pad, the more chance there would be for someone to discover either the pad or plaintext, but a lot of the article is theoretical, and theoretically I'm not sure one time use is absolutely necessary. Please enlighten me. Sewebster 19:50, 31 March 2006 (UTC)

Well, one time use is absolutely necessary. If a one-time pad is used more than once, simple mathematical operations can reduce it to a running key cipher. If both plaintexts are in a natural language (e.g. English or Russian), and even if both are secret, they both stand a very high chance of being recovered by cryptanalysis, with possibly a few ambiguities. Of course the longer message can only be broken for the portion that overlaps the shorter message, plus, perhaps, a little more by completing a word or phrase. The most famous occurrence is the Venona project.--agr 20:15, 31 March 2006 (UTC)

Data remenance

I don't understand why my assertions about relative data rememance were removed. It matters that the pad might persist for longer than the plaintext; it's a potential disadvantage of using (only) the OTP over (only) conventional PFS encryption. I've re-introduced them and I'm hoping we can discuss it here. — ciphergoth 13:45, 12 May 2006 (UTC)

I think its a minor point and a bit speculative. In general, anyone dealing with crypto has to worry about data remenance for plaintext, private keys, intermediate results and so on. I can see your point that there may be situations where OPT presents more of a remenance problem than PKC, but they seem a bit contrived--people usually want to keep plaintext on file--and they can be overcome by good design.--agr 02:38, 14 May 2006 (UTC)

want to chop a lot of stuff out

The OTP was an important crypto method in the pre-mechanical era and in WW2, and was possibly used for diplomatic traffic as late as the 1960's. But as far as is known, computerized cryptography has completely replaced it now. I'd like to remove the stuff about transporting OTP's on DVD-R's and USB keys and condense the examples of OTP's in operation. Just about any serious cryptographers would have conniptions about such methods. Shred a full DVD into 1mm² particles, and each particle will still contain over 100 kilobits of pad data. USB keys often have write wear levelling. Even with a secure destruction method, physical transportation of the pads is insecure and impractical. OTP's are mostly of historical and theoretical interest, and the article should be written that way. Phr (talk) 10:44, 16 July 2006 (UTC)

Numbers stations suggest otherwise. And, in any case, neither you nor I nor anyone outside the (NSA/GCHQ/DSE/...) fraternity is really up to date about what's being actually used. Computers really do make OTP implementationsmore practical, if only one can pass the key material. If I could be sure about that, I'd prefer the OTP because it's got a serious security proof. I can;t see that your proposed cut will be sensible, except possibly to save a little space on the WP servers. A few K of text isn't that big a deal in that context. Err on the side of completeness in a contorversy, is my suggestion. Our Reader can much more easily gloss over stuff than supply now missing stuff, after all. ww 20:26, 16 July 2006 (UTC)

And now I've just come across your changes today. I think you've added something that I think is probably true, but which we have no justification. That is, that OTP are currently useful mostly in situations which are for some reason (govt edict perhaps) unavailable. It's certainly true, that if you can do it properly, it's the most secure you can use on pen and paper. But it's also more secure, if properly done, than other computer based algorithms. So, I think we ought not to make a claim nobody will admit to who knows more about the secret world than I do. ww 20:53, 16 July 2006 (UTC)

I edited the section in question to add the concern that trustworthy computers may not be available. Given the high rate of infection of typical PCs, even in large organizations, the security of computer based methods is at least open to question. And I put back the point about OTP being the only system with full proof of security. --agr 00:33, 17 July 2006 (UTC)

Arnold, I hope you don't mind, I'm about to move that paragraph out of the "practical" section and into the intro section. OTP's on computers do nothing to prevent security failure if the computer is infected. The infected computer can leak the pad. And the "proof of security" claim simply mentions a theoretical proof (information theoretic or Shannon security) with no clear assertion that it's of valid practical concern. The overwhelming consensus of both the military and civilian crypto communities seems to be that the deployment hassles of OTP's far outweigh any practical concerns about the lack of Shannon security in conventional cryptography, and so real-world crypto organizations appear satisfied with conventional cryptography even for the highest security traffic. That is to say, they don't care about Shannon security in practice. See for example NSA encryption systems as mentioned elsewhere. If you insist on moving the paragraph back, I won't revert again either way, but note that by moving it, you're converting a reasonably valid theoretical claim to a very questionable practical claim. If you do that, I'd appreciate it if you could follow Wikipedia standards by backing up the claim with a verifiable cite to a reliable source on crypto, that asserts that Shannon security is of practical concern to contemporary crypto users. Thanks. -- Phr (talk) 03:20, 17 July 2006 (UTC)

(outdent)

I don't know of any evidence, and I have extreme skepticism, that anyone in the so-called secret world has used OTP's in the modern era because of their theoretically provable security. Their possible use by less-technologically-advanced countries more than two decades ago doesn't show anything. The likely reason for that apparent OTP was so the users could encrypt and decrypt the traffic without a computer. Unless there's evidence that the stuff printed on the paper was truly random and not the output of a computer-implemented PRNG, it can't be treated as a true OTP. And I don't see the slightest reason to think that the numbers station broadcasts are encrypted with OTP's rather than with conventional crypto.

It's certainly well known (i.e. it's not secret) that the US considers conventional cryptography sufficient for top secret traffic, though the actual algorithms are classified--see type 1 encryption and NSA encryption systems. "If properly done" with regard to computer implementation is an extremely big and probably unachievable "if"; it implies perfectly secure handling, transportation, and destruction of the key material, a concept equivalent to the frictionless pulleys of freshman physics class, that doesn't exist in the real world. The US govt, at least, requires hardware crypto implementation for secret traffic. The hardware security requirements are of course classified but they're surely at least as stringent as the civilian standards (e.g. FIPS 140). I've never heard of anyone implementing an OTP with that kind of hardware. The nonsense about transporting pad material on DVD-R's would send any self-respecting crypto spook into convulsions.

Remember also that OTP's don't provide any authentication, something we should mention in the article. There are some theoretical schemes for authenticating OTP's with provable security (we could mention that), but I've never heard of anything like that ever being deployed in practice. The classical OTP (with no authentication) is less secure than anything that would be considered acceptable today.

It'd be irresponsible for us to imply any more than a remote theoretical possibility that any modern crypto organizations that know what they're doing use OTP's for anything today. For that matter, they might theoretically be using telepathic communications. Phr (talk) 04:22, 17 July 2006 (UTC)

How would one encrypt telepathic communications? Interesting conceit that. But off topic. I am in agreement with you as the type of cryptosystem in use in the secret world, but my endorsement is largely irrelevant as, like Sgt Schultz, I know nothing. Adn if anyone who did know, said so, they'd be in trouble. So I'll assume strongly that we're all in this shrouded boat. That being so, we've no grounds whatsoever to make such an assumption as you suggest on behalf of our Reader. We should not what we know, not what you (and I and I suspect agr as well) assume. And recall that the only crypto system both NSA and the Russians could agree on was in fact a teletype one time pad. And that possession of diplomatic puches and armed couriers makes secure key material distribution much much easier for governments. I appreciate your enthusiasm but think it misplaced in this instance. ww 03:33, 17 July 2006 (UTC)

I think it's extremely unlikely that any govt agencies are using telepathic communications and it would be silly for us to indicate that they are, without evidence. It's the same way with OTP's and Shannon secrecy. The reason stated for the US-USSR hotline using OTP's was that they didn't want to reveal their conventional crypto methods. It had nothing to do with Shannon secrecy. Who would they be trying to prevent from cracking the traffic anyway? Each was the other's main adversary in that era, and the hotline was for them to send stuff to each other. Also, that was the 1960's, before the modern (computer) crypto era. We have to distinguish that from any purported usefulness of OTP's today. Phr (talk) 04:22, 17 July 2006 (UTC)

This article is about one-time pads and we are discussing a section on its pros and cons. We should certainly include all the cons but there are pros as well and they should not be excluded. Telepathy is not an apt analogy. There is no scientific basis for it and no evidence that it was ever seriously used for secure communication. There is a strong scientific basis for OTP, arguably stronger than that for any other method. And it was apparently used for highly sensitive intelligence communications by the U.S. until the mid-1950s at least, when the KW-26 was introduced. See http://www.nsa.gov/publications/publi00017.pdf , pages 4, 7. It was also used for the Moscow Washington Hot Line. (It's silly, by the way, to suggest that the leaders of the U.S. and U.S.S.R. would not have cared if their communications were intercepted. In a crisis they would value the ability to communicate in private without even their allies listening in.) Spies are often found with OTPs and the Grenada find was widely reported around October 28, 1983. I'll try to find a more specific cite. Of course we don't know for sure how such pads were produced; they could have been made using a cipher as an RNG, but cryptographers are a pretty conservative bunch.

I agree it appears that the U.S. has long accepted the use of ciphers for even its most sensitive communications. Whether that was wise or not is open to debate. The Walker spy ring was able to smuggle large amount of keying material to the Soviets and compromised a great deal of highly sensitive information in the process. They would have had a much harder time if OTP had been used due to the sheer volume of material they would have had to smuggle out. Regardless, there are now published algorithms that are approved by NSA for Secret (AES-128 and Skipjack) and Top Secret (Larger block size AES) in "approved systems." Others, however, may not accept NSA certification at face value and may lack the ability to certify algorithms on their own. Whether all other nations and groups have eliminated use of OPT seems purely a matter for speculation. We should not imply that they are still used, nor that they are not.

The theoretical security of OTP is a legitimate point to raise in its favor. It is widely mention in the literature. See, for example, Schneier. Applied Cryptography, 2nd ed. pp 15-17. Your claim that no one cares about Shannon security in practice is belied by the significant interest in Quantum cryptography, which touts, among other things, it's ability to "solve" the key distribution problem for one-time pads. If any conventional crypto system had a theoretical proof of security from first principles, even if there were practical caveats, its supporters would cite it as a very major advantage.

The cited section of Schneier also mentions the idea of distributing OTP on CD-ROM. He did not seem to find it laughable, though he does point out some problems, most of which have been overcome by more modern technology. (It was hard to make just two copies of a CD when he wrote, for example. It's easy now.) --agr 18:19, 17 July 2006 (UTC)

I agree that the US used OTP's fifty years ago and that it was sensible then. I'd consider that to be a historical use that should certainly be cited as one. The section about practical use, I thought, was about practical use in the modern era. Swords have been an important military weapon throughout a lot of history but are practically zero importance today. An article about swords might discuss history extensively but should certainly not give the impression that the US Marines still use them in combat today. It's the same way with OTP's. We have a situation in cryptography where a lot of amateurs think that OTP's are of practical superiority to regular ciphers, because of OTP's theoretical Shannon security; but this is sort of like amateur military buffs who think that swords are better than guns because swords never run out of bullets or jam. Actual military organizations in the real world don't find that advantage compelling enough to even think about replacing guns with swords.

I'd like to know more about the Grenada codebooks found in 1983. Even that, though, was over 20 years ago, an eternity in this business. We were still in the DES-paranoia era then. My copy of AC2 is in storage so I can't check pp. 15-17--what does it say? Schneier's Crypto-grams column has a good essay about OTP's: [1].

Walker also operated in the 1980's, handing over photos of printed key lists for 1950's-vintage mechanical and vacuum tube cipher machines that are ancient by today's standards. Nowadays there aren't any such lists; the keys always live in tamper-resistant hardware and humans can never see them. And of course, if public-key is used, the secrets live only in the end nodes, so there's not any distribution system like the one Walker compromised. OTP can never accomplish that.

I don't think there's that much practical interest in quantum key distribution for now. It's just research. As for provable security, sure, it would be of great practical interest to have a provably secure cipher if the provable security came without practical cost. OTP's have enormous cost. We actually have provably secure stream ciphers (up to the difficulty of integer factoring), e.g. Blum-Blum-Shub, but nobody uses them because they're too slow, even without the key distribution hassles of OTP's. Phr (talk) 23:19, 17 July 2006 (UTC)

If swords were a bit tricky to use but when used properly could stop a tank, they might still be taken seriously. (And every soldier is still taught to use a bayonet.) It is certainly true that many if not most professional cryptographers look down on OTP. But it is not entirely an amateur/professional divide. A couple of companies have formed to sell quantum cryptography and I believe the EU is supporting the work. And I know several professional mathematicians who are amused by modern cryptography's reliance on unproved assertions, e.g. "up to integer factorization." I think the current article presents the majority, cautionary opinion quite forcefully. I've tried to strengthen some of that text myself. Maybe more should be added. But there is another point of view, amateur or not, and its legitimate points deserve mention.

After it invaded Granada in October 1983, the U.S. announced it had found a Cuban warehouse on the island with various weapons. President Reagan gave a speech mentioning the find around Oct. 27. Among the material found was a supply of new code books in pairs that appeared to be one-time pads. I recall seeing a photo at the time, either in the NY Times of maybe Aviation Week. Schneier's section on one-time pads starts out "Believe it or not, there is a perfect encryption scheme." He goes on to explain the method and its history and adds the usual cautions about the difficulty of generating random bit streams, securely transporting large amounts of data and the importance of using keying material only once. He also mentions the lack of authentication. He ends by saying "One-time pads have application in today's world, primarily for ultra-secure low bandwidth channels", mentioning the Hot Line and pointing out that messages encrypted this way "are still secure today and will remain that way forever."

Your certainty that there aren't human-accessible keys may be premature. There is a fair amount of material on the Internet, originally from government web sites, about NSA's Electronic Key Management System, which is a project underway to eliminate the need for physical keys. The material suggests that paper tape keys (cipher keys, not OTP) were still in use at least as of 2000 on legacy systems. Apparently many of the key fill devices in use cannot handle "modern" 128-bit keys, but the KOI-18 paper tape readers can. Maybe they are no longer used today, but it's hard to get budget for replacing stuff that still works. --agr 13:52, 18 July 2006 (UTC)

Terminology confusion - proposal

Part of the confusion and disagreement here in the talk page is that the article uses OTP to mean two different things in different places. I propose that we update the article to carefully distinguish:

1. Use of a one-time additive keystream (for example printed on paper) for encryption, where the keystream comes from some (possibly unknown) random or pseudorandom source. For example, Alice and Bob might meet at a secure location, generate such a keystream on a computer using AES-128 in counter mode, and print out two copies for later use in the field. This does not assert information theoretic (Shannon) security, although if AES meets its intended security criteria, there is no practical way for an attacker to tell the difference. I propose that we try to consistently refer to this in the article as a "Vernam cipher" or something equivalent TBD, and not as an OTP, since the "security proof" frequently associated with OTP's does not apply here.

But it's not a one-time pad, just an approach to it. ww

1. Use of such a keystream where each symbol in the keystream is generated independently by some physically random process (subject of course to a lot of discussion of what constitutes a physically random process, or whether physically random processes exist at all). This is supposed to provide information-theoretic (Shannon) security, so maybe we can refer to such a keystream in the article as a Shannon OTP, and reserve that term specifically for an OTP generated by such a process.

Let me know how this sounds. -- Phr (talk) 03:35, 17 July 2006 (UTC)

Not sure I like Shannon OTP, though I agree it makes a distinction which seems useful to make. But we're not supposed to be inventing terms here -- however sensible, as this is WP. So I think it's a non-starter. But he distinction you not should be made very clear, and if it isn't so made, I think we are under an obligation to make it so. ww 20:58, 17 July 2006 (UTC)

I agree that the term OTP is incorrect, and that some permutation of "Vernam," "Mauborgne," "cipher," "streaming," and/or "random" is more correct. The only people I have ever met who use the term OTP are academics and dilettantes--the professionals I have known never used that term. The main entry, much of which is copied from the article "Re-visiting the One-Time Pad," by Nithin Nagaraj, Vivek Vaidya and Prabhakar G Vaidya, seems stuck on using the term OTP, which is childish. firmDoc 13:43, 12 April 2007 (EDT)

numbers stations

The content of these stations may indeed by OTP encrypted stuff, though I understand they are often high powered which suggests the spyies aren't doing so. What seems to be the general suspicion is that they are key material. Rabin proved (April of 2001?) that entropy can be preserved in a public broadcast like this, though I seem to remember these stations existed long before. So, in this reading, the spies are actually sending in OTP encoded stuff, maybe on flash paper like the Krogers or Col Able, etc.

Or maybe the entropy inthe broadcast stream is used to seed a more conventional crypto system? Not being of the secret world, we are left only sepeculaiton. Which is fair game for WP, if identified as such. ww 20:58, 17 July 2006 (UTC)

I have no inside information, but I do not believe there is any real mystery about the function of these atations. The most natural understanding is that that are sytems for sending untracible coded mesages to recipients anywhere in the broadcast coverage area, often world-wide. The reason for the constant flow of numbers or letters is to achive what NSA calls traffic flow security, i.e. no adversary can determine when or how often messages are sent. That means most of the time the numbers are meaningless and likely purely random except that certain combinations are avoided at certain times, unless a message is actually pending. These combinations serve as addresses. Recipients are given time to listen in and, if they hear the number pattern assigned to them for that session, they copy the remaining numbers, perhaps to an end signal. Those numbers are then decoded, likely with a pad, though possibly these days with a computer program running on their cell phone or gameboy. Messages might also be simple codes, like "go to the secondary meeting point tomorrow." The obvious users would be spys, but it also could serve as a backup for embassies, offices and the like, and even military units.--agr 15:26, 19 July 2006 (UTC)

von Neumann whitening

That just doesn't seem so great an entropy distillation method. It only works if the input bits are independent and are all drawn from the same probability distribution. Both of those seem like unrealistic assumptions. We want some function that maps an input string to an output bit, where if the input string is S assumed to have min-entropy > H, then

$|\Pr[H(s)=1]-0.5|<2^{-O(H)}$

There is some literature about how to do stuff like that, maybe with universal hashing. I'll see if I can find a reference. Phr (talk) 00:04, 18 July 2006 (UTC)

NP vs P double speak

It is very annoying when a Wikipedia article says one thing and then directly contradicts it. Either the NP/P problem is relavent to the security of the best encryption algorithms or it isn't. Please clear this up.

On another note, it sounds silly to say 'most informed observers believe' when what is being 'observed' is mathematical. This is one of those great unsolved problems, and nobody can offer a proof just from 'observation'. Of course common sense tells even the CS undergraduate that N and NP are almost certianly not the same, but there is no proof. This really needs to be rephrased.

The main problem I find is that the article says (i paraphrase) 'NP=P would just destroy all encryption algorithms, zomg' and then tacked onto the end says 'From what I observe NP=P isn't that likely, but even if it was, who cares, it isn't relavent'.

Which is it?

Ok, not a good paraphrase, I'm just tired. Please take this as the tongue in cheek, seme-serious, latenight arm-chair wikipedia punditry that it is :P

—The preceding unsigned comment was added by 70.186.18.164 (talk • contribs) 07:01, 6 August 2006 (UTC2)

P vs NP is one of those conjectures like Fermat's Last Theorem and the Four Color theorem, where just about everyone always believed both were certainly true, but it took a very long time and an enormous amount of new technical machinery to come up with formal proofs. And even if P=NP so there's a P-time cryptanalysis to (say) an AES-like block cipher with an n-bit key and block size, if the best possible running time is O(n⁶⁰⁰), that's still good enough for practical cryptography, especially if that lower bound can be proven. Does that help? Phr (talk) 09:10, 6 August 2006 (UTC)

More precisely, if you have known plaintext or even some way to test if a decryption is plaintext (which you usually do in practice if the plaintext is a natural language and is long enough) then AES-256 can be broken in under 2²⁵⁶ steps, where the length of each step can be specified exactly (no "big O" required). In other words, AES-256 is in the class of constant time problems C, which is a subset of P. (Of course 2²⁵⁶ is so large that this attack cannot be performed by any known technlology.) I agree with the annon user that the P vs NP discussion should be removed.--agr 12:15, 6 August 2006 (UTC)

AGR, Perhaps this discussion is obscure, and hard to follow, but the basic point -- that there might someday be termites in the crypto foundations -- is one worth making. Even if it's somewhat squishy adn not so easily provable (ie, mathematically) as the anon poster hoped. Crypto really is a bit of odd duck, neither mathematical fish, nor merely practical. that's a point worth making here at WP. Clarity is of course a good thing in this as in the rest of the article. ww 04:32, 7 August 2006 (UTC)

I agree your point should be made, but I don't think a discussion of P vs NP is the best way to make it. A proof that P = NP is not likely undermine the foundations of cryptography. If anything Wiles' proof of Fermat's Last Theorem has a better chance of having an impact, since it includes some deep results about elliptic curves. It might help to beef up the Cryptography section in List of open problems in computer science so we could reference it.--agr 16:00, 7 August 2006 (UTC)

Unbreakable

Re:

• The one-time-pad is the only cryptosystem proven secure. Though most experts have confidence in standard cryptosystems for practical purposes, one cannot be certain that a future cryptanalytic breakthrough, or a breakthrough in computer hardware such as quantum computing, will not render them breakable.

Isn't the quantum cipher also proven unbreakable (well, in the sense that no message encrypted with it can be read)? Or is that the wrong sense of the word...? --Katrielalex 13:08, 12 September 2006 (UTC)

K, "The quantum cypher" is sufficiently indeterminate that no answer is possible. On the other hand, quantum transmission of data can be -- at our present understanding of quantum phenomnea -- untappable without detection. This is a moderately high standard for confidentiality if not for cyptography or encryption, and unless new understanding comes, could be thought unbreakable. But, more or less, you're correct it's a misuse of the term. Unbreakability is generally understood to be the reversal of an encryption of some sort.

In the case of the one-time pad, Shannon's proof is based on theory of communication considerations and is nearly universally thought to be fundamental. ww 14:58, 12 September 2006 (UTC)

There is no "quantum cipher" per se. Quantum cryptography provides a way to securely send a random stream of bits from one location to another. Those bit streams can then be used as a one time pad, or they can be used a a list of keys for conventional ciphers.--agr 20:17, 12 September 2006 (UTC)

The best way of expressing the security of the one-time pad is as "unconditionally secure", which in the cryptographic literature is also referred to as "information theoretically secure". It is misleading to say that the one-time-pad is the "only" secure scheme. There is a whole field of "information theoretically secure" cryptographic primitives. Other examples include Shamir's secret sharing scheme, and the privacy of Chaum's blind signatures. "Unconditionally" refers to the fact that the security of the OTP does not require reduction to another problem that is assumed to be hard (such as the security of block cipher, hash functions, the hardness of factoring or the discrete logarithm problem.) 82.6.104.167 (talk) 23:50, 28 November 2007 (UTC)

You are certainly correct in a technical sense. The sense the article seems to working from is more popular however. a cypher encrypts, is it possible to break it? Except for teh one-time pad (and equivalents under another name or style) is unique in that all others include some something less than complete independence from one bit to the next. So in that limited sense, unbreakable in terms of the question in the back of people's minds. But the technical qualiification you note is either more than a Reader can expected to cope with or soemthing we editor should add to the article in such clear lucid prose that even our Reader will get the idea, subtle and technical though it may be. I favor the latter, rather than tripping over the slightly different meanings of common workd use and technical word use. Be bold and have at it! ww (talk) 18:31, 29 November 2007 (UTC)

Just Wondering

I was wondering why this article mentions the Vernam cipher as the basis of the one-time pad, and not the Vigenère cipher. The example given on this page works out when using the Vigenère cipher and not what is described on the Vernam cipher page. Also, in The Code Book by Simon Singh specifically mentions the Vigenère cipher when explaining the one-time pad cipher, and I don't remember the name Vernam being mentioned at all in the book. The page for the Vernam cipher doesn't really explain it much beyond that it is "applied to the individual impulses or bits used to encode the characters" and giving an example where a plaintext of "A" and a key of "B" give a ciphertext of "G", while the example on this page just uses the characters themselves. So is there a reason Vernam is mentioned here and not Vigenère?

You can do one-time pad using lots of operations (any old quasigroup will do), but the Vernam 5-bit-wide addition was the first known implementation (and was very common in real world systems). — Matt Crypto 07:02, 4 October 2006 (UTC)

Yeah, this is unclear in the article. What opperations can you use? what are the qualifications for it to be unbreakable? Can somebody explain and perhalps put it in the article? King Mir 21:34, 11 November 2006 (UTC)

AFAIK, a simple modular addition is always used. XOR is a modular addition too. There is no need to use a more complex operations, it would only bring the possibility of more bugs. Touisiau 12:01, 15 November 2006 (UTC)

Repitition

The article contains a lot of the same information several times over (such as its inventors and early users, and its level of security). Some serious rationalization is needed. --88.111.41.106 00:15, 21 November 2006 (UTC)

One time pads from Digital Cameras

In one aspect the use of one time pads has become relatively more practical. In prior years the generation of a one time pad required some source of truly random data. This called for some specialized hardware, not commonly available (though potentially simple). Common use of digital cameras offers a large amount of data with a significant random component. A simple flash drive full of photos can serve as a one-time pad (with a bit of light shuffling).

There is some merit in waving around a camera, handing out a flash drive, then knowing you can send data in complete security (up to about the size of the flash memory).

Photographs are not truly random data. — Matt Crypto 21:34, 2 January 2007 (UTC)

The less-significant bits of each pixel have a strong random component (otherwise known as "noise"). You want uncompressed (i.e. "raw") not compressed images to keep the noise. Using just the low-bits, what you have in effect is a hardware "noise" generator. The rarity of hardware noise generators for the generation of one-time pads is one main reason this technology was generally impractical. pbannister (talk) 23:48, 28 July 2008 (UTC)

Low order bits from a digital camera may be a good source of noise, but that doesn't mean they can be used directly as a OTP. One would have to demonstrate that they are uniformly distributed and uncorrelated. Applying a whitener may yield a suitable random bit stream, but that can also be done with other sources, such as audio input. I would not agree that "rarity of hardware noise generators for the generation of one-time pads is one main reason this technology was generally impractical." Modern cryptographic protocols are considered more convenient, though they also require good sources of randomness. Most users simply don't care about the added provable security OTP offers.--agr (talk) 23:52, 29 July 2008 (UTC)

Perhaps I should re-phrase. OTP is only practical for some (certainly not all!) use-cases. For the remaining cases, you need a source of real-random data (not pseudo-random data) for the generation of one-time-pads. First time I read up on crypto (mid-1980's), you needed specialized hardware (rare and $$$) to generate and capture white-noise. Even for those use-cases where the shipment of pads was not a problem, the need for specialized hardware pretty much made use of OTP largely impractical.

What was then hard is now easy. A memory card full of raw (not compressed) images could serve (with suitable processing) as a one-time-pad. There is an easy use-case. You go on a trip, take pictures, leave behind a copy of your memory card, then go home. All very ordinary and innocent ... but now you can exchange OTP encrypted data with whomever you gave copy of your memory card (for data up to about the size of the memory card). pbannister (talk) 17:49, 8 August 2008 (UTC)

Computer have had audio digitizers since the late 1980s (e.g. sound blaster cards) which also provided a good way to capture noise. The "(with suitable processing)" step is a bit dodgy. I'm not sure there is a proof that a particular algorithm applied to the output of a digital camera is equivalent to a perfectly random bit stream, tho empirically cryptographic hash operating on a block of image data with a surfeit of entropy compared to the hash output size, say, should work fine. See extractor and the survey referenced there. --agr (talk) 22:23, 10 August 2008 (UTC)

By "dodgy" do you mean possible to do wrong (agreed), or do you mean that you cannot imagine any workable solution? --pbannister (talk) 18:24, 28 August 2008 (UTC)

There are lots of solutions that I would consider workable, the problem is proving mathematically that they work.--agr (talk) 19:08, 28 August 2008 (UTC)

Explanation of Modular arithmetic.

Sorry, maybe I'm being stupid but shouldn't

Note that if a number is larger than 25, then in modular arithmetic fashion, the remainder on division by 26 would be taken. This simply means that, if your computations "go past" Z, you start again at A.

be

Note that if a number is larger than 26, then in modular arithmetic fashion, the remainder on division by 26 would be taken. This simply means that, if your computations "go past" Z, you start again at A.

Because if you get a 26 thats a Z.

Perhaps I'm wrong, if so, sorry.

--Danielcoulbourne 02:16, 14 May 2007 (UTC)

The math is simpler if you start counting from zero. If you look a bit earlier in the article, you'll see it says:

"A" is 0, "B" is 1, and so on through "Z", 25.

That's why the first version of the text you quote is correct.--agr 03:07, 14 May 2007 (UTC)

There's another problem: You never "divide" by 26; you subtract 26. I've changed the text from "the remainder on division by 26 would be taken" to "the remainder after subtraction of 26 is taken." 129.170.204.153 (talk) 22:53, 1 June 2008 (UTC)

One time pad programs

I don't think we should be listing so-called one time pad programs in the links section. The hard part of using OTP is generating random pads and managing them properly. Programs that just combine pad and message, which is generally the case, are essentially trivial and not worth much. Programs the generate pad material require careful audit which is beyond Wikipedia's scope. --agr 17:41, 18 May 2007 (UTC)

I agree. Moreover, implementors of one time pads are often not aware that one time pads do not provide authenticity. At least one of the implementations on this page was not even a proper one-time pad. The other link was badly documented and thus had not even educational value. 85.2.22.56 17:53, 18 May 2007 (UTC)

Yes using a one time pad program can give the user a sense of security that is not present.

The reson why i restored the link is that it demonstrates it's use.

This inspires me to make a flash program to demonstrates it's use (and pitfalls). —Preceding unsigned comment added by Foton40 (talk • contribs)

Provable security

Provable security is often understood as secure against adaptive chosen-ciphertext attacks, which implies non-malleability. One-time pads are malleable. Hence claims that the one-time pad is provable secure is misleading. One-time pads just have perfect secrecy. These two security notions should not be confused. 85.2.86.69 07:01, 12 June 2007 (UTC)

Adaptive chosen-ciphertext attacks are a vulnerability of asymmetric algorithms. I don't see how they would work on an OTP. The article does point out that OPT is malleable, tho we don't currently use the term (we should).--agr 22:32, 12 June 2007 (UTC)

Yes, of course. For 'provable security' of symmetric cryptosystems we also must make sure that chosen plaintexts are not helpful to a potential attacker. A chosen-ciphertext attack against a OTP is simple in theory. An attacker, who has a ciphertext c chooses a random pad r then sends c xor r to the receiver and gets the decryption of c xor r from which the attacker can derive the original message. Whether such an attack can be pulled off in practice is another question, which depends on the protocol that is used. My only point was, when people talk about 'provable security' today then they usually talk about a security notion that is much stronger than just 'perfect secrecy'. Otherwise the article did a good job at explaining the strength and weaknesses of the OTP. 85.2.117.213 08:42, 13 June 2007 (UTC)

The cryptographic community has a nasty habit of defining terms in misleading ways that would shame a consumer marketing executive. The current definition of provable security does not include a proof that the method is secure, merely that is it polynomial equivalent to a problem that is commonly thought to be hard. OPT's proof of security does not depend on this loophole. "Provable security" also excludes absolute deniability as a criteria, even though it is desirable in practice, because no modern cipher can meet that test. But OTP can. So I think it is best to avoid jargonized labels in the article altogether and simply present the facts.--agr 15:35, 13 June 2007 (UTC)

The crypto community isn't that bad. Most papers that propose new schemes exactly describe the properties that are shown and the assumption that were made. The problem is more the term "provable security" itself. It does not have an exact definition. "Provable security" is more a set of unwritten expectations, but these expectations change over time and are often misinterpreted. I certainly agree that the term should be avoided and replaced with more precise statement. 85.2.120.114 08:55, 15 June 2007 (UTC)

one time pad picture

Anyone else find the picture of the one time pad a bit naff? It's just random data (apparently), which is only a one time pad if used as such. Not to mention it being a picture of some text... How about a diagram of the (admittedly trivial) encryption process instead? AbleRiver 15:51, 31 August 2007 (UTC)

I agree that the picture doesn't really add much to the article -- even if it was key generated using a deterministic algorithm we'd be none the wiser. A diagram of the encryption process would boil down to "plaintext + key = ciphertext"; which would be fine, I suppose, but would also do for general symmetric encryption. Ideally, we'd have a photo of some historic one-time pad material. — Matt Crypto 19:21, 31 August 2007 (UTC)

Perfect secrecy

An incorrect claim keeps coming back in different formulations. E.g.:

And in fact all plaintexts are equally probable.

To a cryptanalyst, no possible decryption is any more likely than any other; the worst of all possible situations.

Thus it seems necessary to discuss this here with more details. It is quite important to understand that a cryptanalyst may and usually does have some information about the plaintext. For example the cryptanalyst might know (or guess) that the sender and receiver are speaking English and that they exchange text messages. The cryptanalyst might even have some known plaintext (e.g. standard header, closing, etc.). Thus, it is not true that all plaintexts are equally probable. Some plaintexts are clearly more likely than others. Furthermore, the cryptanalyst will try to exploit any a priori information on the plaintext to decrypt a cipher text. The main point behind perfect secrecy is that the ciphertext does in no way help the cryptanalyst to extend his/her knowledge about the plaintext (other than possibly its length); even under the assumption that unlimited computational resources are available. 85.2.88.244 09:28, 18 October 2007 (UTC)

85.2, Yes, it's probably good to discuss it here.

What you've noted above is just that which is essentially the point the text(s) you object to attempts to make. Pure cryptanalysis provides no purchase on a correct decryption, because of the equi-probablility of all texts. Successfully breaking a one time code message requires additional information, and even if a crib is available and helpful, the next character in a properly protected message will be independent of those in the cribbed portion. Your perspective is slightly skew to the point being made. Form the perspective given, the text and its replacement are actually correct. ww 04:39, 19 October 2007 (UTC)

Again, assuming "equi-probability" of plaintexts does not make a convincing argument. So the goal is to show the statistical independence between plaintext and ciphertext. Claiming that for a given ciphertext all plaintexts are equally likely is at least confusing. Rather one should argue that for a given plaintext all ciphertexts (of equal length) are equally likely. This would imply that the distribution of ciphertexts does not depend on the plaintext and therefore the ciphertext does not give information about the plaintext. More formally, we want to show that $P(M)=P(M|C)$, i.e., the probability of a given plaintext $M$ does not depend on the ciphertext $C$. Using Bayes' theorem this is equivalent to $P(C)=P(C|M)$, i.e., the probability of a given ciphertext $C$ does not depend on the plaintext. Moreover, since for every pair $(C,M)$ there is exactly one key encrypting M to C it can be shown that $P(C)=P(C|M)=2^{-n}$ where $n$ is the length of the message. 85.2.9.211 08:36, 19 October 2007 (UTC)

Scrabble

Why's there a picture of the full Scrabble set when it says you should only use 1 of each letter 15:32, 19 December 2007 (UTC)15:32, 19 December 2007 (UTC)15:32, 19 December 2007 (UTC)15:32, 19 December 2007 (UTC)15:32, 19 December 2007 (UTC)15:32, 19 December 2007 (UTC)66.254.246.198 (talk) 15:32, 19 December 2007 (UTC)