sidhe – PlaidCTF 2020

by goulov and mandlebro

Points: 300 (29 solves)

Given: sidhe-273d8113d1283172865d2285f1b3a5743f5fa7451186ecb89febc75684833df7.tar.gz; nc 149.28.9.162 31337

tldr

  1. Server does the SIDH key-exchange, but reuses its key. We are also given an oracle on the correctness of the agreement.

  2. Known adaptive attack described in https://eprint.iacr.org/2016/859.

  3. Account for Bob (server) having a \(3^n\)-isogeny (Remark 2 in the paper).

attack

The given file in sage implements a server which performs the SIDH key-exchange. The protocol starts with public keys being exchanged by Alice/user \((E_A,\phi_A(P_B),\phi_A(Q_B))\) and Bob/server \((E_B,\phi_B(P_A),\phi_B(Q_A))\) (public parameters \(P_A,Q_A,P_B,Q_B\)). Then, the server decrypts a ciphertext controlled by the user, giving an oracle that distinguishes a good decryption (“Good ciphertext”) from a bad one (“Bad ciphertext”).

More importantly, the server performs 300 key-exchanges, always with the same secret key. But, there is an adaptive attack against key reuse in SIDH, which makes this setting insecure and it is the vulnerability of this challenge.

The attack for this vulnerability is given in the paper On the Security of Supersingular Isogeny Cryptosystems [GPST16], namely in Algorithm 1. The only catch is that the server is playing Bob in the key-exchange, meaning it has a \(3^{e_B}\)-isogeny and its group is \(E[3^{e_B}]\) (this is referenced in Remark 2 in the paper).

In practice, given the actual implementation, one can see that the secret keys are normalized as \((1,\alpha)\). The goal is then to recover Bob’s secret key \(\alpha\), which we write in base \(3\) as \(\alpha= \alpha_0 + \alpha_1\cdot3^1 + \ldots + \alpha_i\cdot3^i + \ldots + \alpha_{e_B-1}\cdot3^{e_B-1}\), and this will be done successively trit by trit \(\alpha_i\).

Let \(R = \phi_A(P_B), S = \phi_A(Q_B)\). We will craft indistinguishable (to the server) public keys to decide between:

\[\begin{cases} \left< R+[\alpha]S\right> \quad &\text{ if } \alpha_i = 0\\ \left< R+[\alpha]S + [3^{e_B-1}]S\right> \quad &\text{ if } \alpha_i = 1 \\ \left< R+[\alpha]S + [2 \cdot 3^{e_B-1}]S\right> \quad &\text{ if } \alpha_i = 2 \end{cases}\]

And so we would send to the server our public key (omitting scaling factor \(\theta\)),\[ (E_A, R - [x3^{e_B - i - 1}]S, [1+3^{e_B - i - 1}]S) \] with which it computes \[ \left< R + [\alpha]S + [3^{e_B-i-1}][\alpha - x]S\right>, \] meaning that the shared key will only match if \((3^{e_B-i-1})(\alpha-x) = 0 \;(\text{mod } 3^{e_B})\), which the oracle tells us. From this and rewriting \(\alpha\) as \(\alpha = K_i + \alpha_i\cdot 3^i + 3^{i+1}\cdot \alpha’\), where \(K_i\) is the partial key already recovered up to trit \(i-1\), and we can deduce what \(x\) should be:

\[\begin{align} (3^{e_B-i-1})(\alpha-x) &= 0 \enspace\text{mod } 3^{e_B} \\ (3^{e_B-i-1})( K_i + \alpha_i\cdot 3^i + 3^{i+1}\cdot \alpha'-x) &= 0 \enspace\text{mod } 3^{e_B} \\ 3^{e_B-i-1}\cdot K_i + 3^{e_B-1}\cdot \alpha_i + 3^{e_B}\cdot \alpha'- 3^{e_B-i-1}\cdot x &= 0 \enspace\text{mod } 3^{e_B} \\ 3^{e_B-i-1}\cdot x &= 3^{e_B-i-1}\cdot K_i + 3^{e_B-1}\cdot \alpha_i \enspace\text{mod } 3^{e_B} \\ x &= K_i + 3^{i}\cdot \alpha_i \enspace\text{mod } 3^{e_B} \end{align}\]

For each query, we can begin by guessing whether \(\alpha_i=0\). If we are successful, we proceed to the next trit, otherwise we guess \(\alpha_i=1\) and from there, either the oracle is positive and the trit is \(1\) or it is negative and we know the trit must be \(2\).

Since we require at most 2 attempts to learn each trit, we require at most \(2\cdot e_B = 2\cdot 137 = 274\) which is less than the allowed \(300\) attempts.

Finally, to avoid detection by the validation done (via Weil pairing) when the server receives the public key, there is the need to multiply by a scaling factor \(\theta\) (sage actually fails to compute this square root in Zmod(3^e) so we load it from sqrts.sage). However, for the final trits, avoiding detection is not possible (Lemma 3.3) so these are bruteforced locally, which does not take too long…

PCTF{if_you_wish_for_postquantum_crypto_ask_a_supersingular_isogenie}

resources:

The solution code can be found in sidhe_stt.zip. For all possible details and proofs one should refer to https://eprint.iacr.org/2016/859.