2. Cryptography 1 – Encryption Decryption
Cryptography 1:
Encryption Decryption
Alvaro Monsalve
alvaro. .au
CITS3004
1
1. Cryptology Concepts
2. Classical Ciphers
3. Product Ciphers with Symmetric Key
4. Encryption Modes (Algorithms)
5. Cryptanalysis
Sections
2
Cryptology is the study of cryptographic techniques
and analysis of systems
3
1. Cryptology
Cryptology
Cryptography
Private-key
Cryptography
Public-key
Cryptography
Protocols
Cryptanalysis
Source: Prof. Baktier’s lecture at WPI
Cryptography
– To keep information safe from adversaries
Cryptanalysis
– Understanding the mechanisms of cryptography
4
Cryptology
We will look at ciphers of cryptography
5
Cryptography
Cryptology
Cryptography
Private-key
Cryptography
Public-key
Cryptography
Protocols
Cryptanalysis
Plaintext (P)
– Original message – “this is a secret message”
Ciphertext (C)
– Encrypted message – “dlgc mq k wcmvcd qccwyqi”
Cipher (algorithms)
– Algorithm or set of instructions for converting plaintext to ciphertext, and vice versa. – Caesar,
Vigenere, DES, AES, TWOFISH etc.
Key(s) (K)
– Secret information to correctly operate the ciphers
– Can be the same for encryption/decryption (symmetric), or different ones (asymmetric).
Encrypt E(P)
– Converting the plaintext into a ciphertext
Decrypt D(C)
– Recovering the plaintext from a ciphertext
6
Basic Terminologies
Using Vigenere cipher with key “key” from https://planetcalc.com/2468/
7
Basic Terminology
Sender Receiver
Encryption
algorithm
Decryption
algorithm
plaintext ciphertext plaintext
symmetric key cipher
Bob’s public key Bob’s private key
fdafieoa
jfvhlfjea
asymmetric key cipher
AES, DES etc…
RSA etc…
• The principle of ciphers is to use both substitution
and transposition
– Proved by C.E. Shannon
– Using information theory in 1945
• Formulate the principles of “ ” and
“ ”.
8
Principle of Ciphers
confusion
diffusion
• Confusion
– Through transposition/permutation
– Changing the plaintext order
• Diffusion
– Through substitution
– Replacing plaintext with ciphertext
9
Principle of Ciphers
• Transposition (permutation)
– Plaintext: This is some secret message
– Ciphertext: hTsi si osem esrcte emssgae
• Substitution
– Plaintext: This is some secret message
– Ciphertext: Xduq uq qzvl qlrklx vlqqmyl
10
Principle of Ciphers
1. Classical Encryption techniques
• Caesar cipher
• Mono alphabetic cipher
• Vigenere cipher
• Transposition cipher
2. Modern ciphers
• Product ciphers
• DES, AES etc.
11
2. Ciphers
• Typically uses either substitution or transposition
only.
• Substitution ciphers further divide into
monoalphabetic and polyalphabetic
12
Classical Ciphers
• Earliest known substitution cipher
• By Julius Caesar
• Replace each letter by the ith letter
13
Caesar Cipher
Key = i
• Given the secret message:
– P : hello world!
– K : 10
– i.e., ‘a’ becomes ‘k’
• What is the ciphertext using Caesar cipher?
• How to decrypt?
14
Caesar Cipher
A: rovvy gybvn
C = E(P) = P + K mod 26
P = D(C) = C – K mod 26
• Modular operations example
• If 6 hours pass, what time is it?
• 13? No (not on this clock)
• 7 + 6 mod 12 ≡ 1
15
Caesar Cipher
• New Clock: Caesar clock
– Modulus 26 using English
16
Caesar Cipher
A B C D … Y Z
0 1 2 3 … 24 25
We will cover more mod operations later in RSA next week
• Cipher is known (i.e., Caesar cipher)
• Key is unknown
• Task: Retrieve the plaintext
• Found the plaintext? You just did a brute-force attack!
17
Class exercise
C: uijt jt b tfdsfu
Q: How long will it take to brute-force?
P: This is a secret
• Why is it so weak?
– A: The key size is too small (25)
• What can we do to improve this?
– A: use a mono alphabetic cipher that uses an arbitrary
substitution
18
Caesar Cipher
Shuffling the letters in the plaintext by
mapping them to a different random
ciphertext letter
• Setup a secret key phrase (or a word)
– Secret key: MARKET
• The rest alphabet letters follows the last character
– E.g., T is the last letter in our secret key
• Remaining alphabets appended at the end in order
– Excluding ones already used in the secret key
19
Mono Alphabetic Cipher
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
M A R K E T U V W X Y Z B C D F G H I J L N O P Q S
20
Mono Alphabetic Cipher
What are some commonly
used letters?
21
Mono Alphabetic Cipher
• Here is an example.
• Frequency computation result
SLAAP UNAOL NVVKZ ABMMP UDOPS LRLLW PUNAO LIHKZ ABMMV BAPZA
OLJYP APJHS WYVIS LTAOH AHUFJ VTWBA LYMPY LDHSS ULLKZ AVZVS
CLPAO HZAVH JAHZN HALRL LWLYP AOHZA VMPNB YLVBA DOPJO IPAZH
YLOHY TMBSH UKKLU FAOLT LUAYF PAOHZ AVKVA OPZDP AOVBA BUYLH
ZVUHI SFKLS HFPUN AYHMM PJ
A: 29 B: 9 C: 1 D: 4 E: 0 F: 5 G: 0 H: 18 I: 4 J: 6 K: 7 L: 24 M: 9 N: 6
O: 14 P: 18 Q: 0 R: 2 S: 10 T: 4 U: 11 V: 14 W: 4 X: 0 Y: 11 Z: 12
22
Vigenere Cipher
• Mono alphabetic cipher fails to hide the frequency
information.
• To address this issue, we use a series of different
Caesar ciphers.
• This is called polyalphabetic cipher
• A popular example is the Vigenere Cipher
(Vee-gee-nee-er)
23
P: WE HACK AT NOON
K: PAID
C: LE PDRK IW COWQ
Polygram substitution
To do: Encrypt the message.
24
Vigenere Cipher
• How to break?! Cannot perform frequency analysis anymore
• Kasiski Examination (1863): There is a chance that a repeated
word is encrypted using the same sequence of the key
• There are more substitution ciphers.
C R Y P T O I S S H O R T F O R C R Y P T O G R
A B C D A B C D A B C D A B C D A B C D A B C D
C S A S T P K V S I Q U T G Q U C S A S T P I U
P
K
C
25
Transposition Cipher
• The aim is to hide the message by rearranging the
letters without altering the original letters
• These ciphers are prone to frequency analysis attacks
• For example: Rail fence cipher (or zigzag cipher)
26
Rail Fence Cipher
• Arrange the plaintext in N dimensions in a zigzag
style
• Recollect the letters in straight lines to formulate the
ciphertext
– E.g., 2 dimension (N = 2)
– P: THE ANSWER IS ELEVEN
– C: TENWRSLVNHASEIEEE
– You can do it multiple rounds!
T E N W R S L V N
H A S E I E E E
• Classical ciphers are not so secure
today due to the limited key size
and also language characteristics
• To improve the security of ciphers,
both substitution and transposition
techniques are used together
27
Classical Ciphers summary
substitution &
transposition
• Which one is more secure?
– Substitution twice
– Transposition twice
– Substitution and then transposition
28
3. Modern Ciphers
In General, we call these product ciphers
29
Classification of
Encryption algorithms
Encryption algorithms
Symmetric key
Block
Feistel SPN etc
Stream
random Pseudo-random
Asymmetric key
Later…
DES AES
64 bits, 128 bits etc 1 bit (or byte)
30
Stream Cipher
Pseudo-random
sequence generation
Plaintext
bitstream
Ciphertext
bitstream
Key
Operation (e.g., XOR)
Plaintext bitstream 111111110000……
Pseudo-random stream 100101110100……
Ciphertext stream 011010000100……
Plaintext
31
Block Cipher
Block
cipher
K bits Key
n bit
ciphertext
n bits n bits n bits n bits x bits padding
n bits
Block ciphers have different operation modes:
ECB, CBC, OFB, CFB, CTR (coming soon)
Stream Block
Pros.
• Speed of transformation
• Low error propagation
• High diffusion
• Immunity to insertion of symbols
Cons.
• Low diffusion
• Susceptible to malicious insertion
and modification
• Slow
• Error propagation
32
Stream vs Block
SecurityPerformance
• DES – Data Encryption Standard
• Block cipher
• 64bits plaintext
• 64 bits key (56 bits key + 8 bits parity)
• 64 bits ciphertext
33
DES
• 16 rounds
• S and P boxes each
round
34
DES
For more details, see additional items.
• 56 bit key is too short(!)
• We can brute force it with today’s computers
– Takes roughly 256 trials.
– Typical CPU today would still take 100+ years
– But we can also parallelise the process, as well as exploit the algorithms
• 1997: DESCHALL Project (parallel computing) -> 96 days
• 1998: EFF’s DES cracker -> 56 hours
• 1999: DES cracker + distributed.net -> 22 hours
• 2017: chosen-plaintext attack with rainbow table* -> 25 seconds!
35
DES: Security concern
*A rainbow table is a listing of all possible plaintext permutations of encrypted passwords specific to a given hash algorithm.
• To overcome this problem, NIST published Advanced
Encryption Standard (AES) in 2001
– The AES competition included RC6, Serpent, MARS, and Twofish
• But we built software and hardware for DES
• Let us not waste it
– Solution: lets use DES multiple times!
36
DES: Security concern
But how many times?
• 2-DES: C = EK2(EK1(P))
• So, X = EK1(P) = DK2(C)
• Given a known pair (P, C), attack as follows:
– Encrypt P with all 256 possible keys for K1
– Decrypt C with all 256 possible keys for K2
– If EK1’(P) = DK2’(C), try the keys on another (P*, C*)
– If works, it is highly likely that (K1’, K2’) = (K1, K2)
37
DES Twice!
Q:How much did it improve from 1-DES?
• Let us triple the DES:
• In practice, C = EK3(DK2(EK1(P))) (a.k.a. EDE encryption)
• How many keys do we need?
38
Triple DES
2 (or 3)
K3 = K1 would result in a totally different C
(i.e., works with only 2 keys)
If K1 = K2 = K3, then it is equivalent to 1-DES.
This means Triple DES can be used as 1-DES as well.
• We can use meet-in-the-middle attack on 3DES
– Requires known pair of (A, C)
1. Encrypt P, producing value A
2. Using A and C, attack 2DES (i.e., slide 37)
• This attack takes (256 x 256) = O(2112) steps
39
Triple DES: Lets attack it
E
E
D
P
C
K1
K2
K1
A
B
Assuming a 64 bit key, you would require 100 million
computers with 1.6TB hard drive to carry this out
• Triple DES has been implemented into some internet
applications
– Such as PGP (pretty good privacy) and S/MIME
(Secure/Multipurpose Internet Mail Extensions)
• But! Triple DES is too slow
• Let us have a look at its successor – AES
40
Triple DES downfall
• Advanced Encryption Standard
• Block length of 128 bits (fixed)
• Key size varies 128, 192 or 256 bits
• Number of rounds are 10, 12 and 14 respectively to
the key size.
41
AES: ADVANCED
ENCRYPTION STANDARD
42
AES
• Four functions are used each round
– ByteSub (nonlinear layer)
– ShiftRow (linear mixing layer)
– MixColumn (nonlinear layer)
– AddRoundKey (key addition layer)
• Currently no practical exploits
– 2126 operations needed to break 128 bits key size AES (2015)
– Other approach includes side channel attacks (covered later)
43
AES
Animation (YouTube video) in the additional items
• DES, Triple DES, AES <- all block ciphers. • Need some way to encrypt/decrypt arbitrary amounts of data in practice • 5 common modes are defined for AES and DES – ECB: Electronic Code Book – CBC: Cipher Block Chaining – CFB: Cipher Feed Back – OFB: Output Feed Back – CTR: Counter 44 4. Encryption Modes • Message is broken into independent blocks • Each block is encrypted independently • If two same messages are encrypted using the same key and sent, their ciphertexts are the same – E.g., Sending your personal information. • Should only be used to transmit single values. 45 ECB: Electronic Code Book 46 ECB Encrypt P1 C1 K Encrypt P2 C2 K Encrypt Pn Cn K… Decrypt C1 P1 K Decrypt C2 P2 K Decrypt Cn Pn K… • Can be parallelised but… • Due to the design, message repetitions may show in the ciphertext – Particularly with data such as graphics – Messages that change very little etc. • The independence between the encrypted messages is the problem 47 ECB 48 ECB Original ECB • Removes the independence between message blocks – By linking the encryption operations – i.e., next ciphertext depends on the previous ciphertext • Establish an Initial Vector (IV) to start the process • Can be used for general transmission of block ciphers – E.g., IPSec using 3DES-CBC, AES-CBC 49 CBC: Cipher Block Chaining 50 CBC … … Encrypt P1 C1 K IV Encrypt P2 C2 K Encrypt Pn Cn K Decrypt C1 P1 K IV Decrypt C2 P2 K Decrypt Cn Pn K • A ciphertext block depends on all the previous blocks – i.e., no repetitions of the same plaintext • Requires the Initialisation Vector (IV) – Must be known to both sender and receiver – Can be a fixed value (with an integrity guarantee), or – Sent encrypted (e.g., using the ECB mode) • Error propagation problem 51 CBC 52 CBC Decrypt C1 P1 K IV Decrypt C2 P2 K Decrypt C3 P3 K Decrypt C4 P4 K Broken Affected 53 ECB vs CBC Original ECB CBC • To use the cipher block of the previous step as the input of the cipher in the next step • Divide the plaintext into segments of length s bits – S ≤ block size • Encryption is used to generate a sequence of keys of length s bits • The ciphertext is produced by XOR operation of the plaintext and the key 54 CFB: Cipher Feed Back 55 CFB … Encrypt C1 P1 Decrypt IV P1 K C1 Decrypt C2 P2 K … Decrypt Cn Pn K Encrypt C2 P2 Encrypt Cm Pn K IV K K • The block cipher is used as a stream cipher • Used in scenarios where data arrives in bits/bytes – Common value for s is 8 bits – The bit can be as small as 1, denoted as CFB-[bit size] • Similarly with CBC, the ciphertext depends on the all previous plaintext 56 CFB 57 CBC vs CFB Encrypt P1 C1 K CBC Encrypt C1 P1 CFB CBC performs XOR first with the plaintext before encryption CFB performs XOR with the plaintext after encryption K • Message is treated as stream of bits • Output of the cipher is added to the message • Output is used for the next cipher step (feed back) • Feedback is independent of message – i.e., can be computed in advance • Can be used to encrypt stream of messages on a noisy channel – E.g., satellite TV transmission etc 58 OFB: Output Feed Back 59 OFB …DecryptIV P1 K C1 Decrypt C2 P2 K … Decrypt Cn Pn K Encrypt C1 P1 Encrypt C2 P2 Encrypt Cn Pn IV K KK • No bit error propagation • More vulnerable to message stream modification • Should never reuse the same sequence of key and IV – Because it generates the same ciphertext! • Requires synchronisation between the sender and the receiver – But this is more related to computer networks – see CITS3002 60 OFB OFB is a variation of a Vernam cipher, which XOR the plaintext with a random stream of data of the same length • Relatively new compared to other four • Similar to OFB but encrypts the counter value instead of the feedback value • Requires different keys and counter values for every plaintext block • Used in high-speed network encryptions 61 CTR: Counter 62 CTR …DecryptNonce + Counter (1) P1 K C1 Encrypt Nonce + Counter (1) C1 P1 K Encrypt Nonce + Counter (2) C2 P2 K Encrypt Nonce + Counter (n) Cn Pn K… Decrypt Nonce + Counter (2) P2 K C2 Decrypt Nonce + Counter (n) Pn K Cn 63 OFB vs CTR Encrypt C1 P1 Encrypt Nonce + Counter (1) C1 P1 K IV is replaced with Nonce and counter combination No more feedback operations in CTR OFB CTR IV K • A counter is initialised in addition to a nonce • The counter is incremented by 1 for each block • For example, 128 bits (16 bytes) 64 CTR Initial 24 49 E3 7A 83 1B 74 9A 00 00 00 00 00 00 00 01 Counter 2 24 49 E3 7A 83 1B 74 9A 00 00 00 00 00 00 00 02 Counter 3 24 49 E3 7A 83 1B 74 9A 00 00 00 00 00 00 00 03 Counter 4 24 49 E3 7A 83 1B 74 9A 00 00 00 00 00 00 00 04 Nonce Counter • Fast encryption decryption – E.g., parallel computation • Random access to encrypted data blocks – i.e., no feedback • Provable security (as good as other modes) 65 CTR • ECB – Electronic Code Book • CBC – Cipher Block Chaining • CFB – Cipher Feed Back • OFB – Output Feed Back • CTR – Counter 66 Block Cipher Modes summary Don’t use Most popular Fast Use CTR instead • Cryptology is the study of cryptographic techniques and the analysis. 67 Cryptology Cryptology Cryptography Private-key Cryptography Public-key Cryptography Protocols Cryptanalysis Source: Prof. Baktier’s lecture at WPI • Objective to recover key not just message • General approaches – Brute force attack – Cryptanalytic attack 68 5. Cryptanalysis • To try every possible way • Simple to develop the procedure • Success rate proportional to the key size • Assume known or recognised plaintext 69 Brute Force attack Key size (bits) No. of keys 1 decryption/µs 106 decryptions/µs 32 232 = 4.3 x 109 35 minutes 2 ms 56 256 = 7.2 x 1016 1142 years 10 hours 128 2128 = 3.4 x 1038 5.4 x 1024 years 5.4 x 1018 years 168 2168 = 3.7 x 1050 5.9 x 1036 years 5.9 x 1030 years 26 characters 26! = 4 x 1026 6.4 x 1012 years 6.4 x 106 years AMD Ryzen Threadripper 3990X : 2,356,230 IPS/µs at 4.35 GHz But, 1 decryption > 1 instruction
https://en.wikipedia.org/wiki/Ryzen
• Ciphertext only
– Only knows the algorithm and ciphertext
• Known plaintext
– Knows the plaintext & ciphertext
• Chosen plaintext
– Select plaintext and obtain ciphertext
• Chosen ciphertext
– Select ciphertext and obtain plaintext
• Chosen text (combination of the above two)
– Select plaintext or ciphertext to encrypt/decrypt
70
Cryptanalytic Attacks
Known to attacker C1, C2, …, Cn
Objective
1) P1, P2, …, Pn
2) Key K
3) Algorithm Cn+1 -> Pn+1
71
Cryptanalytic Attacks
Ciphertexts
generated using the
same key
Find an algorithm that can
decrypt any message
encrypted using the key K
• Ciphertext only
• Known plaintext
72
Cryptanalytic Attacks
Known to attacker (P1, C1), (P2, C2), …, (Pn, Cn),
Objective
1) Key K
2) Algorithm Cn+1 -> Pn+1
Attacker cannot
select these pairs
• Chosen plaintext
73
Cryptanalytic Attacks
Known to attacker (P1, C1), (P2, C2), …, (Pn, Cn),
Objective
1) Key K
2) Algorithm Cn+1 -> Pn+1
Attacker can select
the plaintext before
attack begins, and
cannot gain
additional pair after
the attack started.
• Chosen ciphertext
74
Cryptanalytic Attacks
Known to attacker (P1, C1), (P2, C2), …, (Pn, Cn),
Objective
1) Key K
2) Algorithm Cn+1 -> Pn+1
Attackers can select
ciphertexts before
the attack begins
This attack exploits public key algorithm, as attackers can
generate ciphertexts using the public key
• Total break
– Found the key
• Global deduction
– Did not find the key, but found the algorithm
• Instance deduction
– Obtained some plaintexts from some ciphertexts
• Information deduction
– Obtained partial bits of plaintext
75
Result of attacks
• Computationally secure
– Cost to break is higher than cost to encrypt
– Time taken exceeds the useful lifetime
• Probably secure
– The security mechanism can be proven to be equivalent to a hard
problem
• Unconditional security
– The attacker cannot succeed in cryptanalysing the algorithm given an
infinite amount of resources
76
Secureness of ciphers
• We covered various classical ciphers
– Caesar, mono alphabetic, Vigenere and Rail Fence
• We covered modern ciphers
– DES, Triple DES and AES
• Details of block cipher modes
• Cryptanalysis overview
77
Summary
• Cryptography 2: RSA and DH
– Plus hashing and Blockchain
78
Next Week
1. https://en.wikipedia.org/wiki/Instructions_per_secon
2. DES details
– https://www.tutorialspoint.com/cryptography/data_encryption_standard.
htm
3. AES encryption animation (mind the music)
– https://www.youtube.com/watch?v=evjFwDRTmV0
4. Block Cipher Modes
– http://www.crypto-it.net/eng/theory/modes-of-block-ciphers.html
5. Image From:
– https://pixabay.com/photos/bitcoin-mining-processor-3369039/
79
References
https://en.wikipedia.org/wiki/Instructions_per_secon
https://www.tutorialspoint.com/cryptography/data_encryption_standard.htm
http://www.crypto-it.net/eng/theory/modes-of-block-ciphers.html
https://pixabay.com/photos/bitcoin-mining-processor-3369039/