Power Analysis of MACKeccak: A SideChannel Attack
Presentation
Term Paper
AbstractIn the spring of 2017, two documents were discovered to have the same hash value when run through the Secure Hashing Algorithm 1 (SHA1) cryptographic hash algorithm. This discovery is an indicator that SHA1 may not be secure for much longer. One consequence of a general attack upon SHA1 would be the security of hashbased message authentication codes (HMAC) that use SHA1 as their hash function. Because of this, many have begun to look towards Keccak, the finalist for NISTâ€™s SHA3 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 KeccakMAC (KMAC) construction proposed by NIST.
Overview
Table of Contents
 Introduction
 SideChannel Attack
 Power Analysis
 Simple Power Analysis (SPA)
 Differential Power Analysis (DPA)
 Correlation Power Analysis (CPA)
 KECCAK
 DPA Against MACKeccak
 CPA Against MACKeccak
 Counter Measures
 Masking
 KMAC
 Conclusion

Definitions
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 MerkelDamgard construction found in many cryptographic hash algorithms, including SHA1.
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.
SideChannel Attack: An attack that gleans secret information from the physical effects produced by running a cryptographic operation on a device.
Power Analysis: A sidechannel 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 x_{1},...,x_{i} and f(x_{1}),...,f(x_{i}), an adversary cannot predict f(x_{i+1}) for any x_{i+1}.
KECCAK: A family of sponge functions that use KECCAKf 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 KECCAKf[1600], where 1600 is the size of the internal state in bits.
KECCAKp[b,n_{r}]: A specification of the underlying function KECCAKf, where b is the size of the functions internal state in bits, and n_{r} is the number of rounds carried out within the function.
KECCAKf[b]: A specialization of KECCAKp[b,n_{r}] where n_{r} is equal to 12+2l and l=log_{2}(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.
 [1] Bertoni, G., Daemen, J., Peeters, M., Assche, G. V., and Keer, R. V. Note on sidechannel attacks and their countermeasures. https://keccak.team/files/NoteSideChannelAttacks.pdf
 [2] Bertoni, G., Daemen, J., Peeters, M., Assche, G. V., and Keer, R. V. Team keccak. https://keccak.team/files/index.html
 [3] Bertoni, G., Daemen, J., Peeters, M., and Van Assche, G. Cryptographic Sponge Functions. 2011.
 [4] Bertoni, G., Daemen, J., Peeters, M., and Van Assche, G. The KECCAK Reference. 2011.
 [5] Bertoni, G., Daemen, J., Peeters, M., and Van Assche, G. The KECCAK SHA3 Submission. 2011.
 [6] Brier, E., Clavier, C., and Olivier, F. Correlation Power Analysis with a Leakage Model. Springer, Heidelberg, 2004.
 [7] Kocher, P., Jaffe, J. Jun, D., and Rohatgi, P. Introduction to Differential Power Analysis. Springer, Heidelberg, 2011.
 [8] Luo, P., Fei, Y., Fang, X., Ding, A., Kaeli, D., and Leeser, M. SideChannel Analysis of MACKeccak Hardware Implementations. In Proceedings of the Fourth Workshop on Hardware and Architectural Support for Security and Privace (2015).
 [9] Lynn, B. PseudoRandom Functions. Retrieved Feb 20, 2018: https://crypto.stanford.edu/pbc/notes/crypto/prf.html
 [10] National Institute of Technology and Information, FIPS PUB 198: The KeyedHash Message Authentication Code (HMAC). National Institute of Technology and Information, Gaithersburg, 2002.
 [11] National Institute of Technology and Information, FIPS PUB 202: SHA3 Standard: PermutationBased Hash and ExtendableOutput Functions. National Institute of Technology and Information, Gaithersburg, 2015.
 [12] National Institute of Technology and Information, NIST Special Publication 800185: SHA3 Derived Functions. National Institute of Technology and Information, Gaithersburg, 2016.
 [13] Stinson, D. R., Crytography: Theory and Practice, 3rd Ed.. Chapman & Hall/CRC, Boca Raton, 2006.
 [14] Taha, M., and Schaumont, P. Differential Power Analysis of MACKeccak at Any KeyLength. Springer, Heidelberg, 2013.
 [15] Tran, X. Power Analysis Attacks on Keccak. RIT Scholar Works, Rochester, 2015.
 [16] Zohner, M., Kasper, M., Stottinger, M., and Huss, S. Side Channel Analysis of the SHA3 Finalists. In Design, Automation Test in Europe Conference Exhibitions(2012), pp. 10121017.