Friday, September 22, 2006

Israeli army's radio security flaws

Had the Israeli army used one of my encryption methods (see previous posts), Hezbollah's resistance might not have been so effective.

Mohamad Bazzi, a reporter for Newsday, disclosed in a Sept. 18 report that Hezbollah intelligence had broken into Israeli army security -- with important military consequences.
Israeli military radio, which uses frequency hopping and supposed strong encryption, was targeted by Hezbollah analysts who may have been using Iranian equipment. It was speculated that some of the radio security breaches occurred because of encoding mistakes by radio operators. Experts can sometimes use such errors to break into an encryption system.
(Search: Hezbollah cracked)

However, even with human error, a onetime keyworm system is highly resistant to timely cryptanalysis. So this suggests the possibility that the Israeli military was using a commercial-grade system, perhaps believing that it had high-grade security. But, I suspect that numerous commercial systems have back-doors required by the various national security agencies. Crypto-communists in the dark hearts of western governments would never permit use of uncrackable encryption systems.

On the other hand, Bazzi's story notes that Hezbollah made effective use of traffic analysis. Hence, Hezbollah likely used volume analysis and direction-finding triangulation to pinpoint command posts and areas of military concentration. In addition, analysts might have identified a few stock phrases appearing in transmissions and used these to identify units.

Overconfidence played a significant role in Israel's failure to score a knockout blow, a general told Bazzi. A raid on a Hezbollah signals intelligence unit came up with the cell phone numbers of Israeli commanders, leading one to wonder whether the commanders were violating signal security through use of cell phones. They are handy and fast, after all.

Saturday, September 09, 2006

Power cipher II

This next cipher (which is really a cipher/code hybrid) couples the pseudorandom generator with an old system, the dictionary method.

During the U.S. Civil War, one method used was the dictionary system, whereby words were swapped according to some specific scheme. For example, the encoder would find his word at the mth position on page x of a copy of a dictionary used by both parties and then go backward or forward n pages and count down to the mth word on that page. The decoder would find the code word on page (x - n) and then find the decryption at position m on the xth page.

Such systems are easy to crack. But, not when hitched to a computerized process!

There are two big advantages to the system I propose.

* On average, there is no data inflation. In many systems, nulls are an important feature for bringing noise into the message. Also, most systems inflate because they are perforce not as efficient as the most efficient Huffman-type codes used for the plaintext. However, this problem does not occur in our system.

* Since the message contains all natural language words, the frequencies will reflect those of the language in the dictionary used. Hence, the fact of encryption won't be detected by simple automated programs that use standard frequency analysis.

Here's the system:

We use a public key method for arranging that the recipient computer receive an identical copy of some lexicon of n words. Then we send a key for a deterministic recursive pseudorandom number generator, plus a set of seeds (initial values).

The pseudorandom function and seed set are automatically changed via public key after specified numbers of transmissions.

Each word in the dictionary is assigned a number, which reflects its canonical (alphabetical) position. At every mth word of the message a new seed is used to generate a new permutation.

The generator then constructs a permutation of the numbers [1, n]. The original lexicon is then put in a bijective relationship with the permuted lexicon. This substitution cipher/code permits the "random" possibility that a word will represent itself. This is helpful in that involutary functions can tell the adversary where a probable word isn't. The fact that the lexicon can have an n as high as 500,000 (approximate number of words in English) means that unscrambling can be put out of computational reach, especially in light of the fact that the permutation is changed so often as to make comparisons of any sort quite unlikely.

This system however does not contain the super-encryption of the system below, which adds to security by masking the pseudo-random number generator. So, in exchange for good camouflage and efficiency, the system sacrifices the extra security of Hill super-encipherment.

A variant of this system: use two dictionaries (even if separate languages). Both must be transmitted to the recipient. The, say, English lexicon of n words is then coupled with, perhaps, a Russian dictionary of n words, which is permuted as above. So the English plaintext comes out as a mostly non-grammatical string of Russian words.

Of course, this natural-language counterfeiter would face a countermeasure in the form of a detector that counts frequencies of common one-, two- and three-letter words, such as "a", "I", "of", "be", "and", and "the." A method could then be devised to outsmart the detector, but at the expense of efficiency (we'd have to introduce nulls).

Thursday, September 07, 2006

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:

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.

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.