Exporting strong encryption?

In the post 9/11-era, U.S. policy concerning the export of strong encryption technology is something of a mystery. The NSA has never liked strong encryption for the masses and has long fought to find ways to limit its availability.

In the Clinton years, the burgeoning of computer-to-computer financial transactions put business on the side of the privacy advocates. An arms-export case against Phil Zimmerman, who made strong encryption available via internet download, was dropped.

It has been reported however that an Iranian assassination plot was solved because Crypto AG sold the Iranians a strong encryption program that had a backdoor through which the U.S. could enter. So one must worry when downloading Zimmerman's PGP program that one is not receiving a lookalike program with a hidden key available to intelligence agencies. Considering the NSA's attitude in general, I'd say there is a fairly strong chance of such a Trojan Horse compromise.

Obviously if the NSA's no-warrant wiretaps are being used against encrypted phone calls from "terror suspects" they would be of little use unless the NSA could decipher the messages.
Yet, when one checks the FBI's cybercrime page, export of strong encryption is not listed as a concern. The State Dept. these days has little to say, other than the claim that it checks to make sure strong encryption products exported to China are used strictly for business and not for military purposes.

Bush, without going into specifics, has signed an executive order continuing Clinton's executive order intended to limit the export of dual-use technology, including strong encryption.

Additionally, Congress wants internet phone services to build in technology that makes it easy for the feds to wiretap.

So I am going to provide an algorithm that a competent programer could turn into a super-strong encryption system that can be used by anyone.

But before doing so, a couple of remarks:

* Slower public key cryptography may well be safer than courier for passing of keys to the faster symmetric key encryption systems. But, public key systems are particularly vulnerable to the cryptological blunder of encipherment of the same plaintext with a different keytext. Cryptanalysts can then compare the cryptotexts and divine the particular key.
So we can well imagine that the NSA has a "crib" exploitation unit that specifically works on this weakness of public key systems. It is quite likely the agency uses network theory and Ramsey theory in its search for significant patterns that would disclose such weak points.

* A system, such as the so-called one-time pad system, that uses a randomly numbered key that is at least as long as the message is provably uncrackable in principle, though human error, such as occurred in the Venoma affair, can lead to compromise.

* The following algorithm can be adapted in such a way as to provide highly secure internet phone links that bypass wiretap backdoors.

Actually, I am not going to give a formal algorithm but an outline that is sufficient to enable a computer programer to set up the system. This public knowledge does not significantly affect the effectiveness of the algorithm, unlike the case of numerous other "strong" encryption programs.

Our asymmetric system uses the public key method to initiate the efficient symmetric key method. That is, the private keys are provided during public-key communication.

The primary private key is simply a recursive deterministic pseudo-random number generator with a specific initial value. The function is chosen with an eye to assuring that its complexity is such that there is no known way to arrive at the nth value without a computer doing about the same amount of work.

The receiver then has that generator and is able to determine the key using it and the proper initial value.

The number can be used to encrypt a message in two ways:

1. The number can give the permutation of the binary digit number representing a block of plaintext.

This is similar to how DES and AES work. Even in the 1970s it was believed that NSA supercomputers could find all relevant permutations of a 58-digit number (in binary). These days, block lengths of 2^10 digits are recommended. Note that because of constraints of coding (not encipherment), cryptanalysts could weed out numerous permutations as no-go's, thus cutting computer time substantially.

2. The number can be used with the ASCII character set prior to encodement. That is, the software cuts the message into specific block lengths. Each ASCII character tops a column composed of pieces of the long digit string (number). These smaller numbers represent the character. Once the program enciphers a charcter with one member of the column, it uses another member for the next appearance of that character. Probability of the same number appearing twice is very low.

Example using artificially small strings:

A B C
0110 1111 1010

1111 1100 0101

0011 1110 1100

That is, the generator produces 011011111010111111000101001111101100 and breaks it up by following the standard ASCII character order.
"CAB" would then be enciphered 101001101111. A second encipherment of "CAB" would yield 111111000101.

As long as the number is effectively random, messages so enciphered are uncrackable. However, it is left to the programer to devise a subroutine that chooses pseudorandom numbers of some specific block length. This generator should change at specified intervals. Compromise of the generator is a significant concern.

However, secondary encryption (superencryption) is the next step. Being aware that methods have long existed for stripping off simple multipliers or added sums, we resort to the classical Hill cipher. Once the pseudorandom number is generated, another program uses linear algebra to encrypt that number. That is, a noncommutative multiplication is made on a matrix composed of pieces of the digit string.

A secondary key is the matrix A which is used to multiply B, which is composed of some set of elements of the digit string. With the property of invertibility included when selecting A, the receiver is able to recover the pseudorandom number.

The purpose of superencryption is to disguise any possible tell-tale signs inherent in the pseudorandom number that might imply which recursive generator was used. That key should also be replaced regularly via the public key method.

So, now the question here is: does this post, available internationally, violate U.S. strong encryption export laws? Also, is there any point to such laws, considering that competent programers can presumably rather easily implement strong encryption.

Also, software using this method can be adapted to internet phone links, and downloaded into PCs.

Of course, one must still be aware of the fact that terminals give off characteristic electromagnetic emissions that give away what keys are being pressed. An eavesdropper with the right equipment can park in a van nearby and record the plaintext before it is encrypted. Material to absorb such emissions is on the market, but the government apparently makes its purchase difficult.

By the way, this method can be adapted to stream encryption, which is encipherment one digit at a time. As long as both random number generators are in sync, each binary digit can be pseudo-randomly enciphered as either itself or its complement. In that stream encryption is usually chosen because speed is valued at the expense of airtight security, we may wish to dispense with the super-encipherment step.

Otherwise, we can use a second pseudo-random number generator for that step. This provides no additional security for a truly random first step. However, pseudo-randoms have certain telltale traits, which might enable a cryptanalyst to discern the specific function used.

Also, one might super-encrypt with a Hill cipher thus: A X B, with A constant and B having all matrix positions but one constant. That matrix hole is filled with the particular pseudorandom digit.


UNDER-THE-RADAR ENCRYPTION
Suppose you'd rather that the authorities not know that your message is encrypted. You could use steganography, the art of concealing the message's existence.

These days, however, there are a lot of messages and so, we can surmise, automated programs are used to sniff out those messages that are encrypted and copy them for further analysis.
They detect encryption with frequency analysis. It's simple; each natural language (and technical language variant) has a unique frequency distribution that is summed up as the index of coincidence. That is, on average, in English "e" appears about 12% of the time and other letters have typical probabilities of occurrence. So if we add up the probabilities we get a unique sum.

Hence, a program can analyze the frequencies of characters showing up in a text and determine whether the sum is within the bounds for a known plaintext language. If not, the program will assess that the text is probably encrypted.

To evade this detector, we simply require that a program be devised to require that every number that appears in the text be repeated according to its typical frequency. The decryption program knows to ignore all repeated numbers as "nulls." Of course, we must make sure that the ratio of keytext length to message text length is such that a number isn't repeated as a non-null.

Now this preventive measure will slow down encryption-sniffing. But we can imagine that programs used for mechanical translation from one language to another can be adapted for use as encryption sniffers.

The addition of these "nulls" does nothing to upgrade the security of the encryption itself. Their purpose is simply to make spotting of encrypted messages tougher for traffic analyses programs.