ZeroTier is a "a smart ethernet switch for earth". It creates encrypted virtual L2 network which can be joined by any authorized device. The devices are identified by 5 byte strings, which are hashes of Curve25519 public keys.
The hash function used for identity derivation is not standard one like SHA256 - with only 2^40 possible values it would too easy to spoof someone identity. Instead, a custom proof of work function is used. This function is claimed to be memory-hard (i.e. requiring a lot of memory to compute) - this property would make it harder to crack it on GPU or custom ASICs.
I show that the proof-of-work function isn't in fact memory hard. For now, it is mostly theoretical result - the computation still takes long time. Most importantly, the full public keys are cached by devices and centralized root servers. Even when someone spoofs identity, he would still need much luck and collaboration with ZeroTier Inc, which runs the root servers. I have notified ZeroTier Inc about 3 months ago and they weren't too worried about the consequences of my 'attack' (which is an opinion I agree with), saying they will eventually redesign the identity derivation function during transistion to post-quantum ciphers.
The hash function
The hash function used for identity derivation is not specified anywhere, so I have extracted its description from ZeroTier code.
computeMemoryHardHash(publicKey: string) -> string
digest = sha512(publicKey) # 64 bytes
initialize Salsa20 stream with IV=digest[0:32] key=digest[32:64]
genmem = empty 2MB array
current = 64 zero bytes
# the genmem array is initialized with CBC-like scheme
for i=0..2000000/64: # loop 1
current = encrypt with salsa(current)
genmem[64*i:64*(i+1)] = current
for i=0..2000000/16: # loop 2
num1 = convert genmem[8*i:8*(i+1)] to big-endian integer
num2 = convert genmem[8*(i+1):8*(i+2)] to big-endian integer
idx1 = num1 % 8
idx2 = num2 % (2000000/8)
swap digest[8*idx1:8*(idx1+1)], genmem[8*idx2:8*(idx2+1)]
digest = encrypt with salsa(digest)
if digest[0] >= 17:
if generating identity, retry with different public key
if validating identity, abort
(this part makes it easier to validate identity, than to generate one - a defining characteristic of a proof-of-work function)
return digest[59:64] # last 5 bytes
We can see that computeMemoryHardHash tries to shuffle memory around in a way that depends on results of previous computation. However, if we look at this code long enough, we can see that sometimes it miserably fails. Specifically, if during the last iteration of loop 2 idx1 == 7, then the result (last 5 bytes of digest) only depends on X=gemem[8*idx2:8*(idx2+1)]. This happens, because Salsa is a stream cipher, so digest = encrypt with salsa(digest) encrypts digest[59:64] in a way than only depends on old digest[59:64].
At first glance, X still can't be computed without lots of memory - it could be changed at any time by swap in loop 2. However, it turns out that the most values of genmem won't ever be modified by loop 2. The loop runs for 2000000/16 iterations and each time psuedorandomly selects one of 2000000/8 indexes to modify - so any particular index will be modified with probability (1-2000000/8)**(2000000/16) ≈ 39%.
With this knowledge, we can create a sketch of memory-easy version of the hash function:
computeMemoryEasyHash(publicKey: string) -> string
digest = sha512(publicKey) # 64 bytes
initialize Salsa20 stream with IV=digest[0:32] key=digest[32:64]
current = 64 zero bytes
# the genmem array is initialized with CBC-like scheme
for i=0..sizeof genmem/64: # loop 1
current = encrypt with salsa(current)
# this is the same as last num1 with probability 61%
lastnum1 = convert current[48:56] to big-endian integer
# this is the same as last num2 with probability 61%
lastnum2 = convert current[56:64] to big-endian integer
lastidx1 = num1 % 8
lastidx2 = num2 % (2000000/8)
if lastidx1 == 7: # probability 12%
retry
initialize Salsa20 stream with IV=digest[0:32] key=digest[32:64]
# generate genmem again, now to fetch block that contains `genmem[8*lastidx2:8*(lastidx2+1)]`
current = 64 zero bytes
for i=0..lastidx2/8: # loop 1
current = encrypt with salsa(current)
# 61% that swappedvalue == genmem[8*lastidx2:8*(lastidx2+1)]
swappedvalue = current[lastidx2%8]
return swappedvalue[3:8]
Overall, the probability that computeMemoryEasyHash returns correct results is about 1/35.
Suppose Eve wants to spoof identity of Alice. She needs to generate same identity as Alice, but with private/public key known by her ("preimage"). She will run computeMemoryEasyHash on her GPU or ASIC. When the function returns the identity of Alice, Eve will compute the identity again using computeMemoryHardHash (on CPU). If both functions return the same result, she has what she wants. Otherwise she just repeats the whole procedure.
computeMemoryEasyHash is correct with probability 1/35, but Eve also needs to fullfil proof-of-work condition (digest[0] >= 17), so she will need to call computeMemoryHardHash about 35*(256/17) ≈ 527 times to find the preimage.
The whole operation requires 2^26*2^40*(256/17)*35 ≈ 2^74 Salsa20 operations. Even with ASIC acceleration (assuming 60Gops/s), the computation would take 10.000 years. Algorithmic improvements to computeMemoryEasyHash are almost surely possible.
Quite messy proof of concept is available.