![[A random value enciphers data, and is itself
enciphered for transmission]](MESKYENC.GIF)
The original 1990 Cloak design demonstrated the practical use of Dynamic Substitution in a large-keyspace message-key stream cipher. Cloak2 is an improved design with added strength, speed and especially key-management, which is the heart of a modern cipher.
Like most stream ciphers, the Cloak2 design consists of a random number generator (RNG) subsystem, and a reversible data-plus-confusion combining subsystem. The Cloak2 design differs from a conventional design by using:
The Cloak2 design is a binary-oriented cipher in the sense that any plaintext file is always translated into binary ciphertext; there is no "network ASCII" mode.
The Cloak2 re-origination unit is the "block," a simple variable-length data structure consisting of a 32-bit length value, and the ciphertext data. (The length value in a one-block file is the same as the overall file length.) Any ciphertext error within a block will affect the rest of that block, but no more.
A single file can contain multiple blocks, which can be separately deciphered into a common result file. This peculiar capability allows keys to be added to an alias file without deciphering the alias file, and also allows ciphertext under the same key to simply be collected in archives.
A CRC-32 of the data is added at the end of the data area of each block so the correctness of the recovered data can be ascertained.
A Cloak2 message key is a large random value which is enciphered and sent with each Cloak2 message. The message key is the actual key which enciphers data. The various user keys simply act to encipher the message key.
When a message is deciphered, the user key acts to decipher the random message key. The random message key value is then used to initialize the cipher which actually recovers the data.
![[The deciphered message key is the key for deciphering data]](MESKYDEC.GIF)
A Cloak2 message key is easier to protect than data, because it is shorter (124 bytes) than the usual message and random. The message key also assures that actual data key is an arbitrary selection from among all possible keys.
The Cloak2 components include a random hash, a key hash, random number generators (RNG), Jitterizers, and Dynamic Substitution combiners.
If we are going to use message keys, we must somehow produce them. Message keys should be random, unrelated, unknowable values. We can produce message keys with a separate cryptographic RNG, but we must somehow initialize this RNG, preferably with a random, unknowable value.
The random hash starts with 124 bytes of unknown existing memory values. Data-entry input characters and PC-platform precision time readings are combined into the existing value. Character sampling and combining continues during data-entry, whether or not a new key is available. The time spent in the hashing loop is data dependent and varies at least 3:1, so the number of samples of a particular input value varies widely. Moreover, human typing delays affect the number of samples per character, the absolute time of key-press, and the key value itself.
Experiments indicate that a single bit-change will "avalanche" the entire 124-byte hash value in five passes. Even in a 386/25 we get about six large-hash passes per second during data entry. Data entry includes both the editable command-line as well as User Key, Alias Key, and Batch Key entry and editing. The result is a an unknowable value which is an arbitrary selection from among all possible values.
The Cloak2 key hash takes a key of arbitrary length and content and produces a 992-bit random-like hash result. The key hash is produced by running 32 different CRC operations over the key, each time using a different deg-31 CRC primitive. This yields 32 results of 31 bits each, which are rearranged into 31 values of 32 bits each.
The use of the CRC operation is warranted because this is just an internal transformation of a secret quantity: Strength comes after this operation. In contrast to so-called "cryptographic hash" algorithms, the CRC is very fast and has a strong mathematical basis.
The Cloak2 main RNG produces 32-bit values using an Additive RNG of degree 9689 with an internal state of 310,048 bits (9689 x 32) and a primitive trinomial. The message key RNG is similar, but uses a degree 607 polynomial.
The nearly 38K of state needed to run the main RNG is developed from a 992-bit (124-byte) original value. The original value is sufficient to fill a 32-bit-wide deg-31 Additive RNG, which (with a jitterizer) fills a deg-127 RNG, which fills a deg-607 RNG, which fills a deg-3217 RNG, which fills a deg-9689 RNG. In every case, the RNG fills separate store, and RNG output is isolated and confused by a "jitterizer" mechanism. Thus, the original 992-bit value is nonlinearly altered four times as it is expanded.
The Jitterizer is a simple but effective mechanism which deletes values from a linear RNG 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. Then it is time to collect another skip / take value, skip more RNG values, and produce a new offset.
The Cloak2 combiner subsystem takes single-byte plaintext input, plus two RNG confusion bytes, plus four more confusion bits, and produces a one-byte ciphertext result. The Cloak2 combiner subsystem has two combining layers: The first combining level is a 256-byte Dynamic Substitution combiner. The second combining level is an arbitrary selection from an array of sixteen Dynamic Substitution combiners.
All seventeen combiner tables are properly shuffled (without bias) by values from the main RNG before data ciphering starts. (Note that a two-level combiner only makes cryptographic sense when at least one of the combining levels is nonlinear. And an array of combiners only makes cryptographic sense when the combiners differ; choosing from an array of exclusive-OR's would not be particularly helpful. This demonstrates how a new component can open completely new opportunities for ciphering architectures.)
The Cloak2 cipher uses two large RNG's: one to produce message keys, and another for data. Each RNG starts out small and uses a "small" 992-bit "init" value which is expanded into the state needed by a larger RNG.
Cloak2 124-byte message-key values are produced by a degree-607 Additive RNG which is initialized by an unknowable value. The message key RNG holds 607 32-bit values, for an internal state of about 2.4KB. The init value consists of the 124-byte random hash value exclusive-ORed with key-related values which are secret and so assumed unknown.
The actual message key values are produced by over 124 steps of the message key RNG. The 4-byte-wide RNG output is exclusive-ORed into a single byte each time, and about 10% of the sequence is discarded by the associated nonlinear jitterizer.
The use of a cryptographic RNG for message keys seems necessary to support massive wildcard ciphering. (A hardware "really random" source of sufficient bandwidth could be used in the exact same cipher, but this does not exist within the normal PC environment.)
The 124-byte "plaintext" message key is expanded into the degree-9689 main data RNG through a sequence of intermediate RNG's of degree 31, 127, 607 and 3217. The resulting (jitterized) RNG is used first to shuffle the 17 Dynamic Substitution tables, and then encipher data.
Cloak2 needs 17 keyed 256-byte tables and possibly 17 more tables for inverses. These are set up in arbitrary sequence by first shuffling an array of values 0 through 16, then shuffling the tables in the resulting order. The unbiased shuffle uses one-byte values exclusive-OR combined from all four bytes of the 32-bit-wide jitterized degree-9689 main RNG.
Ciphering starts by protecting a message key. Some key (probably a long random key from the alias file) is hashed into 992 bits, then expanded into the deg-607 message key RNG. The jitterized sequence from the message key RNG is saved and then exclusive-OR combined with each message key to protect it.
![[The User Key is hashed and expanded through three
jitterized LFSR's before protecting the Message Key]](CLO2MESK.GIF)
The unprotected 992-bit message is expanded into a degree-9689 Additive RNG. The jitterized sequence from that RNG is combined with the data by Dynamic Substitution.
![[The Message Key is expanded through five jitterized
LFSR's before ciphering data]](CLO2OPER.GIF)
For each data byte enciphered, the deg-9689 main RNG produces a 32-bit value. Eight RNG bits are used in the first-level Dynamic Substitution combiner. Four RNG bits select one from among the sixteen second-level Dynamic Substitution combiners. Eight RNG bits are used in the selected second-level combiner, which produces ciphertext.
Deciphering occurs in reverse order with inverse combiners.
Perhaps the most controversial part of the Cloak2 design is the huge 992-bit size of the keys (the internal key and message key). Normally, an 80-bit key would be considered secure against a key-exhaustion attack. A birthday attack on 80-bit message keys could find some identical key values with about 2**40 messages; if this were important, perhaps we could argue that message keys should be 160 bits. So why are Cloak2 keys six times that length?
The main reason for huge keys is that they support a convenient, straightforward design at an acceptable cost. An extra 132 bytes per file seems negligible in the context of modern files, so -- in effect -- there is no reason not to use huge keys. The main expense in Cloak2 is the slight delay for RNG expansion to degree-9689, and this is not related to base key size. The expense involved in running an Additive RNG is independent of RNG size. There is of course some advantage to having a similar size for message key RNG init value, the message key itself, and the main RNG init value. There is also an advantage in using random message key values to directly seed the RNG, since this means that we avoid intermediate processing and so need not discuss the possible weaknesses of such processing. Huge keys also help to avoid the usual simplistic arguments based solely on key size, and so may contribute to a higher level of discussion of the design.
Even with a base state of 992 bits, we can fully seed only a relatively small RNG, and an Additive RNG of degree n can be completely penetrated with a knowledge of only n elements. But the attack must somehow produce n elements of information from the ciphertext, and in Cloak2 we only get one byte of ciphertext for each four-byte element from the RNG. Messages of under 38,756 bytes simply do not contain sufficient information to develop the state of a degree-9689 RNG. Stream-cipher messages with less state than the amount in the RNG are arguably absolutely secure.
The advantage of an RNG with huge state for messages containing more than that state is more ambiguous. Still, it is not completely unreasonable to expect that, if the isolation mechanisms do leak information, they may do so at some fraction of the data rate. This could greatly expand the size of the message such an RNG would arguably protect absolutely. Messages larger than that would be insecure at some cost level -- hopefully high, and repeated for every message. Of course, any cipher can only protect information which is otherwise secret, and virtually any other approach would be preferable to attacking Cloak2 ciphertext.
The step-by-step nonlinear expansion of the main RNG state through four buffers to degree 9689 is almost twice as expensive as a simple linear expansion in a single buffer. One could argue, however, that such linear expansion would allow one to attack the original degree-31 RNG state using the information in final RNG. Consequently, RNG expansion must be (and is) nonlinear.
The Opponent tries each possible RNG state until the cipher is broken.
There are 992 bits of independent RNG state: Clearly, it is only necessary to step through all possible states to "break" the cipher. This is the design strength. (Cloak2 is a secret key cipher and can be directly compared to the 56-bit keyspace of DES. That is, DES has 2**56 possible keys; Cloak2 has 2**992 possible keys.)
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 Cloak2 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.
Cloak2 supports User Keys of virtually arbitrary length, but even a long key is not necessarily "strong." Concatenating the names of family members 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. Cloak2 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 from the User Key, 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 to process the User Key, as opposed to, for example, a "cryptographic" hash which has no known strong mathematical basis.
Note that the resulting CRC state is only used to produce an arbitrary message key cipher value, which ciphers arbitrary message keys. It is hard to imagine how changing the User Key could possibly produce directed results in the main data RNG, for example. Undirected results are unlikely to be useful.
Here the Opponent exploits known 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 Cloak2 tables are "keyed." That is, all Cloak2 tables are unbiased arbitrary permutations created by an RNG initialized by a particular message 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 a knowing a particular table arrangement is lost.
It is certainly true that some table arrangements can be said to be "better" than others in terms of block cipher avalanche. But these "weak" tables may not be weak when used in stream-cipher processing. And Dynamic Substitution tables continue to change during processing, so any possible advantage is at best transient.
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 Cloak2 cipher are extensively randomized by two stages of adaptive Dynamic Substitution and a substantial jitterized Additive RNG. It is hard to imagine how a statistical relationship could survive this.
The Opponent somehow "obtain" 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 is then used to develop the original cipher state, which breaks the cipher.
Cloak2 has a two-level combiner which combines a single byte of data with two bytes and four bits of confusion to produce a single byte of ciphertext. Accordingly, a single known-plaintext byte cannot, by itself, describe the confusion which produced the ciphertext.
Nor do single bytes reveal the Dynamic Substitution table states, because the selected table element (and indeed -- at the second level -- the table itself) changes at random after use. In contrast to other stream-cipher designs, known-plaintext will not immediately resolve the confusion value in a Dynamic Substitution design so that the RNG can be attacked.
The Opponent uses a known-plaintext to develop the values from the RNG, then waits for the RNG to cycle, to use those RNG values again.
Cloak2 uses RNG's with cycle lengths far too large to repeat in practice.
The Opponent accumulates enough ciphertext to find two or more messages enciphered with the same message key, then tries to analyze the initial ciphering state, which must be the same if the message key is the same.
First, identical Cloak2 message keys can only be identified under the same User Key. That is, if the same message key value occurs under different User Keys, it will produce two different enciphered message key values. Thus, we will not know, externally, that the message keys are in fact the same.
Next, if we assume that message key values are "random like," the probability of finding two messages with the same 992-bit message key is very, very, very small. We would expect to find just two messages with the same message key after we have accumulated about 2**496 messages. This is essentially impossible.
Last, note that the Dynamic Substitution combiner state will deviate with each data difference. As the combiner states diverge, analysis of the RNG state would seem to be increasingly complex.
The Opponent somehow arranges to use the cipher at will, but does not know the key. The cipher is 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.)
Since message-key values are not under the control of the user, there simply is no fixed internal state to be examined by using different messages. And since both the Dynamic Substitution and RNG state is dynamic, there is no fixed internal state that can be examined in one message either.
The obvious attack on a single level of Dynamic Substitution is to use defined-plaintext repeatedly to traverse the entire table both before and then after a particular character is enciphered. This will reveal the confusion byte at the combiner so that the RNG can be attacked in the way of the usual exclusive-OR stream cipher. (Note that this requires far more work than the exclusive-OR combiner.)
Cloak2 complicates chosen-plaintext attacks in several ways:
There is no known attack -- not even a theoretical attack -- on a dual-level-nonlinear-combiner message-key cipher like Cloak2.
The current Cloak2 implementation is a relatively small (49K including substantial "help" information), relatively fast (154 KBytes/sec max. 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.
Cloak2 directly supports wildcard mass ciphering, enciphered secret key "alias" files, and enciphered Cloak2 "batch" files of Cloak2 commands:
![[The ciphering key comes from an enciphered alias file]](BOTHMASS.GIF)
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. New Cloak2 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, and automatically 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 important for business. As people leave, alias files can be extended with new keys, and ordinary users can use the exact same aliases and so be impacted little if at all.
The Cloak2 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