Power Analysis of MAC-Keccak: A Side-Channel Attack
In the spring of 2017, two documents were discovered to have the same hash value when run through the Secure Hashing Algorithm 1 (SHA-1) cryptographic hash algorithm. This discovery is an indicator that SHA-1 may not be secure for much longer. One consequence of a general attack upon SHA-1 would be the security of hash-based message authentication codes (HMAC) that use SHA-1 as their hash function. Because of this, many have begun to look towards Keccak, the finalist for NIST’s SHA-3 competition. However, a number of attacks have been proposed against Keccak. Perhaps most dangerous amongst these are side channel attacks that retrieve secret information by taking advantage of the physical effects of running a cryptographic operation on a device. This paper discusses two proposed attacks against Keccak based message authentication codes that make use of power analysis, a side channel attack that focuses on energy consumption. It then discusses different ways in which the effectiveness of power analysis may be reduced, including masking and the Keccak-MAC (KMAC) construction proposed by NIST.Overview
Table of Contents
- Side-Channel Attack
- Power Analysis
- Simple Power Analysis (SPA)
- Differential Power Analysis (DPA)
- Correlation Power Analysis (CPA)
- DPA Against MAC-Keccak
- CPA Against MAC-Keccak
- Counter Measures
Length Extension Attack: An attack against a MAC whereby an adversary appends information to a message and forges a valid MAC by passing the intercepted MAC and the additional information to the compression portion of the hash function. This is a significant weakness of the Merkel-Damgard construction found in many cryptographic hash algorithms, including SHA-1.
HMAC (Hashed Message Authentication Code): A nested MAC algorithm built from the composition of two families of keyed hash functions, G and H. This construction prevents length extension attacks. The security of HMAC relies upon the functions H being secure as a MAC with an unknown key, and the functions G being collision resistant with an unknown key.
Side-Channel Attack: An attack that gleans secret information from the physical effects produced by running a cryptographic operation on a device.
Power Analysis: A side-channel attack that determines secret information of a cryptographic operation by analyzing the power consumption of a device as it runs the cryptographic operation.
Power Trace: Sequence of measurements of a device's power consumption taken across the execution of a cryptographic operation on the device.
Simple Power Analysis: Focuses on features of a power trace that are directly visible.
Differential Power Analysis: Uses statistical methods on collection of power traces to determine secret information.
Correlation Power Analysis: Uses correlation coefficients on a collection of power traces to determine secret information.
Sponge Construction: Specifies families of functions with arbitrary output length.
Sponge Function: A family of functions produced by a sponge construction with: a unique underlying function f, a bit rate r, and a padding rule pad.
XOF (Extendable Output Function): A function that produces an output of any length including infinity. This is useful for when a user wants a specific length or does not know the desired output length before running the function.
PRF (Pseudo Random Function): A function f such that given x1,...,xi and f(x1),...,f(xi), an adversary cannot predict f(xi+1) for any xi+1.
KECCAK: A family of sponge functions that use KECCAK-f as the underlying function.
KECCAK[c]: A subset of the KECCAK family that determines its bit rate r according to an entered capacity c. In addition, its underlying function is KECCAK-f, where 1600 is the size of the internal state in bits.
KECCAK-p[b,nr]: A specification of the underlying function KECCAK-f, where b is the size of the functions internal state in bits, and nr is the number of rounds carried out within the function.
KECCAK-f[b]: A specialization of KECCAK-p[b,nr] where nr is equal to 12+2l and l=log2(b/25).
SHAKE: A mode of any KECCAK function that transforms it into a XOF where the length of the output is determined by the user and need not satisfy c=2d, where c is the capacity and d is the desired length. When the length entered is zero, SHAKE produces an infinite output.
cSHAKE: A function that accepts a message X, an output length L, a function name bit string N, and a customization bit string S. When S and N are both equal to the empty string, the result is a call to SHAKE; otherwise it is a call to KECCAK where encoded and padded versions of N and S are appended to X.
KMAC (KECCAK Message Authentication Code): A MAC algorithm built using KECCAK. Unlike HMAC, KMAC does not use a nested construction since its underlying function, KECCAK, is resistant to the length extension attack. KMAC takes as arguments a message X, a secret key K, an output length L, and a customizaiton bit string S. After prepending and appending encoded and padded versions of K and L to X, the result is passed to cSHAKE along with L, S, and the string "KMAC".
Masking: Represent secret information using two or more shares. The shares are used in such a way that there is never any correlation to the original value.
-  Bertoni, G., Daemen, J., Peeters, M., Assche, G. V., and Keer, R. V. Note on side-channel attacks and their countermeasures. https://keccak.team/files/NoteSideChannelAttacks.pdf
-  Bertoni, G., Daemen, J., Peeters, M., Assche, G. V., and Keer, R. V. Team keccak. https://keccak.team/files/index.html
-  Bertoni, G., Daemen, J., Peeters, M., and Van Assche, G. Cryptographic Sponge Functions. 2011.
-  Bertoni, G., Daemen, J., Peeters, M., and Van Assche, G. The KECCAK Reference. 2011.
-  Bertoni, G., Daemen, J., Peeters, M., and Van Assche, G. The KECCAK SHA-3 Submission. 2011.
-  Brier, E., Clavier, C., and Olivier, F. Correlation Power Analysis with a Leakage Model. Springer, Heidelberg, 2004.
-  Kocher, P., Jaffe, J. Jun, D., and Rohatgi, P. Introduction to Differential Power Analysis. Springer, Heidelberg, 2011.
-  Luo, P., Fei, Y., Fang, X., Ding, A., Kaeli, D., and Leeser, M. Side-Channel Analysis of MAC-Keccak Hardware Implementations. In Proceedings of the Fourth Workshop on Hardware and Architectural Support for Security and Privace (2015).
-  Lynn, B. Pseudo-Random Functions. Retrieved Feb 20, 2018: https://crypto.stanford.edu/pbc/notes/crypto/prf.html
-  National Institute of Technology and Information, FIPS PUB 198: The Keyed-Hash Message Authentication Code (HMAC). National Institute of Technology and Information, Gaithersburg, 2002.
-  National Institute of Technology and Information, FIPS PUB 202: SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions. National Institute of Technology and Information, Gaithersburg, 2015.
-  National Institute of Technology and Information, NIST Special Publication 800-185: SHA-3 Derived Functions. National Institute of Technology and Information, Gaithersburg, 2016.
-  Stinson, D. R., Crytography: Theory and Practice, 3rd Ed.. Chapman & Hall/CRC, Boca Raton, 2006.
-  Taha, M., and Schaumont, P. Differential Power Analysis of MAC-Keccak at Any Key-Length. Springer, Heidelberg, 2013.
-  Tran, X. Power Analysis Attacks on Keccak. RIT Scholar Works, Rochester, 2015.
-  Zohner, M., Kasper, M., Stottinger, M., and Huss, S. Side Channel Analysis of the SHA-3 Finalists. In Design, Automation Test in Europe Conference Exhibitions(2012), pp. 1012-1017.