Cryptology: Letter Frequencies in Artificial Languages

Cryptology

Letter Frequencies in Artificial Languages

a7Hzq .#5r< kÜ\as TâÆK$ ûj(Ö2 ñw%h: Úk{4R f~`z8 ¤˜Æ+Ô „&¢Dø

MS-DOS-EXE Files

Byte	Frequency
`00`	ca 8%
`8B E8`	ca 3%
`06 FF 20 74`	ca 1.8%
`04 50 02 75 01`	ca 1.4%
`03 46 65 B8`	ca 1.4%

The values fluctuate widely.

The frequency of the bytes 65 (letter e) and 20 (space symbol) depends on the portion of embedded text in natural languages.

Therefore the cryptanalysis by statistical methods is significantly more difficult than with natural text.

The method of pattern recognition is indispensable.

Programs in Pascal

Character	Frequency
Space symbol	ca. 25%	An author who uses a lot of separating lines :-)
- (dash)	ca. 6%	An author who uses a lot of separating lines :-)
e LF CR	ca. 3.5%
R N ; : E n	ca. 2-2.5%	depend heavily on the author
O a T , I l	ca. 1.5-2%
u = ' ( ) D S	ca. 1.2-1.4%

The frequencies depend on the style of the programmer. In the example the author

wrote keywords in capitals,
included a lot of commentaries in natural language,
used many spaces for optically structuring commentary blocks,
inserted many commentary lines consisting of dashes for optically structuring the source code.

Specific Characteristics:

CR/LF is a typical bigram = end of line (in the MS-DOS world); together with the command separator »;« this reveals the structure of the program.
All kinds of brackets occur pairwise.

Cryptanalysis by statistical methods is significantly more difficult than with natural text.

Pattern recognition methods are indispensable.

MS-Word (.doc Files)

Byte	Frequency
`00`	ca. 7-70%
`01`	ca. 0.8-17%
`20` = space	ca. 0.8-12%
`65` = e	ca. 1-10%
`FF`	ca. 1-10%

Observations:

All bytes 00-FF occur.
The values fluctuate widely, over and over again we find unexpected frequency peaks.
Using a hex editor we see long chains of 00 bytes. These reveal large parts of the key for an XOR encrypted file.

Here is a sample encrypted MS-Word file.. Exercise: Analyze it and decrypt it. You will need a hex editor, and maybe an XOR program.

The last remark leads to an efficient method of cryptanalyzing XOR-encrypted files that use a periodically repeated key: Add (by XOR, that is binary) the blocks pairwise. If one of the blocks corresponds to a plaintext block with predominant zero bytes, the the sum yields readable plaintext.

Plaintext	...	a₁ ... a_s	...	0 ... 0	...
Key	...	k₁ ... k_s	...	k₁ ... k_s	...
Ciphertext	...	c₁ ... c_s	...	c₁' ... c_s'	...

where c_i = a_i + k_i, c_i' = 0 + k_i for i = 1, ..., s.

Hence c_i + c_i' = a_i + k_i + k_i = a_i—a plaintext block is revealed—

and k_i = c_i'—the key is revealed.

If the addition of two ciphertext blocks yields a null block, then with some probability the corresponding plaintext blocks consisted of zeroes only. Then also you get the key.

[For more general shift ciphers this method works the same way, only apply the inverse group operation for the single steps.]

Author: Klaus Pommerening, 1999-Oct-18; last change: 2014-Feb-06.