October 18, 2021 | By devevon

Modern Cryptography

Modern cryptography is one of the most important aspect of computer and communications security. It is based on mainly mathematics concepts like number theory, computational-complexity theory and probability.

Unlike classical cryptography which manipulates traditional characters, modern cryptography operates on binary bit-string. It could also be proven, under given assumption, to be computationally secure.

The primary goals that modern cryptography is trying to achieve are:

1. Confidentiality:
   • Also known as privacy or secrecy. It means that even if an adversary manages to eavesdrop on one’s message, it could not know the meaning of the message.
2. Integrity:
   • Confirms that data transmitted is not modified by an unauthorized entity. All modified data should be detected.
3. Authentication:
   • Provides the identification of the parties that one is communicating with.
   • i.e. A cannot pretend to be B when talking or sending data to C.

There are 2 main types of cryptographic methods that are adopted today:

1. Symmetric (Private Key)
2. Asymmetric (Public Key)

Some key terms to know:

• Plaintext: message that needs to be encrypted.
• Ciphertext: encrypted plaintext. If encryption is done properly, it reveals no information about the plaintext.
• Key: a randomly generated string used in encryption and decryption

All cryptography algorithms can be broken down into 3 parts:

1. Key generation, KG () (takes in no parameter): a function outputs a randomly chosen key.
2. Encryption, or Enc(Msg, Key): this function takes in a key and a plaintext message, encrypts the plaintext based on the key, and outputs the resultant ciphertext, C
3. Decryption, or Dec(C, Key): this function takes in a key and a ciphertext, decrypts the ciphertext based on the key, and outputs the resultant plaintext, M

For any algorithm to work as intended, if the key is correct, the following must hold:

i.e. I must get back to the same message if my key(s) is(are) correct.

Section 1: Symmetric Encryption

Symmetric encryption is a type of encryption where only one shared secret key is used to both encrypt and decrypt data (bit-string).

Topic 1: One Time Pad

Section 1: Introducing the Encryption Algorithm

Topic Description/Background Info

One Time Pad works by taking a key that is as long as the text you want to encrypt and then performing the XOR operation to get the encrypted text. The same key used to encrypt the text is also used in decrypting, by performing the XOR operation with the encrypted text and the key.

Xor property:

For one time pad, the 3 parts:

• KG(): it will output a randomly generated bit-string that has the same length as the plaintext
• Enc(M, K):
  • Message M and Key K must have the same length.
  • It will output a ciphertext C, where

• Dec(C, K):
  • Ciphertext C and Key K must have the same length
  • It will output a plaintext M, where

To summarize and XORing is a cheap operation so it is easy to encrypt and decrypt messages which is an advantage of the One Time Pad.

Note: OTP is proven mathematically to satisfy perfect secrecy

To understand the following extra readings, some understanding in statistics is needed

• Perfect secrecy: https://www.cs.miami.edu/home/burt/learning/Csc609.011/Perfect/#:~:text=A%20cryptosystem%20has%20perfect%20secrecy,one%20key%20that%20connects%20them.
• Proof that OTP satisfies perfect secrecy: http://math.umd.edu/~lcw/OneTimePad.pdf

OTP Challenge 1: Proper Encryption and Decryption (Stage 1 and Stage 2)

Section 2: Why is One Time Pad not used in the real world.

Background Info

The main disadvantage of this encryption algorithm is that it requires a key of the same length as the message to be encrypted. Every time when a message is sent, a key of the same length must be shared as well. (Why not reuse the same key?).

Suppose we have a message of length 2048, we need to send securely a key of length 2048 together with the encrypted message.

In other word, if we are sending a file of size 1GB, in total, we will need to send 2GB worth of load.

OTP Challenge 2: Attack OTP when the same key is used.

Topic 2: Block Ciphers

Section 1: Introducing the Encryption Algorithm

Background Info:

Block Cipher is another symmetric encryption algorithm, it works by take a block of the plaintext and then using a key to pick a permutation of the possible outputs.

For example, for a 3-bits block and 2-bits key

Plaintext	Cipher (Key = 00)	Cipher (Key = 01)	Cipher (Key = 10)	Cipher (Key = 11)
000	100	110	010	010
001	011	001	011	100
010	111	000	101	110
011	101	101	000	011
100	000	010	100	101
101	010	100	111	001
110	110	111	001	000
111	001	011	110	111

Suppose our key = 01, message = 101, then the ciphertext = 100.

Note: not all possible permutations are used here.

For a block that has N-bit inputs there are 2^N! possible permutations and for a key that has k-bits there are 2^k possible keys. Each key will map to a unique permutation. It is very likely that not every permutation will be used.

One of the nice things about Block Cipher is that it is extremely hard to break that is it is very expensive to try since there is no known efficient algorithm that can break Block Cipher without having to brute-force it.

In real life where key size is as long as 256 bits, there will not be a key-plaintext-ciphertext table. Instead, an interesting pseudo-random permutation algorithm will be used to make the encryption algorithm efficient.

e.g.

AES: http://etutorials.org/Networking/802.11+security.+wi-fi+protected+access+and+802.11i/Appendixes/Appendix+A.+Overview+of+the+AES+Block+Cipher/Steps+in+the+AES+Encryption+Process/

DES: https://www.geeksforgeeks.org/data-encryption-standard-des-set-1/

Block Cipher Challenge 1: Based on a key table, encrypt and decrypt

Section 2: Attacking the Algorithm with brute force

Background Info:

Currently there is not a known efficient way to break a block cipher other than trying out all possible keys.

Block Cipher Challenge 2: breaking using brute force

Section 3: 2DES (Meet in the middle attack)

Background Info

As computer powers becoming stronger, DES that uses 56-bit key could be broken within a few hours.

A possible way to make it harder to break, apart from using a longer key or changing to AES, is using 3 DES.

3 DES (needs 2 56-bits keys)

• To encrypt:
  • 1^st Encrypt with DES the plaintext using Key1 to get C1.
  • 2^nd Decrypt C1 with Key2 to get C2.
  • 3^rd Encrypt C2 with Key1 to get the final ciphertext.
• To decrypt:
  • 1^st Decrypt the ciphertext with Key1 to get C2.
  • 2^nd Encrypt C2 with Key2 to get C1.
  • 3^rd Decrypt C1 with Key1 to get the plaintext.

2 DES (?)

Proposed encryption algorithm:

• 1^st Encrypt the plaintext with Key1 to get C1.
• 2^nd Encrypt C1 with Key2 to get the final ciphertext.

Challenge: Attacking 2DES without knowing the key

Topic 3: Electronic Code Block (Encrypting messages that have variable length)

Section 1: Introducing the Encryption Algorithm

Background Info

The Electronic Code Block works by breaking the message into equal size blocks and then performing block cipher on each block with the same key then concatenating the result of each of the block ciphers.

Electronic Code Book Challenge 1: Encryption and Decryption

Section 2: Weakness i.e. frequency analysis. Demonstrate information leakage

Background Info

• ECB is deterministic. i.e. On a given input, it will always have the same output.
• It leaves plaintext data patterns in the ciphertext and creates opportunities for frequency analysis.
• Typical example is encrypting images using ECB:
• https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#Electronic_codebook_(ECB)
• Since the algorithm is deterministic, it is extremely easy to forge messages.

Electronic Code Book Challenge 2: Attacking the algorithm

Topic 4: Counter Mode Encryption (Encrypting messages that have variable length)

Section 1: Introducing the algorithm

Background Info

Unlike ECB, counter mode adds in randomness to the ciphertext.

Encryption:

Given key K and message M,

1. Like ECB, counter mode will first divide a long plaintext into multiple N-bits long blocks.
2. Randomly generate a N-bits Initialization Vector (IV). Save it as C[0], i.e. the first block of the ciphertext.
3. For the i-th plaintext block:
   1. Encrypt (treat IV as an integer, then add to it. If the result overflows, disregard the most significant bit) using block cipher with key K.
   2. Using the result from step a., xor with the i-th plaintext block.
   3. Save the result from step b as or block of the ciphertext.

Or visually,

Src: https://courses.cs.washington.edu/courses/cse484/21sp/slides/cse484-lecture10-sp21.pdf

Decryption:

Given key K and ciphertext C,

1. Divide the long ciphertext into multiple N-bits long blocks.
2. Take C[0] and treat it as the IV
3. To get the i-th plaintext block:
   1. Pass to the block cipher with key K
   2. Using the result from step a, xor with the ciphertext block to get the plaintext block

Advantage:

We do not need to inverse the block cipher.

Counter Mode Encryption Challenge 1: Encrypting a long message using CTR mode encryption

Section 2: What if IV is reused?

Background Info

There are a few things that we need to know before talking about reusing IV:

1. Block Cipher is deterministic. i.e. On a given key and message, a block cipher will always output the same ciphertext. No matter when it is done.
2. If messages are not the same, outputs will be random. i.e., you cannot predict the ciphertext of M, given the ciphertext of M’.
3. In counter mode, inputs to the block cipher are always different. Based on point 2, we could say the outputs of the block cipher are random. Since we are xoring each message block with a randomly generated bit-string, we are just applying OTP on each block.

What would happen if we reused an IV? Here assume we do not change the key

1. IV used to encrypt 2 messages will be the same.
2. IV + 1, IV + 2, …, IV + n used in these 2 encryptions will be the same.
3. Outputs of the block cipher, (inter 1, inter 2, …, inter N) will be the same since block cipher is deterministic given fixed message and key.
4. If inter 1, inter 2, …, inter N are the same in these 2 encryptions, we are essentially applying OTP using a used key which is problematic.

CTR Mode Challenge 2: attacking a flawed CTR mode encryption algorithm

Topic 5: Ciphertext Block Chaining

Section 1: Introducing the algorithm

Background Info

https://courses.cs.washington.edu/courses/cse484/21sp/slides/cse484-lecture10-sp21.pdf

To Encrypt

• A random IV which has the same length as a block will be generated
• Save the IV as C[0] (first block of the ciphertext)
• Let SK = IV, for i = 0, i < number of blocks, i++:
  • Xor SK with the Plaintext[i] to get Temp
  • Pass Temp through a block cipher with the key K to get C[i + 1]
  • Let SK = C[i + 1]

https://courses.cs.washington.edu/courses/cse484/21sp/slides/cse484-lecture10-sp21.pdf

To Decrypt:

• For i = number of blocks – 1, i >= 1, i–:
  • Decrypt C[i] using the decryption algorithm of the block cipher with the key K to get Temp
  • Xor Temp with C[i – 1] to get Plaintext[i – 1]

Challenge:

Section 2: Padding

Background Info

When do we need to do padding?

Since we need to pass Temp through a block cipher using the same key, K, all the Temps must have the same length. This means that length of the plaintext must be a multiple of N, where N is the length of a block.

Why does CTR not need to do padding?

What we are passing to the block cipher in CTR is the randomly generated IV + i. It is guaranteed to have the same length as the initial IV. If the last block of the plaintext has a length < N, we can simply remove the first/last few bits of InterI to make them to have the same length.

How do we pad the last block?

First attempt: Using 0 at the end of the block

Qn: How can we distinguish the padded 0 from the actual value 0?

Byte Padding: Block size is in bytes

PKCS#5 and PKCS#7:

Instead of using 0, we pad each byte with the value of total number of bytes added.

e.g.

If we only need to pad 1 byte, we will pad 01 at the end

2 byte: 02 02

3 byte: 03 03 03

Suppose the message is

… | AB 12 19 9C 11 05 F3 D4 | 5E 06

Block size = 8 bytes

The last block has a size of only 2 bytes

• We need to pad 6 bytes to the last block, so the value to pad is 06

Therefore, the padded message will be:

… | AB 12 19 9C 11 05 F3 D4 | 5E 06 06 06 06 06 06 06

Note: there are 7 06’s at the end of the last block, the first one is part of the message.

If the original message’s length is a multiple of N, where N is the block size, an extra block filled with N with be added to the end of the message

e.g. For message like

… | AB 12 19 9C 11 05 F3 D4 | 5E 06 12 51 0E AF BB 9D

Which has all blocks filled. The padded message will be

… | AB 12 19 9C 11 05 F3 D4 | 5E 06 12 51 0E AF BB 9D|08 08 08 08 08 08 08 08

This is to make the last block to always be a padded block. Why is this needed?

We will then encrypt this padded message using CBC.

Challenge: Determine if a padding is valid

Section 3: Padding Oracle Attack

Background Info

There are a few things to keep in mind before going deeper into the topic:

1. The last block is always padded
2. To get the plaintext[i – 1], we are xoring cipher[i – 1] and Dec(K, cipher[i])
3. 
4. 
5. The decryption algorithm will throw an invalid padding error when the plaintext[i – 1] it decrypted does not have a valid padding.

Without other protection, padding could possibly leak the entire message’s content.

Notation wise:

1. Let the last ciphertext block to be C
2. Let the second last ciphertext block to be C’
3. Let C[i] denotes the i’th byte of the block C, starting from 0
4. Let size of each block to be N

Let’s see how we can get the last byte:

1. There are 2 ways that a ciphertext can be decrypted without throwing an invalid padding error
   1. Decrypt the ciphertext without modifying it
   2. Set the last byte to be 01
2. We want to make use of the property 1.b.
   1. Recall the last step to decrypt a block is xoring with the previous ciphertext block
   2. We have edit access to the ciphertext block
3. Aim: Edit C’[N-1] such that
   1. We know that, without any modification , where A is the original value
   2. What if we make to be the last block.
      1. Based of the xor property, it will output 01 which will not throw an invalid padding error
   3. Now, we only need to find A.
      1. We know that there are 2 values that will not make the decryption algorithm to throw an invalid padding error
         1. 01, i.e.
         2. A, i.e.
      2. We just need to xor C’[N-1] with all possible values [02, FF] and send to the decryption algorithm to find the only value that does not throw an invalid padding error. The value will be A. (We only need 256 trials per byte)

How can we extend this to get all other bits?

Note: we already found out the last byte. We need to find the second last byte. What are the values that the last 2 bytes can take such that they will not cause an invalid padding error?

Challenge: Padding Oracle Attack to find out the entire block

Bonus Challenge: Padding Oracle Attack to find out the entire message

Click here for CTF challenges