PAD Holiday Encryption Challenge 4

All good things must come to an end, so sadly, this is the final part of our challenge. We hope you have fun cracking the final puzzle!

Make sure to connect with us on Twitter and Discord if you enjoyed participating in our Christmas Challenge!

Challenge 4 Details:

In Challenge 2, you played the role of verifier in a zero-knowledge protocol. The verifier is supposed to learn that some fact is true, without learning anything else - but you found a way to learn the secret held by the prover.

In this challenge, you will do the opposite. You will be the prover even though you do not know the secret.

We work over the same group as in Challenge 1. Your friend computes a value h = gx, where x is a secret that you do not know:

• h = 49058952657740725354233935099102638115233099545082590230320907521911300169263

Your friend will create a non-interactive ZK proof of knowledge of the discrete log of h. The proof has the following form:

• The prover chooses a random value r from G and computes t = gr.

• The prover derives a challenge value c as f(g||t||h), where f is a hash function and || is string concatenation (see code sample).

• The prover sends to the verifier the NIZK (t, c, s) where s = r + cx, modulo q.

• The verifier accepts if and only if gs = t * hc. modulo p.

Your friend posts the NIZK below, but uses a flawed implementation because the choice of hash function f is too weak: it is simply the first eight digits of the digest of SHA-256:

• t = 70721044576916814288132921824189394601762867528615040793835235325077347383329

• c = 53584943

• s = 21412631881183161520013274604070003212992868897377917235050401754756867922788

You want to use your friend’s NIZK to issue another NIZK for a discrete log without knowing the discrete log. Despite not knowing x, you will prove knowledge of gx+y. Your NIZK will be (t', c', s') where t' = t and c' = c and you should choose y as the smallest integer allowing your proof to take this form. The answer to this challenge is s’.

Example python:

def weak_hash(x): return str(int(hashlib.sha256(x.encode()).hexdigest(), 16))[0:8] def challenge_value(g, t, h): return weak_hash(str(g) + str(t) + str(h))

Secret Key Reconstruction Directions

You think that you have sufficient information to steal our coins? Let’s see! The private key to our wallet has been secret shared into 4 shares using a Shamir scheme with threshold 3. The prime number we use in the Shamir scheme as the polynomial modulus is given by:

• p = 47691027682862136953792492644313896868091731521408932524622766147428587604078803781777571528885751867730427043206604868334701714257315063321

The first step is to convert each challenge answer into the correct share:

• Challenge 1: The share is the English message M encoded as an integer in the way described within the challenge. As a sanity check, this is a 65 digit number beginning and ending with a ‘4’.

• Challenge 2: The share is our secret key from the challenge. It is a 77 digit number beginning with a ‘1’ and ending with a ‘0’.

• Challenge 3: The answer to the challenge chal_three_ans is a hexadecimal number. The share is given by chal_three_ans * q (mod p), where q = 6286830612815110881327732104221622054406275870503544698922570348552541145913735084592342651936238046831503424600151140036174162874314986548. (Do not forget to convert all numbers to base 10 before performing operations.) As a sanity check, the share is a 125 digit number starting with ‘7’ and ending with ‘1’.

• Challenge 4: The share is given by chal_four_ans * q' (mod p), where q' = 39099927403513413972814714808791399633126497503101011258146112966414490527438158022175438013652534241877600100455331203677855399701672740212. The share is a 126 digit number starting with ‘2’ and ending with ‘7’.

Any three shares are enough to reconstruct our key:

1. Interpolate the degree-2 Shamir polynomial and find p(0). Use the fact that the shares as computed above give p(i)for i=1,2,3.

2. Our secret key is a message encoded using the same method as in Challenge 1. The encoding of the message is p(0)and you must undo the encoding to obtain the key.

3. The key is a private key for our Electrum wallet. You can use Electrum and import the key. You will need to prepend the key with “p2wpkh:“. Congrats!