![[The line key is enciphered by Simple Substitution]](PENLINKY.GIF)
At the design level, the Penknife program is an application of Dynamic Substitution to an error-resilient stream cipher. At the user level, Penknife is an e-mail cipher program which should work with any e-mail system. The Penknife program supports serious key management, which is the heart of a modern cipher.
Penknife builds on the basic concepts of a conventional stream cipher: The classical stream cipher combines a confusion stream with a data stream to produce a ciphertext stream. A conventional stream cipher uses some sort (pseudo-) random number generator (RNG) which is additively combined with data by exclusive-OR. The Penknife design differs by using:
The Penknife components include a random number generator (RNG) and Jitterizer in the confusion subsystem, and Dynamic Substitution and exclusive-OR in the combining subsystem. And ciphertext feedback further complicates the RNG subsystem.
The Penknife RNG produces 16-bit values from a 63-bit internal state. The RNG uses both a standard 32-bit Linear Multiplicative Generator (LMG), and a degree-31 Linear Feedback Shift Register (LFSR). (The deg-31 LFSR primitive is a 17-nomial for better randomization effects.) The two RNG elements step separately, with their most-significant 16 bits combined by exclusive-OR to produce the desired RNG output.
The Jitterizer is a simple but effective mechanism which deletes values from a linear sequence, and confuses the values which are accepted. First, an RNG value is collected, in which two bits represent the number of RNG values to "skip" (1..4), and six bits represent the number of RNG values to "take" in the next take group (1..64). Then the indicated number of RNG values are skipped, with the last value retained as an "offset," to be exclusive-ORed with all members of the upcoming take group. Then another RNG value is produced, exclusive-ORed with the offset, and returned. Subsequent Jitterizer calls collect and offset each RNG value until the number of take counts expire and it is time to skip more RNG values and produce a new offset. The Jitterizer deletes about 10% of the input sequence, but the sequence skips and changing data offsets make the sequence very nonlinear.
The Penknife combiner subsystem takes a single-byte plaintext input, plus two RNG confusion bytes, and produces a one-byte ciphertext result. This occurs in two sequential combinings: The first combiner is a nonlinear byte-wide Dynamic Substitution combiner [1,2], which adaptively randomizes the input codes. This means that repeated uses of the same character are generally assigned different codes. The output of the Dynamic Substitution combiner is then fed into a linear exclusive-OR combiner, which produces the ciphertext output. (Note that a two-level combiner only makes cryptographic sense when at least one of the combining levels is nonlinear.)
In addition to the two levels of combining, the byte data value between the two combiners is fed back into the RNG subsystem by addition mod 2**16 with the least-significant word of the LMG. This means that any character differences between lines will produce different RNG sequences for the rest of each line. This helps make it difficult to explore the Dynamic Substitution tables. It also means that a single ciphertext error is likely to garble the rest of that ciphertext line.
The Penknife cipher uses two identical isolated RNG's: one to develop the Line Key values, and the other to cipher the data. A substitution table is used to cipher Line Key values.
Simple Substitution is useful here because the Line Key values are evenly distributed, thus avoiding the usual attack on Simple Substitution.
We also have the main data-ciphering RNG, which is initialized from a CRC of the key phrase or random key. The main RNG directly drives the combiner.
![[RNG w/feedback, and two-level combining]](PENCIPH.GIF)
The data combiner is a two-level structure. The first combining level consists of a particular Dynamic Substitution table selected from an array of sixteen such tables. The selection is made using a value from the data RNG once per ciphertext line. The second combining level is exclusive-OR. The combiner thus takes eight bits of data and sixteen bits of confusion and produces eight bits of ciphertext.
There is an 8-bit to 6-bit converter which takes 53 enciphered data bytes and 4 enciphered Line Key bytes and produces 76 bytes of 6-bit values (0..63).
![[8-bit values to 6-bit values to base-64 ASCII]](PENASCII.GIF)
A keyed substitution table is used to translate the 6-bit values to network-transportable characters. Keying this table is useful because it provides some added strength at essentially no cost. The 6-bit symbol-frequency statistics are flat, which avoids the usual attack on Simple Substitution.
It is important to keep in mind that the cryptographic cipher proper exists only in the context of a larger design. It seems useful to first generally describe how ciphering is invoked.
Ordinarily, we expect the user to have an alias file of secret keys, each of which is accessible by public alias.
The cipher is given an alias, finds the "closest" alias file, deciphers that file in memory only (using the same Penknife cipher), and produces the current secret key associated with that alias. The "current secret key" can be a long random value, and is the key used for actually ciphering data.
![[The ciphering key comes from an enciphered alias file]](BOTHMASS.GIF)
A key of arbitrary length and content is converted into 63 bits of RNG state using Cyclic Redundancy Check (CRC) operations. CRC-32 is used to build the state for the LMG, while a degree-31 primitive builds the state for the LFSR. This 63-bit base state is placed in the line-key RNG, where it is first used to set up various substitution tables. Each table is first initialized with entries in counting sequence, and then shuffled under control of the Jitterized RNG output, to produce particular arbitrary table permutations associated with a particular User Key.
The network-ASCII table is also permuted under the control of the base-state sequence, thus producing a character mapping unique to each User Key. This is an additional layer of protection which is essentially free, since the mapping is required in any case.
The separate line-key RNG is randomized with the current date and time (and -- in the PC environment -- samples from the high-speed timer) before being used to produce line-key values. Each line key is created from two line-key RNG operations, and is enciphered by byte-wide Simple Substitution. Note that this substitution occurs on highly-randomized values; the character-frequency statistics which normally make substitution weak do not exist at this point.
We assume that the User Key has initialized the RNG's and all the tables.
The 32-bit line key associated with the ciphertext line is treated as an extension to the User Key, being combined into the base RNG state with CRC-32 and a deg-31 CRC. This produces the initial RNG state for the confusion sequence or "running key" for each line.
The resulting RNG state for each line selects one of 16 possible combiner base-states and used as the combiner for that line. The Dynamic Substitution state and RNG state then progress -- change -- through the end of that ciphertext line.
To encipher each ciphertext line, up to 53 plaintext bytes are acquired from the input. Then the Line Key RNG generates a 32-bit Line Key value. The line key value is used to transform the base state of the data RNG into a particular state for that line, and that RNG state selects one of 16 Dynamic Substitution tables.
For each data byte, the data RNG is stepped to produce a 16-bit confusion value. The data byte is combined with confusion first by Dynamic Substitution then exclusive-OR, producing a single enciphered byte. In this way, up to 53 bytes are accumulated.
When the ciphertext line is finished, it is collected with the enciphered line key and translated from 8-bits-per-byte to 6-bits-per-byte format. The 6-bit values are simultaneously coded for transmission and enciphered in a keyed substitution table.
Because the Penknife cipher is designed to be error-resilient, it has no external structure. There are no --BEGIN CIPHERTEXT-- or --END CIPHERTEXT-- flags. The ciphertext blocks produced by different files can be concatenated, which is surprisingly useful.
There is an overall CRC-32 of the plaintext data in each block; the CRC result is enciphered as data. When the file is deciphered, overall ciphering correctness is indicated to the user. The CRC-32 field is deleted and the resulting file length is correct to the byte.
A random overall message key is sorely missed. However, such an entity would mean that a transmission error in the message key would destroy the entire message, contradicting the design goal of error-resilience.
It is interesting to consider the cryptographic use of the much-maligned CRC function. Penknife uses CRC to produce a cryptographic transform from an initial RNG state to some arbitrary RNG state depending on the User Key phrase. (We could consider the result to be a binary vector which is then combined by exclusive-OR with the initial state.) In its favor, CRC is very fast and has a strong mathematical basis for producing a random-like hash from the biased symbol distributions in ordinary text. CRC is linear so it is also weak, in the sense that we could predict the transformation, but that is irrelevant: If The Opponents knew either the external User Key phrase or the internal starting RNG state, they would not have to attack the cipher.
In practice, the 32-bit line keys mean that, for a given User Key, there are 2**32 (4 * 10**9 or 4E9) different initial line states. The Birthday Paradox tells us that we can expect (probability 0.5) two identical line keys (thus initial line states) after only 1.18 * 2**16 or 77E3 lines. (With 53 data bytes per line, 77E3 lines would imply 4 MB of data.) However, at this level we still have (prob. 0.5) only two lines with the same initial RNG state, and those states remain similar only until the first character difference between the two lines has been encountered. As more lines become are available, we may find other sets of lines in which two lines have same line key, but it will (probably) take MANY more lines before we can expect to find even three lines enciphered under one key. Clearly, collecting lines enciphered under one User Key and one line key is going to be very expensive.
(Obviously, given enough ciphertext, it will eventually be possible to find many lines with the same line key. This would allow an Opponent to start the sort of technical attack which is discussed later. This is only one of several reasons to change User Keys periodically; another is the perhaps more-realistic possibility that someone has stolen the key without leaving any signs or other indication.)
Even though the RNG has 4E9 different initial line states, there are still only 16 Dynamic Substitution tables under any particular key. It is not clear how one would go about exposing this internal state.
The ASCII-only output is extremely flexible. Because the jumbled ciphertext lines really are text lines, they can be included in text documents as a way to transport or save binary files. Once Penknife is in place, it can be used to decipher its own upgrades sent by e-mail.
The 64-symbol ciphertext means that for every three 8-bit data bytes we get four 6-bit ciphertext bytes; for every 53 data bytes we have 4 line key bytes; and every ciphertext line must have CRLF. Ultimately, 53 data bytes produce 78 ciphertext characters, a data expansion of 47 percent. This is somewhat more expansion than in other e-mail ciphers (which may not be error-resilient) due to the use of line keys in the Penknife design. But any e-mail -oriented cipher will expand data when they are enciphered, and so will be somewhat inefficient for extensive local file ciphering. On the other hand, the lack of a binary output mode means that the enciphering operator does not need to select "binary" versus "text" output, and the deciphering operator need not be confused by the possibility of two incompatible modes.
Penknife assumes that the plaintext is binary data, which is then enciphered with an overall CRC. The mapping to 64-symbol network-ASCII is random, under a particular User Key. The ciphertext contains no control fields: There is no cipher identification, nor indication of ciphering mode. The only Penknife data structure is the ciphertext line, which should be virtually indistinguishable from any other random 76-character line. Deciphering recovers the original data, strips off the CRC, and announces the CRC result.
Because of the ciphertext structure of independent text lines, ciphertext can usefully be concatenated as ciphertext, without deciphering. This property is useful for collecting ciphertext archives and also creating files which are updated from time to time. The prime example of this is alias files, which hold user keys associated with public aliases. As keys are added and updated, new sections need only be appended to the existing file, without deciphering (and thus exposing) these critical contents.
The Opponent tries each possible RNG state until the cipher is broken.
There are 63 bits of RNG state: Clearly, it is "only" necessary to step through all possible states, setting up all the dynamic tables each time, to "break" the cipher. This is the design strength of the cipher.
The Opponent tries each possible User Key until the message deciphers properly. Try most-likely keys first. (This is most applicable to the alias file key, which may be a language phrase.)
No cipher can do very much about this attack if a user really wants to use a weak key. The advanced Penknife program supports the automatic generation of random keys into an alias file, where they can be selected and used with a non-secret alias tag. This does not completely solve the problem, however, because the alias file itself requires a User Key.
Penknife supports User Keys of virtually arbitrary length, but even a long key is not necessarily "strong." For example, concatenating the names of family members into a long key will not make a good key. A strong key must be unique and unsearchable, and never written down or stored as plaintext in other files. Penknife alone cannot assure this.
Since the alias file User Key must be entered, it can be stolen, and so should be changed periodically. This is easy to do by deciphering the alias file under the current key and then immediately enciphering under the new key. In most cases, it is not the cipher design but instead the alias-file key which is the weakest part of the system.
The Opponent tries various keys, adaptively, and compares the resulting ciphertext to the real ciphertext, to try and gain insight into the correct key value.
Given that CRC is used to generate the internal RNG base state, it is hard to see how any particular bit arrangement could possibly be preferred, or occur unusually often. This is one big reason for using CRC as opposed to, for example, a "cryptographic" hash which has no known strong mathematical basis.
Here the Opponent exploits properties of particular known substitution tables or transformations. Repeated similar transformations on data may produce an uneven distribution of bit probabilities. This information can be used to effectively reduce the number of "rounds" in an iterated block cipher.
Differential Cryptanalysis does not appear to apply to this cipher, because all Penknife tables are "keyed." That is, all Penknife tables are unbiased arbitrary permutations created by an RNG initialized by a particular key. Since proper shuffling algorithms are used, every table permutation is equally probable. This means that the particular table arrangements will be unknown to The Opponent, so the advantage of prior knowledge of a particular table arrangement is lost.
The Opponent accumulates a mass of ciphertext material and tries to find relationships within the data which expose successive levels of the mechanism, until the cipher is broken.
The data flowing through the Penknife cipher are extensively randomized, first by adaptive Dynamic Substitution, and then by exclusive-OR with a pseudo-random sequence. The data then pass through 3-to-4 byte conversion and the network-ASCII mapping table (which is also a function of the User Key). By itself Dynamic Substitution removes the usual symbol-frequency statistics to produce a random-like result, and the exclusive-OR also produces a random-like sequence. Consequently, it is hard to see how one could get a statistical hook into even the network-ASCII table, let alone the rest of the cipher.
The Opponent somehow "obtains" some amount of plaintext and the corresponding ciphertext. Ordinarily, this attack is on a conventional stream cipher using exclusive-OR combining, which will immediately reveal the confusion sequence. The confusion sequence and knowledge of the RNG design are then used to develop the original cipher state, which breaks the cipher.
Penknife has a two-level combiner which combines a single byte of data with two bytes of confusion to produce a single byte of ciphertext. Accordingly, a single known-plaintext byte cannot, by itself, describe the two bytes of confusion which produce the ciphertext.
Nor do single bytes reveal the Dynamic Substitution table state, because the selected table element changes at random after use. In contrast to other stream-cipher designs, known-plaintext will not immediately resolve the confusion value so that the RNG can be attacked.
On the other hand, if we could find enough lines which have the same line key (under one User Key), but different initial character values, we could try to describe the initial state of the selected Dynamic Substitution table. Then, given lines with the same initial byte, but every possible second byte, we could try to describe the complete state of the Dynamic Substitution table after a single character. This would allow us to identify which elements of the table have changed, and thus, implicitly identify the hidden first RNG value, on the way to attacking the Jitterizer (and RNG). Of course, such an attack seems to require that every possible plaintext byte occur both as the first and the second (and then the nth) element, all in the same line key. Because line keys are random-like, this would imply a huge amount of known-plaintext.
All this assumes that some method has been found to surmount the network-ASCII table, or to postpone this mapping for resolution in later analysis. It is not clear how one could do this.
The Opponent somehow arranges to use the cipher at will, but does not know the key. The cipher is used to encipher potentially huge amounts of data specifically -- and sometimes dynamically -- chosen to reveal the cipher.
(It is not clear that this would be a realistic attack in the context of normal secret-key end-user-cipher operation: If The Opponent has access to the ciphering computer, the compute state probably could be stored to a file, which would then contain the internal key. This is more a "black bag" attack than cryptanalysis, but would far easier and thus far more likely under the stated conditions.)
A chosen-plaintext attack can be no harder than the same attack under known-plaintext; the question is whether it would be any easier. Since the line-key values are not under the control of the user, even controlled ciphering is going to require a huge amount of ciphering simply to explore the first and second table states. If the table states can be exposed, we could acquire the 16-bit result from the Jitterizer. But the RNG contains 63 bits of state, so there are about 2**47 ways in which the RNG could have produced that value. This is searchable to the extent that the 63-bit RNG is searchable. But when we include the effect of the 32-bit state inside the Jitterizer, clearly, any RNG output value can produce any Jitterizer result, depending on the internal Jitterizer offset set earlier in the sequence. So the RNG may be attackable, but seems quite unlikely to be broken with a single Jitterizer value, and collecting Jitterizer values indirectly by exploring table state is very, very expensive.
Exploring table state involves the coincidental appearance of every possible character in the last position of an expanding sequence. Consequently, this approach would seem to be exponentially difficult, and to require exponentially more ciphertext for however many elements are required to break through the Jitterizer into the RNG's themselves.
Worse, the RNG sequences on two lines with the same line key differ after the first different data byte, and the value which makes this difference is hidden between the combiners. Thus, we seem to need the Jitterizer value to expose the hidden value to be able to expose the next Jitterizer value.
The Opponent would no doubt like to be able to simply encipher every possible one-character message under a given key. But, again, the line keys are not under user control, and they are 32 bits wide. Still, if there were a complete single-character enciphering under one line-key (and, thus, selecting a particular initial Dynamic Substitution table), it should be possible to completely explore the table (with some constant offset from the exclusive-OR combiner). Then, given any single initial character, if all possible two-character messages could be obtained (under a single line key!), then the second table state could be explored, and the hidden Dynamic Substitution confusion value identified (and this would be absolute, not relative to the exclusive-OR). But all this depends on getting a complete set of ciphertext values under a single line key, and it is not clear how one can do that other than chance. Again, this would be very, very expensive.
And, once again, all this assumes that some method has been found to surmount the network-ASCII table, or to postpone this mapping for resolution in later analysis.
Clearly, the line keys provide significant protection, so it is interesting to speculate about the need for line-key randomness or ciphering.
Without line keys, the cipher is immediately subject to (a still expensive) chosen-plaintext attack. This may or may not be a big deal in an end-user cipher, assuming that only the key-holders encipher data.
Without line keys, acquiring known-plaintext with "every" first byte code could explore the Dynamic Substitution table. Acquiring known-plaintext with "every" second byte code (for some particular first byte code) could explore the Dynamic Substitution table again, identifying differences, and indicating the hidden Dynamic Substitution confusion value, leading to the start of an attack on the Jitterizer/RNG. If "every" second byte code is not available after one particular first byte code, the various Dynamic Substitution tables could be explored, but after the first character, the internal RNG sequences begin to diverge anyway, so to some extent each must be explored separately until the RNG can be cracked, and it is not clear what it would take to do that. Still, this attack would be much easier without line keys.
If the line keys were not enciphered, their effect on the RNG state would be easily computable. Although the original RNG state would not be known, the line-key effect on that state would be known. This would mean that the ultimate change in the first RNG value would also be known. However, the first RNG value on each line is not available for analysis, since it is used by the Jitterizer for "skip" and "take" values. The first RNG value which is produced from the Jitterizer occurs later, and is confused by Jitterizer offset, so the relationship to the line-key is not direct or immediate. And The Opponent would still have the problem of exploring the Dynamic Substitution tables (as well as the Network ASCII table).
If line key values were produced, say, by a counter, they would be difficult to protect by fast, simple cipher. (By itself, a single arbitrary value is easy to protect. However, a sequence of values, produced in a known way, is harder to hide.)
Line key values could be produced by some sort of really-random system. But if really-random stuff is necessary, the design is not likely to be very portable.
Consequently, line keys are now produced by second Jitterized RNG. One does have to wonder whether some characteristic of the RNG could survive both the Jitterizer and Simple Substitution to help The Opponent resolve the line-key RNG state. Resolving that RNG could give insight into line-key effects on the ciphering RNG, and so help crack the overall system. But the use of an RNG which is a combination of two well-known types of basic RNG mechanism, and the nonlinear action of the Jitterizer, make it difficult to imagine how any single RNG characteristic could survive unscathed.
Note that any enhancement to produce line-key values in some stronger random way would be completely compatible with the existing design.
Absent an overall Message Key, and with small (32-bit) line keys, breaking Penknife probably means resolving the initial RNG state, which is the arbitrary value set by the User Key. The cipher thus remains broken until the next key change (which obviously must not be done under the "cover" of the broken cipher). The original, hand-exchanged keys might be used simply to transfer random keys (which are easy to use in enciphered alias files). In this case, the usual periodic key change--which is necessary anyway, since a key may have been exposed without our knowledge--should reset security to original levels as long as the original keys have themselves not been exposed. In the advanced implementation, actual transmission keys can be changed periodically, through the prior establishment of dated aliases for future keys. The alias file User Key should be changed periodically as well.
The current Penknife implementation is a relatively small (47K including substantial "help" information), relatively fast (80 KBytes/sec on a 486/DX2-50), command-line program for DOS on IBM PC-type machines. The current design includes an interactive command-line entry mode which is easy to use under Microsoft Windows. Inner ciphering loops are written in hand-optimized assembly-language for best speed, but the program will run on an old 8088 machine, and requires no numeric co-processor.
The overall cipher design includes extensive key-management features to help create, transport, and use large random keys. Enciphered alias files allow many secret keys to be kept under a single alias-file key, and then selected by public alias. This supports a single key-entry by the user, since, if the key is entered incorrectly, the alias will not be found and ciphering will not occur.
Aliases inherently support painless key-update, since the user continues to use exactly the same alias for each new key. Because each Penknife line is ciphered separately, new keys can be added to the enciphered alias file without deciphering and possibly exposing the existing keys.
Dated-aliases allow keys to be programmed in advance, then automatically selected and used when the date changes. The ability to access old, replaced keys by date supports access to old messages and entire archives. Alias files also support the centralized key-management which is important for business.
Penknife can handle messages containing both plaintext and ciphertext, can automatically find and decipher the ciphertext, and optionally pass the plaintext through to the output file. Because of this, email files normally do not have to be cleaned up for deciphering, and headers and signatures can be kept with the deciphered text. And all of this is done WITHOUT announcing that the text is ciphered, or the name of the cipher, or using "--BEGIN CIPHERTEXT--" and "--END CIPHERTEXT--" bracketing.
The Penknife cipher is a serious commercial design, and is part of a growing family of serious ciphers and cipher engines for software developers. These designs use a wide range of technology to achieve a wide range of speed versus performance tradeoffs in software implementation.
[1] Ritter, T. 1990. Substitution Cipher with Pseudo-Random Shuffling: The Dynamic Substitution Combiner. Cryptologia. 14(4): 289-303.
[2] Ritter, T. 1990. Dynamic Substitution Combiner and Extractor. U.S. Patent 4,979,832.
[3] Ritter, T. 1991. The Efficient Generation of Cryptographic Confusion Sequences. Cryptologia. 15(2): 81-139.
Last updated: 1996-05-31