FIT2093 INTRODUCTION TO CYBER SECURITY
Week 5 Lecture Information Integrity & Authentication
Principles for INTEGRITY
www.monash.edu
Copyright By PowCoder代写 加微信 powcoder
Integrity & Message Authentication
● Public-keyCryptographicIntegrityTechniques
• digital signatures
• hash functions
● Symmetry-keyCryptographicIntegrityTechniques
• message authentication codes (MAC)
• from block ciphers
• from hash functions
• authenticated encryption (AE), sign-then-encrypt
Public-key Cryptography for Integrity & AUTHentication
Recap: INT/AUTH goals/strategy
• INT/AUTHAims:
• Integrity (INT): Received data not tempered with (modified) • Authenticity (AUTH): Received data not fake (fabricated)
Problem: Insecure channel / storage
• accept fact: channel insecure
• whatever sent could be modified, fabricated data could be sent
• So: make sure mods/fakes are detected by receiver
• receiver rejects the mods/fakes
Data INT/AUTH: How?
○ Requirements
○ Only authentic sender can sign
○ infeasible for attacker to forge ○ Receiver can efficiently verify
○ Paper world analogy: hand-written signatures
○ Q: Why not adapt in the digital world?
○ Attach to document an image of handwritten signature ○ But… is it secure?
Q: How could Marvin, intercepting a document m with attached image of Alice’s signature, produce a modified document m’ accepted by Bob as authentic from Alice?
INT/AUTH: How?
○ Replay (copy) attack with unchanging (fixed) signatures:
Doc (modified)
Sig (copied)
copied sig authenticà
modified m’ accepted by Bob!
○ Idea: to detect replay (copy) attacks:
○ make the signature dependent on the signed document! ○ copied sig. for m will not be valid for different m’
○ Q: Modify ideas of PKE to build such a digital signature?
○ To prevent forgeries: sig. depends on sender’s private key ○ To allow anyone to verify: verify with sender’s public key
Recap: PKE
Integrity & Authentication
● Recall from last week: PKE for CONFidentiality
○ Q:usewhatkeytoencryptsoonlyrecipientcanundo(i.e.decrypt)?
@Tx: (pkT , skT)
@Rx: (pkR , skR) Decrypt
PKC for AUTH & Integrity
Integrity & Authentication
● Idea: “dual” (inverted) use of keys for AUTH
○ Q:usewhatkeytosigntoensureonlyoriginatorcando(thesigning)?
○ known as digital signature @Tx: (pkT , skT)
Received Document
Encrypted Signature
Digital Signatures
Integrity & Authentication
● AUTHentication: verify msg really came from sender
○ use digital signature:
• only sender could have generated signature,
• because only sender has her private key
● INTegrity: verify msg has not been modified by unauthorised parties
○ use digital signature:
• infeasible for attacker to modify msg together with valid sig
• without knowing sender’s private key
Digital Signatures: Examples
Integrity & Authentication
● RSA Signature [1977]
○ AUTHentication variant of RSA encryption
○ security based on Integer Factorisation Problem
● Digital Signature Algorithm (DSA) [ElGamal 1984, Schnorr 1991, NIST 1991]
○ AUTHentication variant of Diffie-Hellman key exchange/El-Gamal
encryption
○ security based on Discrete Logarithm Problem
○ Shorter/faster variant: Elliptic Curve Digital Signature Algorithm (ECDSA) [ANSI 1998, NIST 2000]
Digital Signatures Example: RSA
Integrity & Authentication
● Key Generation for the Tx Alice:
○choose two primes: p = 5, q = 11
○getmodulus:multiplypandq: n=pxq=55
○And φ(n)=(p–1)x(q–1)=4×10=40
○find two numbers e = 3 & d = 27 which satisfy e x d mod φ(n) = 1
(3 x 27) mod 40 = 1 ○ Tx’s Alice’s public key
■ two numbers:
(e,n) = (3, 55)
■ encryption algorithm: modular exponentiation
○ Tx’s private key:
(d, n) = (27,55)
Digital Signatures Example: RSA
Integrity & Authentication
● Alice has a document m = 19 to sign:
○ use private key d = 27 to calculate the digital signature of m = 19: s = md (mod n)
= 1927 mod 55 = (193)9 mod 55 = (31×19)9 mod 55 = (393)3 mod 55 = (36×39)3 mod 55 = 293 mod 55
= (16×29) mod 55
○ append 24 to 19. Now (m, s) = (19, 24)
○ the doc is 19, and Alice’s signature on the doc is 24
Digital Signatures Example: RSA
Integrity & Authentication
● Verification by a verifier Bob:
○ receive a pair (m,s) = (19, 24)
○ look up the web directory and find out Tx Alice’s public key ○(e, n) = (3, 55)
○ calculate t = se (mod n)
= 243 (mod 55) ) = 26×24 mod 55
= 19 ○ check whether t = m
○ confirm that (19,24) is a genuinely signed document of Alice if t = m
Digital Signatures Example: RSA
Integrity & Authentication
● Supposep=3,q=11,
● Alice’s private key (d,n) = (7,33) ● Alice’s public key (e,n) = (3,33)
1) What is Alice’s signature s on message m = 2?
2) If Cathy receives message signature pair (m = 4, s = 31) from Alice, does Cathy conclude s is a valid signature by Alice on m?
Activity (5 mins)
1) Click the latest link in the Zoom chat
2) Add your question response to the Ed forum
Digital Signatures & Hash Functions
Integrity & Authentication
● Digital Signature is slow, similar to PKE
○ docs (m) to sign are usually long (MBs-GBs)
○ so sign a short (~hundreds of bits, e.g. 256 bit) representation (digest/hash value) of m, not directly on m
m digest signature
● Hash function:
○ convertmtodigestd,|m|>>|d|
○ Sidebenefit:improvesUNForgeabilitysecurityofsignatures
Hash function
Hash Functions
Integrity & Authentication
● input:mofanylength
● output: h of fixed length L ● |m|>>|h|
digest/hash
mhs ●e.g. “MD5”(obsolete)hasL=128bits
“SHA-1” (obsolete) has L = 160 bits
● Use SHA-2 (L=256 to 512) or SHA-3 (L=256 to 512) hash functions
Hash function
Hash Function: One-Way Security
Integrity & Authentication
● (I) One-way function security: (aka preimage-resistance):
given h = H(m), computationally infeasible to find m such that h = H(m)
○ thougheasytocomputeoutputh=H(m)frominputm ■ i.e. hard to find input for an output
■ needed for password storage security (later), RSA signature security mhs
Hash function
Q: How could an attacker efficiently forge some message m with a valid RSA signature if Hash Function is not a one-way function? Hint: What does RSA signature verification of s compute?
Activity (2 mins)
1) Click the latest link in the Zoom chat
2) Add your question response to the Ed forum
Hash Function: One-Way Security
Integrity & Authentication
Efficient direction mhs
Infeasible direction
Hash function
Hash Function: COL Security
Integrity & Authentication
• (II) COL: collision-resistance security
○ computationally infeasible to find any pair of distinct
messages m1 , m2 such that h1= H(m1) is equal to h2 = H(m2) m1 h1 s1
Hash function
Q: Suppose RSA signature uses a Hash function that is not collision-resistant. How could an attacker exploit this to efficiently forge some document and its valid RSA signature?
Activity (2 mins)
1) Click the latest link in the Zoom chat
2) Add your question response to the Ed forum
Hash Function: COL Security
Integrity & Authentication
● Hashfunctions:longinputtoshortoutput,|m|>>|h|
○ more possible input values than possible output values
○ collisions must exist
○ the hash table is being filled up by: ■ 1mod9=1
■ 2mod9=2 .
Hash Function: COL Security
Integrity & Authentication
● hashtablealreadyfullaftercomputing9values…
○ further computing e.g. 10 mod 9 = 1
gives collision as shown
● Pigeonholeprinciple
Hash Function: COL Security
Integrity & Authentication
● Surprising Fact (Birthday “Paradox”)
○ only need 23 ≈ 365 random people in a room to have good
chance of finding a pair with same birth day & month
○ à In general: for any hash function H with n-bit output, can
find collision using ≈ 𝟐𝒏 = 𝟐𝒏/𝟐 random inputs to H
○ e.g. for n = 256, can find collisions with ≈2128 input, so only
have security against attacks with run-time < 2128 ops
● à expected collision-resistant (COL) security for hash function: ○ should take about 2n/2 evaluations of H to find COL
*BIRTHDAY PARADOX: EXAMPLE
How many people required in the same room for two people in the room to have the same birthday with about 50% chance?
Assumptions made:
1. 29th February doesn’t exist
2. Each birthday is equally likely to come up.
3. Each people in the room are independent from each other. E.g. none of them are twins etc.
The importance of independence is that we can multiply the probability of occurrences of the events together
*RELATING TO COLLISION RESISTANCE
You might think that we will be needing a lot of people to eliminate the chances away, however it is much less than a lot of us would tend to think:
The answer is only 23 people!
*Birthday Paradox Calculation
Instead of proving “How many people for collision (two people having same birthday)”, we’ll look at complement: what’s the probability that no one in the room shares a birthday?
When 2nd person enters the room, his/her birthday When 3rd person enters the room, same concept applies, he/she has to avoid must not be the same with the 1st person. To avoid first two birthdays, thus 363 possibilities left.
the first birthday the probability of getting different
birthday at this point:
Digital Signatures: Properties
Integrity & Authentication
● analogous to handwritten signature ○ canonlybedonebytheowner
● Properties:
○ verifiesauthor
■ UNForgeable
■ Undeniable–non-repudiatable–Q:why?
○ authenticatesthecontents(m)atthetimeofsignature ○ universallyverifiable:
■ verifiablebythirdparties,toresolvedisputes
Digital Signatures: Security
Integrity & Authentication
● Attack model for Signature Schemes: EUF-CMA
● Attack capability: attacker knows signer’s public key pk
○ Chosen-MessageAttacks(CMA):
■ Shouldbeunforgeableevenifattackercanseemanyvalidsignatureson
many messages, even messages chosen by attacker.
● Attack goal:
○ ExistentialUnForgeability(EUF):
■ Shouldbeinfeasibleforattackertoproduceanyvalid(msg,sig)pair where msg has not been signed by the honest signer
(even for randomly looking msg)
# Digital Signatures: Security
Integrity & Authentication
● Warning: “Textbook RSA signature” without one-way hash function is NOT EUF- CMA , shouldn’t be used
○ e.g..easytocreatevalidforgerysignatureforrandommessagem ○ (andalsosomenotsorandommsgs...)
● à Use a standardised digital signature scheme using a secure (one-way and collision-resistant) one-way hash function
○ e.g.“RSASSA-PSS”digitalsignatureschemeinPKCS#1v2.2standard
○ designedtoachieveEUF-CMAsecurityusingasecurecryptographicone-way hash function
Symmetric Cryptography for Integrity
Symmetric Crypto for INTegrity
Integrity & Authentication
● Problems with Digital Signature (PKC)
○ PKCisslow
○ Universalverifiabilitymaynotbeneeded
■ Maybesufficienttoallowreceivertoverifymsgcamefromotherside ○ Sendermayalreadyshareasecretkeywithotherside
■ à can use a MAC instead of signature
● Message Authentication Code (MAC): symmetric key analogue of digital
○ similarbuildingblocks/operationsassymmetrickeyencryption
MACs vs others
Integrity & Authentication
Public-Key Crypto
Symmetric-Key Crypto
(private key distribution problem)
CONFidentiality
Public Key Encryption / Key Exchange Protocol
Symmetric Key Encryption
Digital Signature
Message Authentication Code (MAC)
MAC: What?
Integrity & Authentication
● MAC can be viewed as a cryptographic checksum
○MAC = CK(M)
○ condenses a variable-length message M
○ using a secret key K
○ to a fixed-sized authenticator / check code / INT code
● is a many-to-one function
○ potentially many messages can generate the same MAC ○ (compressing feature similar to hash functions)
○ but finding those messages should be difficult
Q: What is a main difference between a MAC and a Hash Function?
MAC: Diagram
Integrity & Authentication
MACs: Security
Integrity & Authentication
● Attack model for MACs: EUF-CMA – similar to signatures (except no pk) ● Adversarial capability:
○ Chosen-messageattacks(CMA):
■ ShouldbeunforgeableevenifattackercanseemanyvalidMAC
authenticators on many msgs, even msgs chosen by attacker
● Adversarial goal:
○ Existentialunforgeability(EUF):
■ Shouldbeinfeasibleforattackertoproduceanyvalid(msg,auth)pair where msg has not been MAC’d by the honest sender
(even for randomly looking msg)
MACs: Security Properties
Integrity & Authentication
knowing a message m and MAC output s,
○ infeasibletofindanothermessagem’withsameMAC
○ dealswithmessagereplacement(MACcopy/replay)attacks
MACs should be uniformly distributed across the messages
○ dealswithneedtothwartabrute-forceattackbasedonchosenplaintext
MAC should depend equally on all bits of the message
○ dictatesthattheauthenticationalgorithmshouldnotbeweakerwithrespectto certain parts or bits of the message than others
MACs: How to Construct
Integrity & Authentication
● Two common ways:
○ usingblockciphers
■ specialblockcipherauthenticationmodesof operation, e.g.
● CMAC(CBCmodeforauthentication)
○ usingcryptographichashfunctions
■ specialhashfunctionauthenticationmodesof
operation, e.g.
MACs: from Block Ciphers
Integrity & Authentication
● can use any block cipher chaining mode & use final block as a MAC
○ needtodocarefullytodealsecurelywitharbitrarymessagelengths
● Old method (obsolete): Data Authentication Algorithm (DAA) was a widely used MAC based on DES-CBC
○ Nolongerrecommendedforuseasitistoosmallforsufficientsecurity,and has other problems
● New method: CMAC (NIST, 2005)
○ usestwokeysK1,K2derivedfromasinglekeyK ○ workswithanysecureblockcipher(e.g.AES-128)
MACs: from Block Ciphers
Q: Why need two cases/keys K1 and K2? Integrity & Authentication What would go wrong if we just had one
case (K1=K2)?
Fig Ref: NIST SP800-38b
MACs: from Hash Functions
Integrity & Authentication
● Hash function is similar to MAC: ○ one-way
○ foranyinputlength,fixedoutputlength ○ butnokeyinput
● Can be used with both symmetric & public key cryptography ○ Hashingthemessageindigitalsignatures
■ canalsobeusedtodesignaMAC
MACs: from Keyed Hash Functions
Integrity & Authentication
● want a MAC based on a hash function
○ because hash functions are generally faster than block cipher ○ crypto hash function code is widely available
● hash includes a key along with message
● original proposal:
○ KeyedHash = Hash(Key||m)
○ some security weaknesses were found with this
● eventually led to development of the MAC standard HMAC
MAC Example: HMAC
Integrity & Authentication
MAC Example: HMAC
Integrity & Authentication
● specified as Internet standard RFC2104 ● uses hash function on the message:
○ HMAC(K,M)= Hash[(K+ XOR opad) || Hash[(K+ XOR ipad) || M)] ] where K+ is the key padded out to size
○ opad, ipad are specified padding constants
● overhead is just hash calculations on 3 more blocks than hashing the message alone
● any hash function can be used
○ eg. MD5, SHA-1, RIPEMD-160 (obsolete, not recommended) ○ SHA-2, SHA-3 (recommended)
HMAC: Security
Integrity & Authentication
● proved: security of HMAC relates to that of the underlying hash algorithm
● attacking HMAC requires either:
○ brute force attack on key used (2n)
○ birthday attack (but since keyed would need to observe a very large number of MAC’d messages)
■ Collision resistant attacks, an adversary wishes to find 2 messages that yield the same hash (attack needs ~2n/2 MAC’d messages)
● choose hash function used based on speed vs security constraints
MACs: Combining with Encryption
Integrity & Authentication
● for secure communication, need both: ○ CONFidentiality
○ INTegrity
● can combine: authentication + encryption
○ e.g.encrypt-then-MAC
○ useseparatekeysforencrypt&MACtoavoidsecurityvulnerabilities ○ docarefullytopreservesecurityofbothmechanisms
● In practice: use efficient & secure authenticated encryption modes of block ciphers:
● e.g. GCM authenticated encryption mode [NIST 2007], will not cover in detail)
PKC for INTegrity & AUTH
Integrity & Authentication
● if public-key encryption / signature is used:
○ Pub key encryption provides no authentication of sender
■ since anyone potentially knows public-key ○ however if
■ senders signs the message using their private-key ■ then encrypts with recipient’s public key
■ Then we have both CONFidentiality and AUTHentication ○ Cost: two public-key mechanisms
Further Reading
Integrity & Authentication
• Chapter 2 (Section 2.2) and Chapter 21 (Sections 21.1-21.2) of the textbook: Computer Security: Principles and Practice” by & , , 2015
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com