RaRCTF 2021 | Shamir's Stingy Sharing.md

Task

I set up a secret sharing system with my friends, but now my friends all hate me. Can you help me get the secret anyway?

Attachment with the source code:

import random, sys
from crypto.util.number import long_to_bytes

def bxor(ba1,ba2):
	return bytes([_a ^ _b for _a, _b in zip(ba1, ba2)])

bits = 128
shares = 30

poly = [random.getrandbits(bits) for _ in range(shares)]
flag = open("/challenge/flag.txt","rb").read()

random.seed(poly[0])
print(bxor(flag, long_to_bytes(random.getrandbits(len(flag)*8))).hex())

try:
	x = int(input('Take a share... BUT ONLY ONE. '))
except:
	print('Do you know what an integer is?')
	sys.exit(1)
if abs(x) < 1:
	print('No.')
else:
	print(sum(map(lambda i: poly[i] * pow(x, i), range(len(poly)))))

Task analysis

First thing that catches the eye is that this "secret sharing system" isn't actually a polite one - it responses with a heartfelt insult if we dare to send it something but integer. Maybe that's the real reason why all friends hate you now, Shamir? Anyway, after hours of googling what an integer is and overcoming a sudden impostor syndrom attack I was able to finally recover from such a terrible assault and start investigating source code. Below is a scratch of how it works:

• 30 random numbers (shares) 128 bits long are generated when we connect to server and are put into array called poly
• First share of poly is used as seed for a subsequent number generation
• Each flag character is XOR ed with randomly generated bits and result is printed to us as a hex value
• Then we are requested to enter aforementioned integer x
• x is used to calculate sum poly[i] * x ** i, where i = 0, 1 ... 29. This sum is also printed

Finding vulnerability

So far, we are given two values:

1. Encrypted flag
2. Some sum of shares that depends on our input x

To get the flag we need to decrypt it. To decrypt the flag we need to know the key. Once we get it, we can simply XOR it with the encrypted flag for decryption. Key is some randomly generated number. Fortunately for us, first share of poly is used as a seed for key generation. So if we know the poly[1] then we'll be able to replicate key generation.

We know that poly[0] along with other shares is used to calculated the sum of shares. This sum also depends on x, our input. Let's investigate deeper the relation between x and sum of shares and see what we can get out of it.

For demonstration purpose, let's consider: poly = [42, 33, 54] for x = 3

42 * (3^0) = 42
33 * (3^1) = 99
54 * (3^2) = 486
sum = 42 + 99 + 486 = 627

Hope that now it's clear how the sum is calculated. But x = 3 is not that useful for us - there's no way we can get poly[1] which is 42 from 627. Let's consider more interesting case where x = 1000

42 * (1000^0) =       42
33 * (1000^1) =    33000
54 * (1000^2) = 54000000
sum = 42 + 33000 + 54000000 = 54033042

Bingo! You see it? Last two digits of sum is actually the first share that we are looking for. So, by entering x = 10^n where n > len(poly[0]) we are able to easily extract first share from the resulting sum.

Assembling exploit

Let's get poly[1] first. I am a lazy one, so I just did it manually:

f79ace6c50045d9617387178738bc492c8a36bce6f62065ffd1712060127af
Take a share... BUT ONLY ONE. 1000000000000000000000000000000000000000000000000000000000
34478190794372095687151499154929969606000000000000000000189455481892595731087980110991446798558000000000000000000114630140621231452731774690192563700399000000000000000000106632736526610982274784394939300666050000000000000000000291631389647804997343114057740596739647000000000000000000172012636010265165504878126886679875380000000000000000000336861561406951606841928859228335262394000000000000000000161848776124756622238036523550575234204000000000000000000206862146054773644222270964178367439926000000000000000000224747282815671094222821409187167038646000000000000000000167733096288035467315188096730334274378000000000000000000197540947692537841721737142231640993834000000000000000000255889694312681513731712154838030686397000000000000000000179179493363428125430318105043279961232000000000000000000042849152778181079831098138309449439970000000000000000000132016736123401412585347409983527651970000000000000000000128062869669623764825957631887084013359000000000000000000282823708958133194464944972998546961307000000000000000000258963511533578375727556494488139105966000000000000000000106113149607806035776895731827681332171000000000000000000317662669549313551440810288726726989624000000000000000000333094458583116878063642005820211993426000000000000000000323902500681250286825223845301590529386000000000000000000067066857889771218669374826568658446582000000000000000000213694534015072472486306685687034856088000000000000000000035020349875265934224376635827160468187000000000000000000323763878541563552432622617181982778364000000000000000000126141063774744186389048070631075055350000000000000000000121036704086086339233282037033529357567000000000000000000005071636503793964919135745354381215807

now all that is left to do is to generate key using poly[0] and XOR it with a given encrypted flag:

#!/usr/bin/python3

import random
from Crypto.Util.number import long_to_bytes, bytes_to_long

def bxor(ba1, ba2):
    return bytes([_a ^ _b for _a, _b in zip(ba1, ba2)])

encrypted_flag = 'f79ace6c50045d9617387178738bc492c8a36bce6f62065ffd1712060127af'
poly_0 = 5071636503793964919135745354381215807

random.seed(poly_0)
key = long_to_bytes(random.getrandbits(len(encrypted_flag)*4))
print(key)
flag = bxor(long_to_bytes(int(encrypted_flag, 16)), key)
print(flag.decode())

After running this script we will get the flag: rarctf{n3v3r_trust_4n_1nt3g3r}

Interesting fact

Formula for sum calculation is very similar to the positional system formula (https://en.wikipedia.org/wiki/Numeral_system#Positional_systems_in_detail) but the latter one has some restrictions