Encryption: Part 3

This time we'll look into simple stream ciphers. In stream ciphers there's a key stream and a data stream and the n-th byte of the data stream is encrypted with the n-th byte of the key stream. A very simple stream cipher might just encrypt the data with the key while looping through the key such that the n-th byte of data is encrypted using the n-th byte of key modulo the length of the data:

func crypt(key []byte, data []byte) {
	for i := 0; i < len(data); i++ {
		data[i] ^= key[i % len(key)]
	}
}

func main() {
	data := []byte{167,87,98,67,88,10,12}
	fmt.Println(data)
	crypt([]byte{1,2,3}, data)
	fmt.Println(data)
	crypt([]byte{1,2,3}, data)
	fmt.Println(data)
}

Stream ciphers are symmetric... meaning the same key is used for encryption and decryption. Also, in this case the function needed to encrypt is the same as needed to decrypt. This encryption algorithm simply encrypts ever byte of data by xoring it with a byte of the key. The key stream here is just endlessly repeating the key. The XOR operation has the property that (a XOR b) XOR b = a. It's a bitwise operation where a XOR 1 = !a and a XOR 0 = a. In other terms, a XOR b is 0 if a == b and 1 if a != b. In the code above we use a 3 byte key which means it's a 24bit key. That sounds week. What if we use a 4096bit (512 bytes) key? Is this any good? No, not really.

Known plaintext attack

If we have a 512 byte key and we have a payload where we know 512 bytes of plaintext we can extract the key because (a XOR b) XOR b = a which means that (key XOR plain) XOR plain = key (xor is commutative). For reasons of readability we'll stick to using 32bit keys in the examples. Let's say we know the first 4 byte of a plaintext:

func main() {
	plain := []byte("GET /api/?secret=44894798")
	fmt.Printf("%x\n", plain)
	key := []byte{0x66,0x77,0x88,0x11}
	
	crypt(key, plain)
	fmt.Printf("%x\n", plain)
	ciphertext := plain // it works in place
	
	// We know the first 4 bytes are "GET "
	knownPlaintext := []byte("GET ")
	extractKey := make([]byte, 4)
	for i := 0; i < 4; i++ {
		extractKey[i] = ciphertext[i] ^ knownPlaintext[i]
	}
	fmt.Printf("Key: %x\n", extractKey)
}

-- OUTPUT --

474554202f6170692f3f7365637265743d3434383934373938
2132dc314916f8784948fb740505ed655b43bc295f43bf285e
Key: 66778811

Attacking the weakness of repeating the key

Since the key stream is just repeating the key over and over again we know that each 4 byte block will encrypt to the same ciphertext:

func main() {
	plain := []byte("AAAAAAAAAAA")
	key := []byte{0x12, 0x51, 0x76, 0xFF}
	
	crypt(key, plain)
	fmt.Printf("%x\n", plain)
}

-- OUTPUT --

531037be531037be531037

We might not know what the exact plaintext is, but we know it has repeated blocks in it. If we know a bit more about what was exactly encrypted this allows us to crack it. If it's for example a black and white image the output might look something like this:

125176ff
135077ff
125077fe
125176ff

This is a 4x4 image. We can easily see that the first line and the last line all have the same pixel value. Since the key is repeated we also know that the first and last pixel of each line is always the same in the first, third and second line. With very large pictures this allows us to see structures of the image in the ciphertext:

125176ff125176ff125176ff125176ff125176ff
125176fe135077ff125176fe135077ff125176ff
125176fe135077ff125176fe135077ff125176ff
125176fe135077fe135077fe135077ff125176ff
125176fe135077fe135077fe135077ff125176ff
125176fe135077ff125176fe135077ff125176ff
125176fe135077ff125176fe135077ff125176ff

Can you see the structure? No, let me highlight some blocks that differ:

125176ff125176ff125176ff125176ff125176ff
125176fe135077ff125176fe135077ff125176ff
125176fe135077ff125176fe135077ff125176ff
125176fe135077fe135077fe135077ff125176ff
125176fe135077fe135077fe135077ff125176ff
125176fe135077ff125176fe135077ff125176ff
125176fe135077ff125176fe135077ff125176ff

Seems like this image contains an uppercase letter 'H'!

Summary

What next?

More stream ciphers!