This continues from discussion of application security testing.

Data flow analysis is a static analysis technique for calculating facts of interest at each program point, based on the control flow graph representation of the program [vJ11, p. 1254].

A canonical data flow analysis is reaching definitions analysis [NNH99, Sec. 2.1.2].

For example, if statement $i$ is x := y◻z, where ◻ is any operator, and x is defined at statement $i$.

Reaching definitions analysis determines for each statement $j$ that uses variable x which previous statement defined x.

1 x := y + z;
2 w := x + z;
3 x := w;

More formally, data flow analysis can be expressed in terms of lattice theory, where facts about a program are modelled as vertices in a lattice.

The lattice meet operator determines how two sets of facts are combined.

Given an analysis where the lattice meet operator is well-defined and the lattice is of finite height, a data flow analysis is guaranteed to terminate and converge to an answer for each statement in the program using a simple iterative algorithm.

A typical application of data flow analysis to security is to determine whether a particular program variable is derived from user input (tainted) or not (untainted).

Given an initial set of variables initialised by user input, data flow analysis can determine (typically an over approximation of) all variables in the program that are derived from user data.

Kocher et al. [KJJ99] pioneered the method of differential power analysis (DPA).

A power trace is a set of power consumption measurements taken over a cryptographic operation; see Fig. 1 for an example.

Let us define simple power analysis (SPA) before we get into DPA. SPA is the interpretation of direct power consumption measurements of cryptographic operations like Fig. 1.

Watch a demonstration of SPA:

Most hard-wired hardware implementations of symmetric cryptographic algorithms have sufficiently small power consumption variations that SPA cannot reveal any key bit.

Unlike SPA, DPA is the interpretation of the difference between two sets of power traces.

More precisely, this difference is defined as

where

• $m$ is the number of traces;
• $j$ is the time index;
• $D(C_i,b,K_s)$ is the selection function which for the DES (see Figs. 2-3) is defined as the value of bit $b$ ($0\leq b\leq 31$) of the DES intermediate $L$ (see input to block E in Fig. 3) at the beginning of the 16th round for ciphertext $C_i$ when $K_s$ is the 6-bit subkey entering the S-box corresponding to bit $b$;
• $\vec{T}_i[j]$ is the $i$th power trace (vector of power values).

Note each trace is associated with a different ciphertext.

DPA uses power consumption measurements to determine whether a key block guess $K_s$ is correct.

• There are only $2^6=64$ possible values of $K_s$.
• When the attacker’s guess of $K_s$ is incorrect, the attacker’s value of $D$ differs from the actual target bit for about half of the ciphertexts $C_i$; equivalently, the selection function $D(C_i,b,K_s)$ is uncorrelated to what was actually computed by the target device, i.e., $\lim_{m\to\infty}\Delta_m[j] = 0$.

• When the attacker’s guess of $K_s$ is correct, $D$ is correlated to the value of the bit manipulated in the 16th round, i.e.,

  • $\Delta_m[j_b]$ approaches the effect of the target bit on the power consumption as $m\to\infty$, where $j_b$ is the time index corresponding to when $b$  is involved in computation;
  • $\Delta_m[j]$ approaches zero for all the times when $b$ is not involved in computation.
• Fig. 4 shows four sample power traces (1 simple, 3 differential).

The Diffie-Hellman (D-H) key agreement (often called “key exchange”) protocol is standardised in NIST SP 800-56A [BCR+18].

The protocol originated in the seminal 1976 paper by Whitfield Diffie and Martin Hellman [DH76], both recipients of the 2016 Turing Award (their contribution took 40 years to be recognised).

Protocol between 👩 Alice and 🧔 Bob [KL21, CONSTRUCTION 11.2] in Fig. 1:

1. On input of security parameter $1^n$, 👩 Alice runs probabilistic polynomial-time (PPT) algorithm to obtain the domain parameters $(\mathbb{G}, q, g)$, where $\mathbb{G}$ is a cyclic group of prime order $q$, and $g$ is a generator of $\mathbb{G}$.

   The bit-length of $q$ = the security parameter $n$.

   The domain parameters can be pre-distributed.

2. 👩 Alice chooses $x\in\mathbb{Z}_q$, $0\lt x\lt q$, uniformly at random, and computes $h_A \gets g^x$.

   $\mathbb{Z}_q$ is the (cyclic) group of integers modulo $q$.

   👩 Alice’s (ephemeral) private key and public key are $x$ and $g^x$ respectively.

3. 👩 Alice sends $(\mathbb{G}, q, g, h_A)$ to 🧔 Bob.

4. 🧔 Bob chooses $y\in\mathbb{Z}_q$, $0\lt y\lt q$,  uniformly at random, and computes $h_B \gets g^y$.

   🧔 Bob’s (ephemeral) private key and public key are $y$ and $g^y$ respectively.

5. 🧔 Bob sends $h_B$ to 👩 Alice and outputs $k_B \gets h_A^y$.
6. 👩 Alice computes $k_A \gets h_B^x$.

Successful completion of the protocol results in the session key $k_A = k_B = g^{xy}$.

A necessary condition for preventing a probabilistic polynomial-time (PPT) eavesdropper from computing the session key is that the computational Diffie-Hellman (CDH) problem is hard:

However, the hardness of the CDH problem is not sufficient.

Just as indistinguishability plays an essential role in symmetric-key encryption, indistinguishability is key here: if the session key $g^{xy}$ is indistinguishable from an element chosen uniformly at random from $\mathbb{G}$, then we have a sufficient condition for preventing a PPT eavesdropper from computing the session key [KL21, pp. 393-394].

The indistinguishability condition is equivalent to the assumption that the decisional Diffie-Hellman (DDH) problem is hard:

The DDH problem is readily reducible to the CDH problem, since any algorithm that solves the CDH can compute $g^{xy}$ and compare it with $g^z$; implying the DDH problem is no harder than the CDH problem.

In turn, the CDH problem is reducible to the discrete logarithm problem (DLP, see Definition 3), since any algorithm that solves the DLP can compute $x$ from $g^x$, $y$ from $g^y$, and hence $g^{xy}$; implying the CDH problem is no harder than the DLP problem.

In other words, the DDH problem can be reduced to the CDH problem, which in turn can be reduced to the DLP; solving the DLP breaks the D-H key agreement protocol.

The D-H key agreement protocol is used in the Internet Key Exchange (IKE) protocol, which is currently at version 2 [KHN+14].