Partial Key Escrow

[Ted_Anderson@transarc.com]

The recent discussion of the SSL Challenge and the revival of the
Software Key Escrow issue brought the following idea to mind.  For the
purposes of this suggestion let's just assume that the goal is to
provide some kind of Government Access to Keys (GAK) for a widely
deployed crypto system such as clipper phones. 

How about if instead of escrowing the whole key with the
goverment/escrow agent you only save some of the bits of the key?  I am
thinking that the goverment would insist that at a minimum all key bits
in excess of some N be escrowed.  Where N is aournd 48.  So if I was
using IDEA with 128-bit keys, I'd need to escrow at least 80 bits and
reveal all 128 bits only to the receiver.  The export version of RC4 is
similar except that 40 bits are hidden and 88 bits are "escrowed" as
plaintext. 

I see the advantage of this is that it might just be palatable to the
government.  In particular, 48 bits wouldn't be any significant burden
on the NSA or FBI for legally authorized wiretaps (I recall that
something like 1000 were performed in some recent year).  It would be a
simple matter for the FBI to budget enough hardware to do brute force
attacks on a few thousand keys a year with a time-to-crack of a few
hours (I doubt most wiretaps are obtained with more time urgency than
this). 

The big advantage to the user is that this provides are well defined
limit on the effort required to violate their privacy.  The biggest
problem with the clipper-type GAK system is that everyone assumes that
in the worst case keys could be obtained illegally with essentially zero
cost.  There are numerous scenarios where the administrative controls
that protect keys break down and the public is left with no privacy at
all.  In this case, however, there is a significant, well-known, and
quantitative (but, unfortunately, time-variable) cost in obtaining a key
even if the adminstrative controls are completely compromised. 

While this doesn't make the privacy of any particular target much safer
it seems it would significantly improve the safety of the public privacy
in aggregate. 

Ted Anderson