TFC CTF 2024 - ROTATOR CUFFS

Description

Category: Cryptography

Are you ready to rotate your way to victory?

Author: hofill

Attachment:

• rotator-cuffs.zip

Overview

The goal of this challenge is to recover SECRET which appears in this expression:

\[sumyum = 2 \cdot x_1^2 - \text{SECRET} \cdot y_1^2 + 2 \cdot x_2^2 - \text{SECRET} \cdot y_2^2\]

$x_1, x_2$ are the coordinates of the vector $\vec{x}$ and $y_1, y_2$ are the coordinates of the vector $\vec{y}$.

We are provided with $sumyum$ and the vectors $\vec{x}$ and $\vec{y}$ but these vectors are rotated by an unknown angle, so their coordinates are not the same as the ones used to compute $sumyum$.

So our goal is to recover $\vec{x}$ and $\vec{y}$ knowing their rotated version $\vec{x_{rotated}}$ and $\vec{y_{rotated}}$ (maybe not?).

Solution

1. First approach: bruteforcing

Despite that the vectors $\vec{x}$ and $\vec{y}$ are being rotated many times, at the end it is only a rotation of angle $[0; 2 \pi]$.

So we can bruteforce all angle in this range until $2 \cdot x_1^2 - \text{SECRET} \cdot y_1^2 + 2 \cdot x_2^2 - \text{SECRET} \cdot y_2^2$ is equal to $sumyum$.

However, the precision used for $\vec{x}$ and $\vec{y}$ makes the brute-force method very hard but still possible.

2. Second approach: using math

If we look closer at the expression, we can clearly see the formula of the squared norm of $\vec{x}$ and $\vec{y}$:

\[sumyum = 2 \cdot x_1^2 - \text{SECRET} \cdot y_1^2 + 2 \cdot x_2^2 - \text{SECRET} \cdot y_2^2\] \[sumyum = 2 \cdot x_1^2 + 2 \cdot x_2^2 - \text{SECRET} \cdot y_1^2 - \text{SECRET} \cdot y_2^2\] \[sumyum = 2 \cdot (x_1^2 + \cdot x_2^2) - \text{SECRET} \cdot (y_1^2 + y_2^2)\] \[sumyum = 2 \cdot \Vert\vec{x}\Vert^{2} - \text{SECRET} \cdot \Vert\vec{y}\Vert^{2}\]

However rotating a vector doesn’t modify its norm (“length”), so we can simply use $\vec{x_{rotated}}$ and $\vec{y_{rotated}}$ to recover SECRET:

\[SECRET = \frac{sumyum - 2 \cdot \Vert\vec{x_{rotated}}\Vert^{2}}{-\Vert\vec{y_{rotated}}\Vert^{2}}\]

Solve script:

from sage import *
from Crypto.Util.number import *

sumyum = -142226769181911294109604985414279966698269380324397182385943224688881786967396493297107323123238846393606215646973028804858833605857511769169835160302020010947120438688346678912969985151307036771093126928042899151991372646137181873186360733201445140152322209451057973604096364822332301687504248777277418181289153882723092865473163310211285730079965167100462695990655758205214602292622245102893445811728006653275203674798325843446182682402905466862314043187136542260285271179956030761086907321077282094937573562503816663264662117783270594824413962461600402415572179393223815743833171899844403295401923754406401502029098878225426758204788
resulting_x = (3.3634809129087361339072596725006530600959848462815297766832600914180365498172745779530909095267862889993244875375870115862675521807203899602656875152466204714275847395081849947663071267678766620524700684572851632968584152642766533856599351512856580709762480161587856072790441655306539706390277559619708164477066112096159734609814163507781608041425939822535707080207842507025990454423454350866271037975269822168384397403714076341093853588894719723841956801405249658560486108807190027518922407932998209533025998785987344569930974892824749931597842343369782141668038797305601028366704322107431479213165353278773002704707347001056980736352878716736155054293350509670339144379602697176068785416128203382284653052813910539052285224499161723972390574800570738938264516350981139157860135237512937090793549860152173756751719627025142858529263243314917653507237003568510016357713402278753999645732592631577726849749929789275649985363293274521704758513276997442425705172979362522303209937874019044195572717894784790824040985970678829869212168596332338e228, 4.3493076236586169242233212405270398931813271488805260703904730395387317512159124699671617536806847379014763743850012966440449858042327139796085868934120939346500622666309663813415016921760622643752056516232426324399548704613192843351795229042500735885925583510203795565452553753954474949980588780332651769544235511465216034600990329267883327087177217125655503845919331440817328958054102807738186874040636118222352351053320953917165679774298608790659071127811941909136888169274293065733698380573486079052876249484455409206182001827225690775874445171478338344209529207109172368590360722150559332665968826925103060717742483611155201852629766859356827518117986215929527812137774656124580645282319815982553388185475874607903050755710964732279490338614504903256117014312989278124177060468718045944298976827788272885547066724342578660563396148909159051946415261351324693896674313199869788279492452177771905587881622085592044441472137286330359635594402564357596784568377870545793505212074411425362120275312322293627143588322908897500139505746513232e228)
resulting_y = (3.0086123485184949854819528432444522887263618452152977201477700454454717599185922285792607291484161348863603668674724666302028473336653202339259214779198337146709052083562504123644969759313504022148939497579033947489964578987257010705347661159352495880621564046451129149321751369899157697461990748527068553919767557375414807745137776378672423131583632676118768803623661016450513713378889178790819115525404124475586398119768281556573742250499881136366816528002891506377591473809774876327335425713426558761290418087432306668623923825516541279687269109753438014462223886767964900168026643719447209474190574704192551865457553267219179816090151816092471203713238427208397671093453024024773606469951052196613699816481289760243547361942029869165939022611782658000517871759272476768999453412473058498224382162775678590320117678687959374599497850317809926761224934950410879753727042047871292717229649696383856159211062622325024918849176324424823611459590717866478574927162324917352318674258311617781845396479605897293293787546058229588461669469113001e228, 4.1955438730064492244518395125687091233417321001179084616477593364143186962035096742717340249485256810878365124925979444527539802357032735868877910266504910589105346718553503670072791148806000734099122372428956062737130602189826489676949800396857262364104813055382317498461363421406914514918460816121876800728600531432610837129788010503804927836206596876591613685011706833895602299866191433190745884295362337967940063679204541643670409168084686978205876941245671248753306754892761206974604980311577415661960800437927228624982030061751022139301406066860249918396002252864930009083759551916555623475795108943840654272107400479044754688171126386094896825019962082090350188892677712358612478027143147182776057102433244569971150928964257290752485837202929975257858813456753394801152212850446322739077604336730800210171231609831225616780923301071587159265696870229784689201181607735865814975046649574472138172333744474559659785291954987787639082881571990180182337133038177924408020273887276582566592470019342076814034084107444178243083855840959209e228)

F = RealField(3456)
x = vector(F, resulting_x)
y = vector(F, resulting_y)

SECRET = (sumyum - (2*x.norm()**2).round()) / (-y.norm()**2).round()
long_to_bytes(int(SECRET))

Flag: TFCCTF{r0t4t3_and__g0_furth3r...s4me_th1ng...schr0d1ng3r's_r0tat1on...not}