There was an interesting post on Reddit about IOTA, a cryptocurrency, a while ago. Someone’s funds were stolen. The community blamed address reuse as the underlying cause that the attacker exploited. This blog post reports my thought process about the theft, details a (mitigated) vulnerability that could have been used, explores if address reuse was a root cause, and whether address reuse was even necessary for the vulnerability to be exploited.

IOTA and the traditional cryptography community differ in terminology used, as well as what requirements they place on their cryptography. This post tries to describe everything in terms that are accessible to readers with a minimal cryptography background.

Some background: IOTA is a crypto currency that takes a very different path from previous currencies, including creating their own cryptographic primitives, using ternary instead of binary for some operations, storing transactions in a directed acyclic graph instead of a chain and using a central authority, the coordinator. IOTA uses Winternitz one-time signatures (WOTS), which comes with weaknesses and challenges that more common signature schemes do not have. Similar to other crypto currencies, IOTA addresses contain the hash of the corresponding public key. Like other currencies, transactions have to be confirmed. When a transaction is published they are in the pending state. A transaction may take a while to be confirmed.

Winternitz One Time Signatures (WOTS) are described in a paper by Ralph Merkle. An important property of WOTS is that they are secure when only a single signature is published for a private/public key pair. Because each WOTS publishes some part of the private key, they rapidly become less secure as more signatures created by the same public/private key are published. IOTA transactions are sent to many people and can take a while to be confirmed. A weakness that allowed an attacker to quickly forge a valid signature after seeing only one signature would likely be disastrous. The attacker would be able to perform the following attack:

Monitor to the network for pending transactions.
Using the hypothetical(?) weakness quickly forge a valid signature for a different transaction, sending funds to an attacker address.
The IOTA network/central coordinator would accept only one of these two valid transfers. Without knowing the details of the coordinator, this likely gives the attacker a 50% change of stealing funds. It is likely that if the attacker provided extra resources to get the forged transaction confirmed that the attacker would have an even greater chance of success.
IOTA transactions can get stuck and then they need extra actions like reattaching to get confirmed, this gives the attacker a better chance to get the forged transfer confirmed. (There is a small Proof of Work required, this is highly parallelizable, and unlikely to be a barrier for an attacker going after $30,000.)

Back to the reddit thread. The funds were stolen from XTUYYPRVJIMEM9ERPF9CINWXWCOLKEQ9HKCXCYIBECXEMDEZIGVBXRRISKGBGITBQLPWTOJENAUQZKMJW. Using thetangle.org we can see which transactions involved this address:

August 13, 2017 11:44:04 - 6 months and 3 weeks ago 39.61 Gi
OFTXWTSPMUQTHYTHOME9BPRZHXHLUPHHOQ9YLMAXGUKM9GDLHMLGCHAWARCSQ9VJVBPCVRNST99N99999
September 6, 2017 06:52:57 - 5 months and 3 weeks ago -39.61 Gi
JMUWPQDVXKXDVCLNFCKGJXLYJRLZ9ONSAEVTRKEVDSHJHTQBNDCCOAJXLSEXOQ9GHXSABS9DOXQB99999 Confirmed
September 6, 2017 06:52:57 - 5 months and 3 weeks ago 0 i
CLBIVHPIQNDDOEZTNOL9BZLNXADZWRMAEDPJOGFN9SESXBPKPQMKNQGTPCNAXQEGYBQZDUGGTOMN99999 Confirmed
November 28, 2017 10:41:08 - 3 months and 5 days ago 23.46 Gi
VZAVHNYCFQCKVWQOYBAJHUMADALHPMPLOHLIGVGQHVALBWLCGYRBRYQLDJPBOOAJZLEDGCXLDQLOA9999 Confirmed
November 28, 2017 15:21:20 - 3 months and 4 days ago 0 i
XSQLYK9TEBOGLDWUCLRFNEVKETQUHWBTFQQDFYJKRVHN9TAAHGEPSNVWWSNBWPCDIHSSFZZJHBMMZ9999 Confirmed
November 28, 2017 15:21:20 - 3 months and 4 days ago -23.46 Gi
LLKGCXRMOQJGLXRSSSYEDUYPIQQEZHOBCUMAXBJKZADOQTGCTVXMETQ9SDRZKOQJVBWTRNHHBQDN99999 Confirmed

We can see the funds going in on August 13th.
A valid signature is used on Sept 6th to transfer the funds.
On November 28, 10:41:08 funds are again deposited into this address. The community pointed to this as the address reuse that allowed the theft to occur.
On November 28, 15:21:20 the funds are stolen (unauthorized transfer).

This makes for an intriguing puzzle. It seems that the funds were stolen after only one WOTS was published, which should not be possible when the signature scheme is properly implemented. The second interesting thing is that the funds were not stolen when the signature was published, but four hours after funds were deposited into the same address again. Note that sending funds to the same address does not supply an attacker with any information they did not already had. This suggests that the vulnerability requires significant attacker time to exploit. (In theory there could be a second signature, but the author of the reddit post should have mentioned that he tried to transfer the funds then, so that is unlikely).

It looks like a vulnerability was used for the unauthorized transfer because a signature was forged after only one WOTS was published. There are two primary places where this vulnerability can be. One is in the code that implements the WOTS. The second one is in the code that generates the private key. With every WOTS a some part of the private key is published. If the private key was generated in such a way that an attacker could recover the whole private key after seeing only a little bit, she would be able to recover the complete private key and create her forged signatures. IOTA generates all their keys from one starting seed. A standard way to generate multiple keys starting from one secure key is using a KDF, for instance HKDF.

WOTS in IOTA

Winternitz One Time Signatures (WOTS) are used to sign small values. In IOTA each WOTS signs a value from -13 to 13 (0 to 26). In IOTA, transactions are combined into bundles and the bundle hash is signed. To sign the whole bundle hash, many WOTS are required. This is why the IOTA signatures are very large. Each WOTS signs three trits of the bundle hash. This correspond to one character in the bundle hash. The section below describes how IOTA implements WOTS, which is not necessarily a recommended or standard implementation.

Each WOTS requires a private key, which should be a cryptographically secure random number that an attacker cannot guess. To create the public key, this private key is hashed a certain number of times. In IOTA the private key is hashed 26 times. Each WOTS can sign a value from 0 to 26 (inclusive). This is done by hashing the private key as many times as the value indicates. To verify the signature it is hashed another 26 - value times, the result of which should match the public key.

An example using a WOTS that can sign a value 0 to 3 (inclusive):

Creating a public key from a private key, used to sign a value from 0 to 3:
    Private key -> HASH -> HASH -> HASH -> public key
To sign the value 1:
    Private key -> HASH -> publish as signature
To verify the signature, hash the signature another (3 - value) times:
    Signature           -> HASH -> HASH -> Check if this indeed the public key.

This shows a weakness in WOTS. When an attacker sees the signature for any value, they can also calculate the signature for any higher values. To make a full signature for the bundle hash, in IOTA 27 WOTS signatures are created, more if the address uses a higher security level. As described above, IOTA hashes the private key 26 times. This allows each WOTS to sign a value from 0 to 26, 27 different values, the range of one tryte. IOTA signs each tryte by converting them into the range -13 to 13, we will call this signed. The value IOTA signs in their WOTS is 13 - signed. E.g. when signed == 13 IOTA hashes the private key zero times. When signed == -13 IOTA hashes the private key 26 times. Just the public key of a WOTS would give you the hash for signed == -13. In IOTA this is prevented because IOTA doesn’t publish the public key of each individual WOTS directly. Instead the public key is the hash of all the WOTS public keys. Verification then works by hashing each signature enough extra times to get to 26. If the signature is valid this should result in the public key. IOTA hashes all the calculated public keys together and verifies that their combined hash matches the public key.

If used exactly as described above, an attacker could forge a signature by repeatedly generating bundle hashes until she generates one where all the values are equal to or lower than the published IOTA signature. To sign a value one lower, the attacker can just hash the WOTS one more time. IOTA ‘normalizes’ the bundle hash before signing, this prevents the sketched attack. Normalization is done by repeatedly incrementing or decrementing the first values of the bundle hash, until the sum of all the values to sign is 0. As an example, for a very short signature they might end up with: [13, -7, -6]. Since the values always have to add up to 0, an attacker can’t just decrement one and hash the corresponding signature fragment one more time. The attacker would also have to increment one of the other values, and this requires the attacker to send an earlier hash. Calculating an earlier hash (a preimage attack) should be impossible in any cryptographic hash. Due to normalization an attacker can’t just look for a different bundle hash that only has lower values. Incrementing or decrementing the first parts makes the signature weaker, since multiple bundle hashes have the same signature. Specifically, in the example all bundle hashes from [-13, -7, -6] up to [13, -7, -6] have the same signature. So the normalization weakens the signature somewhat, but it does provide protection against an attacker trying many bundle hashes until she finds one with every value that is the same or lower. Even with the ‘normalization’ the 27**27 ~~ 128bit strength of the signature should not be weakened enough to allow an attacker to forge a signature.

If the WOTS looks strong enough, it is time to look at the other option, unsafe generation of the private key. We know that if the value to be signed is 13, no hashing is done to generate the signature. So when signing the value 13, a piece of the private key is directly exposed to an attacker. Let’s see what the normalized version of the bundle hash looks like for the reddit user’s theft of $30,000 worth of IOTA. The original transaction with the only published signature can be seen at thetangle.org. The bundle hash is: GEOKC9BRZRRPYNZRAXOZGIKVHIZTGHPFUJNJFYQPEKCIIHQIINCUOEMXQALSDFGGKCUQQHXKQS9LRYHCY

After normalization:

>>> from iota.types import TryteString
>>> from iota.crypto.signing import normalize
>>> print normalize(TryteString(b"GEOKC9BRZRRPYNZRAXOZGIKVHIZTGHPFUJNJFYQPEKCIIHQIINCUOEMXQALSDFGGKCUQQHXKQS9LRYHCY"))
[[13, 13, -1, 11, 3, 0, 2, -9, -1, -9, -9, -11, -2, -13, -1, -9, 1, -3, -12, -1, 7, 9, 11, -5, 8, 9, -1], [-13, -4, 8, -11, 6, -6, 10, -13, 10, 6, -2, -10, -11, 5, 11, 3, 9, 9, 8, -10, 9, 9, -13, 3, -6, -12, 5], [-12, -3, -10, 1, 12, -8, 4, 6, 7, 7, 11, 3, -6, -10, -10, 8, -3, 11, -10, -8, 0, 12, -9, -2, 8, 3, -2]]

They start with 13s, which means the signature directly exposes a part of the private key. Let’s look into how the private key is generated.

Private key generation

On a high level, private keys are generated based on a seed. This seed is used for all keys. The private key is generated based on a hash of the seed + key index. This hash is fed into IOTA’s Keccak based hash function, Kerl. Kerl is the replacement IOTA implemented after a team from the Digital Currency Initiative at the MIT Media Lab showed serious cryptographic flaws in IOTA’s previous home grown hash function Curl. IOTA uses an instance of the Kerl function, they call this instance the ‘sponge’. The sponge is fed the hash of the seed and key_index using the absorb function. In between, there are some transformations from binary to ternary, etc. that do not have much functional impact. Once the sponge has absorbed the secret key it is used to generate the private key by repeatedly ‘squeezing’ more secret data out. Here is the squeeze function from the IOTA reference implementation in Java. They are using the Keccak implementation from Bouncy Castle (a library that implements cryptographic functions).

@Override
public void squeeze(final int[] trits, int offset, int length) {

    if (length % 243 != 0) throw new RuntimeException("Illegal length: " + length);

    do {

        byte_state = this.keccak.digest();
        //convert to trits
        trit_state = tritsFromBigInt(bigIntFromBytes(byte_state,0,BYTE_HASH_LENGTH), HASH_LENGTH);

        //copy with offset
        trit_state[HASH_LENGTH - 1] = 0;
        System.arraycopy(trit_state, 0, trits, offset, HASH_LENGTH);

        //calculate hash again
        for (int i = byte_state.length; i-- > 0; ) {

            byte_state[i] = (byte) (byte_state[i] ^ 0xFF);
        }
        keccak.update(byte_state);
        offset += HASH_LENGTH;

    } while ((length -= HASH_LENGTH) > 0);
}

In case you are not familiar with what exactly keccak.digest() does with the internal state. Here is the Python implementation from iota.lib.py:

  def squeeze(self, trits, offset=0, length=None):
    ...
    while offset < length:
      unsigned_hash = self.k.digest()

      if PY2:
        unsigned_hash = map(ord, unsigned_hash) # type: ignore

      signed_hash = [conv.convert_sign(b) for b in unsigned_hash]

      trits_from_hash = conv.convertToTrits(signed_hash)
      trits_from_hash[TRIT_HASH_LENGTH - 1] = 0

      stop = min(TRIT_HASH_LENGTH, length-offset)
      trits[offset:offset+stop] = trits_from_hash[0:stop]

      flipped_bytes = bytearray(conv.convert_sign(~b) for b in unsigned_hash)

      # Reset internal state before feeding back in
      self.reset()
      self.k.update(flipped_bytes)

      offset += TRIT_HASH_LENGTH

  def reset(self):
    self.k = keccak_384()

The sponge contains secret data within the Keccak state, this.keccak in the Java version, self.k in the Python version. To generate the first piece of the private key, IOTA takes the digest from the secret internal state, does a reversible bit twiddle, converts it to ternary, sets the last trit to 0 and outputs that as the first private key. After that, they reset the internal state of Keccak. This is done implicitly in the digest call in the Java version, and explicitly using self.reset() in the Python version. After that Kerl does a different reversible bit twiddle on the digest and uses that to set the new internal state of the Keccak. So after generating one piece of the private key, the whole internal state of the sponge only contains information that is also in the first piece of the private key. A Key Derivation Function that behaves like this is critically broken.

Going back to the signatures, when signing the value 13, the output is a piece of the private key. Using this piece an attacker can recover the complete internal state of the Kerl sponge, and calculate the rest of the pieces of the private key. The attacker has to try three versions, because the last trit is overwritten. The python code included takes a bundle hash, an address and a signature and calculates the private keys within seconds. Example run using the data from the reddit post, created using the reddit_key_recover.py:

IOTA$ time python reddit_key_recover.py
Normalized bundle:  [[13, 13, -1, 11, 3, 0, 2, -9, -1, -9, -9, -11, -2, -13, -1, -9, 1, -3, -12, -1, 7, 9, 11, -5, 8, 9, -1], [-13, -4, 8, -11, 6, -6, 10, -13, 10, 6, -2, -10, -11, 5, 11, 3, 9, 9, 8, -10, 9, 9, -13, 3, -6, -12, 5], [-12, -3, -10, 1, 12, -8, 4, 6, 7, 7, 11, 3, -6, -10, -10, 8, -3, 11, -10, -8, 0, 12, -9, -2, 8, 3, -2]]
Finding private key for:
XTUYYPRVJIMEM9ERPF9CINWXWCOLKEQ9HKCXCYIBECXEMDEZIGVBXRRISKGBGITBQLPWTOJENAUQZKMJWUIR9RHQXC
Using first two signature pieces:
   NT9RTWEEFG9DHBIZMEYESHHHGV9LVLOBNICOLJUDVTUS9FCGRLFCTEGUYYJFCSYCVRPYWMAPM9UR9CRGB
   NPWWR9SXHLJUPCGNAYMPXLFLHXPZWQKP9JEGFVJMTVTQILVTOCHUUWWKEFWALYJAKVULETPAPGXLGFGUB
Last Tryte found
No match for security level 1
Private key found for security level 2
Address of recovered private key:
XTUYYPRVJIMEM9ERPF9CINWXWCOLKEQ9HKCXCYIBECXEMDEZIGVBXRRISKGBGITBQLPWTOJENAUQZKMJWUIR9RHQXC
Target address
XTUYYPRVJIMEM9ERPF9CINWXWCOLKEQ9HKCXCYIBECXEMDEZIGVBXRRISKGBGITBQLPWTOJENAUQZKMJWUIR9RHQXC

real    0m2.286s

Based on this, any time a transaction was made with a starting value of 13, an attacker could have forged her own signature and send out a competing transaction within seconds. The value 13 is much more likely to appear than the expected chance of 1 in 27 due to the normalization. In previous versions this used to put much more than ~3% of the transactions at risk. Note that recent versions of the IOTA Java and Python implementations specifically filter out any normalized bundle hash with contains a 13. Current transactions are safe from underlying Kerl vulnerability.

This vulnerability did not require key reuse or address reuse to be exploited. Why did the attackers wait?

If you are considering implementing your own crypto, please be well aware of the weaknesses and challenges of the choices you make. Many components are available in well analyzed and tested implementations. Accidents happen on the frontier, they should not happen on the well trodden paths. (TLDR: DO NOT ROLL YOUR OWN CRYPTO).

TLDR: Many WOTS are required to make one signature. When signing a value of 13 using the IOTA implementation the published signature is the privatekey for that WOTS. The private keys are generated using a broken KDF. The KDF allows complete internal state recovery from one private key. IOTA uses ‘normalization’ instead of checksums, this makes having the value 13 as the first value to sign much more likely. Address reuse was not required to exploit this. The current IOTA implementation doesn’t fix the KDF. Instead it does refuse to create any signatures that require the value of 13 to be signed, mitigating the vulnerability.

Have a crypto implementation or protocol you want me to look at? willem@lekkertech.net

Update: This was published March 12th. I started writing this post March 7th, that is why the date is incorrect at the top.
Update: Fixed links to code when accessing article directly. (Thanks A.)

Lekkertech

Research, Services & Tools

IOTA Signatures, Private Keys and Address Reuse?

WOTS in IOTA

Private key generation

Comments