Insecure seed generation in the Nano Android wallet

On the 21th of June 2018, the release of the new wallet applications for Nano was announced on Reddit. Shortly after that, another announcement was made telling users of the Android app to transfer their funds to a wallet with a seed that was not generated by the app. I quickly looked up the source code and found that the app was using a random number generator that is not cryptographically secure. Let’s analyze how bad this really is. Spoiler: it’s bad.

Discussed on Reddit.

The code

Let’s look at the vulnerable piece of code first:

import java.util.Random;

public static String generateSeed() {
    int numchars = 64;
    Random random = new Random();
    StringBuilder sb = new StringBuilder();
    while (sb.length() < numchars) {
        sb.append(Integer.toHexString(random.nextInt()));
    }
    return sb.toString().substring(0, numchars).toUpperCase();
}

As you can see, it’s using java.util.Random to generate the seed. The algorithm that Random uses to generate random numbers is not cryptographically secure. It’s seeded with a 64-bit integer (usually the current time in milliseconds by default if no seed is specified) and given a number of outputs, the following outputs can be predicted without knowing the seed.

Ok, so this sounds bad, but is it actually exploitable in practise?

Difference in API levels

We first need to know what the implementation of java.util.Random looks like on Android. The API of Random is the same across all API levels, but the implementation differs. Not only the default seed is different, but the algorithm to generate random numbers is also different. We’re only going to look at how the default seed is calculated as the underlying algorithm doesn’t really impact our ability to exploit this vulnerability.

The oldest Android API level the app supports is 16, so we’ll start there.

Level 16 - 19

On API levels 16 - 19, the default seed of Random is calculated as follows (source):

public Random() {
    // Note: Using identityHashCode() to be hermetic wrt subclasses.
    setSeed(System.currentTimeMillis() + System.identityHashCode(this));
}

Older versions of Android use a common implementation of Random where the RNG is seeded with the sum of the current time in milliseconds and the hashCode of the Random object.

Time is obviously a bad source for secure randomness. If we wanted to iterate over all timestamps of a particular day, we’d only have 86400000 of them to go through (as that’s the amount of milliseconds a day has).

The default hashCode implementation can differ across JVM implementations, but it usually returns the memory address of the object. This is also the case on Android. That makes it a little harder to guess, but it’s a 32-bit number and therefore also trivially brute-forceable.

Let’s say we wanted to brute-force all seeds that could have been generated during the beta period. The timespan of the beta period from the initial announcement up until the announcement of the vulnerability is about 4 months (10510000000 milliseconds). We need to account for the addition of the 32-bit number, so we’ll subtract 2³¹ from the timestamp we start with and add 2³¹ to the last timestamp. This gives us a total key space of only 14804967296 (less than 2³⁴)!

Level 20 - 23

On API levels 20 - 23, the default seed of Random is calculated as follows (source):

private static volatile long seedBase = 0;

public Random() {
    // Note: Don't use identityHashCode(this) since that causes the monitor to
    // get inflated when we synchronize.
    setSeed(System.nanoTime() + seedBase);
    ++seedBase;
}

This implementation uses the sum of System.nanoTime and an offset to seed the RNG.

Note that nanoTime does not represent the current time. The starting point is unspecified. On Linux, this represents the elapsed time since startup in nanoseconds, excluding the amount of time spent sleeping (CLOCK_MONOTONIC). This is also the case on Android. I’d say this number is a bit harder to guess, but it’s definitely a lot less than 64 bits of entropy.

Integer ‘seedBase’ is incremented to make sure every instance of Random produces a different output. That’s its only purpose, it doesn’t make things any more secure.

To be clear, even if nanoTime wasn’t predictable in any way, a key space of 64 bits is still way too small for comfort. There’s a reason why we only use key sizes of at least 128 bits.

Level 24 - 27

On API levels 24 - 27, the default seed of Random is calculated as follows (source):

public Random() {
    this(seedUniquifier() ^ System.nanoTime());
}

private static long seedUniquifier() {
    // L'Ecuyer, "Tables of Linear Congruential Generators of
    // Different Sizes and Good Lattice Structure", 1999
    for (;;) {
        long current = seedUniquifier.get();
        long next = current * 181783497276652981L;
        if (seedUniquifier.compareAndSet(current, next))
            return next;
    }
}

private static final AtomicLong seedUniquifier
    = new AtomicLong(8682522807148012L);

This looks a bit more complicated, but the principle is basically the same as the previous implementation we looked at. It also uses nanoTime to seed the RNG but it has a different mechanism to make sure all instances of Random produce different output.

Proof of concept attack

To test if my analysis is correct, I decided to write a POC program that generates all seeds that could have been generated during the entire beta period of the app on Android devices with API level 19 or lower.

Here are the steps the program goes through:

1. Generate the list of seeds, starting with the time of the beta announcement minus 2³¹ and ending with the time of the vulnerability announcement plus 2³¹.
2. Derive Ed25519 keypairs from the generated seeds. This involves doing some BLAKE2b hashing to derive a private key from the seed and an index number.
3. Iterate over all public keys of the keypairs and check if any of them exist in the frontier list.
4. If there’s a match, we know we have found the seed for that particular public key.

There are definitely more intelligent ways to do this attack. This is just a proof of concept. For example, a way to improve the attack could be to reduce the space of the 32-bit number we need to explore by taking memory alignment into account.

Results

After letting the program run for a couple of days, I found a total of 84 existing addresses that I was able to generate a seed for. The addresses held a grand total of around 663 NANO. To be absolutely clear, I’m not going to steal any funds. I deleted the seeds right after the brute-force completed.

This is not a lot of money, but it’s not insignificant either. Keep in mind that we only looked at a very small portion of affected users: the ones running Android KitKat or older. According to Google’s statistics, this amounts to 14.6% of their userbase. We did not look at more recent Android versions, which amount to 84.7%. Surely, we would have found a lot more seeds with existing addresses if we did do that. As far as I can tell that would require quite a bit more computing power though.

Warning users

Eventhough the Nano team repeatedly reached out through their social media channels (Reddit, Twitter, Discord, Telegram and even Blockfolio) telling users to change their seeds, the accounts I found still held a bunch of NANO. Of course not every holder of NANO is active on social media or follows cryptocurrency news, so I wanted to try a different way to warn users before publishing this post.

My first idea was to send transactions to all vulnerable addresses I found and use steganography to encode a message into the balance. While this is a cute way to send messages over the block lattice, it’s very unlikely users will notice this. A friend came up with a much better idea: send small amounts of NANO from 3 vanity addresses that spell out a message:

xrb_1changec1b68rgyrhpbngthck1p3yekcu868chcxnm6zsm6u87u4bx1iw7wj
xrb_1seedmpo9e63piyyo77db44i6hthedmou9chthe3qudswow75q8f7rzfhhrg
xrb_1asap5ufpqzobb1rkdnjx3eieantny16b1dpequy3csrcrsixexa4517xh7y

I sent 0.000001 NANO from each of the above addresses to the vulnerable addresses I found that had a balance of 0.001 or more. Unfortunately the transactions didn’t always arrive in the correct order. Due to the way a block lattice works, wallets have no way of knowing the order in which transactions occurred if the transactions did not originate from a single account, so the order ends up being arbitrary.

But sure enough, one of the accounts responded by moving their funds elsewhere:

Luckily, this happened to be the account that held the largest amount of NANO. This resulted in a big reduction of the amount of NANO these addresses were holding. The total is now around 131 NANO at the time of writing.

Update 2018-07-02: After publishing this post another account appears to have transferred its funds elsewhere: xrb_16dpz3fj8o3i8tizmyx9ataxmcus53bb3tgfy5eu6f86d4ozc5i8tuww7sdn. According to the transaction history, this account has received funds from the address the funds were just sent to before, so we can be reasonably sure that they were not stolen. This brings the total down to about 34 NANO.

Update 2018-07-06: It looks like someone has reproduced the attack and stole the remaining funds. Luckily the majority of the funds on the vulnerable addresses I found were moved elsewhere as a result of my post, but he still got away with 34 NANO. This is the address of the thief: xrb_3tsjtouqoae78e6pba1e1s1amod66fxsswrq4dzkg3ohh1fqgfrykr75xw6w.

Conclusion

This is one of the worst mistakes one can make when using cryptography. Unsurprisingly, this turns out to be very easy to exploit and it’s only a matter of time before someone else exploits this vulnerability and starts stealing the remaining funds. I was going to publish the POC code but decided not to because I’m afraid I’ll receive the blame eventhough the attack I demonstrated is trivial. To be honest, I was very surprised to see that no funds had been stolen yet.

Before publishing this post, I gave the Nano team a chance to read it and to provide feedback. I also kept them up to date on what I was doing and what the results of the proof of concept attack were.

It’s important to note that this vulnerability was patched almost immediately after it was found. Seeds generated with the new version of the app are generated using a CSPRNG and are therefore secure. I spoke with the Nano team and was told that the vast majority of their users are now on version 1.0.2 or newer of the app which means they were forced to migrate to a new seed. However, users who exported their seed and uninstalled the app are still at risk.

So please, if you used the Nano Android wallet, move your funds to an address derived from a different seed if you haven’t done so already.