"wisecrackers" by Levy in March Wired

["Vladimir Z. Nuri" <vznuri@netcom.com>]

I sent this to <steven@echoync.com> but the address bounced.
in any case I thougt I would cc: the list. this is a fun
article to read, and I encourage everyone here to check it out.


------- Forwarded Message

To: steven@echoync.com
Subject: wisecrackers feedback
Date: Tue, 27 Feb 96 18:12:02 -0800
From: "Vladimir Z. Nuri" <vznuri@netcom.com>


hello, I'm a cypherpunk subscriber.

I liked your wired article on the cpunks ("wisecrackers")
a lot. I thought I would mention some things:

1. you didn't seem to address the issue that factoring has
not been proven to be difficult. a 
fast factoring algorithm is not ruled out by any existing 
mathematical theories, although no one
expects that one exists. in other words, it is purely
mathematician consensus that insists that factoring is a 
hard problem. hence RSA has not actually been proven to
be a secure way of encoding information. its only secure
because no one knows how to factor numbers quickly, and
everyone is pretty confident that such a capability
does not exist, although no one has proven it (yet).

RSA rests on the
difficulty of undoing a "trapdoor function" and as 
far as I know, there is no proof that any operation used
for cryptography is intrinsically difficult to undo. 
(there are proofs that some functions are "intrinsically
difficult" but they can't be used for crypto, because what
you need in crypto is some operation that "is difficult when
you don't have secret information, but is easy when
you do."-- that is, not "always difficult".
 that's a trapdoor function, such as that used in
RSA-- the secret knowledge makes the operation possible, 
whereas without it, it is "computationally impossible", i.e.
possible in theory but not practice.)

in fact there have been very incremental improvements in
factoring algorithms.  but no one can say, "factoring number [x]
takes exactly [y] years" because no one knows what is the
optimal factoring algorithm-- they only know the 
best one that has been *found* to date. (which is the quadratic
sieve you mention).

the question of whether factoring really is difficult is
interesting to study. there is a whole class of computer 
problems called "NP" that can be shown to be "difficult"
in an equivalent way. whether they are truly "difficult" is
an open question. surprisingly, factoring has not yet been
proven to be in this "NP" class, despite that many other
problems have been. 

also, some mathematicians say that people have been trying
to factor numbers since the dawn of time (well, at least
since the greeks) so that if there was a good algorithm,
we would probably have found it by now. I would argue against
this position, saying that computers are a very recent
invention on the horizon of human knowledge. the study of
algorithmic complexity did not really begin in earnest until
the 70's or so, again an extremely recent blip of time in
regards to the history of human mathematical thought.

2. I think you were overplaying what Morris said to Zimmermann
at the end. it made for good drama but I suspect the truth is
more mundane.  the fact that he asked "how much would the NSA spend for [x]"
(where here [x] is "break PGP keys").
does not imply that they can actually do [x]. rather, what it
implies is that their first inclination is to assume that
something is theoretically possible, and then determine how
much it would cost to do [x]. then, they determine whether
the stategic results of obtaining [x] are worth its cost.

in other words, the NSA has to approach all cryptoanalysis
from this basic point: can we justify the cost based on the
stategic value of the intelligence. they have to make this 
choice all the time as to where they invest their resources
based on the payoff. their first question is, "what is the
strategic value of cracking [x] code". I believe that
they are run internally such that projects that are feasible
and that they have the money are not actually carried out
just because they are possible-- the strategic value has
to be determined.

what Morris was asking Zimmerman was, "how much would it
be worth to an attacker to be able to read PGP messages".
the NSA might well come to the conclusion that nobody important
is using PGP and therefore trying to break it to read their
messages is a waste of time. my opinion is that what was
implied by Morris's position.

frankly, I think the threat of prosecution against Zimmermann
suggests the NSA may not be able to break the RSA cypher at
certain key lengths no matter how much of our tax money they
burn trying.

3. a group broke a 384 bit PGP key a little while ago. I was surprised how
little coverage this got. perhaps it was due to the choice of keys. 
some are more "respectable" than others. <g> Paul Leyland and
Jim Gillogly (Derek Atkins maybe?) were involved as well as some cpunks.


anyway, keep up the good work.

(heh. loved the description of the media outlets as "bottom 
feeders").

bye

------- End of Forwarded Message