markov mystery

problem

My friend Markov says he lost the main system, but I know nothing of these weird stuff.

see output.txt

see markovgraphy.pyc

solution

pyc files are compiled python files, and are not human readable

what we can do to decrypt it is use pycdc

the problem here is that some of the opcodes are not found and so pycdc fails

what we can do is just clone a copy from here and then remove the error message on the missing opcode

diff --git a/ASTree.cpp b/ASTree.cpp
index e7c9262..0fb62ee 100644
--- a/ASTree.cpp
+++ b/ASTree.cpp
@@ -2363,10 +2363,6 @@ PycRef<ASTNode> BuildFromCode(PycRef<PycCode> code, PycModule* mod)
         case Pyc::PUSH_NULL:
             stack.push(nullptr);
             break;
-        default:
-            fprintf(stderr, "Unsupported opcode: %s\n", Pyc::OpcodeName(opcode & 0xFF));
-            cleanBuild = false;
-            return new ASTNodeList(defblock->nodes());
         }

         else_pop =  ( (curblock->blktype() == ASTBlock::BLK_ELSE)

then we can compile it and use it to get the following:

# Source Generated with Decompyle++
# File: markovgraphy.pyc (Python 3.10)

import random
import numpy as np

with open('flag.txt', 'r') as f:
    FLAG = f.read()

random_letter_number = 'abcdefghijklmnopqrstuvwxyz0123456789'
system_1_states = np.array([
    't',
    random.choice(random_letter_number),
    random.choice(random_letter_number)])
system_1 = np.array([
    [
        0.125,
        0.428571,
        0.75],
    [
        0.75,
        0.142857,
        0.25],
    [
        0.125,
        0.428571,
        0]])


def create_system(letter):
    size = random.randint(5, 10)
    states = []
    for i in range(size):
        random_letter = random.choice(random_letter_number)
        if random_letter not in states and random_letter != letter:
            pass

        states.append(random_letter)

    states = np.array(states)
    states[random.randint(0, size - 1)] = letter
    transition_matrix = np.random.rand(size, size)
    transition_matrix = transition_matrix / transition_matrix.sum(axis=1, keepdims=True)
    values = the_markov_mystery(transition_matrix)

    dictionary = {}
    for i in range(size):
        dictionary[states[i]] = values[i]

    highest = max(dictionary, key=dictionary.get)
    dictionary[letter] = dictionary[highest]
    dictionary[highest] = dictionary[letter]

    # swap heighest and j
    for i in range(size):
        if states[i] == highest:
            dummy = i
            states[i] = letter
    for j in range(size):
        if states[j] == letter and j != dummy:
            states[j] = highest

    return states, dictionary, transition_matrix


def the_markov_mystery(p):
    # deterministic btw
    dim = p.shape[0]
    q = p - np.eye(dim)
    ones = np.ones(dim)
    q = np.c_[(q, ones)]
    QTQ = np.dot(q, q.T)
    bQT = np.ones(dim)
    return np.linalg.solve(QTQ, bQT)


if __name__ == '__main__':
    flag_dictionary = {}
    i = 1
    for letter in FLAG:
        states, dictionary, transition_matrix = create_system(letter)
        transition_dictionary = {}
        for k_index in range(len(states)):
            transition_dictionary[states[k_index]] = transition_matrix[k_index]
        flag_dictionary[i] = transition_dictionary
        print('System ' + str(i) + ' \n')
        print('States: ' + str(states) + '\n')
        print('Transition matrix: \n' + str(transition_matrix) + '\n')
        print('Dictionary: \n' + str(transition_dictionary) + '\n')
        i += 1

we can see that the largest value of the output of the_markov_mystery is swapped with the actual letter of the flag

from this, we make a solve script

import numpy as np


with open("out.txt") as f:
    systems = []
    states = []
    save_data = ""
    next_is_transition_matrix = False
    for line in f.read().splitlines(False):
        line = line.replace("\x00", "")
        if line.startswith("States:"):
            states = [_[1] for _ in line[9:-1].split(" ")]
        if line.startswith("Tran"):
            next_is_transition_matrix = True
            continue
        if next_is_transition_matrix:
            if line.startswith("Dic"):
                systems.append([eval(save_data), states])
                states = []
                save_data = ""
                next_is_transition_matrix = False
                continue
            save_data += line.replace("  ", " ").replace("  ", " ").replace("  ", " ").replace(" ", ",")


def the_markov_mystery(p):
    # deterministic
    dim = p.shape[0]
    q = p - np.eye(dim)
    ones = np.ones(dim)
    q = np.c_[(q, ones)]
    QTQ = np.dot(q, q.T)
    bQT = np.ones(dim)
    return np.linalg.solve(QTQ, bQT)


for system in systems:
    transition_matrix, states2 = system
    data2 = the_markov_mystery(np.array(transition_matrix)).tolist()
    data2 = [float(_) for _ in data2]
    print(states2[data2.index(max(data2))], end="")

flag is ictf{0h_d4mn_m4rk0v_ch41n5_4r3nt_th4t_b4d}