[TriLUG] "congress mulls stiff crypto laws"

[Jonathan Magid]

On Fri, 14 Sep 2001, Tom Bryan wrote:

>
> If investigators want to intercept a particular individual's e-mail, work
> with ISPs to intercept the individual's e-mail on its way into the system.
> If it is encrypted, break the encryption.  Certainly, there's an expense of
> computer time here, but how much encrypted e-mail do they actually have cause
> to "wiretap"?  I would prefer to spend the money on the computing power and
> techniques to break the encryption than lose the right to use encryption.
> Note to readers: I don't even encrypt my e-mails, but if I wanted to send
> e-mail instead of the e-postcards, I would want to put an electronic envelope
> around my messages.

I think you underestimate the strength of encryption. There are no known,
publically available computation techniques that will break strong
encryption algorithms. The problem is that public key algorithms like RSA
are based on non-symetric operations. Basically, it cheap and easy to
calculate an encryption (basically multiplication and modulo arithmetic)
but it's very hard to compute the inverse operation.

To decrypt RSA, you must factor a very large number. The only known way to
factor a large number is almost brute force- you try every reasonable
possibility. Factoring is NP- it's non-polynomial time. Each additional
bit of key size doubles the difficulty of the problem. So a 1024 bit key
is 2^512 times more difficult than a 512 bit key, not twice as difficult.
Using known methods of factoring it might take more time than we the
universe has existed to decrypt a 2048 bit key using the most powerful
computers we can imagine. Or something like that (I didn't work it out-
no  calculator around with bignums). Anyway, 2^512 is a really big number.

Although distributed computing methods using the internet have yielded
computation speeds totally unanticipated by the cryptographers, and have
thus decrypted problems which were thought to be forever secure, it's
still easy to add bits to your keysize. And thus double and redouble the
difficulty of the problem.

Now, that doesn't mean that even big-key strong encryption is forever
secure. The NSA has many smart people working for it- mathematicians,
statisticians, cryptographers, computer scientists. It's possible that
they have developed factoring techniques that are unknown to civilian
science. There are many other non-symetric techniques that are the basis
of strong encryption algorithms, but all are NP. It's been mathematically
proven that there are certain problems that are NP-complete. That means
that any NP-based problem can be re-written in terms of it. So if you find
one technique to solve a NP problem in polynomial time, lots of other
problems would crumble in the face of it. But, there are lots of other
smart people who don't work for the NSA, and the problem domain of
encryption and NP algorithms is well studied. So it would be surprising if
the NSA knew something about this that no one else does.

But there are other approaches to get around encryption besides the
strictly mathematical technique. Although the algorithm is strong, the
particular implementation may be weak. A good example is an early version
of SSL in netscape- the programmer used the PID as the seed for a standard
pseudo-random generator. There are very few bits of randomness in a Unix
PID, and they are easily guessed. So the actual range of values for keys
were much much smaller than the theoretical maximum.

Bruce Scheiers book, Applied Cryptography, (the canonical source on
implementing encryption) also describe many other possible attacks. Subtle
man-in-the-middle attacks which manipulate the way programs may implement
trust and transmission.

Just as important, sneakier techniques can lay a hard algorithm low. If
you have access to a person's physical computer or dwelling, you can
capture keystrokes various ways, you can use a sensitive attenae to pick
up the EM emissions of the computer and figure out its operation from that
information. You could plant a small transmitting camera that watched the
user type over his shoulder. So, there are ways.

There are future technologies that may bring current encryption techniques
low. Quantum computing and genetic computing offer promising techniques
for breaking diffult exponential problems in reasonable time. I don't
believe either of these are presently capable of breaking a big RSa key,
but I may be mistaken- the government knows many things they don't share.
Even if current public technologies is not there, Moore's law may apply to
these computing technologies, like it does in silicon. If so, there is
definitely a place where the curves cross and current strong encryption
will yield to these techniques. New forms of encyrption and massively
larger keys might keep the race going though.

Sorry for such a long message, but I wanted to show that simply spending
alot of money on computation power for law enforcement will not enable
them to get into bad-guy's e-mail if its encrypted with a strong
algorithm. In fact, one technique- the one time pad- is theoretically
unbreakable. It's inconvenient to use, but its inpenetrable. But it's
limited by the fact that you need as much key as you have data, and  both
sides must have the same key securely. You must use a new key each time.
But done right- inpenetrable.

It's a hard problem. I think we have a first ammendment and fourth
ammendment right to encryption. Keeping your communications from a
government which finds them inpalatable, could be an important tool in
maintaining civil liberty. But there is clearly a public safety involved
in reading really bad guys communications.

I think the genie is out of the bottle. There is no going back, and
anti-encryption laws will only prevent honest citizens and naive criminals
from protecting their communications. The people who performed this
travesty are neither.

cheers,
jem.

-- 
Global Village Idiot
Email: jem at sunsite^H^H^H^H^H^H^Hmetalab^H^H^H^H^H^H^Hibiblio.org