Subject: [Cfrg] Possible RFC: Data integrity combined with encryption

From: [email-masked] (Mok-Kong Shen)
Date: Fri, 20 Sep 2002 10:36:42 +0200

Terry Hayes wrote:
[snip]
> Right now it is difficult for designers to get good information on how
> to build protocols that provide both encryption and integrity.  In
> fact, some of the best known sources of information about
> cryptographic algorithms seem to provide methods that are now believed
> to be incorrect.  For example, Handbook of Applied Cryptography
> (Menezes, van Oorschot and Vanstone) contains a section in Chapter 9
> called "Data integrity using encryption and an MDC".  This section
> essentially describes the method proposed in OpenPGP.  While it does
> include remarks about the dangers of using this method with stream
> ciphers in situations where there is known plaintext, the overall
> impression is that it is always good method when used with block
> ciphers in CBC mode. The RFC might describe what steps should to be
> taken to use this method in a protocol (if it is possible at all).
[snip]

In CBC the error propagation property is extremely
limited. If, instead of the ciphertext of the
immediately preceding block, one uses the cumulated
sum of all previous plaintext and ciphertext blocks
to chain, then there would be comparatively quite 
strong propagations, if anywhere a bit is changed. 
Wouldn't using this in place of CBC provide better
integrity protection? Thanks.

M. K. Shen
_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: Helger Lipmaa <[email-masked]>
Date: Fri, 20 Sep 2002 12:25:38 +0300 (EEST)

In formal models, CBC is only secure if the IV is unpredictable.

In this concrete case that you propose there would be at least a few
practical breaks. The most severe is probably the following:

*. Since IV = Sum (P_i+C_i), then since attacker knows Sum C_i, she can
   deduce Sum P_i. This leaks information. It is especially bad when the
   previous plaintext has length 1.

The solution is to use a fresh unpredictable random number for the IV
every single time. (If you work in some strange models where for example
not all C_i get public, there might be other solutions. But it is better
stick to the general model.)

This much about confidentiality. If you want the combine it with
integrity, Mihir's pointers gave a very good summary.

Helger

---

From: [email-masked] (Mok-Kong Shen)
Date: Fri, 20 Sep 2002 18:21:22 +0200

> integrity, Mihir's pointers gave a very good summary.

Would your critique remain true, when the sum is
initialized with a random IV? (I actually mentioned 
use of IV, when I suggested the same in sci.crypt
quite a time back.)

M. K. Shen

---

From: "Anton Stiglic" <[email-masked]>
Date: Fri, 20 Sep 2002 13:36:56 -0400

>----- Original Message -----
>From: "Mok-Kong Shen" <[email-masked]>
>

You have to be really careful.  I, and another cryptographer, once
suggested using what is known as the infinite garble as a mode of
encryption that also provides integrity assurances (by having some
known plaintext encrypted as the last block, hoping that any change
would garble all the way to the last block).  We called it Free-MAC.
The intent was to avoid attacks such a the swapping of two
ciphertext blocks.  See the post to sci.crypt
http://groups.google.com/groups?q=Mac+Adam+Back&hl=en&group=sci.crypt.*&safe
=off&rnum=3&selm=38C5A4ED.5804E1D0%40zeroknowledge.com
But Virgil Gligor, by private communication,  pointed to us an attack
which broke the integrity property, it consisted of swapping and xoring
ciphertext blocks in a way that still preserved the integrity of the last
block.
See also the post by Charanjit Jutla
http://groups.google.com/groups?q=sci.crypt+Free-MAC&hl=en&lr=&ie=UTF-8&oe=U
TF-8&selm=39BFD167.B01F48C%40watson.ibm.com&rnum=1

The point is that you shouldn't rely on any error propagation properties
of an encryption mode.  You need to either do encryption AND macing,
or use a scheme that combines both (which Jutla proved necessitates
the computation of at least log m extra encryption, where m is the number
of blocks, for any linear scheme).  But most of the schemes (if not all ??)
that combine both confidentiality and integrity in one mode are patented.

Cheers!

--Anton

---

From: csjutla <[email-masked]>
Date: Fri, 20 Sep 2002 14:15:15 -0400 (EDT)

A new version of the paper showing no such schemes will work
(i.e. which provide message integrity with encryption)
is on iacr archive:

"Tight Lower Bound on Linear Authenticated Encryption "

http://eprint.iacr.org/2002/132

It also has a few diagrams of tempting schemes which do not work.

-Charanjit Jutla

---

From: [email-masked] (Mok-Kong Shen)
Date: Fri, 20 Sep 2002 21:38:46 +0200

> It also has a few diagrams of tempting schemes which do not work.

A question of ignorance: Would using some non-linear
quantities, e.g. the sum of squares of all preceding
plaintext and ciphertext blocks, to chain render
some improvemants?

M. K. Shen

---

From: [email-masked] (Mok-Kong Shen)
Date: Fri, 20 Sep 2002 22:00:13 +0200

csjutla wrote:
> 
> Sure, non-linear schemes work.
> But, if you want to use non-linearity,
> some really simple schemes work.
> See my old paper : (which describes two schemes IAPM and IACBC).
> 
> http://eprint.iacr.org/2000/039/
> 
> Also see
> www.nist.gov/aes/modes/proposedmodes (and look under my name).
> 

Many thanks for the references.

Anton Stiglic mentioned that possibly all good schemes 
known are patented. Is that true or could you name
one that is free? Thanks.

M. K. Shen

---

From: "Housley, Russ" <[email-masked]>
Date: Fri, 20 Sep 2002 17:04:49 -0400

> > www.nist.gov/aes/modes/proposedmodes
>

Please take a look at 
http://www.ietf.org/internet-drafts/draft-housley-ccm-mode-00.txt

Russ