ZKHack Challenge No.1 – step by step

The LogN team is a team of ZK researchers consisting of mathematicians and programmers. It was interesting to test our current knowledge and gain new ones by participating in the ZK hackathon. Our result is 15th place, which we believe is a great placement, judging by our short experience in this field (and the exceptional teams ahead of us and their long experience).

This article will present our solution to the first puzzle on the ZKHack event. ZKHack is a 7–week virtual event featuring weekly workshops and advanced puzzle solving competitions. Each week, participants learned about key ZK concepts and tools and/or competed to find bugs in protocols in puzzles competition and win prizes.

ZKHack – puzzle 1

Puzzle problem

Alice designed an authentication system in which users gain access by presenting a signature on a username that 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 didn’t know! This shouldn’t be possible due to existential unforgeability, as she never signed such a message. Can you find out how it happened and produce a signature on your username?

Prerequisites

We will refer to BLS signatures, Pedersen hashes and a little bit of linear algebra. We assume that the reader is already familiar with those concepts for simplicity. If not, ZKHack provided resources are sufficient to follow the further text.

Initial thoughts

So, from the puzzle problem, it’s clear that we have to play with BLS signatures. Maybe the first thing that comes to mind is to somehow forge a private key [sk]. We have discarded that because of a few simple reasons.

First of all, in situations where Bob exchanges messages with Alice, he also has identical information about signatures and messages, and it’s well known that it’s not possible to forge someone’s [sk] signature and message. Also, some leaked messages (256) are quite specific and it’s obvious that it’s there for a reason, but it’s pretty tiny for some hash collision attacks on [sk].

Another reason to discourage us from that idea is in the description itself: “This shouldn’t be possible due to existential unforgeability.” So, we dived into provided materials and tried to get more ideas.

BLS Attacks

Understanding 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 exciting ideas on how valid fake signatures can be created with just simple algebraic manipulation.

Unfortunately, the setup is different from our puzzle. Multiple users sign the same message, but it’s just the opposite in our setup. We have one user (Alice) signing different usernames. After additional research, we found a few more attacks: Consensus attack and Splitting zero attack.

Due to the length of this blog, we will not go into those. We will mention that their setup is also different from ours.

BLS properties

Knowing that every signature comes from the same [sk] and after playing with bilinear map, we obtain simple, but powerful equality. Given that
e(g,sig) = e(g, [sk] · h(M)) = e(pk, h(M)), follows that

e(g, sig₁ + sig₂ + … + sig_n) = e(g, [sk] · h(m₁) + [sk] · h(m₂) + … + [sk] · h(m_n)) =
e(g, [sk] · (h(m₁) + h(m₂) + … + h(m_n))) = e(pk, h(m₁) + h(m₂) + … + h(m_n)).

With m and sig provided, Alice verifies that:
e(g, sig) = e(pk, h(our username)).

So, we can produce pk on the left side now from the statement above. Given the leaked messages, we have to figure out how to make h(our username). One potential solution is a” subset problem” – if we can find a linear 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 an unexplored resource and don’t forget that number 256 still has some role to play.

Pedersen hash

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 we’ll provide simplified pseudo code of pedersen calculation:
m = [m₀, m₁, …, m_n] − message bits
g = [g₀, g₁, …, g_n]− 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 the given message’s bit equals 1, we add a 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 >= m₀ · g₀ + m₁ · g₁ + … + m_n · g_n.

This 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 these linearity properties makes sense to search for the solution within linear algebra.

Linear algebra

Now we should finally focus on 256 leaked messages and signatures. Before hashing a message to curve, the blake2 hash of its bytes is obtained. By doing that, we ensure a uniform distribution of output points. Every message can be represented as a hex array whose length is 64 – meaning that its bits representation is an array of length 256.

On one side, we have 256 messages which can all be represented as a 256-bit array – so it’s a quadratic matrix. On the other hand, our message is also represented as a 256-bit array.

System solving

System (4) should be solved over the bls12-381 scalar field

(52435875175126190479447740508185965837690552500527637822603658699938581184513).

We’ve used Wolfram Mathematica, but there are other great tools like SageMath.

Final calculation

After obtaining system solutions, we need to multiply every signature with its corresponding coefficient. The sum of those will be the affine point representing signature that can pass the verification or, in other words, that it’s the final SOLUTION of the puzzle.

If these challenges are interesting to you, maybe we could join forces and get a medal next time. Throw us your CV or GitHub to [email protected]