This note is a follow on to a previous posting entitled 'A Class of Steganographic Protocols' (sci.crypt.research, 29th Nov 1994).

As background, some comments from William Friedman are apposite.  (Taken from: Special Text No 165, 'Elementary Military Cryptography', 1935 edition, Part 4, Section XX)

h.  The formation and adoption of fixed habits as regards the phraseology of messages, arrangement of contents, use of punctuation, etc., is a most dangerous practice, and will assist the enemy cryptanalysts very greatly. Routine reports of all kinds should be sent by means and agencies not susceptible of interception.

i.  The beginnings and endings of all secret messages are cryptographically their weakest spots and are usually the points first to be attacked and solved by the enemy cryptanalysts. If the address and signature of a message must be cryptographed, this should be done according to a different system than is applied to the interior of the message. Sometimes a special address and signature code must be provided for this purpose, which code must not be employed for any other purpose.

The terms 'beginnings and endings' can be expanded by including the notions of edges, boundaries and discontinuities. Also, the principle should be extended to all processes that are involved in encipherment.

1.1  Padding

It is usually suggested that padding the plaintext with a random prefix and suffix can be used to disguise stereotypical messages and hide such repetitive formats as greetings and signatures.

Also, it is worth pointing out that the latest generation of word processors are extremely helpful to the cryptanalyst. If, say, a series of memos are generated, using the same text format, printer setup etc, then it is certain that several kilobytes at the start and end of the files are very similar.

1.2  Random Sources

Random ASCII text, Random Generators (One-Time Pads) and Pseudorandom Generators should all be usable in the scheme. Random Text could be quite effective, in particular when text compression is applied subsequently.

1.3  Desirable Features

1.  The protocol that delineates the random sections must be minimal in order to avoid attack.

2.  The protocol must enable the sender to totally control the amount of padding. This will help defeat traffic analysis.

3.  It should be possible to apply padding before and/or after encryption.

4.  The amount of padding should be variable down to the bit level. This would enable a file to be an integral number of blocks long, without forcing the enclosed message to be aligned on the same boundary.

5.  The protocol should be usable in traditional systems such as columnar transposition - facilitating the manipulation of letter frequency characteristics etc.

2.  Method

The method has two features that liken it to the previous posting: a) the use of bit inversion to mark a boundary and b) the use of a known random generator. The process is as follows:

2.1  Adding the Padding

(Assume source file F_S, Target file F_T)

a.  Calculate the number of padding bits P_B that satisfy boundary alignment and other criteria.

b.  Split P_B into header and tail bits, so that P_B = P_H + P_T.

c.  Initialise the random generator.

d.  Copy P_H bits from the random generator to file F_T, inverting the last bit.

e.  Copy all the bits of file F_S to file F_T.

f.  Copy P_T bits from the random generator to a temporary file, inverting the last bit.

g.  Append the temporary file (in reverse) to file F_T, ie starting with the last bit in the temporary file.

2.2  Removing the padding

a.  Initialise the random generator.

b.  Compare the generator output with the start of the file and stop when the bitstreams differ. The next bit is the start of the message.

c.  Compare the generator output with the end of the file (moving towards the start of the file) and stop when the bitstreams differ. The next bit is the end of the message.

The choice of random generator and its initialisation are left to the implementer. Their parameters must be considered in the light of the overall cryptosystem design.

© November 1995, Keith Lockstone

[Moderator's note: The problem of fixed message headers and endings and standardised message formats (eg "Nothing to report") was a major factor in helping break Enigma. The Allies avoided this with (a) random padding of messages and (b) splitting the message in two and swapping the two halves so that the less-predictable message body was at the start and finish. If my memory serves me correctly, one of the cryptographers operating in Vichy France before it was occupied used to encrypt his dispatches to England with Enigma using this technique, appending "Heil Hitler" as the padding at the end. As far as anyone knows it was never broken].

Comments welcome:  Keith

Back to home page _{cipher,crypto,cryptography,cipher design,encryption, steganography,Friedman,bookends,czczcz}