Re: Why Micosoft products using RC4 failed

From: Schmenge (Schmenge@bigroom.com)
Date: 04/11/03 

From: Schmenge <Schmenge@bigroom.com>
Date: Fri, 11 Apr 2003 00:14:25 -0700

On Fri, 11 Apr 2003 06:21:36 +0000 (UTC), daw@mozart.cs.berkeley.edu
(David Wagner) wrote:

>Schmenge wrote:
>>But then encrypting the checksum block prior to XOR will block the
>>HMAC attack you (and Michael Amling) suggest, yes?
>
>I don't think so.
>
>If your encryption is XORing with some RC4 keystream, the encryption
>didn't do any good. You'd still be hosed in this case, I think. I can
>still XOR the encrypted checksum with the value D, where
> D = CHK(valid ciphertext) xor CHK(malciphertext).
>

I see it. OK. Still linear. Cannot get rid of that with XORing.
Then since I am constrained by this inability (self-imposed) to not
add OWF code, then the following:

I generate the PRF'd key and sequence and two 128-bit hard-to-guess
blocks (chunk3 and chunk4) with the first RC4 session using all the
hygiene. You do not have access to these.

I generate a strong RC4 keystream (by starting with a PRF'd key and
dropping 1024 bytes), and after using it standard RC4 to encrypt
plaintext, I then add chunk3 to the checksum/padding to create a final
checksum. Continue using RC4 stream to encrypt the final checksum.

Then it is XOR'd with chunk4. So you don't have access to change the
checksum/padding and I believe the original checksum is now not
linear, right? Or have I removed enough linearity?

You know what is in there (because you can checksum the ciphertext)
but you can't change it in a manner that I won't discover. And you
cannot change the ciphertext in a manner I won't discover either.

Does this hold water?

>>BTW, thank you.
>
>No problem.
>
>>>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.
>>
>>Sure it is a good argument. But I'm not rolling my own. I'm looking
>>for countermeasures to possibly prevent known attacks on RC4.
>
>I'm not sure I see the difference. You're describing a new
>algorithm for enciphering plaintext. Your algorithm happens to
>use RC4 as part of its innards, but it also has a significant amount
>of new, unanalyzed innovation. New, unanalyzed innovation is risky.

True that unanalyzed is risky, but I'm not quite sure I'm using it in
an unanalyzed fashion.

The attacks seem to coincide with starting RC4 with a weak key, or
using the first couple bytes to gain a wedge, but I'm not doing that.

Once RC4 is started correctly the strength of the PRNG seems to have
been highly analyzed. And the best anyone seems to be able to do is
predict that a random stream is not a random stream, but is indeed RC4
after greater than 500MB (that may be incorrect) of stream.

I'm trying to carefully use this PRNG strength to PRF and HMAC. This
is not innovation, is it? I'm doing nothing new.

Relevant Pages

  • Microsoft Windows Remote Desktop Protocol checksum and keystroke vulnerabilities
    ... All versions of Microsoft Windows using encrypted RDP are vulnerable to ... the checksum vulnerability. ... since packets with the same plaintext have matching checksums. ... When RDP has encryption enabled, packets are first encrypted using RC4, ...
    (Bugtraq)
  • Re: What is the name of this cipher algorithm?
    ... The first method seeds the encryption ... Looks like RC4 plus a weird almost-periodic XOR of 'M_subKey'. ... I think reset was called for every new package, ... The weird thing is the re-seeding though. ...
    (sci.crypt)
  • Re: Native RC4 code
    ... i'd rather advise you to avoid using RC4 encryption, ... drop them before using RC4 stream, you can never reuse key stream +++. ... I'm new in encryption and I have a question. ... I have a public key, a .p7b file, how can I load the public key and use ...
    (microsoft.public.dotnet.security)
  • Re: RC4 broken?
    ... Few encryption algorithms have had the ... >> time that the first few bytes output by RC4 were ... >> the secret key the secret key ...
    (sci.crypt)
  • Re: how these 2 functions may differ?
    ... you not using the encryption functions built in to Windows? ... as far as I know there isn't any .net builtin RC4 ... Windows has RC4 builtin. ... it should have been as simple as calling new CryptoAPITransform ...
    (microsoft.public.dotnet.languages.csharp)