IS-59a CDMA security flaw (was: NSA crippling of crypto makes Congress vulnerable to attack)

[mean-green at hushmail.com]

At 05:27 PM 1/15/2002 -0800, Tim May wrote:
>Cellphones are easily interceptable.

Indeed they may be.  The 196 European Patent EP0752772A2 of James A Reeds, assigned to AT&T details one of the major IS59a cryptogrphic flaws the following passage of the Summary section:

"A previously unrecognized problem with the cryptographic system that is specified by the (IS-59a) Draft Standard is that it permits an eavesdropper to easily and quickly cryptanalyze transmissions encrypted according to the Draft Standard and thereby gain access to the substance of the transmission The forward traffic charnel described in the Draft Standard calls for encrypting an input voice or data signal prior to transmission with a key signal. The Draft Standard also specifies that the input signal be combined with the long code sequence in an Exclusive-OR (i.e., mod 2 addition) function to produce an encrypted output signal.

The Draft Standard calls for generating the long code sequence from a publicly known sequence and a private 42-bit pattern, known as the long code mask. The publicly available sequence is placed in what can be conceptualized as a linear shift register The output of the linear shift register is combined with the bits of the long code mask The linear nature of the combination causes the long code sequence to depend linearly on the bits of the private long code mask. This enables an eavesdropper to decrypt a wireless communication with access to 42 bits of the long code sequence The eavesdropper could use the bits from the long code sequence to create 42 linear equations that depend on the 42 unknown bits of the long code mask. However, the Draft Standard does not call for direct transmission of the bits of the long code sequence. Rather, an ExclusiveOR function combines the bits of the long code sequence with the unknown input signal thus corrupting the bits of the long code s!
equence. This should diminish the chances that an eavesdropper will successfully cryptanalyze a transmission. This is not the case with the Draft Standard because of the way that the input signal is processed to form frames of 384 bits for error correction.

An eavesdropper can cryptanalyze a transmission by recognizing relationships among the last sixteen bits in each frame of the input signal. Specifically, the eavesdropper car combine selected bits of the input signal from the last sixteen bits in each frame so as to produce modulo2 sums of zero. By adding (mod 2) the bits of the output signal such that the sum of the corresponding input bits is zero, the eavessdropper can obtain data that represent combinations of bits of the long code sequence. Essentially, the eavesdropper can cancel the effect of the input signal on the output signal. Each bit of the long code sequence is linearly dependent on the 42 bits of the long code mask. Thus, the eavesdropper can combine known bits of the output signal to create equations that are linearly dependent on the bits of the long code mask. Successive frames of data yield 42 equations so as to allow decryption of the communication within less than a second after the communication commenc!
es."