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
padding, which got through considerable review for a decade,
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)
  • Re: ADVERT: Secure communications
    ... it "hides" ciphertext in padding? ... | eliminating security risks from symmetric ciphers. ... The security of RSA isn't even proven, ... encrypt with RSA. ...
    (comp.os.linux.security)
  • Re: Secure host newbie - fun - humm
    ... Show us that kernel.org is insecure. ... needs to back it up -- show us that kernel.org is secure. ... If you understood security, you'd know that the best position to start ... it's a basic fact that there are undisclosed vulnerabilities. ...
    (Security-Basics)