Programs DYNSUB and DYNTRAN November 5, 1989 Terry Ritter (512) 892-0494 Blue Jean Computer Engineering 2609 Choctaw Trail Austin, TX 78745 These programs are intended to explain the algorithms for two "cryptographic combiner" mechanisms which I seem to have invented. The programs also provide the basis for assessing the effectiveness of these mechanisms. Each of the two programs combines pseudo-random values with data from standard input, and sends the result to standard output. Two command-line parameters allow selection of "decipher mode" (/d) and initialization of the RNG with a selected key value (/k). These combiners tend to obstruct a "known-plaintext" attack, since they do not easily disclose the pseudo-random sequence, even if the original plaintext data is available with the corresponding ciphertext. Since the pseudo-random sequence is generally produced algorithmically, if it becomes available for analysis, it might (potentially) be fully analyzed and reproduced, which would naturally penetrate the system. Both of the combiners seem to produce a pseudo-random output if either one of their inputs is random-like (even if the other input is a CONSTANT value). This may be a requirement for a secure cryptographic combiner, and is comparable to the statistical performance of exclusive-OR. I call the two schemes "The Dynamic Substitution Combiner" and "The Dynamic Transposition Combiner," for reasons which will soon become apparent. DYNAMIC SUBSTITUTION First, we map characters or bytes through a substitution table; this is Simple Substitution. Then, after each byte is mapped, we CHANGE the contents of the table. Thus, the substitution is "dynamic" in the sense that the substitution mapping changes as time goes on. For example, as in the program DYNSUB, we might exchange the just-used table element with some table element selected at random. So whenever a substitution element is used, that substitution is (probably) changed, and the more often it is used, the more often it is changed. It will be seen that this mechanism AUTOMATICALLY compensates for any uneven frequency distribution in the source text. Since an uneven distribution is the most common way to break a substitution cipher, frustrating this approach seems to be a significant result. In addition, the pseudo-random sequence operates only in the background, to re-arrange the table. In this way, the substitution table continues to change, and the pseudo-random sequence is hidden. Of course, in cryptography, "hidden" is a relative term. For deciphering, an inverse table is maintained and permuted appropriately; to do this efficiently, a non-inverse table is also maintained and permuted. Different symbol alphabets and multi-table polyalphabetic versions are some obvious extensions of the basic mechanism. DYNAMIC TRANSPOSITION First, we fill a block with data, and then shuffle the block; this is a form of block transposition (permutation). In particular, as in the program DYNTRAN, we step through the block element-by-element, and exchange the current element with some element at random; in this way, the pseudo- random sequence selects a particular block permutation. The mechanism is "dynamic" in the sense that no two blocks need be permuted similarly; the block permutation thus changes through time. We also note that such a permutation is reversible, provided that the pseudo-random sequence can be made available in reverse. There are some tricks: First, we shuffle BITS, not bytes; this takes longer, but works much better. (The bits of any particular byte may end up anywhere in the block.) Second, we arrange to "bit-balance" each block, so that EVERY block contains EXACTLY half 1-bits and half 0-bits. This is done by counting the data bits as the block is being filled, and adding appropriate bit-balance data to fill out the block. The bit-balancing gives us a way to GUARANTEE a powerful encipherment, since the strength of a block-permutation is dependent on the frequency distribution of the particular data being enciphered. (Permuting a block filled with occurrences of exactly one value does little good.) The bit-compensation data will be identified and removed as part of deciphering. And we can reverse the pseudo-random sequence (for deciphering) by buffering the desired number of values, and using them from the buffer in reverse. Whenever we deal with data in whole blocks only, the last block may be only partially filled with data, and thus may need to be "padded" to fill it out. But we can arrange the padding so that it is removed with the same mechanism used to remove the bit-compensation. For deciphering, we do the same bit-exchanges as were done in the enciphering shuffle, only in reverse order, and this puts everything back where it was. Since many different random sequences can produce the same block permutation, the pseudo-random sequence seems well hidden. Since there can be no way to know which bits belong together, the data itself also seems well hidden. And the bit-balancing would seem to prevent even a bit-level frequency distribution analysis. Allowing different size blocks, stepping through a block in a non- sequential order, and continuing beyond a single pass through a block are other obvious extensions of the basic mechanism. Since encryption overhead is linear with the amount of data, very large data "blocks" can be accommodated efficiently, and they need not have an even binary length. The combiner can also permute a block initialized as a counting sequence, and end up with an explicit definition of the resulting permutation (each element will bear the value of its previous position). This definition can then be used either for combining or extracting. PROGRAM EXAMPLES An example software implementation is given for each type of combiner. The examples are given in Turbo Pascal 5.5 source code, since this is what I generally use. Obviously, the combiners could be implemented in hardware instead of software, and would make especially nice integrated circuits. The example programs are cut down as much as possible, to show the logic clearly, so they are NOT intended to be cryptographic systems. For example, the programs use the Turbo Pascal RNG, which may be fine for statistics, but is not a good idea for serious cryptographic work. Also, neither program implements a "message key" or any other approach to prevent re-use of a particular pseudo-random sequence. Various other features necessary for serious security are also omitted. As they stand, however, they are probably more secure than some common approaches. The example programs DYNSUB and DYNTRAN function under DOS, and take input from StdIn and send output to StdOut; in general, these would be files. Note that the user must specify these files on the command line as part of the invocation (e.g., "outputfile"). Each program has two optional parameters (which may each be placed anywhere on the command line): "/d", which means "decipher mode" (as opposed to the default "encipher mode"), and "/k", which introduces a key value. The key value is a 9.3 decimal digit positive or negative integer (-2,147,483,648 through 2,147,483,647) which is converted to a 32-bit binary value to initialize the Turbo RNG. For example: "dynsub cipher.txt /k = -1234567890" enciphers the file "plain.txt" into the file "cipher.txt"; then "dynsub /d plain2.txt /k = -1234567890" deciphers it. The plaintext files may be of any length, and may contain any byte values. Executable files may be enciphered, as may archive (library) files. Program DYNTRAN operates in a similar way. FEEDBACK Naturally, I would be interested in comments relating to these mechanisms; please use U.S. "snail mail."