PoliCTF 2017

PoliCTF 2017 - Splyt

09 Jul 2017

Case Notes

Bob splitted a secret and gave some pieces of it to some of his friends. We managed to convince Eve and Chris to give us their shares.

Download the challenge here!

(SHA 256 checksum: 85f204b9f2bc285aea8f5095f0e1fb634f096a5bcc3c79c350ac5bac3b411977)

Recon

We have 4 main files given, Splyt/__init__.py, build.sh, challenge.json, splyt.py. The files can be found here. It is recommended to have a look at the files first before proceeding (it is not a reversing challenge so don’t worry).

init.py

Upon inspection, this file contains 2 main functions.

split(secret, N, T)

This function uses the Shamir Secret Sharing Scheme to split the given secret into N shares so that at least T shares are needed to reconstruct the secret. More specifically, each character in the secret (in this case our flag) is being splitted into N shares.

join(shares)

This function reconstructs the secret from the shares generated with split().

The rest are just helper functions to do some math for us.

pick_coefficients(threshold)

Returns a list of threshold - 1 random numbers as the coefficients for our polynomial.

compute_poly(x, secret, coefficients)

Returns the result of f(x) where coefficients are the coefficients of the polynomial and secret is the constant term.

compute_lagrange_interpolating_polynomial(x, points)

Calls lagrange_basis_polynomial() to interpolate the points, in order to reconstruct the secret.

lagrange_basis_polynomial(x, points, i)

Just performing some calculations.

splyt.py

This script can be used with either python splyt.py split <file> <n> <threshold>, or python splyt.py join <shares.json>, and calls the corresponding function in __init__.py.

build.sh

In short, this bash script calls splyt.py with the flag and arguments N = 20 and T = 13, then uses jq on the result to get 3 out of 20 shares, and saves them in challenge.json.

challenge.json

Contains the shares generated with build.sh

The main thing here is the Shahmir Secret Sharing scheme that is being used by the script. More information can be found here.

If you are lazy, you can read a less detailed guide of it here.

Aim

The main objective of this method is to divide a secret S into n shares, so that with t or more shares the secret can be easily reconstructed. However with less than t shares available, if implemented correctly, it is completely impossible to reconstruct the secret, even with unlimited computational resources.

Implementation

Say we now want our secret to be splitted such that it needs to be reconstructed from at least t shares, we pick t - 1 random numbers as coefficients for a polynomial with degree t - 1, f(x) without the constant term, and set the constant to be our secret.

Then, we just pass in t different values to f(x) to get t different shares. Of course we can create more than t shares, but only t values are needed to reconstruct our secret.

Reconstruction

Reconstructing the secret is pretty easy, we just need to compute the Lagrange basis polynomial (which basically just does some interpolation), to reconstruct the polynomial and retrieve the secret which is the constant term.

There is an example here on the entire process of splitting and reconstructing.

Challenge

According to build.sh, we are given 3 shares while needing 13 shares to reconstruct the secret. The astute reader may recall that it was mentioned earlier that without the required amount of shares it is impossible to reconstruct the secret.

That’s true, however, only if it is implemented properly.

Definitions

Before we move on, we need to define some mathematical terms.

The splitting is done with the mathematical function f(x) = polynomial(x) + secret, where polynomial(x) is the t - 1th degree polynomial without the constant term, and secret is the corresponding ordinal value of the character in the string.

If we have a string x0,x1,x2...xn, where xi represents the ith character in the string, and have y0,y1,y2,...,yn, where yi represents one of the shares for xi, we can say that yn = polynomial(p) + xn, where p is an arbitrary value mentioned earlier used to get one of the shares of the secret.

Implementation flaw

If we look at the program carefully, we realise that the same random values are being used to split each of the characters in the string, which means polynomial(x) is always the same.

The main problem is that we can have y0 = polynomial(p) + x0, and y1 = polynomial(p) + x1 with both polynomial(p) being the same function. You know what that means, we can just simply do y1 - y0 = x1 - x0, y2 - y0 = x2 - x0, and etc.

Solution

Now, we don’t even need 13 shares to reconstruct the secret, in fact, we just need 1.

Since the difference between each value in a share is the same as the difference between their corresponding secret, I made a list of the differences.

I also applied a modulus of 255 to the values as that was being done in compute_poly() and compute_lagrange_interpolating_polynomial().

#!/usr/bin/env python3
import sys
import json
from Splyt import Splyt

with open(sys.argv[1]) as f:
	shares = json.load(f)

secret = ""
base = []
prev = shares[0]["y"][0]

secret_len = len(shares[0]["y"])
for i in range(secret_len):
	base += [shares[0]["y"][i] - prev]

Since I have the relative difference of every character, I can just add different offsets to them, and the flag will be one of the resulted strings.

for i in range(ord('a'), ord('z') + 1):
	for c in base:
		sys.stdout.write(chr((i + c) % 255))
	print("")

for i in range(ord('A'), ord('Z') + 1):
	for c in base:
		sys.stdout.write(chr((i + c) % 255))
	print("")

vagrant@vagrant-ubuntu-trusty-64:/vagrant/polictf/splyt$ python3 solve.py challenge.json
ag\bvm.pn,ibZm/i_+hZ,nZi+oZapix
bh]cwn/qo-jc[n0j`,i[-o[j,p[bqjy
ci^dxo0rp.kd\o1ka-j\.p\k-q\crkz
dj_eyp1sq/le]p2lb.k]/q]l.r]dsl{
ek`fzq2tr0mf^q3mc/l^0r^m/s^etm|
flag{r3us1ng_r4nd0m_1s_n0t_fun}

gmbh|s4vt2oh`s5oe1n`2t`o1u`gvo~
hnci}t5wu3piat6pf2oa3uap2vahwp
iodj~u6xv4qjbu7qg3pb4vbq3wbixq
jpekv7yw5rkcv8rh4qc5wcr4xcjyr
kqflw8zx6sldw9si5rd6xds5ydkzs
lrgmx9{y7tmex:tj6se7yet6zel{t
mshny:|z8unfy;uk7tf8zfu7{fm|u
ntioz;}{9vogz<vl8ug9{gv8|gn}v
oujp{<~|:wph{=wm9vh:|hw9}ho~w
pvkq|=};xqi|>xn:wi;}ix:~ipx
qwlr}>~<yrj}?yo;xj<~jy;jqy
rxms~?=zsk~@zp<yk=kz<krz
synt@>{tlA{q=zl>l{=ls{
tzouA?|umB|r>{m?m|>mt|
u{pvB@}vnC}s?|n@n}?nu}
v|qwCA~woD~t@}oAo~@ov~
w}rxDBxpEuA~pBpApw
x~syECyqFvBqCqBqx
ytzFDzrGwCrDrCry
zu{GE{sHxDsEsDsz
AG<BVMPNIB:MI?H:N:IO:APIXä
O;JP;BQJYå
Q<CRKZæRPKD<OKA
DJ?EYPSQLE=PLBK=Q=LR=DSL[ç
EK@FZQTRMF>QMCL>R>MS>ETM\è
FLAG[RUSNG?RNDM?S?NT?FUN]é
GMBH\SVTOH@SOEN@T@OU@GVO^ê
HNCI]TWUPIATPFOAUAPVAHWP_ë
IODJ^UXVQJBUQGPBVBQWBIXQ`ì
JPEK_VYWRKCVRHQCWCRXCJYRaí
KQFL`WZXSLDWSIRDXDSYDKZSbî
LRGMaX[YTMEXTJSEYETZEL[Tcï
MSHNbY\ZUNFYKTFZFU[FM\Udð
NTIOcZVOGZVLUG[GV\GN]Veñ
OUJPd[^\WPH[WMVH\HW]HO^Wfò
PVKQe\_]QI\XNWI^IP_Xgó
QWLRf]`^YRJ]YOJ^JYJQ`Yhô
RXMSg^a_ZSK^ ZPYK_KZ`KRaZiõ
SYNTh_ b`[TL_![QZL`L[aLSb[jö
TZOUi`!ca\UM`"\R[MaM\bMTc\k÷
U[PVja"db ]VNa#]S\N bN]cNUd]lø
V\QWkb#ec!^WOb$^T ]O!cO^ dOVe^mù
W]RXlc$fd"_XPc%_U!^P"dP_!ePWf_nú
X^SYmd%ge#`YQd&`V"_Q#eQ`"fQXg`oû
Y_TZne&hf$aZRe'aW#`R$fRa#gRYhapü
Z`U[of'ig%b[Sf(bX$aS%gSb$hSZibqý

We get flag{r3us1ng_r4nd0m_1s_n0t_fun}

Notes

Bad implementation not design

Most of the crytographic methods being used out there are proven to be secure and hard to crack. However, it is due to implementation mistakes like this that allows the attacker to break the encryption.

Acknowledgements

Thanks to the Tower of Hanoi team for setting up this challenge.