Cryptography!

Encryption, Decryption, better methods

XOR ⊕

XOR = exclusive OR

Building block for encryption - bit by bit operator

0 ⊕ 0 = 0

1 ⊕ 0 = 1

1 ⊕ 1 = 0

XOR ⊕

What is a One-Time Pad (OTP)?

• An encryption scheme that solves some of the problems that we had with a Caesar Cipher
• An unbreakable and simple way to encrypt a message
• Very easy for a computer to compute
• One of the uses for XOR

​

One Time Pad - Encryption

Key (secret, random): 0011100100010000101110010010110110100000111100110010101101100100

ASCII encoding: 0100001001000101010001010101000001000010010011110100111101010000

Message: BEEPBOOP

XOR

Ciphertext: 0111101101010101111111000111110111100010101111000110010000110100

0⊕0=0

0⊕1=1

1⊕0=1

1⊕1=0

​

Decoded ciphertext: {Uü}â¼d4

Without knowledge of the key, it is impossible for an adversary to extract the message!

​

One Time Pad - Decryption

Key (secret, random): 0011100100010000101110010010110110100000111100110010101101100100

ASCII encoding: 0111101101010101111111000111110111100010101111000110010000110100

Ciphertext: {Uü}â¼d4

XOR

Message: 0100001001000101010001010101000001000010010011110100111101010000

0⊕0=0

0⊕1=1

1⊕0=1

1⊕1=0

​

Decoded message: BEEPBOOP

Do the same operation to the ciphertext to get the message back.

Why can’t our message and key be the same?

Why can’t our message and key be the same?

Recap:

​

• If message is the same as key, ciphertext will be all 0’s!
• Eve will be able to know our message!

One Time Pad Restrictions

• The key is as long as the message
• The key is pseudorandom*
• Only use the key ONCE
• OTP is very easy for a computer to compute using XOR

​

​

* Randomness will be covered tomorrow

One Time Pad

Notice that without the key it is actually impossible for the adversary to directly read the message! If you have the ciphertext below, two different keys will get you two different messages:

EVWSYW OFZ PQWR TP CVIQ EVWSYW OFZ PQWR TP CVIQ

$”#2:< ;.? 88;> 5$ ‘7>? $”#2:< ;.? 20%< 5$ -9&?

attack the hill at dawn attack the barn at noon

​

​

key1

key2

One Time Pad

Notice that without the key it is actually impossible for the adversary to directly read the message! If you have the ciphertext below, two different keys will get you two different messages:

EVWSYW OFZ PQWR TP CVIQ EVWSYW OFZ PQWR TP CVIQ

ECDSWM VYV IILG TW ZVMD ECDSWM VYV OQFE TW PHUD

​

attack the hill at dawn attack the barn at noon

Shifts never fall into repetitive pattern!

https://www.youtube.com/watch?v=FlIG3TvQCBQ

About OTP

• Easy to implement and compute (encryption and decryption are the same operation!)
• Computer can easily compute XOR
• Unbreakable if the key is truly random and not known by the attacker
• The only cipher that has perfect confidentiality

Any problems with OTP?

​

​

​

Problems with the OTP

Key is as long as the message - impractical when you have a lot of messages or a very long message.

Key can only be used once

Bits of the message correspond directly to bits of the ciphertext

Don’t know if a message is legitimate before decoding it

In order to share a secret message, you must first share a secret key. How do you share this key in the first place?

Problems with the OTP

Key is as long as the message - impractical when you have a lot of messages or a very long message.

Key can only be used once

Bits of the message correspond directly to bits of the ciphertext

Don’t know if a message is legitimate before decoding it

In order to share a secret message, you must first share a secret key. How do you share this key in the first place?

Simple message gets very long!

Can we break this the same way we did Caesar?

• Brute force?
• Frequency analysis?
• What else?

​

​

Integrity of One Time Pad

Integrity of One Time Pad

• It is highly vulnerable to tampering
• Alice is going to send Bob either 1 or 0 using an OTP
• The adversary can just flip the bit in the ciphertext
• Alice wants to withdraw $1000 from the bank using an OTP
• The adversary can just flip the bit again so Alice will never gets the right amount

Problems with the OTP

In order to share a secret message, you must first share a secret key. How do you share this key in the first place?

Key must be random.

Don’t know if a message is legitimate before decoding it.

Key can only be used once.

​

​

Try it!

Write the functions in OTP_Exercise.py so that you can do the following:

>>> key = get_key(16)�>>> message = ‘sixteen-byte msg’�>>> ciphertext = encrypt(message, key)�>>> ciphertext�b'\x1f\xdeE4\x12&6\x9aSmNZ\xaf\x97\xb1\xc2' #your results will differ�>>> decrypt(ciphertext, key)�‘sixteen-byte msg’

Tomorrow....

• We’ll learn how to exploit a reused OTP

​