Skip to content

Instantly share code, notes, and snippets.

@hyunokoh
Created October 28, 2021 01:47
Show Gist options
  • Save hyunokoh/8c19c062474bfe28183b9a94b94ce718 to your computer and use it in GitHub Desktop.
Save hyunokoh/8c19c062474bfe28183b9a94b94ce718 to your computer and use it in GitHub Desktop.
Let's hash out
Title : Let's hash out
Solved by Hyunok Oh (hyunokoh@gmail.com)
Problem : 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?
Answer : BLS signature is H(m)^sk where m is a message and sk is a signing key.
If a pedersen hash H is used for 256 bit input then H(m) = \sum_{j=1}^{256} b_j G_j
where m=b_1 || ... || b_256, and b_j are binary, and G_j are hash keys (group elements).
Since 256 signatures are given, let each signature be S_i (1<= i <=256).
Then S_i = \sum_{j=1}^{256} b_{i,j} sk G_j for 1<= i <=256.
To simply the equation, let S be a column vector of (S_1, ..., S_256),
B be a matrix of [[b_{1,1} ... b_{1,256}] ... [b_{256,1} ... b_{256,256}]],
and A be a column vector of (sk G_1, ..., sk G_256).
Then the equations are becoming S = B A.
For a randomly generated binary matrix B, it is known that the probability that B is invertible is more than 0.288.
Note that the probability of a random l×l binary matrix to be invertible is
p(l) =\prod_{k=1}^l(1−2^{−k}) and the limit is \lim_{l-->\inf}p(l) ≈ 0.288788.
Therefore with a non-negligible probability (exactly more than 28%), we can compute A ( = B^{-1} S).
After computing A, for a given message m' ( = b'_1 || ... || b'_256),
we can compute the forged signature \sum_{j=1}^{256} b'_j sk G_j.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment