A Brief Survey of Physical Attacks on Cryptographic Hardware

Previously, the topic of side-channel attacks (SCA) was covered on this blog. These attacks are very popular, for they can be mounted using very cheap equipment and do not necessarily require high level of expertise. Hence, SCA are widely accessible and present a common danger. As a result, they are well researched, and various countermeasures have been developed. Still, they are just a small part of the stack of physical attacks. Figure 1. crudely depicts the this colorful “stack”. The one thing all physical attacks have in common is that it is assumed that the attacker must gain physical access to the target device, and attain it for a certain amount of time. In the remainder of this post, a brief survey of these attacks will be given. More detailed descriptions will be provided in a series of posts that will follow. 

Figure 1: Stack of Physical Attacks

Invasiveness

The first segregation is based on the “invasiveness”. Invasive attacks entail breach of target’s packaging, or its surrounding enclosure. This is often a very delicate process which often requires expensive equipment and a high level of expertise. Since the breach is destructive by nature, it can be easily detected by subsequent users — if the chip itself was not destroyed in the process that is. The goal of this breach is to gain access to internal state of a chip. Commonly attackers target on-chip busses or storage elements, which may contain sensitive intermediaries of cryptographic computations or keys themselves. Aforementioned enclosures are a privilege of expensive devices, often called Hardware Security Modules (HSMs). HSMs may cost tens of thousands of Euros, and are envisioned to provide secure computational environments at high speeds. Apart from restricting access to the chip using sturdy build and “tamper-proof” latches and locks, enclosures are frequently equipped with seals and coatings that are supposed to witness any foul play that may have taken place. Additionally, tamper detection measures may be built in, envisioned to void all sensitive information at the first glimpse of attacker’s activities. Hence, invading these juggernauts is commonly more expensive and time consuming. Unfortunately, market-share of HSMs compared to bare smart-cards and RFIDs is neighboring negligible, especially with the rise of the IoT.

On the contrary, non-invasive adversaries do not cause any structural damage to packaging nor enclosures. They interact with the target device using its existing interfaces, and mediums that require no mechanical interaction with the device. They are virtually free, but may require significant expertise of attackers.

Activeness

The second segregation is based on the “activeness” of the attacker. Active attacks entail induction of computational (logical) or structural changes in the target chip. When we talk about computational changes, a very common example are Fault Injection (FI) attacks. There are two phases to FI attacks: fault injection during the execution of the targeted algorithm, and the analysis based on the observations of faulty outputs. A common method for altering device’s execution is called clock glitching. Namely, by introducing a premature edge on the clock signal, attacker violates devices’s critical path. As a result, incorrect values are captured in device’s registers. Alternatively, faults can be induced by shooting a laser beam with enough power to change the state of the device, while allowing it to remain operational. Here, any data or control register fall under “state of the device”. For example, round counter, commonly used in implementations of block ciphers, is a very favored target for such faults. Active attacks may require higher level of technical skill, and a more sophisticated setup.

On the contrary, passive adversaries may only observe device’s execution, while interacting through its predefined interfaces. Well-known SCA fall under this category. These attacks are well researched, and can be mounted using very cheap equipment. Developed techniques (e.g., Mutual Information Analysis) are extremely powerful, and once incorporated in the attackers setup can be reproduced quite trivially. Consequently, although they entail only limited exposure of the device, they pose a serious threat for they are very accessible even to attackers with modest capabilities.

The Reality

Activeness and invasiveness are two orthogonal properties, resulting in a total of four possibilities (although I find that the existence of “invasive and passive attacks” calls for a philosophical debate). Unfortunately, situation is much more complex than that in practice. Firstly, attackers are likely to use combined attacks. For example, FI + SCA may be a very powerful combination. Additionally, the distinction mentioned above is not as binary. Rather, along each of the two orthogonal axes there are many shades. For example, faults can be injected in some chips by applying laser beams to their packaging (non-invasive), while others may be shielded from such beams (hence they have to be attacked invasively).

Consequently, there exists a myriad of possible attack variations. Moreover, even if we lock on a certain extreme — let us say passive, non-invasive, CPA — quality of the measurement setup plays a very significant role. A 500 Euro oscilloscope can hardly match its 30000 Euro counterpart. In hindsight, there are no upper bounds to the power of a skilled invasive attacker performing a battery of active and passive attacks, apart from the temporal and financial constraints.

Taking all above into account, choosing a set of countermeasures is a difficult task (let alone implementing them properly). Bare in mind that these countermeasures are not for free. They may significantly increase the price of devices, reducing the profit margins severely. Therefore, there are no silver bullets in protection against physical attacks. In other words, in practice security engineers work to demotivate attackers with high probability. They try to stop “the attacker of interest”, rather then stopping all attacks. To achieve this, first step is identifying potential attackers. This process is often called profiling, and in a nutshell I would describe it as follows. Please note that this is a gross simplification of the problem, meant to depict the general idea. No distinction is made between fixed (price of the setup) and recurring (every time the attack is mounted) costs, nor between temporal and financial costs. Lastly, please note that the value of assets is heavily simplified as well, for the sake of avoiding a philosophical discussion yet again.

Manufacturer’s Dilemma

Assume that a device D, which costs d to manufacture, protects assets worth x , and features a
countermeasure C that costs c to deploy. We may consider D to be secure against an attacker A, who can mount a successful attack at a cost a (which includes A’s investment in
development of expertise), as long as

x ≤a+μA,

μA being the attackers profit margin. In other words, if the cost a is high enough attacker can not obtain desired amount of profit for given assets. On the other hand a manufacturer M that produces D wants to sell for a price m such that

m ≥ d + c + μM,

μ M being M’s profit margin. In other words, price of deploying countermeasures c directly cuts into manufacturer’s profits. Looking at these inequalities, it seems that there is no dilemma at all. Nevertheless, cost of attack depends on the selection of a countermeasure, i.e.,

a =f(c).

Assuming that an increase in c leads to the increase in a , by applying some high school math (readers are welcome to play with it), we see that the selection of C must be performed based on the value of assets it protects. A more detailed discussion on this topic will be given in one of the following posts.
In conclusion, physical attacks are a great threat. As IoT progresses, and the amount of ubiquitous devices increases their potential impact may only grow. Deploying devices that protect assets against physical attacks is a complex problem, which demands bespoke solutions, tailored to individual use cases. 

Side-channel analysis

For many years cryptographers and industry implemented crypto algorithms on microcontrollers and ASICs simply by translating the algorithms into assembly or rtl language. Only thing that mattered was correct functionality of the design. However, in mid to late nineties some interesting attacks of cryptographic implementations were shown, that were able to completely break the security of it, reveal secret keys, while the underlying cryptographic algorithm remained mathematically unbroken. First, the timing attack was introduced. Namely the attacker was able discover information based on the time server took to respond to a query since this time depended on the secret key that was used. Most simple application of this is square and multiply algorithm used for RSA exponentiation. Namely, for every bit of the exponent square, or square and multiply operation is used. This will result in different execution times for different exponents.

Kocher et al. introduced new type of side-channel attack  by revealing that information obtained from the power measurements can be also used to extract secret values from devices such as smart cards. We start from assuming that the power signal consist of random noise and deterministic one dependent on the processed value $x$

               $ P = L(x) + R$

Random noise is modeled as a Gaussian distribution with zero mean, and deterministic key dependant value $L(x)$ is usually hamming weight or hamming distance of the value . Following on, we choose intermediate value to be targeted. Good target of the attack for symmetric designs is S-box output, since small hamming weight difference in the input of the sbox leads to not so small hamming weight difference in the output. In the original work it was simply a one bit value, that could be either one or zero. The simplest example is thus by using one output bit of the S-box, with the assumption that power consumption is different for one and zero value. For example, take one S-box operation of the first round of AES. It is calculated using equation below

$SO_i = S(pt_i \oplus key_i)$

 Since we are unaware of what is the correct key value, we construct key guesses and calculate the targeted value, e.g. first bit of the S-box output. Now, for every key guess, we separate power traces into two groups, one that contains power traces for which the key guess produces target value one and other where target value is zero. Lastly, we compute the average of two groups, reducing the influence of the noise, and then we subtract these averages. If our key guess is wrong, difference of means will be negligible, since the power traces in two groups don’t correspond to correct values, and are thus uncorrelated. However, the correct key guess will have a noticeable spike in the point in time where first bit of S-box output is computed.

This very simple, yet very effective attack opened a new area of research. Soon, more elaborate attacks were devised, attacking bytes instead of bits using correlation. More advanced attacks include correlation with variance instead of the mean, or even higher statistical moments. These attacks are usually unpractical for orders higher than two, since the noise influence hardens the attacker’s possibility to retrieve the secret value. Profiling of the devices is sometimes performed in order to devise a more accurate model of the deterministic leakage functions. These attacks are known as template attacks. Designers also came up with various ways of trying to thwart these attacks, such as increasing the noise level by adding redundant circuitry or operations, and shuffling the execution operation. Other methods include secure logic design styles such as WDDL, where logical cells are designed to consume amount of power regardless of their output. Methods on the algorithmic level, e.g. Threshold Implementations, try to ensure no information leakage happens during the execution of the algorithm, regardless of the underlying leakage model of the design technology.

Since classical DPA and correlation analysis involve constructing guesses for all possible key bytes/nibbles, it can be very time consuming. This is where leakage tests became prominent. They tell if a set of randomly chosen traces can be distinguished for set of traces with fixed input value. It works in a very similar way to one bit DPA. 2 Sets of traces are obtained, one with random inputs and one with fixed inputs. Welsh t-test is used to measure if two sets can be distinguished from one another. If $\mu, \ s$, and $n$ are mean, variance and cardinality of a set, t values are calculated as follows

              $  t = \frac{\mu_0 - \mu_1}{\sqrt{\frac{s_0^2}{n_0} + \frac{s_1^2}{n_1}}}$

Approximating statistical degree of freedom with $n=n_0 + n_1$ we can with confidence 0.99999 claim that two sets are distinguishable for $t > 4.5$.  This type of leakage tests allows the designers to be more efficient since it reduces the testing time of the design. Downside of the approach is that leakage tests do not reveal how can the secret values be extracted, only that there is a possibility for an attacker to do so.

In best paper of CHES 2016: Differential Computation Analysis: Hiding Your White-Box Designs is Not Enough, side-channel analysis has been successfully used to break many white-box implementations. This time analysis has been performed on stack layout, instead of power traces, but the principle remained the same. Taking into account that white-box cryptography is currently being widely considered to be added to many software based designs, together with plethora of IoT devices that require protection, side-channel analysis importance will continue to be an important aspect of design process of cryptographic implementation. Thus, researchers will continue to work on improvement of leakage detection and key recovery methods to further reduce cost and time to market of new devices. 

Hardware Canaries: Arbiters of Proper Randomness

Random numbers are  widely used in cryptographic systems. Often they are essential in the very first steps of protocols (e.g., generation of session keys and challenges), or repeatedly used throughout the entire communication (e.g., random nonces). Therefore, failure of random number generators (RNGs) may obliterate security measures. Scale and severity of these failures can be depicted by a study conducted by Bernstein et al. The study shows how improper operation of RNGs, that have passed FIPS 140-2 Level 2 certification, lead to factorization of 184 distinct 1024-bit RSA keys used in Taiwan's national "Citizen Digital Certificate". 

Citizen Digital Certificate is your internet ID for bilateral identification while you are exchanging information on the internet. 

In other words, a team of several researchers could easily track, surveil, or impersonate 184 Taiwanese citizens, simply because random numbers were not generated properly. 

This is only one of many examples in the public-key setting. As alarming as it is, it may not seem to be of great importance to ones who believe their governments will hire capable security experts, or simply ones who trust their browsers while on the internet. Moreover, generation of these random numbers is often out hands of users, in well guarded server rooms, with considerable computational power to check "the quality" (statistical properties) of obtained numbers. And should all fail, there is an organization behind these numbers to be held liable.

On the other hand emerging Internet of Things (IOT) technologies are bringing numerous devices (e.g., wireless sensors, drones) in our environment. While hand-held "smart" devices have became the most ordinary, maybe even mundane, the "smart" hype expands to cars and houses. In this shroud of "smart" that surrounds us, to start to perceive secure communication more personally. Once you can use your smartphone to control the heating furnace in your home, consequences of unauthorized access may cause more fire than some leaked photos. 

Additionally, unlike in the traditional IT setting where ample computational power is available, IOT devices are often constrained in terms of resources, have to be very cheap and operate reliably. Lastly, attackers can easily obtain physical access to deployed IOT devices. Hence, attackers may perform numerous side-channel attacks, and may manipulate devices' environment (e.g., temperature) or tamper with the devices' operation (e.g., shoot lasers). 

Various mitigation techniques are studied to protect against these attacks. For example, sturdy casings, protective meshes, and seals for tamper detection, provide mechanical layer of security. They are expensive, and easily avoided by skilled adversaries. On the other end of the spectrum various circuit techniques, often called "secure logic styles", such as Sense-Amplifier Based Logic (SABL), are used. They are very difficult to implement in practice, due to variations in silicon manufacturing processes. Based on secret sharing, Threshold Implementations (TI) provide  provable security against widely spread Differential Power Analysis (DPA). The only downfall of TI, as well as all masking schemes, is that masks must be random and uniformly distributed. 

Therefore, security of a  device depends on cryptographic primitives (algorithms and protocols), which rely on random numbers, as well as the secure implementation. Since many countermeasures rely on use of random masks, secure implementation also often depends on the RNG. These dependencies are depicted in Figure 1. 

Figure 1: Security dependencies.

Practical problems stem from the circular dependency between RNG and secure implementations. Namely, should the attacker focus RNG as a target of attacks, causing it to malfunction or being able to predict its output, all physical security would be circumvent. 

Consequently, outputs of RNGs must be reliably unpredictable. To ensure this, RNG ouputs must be evaluated using prescribed statistical tests. Furthermore, in order to fit the IOT framework, these tests have to be performed in a lightweight, low-latency, and highly reliable manner. Therefore, storing giga bytes of data and computing over them is not a valid strategy. 

Figure 2 depicts two solutions proposed by Rožić et al based on NIST SP 800-90B model of the entropy source. Both are variations of the same idea to use canary numbers. This concept is already used in software security, and much longer in the mining industry for early warning threat detection. Namely, caged canaries were used to warn miners of poison gasses in coal mines, since they were much more susceptible to it. Hence small doses of gas, fatal to the canaries, could be detected, and miners would have been warned. Similarly, Rožić et al. propose an additional output of the RNG that has significantly worse characteristics. Whether canary numbers stem from a different noise source, or are obtained by weaker processing of the same noise as the random numbers, quality of canary numbers will decline abruptly once the device is tampered with. In the experiments authors have tampered with the chip temperature, cooling it down quickly to change the physical processes that produce entropy. 

Figure 2: RNG architectures with canary numbers.

Figure 3 depicts experimental results obtained on an elementary ring-oscillator based RNG. It clearly shows that the quality of canary numbers decays much more significantly, hence an attack can be detected while a RNG is still producing reliably unpredictable random numbers.

Figure 3: Test results of the elementary ring-oscillator based RNG (from the original paper).

Inherent leakage-resiliency of LWE

Why we care about post-quantum cryptography should be clear by now (if it’s not, you’re in the right place anyway: you just need to take a step back and read this splendidly packaged blog post). A mathematical notion that is having much success in achieving it is the Learning With Errors (LWE) problem (guess what, we've also talked about that here). Thanks to some mathematical evidences, we are quite confident about its hardness so that many cryptographic primitives whose security is based on it have arisen. That said, let’s take a step further and imagine a future (not that far in time) when all those primitives are standardised and deployed at many levels, including hardware security. Our experience with classic algorithms teaches us that we shouldn't be too confident of the security of an implementation given the security of the scheme on paper, and post-quantum cryptography is no exception. In fact, side-channel attacks are known to be a great threat to cryptographic implementations. The question this blog post wishes to partially answer is: how can we secure our (future) post-quantum implementations?

Playing cops and robbers is a way, of course: applying common techniques (e.g. masking, randomisation, …) against known side-channel attacks is possible just by fixing the design of specific schemes. However, this approach has at least a couple of drawbacks:

1. a protection is not guaranteed to thwart future attacks (sometime new attacks are specifically designed to circumvent a countermeasure). More generally, a countermeasure doesn't protect against anything outside what it was designed to protect against;
2. usual countermeasures introduce overhead (in terms of whatever metric you prefer, e.g. area, time, ...). This results in a protected scheme to be less efficient than its unprotected version.

Leakage-resilient cryptography is a possible alternative: a cryptographic scheme is provably secure even in the case of some anticipated amount of leakage, by design. Usually such proofs only rely on a bounded amount of leakage that the scheme can tolerate. The main idea sounds like the following statement.

We build a cryptographic scheme which retains security even if a bounded amount of arbitrary information is leaked.

Full stop. There aren't many other assumptions: this fact gives leakage-resilient cryptography enough generality to capture many, if not all, side-channel attacks. In essence, we are assuming that the scheme is secure if leakage occurs, no matter how that is exploited by an attacker. This seems to address the first drawback of ad-hoc countermeasures, provided everything is implemented in the proper manner. Is there anything we can do about the second drawback?

If we keep thinking of securing a scheme, then answering to that question is really difficult. Indeed a countermeasure, even the most general and provable one, introduces some changes in the original design which necessarily result in a overhead, for the simple reason that they take into account a more powerful adversary, namely one who is able of measuring and exploiting leakage too. However, think of the case in which none of the anticipated amount of leakage actually occurs. Then we end up having a less efficient implementation, the protected one, which doesn't provide any additional security because, without leakage, the original scheme was secure anyway. Eventually, stop thinking of securing a scheme and start thinking of securing an assumption.

In their paper, Goldwasser, Kalai, Peikert and Vaikuntanathan show that LWE has the nice feature of being hard even in the presence of leakage. Does it sound like what we've just said? Essentially yes, but with a great difference: they're not building a leakage-resilient scheme, hence introducing some sort of overhead, but proving the leakage-resiliency of an assumption. This makes a big difference, because the former implies that the efficiency degrades to let leakage-resiliency grow, while the latter implies that security, not efficiency, degrades. In particular, their proof establishes a relation between the security level and the amount of leakage in such a way that we don't need to anticipate a maximum tolerable amount of it. The straightforward consequence is that a scheme based on LWE is secure independently on whether the leakage occurs or not, with the advantage that in the latter case we have not introduced any protection-related overhead in the design. As a result, they propose a symmetric-key encryption scheme being secure even in the presence of leakage (with some caveats): the novelty relies on the fact that you won't find any parameter describing an amount of leakage (usually called $\lambda$ in the literature of leakage-resilient cryptography).

We omit any technicality here as this would like to be a generic and accessible reading. For further details on how the authors achieved this result, we refer to their paper. Instead, it you prefer to have just a mathematical flavour without going into too many details, you may like this post from the Bristol cryptography group's blog. Stay tuned for more insights on post-quantum cryptography!

P.S.: the word "leakage" appears 19 times in this text. If you're tired of reading it, watch this.

Marco (Thanks to Simon and Matthias for some corrections!)

Threshold implementations

Ever since the discovery of differential power attacks (DPA) in late 1990's, cryptographic community has been trying to find effective methods to twarth attempts to extract secret information, i.e. secret key using such attacks. Initial proposals to protect hardware implementations used simple models. Although easy to understand these schemes can still leak sensitive information through power consumption in case of glitches. In most models we assume that Hamming weight of intermediate result is leaked through power consumption.

 Masking

Masking is one of the first ideas to prevent leaking sensitive information using intermediate values during encryption. In most basic example we split the intermediate value $X$ into two randomized values $X_1$ and $X_2$ such that $X = X_1 \oplus X_2$. We assume that leakage is equal to Hamming weight of the variables $\mathcal{L}(X) =  \text{HW}(X_1, X_2)$.  It turns out that first order analysis doesn't reveal input value since mean of the leakage $\mathcal{L}$ is constant for all values of input $x$.          

Table 1. Leakage behaviour of single bit variable using two shares

$x$	$x_1$	$x_2$	$\mathcal{L}(x)$	Mean$(\mathcal{L}(x))$
$0$	$0$	$0$	$0$	$1$
	$1$	$1$	$2$
$1$	$1$	$0$	$1$	$1$
	$0$	$1$	$1$

In case of second order analysis, however, this scheme will leak. Variance of $\text{HW}(X_1, X_2)$ is different for the case when unmasked value takes value 0 and for the case when it takes value 1. In general, to protect against $n^{\text{th}}$ order attack we would need to decompose original variables into $n + 1$ randomized uniform variables $X_1, ..., X_{n+1}$ such that
\begin{equation}
X = X_1 \oplus X_2 \oplus \cdots \oplus X_{n+1}
\end{equation}

In practice this is done by generating $d$ variables $X_1, .... , X_d$ and deriving $X_{d+1}$ so that it satisfies the upper equation. Each of the variables $X_i$ is referred to as share. Once we have a sharing, we need to perform all the operations using these shares so that in the end we still still have correct output shares. In case of affine transform this is easy - applying linear term to all of the shares and adding constant term to one of the shares. Boolean function that have higher algebraic degree are not so trivial as we need to ensure the order in which the operations in the shares are executed. For example function $f(a, b, c) = a \oplus bc$ can be protected using Boolean masking with 2 shares in following way
\begin{equation}
f_1(a_1, b_1, c_1) = (a_1 \oplus b_1c_1) \oplus b_1c_2\\
f_2(a_2, b_2, c_2) = (a_2 \oplus b_2c_1) \oplus b_2c_2.
\end{equation}

This sharing is not unique and there are multiple possible sharing of the same function.
As noted, order in which operations take place is important. Otherwise, we could expose the unmasked value of $c$ in function $f_1$ because $ b_1c_1 \oplus b_1c_2 = b_1(c_1 \oplus c_2) = b_1c$.

Major problem with conventional masking is that it doesn't provide protection when glitches can occur in the circuit, which is inevitable in CMOS technology. Different propagation times of input signals can cause some gates to change state more than once during a single clock cycle, which causes more input current to be drawn from the power source, resulting in increased power consumption during the clock cycle in which glitch occurred. If the increased power consumption can be correlated to the value we want to protect, there is a leak in the device.

Threshold implementations

Threshold implementation, or TI, is a method of protecting against DPA that is resistant to glitches that can occur. It builds upon the classical masking scheme and threshold cryptography. For $d^{\text{th}}$ order security idea is to create shared functions in a way that any linear combination of $d$ shared function is independent of at least one input share. In other words, if we are able to probe any $d$ wires in the design, we wouldn't be able to create correlation with unshared value because we would always be missing at least one input share for correlation.

In order to create a TI of a given function $f(x) : \mathcal{F}_2^n \Rightarrow \mathcal{F}_2^m$ with $s_{in}$ input shares and $s_{out}$ output shares we apply a Boolean masking to input variable $x$, so that we create shares $x_1, ... , x_{s_{in}}$ for which holds $\sum x_i = x$. Now we have a sharing of variable $x$, $\mbox{Sh}(x), \mathbf{x} \in \mathcal{F}_2^{ns_{in}}$. Similarly, we create a sharing of function $f$ by creating $s_{out}$ function components $\mathbf{f} = f_1, ... , f_{s_{out}}, \mathbf{f} \in \mathcal{F}_2^{m s_{out}}$.
Threshold implementation satisfies four key properties:

1. Uniform masking
2. Correctness
3. Non-Completness
4. Uniformity of a sharing

First property simply states that for each possible value of input variable $x$ probability of each valid input sharing is always the same. If we denote the input sharing with $\mathbf{X}$ we could rewrite the previous statement as

\begin{equation}
(\forall x), (\mathbf{x} \in \mbox{Sh}(x) \Rightarrow \mbox{Pr}(\mathbf{X} = \mathbf{x} | X = x) = p)\,  \land  \, (\mathbf{x} \notin \mbox{Sh}(x) \Rightarrow \mbox{Pr}(\mathbf{X} = \mathbf{x} | X = x) = 0) \\ \land \\ (\sum_{\mathbf{x} \in Sh(x)} \mbox{Pr}(\mathbf{X} = \mathbf{x}) = \mbox{Pr}(X = x))
\end{equation}

where $p$ is a constant.

Second property of correctness states that for sharing of a function $f(x)$, $\mathbf{f}(\mathbf{x}) = f_1(\mathbf{x}), .... , f_{s_x}(\mathbf{x})$ XORing all output component gives back the unshared output:
\begin{equation}
(\forall x) ((\mathbf{x} \in \mbox{Sh}(x), a = f(x), a_i = f_i(\mathbf{x})) \Rightarrow a = \sum_i a_i = \sum_i f_i(\mathbf{x}))
\end{equation}

It is simply there to ensure that once we apply the sharing we still get the same result in the output when we perform unmasking.

The previous two properties applies to all masking schemes, not only TI. Property of non-completeness is what ensures $d^{\text{th}}$ order of security:

Any combination of up to $d$ component functions $f_i$ of $\mathbf{f}$ is independent of at least one input share $x_j$.

Being independent of one input share means that even the attacker that knows values of $d$ component functions cannot recreate the original input value $x$. Without all the input shares, the information from all other input shares is independent of the input.

It can be shown that to achieve $d^{\text{th}}$ order TI we need at least $d + 1$ input shares. It can also be shown that there always exists a $d^{\text{th}}$ order TI of a function of algebraic degree $t$ with number of input shares $s_{in} \geq td + 1$ and number of output shares $s_{out} \geq \binom {s_{in}}t$. Also, in order to achieve non-completeness we need at least $t+1$ input shares if degree of the function is $t$.

The final property Threshold implementation requires that the output sharing also need to preserve output distribution, e.g. if the $f$ is a permutation then $\mathbf{f}$ is also a permutation:

$d^{\text{th}}$ order sharing of $\mathbf{f}$ if uniform if and only if
\begin{equation}
\forall x \in \mathcal{F}^n, \forall a \in \mathcal{F}^m \textit{ where } f(x) = a, \forall \mathbf{a} \in \mbox{Sh}(a) \text{ : }|\mathbf{x} \in \mbox{Sh}(x)  | \mathbf{f}(\mathbf{x}) = \mathbf{a}| = \frac{|\mathcal{F}|^{n(s_{in} - 1)}}{|\mathcal{F}|^{m(s_{out} - 1)}}
\end{equation}
It is important when we are cascading TIs of two or more functions, because we need the input sharing of the second function to be uniform. This is almost always the the case, e.g. when we are applying TI to block cipher, output of the previous round is used as input for the next round etc.

Uniformity in practice is non-trivial to achieve and finding a methodical way to get a uniform output sharing is still extensively researched. There is a couple of heuristics, but none of them guarantee a sharing that has uniform output distribution. We will tackle some of them in a future blog.  
  

A simple "hallo" from Erik

Continuing with the theme of introducing ourselves, my name is Erik Boss. I am one of the ESRs from Ruhr-Universität Bochum. I grew up in a fairly small town called Duiven located in the east of the Netherlands. I completed my Bachelor's and Master's degrees at the Radboud University Nijmegen. The latter of which specializing in computer security.

Only deciding right at the end of my studies to pursue a PhD, I applied for one of the ESR positions at the RUB and moved to Germany three months later. Which, so far, has been an interesting experience.

Within the context of ECRYPT-NET, I will be combining my expertise with software-related security with the experience located at the RUB in embedded security. What I will be looking at primarily is the automatic verification of hardware specifications in order to detect, prevent and/or measure side-channel leakages. This allows me combine many areas of computer security as well as some ideas from computer science in general.

Overall, I am grateful for the opportunity provided by this project to do something which is fun and fulfilling and maybe even useful to the world at large. Already I have met some great people within the context of ECRYPT-NET and I am looking forward to seeing everyone again in Tenerife.