52 Things: Number 47: What is the Fiat-Shamir transform?

This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know To Do Cryptography': a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. Having introduced Sigma Protocols, we now look at an important method for ensuring they are zero knowledge. Thanks again to David Bernhard for his assistance.

What is the Fiat-Shamir transform?

Sigma protocols, which we saw last week, are fast and useful protocols for Alice to prove something to Bob - as long as they're both online at the same time. Alice sends Bob a commitment, Bob replies with a challenge and Alice sends a response. Unfortunately bar further modifications, Sigma protocols are not actually known to be zero-knowledge: they are only honest-verifier zero- knowledge.

The Fiat-Shamir transform is a technique to turn a Sigma protocol into a non- interactive proof. This not only lets Alice send a proof to Bob by e-mail, which he can read later without having to send her a challenge back, it also lets her turn any Sigma protocol into a digital signature scheme with which she can assert "someone who knows the secret for this Sigma protocol has signed that message". Alice can create a signature once and post it to a usenet bulletin board and everyone who sees the signed message can check the signature without having to contact Alice. And zero-knowledge comes for free, since Bob or any other reader no longer has to do anything.

Although this technique is explained in Fiat and Shamir's 1986 paper, several eminent cryptographers have pointed out in the past that it was actually given by Blum in an even earlier work, though we have not been able to trace this.

A Sigma protocol can be implemented as four algorithms *Commit*, *Challenge*, *Respond* and *Check*, to be executed as follows:

Alice                                Bob
-----                                -----
    
co,st = Commit(secret,public)
         ---------- co --------->
                                     c = Challenge()
         <--------- c  ----------
r = Respond(st,c)
         ---------- r  --------->
                                         Check(co,c,r)

For the Fiat-Shamir transformation, Alice picks a hash function $H$ and uses it to create the challenge herself:

Alice                                World
-----                                -----

co, st = Commit(secret,public)
c = H(public,co)
r = Respond(st,c)
         ------ co,r ----------->
                                     c = H(public,co)
                                     Check(co,c,r)

If Alice wants to sign a message m, she includes that in the hash: c = H(public, co,m) and posts (m,co,r) as her signed message.

Why does this work? If $H$ were a random function, then the challenge is clearly uniformly random and independent of Alice's public information and commitment. The security analysis considers an Alice who does not have access to the code of $H$ directly, only to an oracle for $H$. In this case, the probability of Alice making a correct response without following the protocol (especially if she does not know the necessary secret) is proportional to the inverse of the size of the range of $H$, that is if $H$ has domain X and range Y then someone without the the secret who makes up to q $H$ -calls has at most a q/|Y| probability of making a r-value that *Check* accepts. Typically |Y| = 2^n for a decently large value of n, so this probability is negligible.

Some people will tell you that this style of analysis, known as the Random Oracle Model (ROM), is deeply flawed because there's an artificial counter- example of a scheme that is secure in the ROM but is insecure for any actual hash function $H$. What this counter-example shows is that if you go to enough effort to make a stupid scheme, you can end up with a stupid scheme. In practice, Fiat-Shamir has been known since at least 1986, used in several practical applications and stands unbroken to this day (if done properly). No- one has to date proposed a workable attack on a Fiat-Shamir transformed Sigma protocol that was not deliberately designed to be stupid, which is more than can be said for quite a few other cryptographic schemes.

52 Things: Number 46: What do correctness, soundness and zero-knowledge mean in the context of a Sigma protocol?

This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know To Do Cryptography': a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. This week we enter the final phase, introducing Sigma Protocols as the first 'advanced protocol'. Thanks to David Bernhard for his assistance in writing this blog.

Sigma protocols

Sigma protocols are protocols for Alice to prove something to Bob (that she knows some secret). They have the following general form: Alice knows a secret; Alice and Bob both share some common information. Then:

1. Alice sends a value to Bob, known as a commitment.
2. Bob picks a challenge uniformly at random and sends it to Alice.
3. Alice computes a response and sends it to Bob.
4. Bob checks the response and accepts or rejects Alice's claim.

Legend has it that if you draw a diagram of this in some way, it looks like the Greek capital letter Sigma, hence the name Sigma protocol.

In cryptography, the properties we expect a Sigma protocol to support are:

• Correctness If everyone does what they are supposed to, then Bob accepts.

• Soundness If Alice lies, then Bob can tell (she can't trick him into accepting something false)

• Zero-knoweldge If Alice tells the truth, Bob can't learn what her secret input was.

A more formal treatment

Having provided a rough overview, we now provide a more formal treatment, based on David's PhD thesis "Zero-Knowledge Proofs in Theory and Practice".

Defining a Sigma Protocol

Let $k$ be a field. We're interested in linear functions $f: W \to X$ from one $k$- vector space to another, where Alice and Bob both know some public $x \in X$ and Alice also knows a secret preimage $w \in W$ such that $f(w) = x$. Alice wants to prove to Bob that she knows a preimage of $x$.

Quite a lot of cryptography is done over elliptic curves nowadays. An elliptic curve is a group of points of the form $P = (x,y)$ and a special point "at infinity" that is an honorary member of the curve. These points satisfy some equations and most importantly, one can add two points on the curve to get another and this addition makes the curve into a group. One often starts with a large prime $p$, works over the base field $k = \mathbb F_p$ and considers points $P$ in $E_p = E \cap \mathbb F_p \times \mathbb F_p$.

Many elliptic curve protocols start out by generating keypairs using point multiplication: everyone agrees on a common, public base point $P$. Then one can pick a secret key $x \in \mathbb F_p$ and compute the related public key $Y = x \cdot P$. If Alice wants to register her public key somewhere, it is good for security if the registrar asks her to prove that she knows the associated secret key, or else she could register someone else's key as her own. But of course Alice should not reveal her secret key to the registrar. She could, for example, use a Sigma protocol to prove that she knows the secret key that she claims to know, without revealing it.

If one takes $W = \mathbb F_p$ as a $k$-vector space and $X = E_p$ then point multiplication for a fixed base point, specifically $f: W \to X, w \mapsto w \cdot P$ is a linear function. The same can be said for "matrix product" functions. Suppose that Alice has a secret key $x$ and a public key $Y = x \cdot P$, and someone sends her an ElGamal ciphertext $(C,D)$ for her key. She wants to decrypt this and prove that she has decrypted it correctly, one way to do this is to compute a decryption share $S = x \cdot C$. The decryption is then $D-S$ which anyone can compute from $(C,D)$ and $S$. So Alice want to show that she knows an $x$ meeting the two equations $Y = x \cdot P$ and $S = x \cdot C$, so we set $W = k, X = E_p \times E_p$ and $f(x) = (x \cdot P, x \cdot C)$ which is a linear function $f: W \to X$.

The Sigma protocol for $f: W \to X$ is the following construction. Alice knows $(x, w) \in X \times W$ with $f(w) = x$ and Bob knows $x$. 1. Alice picks $r \in W$ at random, sets $A = f(r)$ and sends $A$ to Bob. This is the commitment (Alice is committing to $r$). 2. Bob picks $c \in k$ at random and sends it to Alice. This is the challenge. 3. Alice computes the response $s = r + c \cdot w$ in $W$ (the product is scalar multiplication in $W$) and sends $s$ to Bob. 4. Bob accepts if $f(s) = A + c \cdot x$ in $X$.

Let's look at the three security properties for Sigma protocols in more detail:

Correctness

In just about any protocol (cryptographic or otherwise), correctness means that if everyone follows the protocol then it does what it should. In the context of Sigma protocols, this means that if Alice and Bob do as told then Bob accepts; this is true because $f$ is linear.

Soundness

Soundness means that Alice cannot prove a false statement. This trips up a lot of people because the first protocol they see is Schnorr's protocol for proving that $y = x \cdot P$, so Alice is proving that such an $x$ exists. But that is obvious! (Alice is also proving that she knows $x$, which is more interesting but that's another property.) But let's look at the other example, Alice proving that $S$ is a correct decryption share for $C$ under public key $Y$. Here, Alice is proving that an $x$ exists such that $Y = x \cdot P$ and $S = x \cdot C$ which is not true for all tuples $(P, C, Y, S)$. What's actually going on is that the image of $f$ is a one-dimensional subspace of the two-dimensional $k$- vector space $X$. In our formalism, soundness means that Bob does not accept (except with perhaps negligible probability) unless $x$ is in the image of $f$ (that is, a preimage $w$ exists such that $x = f(w)$).

Sigma protocols are sound. Actually, they are even more than that, they have a property called special soundness. Informally, consider the point in time when Alice has just sent her commitment $A$ to Bob. For which values of $c$ can Alice possibly find a $r$ that Bob will accept? If there is at most one such value then Alice gets Bob to accept overall with probability at most $1/|k|$. Usually, $|k|$ is exponentially large (it's the prime $p$ that we started with) so $1/|k|$ is negligibly small. Special soundness says that if Alice can conveince Bob even for only two out of $|k|$ possible challenges, then a preimage $w$ must exist. Suppose that on challenge $c$ Alice would reply $s$ and on challenge $c' \neq c$ Alice would reply $s'$, and Bob would accept both of these. Then set $d = (c-c')^{-1}$ which we can do as $k$ is a field and $c \neq c'$, and a bit of linear algebra shows that $w = d \cdot (s-s')$ where the product is again $W$-scalar multiplication satisfies the equation $x = f(w)$.

Zero-Knowledge

Bob is happy because the protocol is sound. Alice still needs to know that Bob can't learn $w$ from the Sigma protocol. Actually, Alice probably wants even more than that: after running the protocol with Bob, Bob should not be able to prove to Charlie that he knows Alice's secret $w$ either. Zero-knowledge says even more than that, Bob does not learn anything from the protocol except that Alice knows $w$ (and therefore, that $w$ exists and $x$ is in the image of $f$).

The proof that Sigma protocols are zero-knowledge ... does not exist! Contrary to what one might guess after learning about Sigma protocols in the textbook chapter on zero-knowledge, Sigma protocols in general are not zero-knowledge, which beginning students of cryptography would do well to remember for their exams. (They meet a weaker requirement called honest-verifier zero-knowledge.)

Discussing Sigma protocols in the context of zero-knowledge isn't completely arbitrary though: one can make them zero-knowlege in several ways, the most practical of which is making them non-interactive. But that's next week's topic...

52 Things: Number 45: Describe some basic (maybe ineffective) defences against side channel attacks proposed in the literature for RSA.

This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know To Do Cryptography': a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. This week we consider what can be done to mitigate the threat of side-channels against RSA implementations...

To keep things simple in this post, we'll talk about so-called "vanilla" RSA (where no randomness is used in encryption) and highlight a small number of potential side-channel attacks along with countermeasures.

Let's start by recalling the vanilla RSA encryption scheme.
Key generation picks a secret pair of odd prime integers, $p$ and $q$, and computes the modulus $N = pq$. An integer $3 \leq e \leq \phi(N)$, coprime to $\phi(N)$, is chosen. Then the public key is the pair $\left(N, e\right)$ and the secret key is the unique integer $3 \leq d \leq \phi(N)$ such that $ed \equiv 1 \: \left( \mathrm{mod} \: \phi(N) \right)$.
To encrypt a message $m \in \mathbb{Z}_N$, one computes $m^e \: \left( \mathrm{mod} \: N \right)$.
To decrypt a ciphertext $c \in \mathbb{Z}_N$, one computes $c^d \: \left( \mathrm{mod} \: N \right)$.

An SPA-Style Attack to Determine the Secret Key

We first give an example of how information about the secret key $d$ could be leaked during the decryption operation. A typical implementation of exponentiation will be a branching program that behaves differently depending on the inputs. Consider, for example, the square and multiply algorithm which efficiently computes an exponentiation where the exponent is expressed in binary:

Say $d = \sum_{0\leq i \leq n} b_i 2^i$ where each $b_i \in \lbrace 0,1 \rbrace$. Then,
\[ c^d = \prod_{0 \leq i \leq n} c^{b_i 2^i }.\] Noting that, if we ignore the bits $b_i$, each factor in the product is the square of the previous factor, we can easily compute the product as follows:

• $ANS \leftarrow 1$
• $fac \leftarrow c$
• For $0 \leq i \leq n$, do
• If $b_i = 1$,
• $ANS \leftarrow ANS \times fac$
• $fac \leftarrow fac^2$
• Else,
• $fac \leftarrow fac^2$
• Return $ANS$.

The algorithm behaves differently depending on whether each $b_i$ is $0$ or $1$. Therefore, if this algorithm is used to decrypt an RSA ciphertext, the time it takes or its power consumption could reveal the value of each bit $b_i$, thus revealing the secret key $d$. This would be an SPA-style attack since only one trace would be needed.

In order to prevent this kind of attack, one must make the two branches of the algorithm look the same to an attacker, i.e. have both branches of the square and multiply algorithm take the same amount of time to run or consume the same amount of power.

An SPA-Style Attack to Determine the Plaintext

The above shows how the exponentiation operation used in decryption could compromise the secret key. But an attacker may be interested in a particular plaintext, $m$ (after all, encryption is designed to keep such messages secret). Again, if the encryption operation is a branching program which depends on the value of $m$, the runtime or power consumption of a single encryption could leak information about $m$ in an SPA-style attack. In particular, note that one has to perform a modular reduction in encryption. In most implementations, instead of a single reduction of a very large integer at the end of the exponentiation, there will be many modular reductions throughout the exponentiation algorithm in order to keep the numbers involved (relatively) small. As a slightly contrived example, suppose we perform modular reduction via the following loop:

• While $ANS > N$
• $ANS \leftarrow ANS - N$

which, since the exponent is known in the case of encryption, leaks information about the base $m$ depending on how long it takes to run and how much power it consumes (cf. David's post about attacks on Montgomery Arithmetic).

Again, to prevent this kind of attack we must ensure that our programme takes the same amount of time and consumes the same amount of power to reduce intermediate values modulo $N$, no matter what size they are (up to some upper bound which can easily be found since we know the exact exponent and range of values for the base).

Preventing DPA-Style Attacks on the Secret Key

Even if we obscure any branching in decryption that depends on $d$, the precise details of the operations performed in carrying out the exponentiations for decryption will still depend (in a less obvious way) on the exponent. So, over multiple decryptions, a statistical relationship between the decryption key and the duration or power consumption of the operations may emerge. Therefore we also need to prevent more subtle DPA-style attacks where the attacker uses statistical techniques on a large number of traces to test hypotheses on the secrect key.

To do this, we have to remove the direct dependency between the secrect key and the calculation performed each time. This involves blinding, where some random noise is injected into the exponentiation operation without affecting the result. In the case of decryption, we introduce randomness in the exponent: while $d$ is the unique multiplicative inverse of $e$ in $\mathbb{Z}_{\phi(N)}$ such that $3 \leq d \leq \phi(N)$, we can add or subtract integer multiples of $\phi(N)$ to $d$ and obtain a new inverse. So to decrypt $c \in \mathbb{Z}_N$, select a random $r \in \mathbb{Z}$ and compute $d' = d + r\phi(N)$. Then compute the message $c^{d'} \: \left( \mathrm{mod} \: N \right)$ which will be the same as directly computing $c^d \: \left( \mathrm{mod} \: N \right)$. The point is that addition is not usually a branching operation, so adding $r\phi(N)$ to $d$ will not leak information about $d$ on a single trace, and using a new random $r$ for each decryption prevents DPA-style attacks.

Coppersmith's SPA-Style Attack to Determine the Plaintext

We conclude this post with a special and interesting attack to determine $m$ which is only possible when $e$ is small ($e=3$ is a popular choice of exponent for efficiency of encryption). There is a theorem due to Coppersmith (see this article) that an attacker can efficiently find all 'small' integer roots modulo $N$ of an integer polynomial $f$ of degree $e$, where small essentially means having absolute value less than $N^{1/e}$. Obviously if $m$ happens to be small then one can use this to directly solve the equation $m^e \equiv c \: \left (\mathrm{mod} \: N \right)$ as required to recover the plaintext. If not, but some of the most significant bits of $m$ are leaked, then we may write $m = m_k + m_u$ where $m_k$ is known and $m_u$ is small, obtaining an integer polynomial $f(X) = \left( m_k + X \right)^e - c$ whose small roots modulo $N$ can be found via the Coppersmith method and correspond to the remaining bits of $m$. So we need to make sure that bits of $m$ are not leaked by the encryption operation.

To counter this kind of attack, one again uses blinding: we introduce some randomness to $m$ before exponentiating and remove it again afterwards. More precisely, to encrypt $m \in \mathbb{Z}_N$, we select a random $r \in \mathbb{Z}_N$, compute $rm \: \left( \mathrm{mod} \: N \right) $, then $\left(rm\right)^e \: \left( \mathrm{mod} \: N \right)$ and finally multiply the result by $r^{\phi(N)-e}$ (and reduce modulo $N$ again). Obviously the ciphertext is the same as it would have been without blinding, but the leakage of the exponentiation operation is now independent of $m$.

This should give you a flavour of the kind of side-channel attacks that can be mounted on an encryption scheme and the way implementations can avoid them.

52 Things: Number 43: Describe some basic (maybe ineffective) defences against side channel attacks proposed in the literature for AES

This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know To Do Cryptography': a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. This week we consider what can be done to mitigate the thread of side-channels against AES implementations...
Sidechannel defences: Why?
For a modern cryptographic scheme to be taken seriously, we generally require some form of security justification. In the case of AES, we believe it acts like a random permutation if the adversary doesn't know the key. However, if the adversary has side-channel information, it is possible that this is no longer the case. So, what can we do about it?  Ideally we would create an implementation that is completely impervious to side-channel attacks. However, this effectively means the implementation must sit in total isolation, with absolutely no output streams - which makes it rather pointless!
Perhaps we can make sure that whatever we do, it doesn't matter if the AES implementation leaks information through side channels? This leads to the field of leakage resilient cryptography, which is a very strong security requirement indeed. As such, schemes secure in these conditions (of which there are very few) tend to be drastically less efficient than those which avoid (/ignore) the problem. Since trade-offs must always be made in design, in practice we tend to use schemes that assume AES doesn't leak any information, and combine them with implementations that contain defences against some of the simpler side-channel attacks. The hope is that this pushes the attack cost beyond the value of the information secured and so (even though they could) no adversary will bother attacking the system because it is no longer viable.

Some Basic Defences
So, with that in mind, let us consider a couple of basic defences against some of the less sophisticated side-channel attacks. As pointed out in the question, these techniques may be easily bypassed, so think of this post as explaining the general concept, rather than providing any sensible suggestions!

Attack: Timing Attack
Weakness: Some implementations run in different times depending on their inputs. As such, by observing how long the system takes to respond one learns something about the key/inputs.
Defence: Constant time implementations. As the title says, the best defence against a timing attack is to make sure the implementation takes constant time, and most implementations will be constant-time nowadays. This might not be too hard in hardware, but in software it can be very difficult indeed, because the microcode (the internal programming of the processor) is generally a trade secret and open to change.

Attack: Power Analysis (DPA,SPA)
Weakness: The power usage of some implementations is correlated with the key material, often due to the hamming distance when storing values. For more information, read the blog from two weeks ago.
Defence (1): Masking Rather than using the AES Sbox directly, one applies a mask to the input value, and looks this up in a masked Sbox (which is effectively the Sbox with its values reordered to accommodate the mask).  Then, even though the attacker may be able to detect correlations between certain internal variables, these are all masked, and do not [directly] correspond to the key material as they had previously. More complex masking schemes will be more complex to instantiate, but lead to better resistance to attack.
Defence (2): Shuffling To conduct a power analysis attack, the attacker uses the fact they know the internal structure of the AES scheme. If we shuffle the order of the S-boxes in our implementation (by some secret permutation), the adversary will not know how their readings correspond to the internal key materials. A variation on this is the deliberate use of non-determinism, allowing the processor to reorder certain collections of instructions on it's own.


Attack: Cache-flooding
Weakness: Implementations using lookup-tables (eg for the SBox) will be more or less efficient if the appropriate cells are already in the processors cache. By pushing most of the lookup table out of the cache, an attacker can observe whether the appropriate cells are called, leaking information. Can also be observed as a timing attack or by power analysis if the cost of loading the cache can be observed.
Defence: Dont use lookup tables on secret data! The simplest defence in this list - if you don't want to leak information about which lookup entries have been used, don't use lookup tables. In the case of AES this is reasonable, because the AES Sbox can actually be computed as a simple function on the input byte. This would be much less practical with (for example) the DES Sbox, which does not have this structure.

52 Things: Number 41: Are all side-channels related to power analysis?

This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know' to do Cryptography: a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. In this post (spoiler alert!) we enumerate various flavours of side-channel attacks.

Right, shall we keep this one simple? Side-Channel Attacks (SCA) utilise information acquired in the context of physical implementations of cryptographic algorithms, as opposed to classical cryptanalytic attacks which target theoretical weaknesses. Power analysis is perhaps the most popular flavour of SCA, but it is certainly not the only one.

It would be beyond the scope of this blog to provide a comprehensive list of all side-channels and attack methodologies. Instead, here are some of the most common SCA targets, together with references to simple but clever attacks:

• Power consumption. The instantaneous power consumption of a device can leak information about the  processed value, e.g. its Hamming weight. I recommend Mangard's attack on the AES key schedule as a starting point for those interested in Simple Power Analysis (SPA). 

• Execution time. Such attacks exploit data-dependent differences in running time of algorithms. A famous target is the square-and-multiply algorithm used in modular exponentiation, for example Kocher's attack. Fun fact: even a constant-time implementation is vulnerable to power attacks.

• Electromagnetic radiation. Apparently, it's rather tricky to get the measurements right for this one, but once that's done -- the attack methodology is similar to Power Attacks. Here's the most cited paper dealing with EMR.

• Other. There is no limit to what can constitute a target for SCA, and that's in part why they are so interesting. Here's some more ideas: 

• an acoustic attack on RSA, 

• an attack that uses visible light emitted from computer LED (light-emitting diodes),

• a smudge attack on smart phone touch screens, 

• an attack exploiting error messages, also known as padding oracle attack

Writing the above, I realise how it could be unsettling to know or to find out that there are so many loopholes. SCA is very much a cat-and-mouse game, and researchers usually recommend ways to avoid the signaled vulnerabilities.

52 Things: Number 38: What is the difference between a covert channel and a side-channel?

This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know To Do Cryptography': a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. In this week, we discuss the difference between a covert channel and a side-channel.

Covert channels and side-channels are two types of information leakage channels.

A covert channel uses mechanisms that are not intended for communications, e.g., writing and checking if a file is locked to convey a “1” or “0”. In a covert channel an insider process leaks information to an outsider process not normally allowed to access that information. The insider (sending) process could be a Trojan horse program previously inserted stealthily into the computer. An outsider (receiving) process need only be an unprivileged process [1].

In side-channel attacks, also known as passive non-invasive attacks, the cryptographic device is essentially attacked as it is, i.e. only directly accessible interfaces are exploited. The device is not permanently altered and therefore no evidence of an attack is left behind. The basic idea of side-channel attacks is to determine the secret key of a cryptographic device by measuring its execution time, its power consumption, or its electromagnetic field [2].

In a physical side-channel attack, unconventional techniques are used to deduce secret information. Typically, the device has been stolen or captured by the adversary who then has physical access to it for launching a physical side-channel attack. Traditional side-channel attacks involved differential power analysis and timing analysis. Different amounts of power (or time) used by the device in performing an encryption can be measured and analysed to deduce some or all of the key bits. The number of trials needed in a power or timing side-channel attack could be much less than that needed in mathematical cryptanalysis [1]. 

In software side-channel attacks a victim process inadvertently assumes the role of the sending process, and a listening (attacker) process assumes the role of the receiving process. If the victim process is performing an encryption using a secret key, a software side-channel attack allows the listening process to get information that leads to partial or full recovery of the key [1].

[1] Wang, Zhenghong, and Ruby B. Lee. "Covert and side channels due to processor architecture." Computer Security Applications Conference, 2006. ACSAC'06. 22nd Annual. IEEE, 2006.

[2] Mangard, Stefan, Elisabeth Oswald, and Thomas Popp. Power analysis attacks: Revealing the secrets of smart cards. Vol. 31. Springer Science & Business Media, 2008.

52 Things: Number 36: Index Calculus Algorithm

This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know To Do Cryptography': a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. We continue the mathematical attacks with a description of an index calculus attack...

What is the objective?

An index calculus attack is a method for trying to solve the discrete logarithm problem (DLP).  Very briefly, it works by writing the target value as the product of powers of elements in a factor base, elements whose logarithm is already known, then extract the target value through laws of logarithms. We now proceed to explain what that means in a bit more detail.

How does it work?

The algorithm can be applied to calculating the discrete logarithm for an arbitrary element $h$ any group $G=\langle g \rangle$. We will rely on the fact that if $x^ay^bz^c=1$, then $a*\log_g(x)+b*\log_g(y)+c*\log_g(z)=\log_g(1)=0$. So, if we can find some collection of $x_i$ who's logarithms are all known values $L_i=\log_g(x_i)$ and somehow manage to write $h=x_1^{a_1}\dots x_r^{a_r}$, then we know that $\log_g(h)=a_1*L_1+\dots+a_r*L_r$. The index calculus attack exploits this, and the efficiency (or inefficiency) of the attack comes down to how fast the various stages of this can be done. For context, alongside the generic technique, we will follow an example in terms of the discrete logarithm over the group $\mathbb{Z}/p\mathbb{Z}$ with generator $g$, the most common application. Being a little lazy, we will use the terms "offline computation" and "precomputation" interchangeably to refer to work that need only be done once per group.  Similarly "online" and "everytime" work corresponds to work that must be done for every DLP required.

 
(Precomputation, basically free) Choose a Factor Base.

The factor base is a collection of elements ${b_0=g,b_1,\dots,b_r}\in G$. How to pick them, and how many to pick, are dependant on the group we're working over and the running times of the later stages. Indeed, simply choice of $r$ generally leads to a trade-off between expensive online (small $r$) and offline (large $r$) computation. Working within our example, one would generally pick $-1$ and the first $r$ primes, since these tend to make the online calculations more efficient (see below).

(Precomputation, expensive but very parallel) Find relations between the DLPs of the Factor Base elements.

Using whatever techniques we can (generally just taking arbitrary products and hoping to get lucky!) we find equations in terms of the different factor base elements relating them to both each other. By taking logs, these translate into linear relations between their discrete logarithms. We continue searching for these until we have found $r$ independent relations, which clearly takes longer the bigger we make $r$. That said, this can easily be done in parallel by simply asking each process to search independently and then merging the result sets. Our example works in exactly this way.

(Precomputation, relatively cheap) Solve the Factor Base DLPs

From the previous step, we have a number of linear relationships between the DLs of the factor base elements. In particular, we have $r+1$ equations in $r+1$ variables (since $\log_g(g)=1$ is known a priori), and so can solve to find all their logarithms. Whilst this requires using a large matrix solver, it tends to be basically free compared to the previous and next steps, since solving linear equations is much more efficient than the almost exhaustive nature of searching for relations.

(Online, expensive but very parallel) Write $h$ as a product of factor base elements

We now try and find a value $y$ and a list $a_i$ such that $h g^y = b_1^{a_1} \dots b_r^{a_r}$. This can easily be done in parallel, since each process tries a different collection of $y$ values,   stopping as soon as one of them. Once that's done, we simply take logs across each value, meaning:

$$\log_g(h) = -y + L_1a_1 + \dots + L_r a_r$$

Now, I've skimmed over a big issue in that previous paragraph: how do we find this $y$? Well, in the case of our example its not too bad. Because the factor base were all small primes, we simply try and factor $hg^y$ using traditional division-like techniques. However, in other groups this can be very difficult indeed, and computationally impractical.

A very brief conclusion
So, the Index Calculus algorithm uses the fact that taking logarithms transforms multiplications into sums to try and find the discrete logarithm of a particular point. It does this by building up a table of known results (the factor base), then finding an element related to the target that can be easily written in terms of these. As such, the algorithm is very generic, and by changing the size of the factor base $r$ one recovers a number of obvious classical attacks. However, picking a value of $r$ such that every stage of the computation can be done efficiently is generally not possible, since either the precomputation or online computation (or often both!) will be prohibitively expensive.

52 Things: Number 32: difference between game-based and simulation-based security definitions

This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know to do Cryptography': a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. In this post we outline the difference between a game-based and a simulation-based security definition.

In a game-based security definition the security is defined, unsurprisingly, by a game. This game revolves around some generic primitive and is usually played by a challenger and an adversary, where the challenger poses a challenge to the adversary with a certain 'goal' in mind. The adversary may further have access to some number of oracles and it is said to 'win' if it achieves its goal, which usually means it needs to provide some 'correct' output depending on the challenge. The advantage of an adversary is defined as a number that roughly corresponds to how much 'better' the adversary can do at the game than a trivial adversary that just guesses its output. E.g., if the adversary needs to output the value of an uniformly random bit, its advantage corresponds to how much better it can do than a success probability of one half. Now, a cryptographic scheme is said to satisfy this security definition if and only if all 'efficient' adversaries cannot achieve a substantial advantage when the generic primitive is instantiated by the scheme.

Informally, one may think of the challenger as a legitimate user that wants to use a cryptographic scheme and of the adversary as the bad guy that wants to achieve something against the wishes of the legitimate user, where this 'achievement' corresponds to the goal of the adversary. Generally, the challenger will have access to all secret parameters (think secret or signing key), whereas the adversary only has access to some oracles (think public hash functions or public key encryption) plus whatever it is given by the challenger during the game (think public parameters and the challenge).

Security proofs in this paradigm include two important concepts. To link security to computationally hard problems they use reductions, which lead to a statement of the following form: 'if an adversary wins the game with non-negligible advantage, it is possible to construct an algorithm that uses the adversary as a subroutine to solve some hard problem efficiently.' The other concept is game hopping through a sequence of games. Here, one takes the event of an adversary winning the game and relates it to events in a sequence of different games. Each subsequent game is close to the previous one in the sense that the adversary cannot tell the difference between two subsequent games unless it can solve some hard problem or alternatively something happens that has a negligible probability of happening.

The previous five blog posts in this series contain four game-based security definitions and one example of a game-based proof with a sequence of games, so we will not consider any specific examples here.


In a simulation-based security definition, security is defined by the existence of a simulator and some ideal 'functionality'. Consider a cryptographic scheme in the real world and now imagine how you would like this scheme to behave in an ideal world. E.g., in a voting scheme, it would be nice to have a trusted third party that has secure channels to all voters, takes in all the votes via these secure channels, and publishes the result and nothing else. A cryptographic scheme is now secure if, for any adversary against this scheme in the real world, there exists a simulator that provides the same output as the adversary in the real world, while interacting with the ideal 'functionality' in the ideal world. This means that any 'attack' possible in the real world can also be applied to the ideal functionality in the ideal world. Conversely, if the ideal functionality resists attacks in the ideal world, the real scheme resists these attacks in the real world as well.

The notion first appears in a paper by Goldreich, Micali, and Widgerson, who show that you can play any game (which is some joint computation by multiple parties) such that at any step of the game, any group of less than half the players know nothing more than they would in an ideal execution of the game with a trusted party. More recently, the notion of simulation-based security appeared in the paper introducing Universal Composability by Ran Canetti. It is mostly used in settings of multi-party computation.


So what is the difference? In the game-based approach, each notion of security has its own game. If this notion correctly captures or models the real world attributes you would like your system to have, then you are done. If your scheme needs to satisfy various notions, you will need to play games for each one. However, there is a known hierarchy in some cases, e.g., IND-CCA security implying IND-CPA security.

Conversely, in the simulation-based approach, the security is modeled by the ideal functionality. Conceptually, your schemes will be secure from attacks that do not break the ideal functionality. This means that different security notions are captured by this model.

For more reading, you can find good discussions on the crypto StackExchange here and here.

52 Things: Number 26: Describe the NAF scalar multiplication algorithm.

This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know' to do Cryptography: a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. In this week, we describe the NAF scalar multiplication algorithm.

The NAF scalar multiplication algorithm is an enhanced form of scalar multiplication, in which the use of Non-Adjacent Form (NAF) representation decreases the expected running time of the algorithm. In more detail:

Let k be a positive integer and P a point on an elliptic curve E over the field $\mathbb{F}_{q}$. The operation that computes the multiplication $Q = k\cdot P$ is known as the elliptic curve scalar multiplication (or point multiplication) and dominates the execution time of elliptic curve cryptographic schemes. One of the most basic methods to compute a scalar multiplication is based on a double-and-add variant of Horner's rule, known as the binary method. As the name suggests, the two most prominent building blocks of this method are the point doubling and point addition primitives. More particularly, to calculate $k\cdot P$, integer k is represented as $k=k_{n-1}2^{n-1}+k_{n-2}2^{n-2}+ \cdots +k_{1}+k_{0}$ , where $k_{i} \in \{0,1\}$, $i= 0,1,2...,n-1$ (binary representation form). The following algorithms form the additive versions of the basic repeated-square-and-multiply methods for exponentiation [1,2].

INPUT: k = (kt−1,..., k1, k0)2, P ∈ E($\mathbb{F}_{q}$). 
OUTPUT: k $\cdot$ P.
       Q←$\infty$.
       For i from 0 to t−1 do
           If ki  = 1 then Q←Q+P.
           P←2P. 
Return(Q). 

INPUT: k = (kt−1,..., k1, k0)2, P ∈ E($\mathbb{F}_{q}$). 
OUTPUT: k $\cdot$ P.
       Q←$\infty$.
       For i from t−1 down to 0 do
             Q←2Q.
             If ki = 1 then Q←Q+P.
Return(Q). 

The first algorithm processes the bits of k from right to left, while the second processes the bits from left to right. The expected number of ones in the binary representation of k for both  algorithms is t/2≈m/2, therefore the expected running time of both algorithms is approximately m/2 point additions and m point doublings [1]: 

$\frac{m}{2} \cdot A + m \cdot D$.

In 1951, Booth [3] proposed a new scalar binary representation called signed binary method and later Rietweisner [4] proved that every integer could be uniquely represented in this format [5]. More particularly, If P=(x,y)$\in$E($\mathbb{F}_{q}$) then −P=(x,x+y) if $\mathbb{F}_{q}$ is a binary field, and −P=(x,−y) if $\mathbb{F}_{q}$ has characteristic > 3. Thus subtraction of points on an elliptic curve is just as efficient as addition. This motivates us to use a signed digit representation $k=\sum_{i=0}^{l-1} k_i \cdot 2^i$, where $k_i \in \{0, \pm \}$. A particularly useful signed digit representation is the non-adjacent form (NAF). A NAF representation of a positive integer k is an expression $k=\sum_{i=0}^{l-1} k_i \cdot 2^i$ , where  $k_i \in \{0, \pm \}$ , $k_{l-1} \ne 0$ , and no two consecutive digits ki are non-zero. The length of the NAF is l [1].

Properties of NAF [1]:

1. k has a unique NAF denoted NAF(k). 
2. NAF(k) has the fewest non-zero digits of any signed digit representation of k. 
3. The length of NAF(k) is at most one more than the length of the binary representation of k. 
4. If the length of NAF(k) is l, then 2l /3 < k < 2l+1/3.
5. The average density of non-zero digits among all NAFs of length l is approximately 1/3. 

NAF(k) can be efficiently computed using the following algorithm [1]:

INPUT: A positive integer k.
OUTPUT: NAF(k).
       i←0.
       While k≥1 do
             If k is odd then: ki ←2−(k mod 4), k←k−ki;
             Else: ki ←0.
             k←k/2, i←i+1.
Return(ki−1, ki−2,..., k1, k0).

The last algorithm presents the way we can modify the left-to-right binary method for scalar multiplication by using NAF(k) instead of the binary representation of k [1]:

INPUT: Positive integer k, P ∈ E($\mathbb{F}_{q}$). 
OUTPUT: k $\cdot$ P.
       Based on previous algorithm compute NAF(k) =$\sum_{i=0}^{l-1} k_i \cdot 2^i$. 
       Q←$\infty$.
       For i from l−1 down to 0 do
             Q←2Q.
             If ki  = 1 then Q←Q+P.
             If ki  = −1 thenQ←Q−P.
Return(Q).

Based on the third and fifth properties of NAF, the expected running time of the NAF scalar multiplication algorithm is approximately [1]:

$\frac{m}{3} \cdot A + m \cdot D$.

[1] Hankerson, Darrel, Scott Vanstone, and Alfred J. Menezes. "Guide to elliptic curve cryptography". Springer Science & Business Media, 2004.
[2] Jonathan Taverne, Armando Faz-Hernández, Diego F. Aranha, Francisco Rodríguez-Henríquez, Darrel Hankerson, Julio López. "Speeding scalar multiplication over binary elliptic curves using the new carry-less multiplication instruction", Journal of Cryptographic Engineering, Vol. 1, No 3, pp. 187-199, 2011.
[3] A.D.Booth, “A Signed binary multiplication technique”, Journal of Applied Mathematics, Vol. 4. No. 2, pp.236-240, 1951 
[4] G.W.Reitwiesner, “Binary Arithmetic”, Advances in computers, Academic Press, Vol. 1, pp.231-308, 1960
[5] Karthikeyan, E. “Survey of elliptic curve scalar multiplication algorithms.” International Journal of Advanced Networking and Applications, Vol. 4, No 2, pp. 1581-1590, 2012