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 264 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 264 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 264 address computations isn’t instantaneous though; because it involves a key generation operation, these 264 operations are considerably slower than (say) 264 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 263/NM operations. With only 64 targets and 256 cores, we’re talking of 249 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.

11 comments

  1. Hi JP Aumasson,

    Thank you for the article. However, the numbers you provided in the “Exploitation and mitigation” section make several wrong assumptions and in reality, it is much more difficult to complete the mentioned attack. Finding a collision with a unique account out of 264 will take much more than a month even assuming an overwhelming computational power. As you mention, derive Ed25519 keypair is orders of magnitude slower than evaluations of a hash function. If we assume there is a hardware capable of computing a Gigakeypair per second (109 Ed25519 keypairs every second), an attacker will take an average of 585 years to find the collision with the mentioned account holding 1.6 million LSK. And this is assuming such a hardware (or an optimized implementation of Ed25519’s arithmetic) exists.

    If we take 64 insecure Lisk addresses as you did, the same attacker will take an average of four months to find a collision with such “ideal” cracking hardware/software. But in this case, the collision will be any of the 64 addresses which may probably have a small amount of LSK, and make the attack again not profitable. These numbers are not complex maths, it is just applying the well-known birthday attack to this problem: https://en.wikipedia.org/wiki/Birthday_attack

    Having said that, the security of our users is taken very seriously by Lisk HQ. The current address system in place dates back to Max and Oliver’s time at Crypti, where it was initially implemented. We have a team dedicating to solving the remaining flaws in the system.

    We still recommend that all users initiate their account by conducting at least one transaction; it is as simple as sending yourself one LSK. By doing this, the public key is cemented into the Lisk blockchain and reduces any insecurities regarding the current address system.

    Lisk Core 1.0 marks a significant release as the API will completely change, removing all current limitations. You can view the new (completed) API here: https://github.com/LiskHQ/lisk/projects/6

    Best,
    Lisk HQ

  2. Thanks Jennifer for the response, and I agree that Lisk properly warned its users.

    To clarify, when I talk of a “collision” in my post, I mean 2 arbitrary secrets to the same address, as per the established definition of a collision. This takes ~2^32 evaluations of the address computation, which takes maybe an hour on a standard multi-core machine. If I remember correctly, the rate on a single core was ~2^28 attempts per core per hour; renting 2048 cores and targeting only 64 addresses over 3 months, that’s only a 1/1000 chance to hit one address. This is unacceptably high, with respect to crypto/security standards.

  3. Hi JP,

    Thank you for your reply. Your reasoning seems to be in line with our cryptographer’s numbers. He said it will take at least four months to hit one of the 64 addresses and you say it will take around three months to have 1/1000 of a chance to hit them.

  4. Not sure what’s happening.. indeed a number of accounts that send money to this account have had their first transaction after the publication of this post.

  5. Seems to be a false alarm. Most likely some of the ‘top accounts’ of a few days back are intermediate (exchange) accounts.Your article might have been a trigger for them to get rid of the existing intermediate accounts. It would not surprise me if they started consolidating the accounts to ensure that there was a public key attached. People from inside the Lisk team have stated that they know who the owner would be, but cannot disclose it publically. As you said, and what i expected: finding collisions this fast is unlikely.

  6. There is one significant miscalculation there: anybody wanting to steal funds would not limit themselves to renting 1k cores for usual market prices … they woudl go for 1000k cores of a botnet rented at significant dicount … or even wait for proper 0day to get even order ot two higher computation power on shorter time scales.

    There is reason why you always want your crypto secirity with significant overkill factor.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s