LETTERS

Hidden Secrets

The S-CODER algorithm Robert Stout presented in the January 1990 issue of DDJ seems reasonable, but the programs using it (Listings One and Four) don't give adequate protection against Kerckhoff's superposition. This 19th-century technique is mentioned in the cryptographic hobby literature (perhaps in Secret and Urgent by Fletcher Pratt or The Codebreakers by David Kahn). The method is not very computationally intensive, as one might expect given its age.

Consider Listing One. Suppose NF files are encrypted with the same key. Since cryptext[] does not depend on the plaintext, all the files are encrypted by XORing with the same byte stream X[1], X[2], . . . If P[i,j] is the ith byte in the jth plaintext file and C[i,j] is the ith byte in the jth ciphertext file we have

C[i,j] = P[i,j] XOR X[i]

If we form the set of bytes C[i,j], j = 1, ... NF for some fixed i, all these bytes are encrypted by XORing with the same byte. We can readily find the value of X[i] that decrypts this set of bytes most resembling plaintext. For example, if we assume ASCII plaintext, the space character will be overwhelmingly the most common (ordinarily) and X[i] = (most common byte in the set C[i,j], j = 1, ..., NF) XOR <space> will be right most of the time. We can do this for each value of i separately without worrying about the recursion relating the X[i]s.

For Listing Four the first thing to observe is that the transposition is keyed with a sequence of random numbers whose seed is in the cryptanalyst's possession. He can thus remove the transposition at will. The other problem is that crypt_ptr is initialized to (file length) mod (key length). The file length is not concealed from the analyst, however, and the key length might well be less than 20. With several hundred files encrypted with the same key in his possession, the analyst can assume a key length and then group together sets of files whose lengths do not differ modulo the key length. He can then still use the superposition method on these sets of files. If he has assumed the wrong key length he will quickly notice that the sets of bytes C[i,j], j = 1, ..., NF will have frequency distributions that are too smooth.

I suggest two changes. First, the random number seed should depend on cryptext[] so the analyst will need to deal with a nontrivial transposition. Second, the initial values of the bytes in cryptext[] should be modified using the sum of many or all of the bytes in the plaintext so that the chances of many files having identical key streams X[i] will be negligible. This sum of bytes can be put openly in the file header along with the length, or some more devious method chosen.

  Stewart Strait
  San Diego, Calif.

Bob responds: First of all, thank you for your comments. As suggested in the article, S-CODER isn't necessarily an end in itself, but an embeddable encryption engine. The final listing in the article begins to suggest ways to create more secure applications, although the example I used is subject to fairly straight-forward cryptanalysis. This, incidentally, was deliberate, leaving open the option of embedding S-CODER in a more secure wrapper as a challenge to critics.

Aside from the principle that S-CODER should be considered more of a building block than anything else, the two primary points I'd like to stress are that:

1. The unembellished S-CODER engine was not suggested as being particularly secure when faced with known plaintext analysis, but is rather more suitable for short-term security or unknown plaintext applications. In this sort of application, the only requirement would be that the key is longer than the longest item of plaintext, which might be known by implication (for example, words like "the," a company name, etc.);

2. A truism of data security is that a theoretically secure method known to everyone (e.g., DES) is often less desirable than a theoretically less secure method (e.g., an enhanced algorithm using an embedded S-CODER engine) which is not known. S-CODER buried within an unknown block transposition cipher as suggested in the article, or something equally (or even more) obscure presents the cryptanalyst with the immediate problem of classifying the algorithm before being able to break it. Knowing only that S-CODER is buried in there somewhere is of little help since S-CODER is a stream cipher and any enhanced application will randomize the serial dependencies of the S-CODER encryption.

Addressing your specific objections, cryptext[] is only independent of the plaintext during the first pass through it. The ability (suggestion, actually) to set crypt_ptr at some arbitrarily random starting point within cryptext makes the kind of analysis you suggest much more difficult. If we assume that the initial value of crypt_ptr is determined by some unknown feature of the plaintext, the relationship between i and j in your example will be randomized. In your second point, you're absolutely correct that the implementation in Listing Four is flawed in that the information used to provide the additional security is openly available to the cryptanalyst. Any conceivable method used to conceal the file length would remove this objection. Once this vital piece of information is concealed, the next step is to modify the actual function within which S-CODER is embedded. Ideally it should be fast, as is the block transposition cipher shown in the listing, but the exact method should be known only to the implementor. This is what I meant above when I said that an unknown method may offer more security than a better, yet known, method. The real value of Listing Four is in showing that such methods needn't sacrifice any significant performance over the raw S-CODER algorithm to offer significant levels of security. One of the purposes of the article was to encourage people to think of how to write practical software rather than worry about theory so much. I welcome your contribution and will consider your suggestions in future applications.