[HITCON 2022] - Babysss

지난번에 포스팅 했던 문제인데,, 그냥 아무 생각 없이 다 지웠다가 지우면 안될 문제들까지도 다 날라가버렸다 ㅠㅠ 그래서 Notion 에 작성했던 것을 토대로 다시 포스팅을 해보고자 한다. (저처럼 충동적으로 행동하시면 이 꼴 납니다 ㅎㅎ)

🖲️ Code Analysis

먼저, 코드부터 천천히 살펴보자. 별로 어렵지 않은 문제라 비교적 쉽게 해결할 수 있다.

from random import SystemRandom
from Crypto.Cipher import AES
from hashlib import sha256

rand = SystemRandom()

def polyeval(poly, x):
    return sum([a * x**i for i, a in enumerate(poly)])

DEGREE = 128
SHARES_FOR_YOU = 8  # I am really stingy :)

poly = [rand.getrandbits(64) for _ in range(DEGREE + 1)]
shares = []
for _ in range(SHARES_FOR_YOU):
    x = rand.getrandbits(16)
    y = polyeval(poly, x)
    shares.append((x, y))
print(shares)

secret = polyeval(poly, 0x48763)
key = sha256(str(secret).encode()).digest()[:16]
cipher = AES.new(key, AES.MODE_CTR)
print(cipher.encrypt(flag))
print(cipher.nonce)

POLY 라는 list 에 임의의 값들을 추가한 다음, 이를 이용해서 polyeval 함수로 계산해주게 된다. 잘 보면, poly 는 어떤 x 에 대한 방정식의 계수들을 모아놓은 것으로, 계수에 x 의 차수에 대한 값을 더해서 계산해주면 된다.

 

예를 들어서 [1,2] 이고, x = 3 이라면, polyeval 로 계산한 최종 값은 1 + 2 * 3 = 7 이 된다는 것이다.

 

최종적으로 우리는 이 secret 값을 통해서 AES 의 key 를 계산해내기에, poly list 만 추출해낼 수 있으면 문제를 해결할 수 있을 것이다.

💡 Main Idea

우리는 poly 로 계산한 값들을 총 8 개 가지고 있다. 이 8개의 값들을 이용해서 문제를 해결해야 한다. 여기서 방정식의 계수가 항상 동일한 점을 이용하면 모든 계수를 leak 할 수 있겠다.

 

예를 들어 ax^4 + bx^2 + c*x + d 라는 방정식이 있다고 가정하자. 이 방정식은 mod x 로 계산한다면 어떻게 될까??

 

당연하게도 d ( mod x ) 라는 값으로 나올 것이다. 이 문제도 마찬가지이다. 8개의 x 에 대해서 각각의 결과값들을 해당하는 x 에 대해서 나머지를 구한다면, 공통적인 계수가 각각의 modular 에 대해서 어떤 값을 가지고 있는지 나오게 된다!!

📖 Exploit Code

shares = [[41458, 3015894889650529600470920314593280408459518223054415623846810748413393737686521849609926975694824777687791824408686652245102687392987299828716863372946074882798754477101786150262288970710451710086966378817944448615584285684364802621112755627795146504720812935041851556318832824799502759754100408717888912062197676588256634343721633045179136302533777168978134770315363985448879229514802330846792965525004570768212871252658334277172395338054448791891165981203069346039654617938169527772805687564575525262812469960675835101499054296722994451502140787064163668418661661374437567033971648550576296023422536253955229],[3389, 188433716494377932944071544153838579057591833387651830021721770473524507947811754295899393634645349682360212761145039355690817927625249659010181081209481357850193656763556243022791637306094953982811471415645267589939465925098159204147714779617946431727015863707468081949286110249296858079354949234074465541940264775783884708819566758872542606519408358277173683256608326688673226933790117016596834640875497643330432185114931410656582728964222203181026468387428893233826461], [20016, 100434774699078525844435127144579870564983915777345068724291926367405061427748836490810414860997895358378538088786283372231649911113841061354335739776409724471256377867811133591349442950556374825868587940833009529662869081130218551306459690738900795035660420986807973542512081415453215211908130387754214098414826747340962722685373241806099462750595976574593799013733614097923338311883793416643213898201680852118540438376386415411317989072583126108177482838299109479175882214603698768498421016054035672774286507312986602290254323930575001551875601243671354491241420409219], [50683, 444545881882748849210617532697661279371689521082184772844723908765173319859389018743414369945234307906596253496624659734919646710483514374218993496994560985318096082923429834553341897367168830049334302307406087637232329348570485341223211629167329394484624055745054495405880099706580380696671879365741197827080224977821589102425678989782880274304484630899425664722718972847034030888019348402685383311095030884356731112886316823960378572796288532824588478234949384868912708000223119984161992105752059185137674711077940232530298853451166664700609238496874366152042676602089571801873748042888046623717879084695143810047335029], [6445, 101461065764578261241074518788237888467081270902741849861528201922043223477790661159690684156056890167304291810116447916457265705130707166062372766839626095333813681671546097679623755546322833727082145873422243641505450049118758544298328784536759107951763715458884889255549767465897671061295486677353893450789955616926292534325337544782386120469581214993770910137353221116457111551538222138388416162630076391624447865248920466274175229034129561913505977209131490066291917549232913771218316393849495621818397], [1359, 301175604076484656987097022479686300460199620068959954988990822483114048418823291831080744590394713639405681060973359346474547015206086229256524657214311815578895906855833813636970640902962286472992468394831014254279137613828904924898823470285520515090889491445149243620044782726415898188702226878029241518020146726699446397961112596830223444821094650508662477147134721631935528182772284099429814417490160457082241680661], [45286, 244867719210730952183489456726726432791149629831242968845409984537752132549250274779516590253042559196452609852176114909791657154092483479876795482861784431886143414585698773882088948703730268947925790809436449512089696895048994874003651088538416399435467483409931121063976149037130454114161175715871108284419975118570732022104749321213013756795645219060997019373915339235627535694458093194617642834806820772479160496966470147893963746139947337914575231526069667124822677688977724313174612816604463495630041075005651663546036363128325535621487658461744362098985183050127661470315454320073092665472364666768205258769], [5649, 4766101906865350375503575239791521167258753430948472304582908507542293595346756303331383584550516424087839316050412570112796817549423179461056531056102741963677007097061600281918678364910813585444151640384802648969082273001142879806475184857246441212406056540028447374033197873299250076862108042582790928405869475508762352345569281589853917902601519294573327847401601789315980414998055948162169170771240383220643819333682845459742335249254576151835966500230706707674854493184181354958093926469960861]]
enc = b'G$\xf5\x9e\xa9\xb1e\xb5\x86w\xdfz\xbeP\xecJ\xb8wT<<\x84\xc5v\xb4\x02Z\xa4\xed\x8fB\x00[\xc0\x02\xf9\xc0x\x16\xf9\xa4\x02\xb8\xbb'
nonce = b'\x8f\xa5z\xb4mZ\x97\xe9'
from random import SystemRandom
from Crypto.Cipher import AES
from hashlib import sha256
from sympy.ntheory.modular import crt
def polyeval(poly, x):
    return sum([a * x**i for i, a in enumerate(poly)])

key = list()
m = [mm[0] for mm in shares]
for _ in range(128):
    v = list()
    for ss in shares:
        v.append(ss[1] % ss[0])
    res = int(crt(m,v)[0])
    key.append(res)
    for ss in shares:
        a = ss[1] - res
        assert a % ss[0] == 0
        a = a // ss[0]
        ss[1] = a
key.append(2663837216318969053)
secret = polyeval(key,0x48763)
key = sha256(str(secret).encode()).digest()[:16]
cipher = AES.new(key, AES.MODE_CTR, nonce=nonce)
print(cipher.decrypt(enc).decode())

이렇게 key 를 모두 구해낼 수 있고, 어렵지 않게 key 를 통해서 ciphertext 를 복원해낼 수 있었다. 

 

 

Flag : hitcon{doing_SSS_in_integers_is_not_good_:(}