[2629] in cryptography@c2.net mail archive
Re: Is PPTP cryptographically secure?
daemon@ATHENA.MIT.EDU (Arnold G. Reinhold)
Mon May 4 18:31:08 1998
In-Reply-To: <v04003a03b16fc55bc61c@[198.115.179.81]>
Date: Sun, 3 May 1998 10:29:23 -0400
To: Vin McLellan <vin@shore.net>,
"'NT Security Listserv'" <ntsecurity@iss.net>
From: "Arnold G. Reinhold" <reinhold@world.std.com>
Cc: cryptography@c2.net,
Windows NT BugTraq Mailing List <NTBUGTRAQ@listserv.ntbugtraq.com>
At 2:36 PM -0400 5/1/98, Vin McLellan relayed:
> In his own inimitable style, Alan Ramsbottom <acr@als.co.uk>,
>maintainer of the FAQ on NT Cryptographic Password Attacks & Defences"
><http://www.ntbugtraq.com/Contributions/samfaq> recently asked -- twice, on
>the NT-Security List -- why Microsoft chose a stream cipher (RC4) for its
>Point-to-Point Tunneling Protocol.
>
> In PPTP, the same keystream (keyed from the user's password hash)
>seems to be used to encrypt _two_ distinct datastreams: both inbound and
>outbound PPTP.
>
> It is a really good question. This may have been discussed
>elsewhere, but I'd really like to hear Paul Leach or Peter Ford or some
>Microsoft cryptographer answer the querulous Brit... maybe before our new
>and improved PPTP (with the problematic LM hash finally all but squelched)
>lures the big ISPs and half the NT corporate users into pumping their
>digital treasure thru PPTP-enabled VPNs.
>
> I'm no cryptographer, and neither is Alan, but Schneier's bible and
>every Crypto 101 course has taught most of us that to actually use the same
>RC4 keystream (or the keystream from _any_ stream cipher) with two
>different datastreams is simply a mortal sin. Crypto-suicidal.
>
Your understanding is correct. If Microsoft is doing what is alleged, their
security is broken and the break can be readily exploited. We are not
talking about rounding up thousands of Pentiums over the Internet, we are
talking about an attack that can be performed in Basic running on a first
generation IBM-PC. In fact the U.S. was able to crack a mathematically
equivalent problem in the 1940's and 50's without computers. Follow the
VENONA links at http://www.nsa.gov
> If a cryptoanalyst can XOR two datastreams encrypted with the same
>keystream, he gets the XOR of plaintext-1 with plaintext-2. From there, it
>is a seemingly trivial challenge to get the two plaintexts. With plaintext
>in hand, the attacker can then retrieve the keystream, and can thus read
>all messages ever encrypted with that keystream -- until or unless (in the
>case of PPTP) the user is routinely forced to change his NT password.
>
It is only trivial to get the plaintexts if you already know one of them.
If you do not know either plaintext but the texts have a fair amount of
redundancy, for example if they both are in ordinary English, then both
plaintexts can still be recovered, but some skill is required. The key
stream (the raw output of the cipher) is a byproduct of the process. So
once you break one pair of messages, you can get all other messages encoded
with the same key, up to the length of the message you broke. Note that
this does not mean that you recover the key itself. I am not aware of
anyone who has succeeded in doing that with RC4.
>[Questions about Microsoft which I cannot answer deleted]
> Can a two-way, two-datastream, one-key PPTP-based VPN ever be
>cryptographically secure when it relies on a stream cipher?
>
Yes and no. "No" if you mean keying a stream cipher the same way more than
once. "Yes" if what you really mean by "one-key" is sharing only one
secret. The trick is to add something to your secret that differs each
time the stream cipher is used. That unique something must be known to both
sender and receiver but need not be concealed from others. You can transmit
it as part of an initialization protocol, for example.
The unique something can be a random number, a message serial number that
never resets or wraps around, or the combination of date, time, host name
and port number. Just append this unique something to your secret key and
hash. Then use the hash output as the RC4 key.
If you use a random number, it must be long enough to avoid birthday
collisions (80 bits or more) and should come from a true source of random
noise (pronouncements of Microsoft's lawyers are not good enough). You also
have to be careful whenever you loose packets and have to resynchronize.
Using a stream cipher properly requires some care, but RC4's high
performance may well justify the effort in an application like this. For
more information see my "Cryptanalysis of CipherSaber,"
http://ciphersaber.gurus.com/cryptanalysis.html
Arnold Reinhold
