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.

12 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.

  7. This is a problem AND well over 5 to 10 Lisk wallets have been emptied through a collision attack in 2020 alone. Well over 10,000 Lisk stolen. LiskHQs response could be summed up as “we warned you to initialize.” How about not releasing a wallet with a significant security flaw if the user does not initialize (make an outgoing transaction). Unacceptable, completely irresponsible and has costed many people hundreds and thousands of dollars due to LiskHQ releasing an outdated wallet from the days of Crypti. Why would they release such an insecure wallet? With the new GPU’S being released, I can only imagine how many more accounts will be wiped out until Lisk upgrades their wallet system, which will take a minimum of 3 more months. Lisk should accept responsibility of such horrible decision in releasing this wallet, and reimburse all accounts that can prove to be victims or a collision attack. Proving to be a victim of a collision attack is possible. Currently, there are dozens oF Lisk accounts that have not been initialized (including the wallet holding 1.6million LSK tokens) and some of these wallets were created as recent as August 2020. It is obvious that many users do not understand the need to initialize an account AND most would think their tokens would be more secure in the Lisk wallet than on an exchange, and unfortunately they are wrong if they dont initialize. I do not blame these account holders for not initializing, many people if not most in the crypto industry do not understand collision attacks nor what the point is to initialize/ how and why that makes their wallet more secure. LISKHQ has made an extremely costly mistake where all the burden is on the account holders who have and will lose thousands of dollars in LSK tokens. As technology has drastically improved regarding the power of hardware (new GPU’S with much more power) attempting collision attacks upon Lisk wallets will inevitably increase as will the number of victims, all of who were sold the false premise of having their LSK tokens more secure in the Lisk wallet rather than one of the many top volume exchanges. Manf individuals blame the victims for not understanding the crypto wallet system, however in order for crypto to become widely adopted, there must be an ease of transition; not requiring people investing in crypto to understand the complexity of crypto wallet security and technology. The burden of providing a secure wallet, that does not require the account owner to perform an outgoing transaction in order to not be the victim of a collision attack due to LiskHQ rushing out a wallet with such a large security flaw. Other individuals point out the fact of all crypto wallets require an outgoing transaction for optimal security; however they usually do not comment the fact of 99.9% of all other crypto wallets being extremely more secure than Lisk wallet, without performing an outgoing transaction due to more entropy and the project teams not rushing out an insecure wallet being prone to a collision attack which results in all funds being stolen. It is obvious that LiskHQ put significance in their personal growth and profit and not in the security of their community members causing tens of thousands of LSK tokens being stolen and more LSK tokens being stolen in the coming days, weeks and months with no sympathy for the victims as they did not perform an outgoing transaction, and instead thought all that was required was depositing their LSK tokens into the wallet, storing their passphrase in a smart place and assuming LiskHQ has provided an up to date wallet system which is not the easiest wallet to hack into resulting in their funds being stolen. Many, including I am hoping LiskHQ takes responsibility and reimburses proven victims some way some how.

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