CIS1003 Introduction to

Cybersecurity
[3] Cryptography
Dr David Glance
A unit about cats
cybersecurity
https://www.cryptokitties.co/
An example of a Non-Fungible
Token
Each digital CryptoKitty is owned
by a user validated on the Ethereum
blockchain
3 things
 Understand how cryptography is a
control for confidentiality and integrity
 Achieving encryption through
confusion and diffusion
 Managing keys for symmetric and
asymmetric cryptography
 Some History

 We won’t start with Julius Caesar (Born 100 BC)

 Herodotus (425 BC) The Histories talks about
Demaratus warning the Greeks about an
impending attack by Xerxes (Persian) – used
writing on a board and then covered in wax
(Steganography)
 Ancient Chinese wrote messages on silk, scrunched
and the covered in wax and swallowed!
 Caesar Cipher
 Messages sent by Caesar used a substitution cipher
 Replace letters by that letter shifted 3 positions
 AX
 BY

Plaintext: THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG

Ciphertext: QEB NRFZH YOLTK CLU GRJMP LSBO QEB IXWV ALD

 Known as ROT3 (ROTation)

 Decipher by right-shifting ciphertext characters 3
 Some simple maths
 Assume letters are numbered from 0 - 25
 where n = key, x = plaintext letter
 where n = key, x = ciphertext letter
 Reminder: modular math where A = dividend, B = modulus, Q = quotient, R =
remainder. Modulus (% in programs and calculators) just takes the remainder so
Or an easier
approach
 What could go wrong?
 For Julius Caesar, the cipher worked, in
part because his enemies were mostly
illiterate
 It can be attacked using cryptanalysis, in
this case using:
 Brute force: just decrypt using 1 to 25 as the
shift and search for meaningful text
 Letter frequency – just measure the
frequency of the letters in ciphertext and
compare to see how much it has shifted
 Al-Kindi

 Came up with cryptanalysis

 Book Manuscript on Deciphering
Cryptographic Messages in 870 AD
 Not only used letter frequencies but noted
that double letters, and 2-,3-letter words
occurred with a certain frequency

Michel Bakni https://commons.wikimedia.org/w/index.php?curid=97536463

 Cryptology, Ciphers, and Codes
 Cryptology is the discipline of study of cryptography and cryptanalysis.
 Term derived from Greek Kryptós (hidden) and lógos (word)
 Codes are a mapping of one representation of information for another. They operate on the
semantic level of information
 Morse code turns characters into dots and dashes and also used other codes as abbreviations
 Computer codes like ASCII (American Standard Code for Information Interchange) and Unicode
 U+1F600 =
 Ciphers are algorithms that operate on syntax and are semantic agnostic
 Caesar cipher
 Polyalphabetic Cipher
 Substitution cipher using multiple substitution alphabets
 Vigenère cipher was invented by Giovan Battista Bellaso in 1553
 Misatributed to Blaise de Vigenère
 Works by using a repeating key word: letters are shifted by the number code of the letter in
the key

Plaintext H A C K I N G I S F U N
Code 7 0 2 10 8 13 6 8 18 5 20 13
Key C A T S C A T S C A T S
Shift 2 0 19 18 2 0 19 18 2 0 19 18
Ciphertext J A V C K N Z A U F N F
Vigenère Table
 Basically a series of Caesar
ciphers
 To use, find the letter of the
plaintext along the top row and
the corresponding letter of the
key on the side column and take
the letter that intersects
 Breaking Vigenère
 Because there are multiple possible ciphertext letters for each plaintext letter, frequency
analysis is not possible
 Friedrich Kasiski (1863) developed an attack strategy:
 Find repeated use of the same key to estimate the key length
Plaintext: CRYPTOISSHORTFORCRYPTOGRAPHY
Key: ABCDABCDABCDABCDABCDABCDABCD
Ciphertext: CSASTPKVSIQUTGQUCSASTPIUAQJB
 The repetitions are 16 characters apart and so the key length is 16,8,4,2 or 1

 Once you have the key length, then look at frequency analysis of the individual Caesar ciphers
 Other attack strategies: Friedman’s (kappa) test, Kerchoff’s method
 One-Time Pads
 Longer “shift words” and shorter messages make frequency analysis more difficult and making it
harder it is to crack a message
 A one-time pad is a list of random shifts; selected shift sequence must be longer than your message
 This is uncrackable , because of 2 important properties
 Shifts will never fall into a pattern (because pad is longer than message)
 Frequency distribution is uniform (because shifts are random)
 One-Time Pads are known as being “Perfectly Secure” as defined by Claude Shannon in 1949
(Shannon, C. (1949) Communication Theory of Secrecy Systems. Bell System Technical Journal 28)
https://netlab.cs.ucla.edu/wiki/files/shannon1949.pdf
 Principle is that if the key is perfectly random, the potential number of encrypted messages is the same as
the number of potential keys and the number of messages
 However, pseudo-random keys will result in a repeating pattern of keys and so a smaller subset of
encrypted messages
 One-Time Pads
 Practical limitations
 You need to have a large number of random keys
 You need to distribute these keys to the senders and receivers
 You need to protect them from discovery
 Key distribution and protection a general problem even with modern systems
 Public Key Infrastructure (PKI) as we will see later
 The Enigma Machine
 Invented by the German army at the end of WW1 and further developed
during WW2
 Consists of a plug board that switches letters AF, GK, LM and a set of
3 (or more) rotors chosen from a larger set) with 26 positions on each rotor.
 Start by sharing
 Plug board settings
 Set of rotors
 Ring settings
 Initial position
 Each time a character is typed, the rotor turns and the characters on each
rotor are added together to form the substitution
 Check out emulator https://www.101computing.net/enigma-machine-
emulator/
 Transposition
 In transposition, we change the order of characters in the ciphertext without making substitution
 One method:
 Take the message “nowrunalonganddontgetintomischiefimgoingout”
 We pad it with 4 xxxx and arrange as a grid:

nowrunalonga
nddontgetint
omischiefiam
goingoutxxxx

 We can now take the columns to create the ciphertext

 nnog odmo wdii rosh uncg ntho agiu leet otfx niix gnax atmx
 Confusion and Diffusion
 Claude Shannon (1945) A Mathematical Theory of Cryptography
 Confusion
 Each part of the ciphertext depends on several parts of the key
 Hides the relationship between ciphertext and key
 Diffusion
 Change in plain text will result in larger changes in ciphertext
 Hide the relationship between the ciphertext and plaintext
 We can achieve confusion/diffusion using a combination of substitution/transposition
(permutation) and we will see how this is used in modern ciphers.
 Computers and Ciphers
 Text in computers are represented as ASCII (or Unicode) code
 Letter ‘a’ is 97 in decimal, 61 in hexadecimal and 1100001 in binary
 When we encrypt text on a computer we can take the key’s binary and then do logical
operation (AND, OR, XOR) using the key on the plaintext
AND OR XOR

p k c p k c p k c
1 1 1 1 1 1 1 1 0
1 0 0 1 0 1 1 0 1
0 1 0 0 1 1 0 1 1
0 0 0 0 0 0 0 0 0
 Computers and Ciphers
 To encrypt the letter ‘a’ with the letter ‘t’ we could do an ‘AND’, ‘OR’ or ‘XOR’
operation
 1100001 AND 1110100 = 1100000 (hex 60 or “`”)
 1100001 OR 1110100 = 1110101 (hex 75 or “u”)
 1100001 XOR 1110100 = 0010101 (hex 15 or non-printable character)
 Why we use XOR
 Using a one-time pad to encrypt on a computer is best done using an XOR operation.
 To see why: take an image which is represented by bits. Take a string of random bits
and do an AND, OR and XOR
Original AND OR XOR

Images courtesy of https://www.biography.com/scientist/alan-turing encryption by Alex Brownhttps://github.com/Ccamm/Basic-Image-Encryptor

 Why we use XOR
 If we look at outcomes for AND, OR and XOR of 2 binary bits, OR and AND have a
higher chance of leaving things unchanged in the cipher text

AND P(p) = 0.75 OR P(p) = 0.75 XOR P(p) = 0.5

p k c p k c p k c
1 1 1 1 1 1 1 1 0
1 0 0 1 0 1 1 0 1
0 1 0 0 1 1 0 1 1
0 0 0 0 0 0 0 0 0
 Cryptography Today
 Two types of encryption used:
 Symmetric key cryptography: Both parties share the same single key
 Asymmetric key cryptography: Each party has 2 keys: public key and private key
 Both types or encryption are used for different purposes and have different benefits
and drawbacks
 In addition to the above, there are other cryptographic functions that do not require a
key e.g. Hash functions
 Symmetric Key Cryptography
 Modern (digital) ciphers arose with the need for encryption in digital systems
 Of two types: Block and Stream which differ in how the plaintext is handled
 Block ciphers take chunks of the plaintext and manipulates them to encrypt
 Stream ciphers encrypts data as a stream of bytes
 Data Encryption Standard (DES) becomes first US national standard algorithm in 1976
 Invented by IBM and originally called Lucifer which was based on Feistel cipher
 Mired in some controversy because of the involvement of the US National Security
Agency (NSA) in the design and decision about the key length
 DES
 Block length is 64 bits
 Key length is 56 bits (64 bits with 8 bits as parity)
 The process for encryption involves:
 Key schedule
 Subkeys are generated from the key for 16 rounds of application to the plaintext
 Permutations (diffusion) by initial expansion through duplication and mixing outputs at the end of
each round
 Substitutions: using S-boxes which are lookup tables that take 6 input bits and output 4 output
bits
 Not overly important to know the details
 DES (and other block ciphers) Modes
 The previous description details how a single block of plaintext is encrypted but what about a
sequence of blocks?
 Some take an Initialisation Vector (IV) which is a
 Different modes of encrypting a sequence of blocks:
 ECB (Electronic Codebook): Each block is encrypted independently
 CBC (Cipher Block Chaining) Each encrypted block is XOR’d with the next block. Start with the IV
 CFB (Cipher Feedback) Same mechanism as CBC but operates as a stream of real time data
 OFB (Output Feedback) Same as CFB but uses the IV and encrypted versions of the IV as input to
successive blocks
 CTR (Counter) Same as OFB but uses a simple counter to alter seed input to each encryption
ECB Mode
 ECB (Electronic Codebook):
Each block is encrypted
independently
CBC Mode
 CBC (Cipher Block
Chaining) Each encrypted
block is XOR’d with the next
block. Start with the IV
CFB Mode
 CFB (Cipher Feedback)
Same mechanism as CBC
but operates as a stream of
real time data
OFB Mode
 OFB (Output Feedback)
Same as CFB but uses the IV
and encrypted versions of the
IV as input to successive
blocks
CTR Mode
 CTR (Counter) Same as
OFB but uses a simple
counter to alter seed input to
each encryption
 Pros and Cons of Modes
 ECB leaks information ECB Tux Penguin. This is because the same plaintext block
will generate the same ciphertext

ECB penguin Filippo Valsorda (https://blog.filippo.io/the-ecb-penguin/) Original image Wikipedia

https://commons.wikimedia.org/wiki/File:Tux.jpg
 Pros and Cons of Modes
 CBC and CFB mode propagates errors and this will corrupt attempts to decrypt
 OFB does not propagate errors in blocks
 ECB and CTR can be parallelized and so are fast
 DES is broken
 The DES key length became a liability and DES was cracked by brute force in 1997
 Brute forcing by going through all possible keys takes at most 2 56 attempts
 Using a Nvidia 3090 GPU you could to this in about 166 days
 You can parallelise it with more GPUs and do it faster
 1997: DESCHALL Project (parallel computing) -> 96 days
 1998: EFF’s DES cracker -> 56 hours
 2006 COPACOBANA FPGA hardware – around 6.4 days
 2017: chosen-plaintext attack with rainbow table of all 2 56 ciphertext -> 25 seconds!
 Just using a large GPU machine on AWS and hashcat would do DES in about a day.
 3DES and AES
 The solution to DES was to do it 3 times in a row and this became 3DES (Triple DES)
 Don’t do 2DES (Double DES) because it is vulnerable to a meet-in-the-middle attack
 Won’t go through details but it makes it not much better than DES
 Variants of 3DES depending on number of keys used and whether you use 3 encryptions
(EEE) or encryption, decryption, encryption (EDE)
 In the meantime, Advanced Encryption Standard adopted by US NIST in 2000. Based on the
Rijndael scheme.
 128 bit block length
 Keys of
 128 bits with 10 rounds of encryption
 192 bits with 12 rounds of encryption
 256 bits with 14 rounds of encryption
 Public Key Cryptography
 1874 William Stanley Jevons wrote in The Principles of Science:
“Can the reader say what two numbers multiplied together will produce the number
8616460799? I think it unlikely that anyone but myself will ever know.”
 Illustrates a principle that factorisation is hard but the factors are 89681, 96079
 In 1977, MIT researchers Ron Rivest, Adi Shamir and Leonard Adleman came up
with RSA
 Key Generation: Create a public and private key. Public key is shared, private key is
kept secret
 Encryption: Encrypt a message to someone with their public key
 Decryption: Decrypt a message with the private key
 Public Key Cryptography
Alice Bob
Bob’s Public Key Bob’s Private Key

Encryption Decryption

Plaintext Ciphertext Plaintext

 Non-Repudiation
 To prove that Alice was the one that sent the message
 Alice encrypts the document with her private key and Bob decrypts it with Alice’s
public key
 It must be Alice because only she would have her private key
 This also authenticates Alice
 In practice, we don’t need to encrypt the entire document but can do a hash of the
document
 Non-Repudiation
Alice Alice’s Private Key Alice’s Public Key Bob

Encryption Decryption

Plaintext Ciphertext Plaintext

 Confidentiality and Authentication
 Combine the two processes
1. Alice encrypts the document with her private key
2. Alice then encrypts again with Bob’s public key
3. Bob decrypts the document with Bob’s private key
4. Bob decrypts the document with Alice’s public key
 Asymmetric Cryptography: Public Key
Distribution
 Distributing public keys is much easier than sharing private keys amongst people
 However, still have an issue about verifying that a public key belongs to the person it says
 Decentralised models: PGP, OpenPGP
 Centralised models: Estonian ID-Card
 PGP (Pretty Good Privacy) Phil Zimmerman 1991
 Uses variety of symmetric and public key ciphers
 Uses Web of Trust
 Estonian model needs proof of identification (passport, driving license, etc) also can only
be collected in person
 Web Of Trust
 Relies on validation through a
network of people you trust
 Ideally however this is verified in
person
 Can have indirect trust if someone
you trust, directly trusts another
person
 In practice this simply doesn’t work
 It can be manipulated
 It is too hard to do the due diligence
 A version of this can be used with
trusted third parties (but that isn’t
peer-to-peer)
 Public Key Infrastructure
 Trusted 3rd party or internal system that certifies through a certificate that a public
key belongs to an individual
 Known as the Certificate Authority (CA)
 CA delegates authority to identity verification to a Registration Authority (RA)
 Certificates held in database and can be checked for validity
 Certificate policy: specifies architecture, what certificates can be used for, security controls,
etc.
 We will cover certificates in detail later
 Cryptographic Hash Functions
 Algorithm that maps data of arbitrary size to a bit string of a fixed size
 Designed to operate only one way (can’t be inverted)
 Properties:
 deterministic - the same message results in the same hash
 fast to compute
 very difficult to generate a message from its hash
 small changes to message result in large changes to hash
 two different messages are very unlikely to generate the same hash
 MD5 was invented by Ron Rivest in 1992 and very common but proved flawed
 SHA-2 recommended now although it comes from the NSA – can output various sizes of hash (224, 256, 384 and 512
bits)
 SHA-3 released by NIST in 2015
 Hash Functions: Password storage
 Used for password storage and verification
 Password + Salt (random bytes) is hashed and the hash stored for verification
 Never store the plaintext
 Linux stores passwords in a file called shadow:
 openssl passwd -6 -salt randomtext mysecretpassword
 $6$randomtext$SqJRpIQLI4zewKY2NPupGyKBZpzND3yl7sbqi1qachbATjFBafjHeQqfzvAeSS2
FKb7WuJWV/SSCWD/lba7G//
 In practice, Linux will do the hash 5000 times in an attempt to stop brute forcing passwords
 Hashing functions
 Message Authentication Codes (MAC): message is combined with key and hashed
 confirms that a message has not been changed
 provides data integrity and authenticity
 Digital signature
 proposed by Diffie and Hellman in 1976
 Digital Signature Algorithm (DSA) part of NIST’s Digital Signature Standard (DSS)
 Message is hashed and then processed using the private key to produce a signature
 Checking the signature involves taking the hash of the message and the signature and using the
public key to verify the signature.
 https://oag.ca.gov/sites/all/files/agweb/pdfs/erds1/fips_pub_07_2013.pdf
 Key Exchange
 Public key cryptography is slow and so is still not used for real-time encryption of
communications
 Merkle, Diffie and Hellman published papers in 1976/7 on a method of exchanging
public keys securely (known as the Diffie-Hellman Key Exchange
 Once the keys are exchanged, a secret key can be generated and shared to do
symmetric encryption.
 We will see later that this is the basis for TLS which gives the web secure
communication through HTTPS.
 Key Exchange Walkthrough
1. Alice chooses 2 prime numbers g and p and tells Bob what they are.
2. Bob picks a secret number (a), and computes ga mod p and sends that result (A) back
to Alice
3. Alice picks a secret number (b), and computes gb mod p and sends that result (B) back
to Bob
4. Bob takes B and does same operation with it. Ba mod p.
5. Alice takes A and does the same operation with it. Ab mod p.
 The numbers resulting from 4 and 5 are the same!
 This session key can be used to encrypt private key
Worked Example
 Diffie Hellman Vulnerability
 Diffie-Hellman is vulnerable to a man in the middle attack (MITM)
 An attacker simply inserts themselves into the communication and acts as a proxy
 It is vulnerable because there is no authentication of the parties
 Can be mitigated by using signatures as proof of identity
 Summary
 We have covered the fundamentals of cryptography that consist of using a key and
cipher to apply confusion and diffusion to plaintext to generate ciphertext
 We looked at examples of modern cryptography and how this has developed to create
fast and efficient ciphers
 We looked at the way key management could be handled in he case of both symmetric
and asymmetric cryptography