Re: Authenticating encrypted messages?

From: Mok-Kong Shen (mok-kong.shen_at_t-online.de)
Date: 11/27/04 

Date: Sat, 27 Nov 2004 14:27:38 +0100

Francois Grieu wrote:

[snip]
> And wait, the whole scheme is insecure in the general case:
> changing Cj for any j<n is not detected. Root issue is that
> Pj = DEC(C{j+1}) XOR Xj
> X{j+1} = Xj XOR Pj XOR C{j+1}
> implies
> X{j+1} = DEC(C{j+1}) XOR C{j+1}
> therefore any change in the ciphertext cancels out and leaves
> what follows in the decryption unchanged.

While in an earlier response to this I returned to an idea of
mine in another previous thread, namely incorporating non-linear
combination of P and C blocks into the chaining value X (use
of data-dependent rotations seems to be an efficient prospective),
it occurs to me that the problem of cancelling above wouldn't
exist, if one uses modular addition in place of XOR. For one
has then (mod 2^n, n being the block size):

     Pj = DEC(C{j+1}) + Xj
     X{j+1} = Xj + Pj + C{j+1}
     X{j+1} = 2*Xj + DEC(C{j+1}) + C{j+1}

Now, if C{j+1} is changed to C{j+1}', DEC(C{j+1}') + C{j+1}'
is extremely unlikely to equal to DEC(C{j+1}) + C{j+1} for
a good block cipher, so that X{j+1} would get changed and
hence, by the last equation above, X(j+k) (k>1) would also
get changed, i.e. there is error propagation.

Is this argumentation o.k. in your opinion?

In my follow-up to Gregory Rose, I wrote "using the modular
sum (or xor) of all preceding ciphertext and plaintext blocks
as the chaining value of the current block". This "(or xor)"
is evidently wrong, as you have shown. In doing the modular
sum, I think one could just as well (as a compromise for
gaining a bit efficiency) do a word-wise summing instead of
treating entire blocks (consisting of several words) as whole
numbers. (Of course, one could, if one desires, additionally
employ data-dependent rotations of words so as to render the
relationship among the X's more complicated.)

M. K. Shen

Relevant Pages

  • Re: Help me understand Tweakable Block Cipher / LRW
    ... >encryption. ... XOR the computed value hwith the ... Why is the ciphertext further processed by ... theory or theoretical computer science. ...
    (sci.crypt)
  • Re: byte inversion in ciphertext
    ... decryption, resulting in a large expenditure of work. ... Ci = Pi xor K xor N xor Ci-1 ... so if k is the length of the ciphertext then if the ciphertext is 384 bytes ...
    (sci.crypt)
  • Re: Simple cipher program help
    ... For the first round, calculate ... L= R xor ... Land Rto make the 64-bit ciphertext. ... Then combine Land Rto yield the 64-bit plaintext. ...
    (sci.crypt)
  • Re: Authenticating encrypted messages?
    ... >> therefore any change in the ciphertext cancels out and leaves ... > of data-dependent rotations seems to be an efficient prospective), ... if one uses modular addition in place of XOR. ...
    (sci.crypt)
  • Re: stream ciphers
    ... > You take each byte of keystream and combine it with a byte of ... > plaintext to get a byte of ciphertext. ... Xor is comfortable as P xor K xor K = P. That's probably why it's the ...
    (sci.crypt)