CSAW'19 CTF Finals Writeup - Sharing is Caring

Last week we (Sudo_root) played the CSAW’19 CTF in the MENA region and got the second place, the challenges were great and full of crypto, I personally liked the sharing is caring challenge which was worth 500 points so I’m making a writeup about it.

Challenge description

The challenge tells us that ‘sharing is caring!’ and it was just hinting that the challenge was about a secret sharing scheme. The goal was to recover the secret under certain conditions, the most basic one is that we can only get up to threshold-1 shares (otherwise the challenge would be about doing calculations), however, we were able to find an additional free share and thus recover the secret really easily.
The challenge provided a Python2 code that was running on the remote server and you can find it here.

Solution

So the challenge was about secret sharing using polynoms, where single points were complex numbers, the app server asks us to provide a polynom of degree higher or equal to 9000 (minimum threshold is 9001) and a threshold higher than 9000 and asks us about how many share we need, we can get up to THRESHOLD-1 shares, so the best is to have the maximum number of shares so we need to recover only one share to be able to get the secret. The main thing that I noticed is that no matters what polynom we provide, it will always map the value i=0 with the point (a0,0) (a0 is the coefficient of x^0 from our polynom), and since a0 is 0 in our case, this will just be a free share that we can use to do lagrange interpolation and recover the secret.

The solution script for this challenge can be found here, the main script is solve.py which will use a second sage script to do the heavy math. Basically the script will do the following:

• get the prime number used
• send the polynom, threshold and the number of shares to get
• get the shares and save them into files so the second script uses them
• run the lag.sage script to do the heavy math and recover the secret
• send the secret and get the flag!

Below is the execution of solve.py

[youben@ym sharing_is_caring]$ python2 solve.py 
[+] Opening connection to crypto.chal.csaw.io on port 1000: Done
[+] Got prime 86279386867068376297302505847424156586494550934111236939596248557564380476339
[+] Setting polynom to: 5x^1 + 87x^9000
[+] Setting threshold to: 9001
[+] Setting the number of shares to: 9000
[+] Got the shares
[*] Cracking secret...
[+] Finished cracking with status 0
[+] Got secret 33204634315060132722370276963862036606806159174093789534175596021531768399803
[+] Got from server: '33204634315060132722370276963862036606806159174093789534175596021531768399803
'
[+] Got from server: 'flag{i_cant_believe_someone_else_found_a_cheese}
'
[+] Closed
[*] Closed connection to crypto.chal.csaw.io port 1000