Blockchains: How to Steal Millions in 2^64 Operations

I’ve been reviewing the source code of a number of blockchain thingies, both for paid audits and for fun on my spare time, and I routinely find real security issues. In this post I’ll describe a vulnerability noticed a while ago, and now that Lisk finally describes it and warns its users, I can comment on its impact and exploitability.

TL;DR: you can hijack certain Lisk accounts and steal all their balance after only 2⁶⁴ evaluations of the address generation function (a combination of SHA-256, SHA-512, and a scalar multiplication over Ed25519’s curve).

What is Lisk?

In blockchain-speak, Lisk is yet another platform for building decentralized applications. To simplify, Lisk is a kind of Ethereum where contracts are written in JavaScript—instead of Solidity or Viper—and where the consensus protocol relies on proof-of-stake instead of proof-of-work. More precisely, Lisk uses a delegated proof-of-stake (DPoS) protocol, wherein a limited number of nodes, chosen by user through a voting mechanism, will actually validate transactions. Having only a limited number (101) of validators speeds up transactions validation while keeping Lisk kinda decentralized.

As I’m writing this, Lisk is ranked 19th on coinmarketcap, with a market cap of approximately 3.4 billions of dollars.

First problem: short addresses

Like in any cryptocoin platform, coin owners are identified by an address. In Lisk, addresses are 64-bit numbers, such as 3040783849904107057L. Whereas in Bitcoin, for example, an address is simply a hash of one’s public key, a Lisk address is derived deterministically from a passphrase, while generating the users’s keypair along the way. In more details, it works like this:

1. Given a passphrase, compute a 256-bit seed as seed = SHA-256(passphrase).
2. Derive an Ed25519 keypair from this seed, which involves computing SHA-512(seed) and a scalar multiplication.
3. Compute the SHA-256 hash of the public key, and define the address as the last 8 bytes of the 32-byte hash.

Now you guess part of the problem: you can find a preimage of any address in approximately 2⁶⁴ evaluations of the above series of operations.

Second problem: no address–key binding

Ideally, short addresses shouldn’t be a huge problem: if an address already exists and is bound to a key pair, you shouldn’t be able to hijack the account by finding another passphrase/keypair mapping to this address.

And that’s the second problem: an address isn’t bound to a keypair until it has sent money to another address (or voted for a delegate). What this means is that if an account only receives money but never sends any, then it can be hijacked by finding a preimage—and once the attacker has found a preimage, they can lock the original user out of their account by issuing a transaction and binding the address to their new passphrase/keypair.

I don’t know how many accounts are vulnerable, but it’s easy to find ones: just by browsing through the top accounts list, you can for example find a vulnerable account that holds more than 1.6 million of Lisk units (or $48M)—look for an account with no associated public key.

Exploitation and mitigation

Running the 2⁶⁴ address computations isn’t instantaneous though; because it involves a key generation operation, these 2⁶⁴ operations are considerably slower than (say) 2⁶⁴ evaluations of a hash function like SHA-256. But completing the attack within a month will clearly cost you less than $48M.

And of course in practice you’ll parallelize the attacks on N cores, and you’ll target one-of-M addresses, so the expected running time will only be around 2⁶³/NM operations. With only 64 targets and 256 cores, we’re talking of 2⁴⁹ iterations’ latency.

As Lisk now recommends, “it’s important to broadcast the correct public key to the network for any given Lisk address. This can be done by simply sending at least one transaction from a Lisk account.”

I don’t know whether this vulnerability has been exploited, but yet again this shows that blockchain systems security is a vastly unexplored area, with lot of unaudited architectures and source code, and new bug classes to be found and exploited.

PoC||GTFO

I’ve tested that the attack works, by first finding a collision (two passphrases/keypairs mapping to the same address), creating an account using the first passphrase, receiving money to this address, and then hijacking the account using the second passphrase. I also simulated a real preimage attack to estimate the cost of the attack on my machine (can’t find the numbers though, it was a while ago). If you’re interested in benchmarking this, the following code can be useful (combined with an optimized implementation of Ed25519’s arithmetic).

#define N 16

// generates a pub key from a 32-byte seed				
int pubkeyFromSeed(unsigned char *pk, const unsigned char *seed)
{
  unsigned char az[64];
  sc25519 scsk;
  ge25519 gepk;

  sha512(az,seed,32);
  az[0] &= 248;
  az[31] &= 127;
  az[31] |= 64;

  sc25519_from32bytes(&scsk,az);

  ge25519_scalarmult_base(&gepk, &scsk);
  ge25519_pack(pk, &gepk);
  return 0;
}

// computes raw pub key from utf-8 secret
static inline void pubkeyFromSecret(const char *secret, size_t secretlen, uint8_t *pk) {
    // first hash secret
    uint8_t seed[32];
    SHA256((const unsigned char*)secret, secretlen, seed);
    pubkeyFromSeed(pk, seed);
}

// computes raw address from raw pubkey
static inline void addressFromPubkey(const uint8_t *pk, uint8_t *address) {
    uint8_t hash[32];
    SHA256(pk, 32, hash);
    for(int i=0; i<N/2; ++i) address[i] = hash[7-i];
}

string addrToStr(unsigned long long a) {
    stringstream ss;
    ss << hex << setw(16) << setfill('0') << a;
    return ss.str();
}

// address is N/2-byte long
unsigned long long addressToInt(uint8_t * address) {
    unsigned long long addressint = 0;
    for(int i=0; i<N/2; ++i) {
        addressint |= (uint64_t)address[i] << (56 - (i*8));
    }
    return addressint;
}

// tested to match /api/accounts/open
unsigned long long addressFromSecret(unsigned long long in) {
    uint8_t pk[32];
    uint8_t address[N/2];
    string s = addrToStr(in);
    pubkeyFromSecret(&s[0u], N, pk);
    addressFromPubkey(pk, address);
    return addressToInt(address);
}

And there’s more: secret keys aren’t secret

Ah, and there’s another security issue in Lisk: looking at the client API documentation, you’ll notice that clients need to send their passphrase (the secret value) to open an account or to send a transaction. In other word, Lisk is missing the whole point of public-key cryptography, which is to keep secret keys secret. Oh, and there’s even an endpoint (/api/accounts/open) that allows you to request your public key given your secret key. So much for trustlessness and decentralization.