3

IOTA uses Winternitz one time signature scheme (W-OTS). Page no 45

W-OTS uses one-way function f and cryptographic hash function g.

W-OTS selects parameter w > = 2, which is number of bits to be signed simultaneously.

Private key is selected randomly, whereas in IOTA private is computed using seed privatekey = hash (seed + index)

Public key is computed by applying f to each bit string in private key 2^w -1 times.

My questions are

What is one-way function f selected by IOTA?

What is the value of parameter w selected by IOTA?

Most of the post says that after one time signature almost 50% of the private key reveals. That i believe in case of Lamport signature scheme it stands true, but IOTA uses Winternitz signature scheme. Whereas this documentation says that after one time reuse the attacker needs to do around 27^{54} tries to brute force, 54 is nearly 65% of 81 characters address which means 35% of private key reveals after one signature?

  • 1
    w = 3 trits or ~4.75 bits. Note that IOTA signature scheme doesn't use the explicit checksum. – Come-from-Beyond Mar 15 '18 at 12:51
3

All hashes in the signing function use Kerl.

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 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 (=w) 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.

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 normalizedBundle() function for the exact normalization details.

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 the signature for this specific address in this specific transaction bundle.

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.

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 does not 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^27 / 2, 27^54 / 2, or 27^81 / 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!

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

  • IOTA uses kerl - 256 or kerl - 512 ? – Infinity Mar 17 '18 at 6:50
  • 2
    In addition to this great answer I recommend this video youtu.be/7lhS542wDL8 explaining the signature in depth. – ben75 Mar 17 '18 at 7:00
  • 1
    @infinity: Neither 256 nor 512. Kerl uses Keccak.Digest384. – BugFreeSoftware Mar 17 '18 at 19:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.