sch9_ctf_3/tasks/cringe_random

Разбор таска cringe random

• Это что, рандом???
• Тише, тише....

Давайте разберёмся что делает программа. Это генератор чисел, у которого есть состояние - массив из n чисел по n бит, числа последовательно берутся из него, а потом состояние обновляется, так что если мы сможем "развернуть" функцию update_state(), то сможем восстановить все состояния и узнать значения случайных чисел, которые использовались для генерации флага.

Функция n раз копирует первое число в конец, а остальные изменяет, опираясь только на первое (причём, изменяет с помощью xor, который обращается повторным xor на то же самое число), после чего удаляет скопированный первый элемент, так что каждый шаг мы можем развернуть, просто скопировав последний элемент в начало и повторив данную операцию над остальными, а вызов update_state() "разворачивается" просто последовательным разворотом шагов с конца. Код "разворота" update_step():

def prev_state():
    for i in range(n-1,-1,-1):
        state.insert(0, state[-1])
        for j in range(1,n):
            state[j] ^= ((state[0] >> j) & 1) << i
        state.pop(n)

Тогда, чтобы получить первый state, посчитаем сколько раз вызывался update_state(). Для этого можно просто запустить исходную программу и посчитать там количество выполнений этой функции, ведь оно всегда одинаково. Итоговый код возвращения флага:

state=[110, 557, 303, 18, 127, 615, 844, 924, 177, 541]
n=10
def prev_state():
    for i in range(n-1,-1,-1):
        state.insert(0, state[-1])
        for j in range(1,n):
            state[j] ^= ((state[0] >> j) & 1) << i
        state.pop(n)

for i in range(2):
    prev_state()

flag_len = 20
k = 0

def update_state():
    for i in range(n):
        state.append(state[0])
        for j in range(1, n):
            state[j] ^= ((state[0] >> j) & 1) << i
        state.pop(0)

def get_random():
    global k
    if(k == n):
        k = 0
        update_state()
    k += 1
    return state[k - 1]

flag='ctf{' + (''.join([chr(get_random() % 26 + ord('a')) for i in range(flag_len)])) + '}'
print(flag)
update_state()
print(state)