---
# System prepended metadata

title: PicoCTF - Sequences
tags: [PicoCTF, Crypto, CTF]

---

# PicoCTF - Sequences
## Source code
:::spoiler Source Code
```python=
import math
import hashlib
import sys
from tqdm import tqdm
import functools

ITERS = int(2e7)
VERIF_KEY = "96cc5f3b460732b442814fd33cf8537c"
ENCRYPTED_FLAG = bytes.fromhex("42cbbce1487b443de1acf4834baed794f4bbd0dfe2d6046e248ff7962b")

# This will overflow the stack, it will need to be significantly optimized in order to get the answer :)
@functools.cache
def m_func(i):
    if i == 0: return 1
    if i == 1: return 2
    if i == 2: return 3
    if i == 3: return 4

    return 55692*m_func(i-4) - 9549*m_func(i-3) + 301*m_func(i-2) + 21*m_func(i-1)


# Decrypt the flag
def decrypt_flag(sol):
    sol = sol % (10**10000)
    sol = str(sol)
    sol_md5 = hashlib.md5(sol.encode()).hexdigest()

    if sol_md5 != VERIF_KEY:
        print("Incorrect solution")
        sys.exit(1)

    key = hashlib.sha256(sol.encode()).digest()
    flag = bytearray([char ^ key[i] for i, char in enumerate(ENCRYPTED_FLAG)]).decode()

    print(flag)

if __name__ == "__main__":
    sol = m_func(ITERS)
    decrypt_flag(sol)

```
:::
## Recon
這一題真的很詭異，具體也是看[^pico-crypto-sequences-wp-almond-force]的影片才知道一些工具可以解這種問題，首先題目的寫法會讓stack overflow，因為不斷往下recursion的結果就是記憶體爆掉，所以要做的事情就是要優化這個方程式
1. 直接用WolframAlpha這個強大的線上搜尋引擎，雖然是搜尋引擎但本身也可以解決數學的問題，直接打入:
`g(0)=1, g(1)=2, g(2)=3, g(3)=4, g(i)=55692*g(i-4) - 9549*g(i-3) + 301*g(i-2) + 21*g(i-1)`
就可以顯示最後優化的結果為
$$
g(i)={{1612({-21})^i+30685\times 2^{2i+5}\times 3^i -1082829\times 13^i+8349\times 17^{i+1}} \over 42636}
$$
![](https://hackmd.io/_uploads/Hy6P0gvxT.png)
2. 有了優化後的方程式，就可以再次利用wolframalpha的解`i=20000000`的問題，直接打:
`(1612 (-21)^20000000 + 30685 2^(5 + 2 20000000) 3^20000000 - 1082829 13^20000000 + 8349 17^(1 + 20000000))/42636 mod 10^10000`
因為看source code: `24`的地方最後會mod 10\*\*10000，所以直接加在後面就不用再多算一次
3. 在result的地方會有more digit的button，一直按到所有digit都出來為止，然後就可以利用browser的inspector把所有digits尻出來
![](https://hackmd.io/_uploads/r1ITxbPga.png)
    :::spoiler Whole Key
    ```bash!
    9255992309255409483179419845385604076174038906804435862147131271801573863364671050296589603656758794258408363769683958014335858678927280224225587045835554549236411759910608220745411090061107428308955685273979287406544038776309083120692585385738829595466109925134108641705991448085508655504450017990509268760925633701568972881830027061610560435878782702300627297929494871966955716917939371706707268015616593308156496696604916581937050769400369329646318242403439293960972797326591961508734072823394003350315417131956614413828716990680272404638311428692240287388862893111312382911200690775170712470656181173871770843346165473902020842788371815280837350600345873274612288695974628974447382548367670699187634577856102734888566085413732796006178277409299011898018586005894168842976151756634127393139021619117795598661633051521271539523878676739785948001294884571789689490927900913683983739549130273396058399143226419007679327244720322508238328094638668628927305146465933124499123166025607367183896479143811606663266607998143104781472932536517962870064142946144625397409118482948529375842470080996308940228181555868856278635118907503183008759948969042642499296992802929823117992152968592210773980077617609073992433539666043450153737078290684650605359729295102951770694711461980246093793230726069510952832108390343839058578187834443332785573981574093142883050492227667587060213520259865514144542328249027296100425783797607012578290271918793953435463360127600336995858457256850614392061752272722254154308105713290184809674001961254146687993990619053173026936872310492713720330275500652722252195618029796316172978100805935132221268612041959579928042577530526820419119584535052685904447261275310418413248686956899719552564514439618702687638343849484513674694171734435213591420260740566479490794343621991808171166760491608939159807834320688115459926363623951639944589028697445192690646124728566256342389792435969804521066155975776703867010670866905226643086877863465230710100595718033849129799770334210438392357318197622026595775013560170000581836767441557468287425384470655606044094877141189131911510528837751403182546932730981726862216771989383509234877567054461236826949390614566495105022255382856931991575044242339913426032792306478049565359457186829132169808003222243325028652626310095161166749383960092203262812957052229181656830263059054012215047216588117847290728018790343673230003332953508551258024784915192282602155534492742678877926631791253048827739564711644506014349266360429184321481406973201467494658627340758651248713537093402837529826098026053980059834955577271342991416289835227752675490374970512450046682049106507080363044373334490863015296351867206843957520897668462624524697408794293584230426162185084180656752348354284781732407856125955024240750800619775537915436516642312543485650255028594050775824329726464411065155974834914382223375359322586073472902099799870968399129353093933551117138823131500391523207862454881095643216836059114056185567621210349969346322773001970523136569586467928553922556759816995780147911338014075002398099900406865475250060061466196595711092783115852233928711362221294428465110008730032376221811390098890201357718636406741505189198093628817125780661479980043085639258408363072938360753891009465462833335469632467626044690421375033291457334660505739506576025799178496006189196177956994530824690940218609585303782913911708447438142187182926981478894626795456902176806611295290700707265838620112296859471410916725995917774332274290788363516703126067525815657749686032894240952885372190041514195745517242466094437249645852862039820489243179115296739411857999937345382824004834661340869046052653646306780119433815387152755133605774561035882025757872567705036320478601722273548057596707229169819752947743173434922514692459604659989254924691025826519889997310022991556840695569039726702142704241050410911435207616994113021032464407922133128294008095361971182034734357545845729036366311342093217648851382217300855617348105944416959797800045679106051418970936740212201243323374420621407825691038198850295142424362386735016850455273108385213347814948477424622972677362919476397615254720546530031804494636576667039213835518167079053755689483780169794708659175854750079429248450088295652150342673865847877948007025066365086867044327664549023605585607043999489198176552411509573614509346696314655265681005379692562018978024392184039921374721689942446250899039972858579928731641819612416834076914289563149490277258128048991899111474196559739496407766224802408886023880978692457886403296980175876160991944550852846912763591834524913193729446086608083228520607915228071996267423308343063134888427907517509315007222472389958749971119851036755792600655325528041204067006759701899650882688051833189752046173730379687971618778106152429359138121583193895560513945636243134471509560159959342910138282307726776095970363559666437861045509504138185181506053793512330290527298473960426572845110238171117683684041364809195193134404789631117855182678689233515561942021072691997136439472830027014623367190862026964245957075271549021475940633067620735535147002394377565757136258368893655670057033255721591133344504950327269570084772598756931676545313429328183852664697498916280009082153424970243321291245567462087352044270433243592074410354599395985297648098973502854925696106939367723393764563272258573159869455233248604794095580403785375164969409403081664991958224758441901558161776076591761888047641751838451040113125346830296747468600274844343324792391841427920168269451466724402733360927693709608962574594464579536984204944785654570365966337092840214689194020777824352704334046313881288338804180775802282603846332149028417773288289252762349196418160264959236996771411726564554602445482384874934737046588338703536104981717946192703044019694658564450098648845491774640036585262302060685132707254404537015003307098121867501852580890489939024131889401235319636551040339975967238422740240966259515037478254770473708996730051186960847990806128716407679744434499599989634137262723021472296892338440434736145378291606947957568823870560743760517351104324171646786563571781160467327443314778456838020015351241446028925489659469259191936419394977586960658145019513424973791091137643248921605946312129559765684939065366382416571402819258368193526542981160896431303284342924396162774222454806500316599596574249681068946095848501619763049813933785364480427016321396723833776401301274077949645225141713635020427987198026380348105434595680144888649570836956452691173177645938260028423349017079649855941675840603611580622678506371371697560589581420055017577346354260361897276945627730859540343204410331899938007511401885662258331200755215828320367067692873598022854726551625019874259353828693391050015840864024895999795407357598143936695574892246307842161783795560397647511274081780556477771717482679637977149078124055360544607647924994542360536953444119017948371483912417341760402319880478433679698847402873629477418088386984882884367030602730629280761454042804309591833135472741106210177450590122900331916392690960166575957302364880258370864660313841070468917976423612480270717152957780709455158756388635972782046126933529379819689066556155764477143246285455968257184500627209798685519518396787028389456612015798784443980456558550117443763642092453428667889633895366126970127595278029054151815294466903598493508152766946482827975630302463357183665021121093456732176958408682571069411703078859156168396080558652545622296864811704928778418723691428995865934077090633785666707553168035257181052413086259223364488253377812633572773449366795144005798862081976863438611157642682042555702811274364249588365217230773276938197025251263204920250274561918739940317025820821943112146326658971603405997249518942370887739428430647434654176831358048833125278711592425215074394781203447864697270631159656012070957627193840233040056721098784067686855982514452154301379396013592845015085700333286408687000310352955163502073542407384258224528062051710025286474577927921058848236668349074255824260841594925768567573318340711331715155787289165246585583291819252627720144687822781808529370613377586610735928178283327207791931897883424633325083583001975227016830407188727609132036632946234419301131666389964830321414921172514131959586030586931111249491498106713817311838283034349524325163097453961907669495483388300826404610851466022463454212313603637565042757263073095191351465395578859789289286623320311957329723105215118350211185629815472005840341390060401666302409887985194198907321230384356718336469944222033952614808736700826052596589783073153308736029332962140644960168255815809288477363038352552111837655071019625450260503418732701804784747182324638570871601380717550522471539631880754137751840248666247067558719456661594013155374353565787812302603454241932587478074531723845881852522899875520108223989565161816290836725233062170653322013442338668982907977623671041502866086951618008336554936548381992485724315445742522418652645366236207797254801446299025033667397474972659524455906539862842231515555042136670038247248897838354864879530283890881209788864080366922898130228485869246412234498989357579422587192729993196385899640805525931849963321047376078696409505210382363852446788333692920589280728231042105259768204967935237630730947289546176237344157978687526209734663065396354369435887509555819496761529612670892267592613261368154786970843333205497696978891361396207152144495001501963211406214283549677114836227070689864106611003794440829922052585114742533372193737747468840053514452728905654108384095706621378519493931924415799771055333810098449370026530525687192051298576502186041804793590285571178492574358690394687483560097079894226196628064591511497281471180947997153327377330473027002482264767742036860570511304613104070588191520523721602975179515534689251675096747888297896189014738139384973413497771956407580089944032595700454254757322594723644055223823257936218414738084433738393480670154822354418285633492955295404766761380204585025501914177392046923017909349445763892709995098736896765635526774603125001
    ```
    :::
## Exploit - WolframAlpha
```python=
import sys
import hashlib
sys.set_int_max_str_digits(0)

VERIF_KEY = "96cc5f3b460732b442814fd33cf8537c"
ENCRYPTED_FLAG = bytes.fromhex("42cbbce1487b443de1acf4834baed794f4bbd0dfe2d6046e248ff7962b")

def decrypt_flag(sol):
    sol_md5 = hashlib.md5(sol.encode()).hexdigest()

    if sol_md5 != VERIF_KEY:
        print("Incorrect solution")
        sys.exit(1)

    key = hashlib.sha256(sol.encode()).digest()
    flag = bytearray([char ^ key[i] for i, char in enumerate(ENCRYPTED_FLAG)]).decode()

    print(flag)


key = open('./PicoCTF/Crypto/Sequences/key.txt', 'r').read()

decrypt_flag(key)
```
## Reference
[^pico-crypto-sequences-wp-almond-force]:[ picoGym (picoCTF) Exercise: Sequences ](https://youtu.be/ipWfZe-i5g8?si=Oa1br3N4vWxSsnHH)