AES IGE Encryption

Introduction

Infinite Garble Extension (IGE) is a block cipher mode. It has the property that errors are propagated forward indefinitely.

IGE has some leeway in it definitions admitting several possible implementations. This paper documents the way I chose to implement them in OpenSSL, and also provides test vectors.

It also points out some implementation details that may not be obvious from the original papers.

Where is AES IGE used?

Is only used by Telegram. Telegram greatly simplified the exchange by requiring three roundtrips, using RSA, AES-IGE (some weird mode that nobody uses), and Diffie-Hellman, along with a proof of work (the client has to factor a number, probably a DoS protection). Also, they employ some home made function to generate the AES key and IV from nonces generated by the server and the client (server_nonce appears in plaintext during the communication).

IGE Mode

IGE mode uses the following chaining sequence:

\[ y_{i} = f_{k}(x_{i}\oplus y_{i-1})\oplus x_{i-1} \]

where \( f_{k} \) is the underlying block cipher encrypting function with key \( K \), \( i \) runs from 1 to \( n \), and \( n \) is the number of plaintext blocks.

This means that for the first output block, \( y_{i} \), we need two non-existent inputs, \( x_{0} \) and \( y_{0} \). These correspond to the initialization vector (IV) in more traditional modes such as CBC. The implementation specified in the original paper keeps the IV to a single random block by using a second encryption key, \( K’ \) and setting

\[ x_{0} = (0,1)^{l} \]

\[ y_{0} = f_{K’}(x_{0}) \]

where \( l \) is the block size, in bits. I decided to use a more general implementation where both \( x_{0} \) and \( y_{0} \) are provided by the user, rather than using a second key to derive \( y_{0} \).The implementation is otherwise as described in the original paper.

This is for three reasons, firstly it is more efficient if both blocks are chosen randomly, and secondly because the original implementation can be expressed in terms of OpenSSL’s implementation but the opposite is not the case.

The third reason is to do with the way block cipher modes are often implemented because it is possible to encrypt each block as it becomes available, rather than waiting until the entire plaintext is available, many implementations (including OpenSSL’s) make it possible to encrypt partial plaintexts. The necessary chaining information is commonly stored in the memory which was used for the IV. This makes perfect sense, because on subsequent calls to the encryption (or decryption) function, the output is exactly as if the chaining information had, in fact, been provided as an IV.

The implementation as described maintains this possibility, which the original implementation does not.

Note, however, that this makes the IV two blocks long, instead of the usual one block. OpenSSL uses the convention that the first block of the IV is \( x_{0} \) and the second block is \( y_{0} \). The plaintext is XORed, before encryption, with the previous ciphertext; after going through the block cipher, it is XORed with the previous plaintext:

PHP Implementation

Java Implementation

http://goobbe.com/questions/7170339/java-aes-256-decrypt-with-ige

Test Vectors

AES IGE Mode Test Vector 1

Key

00010203 04050607 08090A0B 0C0D0E0F

Initialisation Vector

00010203 04050607 08090A0B 0C0D0E0F
10111213 14151617 18191A1B 1C1D1E1F

Plaintext

00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000

Ciphertext

1A8519A6 557BE652 E9DA8E43 DA4EF445
3CF456B4 CA488AA3 83C79C98 B34797CB

AES IGE Mode Test Vector 2

Key

54686973 20697320 616E2069 6D706C65

Initialisation Vector

6D656E74 6174696F 6E206F66 20494745
206D6F64 6520666F 72204F70 656E5353

Plaintext

99706487 A1CDE613 BC6DE0B6 F24B1C7A
A448C8B9 C3403E34 67A8CAD8 9340F53B

Ciphertext

4C2E204C 65742773 20686F70 65204265
6E20676F 74206974 20726967 6874210A

References

[1] B. Laurie, “OpenSSL’s implementation of Infinite Garble Extension”, 2006 [2] Lars R. Knudsen, “Block Cipher Chaining Modes of Operation”

Updated: