Exploring the IOTA signing process
This article goes in-depth in the details of the IOTA signing process. Be prepared for some deep thinking because it is a complex process. I tried to simplify as much as possible, but I assume you have at least an idea of how the signing process works.
First, all hashing in the signing function uses the Kerl hash function at the moment. It’s a wrapper function that converts between trinary and binary representations and utilizes the well-known Keccak hash function.
Generating the private key
We start from an 81 tryte subseed that is generated by taking Kerl(seed + index). This will make the subseed sufficiently independent so that it is impossible to figure out the original seed that is used to generate the list of addresses.
The private key length depends on the security level S, which can be 1, 2, or 3.
The private key is generated by successively hashing the subseed again and again. It will be hashed 27 times per security level, which results in a key length of S * 27 * 81 trytes, which is 2187, 4374, or 6561 trytes, respectively. Each 81-tryte hash generated is a key fragment.
The private key is then used to generate the address by hashing each key fragment 26 times, and then hashing the results together into an 81 tryte address value. Note that the final address therefore depends on S, which means that the same subseed can generate 3 different addresses, one for each security level.
Signing a transaction
Now for the signing of a transaction you need to take the 81-tryte bundle hash of the transaction bundle containing the address to sign. Depending on S we will take the first 27, 54, or 81 trytes, respectively, of the bundle hash.
First this (partial) bundle hash will be normalized in such a way that the total sum of the trytes (when taking each tryte as a value from -13 to +13) equals zero. The implementation will increment or decrement successive trytes until the sum is zero in a deterministic way. I suggest examining the client library’s normalizedBundle() function for the exact normalization details.
Normalization essentially ‘locks’ the signature in two ways:
- It makes sure that in every case exactly 50% of the private key gets exposed. This is a good thing, because otherwise the randomness of the bundle hash could result in a worse >50% (or a better <50% of course) of the private key being exposed. Because brute forcing is exponentially related to the amount of exposure of the private key, guaranteeing the 50% is a good balance. Sure, it will expose a little more in some cases where <50% would be exposed otherwise, but that is more than offset by limiting the exposure of those cases where >50% would be exposed otherwise. It gets rid of the randomness in the exposure factor. 50% exposure is perfectly safe. Not risking for example 80% exposure is a Good Thing (tm).
- Making the normalized sum zero removes the need for a checksum hash. Essentially the checksum is an implicit zero. Note that this rule means that only the provided signature is valid w.r.t. the exposed parts. If you want to make a different signature using other exposed parts you will need to compensate those somewhere else in the signature with as of yet unexposed parts. Good luck finding those!
Next, each of the normalized bundle trytes will be taken as a number from 0–26, which determines how many times to hash the corresponding private key fragment. The resulting signature fragments are concatenated into the signature for this specific address in this specific transaction bundle. Depending on the security level of the address, the bundle will need 1, 2, or 3 transactions to store the entire signature.
Verifying the signature
To verify the signature all that is needed is for the verifier to ‘complete’ the hashing towards the address. Because he knows the bundle hash he can therefore calculate the normalized bundle hash, which gives him the number of hashes remaining to get to 26 hashes per private key fragment from the signature fragments. He now proceeds to hash each signature fragment the necessary amount to get to 26 hashes (which is 26 minus the normalized bundle tryte value from 0–26). The resulting key fragments are then hashed together and compared to the address. Only the owner of the private key to the address could have hashed it this specific amount of times and gotten a result that, when hashed further, ends up as a match to the address.
Resistance against attacks
Note that by normalizing the bundle trytes we make sure that on average there are 13 hashes necessary for each tryte to get to the correct address. This means that exactly 50% of the private key is exposed. Each signature fragment essentially exposes all the next signature fragment hashes for that tryte, because an attacker can simply calculate those from the signature fragment. But the first series of hashes that were used to get to the signature fragment remain unknown due to the one-wayness of hashing.
Also note that an attacker doesn’t need the original private key to forge a different signature for the same address. All he needs to do is to brute force a bundle hash that has the same starting trytes (depending on S). That’s why brute forcing such a bundle will still take on average 27²⁷/2, 27⁵⁴/2, or 27⁸¹/2 tries, respectively.
And here is the reason why it is important to never to reuse an address. Because if you spend a second time from the same address, you expose a different set of signature fragments, courtesy of the different bundle hash. Now instead of needing an exact match to the start of the bundle hash, an attacker will only need to generate a normalized bundle hash having tryte values >= the minimum of the same position tryte values of the exposed bundles. That’s why it becomes exponentially more feasible to attack an address once a second spend transaction hits the network. You better confirm that transaction as fast as possible!
(Fixed) bug alert!
One additional note: there used to be a bug in the signing code (fixed with October 2017 snapshot). Let’s see what happens if a normalized bundle tryte is zero. In that case we would do zero hashes of the original private key fragment, essentially exposing that private key fragment itself. Now if you remember how the private key is generated: each fragment in succession is hashed to create the next fragment. That means that an attacker could simply generate the rest of the private key fragments starting at the first normalized bundle tryte that was zero! In fact, there was a slightly better than 1 in 27 chance that your normalized bundle started with a zero value, which meant that an attacker could simply generate the entire private key!
Luckily this was realized quickly and a counter-measure was implemented in the signing code. Since it wasn’t an option to change the normalization code, because that would have meant another transition of all addresses in the Tangle, instead it was decided to scan the normalized bundle trytes for these zeroes (encoded as ‘M’ trytes, and therefore know as the M-bug). When it turns out there is a zero in there, the client code will increment the obsoleteTag field and calculate a new bundle hash. This in done in a loop until the normalized bundle hash does not contain any M trytes. It’s a stop-gap measure for sure, but once the Curl hash function is properly vetted and we switch back to Curl, we will need a transition anyway, and this stop-gap measure can be replaced with a better normalization function that does not return zero value trytes.