Re: The NSA Visits Compendium

I don't know anything about uninvited visits, but I did once interview the
designer of a major product about getting an export license. He said that
the NSA were fairly thorough in their review of the product. The most
interesting thing that he mentioned was thatthe company had to guarantee
that the data would never be encrypted sequentially by two _different_
algorithms. Apparently double encryption by 40-bit RC-4 was okay, but using
different algorithms was
verboten. This seemed odd to me at the time and I asked him twice about it.
He agreed that it was weird, but they had no problem with guaranting it.

This led me to these notions:

*) Maybe double or triple DES isn't that great an idea. Maybe the NSA knows
some neat algorithms that can create group-like actions even if the
encryption process isn't a group.

*) Maybe there was a communications problem and no one knew what was being
asked.

*) Maybe the cryptanalysis boys never really talked that much to the folks
who go around regulating export. After all, denying export licenses for
small details is like telling people that certain small details can
confound analysis. This is a leak of information from the NSA which doesn't
seem to like these things.

In general, I think communications between the NSA and the companies begin
when software companies make unofficial inquiries about what is exportable.


-Peter

On Mon, 16 Oct 1995, Peter Wayner wrote:

> [...]
> The most interesting thing that he mentioned was thatthe company had to 
> guarantee that the data would never be encrypted sequentially by two 
> _different_ algorithms. Apparently double encryption by 40-bit RC-4 was 
> okay, but using different algorithms was verboten.

Very interesting indeed.  With RC4 the bulk of the time is in key setup, 
so if they could do two setups in parallel then the total time to search 
a double-encrypted 40 bit keyspace would not be that great.

I suppose they could even 'weight' the number/power of processors assigned
to key setup such that the setup ran as fast as the trial decryptions,
then just proportionally increase their number until you get an acceptable
search time.  I know precious little about parallel processing so this
could be idle speculation. 

Can the same parallelisation be applied to other popular ciphers?


- Andy

+-------------------------------------------------------------------------+
| Andrew Brown  Internet <asb@nexor.co.uk>  Telephone +44 115 952 0585    |
| PGP (2048/9611055D): 69 AA EF 72 80 7A 63 3A  C0 1F 9F 66 64 02 4C 88   |
+-------------------------------------------------------------------------+