FYI: Clipper Key Generation

[Dave Farber <farber () central cis upenn edu>]

------ Forwarded Message
From: koontzd () nebula lrcs loral com (David Koontz )
Newsgroups: sci.crypt,alt.privacy.clipper
Subject: Clipper Key Generation
Date: 19 May 93 20:56:19 GMT

When viewing a block algorithm E such that a plaintext block  P is operated
on using a key K to produce a ciphertext C (ECB mode):

        C = E(P,K)

C and P are the same size.  There can is direct mapping between P and C for
a given K.  When viewing the cryptographic algorithm as a substitution cipher
the elements of the substitution alphabet are block sized.

The total number of substitution alphabets is 2^K.

The total number of possible substitution alphabets without regard to K for a 
64 bit block is 2^128.  A good portion of these sub. alphabets are not valid 
cryptographically (anything with a high degree of correlation between P and 
C).

Block ciphers are implemented with some algorithm mixing key and data through
several iterations.  Each of these iterations or rounds can be thought of as
a one for one block substitution alphabet specified by the number of key bits
involved in each round. 

With 16 rounds in DES there are 16 substitution alphabets used sucessively:

 P ->S1->S2->S3->S4->S5->S6->S7->S8->S9->S10->S11->S12->S13->S14->S15->S16-> C

Each of these 16 substitution alphabets is specified by a 48 bit subset of
the 56 bit key K.  All 56 bits are used accross the 16 rounds.  The domain
of choices for each substitution alphabet (per round) is restricted by this
key bit sharing and by the algorithm executed each round.  Some small set
of weak and semi weak keys are known to exist in DES.  These exist because
of interaction between the substitution alphabets S1 through S16, where
successive pairs null out the cryptographic value of each other, or
corresponding substitution alphabets taken from opposite ends (palindromes)
null each other out.

The question arises as to just how large the domain of strong keys is.  This
is dependent on the algorithm, method of key selection, as well the domain
of strong keys specifying the substitution alphabet of the block cipher
in its entirety (all N rounds).  It is probably safe to say that the number
of key bits used in each round should be smaller than the number of bits
per block.  The relationship between the selected keys of successive rounds 
of the algorithm an the method for mixing key and data in the algorithm 
are key to the strength of the encryption scheme.

Without this information it would be desirable to have a list of weak and
semiweak keys for the Clipper algorithm as well as any rules for dependencies
to avoid between bits in the 80 bit key.  This information along with the
scientific method would allow the nature of the algorithm to be deduced.

Even a go-nogo evaluation of the key, done by a chip, a chip or software
would provide enough information to deduce cryptographic principles of
the Clipper design, unless these checks rejected a subset of strong keys
for no reason other than to muddy the waters.  The limitations on the
useful key space as a result might prevent this.

A third alternative is that the clipper is declared to have no weak or
semiweak keys.  This would require review by crypto pundits before
general acceptance. (A lot of review hopefully)

Otherwise you have no assurance of the strength of a user selected key without
some information of value to cryptanalysis.  It is not desirable that one of 
the 5 other parties to the shared Clipper secret (VLSI Tech - fab, Mykotronx -
programming, NSA - design, Agency1 - key escrow,Agency2 - key escrow) be 
allowed to provide keys.  This includes the use of a blind, such as a chip 
that
generates strong keys or a third escrow agency that provides key generation 
services.  Two of the six parties to the shared secret are already blind 
cutouts for a third party (NSA): VLSI Tech and Mykotronx.  Handling session
keys with the same degree of security as the unit key would be unwieldly
in complexity, and adds to the risks in operating secure communications.

All the sources on the Clipper chip state several things in common.  Clipper
is a symetrical block algorithm, has a 80 bit key and executes 32 rounds.
To avoid large numbers of weak and semiweak keys some portion of the 80 bit
key must be shared between all 32 rounds (or a lot of rule checking on the
round keys must occur).

There is evidence that NSA provides block ciphers with large supplied
keys.  If these keys are Ks domain (selected for each round), a greater
degree of independence between round keys is allowed.  This would result
in increasing the size of the key domain.  Rule checking becomes even more 
important and specifies that a key generation facility be used.  One side
benefit is allowing each round of the block algorithm to be executed in
1 clock.

Specifying an 80 bit key and 32 rounds may be the corollary without 
requiring a key generation facility.   The key scheduler might require
more than one clock per round as occurs in DES implementations  without pre-
scheduling.

------ End of Forwarded Message