1.  Introduction

In the context of text-based messaging systems, the codebook is still a valid technique for producing both compression and confusion.  Codebooks are based on dictionaries as is the predictive word processor.  The combination of the two - sharing a common dictionary - reduces the storage required for messages as well as improving the efficiency of message generation.  The third ingredient of the system is the ability to create a different codebook for each message.  Use is made of RC4's table permutation scheme to provide a substitution table generated from a session key.

2.  Codebook Features

An examination of a Royal Navy codebook of WWII vintage - British Cypher No. 5. - shows a list with space for 10,000 codegroups that represent:

• Words (plus different endings such as plurals)
• Phrases
• Numbers (cardinal, ordinal, fractions and decimals)
• Punctuation
• Dates
• Spelling of words using single letters and digraphs
• Context definition for multiple choices

In the case of frequently used codegroups such as 'and', 'to', 'my' and '.' there are up to 15 homophones - one of which is to be randomly selected.

The book contains a worked example in which a message that in ASCII would take 104 bytes, takes 27 codegroups.  This approximates to a 1.9:1 text compression, assuming that each symbol takes 14 bits and each letter takes 7 bits.  Also, due to multiple choices, there is only one repeated codegroup.

3.  Predictive Word Processors

A scan of the literature yields a number of Predictive Word Processors that are currently available.  These have found a niche market with disabled people who find typing difficult, dyslexics and people with learning difficulties.  Also, they can be useful in military and other rugged, stressful applications such as message entry in arctic conditions where thick gloves are essential.

In an early example of a predictive word processor (Mindreader from Brown Bag Software), as each word is being typed, a menu of options is displayed that offers a single numerical key option to complete the word.  These options would normally be based on the statistics of word usage but other factors can be considered such as context related jargon (cf military ranks, equipment etc).

4.  RC4 (so-called Rivest Cipher no. 4)

The basis of this PRNG is a 256 byte table that is modified by byte swapping every time a random byte is generated.  The transposition consists of:

        x = (x + 1) % 256
        y = (y + t[x]) % 256
        swap t[x], t[y]

where x and y are indices to the table t.  The table has no repeat entries ie it is a 1 to 1 mapping and so it can be used as a substitution table (S-box) and also as a transposition or permutation table.

Variants - the first line can be modified to:

        x = (x + z) % 256

where z is an odd integer.  This effectively remaps the table - but the original characteristics are unchanged.  z is determined by the session key.

Also, the second line can be changed to:

        y = (y + t[x ^ y]) % 256

which makes the algorithm very difficult to run backwards.  However, the effects of using this in a PRNG are as yet unknown and it should be noted that irreversible algorithms can make cryptanalysis easier.

To initialise the table, firstly each entry is set to its index value and then the key is applied so:

        x = (x + 1) % 256
        y = (y + t[x] + k[ki]) % 256
        swap t[x], t[y]
        ki = (ki +1) % kl

where ki is the index to the key array k and kl is the key length.  This sequence is repeated 256 times - although some commentators find this too few.  A good compromise might be to repeat the above 512 times then another 256 times using the irreversibility technique, ie with line 2 now:

        y = (y + t[x ^ y] + k[ki]) % 256

For larger tables, these numbers will have to be scaled up.

5.  The One-Time Codebook

When 2., 3. and 4. are linked together, using a common dictionary, there are some advantages.  One is a reduction in storage for messages by feeding the operator preferred options.  Another is that messages can be stored in their placode form - again reducing storage requirements.

However, the main advantage is the ability to create a One-Time Codebook.  The main feature of this is that the placode consists of a series of randomised codegroups with very few repeats.

Assuming that the messages generally have a maximum length that is conducive with the number of homophones.  (ie the word 'to' shouldn't appear more than 15 times in the message say)  Then the message can be scanned and repeat codegroups reduced by various techniques such as spelling out repeated words, tagging codegroups that are repeated, tagging codegroups to be arithmetically modified and using codegroups for 'repeat codegroup x'.

Confusion can be added by including codegroups that mean 'ignore the next codegroup' and a variety of null codegroups.  (cf the Rossignols' 'Great Cipher' and other works from the history of cryptography)

Finally the codebook is randomised (driven by a one-time session key) using a substitution table and a transposition table - hence the One-Time Codebook notion.  It appears as if a new codebook is created for each and every message.

Assuming a codebook with up to 65536 entries means a 65536 by 16-bit S-box.  To create the S-box, the RC4 approach of starting with an initialised table is used, followed by S-box permutation under the control of a session key.

Again, using the RC4 approach, but with the table the same size as the number of codegroups (or better still, the number of bytes or nybbles) in the message, a permutation table is created from a second session key.

This approach to encryption has some obvious disadvantages in terms of resources required: a 131072 byte S-box, a dictionary of possibly over 500k bytes and the time taken to randomise the S-box.  However, this approach does have cryptanalytical strengths in that the symbol sequences are more random than in a letter based system.  Superencypherment would no doubt be added for very secure applications.

According to Kahn, (The Codebreakers - section on the Zimmermann Telegram), codebooks are broken by looking for patterns generated by punctuation (full stops) and knowledge of the structure of sentences in terms of nouns and verbs - along with a large volume of traffic.  The use of transposition and substitution controlled by one-time session keys should effectively hide these from the analyst.

A simple paper version can be created using a word list.  Create one file with each word at the beginning of a line, pad the line with spaces to column 30 (say) and then add the relevant number from the RC4 table.  Sort the list using column 1.  Create the second file with the number first then the padding and finally the word.  Again, sort from column 1.  File one is the encryption table and file two is the decryption table.

6.  Conclusion

A text based encoding system has been described that overcomes the traditional approaches to codebook analysis.

© November 1999, May 2000 Keith Lockstone

Comments welcome:  Keith

Back to home page