Block mode of operation: why ECB is bad

In an earlier post I discussed how AES works on small 128 bit blocks of plaintext. Your usual data will generally be larger than that. First, as a rule, you will have to fill up your plaintext such that its size is a multiple of the blocksize. This is known as padding and there are several ways to do that. However we will reserve the details for a later topic. If, by chance, your data’s length happens to be a multiple of the blocksize, you need to do nothing.  Lets assume now that your plaintext has the required length property.

In a first naive approach one might be tempted to split the plaintext in portions of the blocksize and encrypt every single block with your key. DO NOT DO THAT! This is known as the electronic codebook ECB and we are going to see just how flawed it is. The basic problem is that identical blocks of plaintext are mapped to identical blocks of ciphertext. An adversary can gain much insight into the structure of your message just by looking at the encrypted stuff. And I mean literally by looking.

For the sake of the argument let’s resurrect the earlier code for AES in Mathematica and build on top of that. Then we implement the ECB by

NeedsPadding[s_String, blocksize_Integer] := (Head[s] == String) && ! (Divisible[StringLength[s], blocksize]);
NeedsPadding128[s_String] := NeedsPadding[s, 16]
NeedsNoPadding[s_String, blocksize_Integer] := (Head[s] == String) && (Divisible[StringLength[s], blocksize]);
NeedsNoPadding128[s_String] := NeedsNoPadding[s, 16]

Encrypt["ECB"][m_?NeedsNoPadding128, k_?Is256Key] := StringJoin@( aes[#, key] & /@ (Array[StringTake[m, {1 + (# - 1) 16, # 16}] &, StringLength[m]/16]))

Decrypt["ECB"][m_?NeedsNoPadding128, k_?Is256Key] := StringJoin@(daes[#, key] & /@ (Array[StringTake[m, {1 + (# - 1) 16, # 16}] &, StringLength[m]/16]))

That’s it. So easy. But that’s the only thing good about it.

We also implement a slightly better (though not the best) mode, the cipher block chaining CBC. Here the first block is XORed with an initialization vector (of course it has to have the same length as a block) and then encrypted by the usual block cipher. The result is the the first block of the encrypted message. This encrypted block is then XORed with the second plaintext block and after that encrypted. The result is accepted as the second block of ciphertext. This in turn is fed to the third block by XORing etc. Got the idea? Every encrypted block depends on the one before it. The initialization vector has to be chosen at random, but does not necessarily have to be kept secret. This avoids semantic analyses of the ciphertext. “Semantic analyses” is fancy talk for finding regularities or patterns by looking at it. I invite you to think about further advantages of CBC over ECB.
The implementation in Mathematica can be achieved in a rather short way:

StringXor[s_String,t_String] := FromCharacterCode@BitXor[ToCharacterCode@s,ToCharacterCode@t]

Encrypt["CBC"][m_?NeedsNoPadding128, k_?Is256Key, iv_?Is128Block] := Module [{tokens, ctokens, in, CBCAESStep},
  tokens = Array[StringTake[m, {1 + (# - 1) 16, # 16}] &, StringLength[m]/16];
  CBCAESStep[ve_, pl_] := aes[StringXor[ve, pl], k];
  in = CBCAESStep[iv, tokens[[1]]];
  ctokens = FoldList[CBCAESStep, in, tokens[[2 ;;]]];
  StringJoin@ctokens
]

Decrypt["CBC"][m_?NeedsNoPadding128, k_?Is256Key, iv_?Is128Block] := Module [{ctokens, stage1, stage2, stage3, tokens, in, CBCAESStep},
  ctokens = Array[StringTake[m, {1 + (# - 1) 16, # 16}] &, StringLength[m]/16];
  stage1 = daes[#, k] & /@ ctokens;
  stage2 = Prepend[ctokens[[1 ;;]], iv];
  stage3 = Array[StringXor[stage1[[#]], stage2[[#]]] &, StringLength[m]/16];
  StringJoin@stage3
]

Note that here and above the decryption is only implemented for the sake of completeness. We won’t need it.

Now let’s make some action. We will encrypt a picture of the sexiest man alive:
gooby
We load it and rasterize it as a 256 x 256 bitmap image. Then we convert it into a sequence of 196608 numbers. Why 196608? Simply  256 x 256 x 3! Each of the (ordered) 256 x 256 pixels carries a RGB color of 3 bytes. Mathematica provides some powerful functions to achieve that in only a couple of lines

pic = Import["/pathto/gooby1.png"];
b = 256;
Rasterize[pic, RasterSize -> {b, b}, ImageSize -> {b, b}]
Pic = ImageData[%, "Byte"];
Flatten[(Pic[[#]])] & /@ (Array[# &, b]);
mes = FromCharacterCode@Flatten@Pic;

RestorePic[enc_] := Graphics[Raster[(Reverse@(Partition[Partition[ToCharacterCode@enc, 3], b])), {{0, 0}, {b, b}}, {0, 255}, ColorFunction -> RGBColor], ImageSize -> {b, b}, PlotRange -> {{0, b}, {0, b}}];

We will need RestorePic later. It can produce a 256 x 256 picture out of an arbitrary string of 196608 ASCII characters.

First look at what happens when we do CBC (with a stupid initialization vector, I admit it)

inv = "1111112222333444";
e1 = Encrypt["CBC"][mes, key, inv];
RestorePic[e1]

One gets

cbcgooby

Looks random, right? Could be anything, right? That’s what encryption is all about. I am not saying that what we did here is bulletproof (it is probably not), but it doesn’t look too bad.

But now look what happens when we apply ECB to the picture,

e2 = Encrypt["ECB"][mes, key];
RestorePic[e2]

ecbgooby

Wtf? That’s not encrypted! It scrambled things a little where different colors meet. That is the effect of AES inside a block. But otherwise the structure of the picture is preserved. That’s what I meant by “looking at the ciphertext”.  An adversary doesn’t even need any fancy schmancy mathematics to tell what the picture is about! If you were to send a nude picture of yourself to your significant other (and you decide to encrypt it to protect your privacy), would your choice of block mode be ECB?

Now a different question: You have seen the ECB and you have an educated guess about what the picture is. Maybe you have come to the conclusion that in the upper left corner there are a bunch of white pixels. You therefore guess that the first 128 bits of the original image are all equal to 1. And you know the corresponding ciphertext. Is it possible to somehow calculate the key from that? In the case of AES the answer to that is “probably no”. Such questions go under the name of “known plaintext attacks”.  To the present day there is no known (or published) attack of this kind against AES. So even if I were stupid enough to use AES in ECB mode, some details of the picture are maybe unrecoverable by adversaries. So I’ve got that goin for me, which is nice.

Lesson learned: if you use block ciphers in ECB mode you’re gonna have a bad time. Enough with the memes.
G’night, folks.

Advertisements

About goobypl5

pizza baker, autodidact, particle physicist
This entry was posted in Encryption, Mathematica and tagged , , , , . Bookmark the permalink.

3 Responses to Block mode of operation: why ECB is bad

  1. Pingback: AES in Mathematica | randomgooby

  2. Pingback: The RC4 stream cipher | randomgooby

  3. Pingback: How to get a job with 250 lines of code | randomgooby

Share your thoughts

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s