1、Generic Attacks against MACs( (消息認(rèn)證碼的安全分析消息認(rèn)證碼的安全分析) )Lei WangLab of Cryptography and Computer Security (LoCCS)Shanghai Jiao Tong UniversityChinaCrypt 2015Modern Cryptography Main objectives: confidentiality; authenticity Applications of authenticity email signature, credit cards, software update, e

2、tc. Cryptographic protocols of authenticity asymmetric-key: digital signature; symmetric-key: message authentication code (MAC)MAC Symmetric-key: Alice and Bob share secret key before communications. Provide authenticity and integrity: Bob verifies if T=T holds.AliceBobM T(M, T)MMACKMACK TSecurity N

3、otions Key recovery: extract the key of MAC Forgery: forge a valid (M, T) for a MAC existential forgery: M is chosen by attacker after interaction; selective forgery: M is chosen by attacker before interaction; universal forgery: M is given to attacker before interaction; Distinguishers distinguishi

4、ng-R: distinguish MACH from a random function (RF); distinguishing-H: distinguish MACH from MACRFSecurity Evaluation Provable security reduction-based: assume underlying primitive is secure. lower bound of MAC Generic attack attacks work for any choice of underlying primitive. upper bound of MACHow

5、to Build MAC Hash function based HMAC, Sandwich-MAC, Envelope-MAC Block cipher based CBC MAC, CMAC, PMAC Universal hash function based UMAC, VMAC, Poly1305 Dedicated design SQUASH, SipHash, PelicanRemaining of this Talk Hash function based HMAC, Sandwich-MAC, Envelope-MAC Block cipher based CBC MAC,

6、 CMAC, PMAC Universal hash function based UMAC, VMAC, Poly1305 Dedicated design SQUASH, SipHash, PelicanOutlook Introduction hash-based MAC known results Functional-graph-based attacks functional graph related-key attacks single-key attacks ConclusionCryptographic Hah Function Map arbitrary-length d

7、ata to short random digest Digest acts as fingerprint of original datadata256/512-bit digestIterative Hash Function CF: fixed-input-length compression function CF: finalization functionIterative Hash Based MACNotable Example: HMAC Designed by Bellare et al. BCK96 Standardized by ANSI, ETF, ISO, NIST

8、 Wide applications, beyond mere MAC authentication: SSL, IPSec; identification: POP3, IMAP; key-derivation: IPSec, TLS.Notable Example: HMAC13Provable SecurityGeneric Attack: Internal-Collision-Basedcollision15Results on Hash-based MACs until 2012: internal collision based attackSecurity proof(lower

9、 bound)Generic attack(upper bound)Distinguishing-RtightDistinguishing-HExistential forgerytightSelective forgeryUniversal forgeryKey recoveryResults on Hash-based MACs since 2012: functional graph based attacksSecurity proof(lower bound)Generic attack(upper bound)Distinguishing-RtightDistinguishing-

10、HtightExistential forgerytightSelective forgerytightUniversal forgeryKey recoveryOutlook Introduction hash-based MAC known results Functional-graph-based attacks functional graph related-key attacks single-key attacks Other generic attacks ConclusionFunctional Graph n-bit to n-bit function F can be

11、represented as a graph iteratively compute #components: #nodes: #cycle nodes: longest path: largest components Distinguishing-R Attacks on HMACRelated-Key Dis-R on HMAC PSW12 HMACKHMACKEquivalent HMACK HMACKCompare HMACK and HMACK HMACKHMACKCompare HMACK and HMACK HMACKHMACKNotation SimplificationNo

12、tation Simplification Essential Observations in PSW12 HMACK and HMACK have highly similar functional graph. In particular, the cycle in largest component has the same length.Related-Key Dis-R on HMAC PSW12 Ideal: compare the cycle length of the largest component Attack procedure:1. Select a random v

13、alue X, iteratively query to get a cycle, denote its length as L.2. Similarly get a cycle length L for 3. Compare if L=L yes: is (MACK, MACK) no: are (R, R) Related-Key Dis-R on HMAC PSW12Application to Other Notions PSW12Outlook Introduction hash-based MAC known results Functional-graph-based attac

14、ks functional graph related-key attacks single-key attacks Other generic attacks ConclusionDis-H Attack on Hash-based MACs?How to Exploit Functional GraphTechnical Novelty in LPW13 Construct a pair of messages: equal length: padding issue; collide at the internal state with a high probability;Collid

15、ing Message Pair in LPW13 Enter cycle twice to have equal length. Colliding Message Pair in LPW13Colliding Message Pair in LPW13Colliding Message Pair in LPW13 Jump out from the cycle loop.Colliding Message Pair in LPW13 Re-enter the cycle of largest componentColliding Message Pair in LPW13 Loop ins

16、ide cycle again, and output collide. Colliding Message Pair in LPW13 Final outputs collide, since two messages have equal length.Colliding Message Pair in LPW13 Overall, this message pair collide with a constant probability. Dis-H Attack in LPW13Dis-H Attack in LPW13Selective Forgery GPSW14Universal

17、 Forgery on Hash-Based MACs46Difficulty of Universal ForgeryCan We Derive More Information?Can We Derive More Information? Yes, we can!Can We Derive More Information?cycle node?50What is Interesting Information?cycle node!Universal Forgery PW14, GPSW141000001232Universal Forgery PW14, GPSW14Universa

18、l Forgery PW14, GPSW14 Phase 2: construct a second preimage to forge second preimage attack on iterative hash function KS05 query collisionOther Functional-Graph Based AttacksPre-computationTimeMemoryHellmans tradeoffdivide-and-recoverGPSW14Outlook Introduction hash-based MAC known results Functional-graph-based attacks functional graph related-key attacks single-key attacks