Skip to content

cyclic one time pad

Jump to bottom
Maxim Pivko edited this page Mar 11, 2018 · 3 revisions

Разработчики WriteOnn опубликовали код криптографического модуля

  • Категория: Crypto
  • Стоимость: 300
  • Автор: Максим Пивко
  • Репозиторий

Условие

Разработчики популярного мессенджера WriteOnn выложили в свободный доступ исходные коды модуля, используемого в мессенджере для шифрования. «Теперь наше приложение ничем не уступает, а в чём-то даже превосходит как российские, так и зарубежные аналоги», — заявил технический директор WriteOnn Алексей Профананцев, — «Наш способ шифрования надёжен, это проверили ведущие специалисты по информационной безопасности».

За неделю до публикации кода WriteOnn предложила экспертам в области криптографии изучить модуль в рамках закрытого тестирования, а сегодня запустила так называемую программу bug bounty, в рамках которой любой желающий может провести исследование сервиса и получить вознаграждение за найденные уязвимости. В качестве подтверждения наличия уязвимости разработчики предлагают расшифровать фрагмент данных: wOS8dBlj5KCChVqRRRWYTa0/nMGSUgCVSAFSU1CFqW34c5Xo4VdEVA==.

Решение

В условии дана ссылка на сайт, позволяющий зашифровать данные.

Oднако дешифровка недоступна.

Также на сайте можно прочитать исходный код алгоритма, использующегося для шифрования:

class Cipher:
    def __init__(self, key, seed):
        self.key = key
        self.seed = seed

    def encrypt(self, data):
        if len(data) > len(self.key):
            raise Exception("Can encrypt only blocks which are no longer than key length")
        data = [x ^ y for (x, y) in zip(data, self.key)]
        random.seed(self.seed)
        random.shuffle(data)
        data = [x ^ y for (x, y) in zip(data, self.key)]
        return bytes(data)

    def decrypt(self, data):
        if len(data) > len(self.key):
            raise Exception("Can decrypt only blocks which are no longer than key length")
        data = [x ^ y for (x, y) in zip(data, self.key)]
        perm = list(range(len(data)))
        random.seed(self.seed)
        random.shuffle(perm)
        unshuffled = [0] * len(data)
        for pos, value in enumerate(perm):
            unshuffled[value] = data[pos]
        data = [x ^ y for (x, y) in zip(unshuffled, self.key)]
        return bytes(data)

Изучив код, можно понять, что алгоритм шифрования состоит из трех шагов:

  1. xor с неизвестной строкой self.key
  2. random.shuffle (то есть некотороая перестановка элементов) с seed равным self.seed
  3. xor с той же неизвестной строкой self.key

Алгоритм расшифровки просто применяет обратную последовательность действий: xor, обратная перестановка, xor. Однако он будет нам не так интересен.

Попробовав зашифровать один и тот же текст дважды и получив одинаковый результат, можно понять, что значения, от которых зависит шифрование (а именно — key и seed) фиксированы.

Поскольку секреты фиксированы, есть риск уязвимости связанной с повторным шифрованием данных. Попробуем понять, что же произойдет, если применить алгоритм дважды.

Одна итерация:

xor ∘ shuffle ∘ xor

Две итерации:

xor ∘ shuffle ∘ xor ∘ xor ∘ shuffle ∘ xor

Но два xor-а взаимоуничтожаются, в результате получается:

xor ∘ shuffle ∘ shuffle ∘ xor = xor ∘ shuffle ^ 2 ∘ xor

Аналогичным образом после n применений алгоритма мы получим:

xor ∘ shuffle ^ n ∘ xor

Однако shuffle — это просто перестановка элементов. А каждая перестановка имеет степень — число раз, которое её нужно применить, чтобы получить исходную последовательность. Итак, если в качестве n взять степень перестановки, то получим:

xor ∘ shuffle ^ n ∘ xor = xor ∘ xor

А как уже обсуждалось выше, xor ∘ xor взаимоуничтожаются, в результате производя эквивалентное преобразование (проще говоря — ничего не делающее).

Значит если зашифровать текст столько раз, какова степень перестановки shuffle, то получится снова исходный текст. Один раз текст, данный в задании, уже зашифрован, остается зашифровать его ещё на один раз меньше, чем степень перестановки. Остается понять, что для этого не нужно знать степень перестановки непосредственно: можно просто применять шифрование, пока не увидим флаг (можно заранее отсеять варианты не удовлетворяющие формату флага — то есть оставить только начинающиеся на QCTF).

Сделать это можно с помощью простого кода на python:

import requests
import base64
import re

encrypted_text = 'wOS8dBlj5KCChVqRRRWYTa0/nMGSUgCVSAFSU1CFqW34c5Xo4VdEVA=='

iteration = 0
while True:
    post_data = {
        'data_format': 'base64',
        'data': encrypted_text,
    }
    response = requests.post('https://cipher.contest.qctf.ru/encrypt', data=post_data).text
    encrypted_text = re.findall('<p class="code">(.*)</p>', response)[1]
    b64_decoded = base64.b64decode(encrypted_text.encode())
    if b'QCTF' in b64_decoded:
        print("Iteration: {}. Text: {}".format(iteration, b64_decoded))
    iteration += 1

Первые три строки (итеации 88, 178 и 268), содержащие QCTF, содержат непечатаемые символы, поэтому вряд ли являются флагами. Ждем дальше и на 358 итерации получаем флаг.

Iteration: 88. Text: b'QCTF{\x08&NT\x95USE_CU\x06\xe5OM_uIPHERS_KWHNX\x84YUT\xba}'
Iteration: 178. Text: b'QCTF{\xc2\x10NT\xc0USE_CU\xd5\x0bOM_\xc4IPHERS_KWHNX\xc8YUT\xd3}'
Iteration: 268. Text: b'QCTF{\x97\xa1NT\x13USE_CU\x99bOM_*IPHERS_KWHNX\x02YUT\xe5}'
Iteration: 358. Text: b'QCTF{DONT_USE_CUSTOM_CIPHERS_KWHNXWYUTT}'

В авторском решении приведен способ решения, требущий не очень глубокого анализа и написания небольшого количества кода. Однако, шифр не претендует на хоть какую-то безопасность, поэтому были и другие способы обойти его. Например, один из альтернативных способов описан в разборе от участников.

Clone this wiki locally