Re: Who's ahead: NSA or the private sector?

[Bill Stewart <stewarts@ix.netcom.com>]

That's not really a meaningful question.
We can write codes they can't crack.  They can write codes we can't
crack.
The cats are out of the bag, and David Aaron can't herd them back in.

In some sense, the NSA is ahead of academia, because academia publishes,
so they can read everything the Good Guys have done (less six months
waiting to get published in journals :-), while the NSA seldom
publishes.
(There are also corporations doing non-published crypto work,
but not much - they also see the value of open system review.
And the KGB may have been good as well, but they're not in our face,
and we can write codes the Russians and French can't crack either.)
The NSA has almost certainly done more work on analyzing obscure Russian
cryptosystems, but who knows how much of that is just brute force.

But the real problems these days are engineering, not science*,
so it's probably worth spotting them a few bits of keyspace just in
case.
The NSA is better able to come up with a few million dollars to build
custom key-cracking hardware than industry is, so we have to presume
they can do at least as well as a Wiener machine for cracking DES;
they're certainly better at eavesdropping on calls than we are.
I don't know if we can coordinate more workstations for a distributed
crack,
but they _could_ issue the FedCast Secure Screen Saver for all federal
PCs;
the only question is how much time would it spend cracking keys and
how much grepping for suspicious files :-)  There may still be radical 
changes in factoring technology, especially as computers get faster,
but I doubt they'll do more in practice than force us to use longer
keys,
unless someone proves P=NP in the far mythical future or proves that
factoring is in or near P.

The interesting questions are at the boundaries of strong crypto
and weak crypto - 40 bits is a nasty joke, DES is still interesting
for things that don't have too much money riding on them,
Skipjack is probably strong enough for a few years unless there's a 
second back door next to the one with the big "Cops Only" neon sign.
How strong can we make something and still get export permission?
Do we care?  What are the threat models for different "Key Recovery"
scams,
and are we willing to write deliberatlely weak code to collaborate?
Are the non-RSA public key systems good enough until the patent expires?

There are some boundary problems that are interesting for non-political
reasons - now that every toaster and digital wristwatch has an IP
address
and a few KB of RAM, what kind of useful crypto will fit in them?

Key distribution is still interesting - how do you make a system that's
convenient enough to use and secure enough to work?  And distributed
cracking systems are interesting, though the main uses for them are
for cracking known-weak cryptosystems.

Then there's the field of secure databases, which I think has both
practical potential and scientific merit - how do you mix data together
without leaking the secure stuff to unauthorized users, either directly
or through combining lots of non-privileged data.

[*Borrowing from Matt Blaze gratefully acknowledged.]