9

Assumptions

You reveal exactly 50% of your private key with the signature of a transaction. What part you reveal is random. (What information is leaked if I reuse an address?) Is this correct?

The signature of a transaction changes when the content changes. The part of the private key I reveal changes when the content changes. Is this correct?

When you sign your transaction twice you can check how much overlapping there is. Is this correct?


Scenario

If Alice wants to send 5 IOTA to Bob from an address she already spent from once (= 50% of SK is revealed) , why can't she just:

  1. build the transaction
  2. sign the transaction
  3. check which part of her private key she would reveal
  4. if the part she would reveal doesn't match the part she revealed already:
  5. if the part she would reveal matches (maybe not 100% but to some extent) the the part she revealed already
    • publish the transaction

If that were possible, you could reuse the same address again and again while only revealing 50% (or just a little bit more) of your private key. Is it possible?


Are my assumptions correct? Which ones are incorrect?

Does the senario work? Which step(s) is/are not possible?

1 Answer 1

13

Sample how one-time signature works

Perhaps it helps with a short sample. Assume we are in a world where you do not need 384-bit security, but only 8-bit security (to make the example shorter). And I'll use a binary, not a ternary example.

Your private key consists of 16 parts, 8 for each bit of security (so you have 8 parts to reveal for a bit that is 1, and 8 parts to reveal for a bit that is 0).

You first create the bundle hash of the bundle (assume we get 11000001). Then to prove that you are the owner of the key, you reveal the first second and last part of the one bits, and the third to 7th part of the zero bits.

As a consequence, 8 bits of your 16 parts are now revealed, and everybody (you as well as everyone else) can use them to sign a message with bundle hash 11000001 from your address.

It is also worth noting that for one-time signatures, the only way to prove that you have a part of the key is to reveal it. Unlike normal public-key crypto (which can be broken by quantum computers), where you can prove that you have a key without revealing any part of it.

now about your assumptions

First one is correct. You will reveal exactly half of the parts, since every bit of the bundle hash is either 1 or 0 (it cannot be both and it cannot be neither). The parts you reveal follow directly from the bundle hash (so if you have two bundle hashes that both have the same bit at the same position, you will reveal the same part of your key). You reveal less "new" information if many bts are the same, and completely other information if all bits are different. As you cannot control the hash (except bruteforcing until you get a hash you like), the part you reveal can be treated random.

Your second assumption is also correct. When you change your transaction (bundle), the hash changes, and therefore the parts you reveal change (for every bit that changes in the hash)

Your third assumption is also correct. Count the bits that are different in the hashes. If your new hash is 11000011 and your old hash wa 11000001, you will reveal one more piece of information (since one bit is different) and have afterwards revealed 9/16.

where is the fallacy in your scenario?

All the steps in your scenario can be performed in theory. The problem is that there are 384 bits, so you will have to try a lot of times (2^384 times to be exact) until you find a bundle that has the same hash (all bits the same, and therefore you can sign it without revealing more information). So while it is possible in theory (just like it is possible in theory to guess seeds until you find one that has 1Giota on it), the time is longer than the universe will exist (even if every atom in the universe was a computer that worked on your problem).

why is it good that your scenario does not work?

Assume that your scenario would work, and you could sign a second transaction without revealing anything (in other words, sign a second transaction using only the information that is already public). Then not only you could sign that transaction, but anybody else, too.

As it is now, you are in danger as soon as you reuse an address. But if anybody could find a message he could sign without revealing more data, you would already be in danger as soon as you use an address the first time, making the signature essentially useless.

5
  • I read your answer some times and it's too cryptographically intense for me. I still don't know if it's not possible or at least possible to some extent. I restructured the question and tried to make it easier to answer to by delimiting the individual questions. Is it even possible to give delimited answers or are all subjects somehow interwoven? Thank you very much for your effort.
    – Zauz
    Commented Dec 3, 2017 at 23:02
  • Your approach is possible, but it is cryptographically harder than breaking the Kerl hash, so if you could do that, you could probably use the same cpu cycles as well for breaking the Kerl hash and steal the funds. (There are 2^384 different ways of what parts are revealed, and trying to reveal the same parts is trying to break the hash function). I will try to update my answer and make it clearer.
    – mihi
    Commented Dec 3, 2017 at 23:04
  • So assumption 3 while true it is insanely CPU intensive?
    – Zauz
    Commented Dec 3, 2017 at 23:20
  • Exactly. Every "other" way of breaking IOTA (which is believed to be too cpu intensive to be possible) will need less CPU than your double-spending "trick"
    – mihi
    Commented Dec 3, 2017 at 23:27
  • @mihi that's great
    – Helmar
    Commented Dec 18, 2017 at 15:24

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