Tim May wrote:
> So, in these four areas real code is being generated. These get
> mentioned on the list...one just has to notice them, and remember.
> My main point is to refute the defeatism that often is clothed in the
> language of cynicism and ennui. Much is still being done. It isn't
> getting the attention of the press, which is probably a good
> thing. (They have moved on to other topics. And nobody is being
> threatened with jail, so crypto is no longer as edgy as it was when PRZ
> was facing prosecution, when crypto exports were illegal, when Clipper
> was in the news.)
Crypto export has been decriminalized, and cryptanalysis programs are now
illegal "circumvention devices" under the DMCA. I am hard pressed to view
this as an improvement. If DECSS and Advanced eBook Processor produce an
exhaltation of prosecutors bent on putting the authors in jail, I doubt
we'll be hearing if someone invents DE-SSH or DE-AES. This greatly
reduces my faith in the robustness of ciphers, particularly those that
have been around to have their tires kicked for a decade or two.
Break a code, go to jail. Even a silly code, like XOR.
The 90's were the Golden Age of public access to crypto, largely driven by
public key cryptography and the need for people to do secure communication
over the Internet without physically meeting to exchange keys.
The 00's will be the Golden Age of something else. Superintelligent AI
perhaps.
> Even Rivest, Shamir, and Adleman knew essentially no number
> theory. One of them got the idea that maybe the difficulty of factoring
> could be used as the core for what they were doing...I have also heard
> that the idea came from another on the staff at MIT, but I won't get
> into that right now. Then they "crammed" and learned what they needed
> to learn about stuff like Euler's totient function, methods for finding
> primes, etc. It was enough.
Such cryptography is based on faith, much like tea-leaf reading. We have
absolutely no hard mathematical evidence that factoring is any harder than
multiplying or taking square roots, or of the existence of easily computed
functions with computationally intractable inverses.
We infer the existence of such things solely from the observation that the
human mind has not yet produced solutions to such problems. If they were
really easy, we conjecture, someone would have figured out the answer by
now.
Well, maybe.
Evidence is begining to emerge which suggests that such a view may be
fundamentally flawed, and just as most humans cannot multiply 100 digit
numbers in their heads, so there are countless wonderful and simple
formulas whose derivation from scratch is so complex that no one will ever
find them simply by trying to derive them directly.
Are hard problems hard because they have no simple solutions, or simply
because their simple solutions lie slightly beyond the range of our
current deductive radar? Are they hard, or are we simply bad programmers?
Compelling evidence for the latter explanation is beginning to mass.
Consider, for instance, the following simple power series
(Bailey,Borwein,Plouffe) for Pi as a sum of inverse powers of 16. Multiply
by a power of 16 and take the fractional part, and you can compute
hexadecimal digits of Pi starting anywhere.
Pi = sum[0,infinity] [4/(8n+1) - 2/(8n+4) - 1/(8n+5) - 1/(8n+6)] * 1/16^n
Now it's pretty easy to verify that this does indeed compute Pi, with a
symbolic integrator, a pile of scratch paper, and much cancellation.
Going in the other direction, however, is virtually impossible, unless you
already know precisely what you are looking for. Given the task of
locating a rapidly convergent series for Pi in inverse powers of 16,
suitable for calculating arbitrary hexidecimal digits of Pi, one might
very well bumble around calculating forever, without stumbling across it.
The derivation is simply too difficult, and exists in a forest of equally
difficult derivations which don't produce Pi.
So how, one might inquire, did we come into possession of this handy
formula? Well, it wasn't derived in a conventional sense. Instead, a
computer program, PSLQ, a polynomial time numerically stable algorithm for
finding relationships between real numbers, was used to examine all such
formulas, and see if any of them produced Pi. One did.
It is likely our ability to generate algorithms by a direct "grep" of all
formulas having a specific form, and perhaps in the near future, all
formulas under a certain length, will uncover many simple but difficult to
directly derive formulas that do useful things. It is this ability which
poses the greatest threat to cryptography in the current decade, as we
find to our surprise that many of the things we thought were hard, like
factorization, were merely obtuse, like trying to multiply big numbers in
your head.
I think there's a very good chance that by the end of the decade, we will
all be laughing hysterically at how we ever could have thought public key
cryptography and block ciphers were secure, and "crypto" will mean
exchanging CD-ROM's of your one-time-pad at midnight in a fast food
restaurant parking lot.
There is a third reason I think the fat lady has sung for crypto as we
know it, in addition to the prosecutions for cryptanalysis of commercial
products, and our blind faith in the computational intractability of
everything historically unsolved.
Selling crypto to the masses has always been based on the envelope
metaphor. Just as you wouldn't use postcards for all your private
communications, so you wouldn't send them in cleartext across the public
Internet. Encryption is to digital messages, what envelopes are to paper
ones.
It should be noted that envelopes only work if everyone uses them. If
everyone who doesn't have anything to hide uses postcards, and people who
have things to hide use envelopes, then it's pretty easy to know where to
apply the rubber hose.
Envelopes only work to hide secrets if they are mixed in with millions of
indistinguishable envelopes which do not contain secrets. Unfortunately,
we have had a complete failure in the area of making encryption the
standard for all data transmitted over public networks. Ten years after
the start of the crypto movement, virtually no one has encryption
software, and virtually no one encrypts their email. People who want to
encrypt their email can't, because the people they are sending it to don't
have the software to read it.
People have demonstrated that they will not choose privacy if it results
in even the slightest amount of inconvenience, which means that encrypted
messages still stand out like a sore thumb in the data stream. It also
means that were there any movement towards the ubiquitous use of crypto,
the government could disintentivize it instantly, by simply dangling some
free gift or convenience before the masses. After all, these are people
who eagerly sign up for Safeway club cards.
"Delete PGP, Win a Free Turkey," "Cleartext, the anti-Osama," or whatever.
So, ten years after the founding of Cypherpunks, we reach the following
crossroads.
1. Export all the crypto you want, but breaking even stupid crypto will
get you prosecuted.
2. Our faith in the mathematical underpinnings of some crypto may be
fundamentally misplaced.
3. The public won't use crypto anyway, so why do we even
bother? Anything encrypted stands out in the bitstream like a giant
red flag with a smiling Saddam on it.
Yes, folks. It's the End of the Golden Age of Crypto. Time to move on to
the Golden Age of something else.
--
Mike Duvos $ PGP 2.6 Public Key available $
[EMAIL PROTECTED] $ via Finger $
