Alice designed an authentication system in which users gain access by presenting it a signature on a username, which Alice provided. One day, Alice discovered 256 of these signatures were leaked publicly, but the secret key wasn't. Phew. The next day, she found out someone accessed her system with a username she doesn't know! This shouldn't be possible due to existential unforgeability, as she never signed such a message. Can you find out how it happend and produce a signature on your username?
I'll refer to BLS signatures, Pedersen hashes and a little bit of linear algebra. For the sake of simplicity I asume that reader is already familiar with those concepts. If not, ZKHack provided resources are sufficicient to follow further text.
So, from the puzzle setup it's clear that we have to play with BLS signatures. Maybe first thing that comes to mind is to somehow forge private key[sk]. I've discared that because of a few simple reasons. First of all, in situation where Bob exchanges messages with Alice, he also has the identical information about both signatures and messages, and it's well known that it's not possible to forge someones sk with signature and message. Also, number of leaked messages (256) is quite specific and it's obvious that it's there for a reason, but it's quite small for some hash collision attacks on sk. Another reason to discourage us from that idea is in description itself: "This shouldn't be possible due to existential unforgeability". So, let's dive into provided materials and try to get more ideas.
Trying to understand existing BLS attacks is a topic that comes naturally given the above thoughts. In materials we come across Rogue key attacks, from which we can obtain interesting ideas how fake valid signatures can be created with just simple algebratic manipulation. Unfortunately the setup is different from our puzzle. Multiple users are signing the same message, but in our setup it's just the opposite, we have one user (Alice) signing different usernames. After additional research I found few more attacks: Consensus attack and Splitting zero attack, due to the length of this blog I won't go into those, I'll just mention that their setup is also different then one we have.
Knowing that every signature comes from the same sk, and after playing with bilinearity properties we can obtain simple but powerful equality:
given that: e(g, sig) = e(g, sk * h(M)) = e(pk, h(M))
e(g, sig1 + sig2 + ..., sign)
= e(g, sk * h(m1) + sk * h(m2) + ... + sk * h(mn))
= e(g, sk * (h(m1) + h(m2) + ... + h(mn)))
= e(pk, h(m1) + h(m2) + ... + h(mn))
With m and sig provided, Alice verifies that:
e(g, sig) = e(pk, h(our_username))
So, from the statment above we are able to produce pk on the left side, now we have to figure out how to produce h(our_username) given the leaked messages. One potential solution is maybe "subset problem" - if we can find combination of given messages that will sum up in our hash. So, at the moment it's not that clear if it is feasible to find that sum, we still have Pedersen hashes as unexplored resource, and don't forget that number 256 still has some role to play.
We use this hash to hash arbitrary message on EC. Let's see how it's done in this particular case. From materials and code examination I'll provide simplified pseudo code of pedersen calculation:
m = [m0, m1, ..., mn] - message bits
g = [g0, g1, ..., gn] - n generators of underlying ec field
digest = group_zero_element;
for i in range(len(m)):
if m[i]:
digest += g[i]
return digest
So, if bit of given message equals to 1, we add generator on that position, else just skip.
If we examine the above code closer, it's just the inner product of m and g. So
pedersen(m) = <m, g> = m0*g0 + m1*g1 + ... + mn*gn
Which leads us to a really nice propery, we can find pedersen hash of message without directly calculating it:
pedersen([0, 1]) + pedersen([1, 0]) = pedersen([1, 1])
Having all this linearity properites, it makes sense to search for the solution within liear algebra.
Now we should finally focus on 256 leaked messages and signatures. Before hashing a message to curve, blake2 hash of it's bytes is obtained. By doing that we ensure a uniform distribution of output points and every message can be represented as an hex array which length is 64 - meaning that its bits representation is an array of lenght 256.
On one side we have 256 messages which can all be represented as 256 bit array - so it's quadratic matrix. On the other side we have our message also represented as a 256 bit array.
Now it's clear why 256 is important - system A * x = y now has unqiue solution by Cramer's rule. A is the above mentioned quadratic matrix, y is our message and x are the coeffitiens for which we are solving. To make it more clear I'll provide a small example over 3 bit space:
a = [a0, a1, a2] - first message
b = [b0, b1, b2] - second message
c = [c0, c1, c2] - third message message
y = [y0, y1, y2] - our message
System to solve:
[a0, b0, c0] [x0] [y0]
[a1, b1, c1] * [x1] = [y1]
[a2, b2, c2] [x2] [y2]
Which leads us to:
a0*x0 + b0*x1 + c0*x2 = y0
a1*x0 + b1*x1 + c1*x2 = y0
a2*x0 + b2*x1 + c2*x2 = y0
So,
every bit of message "a" should be multiplyed by x0
every bit of message "b" should be multiplyed by x1
...
It's same as multiplying :
message "a" with x0,
message "b" with x1,
...
This system should be solved over the bls12-381 scalar field(52435875175126190479447740508185965837690552500527637822603658699938581184513). I've used wolfram mathematica, but also there are other great tools like sage math for example.
After obtaining system solutions, we just need to multiply every signature with it's corresponding coefficient and sum of those will be the affine point representing signature that can pass verification or in other words, that it's the final SOLUTION of the puzzle.