# Single Trace Analysis on Constant Time CDT Sampler and Its Countermeasure
## 3 Single Trace Analysis on a CDT Sampler
### Attack on the CDT Sampler  
This section describes how to recover the sampled values through a single power consumption trace by using the result from the previous section. Although Algorithm 2 casts the value to an unsigned integer, the very moment when the difference between the sampled value and the table value is calculated can be captured in power consumption trace. In other words, high power consumption indicates that the negative value is calculated and hence 1 is added to the variable \(S\). On the contrary, low power consumption indicates that the positive value is calculated so that 0 is added to the variable. For the experiment, a CDT sampler in Algorithm 2 with the table of length 9 was implemented in ATmega128. We sampled 100 times by selecting 100 different random value. In order to clearly capture when the CDT is processed, Algorithm 2 was repeated 10 times with the selected random number as input. The power consumption traces were collected using a LeCroy HDO6104A oscilloscope at a sampling rate of 250 M/s. We used a low pass filter on the collected power consumption traces to reduce noise. Figure 2 illustrates the entire power consumption trace of our implementation, which is then zoomed into the region of interest. As depicted in Figure 2, we can see 10 identical iterations where its unit is marked with a white arrow line. To better represent the power consumption trace of one execution of the CDT sampler, we cut the power consumption trace into each execution of an algorithm. The bottom of Figure 2 illustrates the power consumption trace when a single value is sampled. If the power consumption of sampling is identical to every random value, that is, if the algorithm resists against STA, then the power consumption trace of sampling with certain random values will be identical to the power consumption trace of sampling with any other random values. However, this is not the case for the currently used constant-time CDT sampler. Due to the gap of the Hamming weight of the negative and positive values, the sign of the subtracted result is reflected in the power consumption trace. Figure 3a,b illustrates when the subtracted result is negative and positive, respectively. The power consumption trace when 1 or 0 was added is marked as a black line over gray-colored trace as shown in the figure below. As illustrated in Figure 3, the sign of the subtracted result can be detected through power consumption trace. Figure 2: Part of a single execution of the algorithm. The sign of the sampled bit can also be revealed through STA. Step 6 in Algorithm 2 depends on the sign bit selected in step 3. If 0 is selected, then the result of the sampled value is positive, and negative otherwise. Step 6 in Algorithm 2 flips the variable \(S\) when the sign bit is 1 and remains the same when the sign bit is 0. Therefore, this process is visible through power consumption trace. Figure 4 illustrates the power consumption trace when the sign bit is 1 and 0. For a clear comparison, Figure 5 is the overlapped power consumption trace of Figure 3(a),b. The black power consumption trace illustrates when the sign bit is 1 and the red power consumption trace illustrates when the sign bit is 0. Combining the information in Figures 3 and 4, an attacker can determine the sampled values exactly through a single power consumption trace. To justify our observation, we constructed a tool to  
Figure 4: (a) power consumption trace when the sign bit is 1; (b) power consumption trace when the sign bit is 0. Figure 5: Overlapped power consumption trace of Figure 3(a),b. The black line illustrates when the sign bit is 1 and the red line illustrates when the sign bit is 0. Figure 3: (a) power consumption trace when the subtracted result is negative; (b) power consumption trace when the subtracted result is positive. extract the sampled value automatically given a power consumption trace. First, we divided the power consumption trace into one execution of the algorithm. In our experiment, each execution consists of 6160 points.