This is not the complete set of answers for Homework 3. It is only a discussion and demo of the most challenging parts.
A good cipher should produce pseudo-random output in the ciphertext. If the output is (pseudo-)random, then with two similar input plaintexts, then the output ciphertexts should be significantly different in most cases. One way to measure the difference of two ciphertexts is to count the number of bits that differ. On average, half of the bits should be different. This effect, a small change in the input produces a large change in the output, is referred to as the avalanche effect.
There are two inputs we can vary for a cipher: the key or the plaintext. In this example we vary only the key. The aim is to encrypt one key to find a ciphertext, then decrypt with a slightly modified key (but same plaintext) to find a 2nd ciphertext. Then compare the two ciphertexts and count the bits that differ.
When we say on average half of the bits should differ, then in some cases less than half will differ, and in others more than half will differ. So it is useful to try with different variations on the input.
I have written a simple Bash script called avalanche-test that uses OpenSSL to encrypt a plaintext using DES-ECB with several different keys. Each key differs from the original key by just 1 bit. Running the script produces the following:
sgordon@potato:~/css322/examples$ ./avalanche-test
1010000100000110000111011101001010011111101001110000100010100100
1011101100100111101100001010111000111101010101111101001101111010
Bits different from original ciphertext: 34
0011000000011111110011111101000010001000001000000101111000011110
Bits different from original ciphertext: 28
0100000101011000101110100111100111000101101100000011111000001010
Bits different from original ciphertext: 35
1110001101001101101111101010010011011000000110010111101011000001
Bits different from original ciphertext: 33
1100111000011010001001110100100010000010100011111101100100001010
Bits different from original ciphertext: 32
Five keys were used, comparing against an original. In the five output ciphertexts, compared to the original ciphertext, the number of bits that varied range from 28 to 34. The average is 32.4. The expected value is 32 (half of 64 bit block used by DES). Of course to be more statistically accurate, more keys should be tried - for DES there are 56 keys that differ by 1 bit from the original key. But still in this simple test we see characteristics of the avalanche effect in DES.
In (small) difference between modes of operation for block ciphers is how they deal with errors. For example, you encrypt plaintext of multiple blocks and then transmit the ciphertext across a communications network. Its possible in the transmission that there are bit errors. If the received ciphertext differs from the transmitted ciphertext by just 1 bit (i.e. 1 bit error), how does the decryptor handle this? When decrypting, obviously there are going to be at least 1 bit error in the resulting plaintext. But are there going to be more? Preferably not. As we will see, some modes of operation result in a single bit error propagating to other parts of the plaintext which is a disadvantage is some systems.
I have written a Bash script called modes-test that takes a plaintext, encrypts with DES and one of the selected modes of operation, modifies the ciphertext by just 1 bit, then attempts to decrypt the ciphertext. The original plaintext and received plaintext is shown (as well as ciphertext) so we can compare how the different modes of operation behave in the presence of errors. Below is the output of the script:
sgordon@potato:~/css322/examples$ ./modes-test
Mode: des-ecb
Original ciphertext:
0000000: da33 48db a33a 3615 da33 48db a33a 3615 .3H..:6..3H..:6.
0000010: da33 48db a33a 3615 da33 48db a33a 3615 .3H..:6..3H..:6.
0000020: da33 48db a33a 3615 da33 48db a33a 3615 .3H..:6..3H..:6.
0000030: fd62 6a70 2d1b 0e01 .bjp-...
Modified ciphertext
0000000: db33 48db a33a 3615 da33 48db a33a 3615 .3H..:6..3H..:6.
0000010: da33 48db a33a 3615 da33 48db a33a 3615 .3H..:6..3H..:6.
0000020: da33 48db a33a 3615 da33 48db a33a 3615 .3H..:6..3H..:6.
0000030: fd62 6a70 2d1b 0e01 .bjp-...
Original decrypted plaintext
0000000: 7374 6576 656e 676f 7374 6576 656e 676f stevengostevengo
0000010: 7374 6576 656e 676f 7374 6576 656e 676f stevengostevengo
0000020: 7374 6576 656e 676f 7374 6576 656e 676f stevengostevengo
Modified decrypted plaintext
0000000: 59db 764a 2de9 43b6 7374 6576 656e 676f Y.vJ-.C.stevengo
0000010: 7374 6576 656e 676f 7374 6576 656e 676f stevengostevengo
0000020: 7374 6576 656e 676f 7374 6576 656e 676f stevengostevengo
Mode: des-cbc
Original ciphertext:
0000000: da33 48db a33a 3615 36f8 4d79 588c b7fa .3H..:6.6.MyX...
0000010: 1a63 bc0f f385 ce0b 2ed5 cc68 a8a4 90bb .c.........h....
0000020: 5cd8 9574 4432 dc9e a094 d0db 3e10 5265 \..tD2......>.Re
0000030: 9885 a056 0c70 d4eb ...V.p..
Modified ciphertext
0000000: db33 48db a33a 3615 36f8 4d79 588c b7fa .3H..:6.6.MyX...
0000010: 1a63 bc0f f385 ce0b 2ed5 cc68 a8a4 90bb .c.........h....
0000020: 5cd8 9574 4432 dc9e a094 d0db 3e10 5265 \..tD2......>.Re
0000030: 9885 a056 0c70 d4eb ...V.p..
Original decrypted plaintext
0000000: 7374 6576 656e 676f 7374 6576 656e 676f stevengostevengo
0000010: 7374 6576 656e 676f 7374 6576 656e 676f stevengostevengo
0000020: 7374 6576 656e 676f 7374 6576 656e 676f stevengostevengo
Modified decrypted plaintext
0000000: 59db 764a 2de9 43b6 7274 6576 656e 676f Y.vJ-.C.rtevengo
0000010: 7374 6576 656e 676f 7374 6576 656e 676f stevengostevengo
0000020: 7374 6576 656e 676f 7374 6576 656e 676f stevengostevengo
Mode: des-cfb
Original ciphertext:
0000000: 35b9 759c 0aa5 42cc 2f2f 9e5b 172d aad5 5.u...B.//.[.-..
0000010: 9d87 6a85 7d1b 0eca f169 f2cb aeca 5777 ..j.}....i....Ww
0000020: e783 32b8 a6e0 2658 72a5 9f55 5f4b fa6e ..2...&Xr..U_K.n
Modified ciphertext
0000000: 36b9 759c 0aa5 42cc 2f2f 9e5b 172d aad5 6.u...B.//.[.-..
0000010: 9d87 6a85 7d1b 0eca f169 f2cb aeca 5777 ..j.}....i....Ww
0000020: e783 32b8 a6e0 2658 72a5 9f55 5f4b fa6e ..2...&Xr..U_K.n
Original decrypted plaintext
0000000: 7374 6576 656e 676f 7374 6576 656e 676f stevengostevengo
0000010: 7374 6576 656e 676f 7374 6576 656e 676f stevengostevengo
0000020: 7374 6576 656e 676f 7374 6576 656e 676f stevengostevengo
Modified decrypted plaintext
0000000: 7074 6576 656e 676f d55f c262 81ca aadd ptevengo._.b....
0000010: 7374 6576 656e 676f 7374 6576 656e 676f stevengostevengo
0000020: 7374 6576 656e 676f 7374 6576 656e 676f stevengostevengo
Mode: des-ofb
Original ciphertext:
0000000: 35b9 759c 0aa5 42cc ae23 f2f9 628f 3c0c 5.u...B..#..b.<.
0000010: d36a ff9f c887 ff79 13ec 594d 479d dbf9 .j.....y..YMG...
0000020: 1e82 936f a5b2 4f8f c795 309e e8ba 9ba1 ...o..O...0.....
Modified ciphertext
0000000: 36b9 759c 0aa5 42cc ae23 f2f9 628f 3c0c 6.u...B..#..b.<.
0000010: d36a ff9f c887 ff79 13ec 594d 479d dbf9 .j.....y..YMG...
0000020: 1e82 936f a5b2 4f8f c795 309e e8ba 9ba1 ...o..O...0.....
Original decrypted plaintext
0000000: 7374 6576 656e 676f 7374 6576 656e 676f stevengostevengo
0000010: 7374 6576 656e 676f 7374 6576 656e 676f stevengostevengo
0000020: 7374 6576 656e 676f 7374 6576 656e 676f stevengostevengo
Modified decrypted plaintext
0000000: 7074 6576 656e 676f 7374 6576 656e 676f ptevengostevengo
0000010: 7374 6576 656e 676f 7374 6576 656e 676f stevengostevengo
0000020: 7374 6576 656e 676f 7374 6576 656e 676f stevengostevengo
In each case, the error is in the first byte (and hence first block) of the ciphertext. Focus on the Original decrypted plaintext (i.e. the correct plaintext) and the Modified decrypted plaintext (i.e. the received, incorrect plaintext). Both the hexadecimal and ASCII values can be seen (in ASCII a dot . usually means the value cannot be printed).
Using ECB, each block of ciphertext is decrypted independently. So the when there is an error in a ciphertext block, the resulting plaintext from decryption will also be wrong. Because DES exhibits the avalanche effect, just a single bit difference in input ciphertext, produces a significantly different output plaintext. For subsequent blocks of ciphertext, where there are no bit errors, because each block is decrypted independently, the correct plaintext is obtained. So ECB contains the 1-bit error in 1 block.
Using CBC, the first block of ciphertext is decrypted using DES, producing the wrong plaintext block. But recall from how CBC works, in decryption, the first ciphertext block is then XORed with the output of the DES decryption of the second ciphertext block. So although the second ciphertext block has no errors, the XOR with the first ciphertext block introduces errors in the resulting second block of plaintext. Specifically, the one bit that is in error in the first block of ciphertext, produces an error in the same position in the second block of plaintext. So with CBC, a 1-bit error in the first block produces an error in 1 block of plaintext AND a 1-bit error in the second block of plaintext.
Using OFB, a nonce or the previous value of DES output is used as input to DES, then the result is XORed with the ciphertext block. So when the first block of ciphertext is used in the XOR, the one bit in error will produce an error in the corresponding bit of the plaintext. For the next block, only the second block of ciphertext is used in the XOR - it is not dependent on the first (errored block), and hence no errors in the second block of plaintext. So with OFB, a 1-bit error in the first block of ciphertext produces a 1-bit error in the first block of plaintext only.
You can view the scripts I used for the above two demos. They include the OpenSSL commands, as well as others to process and compare the outputs. Also I have the generated input/output files which you can view. All files are available here.
If you want to run the scripts, then you can do so in Linux. Just download, optionally rename them removing the .txt extension (that was just added so they can be viewed easy in the web browser) and execute with bash:
$ bash avalanche-test
Return to: CSS322 Home | Course List | Steven Gordon's Home | SIIT