[Next] [Up] [Previous] [Index]

A Note on the Importance of Galois Fields

In the descriptions of the block ciphers Rijndael and Twofish, we have encountered the operation of multiplication in a Galois Field.

Looking at other cipher designs, and their effective use of more familiar operations, such as addition, exclusive-OR, conventional and modular multiplication, and table lookup in S-boxes, one might be forgiven for wondering if the use of such exotic and advanced mathematics is really necessary in a symmetric-key cipher.

However, in attempting to answer a question about the simplest way to fully correct a flaw in a particular type of stream cipher, one can see that Galois fields do have an important property which is useful in cryptography.

Some stream ciphers operate merely by generating a pseudo-random output, treated as a keystream, which is merely XORed with the plaintext. Others behave more like rotor machines, and instead of simply displacing the plaintext a varying amount through a fixed alphabet, provide a substitution which is different in arrangement for each symbol enciphered.

In the former case, if one knows the exact plaintext of a message being sent, one could, by inverting the same bits of the ciphertext as one wishes to invert of the plaintext, alter a message in any way one likes without knowing any part of the keystream.

This weakness, known as vulnerability to the "bit-flipping" attack, can, of course, be dealt with by using some form of authentication method.

However, I still found it interesting to investigate the question of what would be the minimal enhancement to the basic PRNG (pseudorandom number generator) with XOR stream cipher to obtain a varying alphabet.

More specifically, I sought a combiner (which could be used alone as a variation on the one-time-pad) with the following properties:

The addition table for a simple cipher with these properties, where N=3, is as follows:

      Key
    | A B C  D E F
  ----------------
P 0 | 0 1 2  0 1 2
L 1 | 1 2 0  2 0 1
N 2 | 2 0 1  1 2 0
      Cipher

To scramble plaintext in the fashion of a one-time-pad, it is sufficient to use either the keystream symbols (A,B,C) or (D,E,F) with equal probability. Because the vertical columns in the ciphertext run backwards in the second half of the table, for a given plaintext-ciphertext pair, if the two keystream symbols that could have caused it in the two halves of the six possibilities are equally probable, changing the ciphertext is equally likely to give either of the two different plaintexts.

Note that what is happening here is that the one-time-pad effect is produced by adding 0, 1, or 2 to the plaintext to produce the cipher output, while the resistance to the equivalent of a bit-flipping attack is produced by previously multiplying the plaintext either by 1 or -1 (equivalent to 2 in modulo-3 arithmetic).

This can also be done for binary data; the minimal way to do so would be to take two bits at a time, as in the following table.

       Key
       A  B  C  D   E  F  G  H   I  J  K  L
  ------------------------------------------
P 00 | 00 01 10 11  00 01 10 11  00 01 10 11
l 01 | 01 00 11 10  10 11 00 01  11 10 01 00
a 10 | 10 11 00 01  11 10 01 00  01 00 11 10
i 11 | 11 10 01 00  01 00 11 10  10 11 00 01
n      Cipher

In the first four columns of the table, using one of keystream symbols {A,B,C,D} is equivalent to performing an XOR of the plaintext symbol with the respective element of {00, 01, 10, 11}.

It can be verified by inspection that this table does have the property I am looking for.

Note that keystream symbols {E,F,G,H} and {I,J,K,L} also perform XORs with the plaintext symbols, after a substitution is performed on them, the substitutions being the ones in the columns labelled E and I.

The following table:

        A  E  I
     00 01 10 11
----------------
00 | 00 00 00 00
01 | 00 01 10 11
10 | 00 10 11 01
11 | 00 11 01 10

shows the three substitutions in use, along with an extra column to make the table symmetric.

Since any operation involving 00 produces 00, this resembles a multiplication table.

And, indeed, it is the multiplication table for the representation of GF(2^2) with modular polynomial x^2+x+1.

So, just as with base 3, we obtained the desired property by performing first a multiplication and an addition, here we performed a Galois Field multiplication, followed by an XOR, which is the operation corresponding to addition in such a Galois Field. (Doing the XOR first and the multiplication afterwards, of course, would also work.)

Is this a general method for obtaining a substitution which has this desired property? Yes; this is a direct consequence of the distributive property. Multiplication over the Galois Field, and XOR, behave like multiplication and addition do in ordinary arithmetic, and thus they will be denoted by * and + respectively below.

Given that (p*B)+A=q and (p*B')+A'=q, if B is not equal to B', then for q' not equal to q, we wish to prove that (p'*B)+A=q' and (p''*B')+A'=q' implies p' cannot equal p''.

This follows from the distributive property, and a few other basic properties of a field. If p' did equal p'', but not p, then for p' not equal to p, the difference between (p'*B) and (p'*B') cannot equal the difference between (p*B) and (p*B'), since the one is p'*(B+B') and the other is p*(B+B'), and B is not equal to B'. (Here, + is equivalent to -, because XOR performs both roles.) However, the difference between A and A' hasn't changed, and so a contradiction results.

Thus, when two operations behave like addition and multiplication, they complement each other as well as two operations can, and thus using them together provides a result which, in the particular respect examined here, resembles the result of having a completely indeterminate permutation.

And to obtain two such operations for symbols that are made up of two or more bits each, the only choice is Galois Field multiplication along with XOR. If, instead, a set of symbols with a prime number of elements is used, one can use ordinary modular multiplication and addition. Thus, this property can be approximated by using, for example, addition modulo 2^n and multiplication modulo (2^n)+1, with the advantage that the inputs to both steps can have all 2^n possible values.

This technique is illustrated here as giving the benefit of preventing anything resembling 'bit-flipping' in a stream cipher, including the one-time-pad. But it is also useful in the design of block ciphers, where it provides what is referred to as decorrelation, and thus this point is also referred to in the section on the Decorrelated Fast Cipher.

Twofish and Rijndael use two different representations of GF(2^8). For 5-level-code characters, as used in telecipher devices, x^5+x^2+1 is a suitable modular polynomial.

Since GF(2^5) multiplication has the distributive property with respect to XOR, the following abbreviated multiplication table is sufficient:

      | 00001 00010 00100 01000 10000
-------------------------------------
00001 | 00001 00010 00100 01000 10000
00010 | 00010 00100 01000 10000 00101
00100 | 00100 01000 10000 00101 01010
01000 | 01000 10000 00101 01010 10100
10000 | 10000 00101 01010 10100 01101 

In the age before inexpensive computers, and ciphers like DES, and hash functions like MD5, this is a technique, as it involves math that was known quite a long time ago, and requires circuitry of moderate complexity even if discrete components are used, which could have been used to protect secure teleprinter links years ago, by using one one-time-tape in the conventional manner, but also using a second one-time-tape, not including the all-zero code, for a multiplication operation. (Actually, of course, it would make more sense to use a special 10-channel one-time-tape.) Yes, it would not have been as direct a solution as a hash function. But it has the important advantage that it would not have the failure mode of a human in the link ignoring a bad checksum and accepting a fraudulent message. Therefore, such a technique does, I believe, serve a legitimate purpose, even when it still needs to be recognized that actual authentication steps are also necessary.

It does not appear that this was used for the Moscow-Washington hot line, but it is not impossible that it was at least considered.

Also, perhaps such a technique might have something to do with the Soviet cipher device described as applying a 15-channel one-time-tape to 5-level-code characters.


[Next] [Up] [Previous] [Index]

Next
Chapter Start
Skip to Next Chapter
Table of Contents
Home Page