Codes versus Ciphers
Symmetric Cryptography Public Key Cryptography
Codes versus Ciphers
13/103
Codes versus Ciphers
Symmetric Cryptography Public Key Cryptography
Codes vs. Ciphers
A code is any way to represent data.
Will use bitstrings (sequence of bits) to represent data. Examples:
– Morse Code, ASCII, Hex, Base64
A cipher is a code where it is difficult to derive data from code.
Almost always uses a key.
Data for a cipher usually called plain text, encoding called cipher text
Function from plain text to cipher text called encryption Function from cipher text to plain text called decryption
14/103
Codes versus Ciphers
Symmetric Cryptography Public Key Cryptography
Codes vs. Ciphers
What is “27” encoded in binary? • 0010 0111
• 0001 1011
• 110110 111011
• 0011 0010 0011 0111 • All of the above
15/103
Codes versus Ciphers
Symmetric Cryptography Public Key Cryptography
Codes vs. Ciphers
What is “27” encoded in binary?
• 0010 0111
• 0001 1011
• 110110 111011
• 0011 0010 0011 0111 • All of the above
27 as decimal 27 as hex
27 as Base64 27 as ASCII Yes
15/103
Codes versus Ciphers
Symmetric Cryptography Public Key Cryptography
Hex
Characters 0 to F encode 4 bits
Easiest way to write down binary as text
0=0000 8=1000 1=0001 9=1001 2=0010 A=1010 3=0011 B=1011 4=0100 C=1100 5=0101 D=1101 6=0110 E=1110 7=0111 F=1111
27 in binary is 0001 1011, hence it is 1B in Hex
16/103
Codes versus Ciphers
Symmetric Cryptography Public Key Cryptography
ASCII
17/103
Codes versus Ciphers
Symmetric Cryptography Public Key Cryptography
Base64
Shortest way to write binary as printable characters Common for keys and crypto
This module will use Hex
18/103
Codes versus Ciphers
Symmetric Cryptography Public Key Cryptography
Code Demos
See Recording.
19/103
Codes versus Ciphers
Symmetric Cryptography Public Key Cryptography
Caesar Cipher
One of the first ciphers was used by Julius Caesar.
The Caesar Cipher replaces each letter of the alphabet with one three to the right, i.e.
a becomes d b becomes e ···
z becomes c.
20/103
Codes versus Ciphers
Symmetric Cryptography Public Key Cryptography
Using a Key
These ciphers are easy to break because as soon as you know the scheme you can decrypt the message.
Kerckhoffs’ principle: A cipher should be secure even if the attacker knows everything about it apart from the key.
For instance, we can use the Caesar cipher using n rotations.
21/103
Codes versus Ciphers
Symmetric Cryptography Public Key Cryptography
from Wikipedia 22 / 103
Codes versus Ciphers
Symmetric Cryptography Public Key Cryptography
from Wikipedia 23 / 103
Codes versus Ciphers
Symmetric Cryptography Public Key Cryptography
from Wikipedia 24 / 103
Codes versus Ciphers
Symmetric Cryptography Public Key Cryptography
Using a Key
For instance, we can use the Caesar cipher with n rotations
But only 26 possible keys so you can just try them all (breaking the cipher is 26 times harder without the key)
25/103
Codes versus Ciphers
Symmetric Cryptography Public Key Cryptography
Using a Key
For instance, we can use the Caesar cipher with n rotations But only 26 possible keys so you can just try them all
(breaking the cipher is 26 times harder without the key)
A better scheme replaces each letter with another letter. Here there are 26! ≈ 4 · 1026 possible keys.
25/103
Codes versus Ciphers
Symmetric Cryptography Public Key Cryptography
Frequency Analysis
While hard to break by brute force, replacing each letter with another is easy to break using frequency analysis.
Frequency analysis counts the number of times each symbol occurs
each pair of symbols etc.
and tries to draw conclusions from this.
26/103
Codes versus Ciphers
Symmetric Cryptography Public Key Cryptography
Frequency Analysis
from Wikipedia
27/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
Symmetric Cryptography
28/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
Modular Arithmetic
Arithmetic modulo n means that you count up to n − 1 then loop back to 0
i.e., 0,1,2,…,n−1,0,1,2,…,n−1,0,1,2,… a mod b = r for largest whole number k such that
a=b∗k+r
e.g. 9mod4=1because9=2∗4+1
29/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
xor
xor (⊕) is binary addition modulo 2:
0⊕0=0 1⊕0=1 1⊕1=1 1⊕1=0
xor on bitstrings of same length defined by applying xor to corresponding bits
Important properties
xor is associative and commutative for all bitstrings M, M ⊕ 0 = M for all bitstrings M, M ⊕M = 0
where 0 is a bitstring of all 0’s of the appropriate length
30/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
One Time Pads
Needs a key as long as the message.
Message: HELLOALICE Key:
Cipher text:
31/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
One Time Pads
Needs a key as long as the message.
Message: HELLOALICE Key: THFLQRZFJK Cipher text:
31/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
One Time Pads
Needs a key as long as the message. XOR/add the key and the message:
Message: Key:
Cipher text:
HELLOALICE
THFLQRZFJK
ALRWERKNLO
31/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
One Time Pads
Needs a key as long as the message.
Cipher text : ALRWERKNLO Key:
Plain text:
32/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
One Time Pads
Needs a key as long as the message.
Cipher text : ALRWERKNLO Key: THFLQRZFJK Plain text:
32/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
One Time Pads
Needs a key as long as the message. XOR/add the key and the message:
Cipher text : Key:
Plain text:
ALRWERKNLO
THFLQRZFJK
HELLOALICE
32/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
One Time Pads
Needs a key as long as the message.
Cipher text : ALRWERKNLO Key:
Plain text:
33/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
One Time Pads
Needs a key as long as the message.
Cipher text : ALRWERKNLO Key: UXDTDXFHXN Plain text:
33/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
One Time Pads
Needs a key as long as the message. XOR/add the key and the message:
Cipher text : Key:
Plain text:
ALRWERKNLO
UXDTDXFHXN
GOODBYEBOB
33/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
One Time Pads
Have perfect encryption:
You don’t learn anything about the plaintext from the ciphertext
Theorem
Given any ciphertext of a certain length, without knowing the key the probability of the ciphertext being the encryption of a plaintext of the same length is the same for all plaintexts of the same length as the ciphertext.
34/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
One Time Pads
Problem
The key needs to be as long as the message Must use key only once
Russia during and after WW2
Reused the key material (ie encrypted several messages with
the same key)
Broken by the Venona project
35/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
Block Ciphers
Modern ciphers work on blocks of plain text, not just a single symbol.
They are made up of a series of permutations and substitutions repeated on each block.
The key controls the exact nature of the permutations and subsitutions
36/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
Advanced Encryption Standard (AES)
AES is a state-of-the-art block cipher.
It works on blocks of 128-bits.
It generates 10 round keys from a single 128-bit key.
It uses one permutation: ShiftRows and three substitutions SubBytes, MixColumns, AddRoundKey.
37/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
Advanced Encryption Standard (AES)
A block of 128 bits is represented by a 4×4-matrix where each matrix element is a byte (8 bits), written as
a0,3 a1,3 a2,3
a0,0 a1,0 a2,0
a0,1 a0,2
a1,1 a1,2
a2,1 a2,2
a3,0 a3,1 a3,2 a3,3
38/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
SubBytes: S-box
from Wikipedia
SubByte is an operation on bytes using finite field arithmetic
39/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
ShiftRows
from Wikipedia
ShiftRows moves the
2nd row one byte to the left,
the 3rd row two bytes and the 4th row 3 bytes.
40/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
MixColumn
from Wikipedia
MixColumn is a substitution of each column such that:
(a0x3 + a1x2 + a2x + a3) × (3×3 + x2 + x + 2) mod(x4 + 1) = (b0x3 + b1x2 + b2x + b3)
41/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
AddRoundKey
from Wikipedia
AddRoundKey applies ⊕ to the block and the 128-bit round key (which was generated from the main key).
42/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
Security of AES
No formal proof of security (P = NP?) but best known cryptographic attack requires 2126 key guesses – an (irrelevant) improvement of factor 4 compared to 2128 key guesses via brute force attack
There are side channel attacks (eg via measuring power consumption, execution time) — see later in the course. Key aspects of security:
Shuffling of rows and columns to ensure small change in input causes very big change in output
Require at least one non-linear operation (in the sense of linear algebra) on the data – provided by the SubByte-operation
43/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
DES
The Data Encryption Standard (DES), was the previous standard.
Designed by IBM in early 1970’s
Before it was accepted as a standard the NSA stepped in and added S-boxes and fixed the key length at 56 bits
44/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
DES
S-boxes are a type of substitution.
It was unclear at the time why the NSA added S-boxes to the design.
Many believed these were a back door for the NSA.
45/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
DES
In 1990, Biham and Shamir discovered differential cryptanalysis.
The S-boxes had made DES resistant to differential cryptanalysis.
It seems that the NSA knew about differential cryptanalysis, at the start of the 1970s and had step into to protect DES.
46/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
Cost to Break DES
1977, Diffie and Hellman, theoretically: $20 million, break in 1 day.
1993, theoretically $1 million, in 7 hours.
1997, RSA Security offer $10,000 for a real break, won by a
distributed computing project, at “no cost”
EFF (Electronic rights group) break in 56 hours for $250,000
2006, COPACOBANA, general purpose brute force, break DES for $10,000
2016, hashcat on Nvidia GeForce GTX 1080 Ti GPU costing $1000 USD recovers a key in an average of 15 days
47/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
A word about key length
Source: https://xkcd.com/538/
48/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
3-DES
Triple DES, was a stop gap until AES 3-DES takes 3 keys, k1, k2 and k3.
Ek1,k2,k3 (M) = Ek3 (Dk2 (Ek1 (M)))
Setting k1 = k2 = k3 gives you DES Expected to be good until 2030 Used in bank cards and RFID chips
49/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
Padding
Block ciphers only work on fixed size blocks.
If the message isn’t of the right block size we need to pad the message.
But receiver needs to tell the difference between the padding and message.
50/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
Padding
Add random bytes to the end of the block?
51/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
Padding
Add random bytes to the end of the block? No.
51/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
Padding
Add random bytes to the end of the block? No. Add zeros to the end of the block?
51/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
Padding
Add random bytes to the end of the block? No. Add zeros to the end of the block? No.
51/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
Padding
Add random bytes to the end of the block? No. Add zeros to the end of the block? No.
Write “this is padding”?
51/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
Padding
Add random bytes to the end of the block? No. Add zeros to the end of the block? No.
Write “this is padding”? No.
51/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
Padding: PKCS 5/7
If there is 1 byte of space write 01
If there are 2 byte of space write 0202
If there are 3 byte of space write 030303
···
If the message goes to the end of the block add a new block of 16161616..
PKCS 7: 16 byte block, PKCS 5: 8 byte block
52/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
Block Cipher Modes
Block Ciphers can be used in a number of modes: 1 Electronic codebook mode (ECB)
each block is encrypted individually,
encrypted blocks are assembled in the same order as the plain text blocks.
if blocks are repeated in the plain text, this is revealed by the cipher text.
53/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
Demo Block Problems
54/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
Block Cipher Modes
Original
55/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
Block Cipher Modes
Source: Wikipedia
Original ECB
55/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
Block Cipher Modes
2 Cipher Block Chaining Mode (CBC)
each block XOR’d with previous block
start with a random Initialization Vector (IV ) helps overcome replay attack.
Suppose the IV= C1= C2=
···
Cn=
plain text is B1, B2, . . . , Bn. random number (sent in the clear) encrypt(B1 ⊕IV)
encrypt (B2 ⊕ C1 )
encrypt(Bn ⊕ Cn−1)
56/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
Block Cipher Modes
Source: Wikipedia
57/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
CBC decrypt
Receive IV
Receive cipher text C1, C2, . . . , Cn Plain text is B1,B2,…,Bn, where
B1 = B2 = ··· Bn =
decrypt(C1) ⊕ IV decrypt(C2) ⊕ C1
decrypt(Cn) ⊕ Cn−1
58/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
CBC decrypt
Source: Wikipedia
59/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
Block Cipher Modes
Source: Wikipedia
Original CBC
60/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
Probabilistic Encryption
Probabilistic encryption schemes use random elements to make every encryption different.
CBC with a random IV is a good way to make encryption probabilistic.
Using CBC and random IVs lets me encrypt the same message, and with the same key, without an attacker realising.
61/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
Misuse of IV
IV must be random, different for each encrypted block
https://xkcd.com/221
Choosing fixed IV can have devastating effect
(Zerologon vulnerability for Microsoft Windows (https://www.secura.com/pathtoimg.php?id=2055))
62/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
Zerologon
Windows has RPC for updating password on the domain controller
Uses cryptographic protocols for authenticating these requests
In particular, use AES with block cipher mode called CFB8, which uses IV exactly as CBC mode.
This is secure with randomly chosen IV Implementation chooses IV to be always 0
63/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
Zerologon
Consequence: AES-CFB8 encryption on all-zero plaintext will produce all-zero ciphertext
This can be used to bypass authentication completely and set domain controller password
Attack only requires network access to domain controller, which is available from any machine in the domain
CVSS score of 10.0
Department of Homeland Security forced all US government institutions to patch Windows Servers within three days
64/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
Sony PlayStation
Sony needs to stop games being copied.
CD and full disk encryption
User can read and write areas of the hard disk, for own files, notes, etc
Why won’t CBC work?
65/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
Sony PlayStation
With CBC, you need to encrypt, or decrypt, the whole file to get to the end.
The Sony PlayStation uses ECB full disk encryption, to stop people copying games.
User can access files they made themselves Hardware controls user access to data.
66/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
Sony PlayStation
Disk Encryption Attack
1 Remove disk and make copy
2 Replace disk in Playstation.
67/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
Sony PlayStation
Disk Encryption Attack
1 Remove disk and make copy
2 Replace disk in Playstation.
3 Copy a file to the disk
4 Remove disk and find the bit of disk that changed (this is the encrypted file)
68/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
Sony Play Station
Disk Encryption Attack
5 Copy target data to user area
69/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
Sony PlayStation
Disk Encryption Attack
5 Copy target data to user area
6 Restart the PlayStation and ask for your file back
7 PlayStation decrypts the file and gives you back the plain text
70/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
Counter Mode (CTR)
Plain text: B1,B2,…,Bn
IV : random number (sent in clear) Cipher text: C1, C2, . . . , Cn where
C1 = C2 = ··· Cn =
B1 ⊕encrypt(IV)
B2 ⊕ encrypt(IV + 1)
Bn ⊕encrypt(IV +n−1)
71/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
Counter Mode (CTR)
Source: Wikipedia
72/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
Counter Mode (CTR)
73/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
Cipher Texts Can Be Altered
AES encryption with a particular key maps any 128-bit block to a 128-bit block (or 256)
AES decrypt also maps any 128-bit block to a 128-bit block. Decrypt can be run on any block (not just encryptions).
74/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
Known Plain Text Attacks
If I know the plaintext I can change CTR encrypted messages eg If I know EncCTR(M1) and I know M1, I can make a
ciphertext that decrypts to any message I want, eg M2 New ciphertext is
EncCTR (M1) ⊕ (M1 ⊕ M2)
75/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
Known Plain Text Attacks
Decrypt it:
DecCTR (EncCTR (M1) ⊕ (M1 ⊕ M2)) =
76/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
Known Plain Text Attacks
Decrypt it:
DecCTR (EncCTR (M1) ⊕ (M1 ⊕ M2)) = DecCTR(Enc(N||Ctr) ⊕ M1) ⊕ (M1 ⊕ M2) =
76/103
Codes versus Ciphers
Symmetric Cryptography
Public Key Cryptography
Known Plain Text Attacks
Decrypt it:
DecCTR (EncCTR (M1) ⊕ (M1 ⊕ M2)) = DecCTR(Enc(N||Ctr) ⊕ M1) ⊕ (M1 ⊕ M2) = Enc(N||Ctr) ⊕ (Enc(N||Ctr) ⊕ M1) ⊕ (M1 ⊕ M2) =
M2
Have to stop this Subject of future lecture
76/103