ecssp (crypto)

The Merkle-Hellman cryptosystem is broken, but what if I use it over elliptic curves?

This is the challenge code:

#!sage
from sage.all import EllipticCurve, GF
from Crypto.Util.number import bytes_to_long

flag = b'SSMCTF{REDACTED}'

#secp256k1
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
a = 0
b = 7

E = EllipticCurve(GF(p),(a,b))

A = [E.random_point() for _ in range(42)]
enc = []

m = bin(bytes_to_long(flag))[2:]
m = m.zfill(len(m)//42*42+42) # makes the number of bits a multiple of 42

for i in range(0,len(m),42):
    buffer = None
    for j, bit in enumerate(m[i:i+42]):
        # the buffer is the summation of points wherein j has a 1 bit
        if bit == '1':
            if not buffer:
                buffer = A[j]
            else:
                buffer += A[j]
    enc.append(buffer)

A = [i.xy() for i in A]
enc = [i.xy() for i in enc]
print(f'{A = }')
print(f'{enc = }')

Output:

A = [(114022552566672434287471812777717333762408551721791348889344472111227927502889, 91848347484952671316308675369245644465513610696925627817363786882910842914630), (5134235591147639910038981348618172041966754946151413595658689762008632417144, 3511794964597550219657005150446044437507191250164867133904557082591168200810), (7032886284728108699844541145867001038913067269804679108520652174728735284910, 23374784913016520963837121466288011654300981565362994781090990047581133995522), (64787929624393757911733465336546182797274948931237749247448226674433887764438, 100817994108392828748624813186243365302623148897918291171263241159232476705779), (61415319441662283644671806891506262708697273153238310958561291976566757851073, 47494855000112343060989722245396024127687216333344414084480138013856386400789), (31185225928020456074752113695930814394830270813864650049700325446839880436127, 98491843633049747320558494747016228169500900638949819454524008871199970848281), (61269037926178524499534355938680601447869226876831633887037654303319306902653, 7355959218752508692581981354345577329362806703629635457558186391126933065749), (46719743249477073536538523513876054148471856984109116152739306755928621137426, 79618227045878281991826536940081720008541694129455394111913396631045566145019), (71315609148455933583113137278156208113945683697681378464038731331649140453423, 41583976526604472993060418781265873641544347584287693599816935475869235033534), (34066985707582221727977428114751711145513492613331952008062524932064871300560, 9357963789875591485663090690843223368692879191592063080397524581806899989236), (112020015499791865542782141811688326015931444990628396652697052762093557415090, 97128953852476344478082470122398620436012998399897014560451651165696740697799), (42634390421337524463301787804160248224871449877456106839396316088983266777563, 36921893488724507975591286756011274949418646781286950314836583088947321399436), (109004872868473933843880334915627471365175851567444755103105745779429972062867, 10573682450940016830774151372886548289936213323569507701136657060721130866102), (24771770795854826019973902904410515550685645037907625865334744293267191703844, 238372343166032899435738271938582337808395959304176115681472003829671766069), (89898689270246478820497970612987341984775455104130834253057564247800138515216, 51361988465970660503417536945674893360422898646549654448056592592182179319322), (29353616892236794960022032235244696999870640837822460779312808945733127358965, 17189936243022410767965833508172954000235716444164810378420545005517265790590), (40907116228495544023560546056350488549701829492088999807726782859492817068142, 30600558861609828228122226133163256268226672743476940517404142980188899308141), (65595884403128634532554508209524238590976304321760189307800388865013736066122, 43739639766381874302525066091683537092274252516033766178153325330777753436173), (25248021323749208361083970171444517434971442331821340582052299954992625989433, 16433968721701929908034597638247694006984447527539174579327824152287410930927), (66637292000429090447834237361626051524039437607541033364971712194112098231001, 62897600570026652121263578113146768874909942153620854376802483617302774115980), (115212652540512582012577970245526787954210815528182926099395974524525631662162, 99777843108973546310076149803711850216390102688256655995359800874570043056555), (83878517831334008537079994787751658186104835789618280423583097526657039236116, 103511299944003266439173166120956421458183958407018392943008279310148901530099), (52594410772860121402953141618705939118615173192654401872197358793802093515001, 83405724211182079540236196795249163629897595215932404038528725584752940112891), (33065844213457587899962903396905924355762651943441569081451445513507319530855, 84459733639665926869498081695782057380035530851686381235158073488183035616786), (92852131344469309458360217477923144206844568659427057865288421289109253101850, 107983952221059675122423299705365141729775323231590366324267237436140008945947), (96029923597418235178467955471356574309551942895748993166823415663148665366818, 44009545809587730664603276939770224891921201461689182875991144734130730148132), (14491509301756702536461113822340540580917882458515619656898399058847358427165, 49697262878580453821093137648994944864996947361941635057840345229346592103325), (7142334457994882719662437060979343972591452514665838139143484105280906359843, 115551291934769872032845156599846422261691630966595375293712684039045331609773), (76199441895199959275724182330257364704683013310299613213681996128885039748856, 61818592218490595235086300654053309843951970828080818853139158729491555260528), (109929676816214299202831373205057089272383846164015783800295478396646698467323, 85603015167410332963621281121877119398125218999394242687621353796693626604814), (42085095747394420012437156518121954367239135800432273121845002452192659516043, 99152489145483114144014322676393985173394178769761002353396529032837553322954), (46785837870376203194490078015227240349998784412414091973301490669202030071274, 50158820599587084300110311636192802928718158911039536915016098936406858562516), (2542408287329394787358496421330518153382875002992489916936545569680393263826, 90960446941858157396519547124374187601195250590035308278734642699690186774134), (71104981300440345730027322716187483726593985627650490829854057008302951470953, 33514784920149980284990693642981138878817995455645608482499592830700653956566), (2219892059755913648923157677311647289191116275916201596356192006714889434836, 88618328428853723603356473619982882118747874012454061529636978281392148038263), (97178746971516087889535720327071518678118751045576788550771262246668598290172, 109805470081585872699137219689787905302272845563258748145297268263743508487479), (115534988340017196814212470995899778229858109387047371649837573529558387904853, 73561296050053000878918947216300173621080314170028964145490299232785134490670), (71020415564613394809479505654058314877327019326561551804364004670235803702823, 63721115749327971913307535980809347713258942827871762375911063350230411291154), (103525157991421687186695127818409910674944424344157107349452655919519635026348, 32688475822302762091357434289719114377166781834307639574849691681988225039970), (5087645535251679155915786583389386699946293717913736425888766550834106777832, 39404753198204781082643593694294372610894075291929137737571839372499106216263), (46869233779509670367924828352772167995400504169134812168319240561141370079721, 10556762214950234444787499536590640061428436758010737349806108326319636463365), (97699454395659998727515199878750545107706971087247916527908427481361566291361, 102405817218001246838012518871118424034120058607873164728157421470161986209902)]
enc = [(64790039097843726619666409283242777555003893618465502278317178757450138780247, 102844883231790621570884937608458381278419605840318534308920025637869951920685), (65467005106282061101664483249093359627045329274101984251422509764159888516782, 29577274831610547096769142678647481089072852714288000323692708023231117856259), (71126810596268579329235558066839193156863450492831082744027778860379767646458, 10061110158348361585582673111744600909320452001919882022692480289045281568038), (68130211277586543741700239238753266861237930181769784115771631347659811533995, 62916875538459760084037730097955290681027631961337350448937045279643828518377), (40739841185675326976137753552659542076873069897376020788702703621548466410384, 95505667868305009079261482128316557710057532847302718993997202290022214506067), (18113528668110280401511533074417338843730161007004980298553405689312187829593, 54549787510067678331569900262990828737439364417965444112678791347445057986509), (65785972692053719083883036722006292317181610120596386229948182706617388553330, 26925186146344157810917265671643490784806237827525588744976777335589847243551), (52049982563010361166332130366254990594595414206544311311954755536493054807189, 49859379427158965363993305038648217602616149186457294969786353267658272232018)]

It does the following:

• Create a secp256k1 curve

• Create an array A containing 42 random points on the curve

• Converts the flag from a bytestring to a bitstring whose length is a multiple of 42

• For each chunk of 42 bits in the flag, if bit i is 1 then add the point A[i] to buffer. Otherwise do not add the point.

  • Once all bits in the chunk are done, append the resultant point into enc

• Give A and enc .

We can basically think of this as a knapsack cryptosystem, where each random point in A is either added or not added into buffer for every chunk.

We can start by trying to solve the problem for an individual chunk of 42 bits.

It would take too much time to calculate all possible chunk values since there are $2^{42}$ possible resultant points (because there are 42 random points in A, and each is either used or not used).

However, we can use a meet-in-the-middle approach:

• For the first 21 points in A, we calculate all $2^{21}$ possible results of point addition and have some dictionary d1 storing point : bitstring mappings where a given point can be produced by the associated bitstring. Note that $2^{21} = 2097152$ operations can be completed in a reasonable amount of time.

• We do the same for the last 21 points in A for dictionary d2.

• For every chunk we need to solve for, we have the encrypted point p. We iterate through the $2^{21}$ entries in d1 . Then for each point D in d1, we calculate x = p - D. If x is present in d2 then we know that p = D + x. This would imply that the point we are using from d1 and the point we are using from d2 exactly add up to our point p, which means that the bitstring we encrypted is d1[D] + d2[x].

Repeating this for all chunks in enc, we can retrieve the flag.

Below is my solve script (takes a few minutes to complete):

from sage.all import EllipticCurve, GF
from Crypto.Util.number import bytes_to_long, long_to_bytes
from tqdm import tqdm

#secp256k1
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
a = 0
b = 7

E = EllipticCurve(GF(p),(a,b))

A = [(114022552566672434287471812777717333762408551721791348889344472111227927502889, 91848347484952671316308675369245644465513610696925627817363786882910842914630), (5134235591147639910038981348618172041966754946151413595658689762008632417144, 3511794964597550219657005150446044437507191250164867133904557082591168200810), (7032886284728108699844541145867001038913067269804679108520652174728735284910, 23374784913016520963837121466288011654300981565362994781090990047581133995522), (64787929624393757911733465336546182797274948931237749247448226674433887764438, 100817994108392828748624813186243365302623148897918291171263241159232476705779), (61415319441662283644671806891506262708697273153238310958561291976566757851073, 47494855000112343060989722245396024127687216333344414084480138013856386400789), (31185225928020456074752113695930814394830270813864650049700325446839880436127, 98491843633049747320558494747016228169500900638949819454524008871199970848281), (61269037926178524499534355938680601447869226876831633887037654303319306902653, 7355959218752508692581981354345577329362806703629635457558186391126933065749), (46719743249477073536538523513876054148471856984109116152739306755928621137426, 79618227045878281991826536940081720008541694129455394111913396631045566145019), (71315609148455933583113137278156208113945683697681378464038731331649140453423, 41583976526604472993060418781265873641544347584287693599816935475869235033534), (34066985707582221727977428114751711145513492613331952008062524932064871300560, 9357963789875591485663090690843223368692879191592063080397524581806899989236), (112020015499791865542782141811688326015931444990628396652697052762093557415090, 97128953852476344478082470122398620436012998399897014560451651165696740697799), (42634390421337524463301787804160248224871449877456106839396316088983266777563, 36921893488724507975591286756011274949418646781286950314836583088947321399436), (109004872868473933843880334915627471365175851567444755103105745779429972062867, 10573682450940016830774151372886548289936213323569507701136657060721130866102), (24771770795854826019973902904410515550685645037907625865334744293267191703844, 238372343166032899435738271938582337808395959304176115681472003829671766069), (89898689270246478820497970612987341984775455104130834253057564247800138515216, 51361988465970660503417536945674893360422898646549654448056592592182179319322), (29353616892236794960022032235244696999870640837822460779312808945733127358965, 17189936243022410767965833508172954000235716444164810378420545005517265790590), (40907116228495544023560546056350488549701829492088999807726782859492817068142, 30600558861609828228122226133163256268226672743476940517404142980188899308141), (65595884403128634532554508209524238590976304321760189307800388865013736066122, 43739639766381874302525066091683537092274252516033766178153325330777753436173), (25248021323749208361083970171444517434971442331821340582052299954992625989433, 16433968721701929908034597638247694006984447527539174579327824152287410930927), (66637292000429090447834237361626051524039437607541033364971712194112098231001, 62897600570026652121263578113146768874909942153620854376802483617302774115980), (115212652540512582012577970245526787954210815528182926099395974524525631662162, 99777843108973546310076149803711850216390102688256655995359800874570043056555), (83878517831334008537079994787751658186104835789618280423583097526657039236116, 103511299944003266439173166120956421458183958407018392943008279310148901530099), (52594410772860121402953141618705939118615173192654401872197358793802093515001, 83405724211182079540236196795249163629897595215932404038528725584752940112891), (33065844213457587899962903396905924355762651943441569081451445513507319530855, 84459733639665926869498081695782057380035530851686381235158073488183035616786), (92852131344469309458360217477923144206844568659427057865288421289109253101850, 107983952221059675122423299705365141729775323231590366324267237436140008945947), (96029923597418235178467955471356574309551942895748993166823415663148665366818, 44009545809587730664603276939770224891921201461689182875991144734130730148132), (14491509301756702536461113822340540580917882458515619656898399058847358427165, 49697262878580453821093137648994944864996947361941635057840345229346592103325), (7142334457994882719662437060979343972591452514665838139143484105280906359843, 115551291934769872032845156599846422261691630966595375293712684039045331609773), (76199441895199959275724182330257364704683013310299613213681996128885039748856, 61818592218490595235086300654053309843951970828080818853139158729491555260528), (109929676816214299202831373205057089272383846164015783800295478396646698467323, 85603015167410332963621281121877119398125218999394242687621353796693626604814), (42085095747394420012437156518121954367239135800432273121845002452192659516043, 99152489145483114144014322676393985173394178769761002353396529032837553322954), (46785837870376203194490078015227240349998784412414091973301490669202030071274, 50158820599587084300110311636192802928718158911039536915016098936406858562516), (2542408287329394787358496421330518153382875002992489916936545569680393263826, 90960446941858157396519547124374187601195250590035308278734642699690186774134), (71104981300440345730027322716187483726593985627650490829854057008302951470953, 33514784920149980284990693642981138878817995455645608482499592830700653956566), (2219892059755913648923157677311647289191116275916201596356192006714889434836, 88618328428853723603356473619982882118747874012454061529636978281392148038263), (97178746971516087889535720327071518678118751045576788550771262246668598290172, 109805470081585872699137219689787905302272845563258748145297268263743508487479), (115534988340017196814212470995899778229858109387047371649837573529558387904853, 73561296050053000878918947216300173621080314170028964145490299232785134490670), (71020415564613394809479505654058314877327019326561551804364004670235803702823, 63721115749327971913307535980809347713258942827871762375911063350230411291154), (103525157991421687186695127818409910674944424344157107349452655919519635026348, 32688475822302762091357434289719114377166781834307639574849691681988225039970), (5087645535251679155915786583389386699946293717913736425888766550834106777832, 39404753198204781082643593694294372610894075291929137737571839372499106216263), (46869233779509670367924828352772167995400504169134812168319240561141370079721, 10556762214950234444787499536590640061428436758010737349806108326319636463365), (97699454395659998727515199878750545107706971087247916527908427481361566291361, 102405817218001246838012518871118424034120058607873164728157421470161986209902)]
enc = [(64790039097843726619666409283242777555003893618465502278317178757450138780247, 102844883231790621570884937608458381278419605840318534308920025637869951920685), (65467005106282061101664483249093359627045329274101984251422509764159888516782, 29577274831610547096769142678647481089072852714288000323692708023231117856259), (71126810596268579329235558066839193156863450492831082744027778860379767646458, 10061110158348361585582673111744600909320452001919882022692480289045281568038), (68130211277586543741700239238753266861237930181769784115771631347659811533995, 62916875538459760084037730097955290681027631961337350448937045279643828518377), (40739841185675326976137753552659542076873069897376020788702703621548466410384, 95505667868305009079261482128316557710057532847302718993997202290022214506067), (18113528668110280401511533074417338843730161007004980298553405689312187829593, 54549787510067678331569900262990828737439364417965444112678791347445057986509), (65785972692053719083883036722006292317181610120596386229948182706617388553330, 26925186146344157810917265671643490784806237827525588744976777335589847243551), (52049982563010361166332130366254990594595414206544311311954755536493054807189, 49859379427158965363993305038648217602616149186457294969786353267658272232018)]

for i in range(42):
    A[i] = E(A[i])

for j in range(len(enc)):
    enc[j] = E(enc[j])

def gen_perms(i, mx):
    if i == mx-1:
        return {
            A[i]:'1',
            E(0):'0'
            }
    res = {}
    z = gen_perms(i+1,mx)
    for val,bitmask in z.items():
        res[val+A[i]] = '1'+bitmask
        res[val] = '0'+bitmask
    return res

maps1 = gen_perms(0,21)
maps2 = gen_perms(21,42)

pt = ''

for enc_pt in tqdm(enc):
    for val,bitmask in maps1.items():
        v2 = enc_pt - val 
        if v2 in maps2.keys():
            pt += bitmask 
            pt += maps2[v2]
            break

print(pt)
flag = long_to_bytes(int(pt, 2))
print(flag) # SSMCTF{jus+_MITM_pr0bab1y_eas1er_th4n_LLL}