PlaidCTF 2012 – Nuclear Launch Detected [150] (Password Guessing)

Our spies intercepted communications and a file between 5 of the top 10 robo-generals and their nuclear bomb server. We must recover the final launch code from the 5 robo-general’s secret codes, so we can stop the detonation!

Summary: Shamir’s Secret Sharing

Here we have a pcap file where 5 communications take place. Each looks like

> *** Welcome to Remote Nuclear Bomb Launch System ***
> # Enter the launch code: 
< (4, 944438008684116...6L)
> !!! Success !!! Bomb has been launched!

It seems that 5 secret codes together allow to launch the bomb. Such things can be done with some secret sharing scheme. Google for some and Shamir’s Secret Sharing is the easiest to find. In wiki’s example only 3 keys are needed, so we need to extend it to 5.

$$a_0=y_0 * {(-x_1*x_2*x_3*x_4) \over (x_0-x_1)*(x_0-x_2)*(x_0-x_3)*(x_0-x_4)}$$

$$…$$

$$a_4=y_4 * {(-x_0*x_1*x_2*x_3) \over (x_4-x_0)*(x_4-x_1)*(x_4-x_2)*(x_4-x_3)}$$

$$secret=\sum_{i=0}^4 a_i$$

Here’s the code:

from libnum import *
 
pairs = []
pairs += [(4, 9444...806)]
pairs += [(2, 8577...243)]
pairs += [(1, 3320...109)]
pairs += [(5, 6259...452)]
pairs += [(3, 6454...858)]
 
p = int(open("p.txt").read())
 
res = 0
for i, pair in enumerate(pairs):
	x, y = pair
	top = 1
	bottom = 1
	for j, pair in enumerate(pairs):
		if j == i:
			continue
		xj, yj = pair
		top = (top * (-xj)) % p
		bottom = (bottom * (x - xj)) % p
	res += (y * top * invmod(bottom, p)) % p
	res %= p
 
print res
print n2s(res)
$ py shamir.py 
723126740974638694358413759917266643240116870314821228110113
s3cr3t_5h4r1n9_i5_H4RD_!!

The flag: s3cr3t_5h4r1n9_i5_H4RD_!!

Leave a Reply

Your email address will not be published.