[2623] in cryptography@c2.net mail archive
Is PPTP cryptographically secure?
daemon@ATHENA.MIT.EDU (Vin McLellan)
Fri May 1 18:44:54 1998
Date: Fri, 1 May 1998 14:36:19 -0400
To: "'NT Security Listserv'" <ntsecurity@iss.net>
From: Vin McLellan <vin@shore.net>
Cc: cryptography@c2.net,
Windows NT BugTraq Mailing List <NTBUGTRAQ@listserv.ntbugtraq.com>
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.
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.
The actual length of the crypto key seems to be irrelevant, given
this vulnerability. The actual source of the key (NT hash vs. LM hash)
seems to be irrelevant, given this vulnerability. Is Microsoft doing
something with the RC4 key internal to the PPTP session that makes this
viable?
Could someone from Microsoft, or someone more savvy about PPTP's
use of crypto, please explain why a stream cipher (in this case, RC4) was
selected as more appropriate than a block cipher for this application? I
assume Alan and I are missing something here, but I don't see what.
Can a two-way, two-datastream, one-key PPTP-based VPN ever be
cryptographically secure when it relies on a stream cipher?
Does implementing PPTP place some additional burden on local
password management? Does ether the sysadmin or the user have some new
obligation to religiously and periodically change passwords? (Oh Holy
Grail!) Or, can PPTP -- now, or in its upgraded future -- be implemented
so that it pulls its cryptographic key from an OTP like SecurID or OPIE?
Mr. Ramsbottom wrote:
>Firstly a quick tour of RC4. For the sake of argument it's just like a
>pseudo-random number generator i.e. give it a seed, kick it and it
>churns out a stream of binary gobbledygook. Give RC4 the same seed
>again, another kick and it churns out exactly the same stream.
There are a lot of reasons Rivest's variable key-length RC4 is so
popular, notably its speed (10 times DES,) its elegant simplicity, its
apparently robust PRN (which can be stepped through 2*1700th possible
states)... and, of course, the fact that people who have been beating on it
for almost a decade still think it is secure.
RC4 works in Output-Feedback (OFB) mode, so the keystream is
generated independent of the plaintext, then simply XORed to it. As I
understand it, the cryptographic complexity of the algorithm lies in its
stepped "next state" function -- which is, in turn, dependent on both the
key and the length of the key.
I think you've got the mechanical spirit of the process just about
right, Alan;-)
The vulnerability you point out presumes, of course, that both PPTP
datastreams -- ie., the senders at both ends -- are independently
generating the same PRN keystream ("binary gobbledygood") and kicking it
(XORing) against two different messages-streams to create two parallel
streams of ciphertext.
Tell us it ain't so, someone. Please?
Suerte,
_Vin
Mr. Ramsbottom continued:
>To encrypt stuff (plaintext), you simply XOR your data with the RC4
>stream and volia, you've got some ciphertext. To get the plaintext
>back again, you XOR the ciphertext with the original RC4 stream:
>
> Alice.txt XOR AlansRC4Stream = Alice.rc4
>
> Alice.rc4 XOR AlansRC4Stream = Alice.txt
>
>We can also recover the RC4 stream:
>
> Alice.rc4 XOR Alice.txt = AlansRC4Stream
>
>Course, I could use the *same* RC4 stream to also encrypt some other
>plaintext:
>
> Bob.txt XOR AlansRC4Stream = Bob.rc4
>
>That might not be such a good idea though, because then:
>
> Alice.rc4 XOR Bob.rc4 = Alice.txt XOR Bob.txt
<snip>
> [...] PPTP uses
>the *same* RC4 stream to encrypt both outbound and inbound data. The
>initial "seed" or key used to generate that stream is derived from a
>user's credentials i.e. password hashes. Furthermore, after every
>256(?) packets the key is changed (a function of the previous key?).
>
>But in this discussion we don't care about the keys. Let's say the Bad
>Guy can observe and capture all of the PPTP data passing through some
>hostile territory between A and B. With a bit of work he'll end up
>with two lumps of data that have been encrypted with the same RC4
>stream(s):
>
> Outbound.rc4
> Inbound.rc4
>
>In the real-world this is very unlikely to constitute anything close
>to *all* the PPTP tunnelled traffic i.e. it will depend on things like
>the size of the packets and the number that are flowing in each
>direction, key changes etc. Still, if Outbound.txt and Inbound.txt are
>the "raw" un-encrypted packets then in principle:
>
> (Outbound.rc4 XOR Inbound.rc4) XOR Oubound.txt = Inbound.txt
>
>In other words if we have knowledge of, or can predict some part of the
>data headed in one direction, then we should be able to recover an
>equal amount of data that was travelling the other way.
>
>How big a problem is this? Well, I'm currently tempted to think this
>ISN'T such a big problem because AFAIK, PPTP encrypts *complete* PPP
>packets so there'll be no really useful things exposed e.g. the IP
>headers for any tunnelled IP packets. Further, I believe PPTP applies
>LZ(?) compression to a PPP packet before the RC4 encryption and I
>guess that might complicate recovery of the plaintext a little.
>
>But I don't know ..I certainly wasn't the first to remark on this
>*potential* problem and furthermore I really wouldn't care to nail my
>flag to *any* of it. Nonetheless, it does seem like another reason to
>be a little uneasy about the use of PPTP and is an issue I haven't
>seen discussed in any great detail. Hence my original question to be
>found way back at the top of this post..
>
>..which of course still stands. So, has anyone got any comments about
>this whole thing?
>
>--Alan--
>acr@als.co.uk
----
-----
"Cryptography is like literacy in the Dark Ages. Infinitely potent, for
good and ill... yet basically an intellectual construct, an idea, which by
its nature will resist efforts to restrict it to bureaucrats and others who
deem only themselves worthy of such Privilege."
_ A thinking man's Creed for Crypto/ vbm.
* Vin McLellan + The Privacy Guild + <vin@shore.net> *
53 Nichols St., Chelsea, MA 02150 USA <617> 884-5548
