FIT2093 INTRODUCTION TO CYBER SECURITY

Week 2 Lecture Cryptography I: Symmetric Key Encryption Part 2

Principles for CONFIDENTIALITY

www.monash.edu

Copyright By cscodehelp代写 加微信 cscodehelp

Symmetric Cryptography

Part 2: Modern Encryption Algorithms ● Blockciphers

● Designrequirements

● CasestudyI:DataEncryptionStandard(DES)

● CasestudyII:AdvancedEncryptionStandard(AES)

● BlockCipherModes:Howtouseblockciphersforencryption • ECB, CBC, CTR

Block Ciphers

Modern Ciphers vs Classical Ciphers

Symmetric Cryptography

● vsclassicalciphers:processplaintextincharacters ● modern ciphers: process plaintext in blocks

Classical: 1 plaintext char e.g. A

Modern: 1 plaintext block ( 128 bits) e.g. 11010…111

Modern approach to encryption design:

1 ciphertext char e.g. X

1 ciphertext block (128 bits) e.g. 01011…011

● Design a block cipher (for encrypting one block length, e.g. 128 bit)

● Use a block cipher mode of operation to encrypt (arbitrary length messages)

● Another approach: stream ciphers – bit by bit encryption (we won’t study)

Block Cipher

Symmetric Cryptography

• plaintext block P of length n bits

• secret key K of length k bits

• ciphertext block C of length n bits

● algorithmEappliesefficientsubstitution&permutation(transposition) operations to compute C = E(K,P)

Block Cipher: Requirements

Symmetric Cryptography

● DecryptionCorrectness:

• Decryption algorithm D correctly decrypts C produced by E, i.e.

• i.e. for any (P, K), if C = E(K,P) then D(K,C) = P

Block Cipher: Requirements

Symmetric Cryptography

● PseudorandomFunctionSecurity(PRF):

• E should have the Confusion & Diffusion properties

• Outputs of E look random: If K chosen randomly,

computationally infeasible for an attacker to distinguish output ciphertexts Ci = E(K,Pi) from random bit strings of same length,

even if attacker corresponding distinct plaintexts Pi’s (known plaintext attack)

P E C rand Z K

Block Cipher: Requirements

Symmetric Cryptography

● PseudorandomFunctionSecurity(PRF): • i.e. as long as K is random,

• outputs C from encryption E should look like random bit strings Z of same length

• attacker cannot tell the difference, even if s/he knows P • à means the encryption really able to “mix” P up

P E C rand Z

Attacker can’t tell difference between C and Z, (even given P, but not given K).

PRF Security: Simple Examples

• Q: Do you think Cipher EA has PRF security?

• What about cipher EB?

P EA C P EB C 11110101 01110110 11110101 00101101

P EA C P EB C

00000101 10000110 00000101 10111110 KK

P EA C P EB C

10110110 00110101

Block Cipher: Design

Symmetric Cryptography

● Repeatedcombinationof…

• Confusion via Substitution

• substitutes

• Diffusion via Permutation • spreads

Q:whyrepeat?

Note: image by PRESENT designers

Block Cipher: Older ones

Symmetric Cryptography

● DES [US, 1977] (stronger version called 3DES) • |P|=|C|= 64 bits, |K| = 56 bits

● LOKI [ADFA, Australia, 1989]

• |P|=|C|=|K| = 64 bits

● FEAL [NTT, Japan, 1990]

• |P|=|C|= 64 bits, |K| = 128 bits

● IDEA [Lai & Massey, Switzerland, 1991], used in PGP

• |P|=|C|= 64 bits, |K| = 128 bits

● MISTY1 [Mitsubishi, Japan, 1995]

• |P|=|C|= 64 bits, |K| = 128 bits

Block Cipher: Newer ones

Symmetric Cryptography

● KASUMI for 3G standard [Mitsubishi+3GPP, 2000] • |P|=|C|= 64 bits, |K| = 128 bits

● AES [Joan Daemen & , Belgium, 2001] • |P|=|C|= 128 bits, |K| = 128,192,256 bits

● Lightweight Block Ciphers

• ISO/IEC 29192-2:2019:

• PRESENT [2007]: |P|=|C|= 64 bits, |K| = 180, 128 bits

• CLEFIA [2007]: |P|=|C|= 128 bits, |K| = 128,192,256

• LEA [2013]: |P|=|C|= 128 bits, |K| = 128,192,256

Block Cipher: Data Encryption Standard (DES)

Symmetric Cryptography

● DES [US, 1977]

• |P|=|C|= 64 bits, |K| = 56 bits

• has Feistel structure [ @IBM]

• used to be *the* standard for encryption

• obsolete, totally insecure, withdrawn as standard [2005]

● Triple-DES (3-DES) [US, 1995] • stronger version of DES

• do DES 3 times

• still in use as a standard

DES Structure: Feistel

Symmetric Cryptography

● 1stround:

• R1 =L0 ⊕f(R0,K1)

● foreachroundi(i=1,2,…,n): • Li=Ri-1

• Ri =Li-1 ⊕f(Ri-1,Ki)

• f = round function

• Ki = round sub-key

● Decryption: reverse the process

Bit-wise exclusive-or (XOR) : Refresher

Symmetric Cryptography

Decrytibility property of XOR: (P ⊕ K) ⊕ K = P e.g. P = 1110, K = 0101,

Encrypt:C=P ⊕ K= 1110 ⊕ 0101=1011 Decrypt:P=C ⊕ K =1011 ⊕ 0101=1110

Q: How to use decryptibility of XOR to decrypt the first round of Feistel cipher?

i.e. given (L1, R1), and K1, how to compute (L0, R0)?

• 1) How can we find R0 from L1? (Hint: Look at the top of left diagram!)

• 2) How can we find T1 from R0 and K1? (Hint: Look at the top of left diagram!)

• 3) How can we find L0 from R1 and T1? (Hint: From diagram, R1 = L0 ⊕ T1)

Activity (2 mins)

1) Add your question responses to the Ed forum

0 0=0 1 1=0 0 1=1 1 0=1

DES Structure: Round Function F

Symmetric Cryptography

● 32bitsgointof

● E: 32 → 48 bits, & permuted

● ⊕: XOR with subkey Ki

● 48→6|6|6|6|6|6bits

● 8 S-boxes: 6 → 4 bits

● 4|4|4|4|4|4→32bits

● P: Permutes the 32 bits of Sbox outputs

Block Cipher: Relation of Parameters to Security

Symmetric Cryptography

● Block size |P|=|C|: ↑ block size ⇒ ↑ security

● Key size |K|: ↑ key size ⇒ ↑ security

● Number of rounds r: ↑ rounds ⇒ ↑ confusion/diffusion ⇒ ↑ security

● Q: Why not making blocksize, key size and number of rounds very large, if this (usually) tends to increase security?

Activity (2 mins)

1) Add your question responses to the Ed forum

Block Cipher: Security vs Brute Force

Symmetric Cryptography

● brute force / exhaustive key search

● effort to guess secret key K & to verify guess

● brute force guess k-bit key needs 2k guesses & verifications

● Q: how to verify key guess?

Block Cipher: Advanced Encryption Standard (AES)

Symmetric Cryptography

● [1997] US National Institute of Standards & Technology (NIST) issued call for proposals of algorithms for Advanced Encryption Standard (AES) to replace DES

● developed by Joan Daemen & [Belgium]

○ also known as Rijndael algorithm

● [2000] AES algorithm selected, standardised in 2001

● Blocksize:

● Key size:

● #rounds:

|M|=|C|=128

|K| = 128, 192, 256 bits

10, 12, 14

AES: Encryption Structure

Symmetric Cryptography

○ represented as array of bytes

● Round function ○ SubBytes:

○ ShiftRow

○ MixColumns

○ AddRoundKey

AES: Round Function

Symmetric Cryptography

● Round function ○ SubBytes

○ ShiftRow

○ MixColumns

○ AddRoundKey

AES: Round Function

Symmetric Cryptography

● Round function ○ SubBytes ○ ShiftRow

○ MixColumns

○ AddRoundKey

AES: Round Function

Symmetric Cryptography

● Round function ○ SubBytes

○ ShiftRow

○ MixColumns ○ AddRoundKey

Symmetric Cryptography

● Round function ○ SubBytes

○ ShiftRow

○ MixColumns

○ AddRoundKey

AES: Implementation Aspects

Symmetric Cryptography

● efficientlyimplementedon8-bitCPU

○ SubBytes:onbytesusingatableof256entries

○ ShiftRows:simplebyteshift

○ MixColumns:matrixmultiplicationinfinitefieldGF(28)i.e.bytevalue coefficients

○ AddRoundKey:simplebyteXOR

● Warning:Don’timplementAESorDESyourself

○ straightforwardimplementationsareinsecureagainstsidechannel attacks (e.g. timing attack)

○ useawell-knowncryptolibrarywrittenbyexperts

Cipher Security: Cryptanalysis

Symmetric Cryptography

● anycipherdesignneedstoundergosecurityanalysis

○ brute force: always applicable, upper bound

> on average, need to try half of key space

> e.g. for k-bit key, key space is 2k

○ Goal of cryptanalysis: Find Shortcut attacks faster than brute force > exploit

– cipher structure

– plaintext characteristics/features/patterns

> To try to make breaking effort < brute force
> For a well designed modern cipher, no shortcut attacks known! > àFastest attack = brute force

Cipher Security: Security Models

Symmetric Cryptography

● Q:Toanalysethreatsagainstciphers,wecanspecifyanattackmodel ● AttackModel=Securitygamebetween:

○ users on one side, with security goal > behave, follow steps

○ attackers on the other side, vs security goal

> have adversarial goal

> have adversarial capabilities

– knowledge of …

– access to …

– can exploit users

Cipher Security Models: Attacker Capabilities

Symmetric Cryptography

● Cancategorizesecuritymodelbasedonattacker’scapabilities(whats/he can access to):

○ Ciphertext Only Attack (COA)

○ Known Plaintext Attack (KPA)

○ Chosen Plaintext Attack (CPA)

○ Chosen Ciphertext Attack (CCA)

– can exploit users

Cipher Security Models: Attacker Capabilities

Symmetric Cryptography

● Passive attacks

● Ciphertext Only Attacks (COA)

○ Attacker only has access to some samples of ciphertexts C

○ Example scenario: eavesdropping ciphertext of a password on the internet

● Known Plaintext Attacks (KPA)

○ Attacker knows some samples of ciphertexts C with their corresponding

plaintexts P, and try to decrypt another ciphertext C’

○ E.g. knowing C,P may reveal info. on key K, could then decrypt C’

○ examples:

○ Q: What could be a possible practical scenario for a known plaintext attack (KPA)?

Activity (2 mins)

1) Add your question responses to the Ed forum

Cipher Security Models: Attacker Capabilities

Symmetric Cryptography

● Active attacks

● Chosen Plaintext Attacks (CPA)

○ Attacker can feed encryption alg. with plaintexts P and obtain matching ciphertexts C

○ example: get sender to encrypt forwarded email received from attacker

○ Such chosen (P,C) pairs may reveal even more information on secret key K

● Chosen Ciphertext Attacks (CCA)

○ Attacker can feed decryption alg. with ciphertexts C and obtain info. on their

decryption P ○ example:

○ attacker sends ciphertext C to web server

○ web server decrypts ciphertext C with key K, checks decryption validity

○ decryption validity or failure error may reveal info. on server’s key K

Cipher Security Models: Attacker Goals

Symmetric Cryptography

● PlaintextRecovery(PR)

○ Attack goal: find the unknown plaintext P* ● KeyRecovery(KR)

○ Attack goal: find the unknown secret key K ● INDistinguishability(IND)

Attacker knows the plaintext list

Attack goal: distinguish which plaintext P* ∈ {P0 , P1} was encrypted to ciphertext C

• Ideal security: not even one bit of info. on plaintext revealed to attacker! e.g is C = E(K,“Yes”) or E(K,“No”)?

Block Cipher Modes

Block Cipher: Modes of Operation

Symmetric Cryptography

● block ciphers E process data in blocks

○ e.g. 64-bits (DES, 3DES) or 128-bits (AES)

● for longer messages, must break up

○ & possibly pad the end to multiple of block

○ unambiguous padding: 100000….0000000

● 5 modes (ways) of operation, to use a block cipher

○ defined in NIST SP 800-38A

○ ECB (insecure for most applications), CBC, CTR

CFB, OFB (we don’t study)

ECB: Electronic Code Book mode

Symmetric Cryptography

● messagebrokenintoblocks,&encrypted

● eachblock’svalueissubstituted,likeusingacodebook ● eachblockisencodedindependentlyofotherblocks

Ci = E(Pi,K)

… … …

ECB Mode: Insecurity

ECB mode is insecure (i.e. not satisfy IND-CPA) even if block cipher is

> Statistical frequency analysis attack, again!

> e.g. easy to distinguish between ECB encryptions of

– M0=(P0 =0,P1 =0)

– M1=(P0 =0,P1 =1)

Q: How can an attacker easily distinguish whether given C0,C1 is ECB ciphertext of

M0 =(0,0) or M1=(0,1)?

Activity (2 mins)

1) Add your question responses to the Ed forum

ECB: Electronic Code Book mode

Symmetric Cryptography

ECB: Limitations

Symmetric Cryptography

● blockindependence

○ messagerepetitionsmayshowinciphertext

> particularly with block data such as graphics

> or with messages that change very little ○ candocode-bookanalysis

● shouldbeavoided(useasecuremodeinstead)

ECB: Limitations

Symmetric Cryptography

● blockindependence:

○ Message block repetitions may show in ciphertext

■ encryption does not destroy the message pattern

ECB Secure mode

CBC: Cipher Block Chaining

Symmetric Cryptography

● messageblockslinkedtogetherinencryptionoperation

● eachpreviouscipherblockischainedwithcurrentplaintext

block, hence name

● useInitialVector(IV)tostartprocess

for i=1,…,N

Ci = E(Pi ⊕ Ci-1,K)

● uses:tosecurebulkdatae.g.harddiskencryption 39

CBC: Cipher Block Chaining

Symmetric Cryptography

Image source: Wikipedia

CBC: Advantages & Disadvantages

Symmetric Cryptography

● ciphertextblockdependsonallblocksbeforeit ○ Encryptioncannotbeparallelized

● change to a block affects all following ciphertext blocks in encryption ● error propagation: error in received block affects two decrypted

plaintext blocks

● needInitializationVector(IV)

○ which must be known to sender & receiver

○ must be chosen independently at random for each encryption

● IND-CPA Security: if IV randomly chosen independently for each message, & block cipher is a secure PRF, then CBC mode is secure

Stream Modes of Operation

Symmetric Cryptography

● vsblockmodes:encryptentireblock ● mayneedtooperateonsmallerunits

○ realtimedata

● convertblockcipherintostreamcipher

○ canuseblockcipherassomeformofpseudo-randomnumber generator (PRNG)

● StreamModes:

○ cipherfeedback(CFB)mode–wedon’tstudy ○ outputfeedback(OFB)mode–wedon’tstudy ○ counter(CTR)mode

CTR: Counter

Symmetric Cryptography

● encryptscountervalueincrementedaftereachblock

● musthaveadifferentkey&differentcountervalueforevery plaintext block (never reused)

ctr1 = IV for i=1,…,N

Oi = E(ctri,K)

Ci =Pi XOROi

ctri+1 = ctri + 1 (increment ctr)

● uses:high-speednetworkencryptions,IPSec,networksecurity

CTR: Counter

Symmetric Cryptography

CTR: Advantages & Limitations

Symmetric Cryptography

● efficiency

○ candoparallelencryptionsinh/wors/w ○ canpreprocessinadvance

○ goodforbursty&highspeedlinks

• No error propagation: error in received block does not affect decryption of subsequent blocks

● randomaccess(independentblocks)toencrypteddatablocks

● IND-CPA Security: if IV randomly chosen independently for each message or a nonce that’s never reused, & block cipher is a secure PRF, then CTR mode is secure

Further Reading

• Chapter 20 of the textbook: Computer Security: Principles and Practice” by & , , 2015

• Chapters 1-3 of textbook: Introduction to Modern Cryptography, by and , Chapman & Hall/CRC, 2008. [deeper understanding]

• [ZoomECB] Zoom Videoconference using ECB mode encryption: https://citizenlab.ca/2020/04/move-fast-roll-your-own-crypto-a-quick-look-at-the- confidentiality-of-zoom-meetings/

程序代写 CS代考 加微信: cscodehelp QQ: 2235208643 Email: kyit630461@163.com