Talk:One-time pad/Archive 1

From Wikipedia, the free encyclopedia

You have new messages (last change).
Archive This is an archive of past discussions. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page.

Contents

Distinction between OTP and stream ciphers

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: Image:One_time_pad-charA.png
an example pad: Image:One_time_pad-Pad1.png
result of encryption: Image:One_time_pad-charA.png XOR Image:One_time_pad-Pad1.png = Image:One_time_pad-charAenc.png
decryption: Image:One_time_pad-charAenc.png XOR Image:One_time_pad-Pad1.png = Image:One_time_pad-charA.png
a false pad: Image:One_time_pad-Pad2.png
decryption with false pad: Image:One_time_pad-charAenc.png XOR Image:One_time_pad-Pad2.png = Image:One_time_pad-chare.png

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)
Retrieved from "http://en.wikipedia.org../../../o/n/e/Talk%7EOne-time_pad_Archive_1_2c8f.html"