Fast Frame Rate Estimation in Electromagnetic Side-Channel Attacks on Public Systems

Abstract

Frame refresh rate estimation is a fundamental step in identifying compromising harmonic frequencies in electromagnetic side-channel attacks. Methods based on discrete linear autocorrelation (DLA) are robust across different scenarios and require a computational complexity of $O(N\log N)$ for a signal containing $N$ samples. This work proposes reducing this complexity to $O(N)$ by exploiting prior knowledge of the target system’s display resolution, as is available for certain models of the Brazilian electronic voting machine. Experiments using software-defined radios show that the proposed method preserves the accuracy of the conventional approach in the evaluated scenarios.

1 Introduction

Electromagnetic side-channel attacks (e-SCAs) refer to a class of security threats in which sensitive information is inferred from unintentional electromagnetic emissions produced by the movement of electric charges. These attacks are commonly known as TEMPEST attacks [1]. In this work, we use the term TEMPEST specifically to denote e-SCAs targeting video devices.

A critical challenge in TEMPEST attacks is estimating the frame refresh rate (FRR) from the leaked signal, which is necessary to reconstruct the intercepted image and helps identify a compromising harmonic frequency. Various methods for FRR estimation have been considered in the literature [8], [2], [7]. Among these, discrete linear autocorrelation (DLA) stands out as a popular method in practical TEMPEST libraries because of its effective estimation across diverse scenarios [3], [6].

This work proposes a method to reduce the computational complexity of DLA from $O(N\log N)$ to $O(N)$ in scenarios where the target system’s display resolution is known beforehand, as observed in [11] for some Brazilian electronic voting machine (UEB) models currently in use. The proposed method is validated using real TEMPEST signals obtained in experiments with software-defined radio (SDR).

2 TEMPEST Signal Model

This section introduces the theoretical foundations of this work. First, Subsection 2.1 presents the TEMPEST signal parameters required by the proposed method. Next, Subsection 2.2 presents the DLA method, whose computational complexity is optimized in this work.

2.1 Basic TEMPEST Parameters

The VGA signal assumed in this work can be modeled as a sum of rectangular pulses:

$$x(t)=\sum_{n=-\infty}^{\infty}x[n]p(t-nT_{p}),$$ (1)

where $x(t)$ represents the real-valued continuous-time signal at time $t$. The period (i.e., duration) $T_{p}$ of each pixel (pulse) in the cable depends on the display resolution and frame refresh rate. $T_{p}$ can be defined as

$$T_{p}=\frac{1}{P_{x}P_{y}f_{v}}\quad\textrm{s},$$ (2)

where $P_{x}$, $P_{y}$, and $f_{v}$ denote the number of pixels per line (including synchronization pixels, i.e., blanking pixels), the number of lines per display frame, and the refresh rate, respectively. TEMPEST attacks are made possible by distortions inherent in the analog components of the video system, which cause leakage at harmonic frequencies that are multiples of the pixel rate [1], [4], [5]. An adversary who tunes an SDR to one of these frequencies can recover the image carried by the signal.

2.2 FRR Estimation Using the DLA Method

After acquiring the raw signal using an SDR in a TEMPEST attack, the frame refresh rate $f_{v}$ must be estimated. The DLA method relies on identifying the dominant peak of the autocorrelation function. For a discrete complex-valued signal $x[n]$ containing $N$ samples, the autocorrelation at lag $\tau$ is given by

$$R_{xx}(\tau) = \sum_{n=\tau}^{N-1}x[n]x^{*}[n-\tau],\qquad 0\leq\tau<N,$$ (3)

where $x^{*}[n]$ denotes the complex conjugate of $x[n]$. For a sampling rate $f_{s}$, the FRR estimate is obtained as

$$f_{v} \approx f_{s}/\tau_{\max},$$ (4)

where $\tau_{\max}$ is the lag associated with the highest peak in (3).

A direct implementation of DLA evaluates the autocorrelation at all lags of interest, resulting in a complexity of $O(N^{2})$. To reduce this cost, widely used TEMPEST tools [3], [6] rely on the Wiener–Khinchin theorem, according to which autocorrelation can be obtained from the inverse Fourier transform of the signal’s power spectrum. Thus, using the fast Fourier transform (FFT) algorithm and its inverse (IFFT), the DLA method runs in $O(N\log N)$ time. Although efficient in the general case, the computational cost of processing signals containing millions of samples—such as the TEMPEST signals considered in this work—may become a limiting factor in critical applications subject to stringent timing constraints, as demonstrated in [9].

3 The Fast DLA (F-DLA) Method

The proposed method, called F-DLA (fast DLA), reduces the computational complexity of conventional DLA by exploiting TEMPEST scenarios in which the parameters $P_{x}$ and $P_{y}$ may be known a priori. Although this is a strong assumption in general TEMPEST scenarios, the assumption that the target system’s parameters are unknown can be relaxed in contexts governed by transparency principles, as in the Brazilian electoral system. Public specifications establish resolutions of $1280\times 768$ for the UE2013/UE2015 models [12] and at least $1280\times 720$ for the UE2020 model [13]. Thus, even without prior knowledge of the model in use, the VESA standard restricts the set of candidate FRRs to only $R=4$ values for these resolutions: 60, 75, 85, and 120 Hz [15]. Accordingly, the first significant autocorrelation peak is expected at one of the lags $\{f_{s}/60,f_{s}/75,f_{s}/85,f_{s}/120\}$, with $R=O(1)$ with respect to $N$.

Correct operation of the DLA method assumes that channel-induced distortions do not shift the dominant autocorrelation peak beyond the interval associated with the correct FRR. Otherwise, even conventional DLA would produce an incorrect estimate. Therefore, in scenarios where conventional DLA operates correctly, the shift $\delta$ must remain bounded by a constant independent of $N$. Consequently, only the lags within a neighborhood of $\delta$ samples around the $R$ candidates need to be evaluated. Since $R=O(1)$ and $\delta=O(1)$, the set $\mathcal{T}$ of candidate lags whose autocorrelation values must be evaluated has size

$$|\mathcal{T}|=(2\delta+1)R=O(1).$$ (5)

Similarly to Eq. (4), F-DLA estimates the FRR as

$$f_{v} \approx \frac{f_{s}}{\tau_{F\textrm{-}DLA}},$$ (6)

where $\tau_{F\textrm{-}DLA}\in\mathcal{T}$ is the lag that maximizes the autocorrelation function:

$$R_{xx}(\tau_{F\textrm{-}DLA})=\max_{\tau\in\mathcal{T}}R_{xx}(\tau)$$ (7)

Since each lag in $\mathcal{T}$ is evaluated in $O(N)$ time (3) and this list has constant size (5), the overall complexity of F-DLA is

$$T_{F-DLA}(N)=|\mathcal{T}|N=O(N),$$ (8)

which is therefore lower than the $O(N\log N)$ complexity of conventional DLA. Under severe channel degradation, the assumption $\delta=O(1)$ may no longer hold, compromising FRR estimation by both DLA and F-DLA. Since this work aims to validate F-DLA as an alternative to DLA in at least one real-world scenario, evaluation under degraded channel conditions is left for future work.

4 Preliminary Results

This section compares the proposed F-DLA method with conventional DLA in terms of execution time and the accuracy of the $f_{v}$ estimate, using signals obtained in a real SDR-based TEMPEST experiment. The experiments used a VGA monitor displaying the UEB interface (available in [14]), configured with an FRR of $f_{v}=60$ Hz and a display resolution of $1280\times 720$, compatible with the UE2020 model. For this configuration, $P_{x}=1650$ pixels and $P_{y}=750$ lines per frame, according to the VESA standard [15]. For further details on the results presented in this section, as well as additional results omitted owing to space limitations, the reader is referred to the lead author’s repository.

The video TEMPEST signal was captured using an Ettus USRP B200 SDR connected to a digital TV antenna positioned $\approx$ 20 cm from the monitor, with the SDR operating at a sampling rate of $f_{s}=54$ MHz. Both methods used $N=2^{21}$ samples. This number is sufficient to capture the minimum of two consecutive frames, corresponding to $2(f_{s}/f_{v})=1.8\times 10^{6}$ samples in the scenario considered. The xcorr function from GNU Octave’s signal package was used as the reference implementation of conventional DLA. For the proposed F-DLA method, the smallest value of $\delta$ that produced the correct $f_{v}$ estimate in the experiments was 1. Although preliminary, the experimental results support the theoretical gains discussed in Section 3. A more comprehensive experimental evaluation is planned for an extended version of this work.

Figure 1(a) shows the autocorrelation function of the TEMPEST signal whose image, reconstructed using the gr-tempest module [3], is shown in Fig. 1(b). The time lag $\tau_{s}$, in seconds, was obtained using $\tau_{s}=\tau/f_{s}$. The autocorrelation peak identified by F-DLA (red bar) at $\tau_{s}=0.016667$ s coincides with that obtained by DLA (blue curve) and corresponds to the expected FRR of $1/\tau_{s}\approx 60$ Hz. However, F-DLA produced this estimate in approximately 0.30 s, with a confidence interval (CI) of $\pm 0.01$ s (95% confidence), whereas conventional DLA required approximately 0.67 s, with a CI of $\pm 0.02$ s. The observed difference reflects implementation constants and optimizations in the xcorr function, as well as the asymptotic orders of the algorithms. This result indicates that restricting the set of candidate lags based on prior knowledge of $P_{x}$ and $P_{y}$, as in the case of the UEB, can reduce the computational cost of estimation without compromising FRR accuracy in the evaluated scenario.

(a) Autocorrelation function plot.

(b) TEMPEST image reconstructed from the experiments.

Figure 1: F-DLA (proposed) and DLA (conventional): FRR identification in an experimental TEMPEST channel. The autocorrelation peak at $\tau_{s}\approx 0.016667$ s obtained by both methods in (a) corresponds to the correct FRR of 60 Hz for the reconstructed image in (b).

5 Conclusion

This work presented Fast DLA (F-DLA), a low-complexity alternative for frame refresh rate estimation in TEMPEST attacks. The method exploits scenarios where the target graphics system’s parameters may be known a priori, restricting the set of candidate lags evaluated through autocorrelation. Under this assumption, the computational complexity was shown to decrease from $O(N\log N)$ to $O(N)$. Results from a real SDR-based TEMPEST experiment showed that F-DLA preserves the FRR estimation accuracy of conventional DLA while reducing processing time. Although preliminary, these results support the theoretical analysis and indicate the approach’s potential for applications with more stringent computational constraints. Future work will extend the experimental evaluation to different scenarios and parameters and consider complexity optimization techniques based on sparse FFTs, e.g., [10].