The MALICIOUS framework: Tweakable Block Ciphers

The MALICIOUS framework: Tweakable Block Ciphers

Adding a backdoor has been an attack method of choice for Eve. Overall the opportunity to insert a backdoor into symmetric-key methods has not been successful. That changed when, in 2020, Peyrin et al [1] proposed “ The MALICIOUS Framework: Embedding Backdoors into Tweakable Block Ciphers.”

Overall they define that the framework has a backdoor that cannot be detected, and is hidden with the design of the cipher. If Eve creates the cipher, she can recover Bob’s secret key, and where Bob cannot detect this. The framework proposes the LowMC-M construction, and based on the LowMC cipher, but allowing an embedded backdoor. Overall we create a tweakable bock cipher (TBC) that uses both a key and tweak to select a permutation. Let’s look at an example of a tweak cipher: XTS.

A Tweak

Before we start, it is important to know that AES encryption deals with 128-bit (16 bytes) encryption blocks, whereas disks typically deal with 512-byte segments. We must thus fit 32 AES blocks into our disk segments (Figure 1). Sometimes we will have empty blocks, so we must fill these with “ciphertext stealing” blocks.

With non-full disk encryption, we typically create an AES key and encrypt the file. The encryption key is typically generated from a passphrase and uses a key derivation function (KDF). We can also create a key pair (a public key and a private key), and then encrypt the key with our public key, and then decrypt it with our private key. With this we are thus encrypting at a file level, and which will be fairly inefficient, as we need to read the whole file in at a time. With full-disk encryption, we typically read from sectors on the disk, and in a random manner.

The smallest addressable element of a disk is a block — and which is typically around 512 bytes — and these are arranged into sectors:

Disk /dev/sda: 640.1 GB, 640135028736 bytes
255 heads, 63 sectors/track, 77825 cylinders, total 1250263728 sectors
Units = sectors of 1  512 = 512 bytes
Sector size (logical/physical): 512 bytes / 512 bytes
I/O size (minimum/optimal): 512 bytes / 512 bytes
Disk identifier: 0x00064a1a

   Device Boot      Start         End      Blocks   Id  System
/dev/sda1              63     2040254     1020096   83  Linux
/dev/sda2         2040255    22523129    10241437+  82  Linux swap / Solaris
/dev/sda4        22523191  1250258624   613867717    5  Extended

But we have a problem here if we are to use full-disk encryption, as most methods — apart from Electronic Code Book (ECB) — have an Initialisation Vector (IV) and where the blocks (typically 128 bits) are then chained together, and where the output of one block feeds into another one. The IV makes sure that for the same input plaintext, we will have a different ciphertext.

Within a disk system, this is a problem, as we need to be able to randomly access sectors, without having to read all the other sectors. XTS (XEX-based tweaked-codebook mode with ciphertext stealing) is a fairly common method which overcomes these problems. For this it uses a “tweak”, and where we take an encryption key, and encrypt the sector number, and use this to X-OR the data within the sector.

Two of the most common modes of block encryption are Electronic Code Book (EBC) and Cipher Block Chaining (CBC). With ECB we basically take blocks of 128 bits, and then cipher these:

Unfortunately, the same input in the blocks will lead to the same cipher output, and leaves us open to a range of cipher attacks. With CBC the blocks are chained together, and where the output of one block feeds into another one. The IV makes sure that for the same input plaintext, we will have a different ciphertext. We initially take an IV and then EX-OR it with the first plaintext block, and then encrypt this. This block is then EX-OR’ed with the next plain text block, and so it continues:

We first define two keys (K1 and K2). If we use 128-bit AES, then we generate two keys which are 128 bits long. The “data” AES key is K1 and the “tweak” AES key is K2. If we use 128-bit keys.

Next, we define an input block (P) and a sector number (i) and a block number (j), and create a tweak (X):

Note, ⊗ is a multiplication (within a finite field of 127). The ciphertext (C) for each block is then:

To decrypt, we do the opposite:

The plaintext (P) for each block is then:

In this way, we just need the encryption key, and the sector number, in order to encrypt and decrypt. The tweak acts as an IV. This process is illustrated by Figure 4.

Overall a sector of a size of 512 bytes will store 32, 16-byte AES-blocks (a block in AES is 128 bits long). In this way, for a single sector, we call the encrypt/decrypt method 32 times using the same ii value, but different j values (0 to 31).

Most fully encrypted disks now use the AES-XTS block cipher mode, and which is defined in IEEE Standard 1619. It is now implemented in many USB encrypted devices, and with Microsoft Bitlocker for Windows 10, TrueCrypt, VeraCrypt, OpenSSL, and Mac OSX FileVault.

The MALICIOUS Framework

An outline of the MALICIOUS framework is defined in Figure 5 and where we have a tweakable block cipher with an n-bit blocksize, and a k-bit key. A tweakable bock cipher uses both a key (K) and tweak (T) to select a permutation.

The backdoor is added due to related-tweak differential characters, and which can be used to recover the symmetric key. In a normal tweakable block cipher , we have users (Bob and Alice) who use the same key, and Eve who tries to break the cipher. With a backdoor, we also have a designer, who add a backdoor into the cipher method. The algorithm to integrate the backdoor is:

In this case we use XOF (EXtendable Output Function) as used with SHA-3. With an XOF we break away from its fixed-length output of ciphers and can produce an almost infinite set of outputs. This could be to take a single byte and produce an output of a billion bytes, or even take a billion bytes of input and produce a single byte output.

The MALICIOUS framework is implemented using the LowMC cipher family, and which is outlined here:

and which has been modified to produce a tweakable cipher: LowMC-M. Overall a TweakAddition transformation is added to each round. The rounds are then: TweakAddition(i); KeyAddition(i); ConstantAddition(i) ; LinearLayer(i); and Sbox. The code for LowMC-M is here:

And here is an outline:

References

[1] Peyrin, T., & Wang, H. (2020, August). The MALICIOUS Framework: Embedding Backdoors into Tweakable Block Ciphers. In Annual International Cryptology Conference (pp. 249–278). Springer, Cham [here].