Re: Another Clipper weakness

-----BEGIN PGP SIGNED MESSAGE-----

From: "Perry E. Metzger" <pmetzger@lehman.com>

> I've just looked over the proposal again, and I've seen no mention of
> random inputs -- only that the 30 bit key would get a "fixed 34 bit
> padding" added to it.

Here is what Denning's writeup says:

  At the beginning of a session, a trusted agent from each of the two key
  escrow agencies enters the vault.  Agent 1 enters an 80-bit value S1
  into the laptop and agent 2 enters an 80-bit value S2. These values
  serve as seeds to generate keys for a sequence of serial numbers.
  
  To generate the unit key for a serial number N, the 30-bit value N is
  first padded with a fixed 34-bit block to produce a 64-bit block N1.
  S1 and S2 are then used as keys to triple-encrypt N1, producing a
  64-bit block R1:
  
          R1 = E[D[E[N1; S1]; S2]; S1] .
  
  Similarly, N is padded with two other 34-bit blocks to produce N2 and
  N3, and two additional 64-bit blocks R2 and R3 are computed:  
  
          R2 = E[D[E[N2; S1]; S2]; S1] 
          R3 = E[D[E[N3; S1]; S2]; S1] .
  
  R1, R2, and R3 are then concatenated together, giving 192 bits. The
  first 80 bits are assigned to U1 and the second 80 bits to U2.  The
  rest are discarded.  The unit key U is the XOR of U1 and U2.  U1 and U2
  are the key parts that are separately escrowed with the two escrow
  agencies.

Here, the notiation E[X; Y] means to encrypt 64-bit number X using 80-bit
key Y with the Skipjack algorithm.

U1 and U2 come from concatenating R1, R2, and R3.
Each of R1, R2, and R3 is a function not only of N, the serial number,
along with the 3 fixed 34-bit blocks, but also S1 and S2, the two random
numbers entered by agents from the escrow organizations.


> > The one problem is that S1 and S2 are not changed for each chip, but are
> > rather kept the same in programming a batch of about 300 chips.  Then
> > they are supposed to be destroyed.
> 
> This was not clearly implied, either. Furthermore, no clear reason has
> been stated why all this complexity is needed and U1 and U2 can't just
> be randomly generated.

  All Clipper Chips are programmed inside a SCIF (secure computer
  information facility), which is essentially a vault.  The SCIF contains
  a laptop computer and equipment to program the chips.  About 300 chips
  are programmed during a single session.  The SCIF is located at
  Mikotronx.

I agree that the process seems complex.  Why should the keys
U1 and U2 be correlated with the serial number in this way?  Here is
one thought:

The most straightforward approach would be to get two random seeds,
S1 and S2, and use them to run a PRNG that produces U1 and U2, the
two key-halves, and N, the serial number.

But the problem with this is that you are depending on the security
of your PRNG to ensure that there is no correlation between N and
U1/U2.  Ordinary PRNG's might allow some correlation to exist.  This
would be weak because then just knowing the N of your chip might allow
a good organization like NSA to crunch out U1 and U2 without going
through the escrow agencies, by exploiting weaknesses in the PRNG.

Instead, they go through a roundabout process which appears to show that
the relationship between N and U1/U2 is as strong as the Skipjack
algorithm itself, in fact when run in a triple-encryption mode.
If NSA had a way, given N, to produce U1/U2, then it would appear
that they must be able to break Skipjack, in which case they wouldn't
need U1/U2.  So this key generation process can be argued not to
introduce any new vulnerability in the system.

Hal

-----BEGIN PGP SIGNATURE-----
Version: 2.2

iQCVAgUBK9QrV6gTA69YIUw3AQGGrAP/Rmx0H603b1EdBIsiGuc637wptW133IFU
/irxw+aCPrL3yOzuBTQbUW+LeMIwpC+Y8DARkAohxnIjhuu/aQXVnIvJPPiUSPr0
fz2PLxhA5tgjVAH0e5xvl9K+CgWnRXazd9Tp+Zbi/xAiWz0PI6kff4QtNG13p1xw
/V0dGDb4tec=
=XgfH
-----END PGP SIGNATURE-----

Hal says:
> Here is what Denning's writeup says:
> 
>   At the beginning of a session, a trusted agent from each of the two key
>   escrow agencies enters the vault.  Agent 1 enters an 80-bit value S1
>   into the laptop and agent 2 enters an 80-bit value S2. These values
>   serve as seeds to generate keys for a sequence of serial numbers.
>   
>   To generate the unit key for a serial number N, the 30-bit value N is
>   first padded with a fixed 34-bit block to produce a 64-bit block N1.
>   S1 and S2 are then used as keys to triple-encrypt N1, producing a
>   64-bit block R1:
[...]

I've reread the text again. There seems to be no assurance at all that
S1 and S2 are random or that they are not the same for all chips.
There also seems to be no rational explanation of why N is only thirty
bits long -- its a strange number in the modern world of computing.

> I agree that the process seems complex.  Why should the keys
> U1 and U2 be correlated with the serial number in this way?  Here is
> one thought:
> 
> The most straightforward approach would be to get two random seeds,
> S1 and S2, and use them to run a PRNG that produces U1 and U2, the
> two key-halves, and N, the serial number.

The number N is not secret and is not random -- it is therefore not
necessary that the PRNG generate N, and indeed N is not generated, it
is given. Its presumably just an ordinary serial number.

> But the problem with this is that you are depending on the security
> of your PRNG to ensure that there is no correlation between N and
> U1/U2.  Ordinary PRNG's might allow some correlation to exist.  This
> would be weak because then just knowing the N of your chip might allow
> a good organization like NSA to crunch out U1 and U2 without going
> through the escrow agencies, by exploiting weaknesses in the PRNG.
> 
> Instead, they go through a roundabout process which appears to show that
> the relationship between N and U1/U2 is as strong as the Skipjack
> algorithm itself, in fact when run in a triple-encryption mode.
> If NSA had a way, given N, to produce U1/U2, then it would appear
> that they must be able to break Skipjack, in which case they wouldn't
> need U1/U2.  So this key generation process can be argued not to
> introduce any new vulnerability in the system.

Why not just generate U1 and U2 by a more straighforward approach that
doesn't involve strange padding and odd randomly selected constants?
Indeed, why not just use true random numbers? Surely a radioactive
source isn't unavailable to Mykotronix.

Furthermore, Denning says about 300 chips are programmed in a batch
using baroque methods in a vault. Well, folks, that just won't do if
twenty or thirty million of these babys are being sold a year -- or
even if just five million are sold a year. Seems to me that the
processing is going to have to get more efficient, and likely thus
much more sloppy.

Perry