Re: convert stream ciphers into block ciphers

jsavard_at_ecn.ab.ca
Date: 05/16/03 

Date: Fri, 16 May 2003 19:33:59 GMT

David Wagner (daw@mozart.cs.berkeley.edu) wrote:
: Not much complexity is needed if you don't care about security.

: On the other hand, if you want a *secure* block cipher (i.e., a
: pseudorandom permutation), it's not that easy. For instance, secure
: block ciphers are supposed to have avalanche from all plaintext bits
: to all ciphertext bits, whereas stream ciphers aren't.

However, it should be noted that Mr. Gwyn has a point. Why is something
like a four-round Feistel construction required, to make a stream cipher
into a secure block cipher *for a sufficiently large block* _if_ the
stream cipher, used as a plain stream cipher, is itself secure?

However, I think an answer is possible in simple terms here.

A four-round Feistel construction involves using the stream cipher four
times... on *half* the block. So it only _doubles_ the amount of work
needed.

Let us suppose using the stream cipher just once on a message the size of
the proposed block is secure - when using it normally as a stream cipher.

How do we normally use stream ciphers in a secure fashion?

We use them with a random IV that is never re-used.

Block ciphers, by definition, aren't allowed the luxury of an IV _as part
of the block cipher_.

I came up with a construction independently which turned out, based on my
understanding of a patent referred to in the initial posting of the thread
'Double Encryption is Patented' to be covered by the IBM patent which
apparently also covers OAEP (although my construction is _not_ OAEP, and
thus lacks some of its desirable properties) which can be modified to
bring it closer to the original IBM patent, although it covers using a
block cipher in CBC mode, not a stream cipher, to cover this case.

Essentially, the second half of encryption amounts to: encipher all the
message, except for an IV-sized portion, using the stream cipher, with the
first chunk of the message serving as an IV.

This would be secure if the first chunk of the message were equivalent to
an IV; essentially random, and containing no information about the rest of
the message.

So the first half of the encryption involves a pass over the rest of the
message using a cipher to create a secure checksum of the rest of the
message to XOR with that first piece. This can be done with a stream
cipher as well as a block cipher.

Of course, the IV will still sometimes recur for non-identical blocks, so
even with two passes (the same as a Luby-Rackoff construction requires) we
have a security tied to the IV size and not the block size. So this
construction could still be considered insecure. But it does show why a
second pass is the *minimum* required for security, _given_ the standard
definition of a block cipher.

John Savard

Relevant Pages

  • Re: Jim Steuert is a clue-challenged braying jackass
    ... Helix cipher. ... That this construction, in recursive form, yields SHA-1 ... is provable secure. ... as David Wagner asserted "we don't need ...
    (sci.crypt)
  • Custom Cryptography
    ... I am in the process of writing a book, "Custom Cryptography". ... It will include multiple examples of "practically secure" ... As just one example of a secure construction, ... Assume H is itself a cipher with a fixed key. ...
    (sci.crypt)
  • A secure hand cipher?
    ... I have been looking for a way to make a secure hand cipher similar to the ... The "encryption device" is a standard set of scrabble tiles with one ... Text1: From Sherlock Holms ...
    (sci.crypt)
  • Re: QC-proof cipher?
    ... to conventional computation techniques, let alone quantum computing. ... one "secure" symmetric cipher too, ... One thing I wonder is people always say this about OTP but what ... is the difference between OTP and a NULL cipher. ...
    (sci.crypt)
  • Re: triple algorithms
    ... matching of algorithms I would advise you don't do this. ... AES is secure insofar as nobody has yet found a viable attack for it. ... creating a new cipher out of a collection of others. ... security depends only on the single assumption that factoring is hard. ...
    (sci.crypt)