Information leakage analysis in block ciphers – Part 2

Cryptology attacks on CBC mode of operation

In the first part we talked about block ciphers and their mode of operation. In this part we want to explain more about how an adversary will misuse this mode of operation and perform some successful attacks on cryptographic system, like decrypting a cipher-text without knowing the cryptographic keys.

As previously mentioned, in CBC each plaintext block is XOR-ed with the previous encrypted block before being encrypted. You may be wondering about what happens to the first block: it gets XOR-ed with a phony block which called IV (Initialization Vector). The sender and receiver can agree on a predetermined IV before starting encryption and decryption phases. But for convenience there isn’t any need to encipher the IV even though in some implementations the IV is enciphered for further security.

Before we dig into this topic you might be wondering on why we have to use a mode of operation.

The simple answer is because block ciphers can be used only on blocks of predetermined size. E.g. in AES plaintext blocks are 128 bits and in DES plaintext blocks are 64 bits in length. But in real world applications, the text to be enciphered is of variable size and normally much larger than 56, 128 bits. So there must be a way/procedure for safely processing blocks of different lengths and also to securely encrypt the data, these procedures are called operation mode.

fig1

As in CBC mode of operation each ciphertext block chained to produce next ciphertext block, so two equal plaintext blocks from the same message are enciphered into two different ciphertext blocks. In the form of mathematical notation, encryption and decryption phases, as seen previously, are performed as below.

fig2

⊕ = Notation for eXclusive OR

P = Plaintext

C = Ciphertext

IV = Initialization Vector (might be construed as C 0 )

Ek = Encryption with the key k

Dk = Decrypt with the key k

P1 = Plaintext blocks to-1

P2 = Plaintext blocks to-2

Pn = Plaintext block n

C1 = Ciphertext block 1

C2 = Ciphertext block 2

Cn = Ciphertext block n

In order to visualize the encryption and decryption process take a look at the process depicted below:

fig3

  • What exactly is IV (Initialization Vector)? If any encryption/decryption involves previous encrypted block, what about the first block? Because there isn’t any C before the first block we can select a random and unpredictable IV, which can be transferred without concealing it. Actually the IV could also be considered part of final ciphertext that is transferred through the network.
  • Padding: In block ciphers, ciphertext and plaintext should be in chunks the size of a block. Because data should be entered in blocks of the same size, if the plain-text block is shorter than the block size, then remaining parts must be filled up with padding bytes, based on the standard in use as padding. Popular padding schemes are PKCS#7, PKCS#11 which are used in almost every cryptographic application. Each of these standards have its rules for filling the rest of the block with proper bit orders. E.g in PKCS#7 if we assume N is number of free blocks need to be fulfilled with some bytes to be fixed size, this standard requires to fill these cells with N bytes with 0xN byte values. For example if we need 5 bytes to fill free space of block the rest of them will be filled with 5 ‘0x5 0x5 0x5 0x5 0x5’. Some examples of right padding are shown below:
    (block-size considered to be 8 bytes.)

 

 

A

B

C

D

4

4

4

4

0x41

0x42

0x43

0x44

0x04

0x04

0x04

0x04

A

B

C

D

E

3

3

3

0x41

0x42

0x43

0x44

0x45

0x03

0x03

0x03

A

B

C

D

E

F

2

2

0x41

0x42

0x43

0x44

0x45

0x46

0x02

0x02

A

B

C

D

E

F

G

1

0x41

0x42

0x43

0x44

0x45

0x46

0x47

0x01

 

But there’s an exception even for a whole full block, why? In PKCS standards the padding must be added to all data, even when such data is the exact size of a block. Consider one 8-bytes block of data in the form of “ABCDEFG1”. The data size is the block size; so if we don’t append dummy padding bytes to the end of this plaintext block the last byte will be removed. After the decryption and after removing the padding bytes, our plaintext will be in the form of “ABCDEFG” that is not what we’ve sent.

 

A

B

C

D

E

F

G

H

8

8

8

8

8

8

8

8

0x41

0x42

0x43

0x44

0x45

0x46

0x47

0x48

0x08

0x08

0x08

0x08

0x08

0x08

0x08

0x08

 

An example if we don’t use any padding rule:

 

A

B

C

D

E

F

G

1

8

8

8

8

8

8

8

8

0x41

0x42

0x43

0x44

0x45

0x46

0x47

0x01

0x08

0x08

0x08

0x08

0x08

0x08

0x08

0x08

What if we don’t use padding rule in this example? Last byte will be considered as pad; not real data.

A

B

C

D

E

F

G

1

0x41

0x42

0x43

0x44

0x45

0x46

0x47

0x01

 

  • Oracle

An oracle is a black-box system which can solve a decision problem for us and respond to us about the result of computation. It’s black-box because we don’t know anything about how it computes and solves the problem. In our case a padding oracle is a black-box cryptographic system which takes an encrypted ciphertext from the user and then decrypts it on its side, then checks for padding; if it’s correct then we’ll get something like a “padding was correct” message or else we get “padding is invalid”.

A padding oracle attack works by distinguishing between a valid and an invalid situation. Thinks about a web server. How you can distinguish between true or false?

May be by looking at changes in HTTP error messages in header of every HTTP response, or may be by stack tracinge errors like debug logs generated by programming languages and looking up for messages like “Invalid padding”,…

What is exactly a wrong padding?

  • Invalid padding

Detecting whether the padding bytes are valid or invalid, begins by looking at the last byte of last block of decrypted message. The padding is checked during the last phase, after decryption.

In the examples below the block size is 8 bytes.

  • This is an invalid padding because when block-size is 8 bytes the padding values are between 1 to 8, not more.

A

B

C

D

E

F

G

25

0x41

0x42

0x43

0x44

0x45

0x46

0x47

0x19

  • Invalid padding because the last byte of final block is 0x02 and so both padding bytes should be 0x02.

A

B

C

D

E

F

25

2

0x41

0x42

0x43

0x44

0x45

0x46

0x19

0x02

  • Invalid padding because the value of the last byte of final block is 0x08 and so the previous blocks should all be 0x08.

A

B

C

D

E

8

8

8

0x41

0x42

0x43

0x44

0x45

0x08

0x08

0x08

  • Invalid padding because again it’s out of range.

A

B

C

D

E

3

3

0

0x41

0x42

0x43

0x44

0x45

0x03

0x03

0x00

  • Valid padding!

A

B

C

D

E

3

3

3

0x41

0x42

0x43

0x44

0x45

0x03

0x03

0x03

Mohsen Ahmadi

BIBLIOGRAPHY [ Cryptography Engineering: Design Principles and Practical Application]

REFERENCE TO IMAGES [ Some slides of professor D. Boneh for schemes]