FIT2093 INTRODUCTION TO CYBER SECURITY
Week 2 Lecture Cryptography I: Symmetric Key Encryption Part 2
Principles for CONFIDENTIALITY
www.monash.edu
Copyright By PowCoder代写 加微信 powcoder
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
AES: Round Function
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代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com