Re: Why Microsoft products using RC4 failed

From: Michael Amling (nospam@nospam.com)
Date: 04/11/03 

From: Michael Amling <nospam@nospam.com>
Date: Fri, 11 Apr 2003 03:10:09 GMT

David Wagner wrote:
> Schmenge wrote:
>
>>Michael Amling <nospam@nospam.com> wrote:
>>
>>>Schmenge wrote:
>>>
>>>>As we go we do
>>>>a simple checksum of the ciphertext. At the end of the process we
>>>>take the final checksum and pad it, if necessary to 128-bits. We XOR
>>>>the value with chunk three and XOR agin with chunk four. We append
>>>>this 128-bit value and prepend the 128-bit non-repeating sequence.
>>>
>>> Mallory can find the "simple checksum of the ciphertext", alter the
>>>ciphertext, and replace your (checksum XOR chunk3 XOR chunk4) with
>>>(malsum XOR chunk3 XOR chunk4).
>>
>>But Mallory does not know, and cannot derive chunk3 or chunk4, and so
>>would be unable to do what you suggest, or am I missing something?
>
>
> I think Michael Amling is right. Suppose your simple checksum
> is a CRC. Since the CRC is linear, we can xor Delta into the message
> and xor CRC(Delta) into the checksum block, and the resulting modification
> will go undetected. That's a security hole.

   If I read the proposal correctly, it doesn't even depend on the
linearity of the checksum. Mallory can observe (CHK(valid ciphertext)
XOR chunk3 XOR chunk4), calculate CHK(validciphertext),
CHK(malciphertext), and XOR those three together to get
(CHK(malciphertext) XOR chunk3 XOR chunk4), regardless of whether CHK is
a CRC or SHA1.

>
> By the way, WEP and SSHv1 were also vulnerable to this kind of
> security hole. It's a good argument against rolling your own crypto.

   Yes, the first protocol I rolled had exactly this flaw.

--Mike Amling

Relevant Pages

  • Re: CRC question
    ... final message padding, order in which input bits form the ... first thing is to check that a basic property of all CRC ... H(A XOR B XOR C) = HXOR HXOR H ... than the textbook CRC, including all CRC-lookalikes ...
    (sci.crypt)
  • Re: More about MT19937 in crypto
    ... end up dealing with XOR chains complex enough that you do have to ... off-diagonal 1's that perform simply a "shift" operation. ... for updating the CRC register for "byte at a time" CRCs, ... the base of the logarithm, not the fact that it's O. ...
    (sci.crypt)
  • crc code using vhdl found , few questions on it!!!
    ... has the software to generate the vhdl code for the crc 32 polynomial. ... crc is computed on only 4 bits of data. ... I will change the variable assignment to the ... Cxor C; ...
    (comp.arch.fpga)
  • Re: Query in Parallel CRC(urgent)
    ... The serial version of the CRC is the CRC ... As you can tell all we did was shift that first initial bit all the way ... Putting it all together is Dxor Dxor ... the first serial data bit is D ...
    (comp.arch.fpga)