## 3 Multiplication Methods over \(GF(2^{m})\) on 8-bit AVR MCUs
### Look-Up Table-Based Methods  
So, as to enhance the performance of field multiplications of the GHASH function in GCM, firstly [PERSON] et al. presented a table-based method using different sizes considering the trade-off between computational speed and memory consumption [16; 17] in their GCM implementation. They used different sized tables: a version of 256 bytes, a version of 4 Kbytes, a version of 8 Kbytes, and a version of 64 Kbytes and measured the performance on a 32-bit Motorola G4 device. Although their table-based methods are efficient regarding computational speed, memory consumption is too huge to be utilized on 8-bit AVR MCUs. Therefore, researchers usually have taken advantage of [PERSON] et al.'s Look-Up Table multiplication method [3; 4; 5], originally aimed for field multiplication of binary elliptic curves operation [2; 14] when implementing the GCM algorithm on resource-limited embedded devices, including AVR and MSP430.  
[PERSON] et al.'s LUT-based technique is an extended version of LtR Comb technique (it is called the \(w\)LtR Comb technique) [2; 14]. The \(w\)LtR Comb technique calculates a multiplication by \(w\)-bit wise rather than single-bit wise at the cost of building a precomputation table. Thus, it can reduce the count of bit operations, like bit XOR and shift operations [2; 4; 14; 18]. At the beginning of the multiplication, it computes all possible results of \(A\cdot u(z)\) about all polynomials \(u(z)\) of degree at most \(w-1\) and stores them in a kind of precomputation table. Then, in the actual multiplication process, multiplier \(B\) is scanned by \(w\)-bit at a time from the left (MSB) to right (LSB) direction, and the corresponding value from the precomputation table is chosen. Namely, the corresponding value from the table is XORed with the intermediate value in the accumulator without actual computation. On 8-bit AVR MCUs, it is widely believed that 4-bit is the most favorable width \(w\) for this \(w\)LtR Comb technique. Therefore, it makes use of \(16\times m\)-bit of RAM memory for maintaining the precomputation table consisting of sixteen multiplication results from \(0\cdot A\) to \((z^{3}+z^{2}+z+1)\cdot A\). This LUT-based method and its variants have been broadly implemented on 8-bit AVR devices [3; 4; 5]. For instance, 163-bit binary field multiplication was implemented by NesC language on an ATmega128 MCU in [PERSON] et al.'s work [3], and it was upgraded by integrating two iterations of the main loop into one, decreasing the count of redundant memory accesses. [PERSON] et al. got 19,670 \(cc\) as the timing result for a field multiplication over \(GF(2^{163})\), which was a 21.1% improvement. In [4; 5], [PERSON] et al. proposed a concept of a rotating register technique in the \(w\)LtR Comb method, and it could greatly decrease the count of redundant memory accesses necessary for executing a multiplication method. Their method was implemented in AVR Assembly language and they reported 4508 \(cc\), 8314 \(cc\), and 11,727 \(cc\) for calculating a multiplication over \(GF(2^{163})\), \(GF(2^{233})\), and \(GF(2^{271})\), respectively. LUT-based multiplication methods give not only good performance but also are resistant against both TA and SPA. However, they are vulnerable to side channel attacks, which uses information about the memory address [11; 12; 19] owing to the large number of resulted memory accesses. In [11; 15], [PERSON] et al. successfully analyzed the \(w\)LtR Comb multiplication technique with a sort of horizontal correlation analysis [12]. Namely, they could get the indices used for accessing LUT by using the correlation between power consumption traces from building up the Lookup table and referencing the LUT element during the process of a multiplication.