From: Phil Karn <karn@qualcomm.com>
Date: Tue, 4 Feb 1997 06:56:38 -0800 (PST)
To: Doug_Merrill@rand.org
Subject: Re: PCS Encryption?
Message-ID: <199702041456.GAA28777@toad.com>
MIME-Version: 1.0
Content-Type: text/plain


>Phil Karn is, of course, the expert on this -- I hope he'll chime in soon
>-- Phil, you out there??

Yup, I'm out here. Just buried under a pile of email.

>Working from my not-so-great memory, CDMA uses a fixed spreading code that
>is determined by a pretty simple "cipher-like" process.  I believe the
>details are covered by an NDA, sorry.  At any rate, it isn't "encryption"
>by any means -- and tapping it requires little more than building a new
>base station (again, given $ and the fact that you're going to have to
>follow the bloody thing around as it moves).

No, it's not covered by NDA. It is, however, all heavily covered by
Qualcomm patents.  It's all specified in complete detail in TIA
IS-95A. The actual spec is copyrighted TIA (even though we did almost
all the work) but you can find an early version, plus a much more
readable overview paper, through my web page. The air interface is
essentially the same as you'll find on the air.

<http://www.qualcomm.com/people/pkarn/cdma.html>

There is essentially no "encryption" in the usual sense of the word in
CDMA. It is true that the complexity (and until recently, the
obscurity) of the modulation method provides some modest protection
against casual eavesdropping (e.g., someone with a Radio Shack
scanner). But phones containing the necessary ASICs are now being
shipped by the hundreds of thousands per month, and as I said earlier
the complete air interface spec has been public for some time.

I do note that the forward (base to mobile) and reverse (mobile to
base) modulation methods are totally different, because the jobs they
have to do are different. Only the reverse link is truly CDMA, as
there you have many transmitters sending to a single receiver. Both
links are spread to 1.25 MHz bandwidths, but that's about where the
similarities end. The phone ASIC contains only a forward link
demodulator function and a reverse link modulator function. The base
station ASICs are not yet generally available. Also, an echo canceller
in the base station effectively blocks any reverse link audio from
coming back out on the forward link.

Consider also the very low and tightly controlled transmitter powers
typically used on the reverse link. One can now make certain
conclusions about the relative ease of intercepting the forward link
as compared to the reverse link.

The closest thing to "encryption" in CDMA is the "private long key"
mechanism. The private long key is the starting state of a 42-stage
linear feedback shift register (LFSR) that is used to spread (reverse
link) or scramble (forward link) the vocoder data. (The IS-95 signal
path is too complex to describe fully here -- see the documents on my
web page for the details, including the difference between scrambling
and spreading).

As anyone with even a rudimentary knowledge of cryptanalysis knows,
LFSRs are not at all cryptographically secure. The Massey-Berlekamp
algorithm can easily determine the state of the long code shift
register with a short (42-chip) sample of its output. Furthermore, the
long key sequence has other specified uses on the reverse link; in
particular it is used as a pseudorandom sequence generator to control
the puncturing (on-off transmitter gating pattern) when the phone is
transmitting at a low data rate between talk spurts. This obviously
suggests other ways to determine the LFSR state without demodulating
individual CDMA chips.

Nevertheless, NSA has repeatedly objected to the export of the
"private long code" feature, and I'm not even sure it's implemented on
the domestic models currently being deployed.

Phil