A Paranoid Encryption Mode

From: John Savard (jsavard_at_ecn.aSBLOKb.caNADA.invalid)
Date: 12/25/03 

Date: Thu, 25 Dec 2003 22:34:23 GMT

Let us suppose, as a recent thread started by Mok-Kong Shen has done,
that two parties share a secret symmetric key-exchange key, and they
wish to exchange secret messages, each of which will begin with a
header field sent in the clear, containing information such as the
date and time of the message and a serial number for the message.

It is intended that no attempt will be made to generate random session
keys with physical randomness, in order to avoid the possibility of
the random session key being used to leak key bits by tampering.

Given that the header field probably has only a very limited number of
possible values, I don't find the idea of simply encrypting the header
field with the key-exchange key to produce the session key appealing,
even though it is not really insecure. I would prefer to do something
more elaborate, involving elements taken from such encryption modes as
OAEP and the various attempts at integrity-aware encryption modes.

Here, then, is my idea of an encryption mode for this case.

It is assumed that a block cipher with a 128-bit block and a 256-bit
key will be used for encryption. The session key and the key exchange
key will both be 256 bits in length.

This mode will not serve to encrypt messages shorter than 640 bits in
length, or five 128-bit blocks.

Encipherment step 1:

The message shall be divided into a first 256 bits, and a remainder. A
256-bit CRC shall be applied to the remainder of the message. The
value produced by that CRC shall be exclusive-ORed with the first 256
bits.

The result of that operation will be termed the session key seed.

Encipherment step 2:

The header to be sent in the clear with the message shall be operated
upon to produce a canonical 256-bit header token. It is not necessary
or intended that a hash function be used for this step.

The session key seed will be encrypted, using the XOR of the
key-exchange key and the header token as the key. (The first 128 bits
will be encrypted in ECB mode, the second 128 bits in CBC mode, using
the output of the ECB operation as the previous plaintext block.)

The result of this encryption shall be sent as the first 256 bits of
the message.

This result will then be XORed with the header token, and the result
of that will be encrypted, using the XOR of the key-exchange key and
the session key seed as the key.

The result of this encryption shall be the session key for encrypting
the remainder of the message.

Encipherment step 3:

The remainder of the message shall be considered to consist of
plaintext blocks P(0), P(1), P(2)... P(N) and any incomplete block at
the end of the message will be enciphered in step 4.

The first 128 bits of the session key seed shall be used to fill a
maximum-period shift register in Galois configuration that is stepped
to the left, except that if they are all zero, the value 0101...01
will be used instead.

The second 128 bits of the session key seed shall be used to fill a
maximum-period shift register in Galois configuration that is stepped
to the right.

These shift registers will be used to generate mask values M(0), M(1),
M(2)... as follows:

a) Step the first shift register.

b) Add the contents of the first shift register to the contents of the
second shift register, using modulo 2^128 addition, with the result
replacing the contents of the second shift register.

c) Step the second shift register. Its contents will be a mask value.

The first time this is done, M(0) is generated.

The remainder of the message will now be enciphered, using the session
key SK, to produce ciphertext blocks as follows:

C(i) = M(i) XOR E( P(i) XOR M(i+1) XOR C(i-1), SK )

where C(-1) will be treated as consisting of all zeroes.

Encipherment step 4:

If there is a portion of the remainder of the message that is left
over after dividing the remainder into blocks P(0) to P(N), then if
that portion is k bits in length, P(N+1) shall be formed from the last
128-k bits of P(N) followed by the left over portion of that message,
and it shall be enciphered as follows:

C(N+1) = M(N+1) XOR E( P(N+1) XOR M(N+2) XOR Q, SK)

where Q is the concatenation of the last 64 bits of P(N-2) and the
first 64 bits of P(N-1).

The last 128-k bits of P(N) will not be included in the message, which
will consist of the header field, the first 256 bits of the message
proper as generated in step 2, P(0) through P(N-1), the first k bits
of P(N), and P(N+1) if a partial block exists or P(0) through P(N) if
a partial block does not exist.

Encipherment step 5:

A 16-bit checksum, using a cyclic redundancy check polynomial, shall
be generated for the encrypted message exclusive of the clear header
field, but including the first 256 bits of the encrypted message and
the encrypted remainder of the message including any partial block at
the end.

The concatenation of the last 112 bits of the message and this 16 bit
checksum will be encrypted using the session key.

All but the last 112 bits of the message will be masked by being XORed
with the last 112 bits of the message repeatedly. The last 112 bits of
the message will not be sent, instead the 128 bit result of the
previous encryption will be sent at the end of the message.

Other details need to be addressed. Steps must be taken to ensure that
the header field is not used to leak key bits, and that key bits are
not hidden invisibly in messages.

A 16-bit checksum is, of course, not enough to prevent existential
forgeries absolutely, but it will serve to allow messages corrupted by
transmission noise to be rejected, and to make it likely that other
types of forgery attempts will be detected.

It is also intended that the header field will at least be sufficient
to prevent the session key from being a hash of the session key seed
that has significantly less than 2^256 possible values.

John Savard
http://home.ecn.ab.ca/~jsavard/index.html

Relevant Pages

  • A Paranoid Encryption Mode
    ... > the random session key being used to leak key bits by tampering. ... I don't find the idea of simply encrypting the header ... > OAEP and the various attempts at integrity-aware encryption modes. ... it possible for an attacker to perform some sort of precomputations ...
    (sci.crypt)
  • Re: encrypt password for webservices
    ... of a Web client and a Web server. ... decrypt them, because the Web server will use a different session key, i.e. ... >> For storage, do not use encryption, use hashing instead. ...
    (microsoft.public.dotnet.security)
  • Re: Hash question ...
    ... header of the file. ... When a user enters an incorrect passphrase, ... if I generate an encryption key with the ... could I safely store the SHA of the passphrase ...
    (sci.crypt)
  • Re: CAPI and RC4: can not decrypt when Final parameter is set to F
    ... Generate a random session key (which is gonna be used for the RC4 ... If i don't do step 3) and use the same HCRYPTKEY handle for both encryption ... the second to do the decryption, ... The client application generates a random key pair (using the .NET ...
    (microsoft.public.platformsdk.security)
  • (newbie) rsa ciphertext and plaintext
    ... in pgp, when the session key is encrypted to the public rsa key, ... (plausible enough to prefer encryption) ... can the ciphertext of the message encrypted to Charlie's key be analyzed to ...
    (sci.crypt)
Quantcast