Topic: schnorr signature weakness, why did they do it this way? (Read 502 times)

The schnorr patent (not copyright) had expired by the time Bitcoin was created.  But there were no mature or standardized industrial grade implementations of a schnorr ECC signature until a couple years later (I believe the ed25519 work was the first and it was published in late 2011).

 To whom it might concern
I found out an interesting fact about why schnorr was not used from the beginning in Bitcoin in here ( min 55/56 I think)
https://youtu.be/0Q5IimX-AAc
In short, they had to wait 20 years for a copy right issue

I have to admit that I hate stats since small language differences can make large changes in the defined problem!

I was talking about the probability that the M out of N signatures r all not malicious/compromised and that it's not exactly the original ratio X/N
i.e., if u r using M=3 signatures out of N=5 with X=2 could be compromised (1-X/N =3/5)
Prob(all M correct)= 3*2*1/(5*4*3)=6/60=0.1=10%
If only one is compromised X=1
Prob(all correct)=4*3*2/60=40%
.
As for the collisions ( prob ≥0.5 that all hash trials r different), the denominator here is like the Birthday days population don't change, each time the result population is still 2¹⁶⁰, N in our terminology,

What u did is saying if the inequality hold for those terms, then it still holds for their logs ..

N(N-1)(N-2)...(N-X+1)/(N^X)≥1/2
2N(N-1)(N-2)...(N-X+1)≥ N^X

implies it holds for the logs too

log(N-1)+..+log(N-X+1)+1≥
(X-1)logN

After some math& abbreviation it will lead to
X~ O(square root of N) for the inequality to hold (the probability to be ≥1/2)
In our case N=2¹⁶⁰, so X=2⁸⁰

It should be fine...
as long as the algorithms hold.
But consider that a megabyte was thought to be all a person would ever
need: https://www.wired.com/1997/01/did-gates-really-say-640k-is-enough-for-anyone/
Perhaps there will be dramatic computing or algorithm performance increases over time.
Individuals have more than one address so that also changes the requirements.

If quantum computing (or just computing) became powerful enough, then bitcoin could counteract this
new space perhaps by increasing key lengths. A few bytes goes a very long way.

It's hard to say what the future holds though. There may be algorithms that were considered impossible, that become possible.
The proof for Fermat's last theorem comes to mind. The FLT current proof relies on properties of elliptic curves, which are also related
to encryption algos. There are all sorts of mathematical problems, such as the millenium problems, Goldbach's or Beal's conjectures,
that remain unproven yet could impact these encryption through new number theories.
One hopes that with any of these changes that bitcoin could transition at an appropriate
rate to better algos or key/address spaces.

Elliptic curves are pretty neat.


(Below is on birthday paradox, not the main topic..)


Except your space is much larger than 365, since it is 2^160.
So,
Probability(all different; eg. no collision) = 1 * [(2^160-1)/(2^160)] * [(3^160-1)/(3^160)] ... * [(2^160-X)/(2^160)]

If you want to calculate this, you are going to struggle with even most modern software.
You can calculate the probability by converting to exponents.

exp(y) = 1+y for very small y

(2^160-1)/(2^160) = 1-1/2^160 = exp(-1/2^160)

For X tries of addresses, the probability is

P(all different) = exp(-sum(i)/2^160)

where sum(i) is the sum of numbers from 1 to X: sum(i) = 1+2+3+...X.

If you want a 50% chance, then

P(a.d.) = .5 = exp(-sum(i)/2^160) --->  log(0.5) = -0.3 = -sum(i)/2^160
sum(i) = 0.3 * 2^160

sum(i) has a closed form solution, sum(i) = X(X+1)/2

So, X(X+1)/2 = 0.3 *2^160
X(X+1) = 0.6 *2^160
X^2 + X = 0.6 * 2^160

Because the number is so large, we can drop out the single powered term, X, and solve:

X^2 ~= 0.6 *2^160
X ~= 0.77*2^(160/2) ~= 2^80 ~=10^24

So, if birthday paradox applies, you'd still have to search a space that is quite large (10^24) for a
50% chance to collide with one address -- but requires that there are X = 10^24 addresses worth finding, which isn't true.

Birthday paradox requires that the number of searches is also the number of interesting birthdays/addresses, which isn't true
in a collision search, where the searches can easily outnumber the interesting birthdays/addresses.

----

There are several things that change this from a birthday problem:
1) keys/addresses will not overlap between individuals, as one can assume that individuals want
to keep their addresses unique from others
[so that 364/365*363/365...(365-X)/365 doesn't apply, raising the difficulty]
2) the reward for any given collision is not equal
3) not all individuals with addresses are searching the entire space
4) Birthday paradox doesn't change the probability of finding the key to a single specific address

Using either point one, three or four above reduces the chances of a collision, i.e. the X^2+X term goes to a simple X.
That's because you are searching for a simple match of one address per go, reducing your search space by that amount per search.

Probability(no collision) = 1 * [(2^160-1)/(2^160-0)] * [(2^160-1)/(2^160-1)] ... * [(2^160-1)/(2^160-X)]
which is probability(no collision) = 1 * [(2^160-1)/(2^160)]^X due to the insignificant effect of the -X term on 2^160.

P = 0.5 = exp(-X/2^160)
-log(0.5) = -X / 2^160
X = log(2) * 2^160

Thus, fancy mathematics shows that to obtain a 50% collision with a single address, you have to search just under half of the space. A bit of a weird result, but does not use birthday paradox.

To change the functions to include that you might have N number of addresses that are not empty worth searching, so the needed searches is smaller (by the factor of interesting addresses):
Probability(no collision) = 1 * [(2^160-N_interesting)/(2^160)]^X
X = log(2) * 2^160 / N_interesting

I think I got that correct... but there are obviously a lot of pitfalls in stats.

For those that disagree with me, wikipedia agrees with you: https://en.wikipedia.org/wiki/Birthday_problem

You can raise the probability of collisions with using a priori knowledge (public states, pollard's kangaroo, poor randomisation, poor k),
but that's no longer birthday paradox.

People are already doing that right now.


Pollard'a Kangaroo reduces the complexity by a factor of 2^30 or so.

Well for one thing sha256 is not completely random. It's not a random oracle so no one really knows whether it is surjective or not. I'd probably agree with you that if you do enough inputs to it, you can get almost any hash not just once but a gazillion times maybe. But "we just don't know". Unless you've tried all possible inputs then you don't know what the set of outputs really is unless you get lucky and finish early. 

---

If bitcoin ever became worth alot of money say where you could buy an entire country of people a pizza for every one of them, I bet people would be working on brute forcing all the bitcoin private keys. That is one way to get ahold of it without "computing" it. Luckily though bitcoin p2pkh addresses are secure. So that can never happen. I mean you would have to start at 0x0000...000 and work your way up to 2^256? Who needs more security than that?

[moderator's note: consecutive posts merged]

My reply meant however the aggregated key is calculated, u have to calculate the probability of its input including a compromised key as described ( a way little Similar to calculating the probability of Birthday Paradox)
=[(N-X)(N-X-1)...(N-X-M+1)]
/[N(N-1)...(N-M+1)]

not just assume it would be (1-p) to the power M, for p=X/N the probability/ratio of compromised keys

And if you ever could compute it, then you have the contributing keys and could just spend the coin.

The aggregated private key is never computed by the signing algorithm of Schnorr multisignatures, because it's not necessary. Only the aggregated public key and the aggregated r,s pair. Specifically:


The process of plugging random private keys to aggregate them into a multisignature is not similar to the birthday problem at all though, but your assumption does hold for calculating the probability of "rogue" keys in theory.

I'm just replying about whether it's similar or not to the Birthday Paradox

In general, no matter what the scheme u r using afterwards, if u have N keys/signatures, X of which r compromised (malicious/hacked/...), Then when choosing M out of N:
Prob(all M is correct)=
[(N-X)/N]*[(N-X-1)/(N-1)]*...*[(N-X-M+1)/(N-M+1)]
=[(N-X)(N-X-1)...(N-X-M+1)]
/[N(N-1)...(N-M+1)]


That's little similar how the Birthday Paradox is calculated, the prob of no collision is:
For no 2 people in a group of size "M" have same Birthday (N
Prob(all different)= 1* 364/365*363/365*...*(365-X+1)/365]
(The 1st person can have any birthday, the 2nd only 364 for this to be wrong, the 3rd only 363,..)
Then it was found out that X as small as 25 can make this probability < 0.5

Only difference here is the number of total possible days (the population we withdraw from) don't change it is always 365, but in signatures the population is like balls decreases by 1 with each withdraw

Because the hashes are much shorter than the input data there an infinite number of second preimages for almost any hash. If that weren't true it would result in statistical discrepancies in the hash function that would distinguish it from random.

Not that small as you may think. Many formats have some dummy fields like comments, Script has OP_RETURN and then you can put any 80 bytes after that, there are ways to construct your transaction in a way where you will have a lot of space for putting any bytes you want. Take http://shattered.io/ for example, they created two PDF's that are different, valid files in this format, and both have the same hash for SHA-1. If you reduce SHA-256 to the first 16 rounds, you can clearly see, how theoretically that attack could be mounted. Of course in case of SHA-1 it was just a collision, not a second preimage, but still, in most formats you can mount that attack by putting random (but correct from consensus point) data in the right place and attack it in this way.

In such system you would have to replace hash-based mining with something else, for example ECDSA-public-key-based mining. So, mining could be replaced (if you reject G/2 from valid points, start from some other point or change it to find leading ones instead of leading zeroes, etc.), but what about merkle tree construction? With no hashes, you will have just point addition or point multiplication, how do you want to construct that tree in a secure way and make it impossible to replace transactions? Even things like Pedersen Commitments use hashing. More than that: even signatures use hashing! So, if you have just ECDSA and you want to make a signature, how do you want to do that without hashing?

I think the chances of that would unimaginably small.  Just because someone finds a second preimage doesn't mean it would be in the format of a valid transaction or any meaningful format at all. How many matches would you have to find before one of them did the thing you needed? And the other thing is, there's no guarantee that a 2nd preimage of some hash even exists. I'm pretty sure about that but I could be wrong but I dont think so...

---

But it would be fun, no? Not having to rely on hashes for sending and receiving money. Seem like a pipe dream in crypto. Hashes are like entropy destroyers. they make you lose information and you can never get it back.

[moderator's note: consecutive posts merged]

If you can compute a second preimage of a arbitrary hash you can already steal any coin, e.g. by replacing the transaction someone signed by another transaction, or even by replacing transactions in the ledger. Bitcoin has an absolute and total dependency of the second preimage security of SHA256.  Nor would it be particularly feasible to construct an alternative system which didn't have similar security requirements.

Fortunately the security history of well studied hash functions against second preimage attacks is extremely good.  Even old and busted hash functions like MD5 and SHA1 still stand up pretty well to second preimage attacks.

Well yeah, I mean, what you said is true. But the real security increase is supposed to come from there being no other way to spend the money unless M of N private keys sign. There can't be any shortcuts or hacks.

As long as hashes are going to be used to represent spending conditions, well, I couldn't consider that to be real multisignature. Real multisignature would be getting rid of P2SH and using the actual redeem script as the payment address. yes it might be big but then I don't think there would be any other way to spend the money unless M of the N private keys belonging to the public keys were used to sign. Not even a theoretical way to get around that. That's real multisig.

I guess there's a difference between "practical/real world" security which deals with things like how people store their private keys and such vs the mathematical underpinnings of how the setup works on the blockchain and what risks there are with that. I'm talking about the latter. Don't care about the former.

Attacks against ECDLP allows you to solve multiple ECDLPs for only very slightly more work.

The security increase from bitcoin multisig comes because some of the participants may be untrustworthy or because they're unable to keep control of their private keys (hacks, etc.).  This same benefit is also provided by true multisignatures.

Multisig is an pre-existing term in cryptography that predates bitcoin, E.g.:

Some people? You mean ... all people, right?  There isn't a way to shortcut it: You can't sign without getting access to the requisite private keys. (assuming the hardness of the hash functions and discrete log problem, of course).

No. It is not a security issue. You'll probably have to see the post referenced below to understand what I'm talking about in relation to the Multisig and normal P2SH.

Collision attack is very different from pre-image attack. In trying to find a collision, we would be finding two of the same hashes when we're searching for the keys. The hash that will be found is completely arbitrary, and the theoretical attack scenario is better described here: https://bitcointalksearch.org/topic/m.57410551.

If you are looking for any specific addresses, you will need to do a second pre-image attack (2^160), so we're finding the inputs that would result in a specific set of addresses. Birthday probability doesn't apply here because we're not looking for random collisions, but inputs that would result in specific addresses.

Wouldn't birthday paradox only apply if all people involved are searching, and the rewards of the finds are equal?
But, as you say, the search space is smaller than the key space (2^80?). The public address space is smaller than the key space (2^160?), so you don't really need to search through the entire private key space for collisions. Maybe this is why the key space was made to be so large.

Maybe public addresses should be longer if the birthday paradox applies? But as you've said, there is SHA256 and P2WSH.


There have been flaws with parts of bitcoin's software, such as poor random generation in early versions. But no, I don't think there is a backdoor in the main methods (for addresses that have never sent a transaction, were generated purely randomly, etc; I don't know enough about multisig), otherwise I can think of a number of public addresses that would have been drained by now.

I agree it does sound very unlikely to do, no one would probably waste resources trying to do that but is there anyway that security issue could be fixed? I seem to have an issue with bitcoin using such short addresses where collissions can be an issue but no matter what the size of the address space, those could always happen. Seems something more fundamental would have to be done to fix that.

---

I was looking at this cowboy's video and he had some nice slides showing schnorr multisignature and from looking over that, it seemed like the aggregated public key had a corresponding aggregated private key although in the algorithm it is never computed since no one is supposed to know all the individual private keys. But if you have all N private keys then you can compute the "master private key" which it seemed like you could use to do transactions and bypass the need for multisig all together. Again, that's just what it looked like. But someone confirmed that is true in the other thread. But they said it's of no consequence since it would be infeasible to find it.

The thing is though, if that's the way it is then an attacker benefits anyway since they are looking for something they know exists.

Maybe the NSA is going to use that master private key as a backdoor? what do you guys think?

[moderator's note: consecutive posts merged]