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
|
|
Initialisation Vector
|
|
Plaintext
|
|
Ciphertext
|
|
AES IGE Mode Test Vector 2
Key
|
|
Initialisation Vector
|
|
Plaintext
|
|
Ciphertext
|
|
References
[1] B. Laurie, “OpenSSL’s implementation of Infinite Garble Extension”, 2006
[2] Lars R. Knudsen, “Block Cipher Chaining Modes of Operation”