# Single Trace Analysis on Constant Time CDT Sampler and Its Countermeasure
## 3 Single Trace Analysis on a CDT Sampler
### Attack on the CDT Sampler
For each partitioned trace, eight iterations were visible, with each iteration consisting of 577 points on average. For example, step 4 starts approximately at 1,154, 1731, 2307, 2883, 3460, 4036, 4615, and 5192. Figure 6 illustrates the part of the single execution of the algorithm, where the red lines indicate when step 4 starts. In order to visualize the difference of the graph when the subtraction result is positive or negative, power consumption traces when 6 and 2 are sampled through Algorithm 2 are overlapped in Figure 6. The blue power consumption trace illustrates when 6 is sampled and black power consumption trace illustrates when 2 is sampled. In our implementation, the sampled value is equal to the number of the subtractions that result in a negative value out of eight subtractions. Therefore, compared to the case when two are sampled, four more of the subtracted result is negative when six is sampled and is visualized as shown in the blue shaded rectangle as in Figure 6. Particularly, the difference between the power trace when the subtracted result is positive and negative was most noticeable after 157 points for each iteration on average. An example of such difference is illustrated in the blue shaded rectangle in Figure 6, which consists of 284 points on average. This means that the difference between the average power consumption when 0 or 1 is distinct so that an attacker can set a threshold to divide the gap. From our experiment, when the average is greater than -1, we assumed that the subtracted result was negative so that 1 was added to the variable \(S\). Let \(x(i)\) be the point where the \(i\)-th loop starts. By calculating the average between \(x(i)+157\) and \(x(i)+441\) and comparing it with -1, we were able to deduce whether 1 or 0 was added to the variable. In this way, we were able to recover 1000 sampled values out of 1000 number of power consumption traces in Figure 1 and 100 sampled values out of 100 number of power consumption traces in Figure 2. Since the difference between the average power consumption of negative and positive is apparent, we believe that full recovery of the sampled value is possible even with a large number of samples. To summarize the attack, STA on a CDT sampler can be performed as follows: suppose that an attacker obtains a power consumption trace that samples 2000 values. The attacker first divides the power consumption trace into each execution of the algorithm, which results in 2000 number of sub-traces. For each sub-trace, an attacker identifies loops of an algorithm. The number of loops must equal the number of table length. By overlapping the sub-traces, an attacker approximates the location where step 5 of the Algorithm 2 is processed. Next, by averaging the power consumption where one or zero adds, an attacker sets a threshold \(t\). For each loop of the sub-trace, an attacker averages the power consumption trace and compares it with the threshold. If the average is greater than \(t\), then the subtracted result is negative so that one is added to \(S\). If the average is smaller than \(t\), then the subtracted result is positive so that zero is added. An attacker can recover the sampled value  
Figure 6: Part of a single execution of the algorithm. The black line is the power consumption trace when 6 is sampled, and red line is the power consumption trace when 2 is sampled. The blue area indicates the difference between the power consumption traces. since the summation of the number of 1s added is equal to the value sampled. The sign of the sampled value can be revealed with the similar process. Note that the CDT sampler is more vulnerable to such an attack if casting to an unsigned type is not used in step 5 of Algorithm 2. If the right shift of the difference is not unsigned, then -1 is added to the variable \(S\) making the gap wider. This results in more visibility in the power consumption graph.