Friday, May 29, 2015

SOLILOQUY: a New Primitive and a Quantum Attack

This week, Ana gave a study group talk based on the paper Soliloquy: a Cautionary Tale by Campbell, Groves and Shepherd of CESG (the Information Security arm of GCHQ).

The paper describes a new primitive, SOLILOQUY, a Key Encapsulation Mechanism, which was proposed secretly in 2007, found to resist classical cryptanalysis (for reasons omitted by the authors), but then abandoned due to the development of "a reasonably efficient quantum attack on the primitive". The paper is very complicated and appears to skip over a number of technical details, so we will present here a very high level view of SOLILOQUY and the attack, before mentioning some of the discussion about this result that has taken place, both in our study group and elsewhere in the academic community.

Construction of SOLILOQUY

Let $n$ be a prime, about 10 bits in size, and $\zeta$ a primitive $n$th root of unity. Let $K$ be the number field $\mathbb{Q}(\zeta)$ and $\mathcal{O}=\mathbb{Z}[\zeta]$ the ring of integers in $K$. One selects a candidate private key $\alpha = \sum_{i = 1}^{n}a_i\zeta^i \in \mathcal{O}$ where the coefficients $a_i$ are sampled from a discrete Gaussian distribution of mean 0 (so they are small). Let $p$ be the norm of $\alpha$. The pair $(\alpha, p)$ can be used as a SOLILOQUY key pair if
  1. $p$ is prime
  2. $c = 2^{\frac{(p-1)}{n}} \not\equiv 1 \: (\mathrm{mod}\: p)$
where condition 2 occurs with probability $1 - \frac{1}{n}$.

We check these conditions because, for a prime $p \equiv 1 \: (\mathrm{mod} \: n)$, the principal ideal $p\mathcal{O}$ decomposes into a product of prime ideals $\mathcal{P}_i$, each with a representation of the form $\mathcal{P}_i = p\mathcal{O} + (\zeta - c_i)\mathcal{O}$ where the $c_i$ are the non-trivial $n$th roots of unity mod $p$. The conditions above ensure that $\alpha\mathcal{O}$ is one of these $\mathcal{P}_i$ and that one of these $\mathcal{P}_i$ has the form $\mathcal{P} = p\mathcal{O} + (\zeta - c)\mathcal{O}$ for the particular choice $c = 2^{\frac{(p-1)}{n}}$. Then, since the Galois group $\mathrm{Gal}(K/\mathbb{Q})$ permutes the prime ideals $\mathcal{P}_i$, we can make sure that $\alpha\mathcal{O} = \mathcal{P}$ by taking some Galois conjugate of $\alpha$ (which will just reorder the coefficients $a_i$).

Now there is a natural homomorphism $\psi : \mathcal{O} \to \mathcal{O}/\mathcal{P} \simeq \mathbb{F}_p$ given by \[\psi(\epsilon) = \psi \left ( \sum_{i = 1}^{n}e_i \zeta^i \right) = \sum_{i = 1}^{n}e_i c^i \: (\mathrm{mod} \: p) = z\] and this is the encryption function in SOLILOQUY. One samples an ephemeral key $\epsilon$ from $\mathcal{O}$ as above, (whose coefficients must again be sampled with a mean of 0) and encapsulates it as $z$, viewed as a (rational) integer $0 \leq z < p$.

To decrypt, one computes $\epsilon = z - \lceil z\alpha^{-1} \rfloor \cdot \alpha$ where $\lceil - \rfloor$ is coordinate-wise rounding. That this is correct is not proved in the paper, but roughly corresponds to $\epsilon$ being small enough that $\lceil \epsilon \cdot \alpha^{-1} \rfloor = 0$. 

The Quantum Attack
Key recovery is an example of the small principal ideal problem: we have a representation $p\mathcal{O} + (\zeta - c)\mathcal{O}$ of the principal ideal $\mathcal{P} = \alpha\mathcal{O}$ of $\mathcal{O}$ and wish to compute the small generator $\alpha$. There are classical sub-exponential attacks for such a problem but the authors claim to provide the first 'practical' quantum algorithm for it. First, they make some simplifications, citing a 2004 result in Algebraic Number Theory that shows it suffices to look at the real subfield $\mathbb{Q}\left( \zeta + \zeta^{-1} \right)$ of $K$ and find $\alpha' = \alpha \cdot (\alpha)^*$ in the ring of integers $\mathcal{O}' = \mathbb{Z}\left [ \zeta + \zeta^{-1} \right ]$. Furthermore, they claim that in this setting it is easy to find a short generator of a principal ideal given any generator. So, to find $\alpha'$ (and hence find $\alpha$), it suffices to find any generator of $\alpha' \mathcal{O}'$.

The attack itself uses complicated ideas, but essentially amounts to using a logarithm function to transform the group of units $\mathcal{O}'^{\times}$ (with multiplicative structure) into a lattice $\Lambda$ (with additive structure). Then we consider an encoding of $\alpha'$ as a hidden, high-dimensional lattice $\Lambda_{\alpha'}$ with known sublattice $\Lambda$ of co-dimension 1. Then, using a "quantum fingerprint" of the hidden lattice, one can approximate the dual lattice $\Lambda_{\alpha'}^*$ (and iterate this procedure to produce many samples close to the true dual lattice). Then, with $\Lambda_{\alpha'}^*$, one can find a basis for $\Lambda_{\alpha'}$, determine the value of $\alpha'$ and hence find the secret key $\alpha$.

While we were unable to examine the algorithm closely during the study group, some felt it was unclear how efficient the proposed attack is (even with quantum computers). Indeed, there has been a fair bit of discussion about the meaning of this paper in the academic community: see, for example, this thread.

While it is welcome that the researchers at GCHQ are sharing some of their work with the wider community, the paper is slightly unclear in places. It was felt that greater clarification was needed for the new attack to have impact beyond SOLILOQUY itself. 

Wednesday, May 27, 2015

52 Things: Number 34: Describe the Baby-Step/Giant-Step method for breaking DLPs

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 blog, we discuss the Baby-Step/Giant-Step attack against DLPs. 

Baby-Step/Giant-Step is an algorithm developed by Daniel Shanks that solves Discrete Logarithm Problem (DLP), of which its hardness founded many of our mordern security protocols.

First, let's just briefly recall DLP.

Given a cyclic group $G$ of order $n$, a generator $g$ and an element of the group $h$, the DLP is to find $x$, such that 

Now let's come back to Baby-Step/Giant-Step.

Since $n$ is the group order, so we have $0 \leq x \leq n$. Therefore we can write $x$ as
x = i\lceil \sqrt{n} \rceil + j
where $ 0 \leq i,j \leq \sqrt{n}$.

So the DLP equation can be rewritten as
h = g^{i\lceil \sqrt{n} \rceil + j}\\
h(g^{-j}) = g^{i\lceil \sqrt{n} \rceil}
The problem is transformed into finding a pair of $(i,j)$ that satisfies the new equation.

One way to do this is to precompute a table of $\{g^{i\lceil \sqrt{n} \rceil}\}$ over $0 \leq i \leq \sqrt{n}$ and $g^{-1}$. For any given $h$, we iterate $j$ for $h(g^{-1})^j$ until we find a match in our precomputed table, which essentially means

g^{i\lceil \sqrt{n} \rceil} = h(g^{-1})^j = h(g^{-j})

Once a match is found, we can simply reconstruct $x$ using

The algorithem has both time and space complexity of $O(\sqrt{n})$. Fortunate for us, this is just not good enough to tear our cryptographic life apart.

Friday, May 22, 2015








[1] -
[2] -

One-Round Cat Exchange

Suppose two parties have generated public/private keypairs and published their public keys. Non-interactive key exchange (NIKE) allows them to agree on a shared secret key without interaction.

This is the internet, so let's demonstrate with cats. The private key is represented by a male cat, and the corresponding public key by a female cat of the same colour. Alice generates a keypair and publishes her public key, and Bob does the same.

Now Alice can obtain Bob's public key, and combine it with her private key to generate a shared secret key. Alice's private key is a male cat, and Bob's public key is a female cat, so they make a shared secret kitten. As anyone with basic knowledge of feline genetics knows, two cats of different colours will have offspring in the colour of the parent whose colour has the largest hex value, with spots in the colour of the parent with the smaller hex value.

Bob used his private key and Alice's public key to generate the shared key. These kittens look the same, so Alice and Bob now have a shared secret key. Great! However this process always generates the same key, which is a problem if the key is compromised. One-round key exchange (ORKE) can help. At the cost of one round of interaction, Alice and Bob can have a whole litter of kittens.

In this week's study group Bin presented a generic construction of ORKE from NIKE published by Bergsma, Jager and Schwenk at PKC this year. The construction makes use of a deterministic strong signature scheme and a PRF.

The users generate NIKE keypairs as before, but now also generate signing keys.

To generate a shared session key, they generate temporary NIKE keypairs, and sign the temporary public key.

After receiving the other party's signed temporary public key, they can compute a shared secret key. First they check the signature is valid, and then they begin computing four NIKE keys using each possible permutation of temporary and long-term NIKE keys available.

Though Alice and Bob compute the second and third keys in a different order, this doesn't matter since the final key is computed through the commutative XOR operation. In fact the session key isn't just the XOR of the four NIKE keys - the NIKE keys are used as keys for a PRF evaluated at a common point derived from the long-term public keys, and the outputs XORed - but why let details clutter cartoon cats. The scheme is secure in a version of the enhanced CK security model for key exchange, and is standard model secure if instantiated with standard model secure components. The proof is quite straightfoward, ignoring the complexities of the security model itself, and you can check it out on eprint.

Friday, May 15, 2015

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.

Friday, May 8, 2015

52 Things: Number 31: Game Hopping Proof

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 give an example of a proof that uses the 'game hopping' technique.

Note, this blog post is based on Section 3.3 of 'An Introduction to Provable Security' by Douglas Stebila, downloadable via this link.

Recall the definition of IND-CCA security for a public key encryption scheme, described by Ana here. If one removes the decryption oracle from the adversary, we obtain the IND-CPA (indistinguishability under chosen-plaintext attacks) security notion. Note that removing the encryption oracle does not change the adversary's view since it holds the public key and can therefore produce its own encryptions.

In an earlier blog post, we described the Decisional Diffie-Hellman (DDH) problem. In this post, we are going to use a technique called 'game hopping' to show that the ElGamal encryption scheme is IND-CPA secure if DDH is hard. Loosely speaking, we will transform the IND-CPA game against ElGamal into a game against DDH and show that an adversary's advantage in the first game cannot be more than their advantage in the second. So if their advantage in the second game is negligible (which is the assumption that DDH is hard), the advantage in the first game must also be negligible (showing that the encryption scheme is IND-CPA secure).

Firstly, let's describe the ElGamal scheme. We work in a cyclic group $G$ of prime order $q$ with generator $g$. (Implicitly the selection of the group depends on a security parameter $\lambda$ and when we say that a quantity is negligible, we mean a negligible function of $\lambda$, but we'll omit those details here.) Plaintexts and ciphertexts are group elements. The private key is a secret exponent $x \in \mathbb{Z}_q$ and the public key is $X = g^x$. To encrypt a message $M \in G$, one selects an exponent $y \in \mathbb{Z}_q$ uniformly at random, computes $c_1 = g^y$, $c_2 = MX^y$ and the ciphertext is the pair $(c_1, c_2)$. To decrypt, notice that $c_2 = MX^y = M(g^x)^y = M(g^y)^x = Mc_1^x$ so, with the private key $x$ we just compute $M = c_2c_1^{-x}$.

Now consider the following game $\mathrm{Game}_0$ played by a PPT adversary $\mathcal{A}$.
  1. $x \overset{\$}{\leftarrow} \mathbb{Z}_q, X \leftarrow g^x$ (generate the public, private key pair)
  2. $(M_0, M_1) \overset{\$}{\leftarrow} \mathcal{A}(X)$ (the adversary, in possession of the public key, produces a pair of challenge messages, possibly using a randomised process)
  3. $b \overset{\$}{\leftarrow} \{0,1\}$ (a random bit is chosen)
  4. $y \overset{\$}{\leftarrow} \mathbb{Z}_q, c_1 \leftarrow g^y, Z \leftarrow X^y, c_2 \leftarrow M_bZ $ (an encryption of message $b$ is produced)
  5. $b' \overset{\$}{\leftarrow} \mathcal{A}(c_1, c_2)$ (the adversary, in possession of the ciphertext, produces a bit, possibly using a randomised process)
  6. if $b = b'$ then return 1, else return 0.
We say $\mathcal{A}$ wins $\mathrm{Game}_0$ if the game returns 1. From the definition in Ana's blog, it should be clear that the advantage of $\mathcal{A}$ against the IND-CPA security of ElGamal (with parameters $G$, $q$ and $g$) is $2|\mathrm{Pr}[\mathcal{A} \: \mathrm{wins \: Game}_0] - 1/2|$ (1).

Next, consider a new game $\mathrm{Game}_1$. This game is exactly as above, except that in Step 4, we replace the command 
$Z \leftarrow X^y$
$z \overset{\$}{\leftarrow} \mathbb{Z}_q, Z \leftarrow g^z$.
So the new ciphertext is $(c_1, c_2) = (g^y, M_bg^z)$ instead of $(c_1, c_2) = (g^y, M_bg^{xy})$. 

Again we say $\mathcal{A}$ wins this game if it returns 1. What is the probability that this happens? Note that $Z$ is now a totally random group element by the randomness of $z \in \mathbb{Z}_q$. So $c_2$ is also a random group element, independent of $X$, $c_1$ and $b$. So the adversary gains no information about $b$ from $(c_1, c_2)$, meaning it outputs the correct bit and wins the game with probability exactly 1/2 (2).

Now we bound the difference in probability for an adversary to win each of the games. Since the only difference in the two games is that the group element $g^{xy}$ is replaced by a random group element $g^z$, it is easy to see how this relates to the DDH problem, where an adversary must distinguish between the triples $(g^x, g^y, g^{xy})$ and $(g^x, g^y, g^z)$ for a random exponent $z \in \mathbb{Z}_q$. To make the link between the games precise, we use the adversary $\mathcal{A}$ to build an adversary $\mathcal{B}$ against DDH as follows:
  1. On input $(X, Y, Z)$, run $\mathcal{A}$ on input $X$ to receive a challenge pair $(M_0, M_1)$
  2. Select a bit $b$ uniformly at random and compute $m_bZ$
  3. Give the 'ciphertext' $(Y, m_bZ)$ to the $\mathcal{A}$ and receive a bit $b'$
  4. If $b = b'$, guess that $Z = g^{xy}$ and return 1, else guess $Z$ is random so return 0.
If $\mathcal{B}$ is given a real Diffie-Hellman triple $(g^x, g^y, g^{xy})$ then the above is a perfect simulation of $\mathcal{A}$ playing $\mathrm{Game}_0$, and if $\mathcal{B}$ is given a fake triple $(g^x, g^y, g^z)$ then it is a perfect simulation of $\mathcal{A}$ playing $\mathrm{Game}_1$. Therefore, the difference between the probability of $\mathcal{A}$ winning $\mathrm{Game}_0$ and $\mathcal{A}$ winning $\mathrm{Game}_1$ is precisely the difference between the probability that $\mathcal{B}$ outputs 1 on input $(g^x, g^y, g^{xy})$ and outputs 1 on input $(g^x, g^y, g^z)$, which is exactly the advantage of $\mathcal{B}$ against DDH.

Combining the above with facts (1) and (2) (and using the triangle inequality to take care of the modulus signs), we can easily obtain that the advantage of $\mathcal{A}$ against the IND-CPA security of ElGamal is no greater than the advantage of $\mathcal{B}$ against DDH. So if DDH is hard for all polynomial time adversaries (meaning their advantage is negligible), ElGamal must be IND-CPA secure.

Tuesday, May 5, 2015

Eurocrypt 2015: Threshold Implementations



f_1(x_2, x_3) = y_1, \\
f_2(x_1, x_3) = y_2, \\
f_3(x_1, x_2) = y_3.

y_1+y_2+y_3 = y, \\
x_1+x_2+x_3 = x.



[1] -
[2] -
[3] -
[4] -
[5] -
[6] -

Saturday, May 2, 2015

52 Things: Number 30: Roughly outline the BR security definition for key agreement

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 look at a security definition for authenticated key exchange.

Establishing a shared key between two parties is one of the oldest problems in cryptography, and turns out to be much harder than standard encryption, even when just considering definitions. Although the classic Diffie-Hellman protocol from 1976 seems to solve the problem, it provides no authenticity guarantee - i.e. that a key has been agreed with the right person - since a man-in-the-middle attack can easily be performed.

To model this kind of attack, and others, we need a security definition. There are two main approaches when defining the security of a key exchange protocol, namely those based on a symbolic model and those using a computational model. In the symbolic model, which become popular in the '90s after the classic paper on BAN logic, techniques from formal methods are used to model and analyse a protocol. The symbolic model is good for identifying attacks, but it is difficult for the underlying logic to capture all classes of attacks, so analysis in this model does not provide great security guarantees, but can be semi-automated using theorem provers.

In their seminal 1993 paper, Bellare and Rogaway instead created a game-based security definition for authenticated key exchange in a computational model, similar to the IND-CPA and IND-CCA definitions for encryption. In this model, cryptographic primitives are not assumed to be unbreakable, but instead we attempt to quantify the success probability of an adversary by computing their 'advantage' in a security game. The main feature of an adversary that we wish to encompass is that all communication is under the adversary's control: they can read, modify, delay and replay messages. They can also run any number of instances of the protocol simultaneously with other parties. The intuition behind the AKA security game is that the only way an adversary can get a party to accept an agreed key is by forwarding honest messages from a genuine protocol run, in which case they cannot possibly learn anything new.

The security game consists of a number of different oracles that an adversary can query. The three main oracles are the corruption oracle, which allows the adversary to take control of a chosen party, the key registration oracle, which registers a public key for any chosen user, and the message oracle, which is the main oracle used for passing messages. Note that messages are not sent directly between the participants, instead the adversary does this using the message oracle.

The message oracle is the main oracle allowing the adversary to create protocol sessions with parties (where they aim to establish a short-term, or ephemeral, shared key) and send messages. When querying the oracle, they can take one of the following actions:
  • Start a new session between two users
  • Learn the secret key of any terminated session
  • Send a message in an existing session and receive the response
The security game follows the real-or-random paradigm, similarly to standard definitions of encryption, by choosing a secret bit $b$; if $b=0$ then the adversary is given a random key for its challenge, otherwise it gets the real key. After interacting with the oracles, the adversary chooses a single session that has terminated, in which both parties are not corrupted and there is no 'matching' conversation where the key has been revealed (to prevent a trivial break), and receives a challenge key for this session. They win the game if they correctly guess $b$.

A protocol is said to be a secure authenticated key exchange protocol if it is correct, and any adversary's strategy is the above game is no better than random guessing. The above outline is only a rough sketch, of course, and there are many further details in the paper.