A poorman's block encryption algorithm
in [Cryptography]
|
From: Mok-Kong Shen on 13 Mar 2010 07:23 Mok-Kong Shen wrote: > Mok-Kong Shen wrote: >> Maaartin wrote: >>> Mok-Kong Shen wrote: >>>> My point was, to fomulate stronger, that there is no authentication >>>> scheme based on a (strict) stream cipher at all (to my humble >>>> knowledge). Or are you of different opinion? >>> >>> I'm not aware about anything like this (and about so many other >>> things :D ). >> >> O.K. Let's see whether some experts could name an authentication >> scheme based on stream ciphers. > > I like to remark that I don't want to cause lenghty discussions on > the "definition" of stream ciphers. Once I mentioned something like > doing addition of a 32-bit computer word output from a PRNG to > 32 bit of plaintext as a stream encryption operation and someone > promptly opposed, saying that's a "block" operation. On the other > hand, I read in descriptions of stream ciphers phrases like "consists > of a sequence of blocks", "the complete block function", etc. > Evidently, different people have different opinions on what's > "exactly" a stream cipher and what is not and there is thus not much > sense to debate on its "definition". [Addendum] The above quoted phrases were taken out of a paper entitled: "Fast Encryption and Authentication in a Single Cryptographic Primitive". I am not sure whether that cipher couldn't be better classified as a block cipher (but with "dynamics") instead of a stream cipher. (For it works on "chunks" of 128 bits, if I don't err. For "dynamics" see also my recent thread "Introducing dynamics into block encryptions".) Personally, I am rather neutral to the "distinction" between stream and block ciphers. Like many other things, there is a "continuum" of types of ciphers, I suppose. For convenience, though, I use to employ the term stream to refer to those ciphers that operate at the level of computer words (using arithmetic and bit operators) and the term block to ciphers that operate beyond that. Doesn't that sound genrally acceptable? Thanks, M. K. Shen
From: Maaartin on 15 Mar 2010 23:58 On Mar 13, 1:23 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > Mok-Kong Shen wrote: > [Addendum] > The above quoted phrases were taken out of a paper entitled: "Fast > Encryption and Authentication in a Single Cryptographic Primitive". > I am not sure whether that cipher couldn't be better classified as > a block cipher (but with "dynamics") instead of a stream cipher. (For > it works on "chunks" of 128 bits, if I don't err. For "dynamics" see > also my recent thread "Introducing dynamics into block encryptions".) > Personally, I am rather neutral to the "distinction" between stream > and block ciphers. Like many other things, there is a "continuum" of > types of ciphers, I suppose. For convenience, though, I use to employ > the term stream to refer to those ciphers that operate at the level > of computer words (using arithmetic and bit operators) and the term > block to ciphers that operate beyond that. Doesn't that sound > genrally acceptable? I've just found a definition by RSA Laboratories (TR-701): Block ciphers operate with a fixed transformation on large blocks of plaintext data; stream ciphers operate with a time-varying transformation on individual plaintext digits. According to this, (p)helix is neither. But it seems that the "time- varying" is the distinguishing criterion. Or maybe the situation has changed in the meantime - the report is quite old (1995).
From: J.D. on 16 Mar 2010 11:08 @Maaartin > > I've just found a definition by RSA Laboratories (TR-701): > Block ciphers operate with a fixed transformation on large blocks > of plaintext data; stream ciphers operate with a time-varying > transformation on individual plaintext digits. > > According to this, (p)helix is neither. But it seems that the "time- > varying" is the distinguishing criterion. Or maybe the situation has > changed in the meantime - the report is quite old (1995). A stream cipher is simply any (purportedly) cryptographically secure pseudo random number generator, whose output depends on the secret key (and an IV or nonce), and which encrypts a message M by generating a pseudo random key stream that is as long as M, and which is combined with M (usually by some simple linear operation like xor) in order to form the ciphertext. The distinction between block ciphers and stream ciphers is somewhat blurred, because a block cipher operating in OFB or CTR mode quite simply _is_ a stream cipher, where the part of the pseudo random number generator is played by the block cipher. Phelix is a stream cipher with an interesting twist -- the pseudo random number generator at its core incorporates the plaintext into its state, and that gives the cipher the ability to authenticate the message. Any attempt to change the plaintext will result in a different key stream and hence will change the 'MAC tag' at the end (which is simply an extra part of the key stream).
From: Thomas Pornin on 16 Mar 2010 12:04 According to J.D. <degolyer181(a)yahoo.com>: > A stream cipher is simply any (purportedly) cryptographically secure > pseudo random number generator, whose output depends on the secret key > (and an IV or nonce), and which encrypts a message M by generating a > pseudo random key stream that is as long as M, and which is combined > with M (usually by some simple linear operation like xor) in order to > form the ciphertext. Not exactly. _Most_ stream ciphers work that way. However, in all generality, the encryption procedure may use the data bytes in more fundamental ways. An example of a dedicated stream cipher which uses plaintext bytes quite fundamentally is the one which was used in PKZIP; see: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.49.2468 (this particular stream cipher was broken in 1994). The Wikipedia page: http://en.wikipedia.org/wiki/Stream_cipher talks about "self-synchronizing stream ciphers" in that case. The CFB mode transforms any block cipher into a self-synchronizing stream cipher. Maybe a better definition of stream cipher would be the following: a "stream cipher" is a symmetric encryption system such that, for a given key K, any sequence s of n bits can be encrypted into an n-bit output, without needing n to be a multiple of some value (e.g. 8 or 128), and such that the first r output bits, for all r < n, are also the output of the stream cipher with the same key K over the first r bits of s. In simpler words, any bit can be encrypted into another bit, without even knowing if there will be subsequent bits of input. This precludes "ciphertext stealing" from being considered as a way to get a stream cipher. Any stream cipher can be turned into a PRNG by encrypting an infinite sequence of zeros. For most stream ciphers, which produce a data-independent keystream, to be XORed with the plaintext, then encrypting zeros only yields that keystream. Phelix is a self-synchronizing stream cipher. Supposedly, that property could be extended into the production of a cheap MAC. It is however quite hard to achieve, because the "keystream" corresponding to that final MAC must depend on all input bits, in a way similar to what a hash function does. Not all self-synchronizing stream ciphers do that; in particular, in a block cipher in CFB mode, the keystream at any particular point depends only on the last few dozen ciphertext bits, making it unsuitable for a MAC-by-additional-keystream. Conceptually, what Phelix tried to do requires a larger internal state than a "regular" stream cipher. --Thomas Pornin
From: J.D. on 16 Mar 2010 12:52
On Mar 16, 12:04 pm, Thomas Pornin <por...(a)bolet.org> wrote: > According to J.D. <degolyer...(a)yahoo.com>: > > > A stream cipher is simply any (purportedly) cryptographically secure > > pseudo random number generator, whose output depends on the secret key > > (and an IV or nonce), and which encrypts a message M by generating a > > pseudo random key stream that is as long as M, and which is combined > > with M (usually by some simple linear operation like xor) in order to > > form the ciphertext. > > Not exactly. _Most_ stream ciphers work that way. However, in all > generality, the encryption procedure may use the data bytes in more > fundamental ways. An example of a dedicated stream cipher which uses > plaintext bytes quite fundamentally is the one which was used in PKZIP; > see: > http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.49.2468 > (this particular stream cipher was broken in 1994). > > The Wikipedia page: > http://en.wikipedia.org/wiki/Stream_cipher > talks about "self-synchronizing stream ciphers" in that case. > > The CFB mode transforms any block cipher into a self-synchronizing > stream cipher. Well I thought I had covered self-synchronizing stream ciphers in my definition, but I can see now that it is definitely more slanted towards synchronous stream ciphers. "....and such that the first r output bits, for all r < n, are also the output of the stream cipher with the same key K over the first r bits of s." Yes. That's an important defining attribute that I left out of my definition. Thanks for the correction. On an unrelated note, I hate it when citeseerx puts the pages in backwards... |