## 3 Multiplication Methods over \(GF(2^{m})\) on 8-bit AVR MCUs
### Secure Block-Comb Multiplication Methods  
Since Block-Comb multiplication methods do not utilize any Lookup Table, they have resistance against a sort of horizontal correlation analysis [11; 15], which was used for analyzing LUT-based methods. However, they are vulnerable to TA and SPA because they contain a conditional branch. Algorithm A1 in Appendix A shows a simple 56-bit wise Block-Comb multiplication method. Steps 11-15 are executed only when the \(l\)-th bit of the multiplier is 1, which is the source of TA and SPA vulnerability. In 2018, [PERSON] et al. [11; 15] presented a masked version of the Block-Comb (MBC) technique for secure GCM implementation on 8-bit AVR MCUs. Algorithm A1 is the masked Block-Comb method and it basically operates on 32-bit wise (Algorithm 1). The algorithm replaces the conditional branch with masked XOR operations for SPA and TA resistance. For instance, if the tested bit (\(BIT\)) at step 3 is 0, then zero values (\(B[m]\&0x00\)) are XORed with the accumulator \(C\) through steps 5-7. Otherwise, normal values (\(B[m]\&0 xFF\)) are XORed with the accumulator \(C\). They combined the MBC with the Karatsuba technique for computing a 128-bit \(BF\) multiplication. It is reported that [PERSON] et al. 's 128-bit \(BF\) multiplication took 14,878 \(cc\). Even though MBC achieves TA security, it still has the vulnerability of SPA in contrast to [PERSON] et al. 's assertion. In other words, XORing with zero value (\(B[m]\&0x00\)) when the tested bit is 0 has a different power consumption pattern compared with XORing with original value (\((B[m]\&0 xFF)\)) when the tested bit is 1. [PERSON] et al. showed that [PERSON] et al. 's MBC is still vulnerable to SPA in their recent work [10]. Most recently, [PERSON] et al. proposed a novel secure Block-Comb method, which has resistance against TA and SPA (in addition, their method is resistant against a sort of horizontal CPA because it does not use any Lookup Table) for a secure GCM implementation on 8-bit AVR MCUs [10]. Similar to MBC, [PERSON] et al. 's method has made use of a 32-bit wise Block-Comb multiplication method. For making a 32-bit wise Block-Comb multiplication method secure against SPA, they introduced the concept of Dummy XOR operations with a set of garbage registers. In other words, the count of registers for the accumulator \(C\) is doubled from 8 registers to 16 registers (\(R_{15},\ldots,R_{0}\)). Thus, their method makes use of 25 registers in total (\((R_{15},\ldots,R_{0})\) for accumulator \(C\), \((R_{20},\ldots,R_{16})\) for multiplicand \(A\), and \((R_{24},\ldots,R_{21})\) for multiplier \(B\)), which is acceptable in 8-bit AVR MCUs having 32 registers. Among \((R_{15},\ldots,R_{0})\) registers, the set of \((R_{7},\ldots,R_{0})\) plays the role of the garbage registers, and the set of \((R_{15},\ldots,R_{8})\) maintains the real intermediate result of the multiplication. With the Dummy XOR operations with garbage registers, the multiplicand is XORed at a different position relying on the value of the tested bit. For instance, if the tested bit is 0, the registers \((R_{20},\ldots,R_{16})\) containing the multiplicand are XORed with the garbage registers \((R_{7},\ldots,R_{0})\). Otherwise, the same registers are XORed with the part of real accumulator \((R_{15},\ldots,R_{8})\). Since the registers keeping real multiplicand values are XORed with the accumulator registers in both cases, the power consumption patterns for both cases are not distinguishable each other with respect to SPA. In order to implement this concept of Dummy XOR as being secure against TA, they introduced the concept of instruction level atomicity \((ILA)\). On 8-bit AVR MCUs, typically the branch instructions consume different clock cycles relying on whether the tested condition is true or not. For instance, if the condition is false (resp. true), it usually takes 1 clock cycle (resp. 2 clock cycles).