Week 7 – Part 1
Deakin University CRICOS Provider Code: 00113B
SIT182 – Real World Practices For Cyber Security
Trimester 2 – 2021
Deakin College
Week 7 – Part 1
Deakin University CRICOS Provider Code: 00113B
Cryptography – Foundations
2
Topics,
“Cryptography has generated number theory, algebraic geometry over finite fields, algebra,
combinatorics and computers.” – Vladimir Arnold
3
Deakin University CRICOS Provider Code: 00113B
Cryptography = math. It’s the most scientific
part of security and the most fun ☺.
Considering the ULOs of this unit, we have
tried to simplify things to the extent
possible and a lot of details are removed
when discussing topics.
You will be assessed to the extent covered
in the lecture for the final exam. What’s
included is the minimum you MUST know
after completing this unit – as per ULOs.
More details, in you future Cryptography
unit – which requires completion of the
Discrete Math unit first.
Note
3
Deakin University CRICOS Provider Code: 00113B
Cryptography
4
Cryptography is the art and science of secret writing, encrypting, or hiding of information from all but the
intended recipient.
Cryptography is:
• A tremendous tool
• The basis for many security mechanisms
It is:
• NOT the solution to all security problems
• Reliable IF implemented properly
• Reliable IF used properly
Valid for all security mechanisms really
(remember Week 1?)
Deakin University CRICOS Provider Code: 00113B
Example: lessons from Task 1.4P?
5
In Task 1.4P, you were able to extract username and password because the traffic was sent in clear
and no encryption was used.
Deakin University CRICOS Provider Code: 00113B
Example: lessons from Task 1.4P?
6
In network security context, we assume attackers can control the network, intercept packets, tamper with or suppress
them, inject arbitrary packets, …
In Task 1.4P, if traffic was sent as encrypted, username and password were not accessible by simply
tapping on to the traffic.
Deakin University CRICOS Provider Code: 00113B
Cryptography and CIA
7
Characteristic Description (reminder) Protection
Confidentiality Ensures that only authorized parties
can view the information
Encrypted information can only be
viewed by those who have been
provided the key.
Integrity Ensures that the information is correct
and no unauthorized person or
malicious software has altered that
data
Encrypted information cannot be
changed.
Availability Ensures that data is accessible to
authorized users
Authorized users are provided the
decryption key to access the
information.
Authentication Provides proof of the genuineness of
the user
Proof that the sender was legitimate
and not an imposter can be obtained.
Nonrepudiation Proves that a user performed an action Individuals are prevented from
fraudulently denying that they were
involved in a transaction.
Deakin University CRICOS Provider Code: 00113B
Encryption and Decryption
8
Encryption:
The process of converting an original message
(Plaintext) into unintelligible enciphered or encoded
message (Ciphertext).
Decryption:
The process of converting an encoded message
(Ciphertext) to original readable form (Plaintext).
Encrypt
ciphertext
►
keye (optional)
►plaintext
Decrypt
plaintext ►
keyd (optional)
►ciphertext
Deakin University CRICOS Provider Code: 00113B
Encryption and Decryption (different notation)
9
As mentioned, encryption and decryption are functions which transform one text into another.
In functional notation:
C = E (P) and P = D(C )
C denotes ciphertext, E is the encryption rule, D is the decryption rule, P is the plaintext.
In this case, we also have:
P = D(E (P))
It is obviously important to be able to recover the original message from the ciphertext!
Deakin University CRICOS Provider Code: 00113B
Keyed Ciphers
10
Often the encryption and decryption algorithms use a key K . The key can be a series of bits used in a
mathematical algorithm (used for E/D) or the knowledge of how to manipulate the plaintext.
So, the functional dependence can be re-written as:
C = E (P, KE) and P = D(C , KD)
* If KE = KD , then the algorithm is called symmetric. If not, then it is called asymmetric. (we will come back to this)
P = D(E (P)) also is re-written as:
P = D(E (P, KE), KD)
An algorithm that does not use a key is called a keyless cipher.
Deakin University CRICOS Provider Code: 00113B
Cryptanalysis
11
Cryptanalysis is the process of attempting to break a cryptographic system and return the encrypted
message to its original form. (remember Week 1? Enigma and Alan Turing story?)
A cryptanalyst may attempt to do any or all of the following (threats):
• to break a single message;
• to recognize patterns in encrypted messages;
• to infer some meaning without breaking the algorithm;
• to deduce the key;
• to find weaknesses in the implementation or environment or the use of encryption;
• to find weaknesses in the algorithm, without necessarily having intercepted any messages.
https://en.wikipedia.org/wiki/Enigma_machine
Deakin University CRICOS Provider Code: 00113B
What is Good Encryption?
12
The following are suggested as tests of worth for current cryptographic practice:
• is based on sound mathematics;
• has been analysed by competent experts and found to be sound;
• has stood the test of time.
• An encryption algorithm is called breakable if, given enough time and information, a
cryptanalyst can recover the plaintext.
• Most encryption algorithms are breakable since the analyst can try all keys
systematically.
• Being breakable does not mean that it is feasible to break.
Breakable Encryption
Deakin University CRICOS Provider Code: 00113B
Strong Encryption
13
A cryptosystem is strong if there is no analytic approach that is substantially faster than brute
force—i.e., trying all the keys one by one. Most strong algorithms are still breakable.
The larger the keyspace, the longer to find the key by search.
– How do you compute the size of the keyspace?
Many ciphers use a n-bit string as key. Given a small number of plaintext/ciphertext
pairs encrypted under key K, K can be recovered by exhaustive search in an expected time on
the order of 2n operations. (E.g., a 1 byte key -> the keyspace is 28 = 256 possible key [1 byte = 8 bits])
Keyspace: the entire range of values that can be used to construct an individual key.
Deakin University CRICOS Provider Code: 00113B
Ciphers: Building Blocks
14
The simplest building blocks of encryption are:
• Substitution: in which each symbol is replaced with another (not necessarily uniformly)
• Transposition: in which the order of symbols is rearranged.
It might seem that these are too naive to be effective. But almost all modern commercial
symmetric ciphers use some combination of substitution and transposition for encryption.
Example Substitutions Example Transposition
Deakin University CRICOS Provider Code: 00113B
Substitution Cipher
Deakin University CRICOS Provider Code: 00113B
Substitution Ciphers
16
• A substitution cipher is one in which each symbol of the plaintext is replaced with another
symbol.
• If this is done uniformly this is called a monoalphabetic cipher or simple substitution cipher.
• If different substitutions are made depending on where in the plaintext the symbol
occurs, this is called a polyalphabetic substitution.
Read on, more details in the next slides…
Deakin University CRICOS Provider Code: 00113B
Simple Substitution Cipher
17
A simple substitution cipher is a 1-1 mapping of the alphabet into itself or another alphabet.
A simple substitution is breakable; we could try all k! mappings from the plaintext
to ciphertext alphabets. That’s usually not necessary though… (you will understand the reason by slide
25)
Redundancies in the plaintext, such as letter frequencies, diagrams (e.g., th), etc., are reflected
in the ciphertext.
Factorial of positive integer n, denoted as n!, is the product of all positive
integers less than or equal to n. E.g., 3! = 3 (2) (1) = 6
Deakin University CRICOS Provider Code: 00113B
Example Monoalphabetic Substitution Cipher: Caesar Cipher
18
The Caesar Cipher is a monoalphabetic cipher in which each letter is replaced in the encryption
by another letter a fixed “distance” away in the alphabet.
For example, A is replaced by C, B by D, …, Y by A, Z by B, etc.
Plaintext: meet me at deakin
Cyphertext: oggv og cv fgcmkp
• What is the key?
• What is the size of the keyspace? Is the algorithm strong?
Try it out at https://cryptii.com/pipes/caesar-cipher
https://cryptii.com/pipes/caesar-cipher
Deakin University CRICOS Provider Code: 00113B
Example Monoalphabetic Substitution Cipher: Caesar Cipher
19
E: encryption algorithm
D: decryption algorithm
P: plaintext (A ≡ 0, B ≡ 1, C ≡ 2, …, Z ≡ 25)
C: ciphertext (A ≡ 0, B ≡ 1, C ≡ 2, …, Z ≡ 25)
K: key in {0, 1, 2, 3, …, 25}; in the previous slide K = 2.
a mod n: the remainder when a is divided by n, e.g. 15 mod 26 = 15 and (15 + 26) mod 26 = 15
The general Caesar Cipher is:
C = E(P, K) = (P + K) mod 26
P = D(C, K) = (C – K) mod 26
Try it out at https://cryptii.com/pipes/caesar-cipher
https://cryptii.com/pipes/caesar-cipher
Deakin University CRICOS Provider Code: 00113B
Example Polyalphabetic Substitution Cipher: Vigenère cipher
20
The Vigen`ere Cipher is an example of a polyalphabetic cipher.
Start with a key string: “monitors to go to the bathroom” and a plaintext to encrypt: “four score
and seven years ago.” Align the two texts, possibly removing spaces:
Try it out at https://cryptii.com/pipes/vigenere-cipher
Then use the letter pairs to look up an encryption in a table – see next slide for the table.
plaintext: fours corea ndsev enyea rsago
key: monit o r s t o g o t o t hebat hroom
ciphertext: rcizl qfkxo t r l s o l r z e t yjoua
https://cryptii.com/pipes/vigenere-cipher
Deakin University CRICOS Provider Code: 00113B
Example Polyalphabetic Substitution Cipher: Vigenère cipher
21
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
A A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
B B C D E F G H I J K L M N O P Q R S T U V W X Y Z A
C C D E F G H I J K L M N O P Q R S T U V W X Y Z A B
D D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
E E F G H I J K L M N O P Q R S T U V W X Y Z A B C D
F F G H I J K L M N O P Q R S T U V W X Y Z A B C D E
G G H I J K L M N O P Q R S T U V W X Y Z A B C D E F
H H I J K L M N O P Q R S T U V W X Y Z A B C D E F G
I I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
J J K L M N O P Q R S T U V W X Y Z A B C D E F G H I
K K L M N O P Q R S T U V W X Y Z A B C D E F G H I J
L L M N O P Q R S T U V W X Y Z A B C D E F G H I J K
M M N O P Q R S T U V W X Y Z A B C D E F G H I J K L
N N O P Q R S T U V W X Y Z A B C D E F G H I J K L M
O O P Q R S T U V W X Y Z A B C D E F G H I J K L M N
P P Q R S T U V W X Y Z A B C D E F G H I J K L M N O
Q Q R S T U V W X Y Z A B C D E F G H I J K L M N O P
R R S T U V W X Y Z A B C D E F G H I J K L M N O P Q
S S T U V W X Y Z A B C D E F G H I J K L M N O P Q R
T T U V W X Y Z A B C D E F G H I J K L M N O P Q R S
U U V W X Y Z A B C D E F G H I J K L M N O P Q R S T
V V W X Y Z A B C D E F G H I J K L M N O P Q R S T U
W W X Y Z A B C D E F G H I J K L M N O P Q R S T U V
X X Y Z A B C D E F G H I J K L M N O P Q R S T U V W
Y Y Z A B C D E F G H I J K L M N O P Q R S T U V W X
Z Z A B C D E F G H I J K L M N O P Q R S T U V W X Y
Plain: f o u
Key: m o n
Cipher: r c h
plain
key
Remember: Obviously, the key should be as
long as the plaintext.
Now, how to decrypt?
Simple, locate the first letter of the key in
left column (e.g., m), look in that row for
first letter of the cipher (e.g., r), what’s the
corresponding plaintext? ☺
Deakin University CRICOS Provider Code: 00113B
Cryptanalysis of Vigenère cipher
22
Assume you are an attacker, how could you break a text encrypted with Vigenere without
knowing the key?
• The Vigen`ere Cipher selects one of twenty-six different Caesar Ciphers, depending
upon the corresponding letter in the key.
• It is susceptible to “statistical analysis”. Both key and plaintext are English language
strings and so have the entropy characteristics of English.
• In particular, the letters E, A, O, T, N, I make up approximately 50% of English text.
Thus, at approximately 25% of indices, these can be expected to coincide.
We cannot cover “the how” in more details in this unit yet. More, in your Cryptography unit ☺! Keen to read more
in the meantime, try http://nob.cs.ucdavis.edu/classes/ecs155-2013-04/extras/vigenere.html – simplified.
http://nob.cs.ucdavis.edu/classes/ecs155-2013-04/extras/vigenere.html
Deakin University CRICOS Provider Code: 00113B
Breaking a Cipher
23
…
…
…
…
{M}
K
?
Sender
Analyst/Attacker
A cryptanalyst’s/attacker’s task is extracting the correct
decryption from the space of possible decryptions, given
limited information.
How much can she glean/extract from the ciphertext
and the circumstances to reduce the search space?
Deakin University CRICOS Provider Code: 00113B
Classification of Attacks Against Encryption Algorithms
24
Attacks on an encryption algorithm are classified according to what information is available to
the attacker.
• Ciphertext-only: attacker has only encrypted text
• Known plaintext: attacker has some ciphertext/plaintext pairs.
• Chosen plaintext: attacker can cause messages of his choosing to be encrypted.
• Adaptive chosen plaintext: chosen plaintext attack adjusted according to earlier results.
• Chosen ciphertext: attacker can decrypt selected ciphertext.
Consider Vigenere against each attack…
Deakin University CRICOS Provider Code: 00113B
Using Information for Cryptanalysis
25
Question 1: Suppose you know that “xyy” encodes a string in the English alphabet (26 letters)
using a substitution cipher. How many decryptions are possible? Note with Vigenère cipher
the 2 “y”s may correspond to 2 different plaintext symbols.
Answer 1: 263= 17576.
Question 2: Add the information that it’s a simple substitution cipher. In this case xyy is
equivalent to xy.
Answer 2: 26 × 25 = 650. (Reduce search space by a factor of 27)
Question 3: Add that you know the plaintext is an English word:
Answer 3: around 40 ☺ (Reduce original search space by a factor of 439.)
Deakin University CRICOS Provider Code: 00113B
Perfect Cipher
26
A perfect cipher would be one for which no reduction of the search space is gained from
knowing:
1. The encryption algorithm, and
2. The ciphertext.
In other words, a perfect cipher can never be broken, even with after an unlimited time. Does it
exist?
Interestingly, ideal ciphers exist and can be implemented in practice, but they are, in fact,
impractical. (we will have an example Perfect Cipher in Week 9 content)
Deakin University CRICOS Provider Code: 00113B
Confusion and Diffusion
27
Two methods for frustrating statistical croptanalysis (introduced by Claude Shanannon in 1949) are:
• Confusion:
o Transforming information in plaintext into cipertext in a key-dependent manner so that an
interceptor cannot readily extract it
o Complicating the relationship between the statistics of the ciphertext and the value of the
encryption key
• Diffusion:
o Spreading the statistics of the plaintext widely over the ciphertext by allowing each plaintext
symbol to affect the value of multiple cyphertext symbols (e.g., letting a ciphertext symbol
equal to average of multiple plaintext symbols so that a plaintext symbol will end up being
used in the avergaing operation of multiple ciphertext symbols)
o Complicating the statistical relationship between the plaintext and ciphertext symbols.
Substitution tends to be good at confusion; transposition tends to be good at diffusion.
Deakin University CRICOS Provider Code: 00113B
References and Further Reading
– [Chapter 9] Matt Bishop, Computer Security Art and Science, Addison-Wesley.
– [Chapter 8] Michael E. Whitman, Principles of Information Security, Cengage.
– [Chapter 6] M. Ciampa, Security Awareness Applying Practical Security in Your World, Cengage Learning, 2016.
28
Deakin University CRICOS Provider Code: 00113B
Acknowledgement
Acknowledging the kind support and contribution of:
Dr Arash Shaghaghi (Deakin University, Australia), Prof. Chang-Tsun Li (Deakin University, Australia), Prof. Sanjay
Jha (The University of New South Wales, Australia), Dr. Nicolas Courtois (University College London, UK), Dr. Young
(University of Texas at Austin).
29