# Re: Authenticating encrypted messages?

From: Francois Grieu (fgrieu_at_francenet.fr)
Date: 11/28/04

```Date: Sun, 28 Nov 2004 16:27:09 +0100

```

In article <co9un2\$fho\$04\$1@news.t-online.com>,
Mok-Kong Shen <mok-kong.shen@t-online.de> wrote:

> It occurs to me that the problem of cancelling 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
Note: that is, sender performs C{j+1} := ENC(Pj - 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.

This is still insecure against a simple attack when n>b,
where b is the block size in bits. Observe that
X2 = 2*X1 + (DEC(C2)+C2) mod 2^b
X3 = 4*X1 + 2*(DEC(C2)+C2) + (DEC(C3)+C3) mod 2^b
Xk = (2^k)*X1 + some function of (C2..Ck) mod 2^b for k>1
Changing C1 leaves Xk unchanged for k>=b, thus leaves
the ciphertext acceptable.

Note: and we have not started to consider the powerful and
harder to analyse attacks where the adversary permutates
ciphertext blocks, which I guess could be an issue with
fixed rotations, or few variable rotations.

I agree that constructing X{j+1} using some suitable mixing
function instead of X{j+1} = Xj + Pj + C{j+1} can provide
security. With an appropriate F, it seems enough to
have X{j+1} = F(Xj,Pj). But which F...

This thread illustrates why modern cryptography moves to
algorithms with provable security: often a cryptosystem may
have plausible security arguments, but be insecure.
My favorite example is the ISO/IEC 9796-1 RSA signature
then was found insecure.

Francois Grieu

## Relevant Pages

• Request to review OWASP ESAPI crypto
... The Open Web Application Security Project is a 501 ... The next release candidate of OWASP's Enterprise Security API (ESAPI) ... Many of these changes to OWASP's symmetric encryption came about as a ... Helper implementation classes (CipherSpec, CipherText, ...
(sci.crypt)
• Re: Ten least secure programs
... and generate a specific response to a question that exists in many Security ... Baselines are determined through sound Configuration Management. ... >I recommend the following be identified as the most insecure: ...
(Security-Basics)
• Re: PRNG using two functions
... can trivially break scheme 2 -- and F had better be invertible if you ... want the ciphertext to be decryptable at all. ... I envisaged a type of PRNG that is a polynomial function mod 2^32.) ... keyed permutation,both constructions are insecure. ...
(sci.crypt)