Angstrom CTF 2022

May 05, 2022 2210 words 11 minutes

Contents

https://i.imgur.com/1OlmrMC.png — AngstromCTF 2022

On this CTF, I managed to solve only one problem as I don’t have much time to work on it. Here’s my writeup for that problem.

Crypto

Prophet

Initial Analysis

We were given a source code like below

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


package main

import (
    "encoding/binary"
    "fmt"
    "math/rand"
)

func main() {
    flag := "actf{REDACTEDREDACTEDREDACTED!!}"
    rand.Seed(12345) // the actual seed is not 12345
    // drastically slow down naive brute force
    for i := 0; i < 100000; i += 1 {
        rand.Uint64()
    }
    for i := 0; i < 4; i += 1 {
        fmt.Printf("flag chunk: %d\n", binary.LittleEndian.Uint64([]byte(flag)[i*8:i*8+8])^rand.Uint64())
    }
    gap := 0
    for i := 0; i < 607; i += 1 {
        fmt.Println(rand.Uint64())
        for j := 0; j < gap; j += 1 {
            rand.Uint64()
        }
        gap = (gap + 1) % 13
    }
}

Skimming through the code, what this code do is basically:

Call rand.Uint64() for 100000 times
Call rand.Uint64() for 4 times. Each value will be xored with the flag chunk
Print value of the rand.Uint64() for 607 times, but there will be a gap between each print (So we don’t get the full complete sequence of it).

Attack Plan

Seems like we need to attack the golang math/rand PRNG. So, we need to dive into the math/rand source code first to see how golang implements it. Below is the relevant source code: go/rand.go

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52


// A Source represents a source of uniformly-distributed
// pseudo-random int64 values in the range [0, 1<<63).
type Source interface {
	Int63() int64
	Seed(seed int64)
}

// A Source64 is a Source that can also generate
// uniformly-distributed pseudo-random uint64 values in
// the range [0, 1<<64) directly.
// If a Rand r's underlying Source s implements Source64,
// then r.Uint64 returns the result of one call to s.Uint64
// instead of making two calls to s.Int63.
type Source64 interface {
	Source
	Uint64() uint64
}

// A Rand is a source of random numbers.
type Rand struct {
	src Source
	s64 Source64 // non-nil if src is source64

	// readVal contains remainder of 63-bit integer used for bytes
	// generation during most recent Read call.
	// It is saved so next Read call can start where the previous
	// one finished.
	readVal int64
	// readPos indicates the number of low-order bytes of readVal
	// that are still valid.
	readPos int8
}

// Seed uses the provided seed value to initialize the generator to a deterministic state.
// Seed should not be called concurrently with any other Rand method.
func (r *Rand) Seed(seed int64) {
	if lk, ok := r.src.(*lockedSource); ok {
		lk.seedPos(seed, &r.readPos)
		return
	}

	r.src.Seed(seed)
	r.readPos = 0
}

// Uint64 returns a pseudo-random 64-bit value as a uint64.
func (r *Rand) Uint64() uint64 {
	if r.s64 != nil {
		return r.s64.Uint64()
	}
	return uint64(r.Int63())>>31 | uint64(r.Int63())<<32
}

And below is the rngSource which implements Source interface go/rng.go

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59


const (
	rngLen   = 607
	rngTap   = 273
	rngMax   = 1 << 63
	rngMask  = rngMax - 1
	int32max = (1 << 31) - 1
)

type rngSource struct {
	tap  int           // index into vec
	feed int           // index into vec
	vec  [rngLen]int64 // current feedback register
}

// Seed uses the provided seed value to initialize the generator to a deterministic state.
func (rng *rngSource) Seed(seed int64) {
	rng.tap = 0
	rng.feed = rngLen - rngTap

	seed = seed % int32max
	if seed < 0 {
		seed += int32max
	}
	if seed == 0 {
		seed = 89482311
	}

	x := int32(seed)
	for i := -20; i < rngLen; i++ {
		x = seedrand(x)
		if i >= 0 {
			var u int64
			u = int64(x) << 40
			x = seedrand(x)
			u ^= int64(x) << 20
			x = seedrand(x)
			u ^= int64(x)
			u ^= rngCooked[i]
			rng.vec[i] = u
		}
	}
}

// Uint64 returns a non-negative pseudo-random 64-bit integer as an uint64.
func (rng *rngSource) Uint64() uint64 {
	rng.tap--
	if rng.tap < 0 {
		rng.tap += rngLen
	}

	rng.feed--
	if rng.feed < 0 {
		rng.feed += rngLen
	}

	x := rng.vec[rng.feed] + rng.vec[rng.tap]
	rng.vec[rng.feed] = x
	return uint64(x)
}

So, basically, the way golang RNG works are:

Seed will determine the initial value of vec
Set the initial value of tap and feed (tap=0, feed=rngLen-rngTap=334)
To generate a random number, it will:
- Decrement tap by 1
- Decrement feed by 1
- Calculate x = (vec[feed]+vec[tap]) % 2**64
- Set vec[feed] = x
- Return vec[feed]

Notes that the tap and feed is circular, so it will point to the vec last element if it got decremented when point to the vec first element.

So basically, the way it generated a random number is through linear equations. Now notice this given code on the problem.

1
2
3
4
5
6
7
8


    gap := 0
    for i := 0; i < 607; i += 1 {
        fmt.Println(rand.Uint64())
        for j := 0; j < gap; j += 1 {
            rand.Uint64()
        }
        gap = (gap + 1) % 13
    }

The given problem gave us some leaked of the generated random value, but it has a gap, so we don’t know the full sequence numbers of it. But, the plan is, from the given sequences, we must need to somehow reconstruct the vec internal state.

Solution

Now, let see the given code

1
2
3
4
5
6
7
8
9


    flag := "actf{REDACTEDREDACTEDREDACTED!!}"
    rand.Seed(12345) // the actual seed is not 12345
    // drastically slow down naive brute force
    for i := 0; i < 100000; i += 1 {
        rand.Uint64()
    }
    for i := 0; i < 4; i += 1 {
        fmt.Printf("flag chunk: %d\n", binary.LittleEndian.Uint64([]byte(flag)[i*8:i*8+8])^rand.Uint64())
    }

Actually, we can ignore the 100000 loops because we don’t need that at all. What we need is only the internal state just before the call rand.Uint64() during xoring the flag chunk, so we don’t care the internal state of vec before 100000 calls.

From observation, it is just linear equations, and it seems like even though what we got is only partial sequences, I think it shold be enough to recover needed internal states to generate the random number those are xored with the flag chunks.

Because I’m too lazy, well let’s simply try to solve it with the help of z3 😃. Turn out, z3 is only able to find some internal states of the vec, but this is enough to generate the 4 random values those are xored with the flag chunks.

Below is the full solver script

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89


from Crypto.Util.number import *
from z3 import *

leaked = [1967981989159506896, 12417576839900903143, 5391827788107581754, 9211837354618349619, 11911979448172444251, 436461377053033951, 8394439408169944148, 9103763829763273513, 7101121394772592963, 18180164424805091773, 10980218005670728650, 3592195252851566282, 15982088259081365278, 18366993356901645139, 16470043187318505301, 12529639613890366320, 5405453295559550962, 3219566894479483465, 16987169033331910230, 9344236955639961560, 3745615208872438517, 3388187019357417407, 17198114806622348859, 9334174653951229381, 1009948000446937143, 14650385610612467309, 14912852548935159537, 8230750145803377492, 13210874570097825431, 4261899336407377866, 2573134042538913249, 10562921983129619234, 4481733723106553150, 6693876041704064709, 13772536884257081061, 4814655535784567940, 17117043381738664412, 10014777550587990992, 7013436321029132294, 953436847296933558, 13864297711807309149, 11312345922389074726, 2199867878612078091, 8402220611296899976, 10378165238796511161, 16078363467890630054, 7098501269083835059, 1681679444219081187, 17235013401211119472, 2203917752371077442, 9217070900827478302, 10058277698897632667, 15972660907870375806, 6622838346930090221, 12586537260105593109, 6433719167686925168, 3032065173778278418, 9743104590135308267, 7391368162387036788, 10725912781903875779, 9846554056484719855, 12343982921622455581, 36206366241642941, 11813694384750487006, 5494944593056217372, 17617075954936948791, 15958686524489577932, 11727447540781267578, 13380151820153190493, 9349098470649357156, 13803047902546235975, 17286479261703485395, 14722281154768715543, 12612473994461271801, 14312822945784769203, 15609063854644643395, 14708036210562969600, 13796313732450064136, 10307023727568972101, 17513680648877824019, 16702438782110391465, 3652001414219721007, 5265625636739631457, 10654632704447374504, 7511078814006349210, 9140982706528528010, 16223838721279393322, 10420524606533750516, 16701377323767306114, 3750804369080437426, 1274885552917066026, 4230518916834636384, 6690624599507792675, 15478451784117638719, 13534840562459518131, 12163976775461276142, 9476524941230848424, 1443362190438042863, 1456911544696158525, 13438749309336286137, 13766436007254005985, 8432370224361500748, 3203865476118736526, 4420206307832455609, 10496653657337759511, 2775211754574419515, 16696355141624962972, 16768338839510607900, 10202318454385533892, 12554418635459033218, 1708421080877496043, 11341735535211029325, 13622421994908208944, 16469847339176897411, 10935449642259488944, 5989762449076810195, 16678533334885732063, 9391936203669602898, 15958497913540135719, 15152164795107255721, 17424538298476802068, 13476846617758916522, 15469288240231942444, 1042058457773191313, 1437682614378048888, 7791872198157832698, 3337812416348112405, 1784790255299050697, 17002639445141763699, 12767980465486129482, 17612162068890083773, 16407551756979473145, 6870903950833453651, 15216520006678599318, 11037528050111055664, 8264794268732416280, 17709510308375523833, 10870329587473006478, 4209076136454212823, 10311372832283085221, 16154509542645742462, 951684807689880439, 2739768274435630200, 15514988817801737887, 11903497272094080274, 14010700631489000318, 8168148822285776139, 15256711994087827473, 6451657483371937183, 7135447898628744494, 5780088181865624760, 6989372305949144334, 16143055753880844914, 17070871628364636997, 17845325327638564426, 11252650532709168300, 8689336205199825409, 7434630126551769888, 14509873386914702491, 11590268219228522253, 6198329276216609561, 11335367112307160031, 6862703832858865940, 16095983259296342520, 4053164335011250682, 17746859978905550439, 11203484631061948861, 13068966305827836785, 17576153053645041814, 3397744133652191854, 14210396404767979432, 832520310222841641, 12993614654248441024, 5971850475856808185, 238574801556615180, 3266474603761581602, 2034926208326210458, 7959880505534650249, 5223282126385860453, 9023127018974238669, 3769567776153636493, 16447344062257806832, 11594390737828822413, 12960041364170007231, 14328319423697083505, 3160154057912510660, 4359044101862451509, 1771349416916391552, 10701387249528119333, 7454181388372329852, 10193237782067880860, 11409283486710807834, 13931727607061863648, 12942968879660231478, 15645948770775587825, 12213288520365533176, 13988040192872290430, 4199713191956978186, 6765946140427179581, 18149742629467781128, 9358470377774505826, 4181580646934571736, 11761756415525998340, 10042926784088060877, 5067835985447795792, 18300732716144522639, 14306304517937131978, 16719268577219265090, 8638464310536291519, 15672756635128514803, 10996148629154702020, 2338742778696722106, 6118424250314589408, 3576387217904727585, 16396068811351621328, 15697480172561236031, 6515775876966862332, 6608472476658256484, 6011737076705937171, 11602240412095671278, 4887262940815095667, 1728593519225716985, 12925038171302350851, 90888454155540380, 7369230194366723483, 7317136921293836973, 12082722249199476773, 971754854524357986, 6642730636302083314, 11144922589757761299, 9598715342896599540, 2922994873083091744, 7854873715768913334, 6670726563807133294, 8086257198858594819, 6212636838339361432, 8107140509430732926, 13755318446376323915, 5167544324749873523, 7054782057945799124, 1526161334406003779, 4255211424472345138, 9441508038017073687, 4389728361916511863, 6644677021040028381, 2254482152083342988, 6435168706358440261, 13693189497937442312, 10885862492982242128, 7849235561927071598, 6391907113707972788, 14828962073252161086, 2876503123100726408, 10885090941428747169, 5338465317393070206, 1137998109085147501, 6090513144357782932, 11819986903687603314, 12881756187512916604, 1976632829063897381, 17359004626847963595, 13766469682650618030, 14767869774356980798, 15329110699901373732, 14457512632645866752, 17306004375585337226, 5155218838341812711, 6331009131442304780, 14914490365911397792, 5484660559942057989, 8403773674380751349, 9057552016854155792, 5663579537065523519, 12733199451408301190, 2475413419854628033, 3060568102591068186, 5501812154734653159, 5346651138403433319, 17321470947055342, 3024691803881787448, 9578227694185769148, 3937732843967753549, 11576647145248770725, 12502558906956667465, 16140681523595189504, 403532231898314336, 9375862167444011146, 14762566527264320944, 12917429116215508760, 16434833897796033665, 5883358706972236206, 7944339108548522200, 16083241360387240578, 15000988351122298376, 15444302627022279479, 9605058712130171968, 2386147020831105373, 11034594787498161455, 7802886467027138095, 1350348277231420649, 16437772745511742326, 16369087367283592028, 3398142503158684448, 4054500637066219363, 5467732778534042094, 6077068069353599623, 15307440136630175772, 8069986704297517454, 16125439950077907217, 12770442876499254350, 4937869616514010993, 8632605460419517226, 6932674954712492885, 302286771578914423, 4343274388536329381, 16646734744492414458, 5139470350573425351, 9616036813843654882, 17399179731673970573, 7559528504137334194, 11792606559736666883, 1931507146899857039, 5138370435813932146, 4682773184333805937, 10015207433908529921, 9158749731870430634, 8026456545492596810, 12220799030369774434, 7429597862103555736, 11738648338629309695, 12334067470465034063, 5385763743086178029, 5154059608961020935, 17698784779105622467, 3770879550769068934, 13227750224933879492, 12331717833041804921, 12687283598432761553, 10198512429289087736, 12799227013745144224, 523893901052610925, 4536140612243831949, 152612941811494342, 11558245922891825026, 10283332526363148674, 15838544722789069949, 2504998818100882442, 6611156300324888802, 7688416891303398949, 6227734655341631822, 10820712144602739488, 15295866970180183410, 3923775810346856986, 991517840166328938, 13114481036694260634, 17049900349182653424, 15100697373785712871, 17231054948403101577, 1635904888551988210, 2403414502881271059, 10367682491889175581, 951809985567679985, 47190420647530861, 6193844265048354679, 8067214936989577532, 1174186205004829237, 15972266219068792232, 11367330706071309285, 1656166667934101515, 5463970542004253172, 15428201938850621155, 14981375974377338893, 15392722228991260355, 5055774487388236697, 13771878092723980305, 14908149214778130335, 4458186772455489664, 1621667363915125240, 12242768691020426622, 16738845235660713409, 1533699165556559812, 4587476094298035934, 2716560561312445378, 9779924594083073649, 16491677495012511194, 13539593605599043897, 15618178338061388078, 10785520677372826562, 17564186308887261427, 1131615290806612735, 2531759660122767543, 12505298531338987879, 492474029227676482, 2737723667282226472, 5979715854853815329, 12779393250154068472, 15295134981686930526, 3507166897496589599, 7341284119395282052, 99949099216076235, 664459355355827092, 5673557022786916384, 4062280886680509198, 3753143692796227591, 9720744323602756112, 15852739373484525101, 4713193192098424552, 11823808585405534972, 7395477688904110211, 3353869124291586677, 17557000440802126351, 1628751339615514676, 499401432804547034, 17373987220646173978, 850336189753160398, 7881956685885300504, 14932489532829173746, 5010989908827863313, 2585509541810523167, 785739870952630663, 11524762024341349167, 6487440112081514312, 12419979263166138897, 14975831105848915410, 7424567364931297202, 15864065278641652233, 18241514788379522028, 7585943313151271840, 10777535152767413064, 225352719270554060, 10997854994497947340, 10272524832164367390, 5242722485383108914, 9323186992411810505, 943805476769405658, 13051010949973843988, 2650605602224782842, 13569018774736913874, 17203657932538731512, 1625197206395123841, 15377572960789566178, 9301532123636801844, 14760470123965786633, 8367033491696096616, 10541048689330497316, 7116607694979695611, 8656306571304113443, 17763160180793285792, 5558652331691804532, 5275697913309919881, 1675941760263045537, 4674605593929983262, 16295648997945326650, 1442185522994780593, 11230035595522639358, 3175022609628443847, 3317179187532987473, 13378403612152884546, 16178462099943891018, 18255894057637720718, 11543214599469751009, 839348084968491956, 15890683711376892834, 3885972505999875921, 9710873193668078772, 1300519432012927879, 5463740936865881094, 14286731208206815520, 18077789592312997300, 8039909510360026888, 1233795886259778003, 335572017272601195, 5975457390139226395, 16561983814830793736, 554015178009661516, 8141418930723554, 12686461009914623685, 1712011832860339914, 11174036971166107003, 7881429032376172567, 3292235123280856452, 8909172722044512468, 17288391302220119350, 15168447606498070850, 14457891814374977663, 6816220750672664043, 17863109280009362027, 9146329203831295, 12329913431311522245, 7349498783049961921, 12250629111452342067, 3891765578451892606, 17576068641665712874, 1848431952530289179, 3000454474338203842, 15247593725994393921, 16573318812369844409, 17807213439559405694, 1889379107953427725, 12042616032274298043, 17557428588942076181, 15253873143659821984, 4736308695753036319, 13050293414344546051, 15674547191274178435, 1666469461345144225, 6669247726270200121, 1787839338823175048, 17324651576862668835, 15370644847914142756, 7760139382203898397, 12392979245409850870, 13979305019762894353, 9564748253335071593, 6645122352072304485, 1825660249356343909, 17688170642718706735, 12202049781628487753, 3508826209444940930, 18086605743722408026, 13565810346354754908, 16950334234603684677, 9403715093755418423, 9580166515402339921, 13334267048245247352, 16620023138838541923, 4729304793048586313, 766813325456740861, 4280327670129976483, 2313322226619393660, 13956914145403286335, 3371111601902487671, 12421037663463004669, 13392560939925046553, 16641944828201280615, 16230339472638516764, 1036411126112899615, 5784231465751852965, 16717221626204281305, 14505329184100083633, 12718491686522986967, 6178494218747816912, 13747900580296447665, 1295719700844734181, 17751263004647575848, 7951434078512558856, 8450121669017454567, 11334455214030781095, 4915738691082134560, 11646111888203774318, 4492674189854122445, 5243434139721421509, 15989052481195537838, 2044543755996076625, 7289401186222225003, 9774957470550651866, 15039586876738796477, 9359371168565703229, 6136604659038796164, 8206024178592261742, 8703210566078213246, 10083020087511115396, 3819883451607411990, 4901503900799540431, 18332034971698881837, 1633299431052025396, 16785686797835701210, 12161756702506149050, 4730594470653837285, 4328499025625952708, 13020700501141530049, 11786400644664054959, 17949844595708384380, 14432907448866140440, 18079002962639073070, 8385909909162861536, 9631903929008173624, 10521106663947071756, 12085621303188816726, 14983599073748502003, 5307818786703978170, 16481433912306567164, 17611012155395367736, 5249288808613375214, 10937751337369966951, 13984714090355081924, 17674814227444345918, 1039466783262400588, 16382420583956810637, 3776588883106511897, 18293727554065967560, 8536871507858159695, 3364069778379681390, 8955870647567369228, 12554204225953208702, 10856968400226224975, 2494859052506628689, 5574467717088748989, 10208855288783468268, 2745532725932792793, 13779513989779142756, 5645543700963755899, 7803574006104008947, 17573461540708036956, 6574608239417173062, 15788008303691725659, 15670582911951089980]

flag_chunks = []
flag_chunks.append(4301770859063564088)
flag_chunks.append(3588343789060400015)
flag_chunks.append(16743982520636489794)
flag_chunks.append(14486217089676259227)

rngLen   = 607
rngTap   = 273

initial_vec = []
for i in range(rngLen):
    initial_vec.append(BitVec("x"+str(i), 64))

class RNG:
    def __init__(self, init_val):
        self.vec = init_val
        self.tap = 0
        self.feed = rngLen - rngTap

    def next(self):
        self.tap -= 1
        if self.tap < 0:
            self.tap = rngLen - 1
        self.feed -= 1
        if self.feed < 0:
            self.feed = rngLen - 1
        self.vec[self.feed] = (self.vec[self.feed] + self.vec[self.tap]) % (2**64)
        return self.vec[self.feed]

    def init_feed_tap(self):
        self.tap -= 1
        if self.tap < 0:
            self.tap = rngLen - 1
        self.feed -= 1
        if self.feed < 0:
            self.feed = rngLen - 1

s = Solver()
rng = RNG(initial_vec)
for i in range(100000):
    rng.init_feed_tap() # Set the initial feed and tap value after the 100000 loops

# Start crafting the z3 equations
for i in range(4):
    rng.next()

gap = 0
leaked_idx = 0
for i in range(607):
    x = rng.next()
    s.add(x == leaked[leaked_idx])
    leaked_idx += 1
    for j in range(gap):
        rng.next()
    gap = (gap + 1) % 13

print('Checking whether it is sat or not...')
if s.check() == sat:
    print('It is sat, reconstruct the RNG internal state...')
    new_vec = []
    model = s.model()
    for i in range(rngLen):
        key = BitVec("x"+str(i), 64)
        val_model = model[key]
        if val_model is not None:
            new_vec.append(val_model.as_long())
        else:
            # Well, some of the internal vec states couldn't be recovered, but it's okay
            new_vec.append(-1)

    # Create new RNG with the internal states found by z3
    new_rng = RNG(new_vec)

    # Init the correct feed and tap pointer
    for i in range(100000):
        new_rng.init_feed_tap()

    print('Retrieving the flag...')
    flag = b''
    for i in range(4):
        x = new_rng.next()
        flag_int = (flag_chunks[i]^x)
        flag += flag_int.to_bytes((flag_int.bit_length() + 7) // 8, byteorder='little') # The flag was converted back to bytes following the LittleEndian convention
    print(f'Flag: {flag.decode()}')

Flag: actf{i_c4n_f0rs33_th3_p4s7_t00_}

Follow me on twitter