Why do block ciphers still have a "decrypt" operation?

[Jan Andres]

These are merely theoretical considerations, but I've been seriously
wondering about this.

It seems to me that most modes of operation of block ciphers like CFB,
OFB, counter mode, etc. don't use the decryption operation of the cipher
at all. Thus if anyone were to design a cipher that had blazing fast
encryption at the expense of very slow decryption, this cipher would
still be usable in the majority of applications and could be considered
an improvement over existing block ciphers. Am I missing something?

Taking this a step further, the existence of a "decrypt" operation then
reduces to the theoretical requirement that for a given key, the map
from plaintext to ciphertext be provably a bijection. Being able to
efficiently compute the inverse map (or have an implementation of it
at all) is not required in practice?

Now, what if we were to replace block ciphers by "pseudo-block" ciphers
that drop the requirement of being reversible and merely had the
property that the ciphertext be a cryptographical hash of the
(key, plaintext) tuple? Would we lose any security by applying this
relaxation?

Is it likely that such a relaxation could, in practice, lead to
"pseudo-block" ciphers that can be implemented more efficiently than
existing block ciphers?

[Robert Wessel]

On Sat, 11 Feb 2012 22:21:05 +0000 (UTC), Jan Andres <J...@nAndr.es>
wrote:

You can build conventional block ciphers out of of hash functions
(Luby-Rackof), and you can use a hash function, which can be
considered a one way encryption function, in the way you describe
(SHACAL, BEAR and LION, for example).

[kg]

Jan Andres <J...@nAndr.es> wrote:
>Now, what if we were to replace block ciphers by "pseudo-block" ciphers
>that drop the requirement of being reversible and merely had the
>property that the ciphertext be a cryptographical hash of the
>(key, plaintext) tuple? Would we lose any security by applying this
>relaxation?

If "cryptographical hash" has its obvious meaning, then no. Let me
explain the technicalities.

A block ciphers is technically called a Pseudo-random permutation
(PRP), a family of permutations on some set along with evaluation
algorithms. There is an alternative notion called a Pseudo-random function
(PRF), a family of functions from one set to another where there need be
no inverse functions, along with an evaluation algorithm. (Presumably,
this is what you meant by "cryptographical hash".)

A PRP (or PRF) is secure if a random permutation (function) from the
family is hard to distinguish from a random permutation on the set
(random function from one set to another).

When you _only_ consider one direction of the PRP, it can be shown
that a secure PRP and a secure PRF are indistinguishable, that is,
one can be replaced by another without anyone noticing (use the PRP/PRF
switching lemma).

As you correctly observe, the PRP used many block cipher modes can be
replaced by a PRF without breaking anything functionally. And by the
PRP/PRF switching lemma, the security proof for the case of a PRP should
go through for the case of a PRF.

--
kg

[WTShaw]

You can simply generate a series based on one or more PRP's and see it
as a series of horizontal lines and harvest the columns as
pseudorandom text in which a whole set of results would have a flat
character distribution. This is easily demonstrated with simple
options to further obscure the whole procedure...nice, very nice.

[Richard Outerbridge]

In article <jh6pkh$o9e$1...@dont-email.me>, Jan Andres <J...@nAndr.es> wrote:

> These are merely theoretical considerations, but I've been seriously
> wondering about this.

[....]

> Now, what if we were to replace block ciphers by "pseudo-block" ciphers
> that drop the requirement of being reversible and merely had the
> property that the ciphertext be a cryptographical hash of the
> (key, plaintext) tuple? Would we lose any security by applying this
> relaxation?
>
> Is it likely that such a relaxation could, in practice, lead to
> "pseudo-block" ciphers that can be implemented more efficiently than
> existing block ciphers?

I think this is an open question. Earlier this year I suggested feeding
the output of a PRNG into a secure hash function to generate a
keystream. The only advantage of such a scheme over counter-mode would
be efficiency.

Whether a secure hash function can be used as a secure raw ECB
encryption primitive is, I think, still unproven.

outer

--
--
"Reality's never been of much use out here."

[kg]

Richard Outerbridge <ou...@interlog.com> wrote:
>I think this is an open question. Earlier this year I suggested feeding
>the output of a PRNG into a secure hash function to generate a
>keystream. The only advantage of such a scheme over counter-mode would
>be efficiency.

Actually, I think SHA-256 in counter mode is slower than AES in counter
mode.

(The Crypto++ benchmark page says 12.6 cycles per byte for AES/CTR. It
says 15.8 cycles per byte for SHA-256, which translates into 1011 cycles
per compression function evaluation, which translates into ~ 32 cycles
per byte of output in CTR mode.)

However, SHA-256 is overkill for counter mode. So you start simplifying
SHA-256, and then you realize that if you make the counter a bit more
complicated, you can really simplify the compression function, and before
you know it, you have a stream cipher...

>Whether a secure hash function can be used as a secure raw ECB
>encryption primitive is, I think, still unproven.

That depends on what you mean by a secure hash function. If you
just mean a collision resistant hash function, there are plausible
counter-examples. If you mean a random-oracle-like hash function, then
it is ok.

--
kg