TELE3119: TRUSTED NETWORKS WEEK 1 Never Never Stand Stand Still Still Faculty Faculty of of Engineering Engineering School School of of Electrical Electrical Engineering Engineering and and Telecommunications Telecommunications Course Coordinator: Prof. Aruna Seneviratne, Room EE 312 E-mail [email protected]

Course web-page: https://subjects.ee.unsw.edu.au/tele3119/ 2 Cyber Security Many things to many people Confidentiality, integrity and availability Confidentiality: Prevent sensitive information from reaching the wrong people, while making sure that the right people get it Encryption, authentication,. Integrity: maintaining the consistency, accuracy, and trustworthiness of data over its entire life cycle Access control, checksums, hashing,.. Availability: ensuring access to data Guaranteeing adequate communication bandwidth Guaranteeing access to the host School of Electrical Engineering & Telecommunications Trusted Networks

3 Cyber-Attacks per-month Source: http://www.hackmageddon.com/ School of Electrical Engineering & Telecommunications Trusted Networks 3 4 Cybercrime top-10 techniques School of Electrical Engineering & Telecommunications Trusted Networks 4 5

Most Common School of Electrical Engineering & Telecommunications Trusted Networks 6 Cost of Cybercrime School of Electrical Engineering & Telecommunications Trusted Networks 6 7 Cost of Cybercrime in Australia School of Electrical Engineering & Telecommunications Trusted Networks

7 8 Australia https://www.acorn.gov.au/ School of Electrical Engineering & Telecommunications Trusted Networks 9 Course Overview Objectives Understand principles, protocols and tools, and applications Three Parts: Security Fundamentals Private/public-key crypto, digital signatures, Network Security Network Security Protocols VPN, SSL, PGP, ToR,

Network Security Apliances IDS, Firewalls Applications Bit Coin School of Electrical Engineering & Telecommunications Trusted Networks 9 10 10 Course logistics Lectures & tutorials Background knowledge Textbooks and resources Labs and project Assessment: Quizzes: 2 x 15% = 30% Labs: 5% + 10% + 15% = 30%

Final exam: 40% Pass in the Final Exam is a mandatory School of Electrical Engineering & Telecommunications Trusted Networks 11 What is network security? confidentiality: only sender, intended receiver should understand message contents sender encrypts message receiver decrypts message authentication: sender, receiver want to confirm identity of each other message integrity: sender, receiver want to ensure message not altered (in transit, or afterwards) without detection access and availability: services must be accessible and available to users School of Electrical Engineering & Telecommunications

Trusted Networks 12 12 Security Glossary: Some Definitions Vulnerability: An error or weakness in the design, implementation, or operation of a system Technical failing in a system Attack: Exploit a vulnerability in a system a deliberate attempt to violate the security of a system Threat: A potential for violation of security a possible danger that might exploit a vulnerability School of Electrical Engineering & Telecommunications Trusted Networks 13 Friends and enemies: Alice, Bob, Trudy well-known in network security world

Bob, Alice (lovers!) want to communicate securely Trudy (intruder) may intercept, delete, add messages channel data, control data Bob messages Alice secure sender secure receiver s Trudy

School of Electrical Engineering & Telecommunications Trusted Networks data 14 14 Who might Bob, Alice be? well, real-life Bobs and Alices! Web browser/server for electronic transactions (e.g., on-line purchases) on-line banking client/server DNS servers routers exchanging routing table updates other examples? School of Electrical Engineering & Telecommunications Trusted Networks

15 15 There are bad guys (and girls) out there! Q: What can a bad guy do? A: A lot! eavesdrop: intercept messages actively insert messages into connection impersonation: can fake (spoof) source address in packet (or any field in packet) hijacking: take over ongoing connection by removing sender or receiver, inserting himself in place denial of service: prevent service from being used by others (e.g., by overloading resources) School of Electrical Engineering & Telecommunications Trusted Networks 16 16 Threats

Joy hackers: Many are script kiddies, some are very competent The hackers share tools more than the good guys do. Profit hackers: Money is the primary motivation Less pure vandalism Viruses are designed to turn victim computers into bots In many cases, hacking is just another venue for ordinary criminal activity Insiders: What if your system administrator turns to the Dark Side? Are on the inside of your firewalls! Often know the weak points Spies: governments may want your technology School of Electrical Engineering & Telecommunications Trusted Networks 17 What is a Cryptosystem? KA

plaintext Alices encryption key encryption algorithm KB ciphertext Bobs decryption key decryption plaintext algorithm m plaintext message KA(m) ciphertext, encrypted with key KA m = KB(KA(m)) School of Electrical Engineering & Telecommunications

Trusted Networks 18 Basic View of Cryptography Cryptography Symmetric Stream Ciphers Asymmetric Protocols Block Ciphers School of Electrical Engineering & Telecommunications Trusted Networks 19 Secret Key vs. Secret Algorithm

Secret Algorithm Military Hard to keep an algorithm secret, if used widely Reverse engineering Secret keys Commercial Publish the algorithm while keeping the key secret The design and analysis of todays cryptographic algorithms is highly mathematical. Do not try to design your own algorithms. School of Electrical Engineering & Telecommunications Trusted Networks 20 Simple Encryption Scheme substitution cipher: substituting one thing for another monoalphabetic cipher: substitute one letter for another plaintext:

abcdefghijklmnopqrstuvwxyz ciphertext: mnbvcxzasdfghjklpoiuytrewq e.g.: Plaintext: bob. i love you. alice ciphertext: nkn. s gktc wky. mgsbc mapping from set of 26 letters to another set of 26 letters School of Electrical Engineering & Telecommunications Trusted Networks 21 Letter Frequency in English Letter Relative frequency

A 8.2% B 1.5% C 2.8% D 4.3% E 12.7

I 7% T 9.1% Z 0.1% School of Electrical Engineering & Telecommunications Trusted Networks

22 Breaking an Encryption Scheme Ciphertext only Trudy (bad guy) has access to enough ciphertext only brute-force search until finding a recognizable plaintext (Exhaustive) Need enough ciphertext Known plaintext Trudy can obtain some pairs secret may be revealed (by spy or time) Eg. in monoalphabetic cipher, trudy determines pairings for a,l,i,c,e,b,o, Chosen plaintext Trudy can choose a plaintext and have its ciphertext computed Can break mono-alphabetic cipher the quick brown fox jumps over the lazy dog School of Electrical Engineering & Telecommunications Trusted Networks 23

More Sophisticated Encryption n substitution ciphers, M1,M2,,Mn cycling pattern: e.g., n=5: M1,M3,M4,M3,M2; M1,M3,M4,M3,M2; .. for each new plaintext symbol, use subsequent substitution pattern in cyclic pattern dog: d from M1, o from M3, g from M4 Encryption key: n substitution ciphers, and cyclic pattern key need not be just n-bit pattern School of Electrical Engineering & Telecommunications Trusted Networks 24 Computational Difficulty Algorithm should be efficient to compute but significantly difficult for a brute-force cryptanalysis

Brute-force cryptanalysis: try all keys until looks like plaintext a longer key means more work for brute-force cryptanalysis encryption: O(N+1), brute-force: O(2N+1) twice as hard with each additional bit Advances in computing benefit cryptographer more, but make old uses of cryptography easier to break DES (56 bit key) was standardized in 1977. It took 56 hours to break it in 1998, less than 1 day in 2008 School of Electrical Engineering & Telecommunications Trusted Networks 25 Types of Cryptographic Functions Crypto often uses keys: Algorithm is known to everyone Only keys are secret Private key cryptography (symmetric cryptography) one shared key Public key cryptography (asymmetric cryptography)

two keys (public and private) Hash function Zero keys!! How can this be useful? School of Electrical Engineering & Telecommunications Trusted Networks 26 Symmetric Key Cryptography KS KS plaintext message, m encryption algorithm ciphertext K S

(m) decryption plaintext algorithm m = KS(KS(m)) symmetric key crypto: Bob and Alice share same (symmetric) key: K S e.g., key is knowing substitution pattern in mono alphabetic substitution cipher Q: how do Bob and Alice agree on key value? School of Electrical Engineering & Telecommunications Trusted Networks 27 Summary What is cryptography Three ways to break cryptography Trivial ciphers

Cryptographic functions and their applications Next : private key cryptography School of Electrical Engineering & Telecommunications Trusted Networks 28 Private Key Encryption Also referred to as: Conventional encryption Symmetric key encryption Secret-key or single-key encryption Only alternative before public-key encryption in 1970s Still most widely used alternative to public-key encryption School of Electrical Engineering & Telecommunications Trusted Networks

29 Private Key Cryptography One key shared by both participators one key, two operations (encryption and decryption) School of Electrical Engineering & Telecommunications Trusted Networks 30 Example: Polyalphabetic encryption 500 years ago! n mono-alphabetic ciphers, C1, C2,,Cn Cycling pattern: e.g., n=4, C1,C3,C4,C3,C2; C1,C3,C4,C3,C2; For each new plaintext symbol, use subsequent mono-alphabetic cipher in cyclic pattern dog: d from C1, o from C3, g from C4 Key: the n ciphers and the cyclic pattern

School of Electrical Engineering & Telecommunications Trusted Networks 31 Polyalphabetic encryption example Plaintext letter: 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 C1(k=5) : 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 C2(k=19) : 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 Pattern: C1, C2, C2, C1, C2 Plaintext message: bob, i love you Cipher text message: ghu, n etox dhz A F

T B G U C1 C2 b o g h C H V D I W C2 b u

, Key? E J X F K Y C1 i n G L Z H M A

I N B C2 C1 l o e t J O C K P D C2 C2 v e o x

L Q E M R F N S G O T H P U I C1 y d

C2 o h C1 u z C2 School of Electrical Engineering & Telecommunications Q V J R W K S X L

T Y M U Z N V A O W B P Trusted Networks X C Q Y D

R Z E S 32 Review: XOR For perfectly random key stream si , each ciphertext output bit has a 50% chance to be 0 or 1 Good statistical property for ciphertext Inverting XOR is simple, since it is the same XOR operation mi ksi ci 0 0

0 0 1 1 1 0 1 1 1 0 School of Electrical Engineering & Telecommunications Trusted Networks

33 Two types of modern private ciphers Stream ciphers encrypt one bit at a time E.g. RC4 Block ciphers Break plaintext message in equal-size blocks Encrypt each block as a unit E.g. DES, IDEA, AES School of Electrical Engineering & Telecommunications Trusted Networks 34 Basic View of Cryptography Cryptography Symmetric Stream Ciphers

Asymmetric Protocols Block Ciphers School of Electrical Engineering & Telecommunications Trusted Networks 35 Stream Ciphers keystream generator input key pseudo random keystream

Combine each bit of keystream with bit of plaintext to get bit of ciphertext XOR operation (modulo 2 addition) m(i) = ith bit of message ks(i) = ith bit of keystream c(i) = ith bit of ciphertext c(i) = ks(i) m(i) ( = exclusive or) m(i) = ks(i) c(i) School of Electrical Engineering & Telecommunications Trusted Networks 36 Stream Ciphers

keystream generator input key Should be random , i.e., Pr(ks(i) = 0) = Pr(ks(i) = 1) = 0.5 Must be reproducible by sender and receiver Synchronous Stream Cipher keystream Security of stream cipher depends entirely on the key stream ks(i) :

pseudo random Key stream depend only on the key (and possibly an initialization vector IV) Asynchronous Stream Ciphers Key stream depends also on the ciphertext (dotted feedback enabled) School of Electrical Engineering & Telecommunications Trusted Networks 37 Random Number Generators (RNGs) Three types of RNGs True Random Number Generators Physical processes Pseudorandom Random Number Generators

They are deterministic Cryptographically Secure Random Number Generators PRNG with an additional property numbers are unpreicitable School of Electrical Engineering & Telecommunications Trusted Networks 38 True Random Number Generators (TRNGs) Based on physical random processes: coin flipping, dice rolling, semiconductor noise, radioactive decay, mouse movement, clock jitter of digital circuits Output stream ksi should have good statistical properties: Pr(ksi = 0) = Pr(ksi = 1) = 50% (often achieved by post-processing) Output can neither be predicted nor be reproduced Typically used for generation of keys, nonces (used only- once values) and for many other purposes School of Electrical Engineering & Telecommunications

Trusted Networks 39 Pseudorandom Number Generator (PRNG) Generate sequences from initial seed value Typically, output stream has good statistical properties Output can be reproduced and can be predicted Often computed in a recursive way: ks0 seed ksi1 f (ksi ,ksi1,..., ksi t ) Example: rand() function in ANSI C: ks0 12345 1103515245 +_12345 mod 231 Most PRNGs have bad cryptographic properties! School of Electrical Engineering & Telecommunications Trusted Networks

40 Cryptanalyzing a Simple PRNG Simple PRNG: Linear Congruential Generator ks0 seed ksi 1 A.ksi B mod m Assume unknown A, B and S0 as key Size of A, B and Si to be 100 bit 300 bit of output are known, i.e. S1, S2 and S3 Solving ks 2 Aks1 B mod m ks3 Aks2 B mod m directly reveals A and B. All Si can be computed easily! Bad cryptographic properties due to the linearity of most PRNGs School of Electrical Engineering & Telecommunications Trusted Networks

41 Cryptographically Secure Pseudorandom Number Generator (CSPRNG) Special PRNG with additional property: Output must be unpredictable More precisely: Given n consecutive bits of output , the following output bits , ksn+2 cannot be predicted (in polynomial time). Needed in cryptography, in particular for stream ciphers Remark: There are almost no other applications that need unpredictability, whereas many, many (technical) systems need PRNGs. School of Electrical Engineering & Telecommunications

Trusted Networks 42 One-Time Pad Unconditionally secure cryptosystem: A cryptosystem is unconditionally secure if it cannot be broken even with infinite computational resources One-Time Pad A cryptosystem developed by Mauborgne that is based on Vernams stream cipher: Properties: Let the plaintext, ciphertext and key consist of individual bits xi, yi, ski {0,1}. Encryption: Decryption: eki(xi) = xi ski. dki(yi) = yi ski OTP is unconditionally secure if and only if the key ski. is used once! School of Electrical Engineering & Telecommunications

Trusted Networks 43 OTP Operation Two pads of paper containing identical random sequences of letters are produced and securely issued to both Alice chooses the appropriate unused page from the pad The way to do this is normally arranged for in advance, as for instance 'use the 12th sheet on 1 May', or 'use the next available sheet for the next message'. The material on the selected sheet is the key for this message. School of Electrical Engineering & Telecommunications Trusted Networks 44 One-Time Pad

Unconditionally secure cryptosystem: y 0 = x 0 k0 y1 = x1 k1 : Every equation is a linear equation with two unknowns for every yi are xi = 0 and xi = 1 equiprobable! This is true iff k0 , k1, ... are independent, i.e., all ki have to be generated truly random It can be shown that this systems can provably not be solved Disadvantage: For almost all applications the OTP is impractical since the key must be as long as the message! (Imagine you have to encrypt a 1GByte email attachment.) School of Electrical Engineering & Telecommunications Trusted Networks

45 Practical Stream Ciphers K Xi K PRNG PRNG Si Yi Si Xi Linear Congruential Generator

ks0 seed ksi 1 A.ksi B mod m What is the drawback? Only needs to know 3 symbols to break the system S2 = A.S1 + B mod m S3 = A.S2 + B mod m School of Electrical Engineering & Telecommunications Trusted Networks 46 Summary Introduction to stream ciphers Random number Generators One Time Pad (OTP) School of Electrical Engineering & Telecommunications Trusted Networks 47

What is the Solution? Linear Feedback Shift Registers (LSFRs) Stream cipher that is small (= low power) School of Electrical Engineering & Telecommunications Trusted Networks 48 Linear Feedback Shift Registers (LFSRs): m=3 LFSR output described by recursive equation: si3 si1 si mod 2 Maximum output length (of 23-1=7) achieved only for certain feedback configurations e.g. the one shown here School of Electrical Engineering & Telecommunications

clk FF2 FF1 FF0=si 0 1 0 0 1 0 1 0

2 1 0 1 3 1 1 0 4 1 1 1

5 0 1 1 6 0 0 1 7 1 0 0

8 0 1 0 Trusted Networks 49 Linear Feedback Shift Registers (LFSRs) Concatenated flip-flops (FF), i.e., a shift register together with a feedback path Feedback computes fresh input by XOR of certain state bits Degree m given by the number of storage elements If pi = 1, the feedback connection is present (closed switch), otherwise (pi = 0) there is no feedback from this flip-flop (open switch) Output sequence repeats periodically Maximum output length: 2m-1 Sm+1

School of Electrical Engineering & Telecommunications Trusted Networks 50 Summary of LFSRs LFSRs typically described by polynomials: P(x) x m pl-1xm1 ... p1 x p0 Single LFSRs generate highly predictable output If 2m output bits of an LFSR of degree m are known, the feedback coefficients pi of the LFSR can be found by solving a system of linear equations Because of this many stream ciphers use combinations of LFSRs Only LSFRs with primitive polynomials yield maximum School of Electrical Engineering & Telecommunications Trusted Networks 51 Attack on LSFR Stream Ciphers

Step 1 Yi = Xi + Si mod 2 Si = Yi + Xi mod 2 I = 0, 1, ., 2m-1 Step 2 Recover S2m, S2m+1, . Unknown pis Remember Sm+1 System of m linear equations with m unknowns Can easily be solved by gaussian elimination (matrix inversion) School of Electrical Engineering & Telecommunications Trusted Networks 52 Summary Overview of LFSR General LSFR

Attacks School of Electrical Engineering & Telecommunications Trusted Networks 53 Basic View of Cryptography Cryptography Symmetric Stream Ciphers Asymmetric Protocols Block Ciphers School of Electrical Engineering & Telecommunications Trusted Networks

54 Block Cipher Primitives: Confusion and Diffusion Claude Shannon: There are two primitive operations with which strong encryption algorithms can be built: Confusion: An encryption operation where the relationship between key and ciphertext is obscured. Today, a common element for achieving confusion is substitution, which is found in both AES and DES. Diffusion: An encryption operation where the influence of one plaintext symbol is spread over many ciphertext symbols with the goal of hiding statistical properties of the plaintext. A simple diffusion element is the bit permutation, which is frequently used within DES. Both operations by themselves cannot provide security. The idea is to concatenate confusion and diffusion elements to build so called product ciphers.

School of Electrical Engineering & Telecommunications Trusted Networks 55 Product Ciphers Most of todays block ciphers are product ciphers as they consist of rounds which are applied repeatedly to the data. Can reach excellent diffusion: changing of one bit of plaintext results on average in the change of half the output bits. Example: School of Electrical Engineering & Telecommunications Trusted Networks 56 Block Ciphers DES: Data Encryption Standard

US encryption standard [NIST 1993] 56-bit symmetric key, 64-bit plaintext input block cipher with cipher block chaining how secure is DES? DES Challenge: 56-bit-key-encrypted phrase decrypted (brute force) in less than a day no known good analytic attack making DES more secure: 3DES: encrypt 3 times with 3 different keys School of Electrical Engineering & Telecommunications Trusted Networks 57 Overview of the DES Algorithm Encrypts blocks of size 64 bits. Uses a key of size 56 bits. Symmetric cipher: uses

same key for encryption and decryption Uses 16 rounds which all perform the identical operation DES 56 k 64 y Different subkey in each round derived from main key School of Electrical Engineering & Telecommunications Trusted Networks The DES Feistel Network (1)

DES structure is a Feistel network Advantage: encryption and decryption differ only in keyschedule Bitwise initial permutation, then 16 rounds 1. Plaintext is split into 32-bit halves Li and Ri 2. Ri is fed into the function f, the output of which is then XORed with Li 3. Left and right half are swapped Rounds can be expressed as: School of Electrical Engineering & Telecommunications Trusted Networks The DES Feistel Network (2) L and R swapped again at the end of the cipher, i.e., after round 16 followed by a final permutation

School of Electrical Engineering & Telecommunications Trusted Networks Initial and Final Permutation Bitwise Permutations. Inverse operations. Described by tables IP and IP-1. Initial Permutation Permutation School of Electrical Engineering & Telecommunications Final Trusted Networks The f-Function main operation of DES f-Function inputs: Ri-1 and round key ki 4 Steps:

1. Expansion E 2. XOR with round key 3. S-box substitution 4. Permutation School of Electrical Engineering & Telecommunications Trusted Networks The Expansion Function E 1. Expansion E ! main purpose: increases diffusion School of Electrical Engineering & Telecommunications Trusted Networks

The DES S-Boxes S-Box substitution Eight substitution tables. 6 bits of input, 4 bits of output. Non-linear and resistant to differential cryptanalysis. Crucial element for DES security! School of Electrical Engineering & Telecommunications Trusted Networks Security of DES After proposal of DES two major criticisms arose: 1. Key space is too small (256 keys) 2. S-box design criteria have been kept secret: Are there any hidden analytical attacks (backdoors), only known to the NSA? Analytical Attacks: DES is highly resistent to both differential and linear cryptanalysis, which have been published years later than the DES. This means IBM and NSA had been aware of these attacks for 15 years!

So far there is no known analytical attack which breaks DES in realistic scenarios. Exhaustive key search: For a given pair of plaintext-ciphertext (x, y) test all 256 keys until the condition DES -1(x)=y is fulfilled. Relatively easy given todays computer technology! School of Electrical Engineering & Telecommunications Trusted Networks 65 3DES 2 keys used instead of 3 keys equivalent key length is 112 bits 3DES operations: EDE for encryption, DED for decryption 3DES is inefficient and expensive Some systems implement 3DES with 3 keys Not standard If K1 =K2 3DES becomes equivalent of DES

School of Electrical Engineering & Telecommunications Trusted Networks 66 3DES School of Electrical Engineering & Telecommunications Trusted Networks 67 AES: Advanced Encryption Standard 1. Symmetric-key NIST standard, replaced DES (Nov 2001) 2. Processes data in 128 bit blocks 3. Three supported key lengths:128, 192, or 256 bit 4. Brute force decryption (try

each key) taking 1 sec on DES, takes 149 trillion years for AES School of Electrical Engineering & Telecommunications Key Length Number of Rounds 128 10 198 12 256 14

Trusted Networks 68 AES Overview School of Electrical Engineering & Telecommunications Trusted Networks 69 Summary Understanding of DES Overview of DES Internals What is 3 DES and AES School of Electrical Engineering & Telecommunications Trusted Networks