CRYPTO-2

Оценка: 20

Описание

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

Решение

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

Участникам предоставлялось условие задачи на языке программирования python:

from flask import Flask, render_template, request
from flag import flag
from Crypto.Util.number import *
from random import randint

assert flag.endswith(b'}')
flag = bytes_to_long(flag)

flag = bin(flag)[2:]
assert flag[-2] == '0'

n = getPrime(512) * getPrime(512)

app = Flask(__name__)

@app.route('/')
def intro():
    return render_template('intro.html', n = n)

@app.route('/guess_bit', methods=['GET'])
def guess_bit():
    args = request.args
    if 'bit' not in args.keys():
        return {"error": "Bit needed to be guessed"}
    index = abs(int(args['bit']))

    if index >= len(flag):
        return {"error": "Index overflow"}
    bit = flag[index]

    if bit == '1':
        return {"guess": pow(7, getPrime(300), n)}
    else:
        return {"guess": randint(n//2, n)}

def main():
    app.run(host='0.0.0.0', port=1177)

if __name__ == "__main__":
    main()

Для решения данной задачи участнику было нужно:

1. Найти длину флага при помощи бинарного поиска (или просто перебора);
2. Понять, что если выбранный бит флага равен единице, то операция будет сильно сложнее, чем операция при бите флага равном нулю.

Ниже представлено решение:

import requests
import time 
from Crypto.Util.number import *

r = requests.Session()
url = 'http://127.0.0.1:5000'

# Данная функция возвращает бит ответа по индексу
def guess_bit(index:int):
    return r.get(f"{url}/guess_bit?bit={index}").json()

# Данная функция возвращает бит ответа по индексу и время, которое на это ушло
def guess_bit_timing(index:int):
    time_start = time.time_ns()
    ans = r.get(f"{url}/guess_bit?bit={index}").json()
    time_end = time.time_ns()
    return ans, time_end - time_start

# Данная функция реализует бинарный поиск по длине ответа, возвращает количество бит в ответе
def find_length():
    msg = guess_bit(0)
    low = 0
    #i think 1000 bits for flag enough
    high = 1000
    #binary search for smart people :D
    while low <= high:
        middle = (low + high)//2
        msg = guess_bit(middle)
        if "error" in msg.keys():
            high = middle - 1 
        else:
            low = middle + 1
    #from zero to length of flag - 1
    return low

length = find_length()
# Данная функция находит среднее время, необходимое, чтобы достать бит по индексу.
def medium_time(index, attempts = 50):
    timings = []

    # hardcoded 50 is a random number
    for _ in range(attempts):
        timings.append(guess_bit_timing(index)[1])
    return sum(timings)/len(timings)


# Находим среднее время для нулевого бита
MED_ZERO_TIME = medium_time(length - 2)

# Находим среднее время для единичного бита
MED_ONE_TIME = medium_time(0)

# Находим медианное время
MED_TO_DIVIDE = (MED_ZERO_TIME + MED_ONE_TIME)/2


# Данная функция находит бит, сравнивая среднее время для бита по индексу и медианное время
def timing_attack_for_bit(index):
    bit_time = medium_time(index, 10)
    return '1' if bit_time > MED_TO_DIVIDE else '0'

# Данная функция находит каждый бит флага
def retrieve_flag():
    flag = ''
    for i in range(length):
        flag += timing_attack_for_bit(i)
    return long_to_bytes(int(flag,2)).decode()
    
if __name__ == "__main__":
    print(retrieve_flag())