Privacy

Zimmermann Legal Defense

CypherPunks

Pretty Good Privacy

by Adam Back

Crypto Law and Politics

Any discussion of encryption technology at the moment is pretty much bound to rapidly turn into a political discussion about the US restrictions on the export of software utilizing encryption. The International Traffic in Arms Regulations (ITAR) classify encryption software as munitions, along with nuclear weaponry, tanks and heavy artillery. In order to export software which uses encryption, it is necessary to register as an arms dealer and request an export license on a per product or even on a per sale basis depending on the strength of encryption used. In practice software companies have found that the NSA (US National Security Agency), which has the final word on what gets the go-ahead, refuses a license for almost all software using encryption which they can't routinely break.

Naturally this places US software vendors at a disadvantage compared to European companies, who can ship secure software packages without regulation. It is this situation which has frustrated US software companies in gaining market shares in non-US, and indeed in US markets (there being no corresponding restriction on imports). The US software industry has been pushing for cryptographic software to be removed from the list of export regulated equipment, but this policy is fiercely defended by the NSA, which claims such a move would harm national security.

In practical terms, the widespread global availability of cryptographic software has meant that most third world terrorist groups have access to stronger encryption than that currently used by US financial institutions. The US industry would claim that the export restrictions are an archaic hangover from the cold war era; these restrictions are hampering todays rapidly expanding digital communications industry, which urgently needs the use of encryption as an enabling technology for electronic financial transactions.

The reader will note that a few years have passed since the export restrictions on shipping personal computers from the US to certain parts of the world were lifted, and there doesn't appear to have been any major impact on world peace. The personal computer case is interesting here because it has similar features to the ITAR restrictions on crypto, in both cases the restricted items had wide availability outside the US: Taiwan, Korea and others were and still are major PC clone manufacturers, and it was eventually admitted that the export policy was out of place. The US software industry, which is estimated to be losing billions of dollars of trade each year as a result of crypto restrictions, would like to see the crypto regulations follow the same path to deregulation as personal computers.

If you're asking yourself why arbitrarily secure crypto-systems need concern you as an individual: "I have nothing to hide", cryptography isn't just about paranoids exchanging secret messages with each other, and contrary to what governments would have us believe it's not just spy organizations and financial institutions who have a need to use encryption. It's about changing the balance of power in a world where the governments dream of the centralized instantaneous control that computers have made possible is quickly becoming reality. Not all governments are benevolent, and even the more democratic have an unfortunate historically proven habit of mis-using power occasionally. Do we really want our governments to be holding all the "master keys" (driver's licenses, credit cards, National ID Cards) that connect everything we do together. One such (failed) US government scheme was the clipper fiasco, involving "key escrow" (read Government Access to Keys), which would have seen government access to all clipper-phone communications. Even if you buy the merits of key escrow you should consider that, even if for no other reason, democratic countries should be setting a good example to other countries in terms of reasonable cryptography laws, otherwise we will have an indefensible position in the ensuing rights problems which will undoubtedly occur when less democratic countries adopting schemes involving key escrow. Cryptography has a profound and important place in keeping the correct balance of interests in the rapidly emerging global computer community, it is your future which is being decided by todays policy makers, stay informed.

Public Key Encryption

The invention of public key encryption in the 70s has greatly improved the practical usability of encryption, it allows for the secure exchange of information between two parties with out the need to exchange secret keys which has always been a problem with conventional encryption schemes.

Public key schemes solve this shortfall by having two keys: one to encrypt, and another to decrypt. Messages encrypted with a public key can only be decrypted by the corresponding private key. This removes the need for secure key exchange as you can exchange public keys in the clear, as all the public key does is allow someone to encrypt a message for the owner of the key pair.

The Rivest-Shamir-Adelman (RSA) public key algorithm was published in the ACM (an international journal) in 1979, by researchers at MIT, Adi Shamir (the S in RSA, and an Israeli national), has since returned to Israel, where he continues to pursue his research in cryptography. The security of the RSA crypto-system is based on the presumption that factorizing numbers with large prime factors is hard. Whilst there have been several significant improvements in factorizing algorithms since the RSA paper was published, these advances have been easily compensated for by increasing key sizes. RSA key sizes of 2048 or more bits are considered to be extremely secure at present. Part of the RSA systems strength is that the difficulty of factorizing the RSA modulus (part of the public key) increases exponentially with increases in key size.

This algorithm has a clever design, but the math involved is elegantly simple. The encryption / decryption algorithm is very simple, and the key generation moderately easy to follow, RSA key generation produces three numbers: n (the modulus), e (encryption key) and d (decryption key):

The public key is the pair of numbers n and e.

To encrypt, we take a message M represented as a number, and calculate the cipher-text C:

             e
        C = M  mod n

It's that simple, there are various optimizations to speed up the calculation but this is essentially what is going on in RSA encryption. To decrypt the message, you reverse the process with the cipher text C, and using the decryption key d as the exponent:

             d
        M = C  mod n

In fact the whole process is so simple, and so widely published, that to attempt to restrict the export of software implementations of this is completely ineffectual. To highlight the bizarre nature of export restrictions, we present here a program written in the perl scripting language which when typed in on a Unix or IBM PC running DOS (with the perl and dc utilities installed), allows you to encrypt and decrypt messages using the RSA algorithm.

-------------------------------------------------------------------------------


#!/usr/local/bin/perl -s
$e-$d&(($k,$n)=@ARGV)==2||die"\$0 -d|-e key mod out\n";$v=$w=1+length$n&
~1;$v-=$d*2;$w-=$e*2;$_=unpack('B*',pack('H*',1&length$k?"0$k":$k));s/^0+//;
s/1/0lM*ln%/g;s/0/d*ln%/g;while(read(STDIN,$m,$w/2)){\$m=unpack("H$w",$m);$a=
`echo 16oOi\U$m SM$n\Esn1$_ p|dc`;print pack("H$v",'0'x($v+1-length$a).$a);}


-------------------------------------------------------------------------------

The above program is hot property, probably the smallest, most innocuous looking piece of munitions you are likely to set eyes on. If you were to be caught exporting this software (all 4 lines) from the US you would probably be contravening the ITAR export restrictions (the author lives outside the ITAR zone, in the UK). Needless to say this program (which the author has for a signature file) has spread rapidly through the Internet amongst those with an interest in encryption, and/or perl hacking. Somewhat paradoxically, it can be published in this international journal, as printed works have certain rights which are not currently afforded to electronically transmitted material. Putting it on a floppy disk and mailing outside the US, or posting it to usenet could probably be interpreted as export. The T-shirts have already been printed! A T-shirt with the code in an OCR font and the caption:

"Warning: this shirt is classified as a munition, and may not be exported from the United States, or sold to a foreign national"

The shirt also has a barcoded version of the program on it, a nice subtlety which ensures that it, like the floppy disk, is in "machine readable form", and hence really is illegal to export from the US. The shirt is available, at cost only, from Joel Furr (see URL references below).

Here's a quick example of how to use the above program to encrypt the nonsensical message "squeamish ossifrage" (those who have kept up-to-date on crypto current events will recognize these as the keywords in a message Rivest encrypted as a challenge in the 1979 paper).

These test keys are 32 bits, but the program has usable performance even for 1024 bit keys (as used in warhead release sub-systems all over the world):

Encrypt with test public key ( e = 10001 and n = 1967cb529 ):

echo "squeamish ossifrage" | rsa -e 10001 1967cb529 > msg.rsa

and then to decrypt provide the private key (decryption key: d = ac363601), and using the modulus n again:

rsa -d ac363601 1967cb529 < msg.rsa

If you know any perl and can see any ways to shorten the code further please contact the author.

Cypherpunks

The author subscribes to the cypherpunks mailing list, a list dedicated to the discussion of such hot topics as anonymous electronic cash, 2nd and 3rd generation anonymous remailers, data havens, changes in crypto law and their privacy implications. The list members, ranging from crypto and security experts to privacy advocates, closely track government policy changes for hidden crypto agendas, from a pro-privacy point of view. The title of this article stems from the cypherpunks motto: Cypherpunks Write Code! Members of the list are often amongst the first to implement new advances in crypto technology, with anonymous electronic cash implementations, digitally mixing remailers, DC-nets, as well as the occasional 4 line crypto-system.

To subscribe to the cypherpunks list send a blank email message to majordomo@toad.com, (an auto-reply daemon will send you the info), or for an automatically converted hypertext version look at the URL:

Vince Cate's comprehensive cypherpunk references page:

ftp://furmint.nectar.cs.cmu.edu/security/README.html