From: lwloen@rchland.vnet.ibm.com (Larry Loen)
Subject: Re: Another well-intentioned novice's question
Date: Tue, 05 Jan 1993 16:08:11 GMT
Reply-To: lwloen@rchland.vnet.ibm.com
Disclaimer: This posting represents the poster's views, not necessarily those of IBM
Organization: IBM Rochester

In article <cfG9faf0Bwwb4F5T9z@transarc.com>, Lyle_Seaman@transarc.com writes:
|> lwloen@rchland.vnet.ibm.com (Larry Loen) writes:
|> > In the hypothetical example, compression moves the overall cost up
|> > to 2 to the 60 from the original 2 to the 54.  That ain't chicken
|> > feed, but it will probably not make a serious difference in overall
|> > security, in the end.  If one can exhaustively break DES in a day,
|> > having to wait 64 days will defeat some opponents, but others will be
|> > just as happy on the 64th day as the first. 
|> > 
|> > Note, however, that the key technology remains breaking the basic DES.  Once
|> > one can spring for a cost on the order of 2 to the 54th, it does not seem
|> > like the typical opponent will run out of money at 2 to the 60th or that they
|> > will not simply wait the extra time if they do.
|> 
|> Does it change the analysis if I substitute "month" for "day" above?
|> "If one can exhaustively break DES in a month, having to wait a little
|> over 5 years will defeat some opponents..."
|>

Only at the margins.  You are correct, of course, that most DES opponents
will fail in the example you cite.  There will be some cases, however, where
waiting 5 years is still very worthwhile.

Also, if one substitutes "decade" for "day" above, then compression wasn't
necessary at all, because it is rare data that needs to be secret for a decade
and the fact that compression moves it up to 640 years is kind of ho-hum.
Maybe the historians will lose out, but that's about it.  Besides, if computation
continues to improve exponentially, it won't be 640 years, which means even
the historians will eventually get a shot at it.

An increase in the work function is always a good thing; but compared to the base
work factor of 2 to the 54, moving to 2 to the 60th isn't more than a marginal 
improvement.  I'd rather go to multiple encryption and multiply by more like
2 to the 54th.

|> I have to imagine that it would defeat nearly all the opponents, since
|> most of the data will be well-nigh worthless after 5 years.  Along the
|> same lines, even governments can't necessarily spend 64X to complete
|> a job which would otherwise require an expenditure of X.
|>

Agreed.  But, that's the point.  Compared to the base cost of 2 to the 54,
an added 64-fold increase may run the opponent out of budget.  But, if one is
worried, why not add larger factors?  There is a lot of uncertainty surrounding
work functions of attackers, after all.  One can never be sure that the cost
to an opponent is entirely linear.  What if the cost is N log(N) and the
compression only adds to the "log(N)" part?
 
|> In short, linear increases in complexity with sufficiently large
|> constant factors may provide a better security enhancement than do
|> exponential increases with small constant factors.
|>

It depends on the cases, but you can certainly construct examples where this
is true.  Question is:  Does it apply to the successful opponent, whose 
technique you aren't sure of?  I'd rather go for exponential stuff, because
it has higher odds of actually adding to the work.
 
|> Not a flame, just a nit.
|>

But, an illuminating one, I think.  I claim, still, that compression should
be done as an economy-of-transmission move and not a security move, per se.  If
one fears that 2 to the 54th (or, whatever one presumes the work factor to be),
isn't enough, one should enhance the _encryption_ by a large factor (>= 2 to 
the 32 or so) and take any added security from compression (which isn't always 
available anyway) as a bonus that one does not count on _as a matter of design_.
 
|> Lyle		Transarc		707 Grant Street
|> 412 338 4474	The Gulf Tower		Pittsburgh 15219
|> "I don't believe it!  I believe it, though..." 	- kazar

-- 
   Larry W. Loen        |  My Opinions are decidedly my own, so please
                        |  do not attribute them to my employer