Talk:Vernam cipher

From Wikipedia, the free encyclopedia
Jump to: navigation, search

(Moved from User talk:ArnoldReinhold)

Why did you make Vernam cipher a redirect? This form of stream cipher is very popular and deserves an article of its own. The problem at the moment is that stream cipher seems to be partially written to suggest that all stream ciphers are Vernam ciphers; an article specifically to address Vernam ciphers seems like an essential part of fixing this. ciphergoth 16:44, 2004 Nov 23 (UTC)

Yeah, I think moving material in the other direction might be a better solution, that is, trim down the discussion of the details of the Vernam cipher in Gilbert Vernam and have it in Vernam cipher instead; Gilbert Vernam can then focus on being biographical. — Matt 17:01, 23 Nov 2004 (UTC)

I was working on the Gilbert Vernam article and I don't think there is enough material for two articles and also the material in each article seems very relevant to the other. I wouldn't argue with Vernam cipher being the main article and Gilbert Vernam the redirect. Then if there is more biographical info on him, that could be expanded. What distinction you (ciphergoth) want to make between stream cipher and Vernam cipher? Vernam's patent arguably covers all electronic stream ciphers. But whatever clarification is needed could be made in either place. --agr 17:12, 23 Nov 2004 (UTC)

A stream cipher is any cipher that can encrypt a variable length message. WAKE is a stream cipher; CBC mode constructs a stream cipher from a block cipher. A Vernam cipher is a stream cipher that XORs the plaintext with the output of a CPRNG. A Vernam cipher is provably as strong as the underlying CPRNG; if the CPRNGs output cannot be distinguished from random, then no information about the plaintext can be recovered. ciphergoth 20:55, 2004 Nov 23 (UTC)
Hmm...I'm not sure about this definition. A block cipher in ECB mode can encrypt a variable length message too, but it would be quite unconventional to describe it as a a stream cipher. In AC, Schneier goes for the definition of "Stream ciphers convert plaintext to ciphertext 1 bit at a time". — Matt 21:48, 23 Nov 2004 (UTC)
Well RC4 doesn't operate one bit at a time. I'd define a stream cipher as an algorithm the produces a string of bits equal in length to the plaintext to be combined with the plaintext it some reversable way producing ciphertext. It doesn't have to be XOR. A varient of RC4 where the cipher byte and the message byte are added mod 256 instead of XOR'd would still be a stream cipher in my book. And I can't see much daylight between any electronic stream cipher and what Vernam patented.--agr 05:16, 24 Nov 2004 (UTC)
ECB isn't a secure stream cipher so it doesn't see much discussion, but yes, it's increasingly common to refer to a chaining mode as a way of constructing a stream cipher given a block cipher. The reason is that this way, the phrase "stream cipher" can be given a precise mathematical meaning that can be reasoned about; we can define what a secure stream cipher is, and then prove that (eg) CBC or CTR mode construct a secure stream cipher given a secure block cipher. Equally, a Vernam cipher is a stream cipher constructed in a particular standard way from a CPRNG, and you can prove that a secure CPRNG results in a secure stream cipher. Applied Crypto was a groundbreaking book but the field has advanced a long way since then, and in large measure because of formalisations like this. ciphergoth 11:49, 2004 Nov 24 (UTC)
See Jovan Dj Golic, "Modes of operation of stream ciphers", SAC 2000 [1]: "If a block cipher is used for encryption in one of these modes with memory, it then essentially becomes a stream cipher whose next-state and/or output functions are determined by the secret-key-dependent encryption and/or decryption functions of the block cipher. ciphergoth 12:05, 2004 Nov 24 (UTC)

The quesion, I think, should be what do we want to say in the Vernam cipher and Stream cipher articles. My view is that Vernam ought to be credited with inventing the electronic stream cipher (and perhaps not the one time pad). If there is a widely recognized distinction between Vernam cipher and stream cipher other than the use of electrical impulses (vs. paper and pencil or mechanical devices), I'd be interested in hearing it. -- 00:33, 25 Nov 2004 (UTC) a.k.a. --agr 00:36, 25 Nov 2004 (UTC)

WAKE is a stream cipher. It is not, however, a Vernam cipher, because the output of the CPRNG depends on the plaintext. ciphergoth 10:18, 2004 Nov 25 (UTC)
By contrast, SEAL is a Vernam cipher, because it generates a keystream which is independent of the plaintext and XORed with it. The paper supports my usage, see the abstract: "under control of a key [...] it stretches a 32-bit position index into a long, pseudorandom string. This string can be used as the keystream of a Vernam cipher." (Rogaway, Coppersmith, 1998 "A Software-Optimized Encryption Algorithm" [2]). Unless someone shouts, preferably with cites from the literature showing contradictory usage *and* arguments why perferring other usage would make the encyclopaedia clearer and more consistent, I shall re-instate "Vernam cipher" and edit in favour of these definitions of stream cipher and Vernam cipher in the next few days. ciphergoth 11:44, 2004 Nov 26 (UTC)
I agree, although I have an alternative suggestion. I had a look at the forthcoming "Encyclopedia of Cryptography and Security", and they had definitions roughly as follows:
  • Vernam cipher — XOR on groups of 5-bit words, key should be completely random; alternatively, they equate the Vernam cipher with the one-time pad.
  • Stream cipher — a cipher which operates with a time-varying transformation on individual plaintext digits; or more precisely, as a cipher using a keystream whose ith digit depends on the secret key and the i-1 previous plaintext digits.
  • Synchronous stream cipher — the keystream is generated independently of the plaintext and ciphertext.
  • Self-synchronising stream cipher — the keystream depends on the key and a fixed number of previous ciphertext digits.
However, it seems people sometimes use Vernam cipher to mean 1) even non-random keys combined in groups of 5 bits; 2) same as the definition for "synchronous stream cipher" above. People also seem to often assume that "stream cipher" implies "synchronous stream cipher" because most of the designs are of that form. And, of course, the snake oil people are quite fond of calling any kind of cipher a "one-time pad", but I assume we can ignore that for now ;-) (And don't forget Simple XOR cipher...!)
Because "Vernam cipher" has a fuzzy meaning (at least in the way people use it), perhaps we could make Vernam cipher a redirect to synchronous stream cipher, and describe the general concept there? — Matt 13:14, 26 Nov 2004 (UTC)
Sounds good to me - I didn't know that term, it's good and useful (if a bit longer). We can say that some people mean a SSC when they say "Vernam cipher" and some mean a one-time-pad... ciphergoth 15:17, 2004 Nov 26 (UTC)
I agrre, but I'd be inclined to add "Synchronous stream cipher", "Self-synchronising stream cipher" and maybe "Vernam cipher" as headings under Stream cipher, rather than separate small articles that are unlikely to be expanded. --agr 22:43, 27 Nov 2004 (UTC)
Fair call. ciphergoth 01:42, 2004 Nov 28 (UTC)