3
$\begingroup$

How would one classify a stream cipher that is neither synchronous, nor self synchronizing? I would have thought asynchronous, but from all the sources I can find, asynchronous is synonymous with self synchronizing.

The internal state of the cipher is initialized by a key and initialization vector. The internal state is modified depending on the current internal state, and the previous byte of plain text. The cipher does not synchronize after a fixed number of bytes. Error propagation is unlimited, so corruption of one byte of cipher text makes the rest of the message undecipherable.

I would like to know the correct classification of the cipher.

Thanks to @otis and @kodlu, who suggested the terms synchronous and additive. Searching those terms has led me to this article, describing nearly exactly what I am after. On page 244, I paraphrase, where W [...] is the running key sequence and where we allow W, to depend both on the secret key (as is customary) and on [all prior bytes of] the plaintext. This article is heavy on the maths and terms, so many of which I need to look up to understand their meaning. I am still working through the terms used in the article, which is why I have not proposed an answer to my own question. I am posting this source, because it might be helpful to someone with a stronger background to answer the question.

| improve this question | |
$\endgroup$
  • $\begingroup$ Actually there are several ciphers that work similar in practice, except that they depend on blocks of prior bytes, rather than individual prior bytes. See NORX for example $\endgroup$ – Richie Frame Feb 2 '16 at 2:58
  • $\begingroup$ Why would such a cipher be impractical? When analyzing it, we would need to consider chosen plaintext attacks (which just don't come up with an additive stream cipher), but that wouldn't be enough to immediately disqualify it. As for the lack of synchronization, we typically don't care about that; we encrypt entire messages, and try to reject them unless we get the entire message unmolested. $\endgroup$ – poncho Feb 2 '16 at 4:54
  • $\begingroup$ @poncho: Instead of is impractical, perhaps I should have said could be argued that it is, or maybe better just left that statement out. I didn't mean to raise an off topic discussion about a controversial statement. I was rather hoping to avoid this discussion by preacknowledging a criticism that I anticipated. $\endgroup$ – alpha_numeric Feb 2 '16 at 13:34
  • $\begingroup$ is it an additive cipher? is the current output a function of current internal state? $\endgroup$ – kodlu Feb 2 '16 at 14:08
  • $\begingroup$ @kodlu: Additive is an independent classification, I think. Synchronous and asynchronous stream ciphers could also be classified as additive. For example, binary additive would indicate that the cipher gamma output is combined by xor with the plain text to produce the cipher text. I am asking for a different classification, not of how cipher text is produced from the plain text and gamma, but of how gamma is generated from key, iv, and plain text. $\endgroup$ – alpha_numeric Feb 2 '16 at 16:42
3
$\begingroup$

Logically I think that should also be a synchronous stream cipher. The word refers to the fact that the keystreams must be synchronized between the encrypter and the decrypter to allow decoding. With anything other than a self-synchronizing cipher that is the case.

However, that does not mesh with existing usage. You will find many texts (example) saying that with synchronous stream ciphers the keystream is independent of the plaintext and ciphertext. So you should definitely not use that term.

Asynchronous is not very good either, for the reason you mention, but you will find it used to describe such ciphers (e.g. Helix here, pdf). So that is probably more understandable than calling them synchronous, even if it too can be confusing.

If you need to write about it, I would avoid the issue and just call it a stream cipher with a plaintext-dependent keystream. You can say that it is not self-synchronous if you need to make that distinction.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks @otus. As you point out, literature largely agrees on the definition of synchronous, that it is independent of the pain text and cipher text. I have seen helix described as neither synchronous nor asynchronous (page three), so it is a valid suggestion to use such a phrase when writing about it. It's not a truly satisfying answer to the question, but maybe the best that can be given. I will consider this, if there is no more satisfying answer. $\endgroup$ – alpha_numeric Feb 4 '16 at 15:02
  • $\begingroup$ @kodlu mentioned the term additive. What about non-additive synchronous stream cipher? This (page 5) talks about CBC mode being non-additive. CBC is self-synchronizing, because it can be synchronized mid-stream from the previous cipher text block. I'm asking about an algorithm that is not self synchronizing, so maybe it is synchronous, logically as you say. It is also not additive, because the key stream is not simply added to, but also depends on, the plain text. Is that the correct usage of the terms, or did I screw up non additive? $\endgroup$ – alpha_numeric Feb 4 '16 at 18:20
  • $\begingroup$ Second thought, maybe CBC is non-additive because the cipher text is the result of block cipher encryption, not simple addition of a key stream. $\endgroup$ – alpha_numeric Feb 4 '16 at 18:22
  • $\begingroup$ @alpha_numeric, exactly, I think Bernstein uses "non-additive" to mean the plaintext is not combined using addition (XOR being addition mod 2), but something that requires a different operation to undo. $\endgroup$ – otus Feb 4 '16 at 20:02
  • $\begingroup$ @alpha_numeric an example of non-additive would be a byte of keystream used to choose one of 256 s-boxes, and the plaintext is then run through the s-box $\endgroup$ – Richie Frame Feb 4 '16 at 20:34
0
$\begingroup$

I would be inclined not to even call it a stream cipher. If I had to give it a name, it would be reactive encryption algorithm or perhaps forward reactive encryption algorithm. This name implies what it does, which is react to the plaintext in some way going forward, rather than simply encrypting it.

You can build something like this very easily using the duplexed sponge construction and AES. Using your key, you encrypt the IV, XOR the first byte of the block into the first plaintext byte, then XOR that same plaintext byte back into the block. You now have a single ciphertext byte, and your new block has changed based on the plaintext value. Repeating the process with subsequent bytes will encrypt all the plaintext, and each of the 256 byte values will result in a different block at that step. It will run about 6% the speed of CTR mode.

Not all stream ciphers operate by XORing the output to generate ciphertext, and just because something does should not automatically make it a stream cipher, in my opinion, unless it can be classified within the definitions that are currently in use.

The definition of self-synchronizing stream cipher calls for synchronization after a number of correct ciphertext bits, but in the case of a reactive cipher, after receiving incorrect ciphertext (bits, bytes, or blocks), the plaintext is no longer correct, and will not synchronize. Synchronous stream ciphers generate a keystream independent of the plaintext, so that definition clearly does not work either.

If anyone has a term better than reactive to describe ciphers that operate in this way, I would love to hear it. I would say adaptive does not fit, as it implies that the algorithm itself would change.

| improve this answer | |
$\endgroup$
  • $\begingroup$ If only there was some existing usage of reactive encryption algorithm or reactive cipher. Can you please cite something? As for being a sponge function instead: a sponge can be applied in modeling, even implementing some stream ciphers, so calling it a sponge doesn't necessarily mean it is not a stream cipher. It is an interesting description of how the cipher works, absorbing cumulative entropy into the state from the input. So, based on this suggestion, I went searching for sponge cipher. I couldn't find anything using that term, either. I would really like not to invent a new term. $\endgroup$ – alpha_numeric Feb 4 '16 at 15:29
  • $\begingroup$ @alpha_numeric a sponge construction is just one way to build a cipher that way, specifically using a duplex type mode similar to MonkeyDuplex. there are other constructions that will also fit. Also there are many sponge based ciphers, the CEASAR competition has about a dozen, see NORX, and I am developing my own for fun. They also do not give a more generalized description of the ciphers, since they are all authenticated. $\endgroup$ – Richie Frame Feb 4 '16 at 20:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.