HyperSonic CTF 2026 aaa Writeup

HyperSonic CTF 2026 aaa 문제 풀이HyperSonic CTF 2026 aaa writeup

Part 4 of 17 2026.06.08 3 min read4 min read

Contents

개요

aaa는 RSA 복호화 과정에서 기록된 사이드 채널 트레이스를 이용하는 crypto 문제입니다. 제공된 코드는 private exponent d를 사용해 모듈러 거듭제곱을 수행하고, 별도로 공개키 값 N, e, ciphertext c가 주어집니다.

확인한 조건은 다음과 같습니다.

분야: crypto
목표: 트레이스에서 private exponent d를 복구하고 c를 복호화합니다.
검증 방식: 복호화한 평문 m에 대해 pow(m, e, N) == c가 성립하는지 확인합니다.

핵심은 복호화 함수의 분기입니다. d의 각 비트가 곱셈 여부를 결정하므로, 트레이스에서 연산 패턴을 읽어내면 d 전체를 복구할 수 있습니다.

문제 분석

사용하는 값은 다음과 같습니다.

N: RSA modulus입니다.
e: RSA public exponent이며, 값은 65537입니다.
c: 복호화해야 하는 ciphertext입니다.
d: 트레이스에서 복구할 private exponent입니다.
samples: 트레이스에 들어 있는 float32 샘플 배열입니다.
run: threshold를 기준으로 나눈 연속 구간입니다.

제공된 복호화 함수는 다음과 같습니다.

python

def modexp_leaky(base, exp, mod):
    result = 1
    for bit in bin(exp)[2:]:
        result = (result * result) % mod
        if bit == '1':
            result = (result * base) % mod
    return result

이 함수는 왼쪽에서 오른쪽으로 exponent 비트를 읽는 square-and-multiply 방식입니다. 모든 비트에서 square를 한 번 수행하고, 비트가 1일 때만 multiply를 추가로 수행합니다.

text

bit 0: square
bit 1: square, multiply

따라서 트레이스에서 square와 multiply가 구분되면 각 비트를 바로 읽을 수 있습니다. 실제 샘플을 threshold 0.4 기준으로 나누면 고전력 연산 구간과 저전력 공백 구간이 명확하게 분리됩니다.

text

고전력 연산 구간: 220 샘플
square와 multiply 사이의 짧은 공백: 25 샘플
다음 exponent 비트로 넘어가는 공백: 135 샘플

이 길이 차이로 비트를 판정합니다.

text

220 high, 25 low, 220 high, 135 low -> bit 1
220 high, 135 low                   -> bit 0

핵심 아이디어

이 문제에서 필요한 정보는 d의 각 비트입니다. RSA의 수학적 약점을 찾거나 N을 인수분해할 필요는 없습니다. 복호화 루틴 자체가 d의 비트에 따라 연산 개수를 바꾸므로, 트레이스의 길이 패턴이 곧 private exponent의 비트열이 됩니다.

bit 0에서는 square 한 번 뒤 곧바로 다음 비트 처리로 넘어갑니다. 반대로 bit 1에서는 square 뒤에 multiply가 한 번 더 나오고, 두 연산 사이에는 짧은 공백이 있습니다. 즉 threshold로 만든 run을 앞에서부터 읽으면서 짧은 공백 뒤에 추가 연산이 나타나면 1, 긴 공백으로 바로 넘어가면 0으로 기록하면 됩니다.

복구한 비트열을 정수 d로 바꾼 뒤에는 일반 RSA 복호화와 같습니다.

text

m = c^d mod N

m을 다시 공개키로 암호화했을 때 원래 c가 나오면 트레이스에서 읽은 d가 올바른 것입니다.

풀이 과정

Step 1. 연산 구간 분리

트레이스는 실수 샘플 배열이므로 먼저 threshold를 정해야 합니다. 값을 바꿔 보니 0.4에서 모든 구간이 기대한 길이로 나뉩니다. 이때 연속된 고전력 구간은 모두 220샘플이고, 저전력 구간은 25 또는 135샘플로만 나타납니다.

이 단계의 결과는 (상태, 시작 위치, 끝 위치, 길이) 형태의 run 목록입니다. 상태가 참이면 연산 구간, 거짓이면 공백 구간입니다.

Step 2. 공백 길이로 exponent 비트 복구

각 비트는 반드시 square 연산으로 시작합니다. 따라서 현재 run이 220샘플짜리 고전력 구간인지 확인한 뒤, 바로 다음 저전력 구간의 길이를 봅니다.

저전력 구간이 25샘플이면 square와 multiply 사이의 짧은 공백입니다. 이 경우 다음에 다시 220샘플짜리 고전력 구간이 나와야 하며, 해당 비트는 1입니다. 이후 비트 경계에 해당하는 135샘플 공백을 하나 더 소비합니다.

저전력 구간이 135샘플이면 multiply 없이 다음 비트로 넘어간 것이므로 해당 비트는 0입니다.

이 규칙으로 전체 트레이스를 스캔하면 2047비트의 d를 얻습니다.

Step 3. RSA 복호화와 검증

복구한 비트열을 int(bits, 2)로 변환하면 private exponent d가 됩니다. 이후 pow(c, d, N)으로 평문 정수 m을 구하고, 이를 바이트열로 바꿉니다.

복호화 결과가 그럴듯한 문자열로 보이는 것만으로는 부족합니다. 공개키 값이 함께 주어져 있으므로 다음 조건을 검사했습니다.

text

pow(m, e, N) == c

이 값이 참이면 복구한 d와 평문이 RSA 관계를 만족합니다.

Exploit / Solver

solver의 전체 흐름은 다음과 같습니다.

트레이스를 float32 샘플 배열로 읽습니다.
threshold 0.4로 연속 구간을 나눕니다.
220/25/135 길이 패턴으로 d의 비트를 복구합니다.
주어진 N, e, c를 읽고 pow(c, d, N)을 계산합니다.
pow(m, e, N) == c로 결과를 검증합니다.

아래는 핵심 루틴만 추린 코드입니다.

python

import array
import re
import struct


def load_npy_float32(path):
    with open(path, "rb") as f:
        if f.read(6) != b"\x93NUMPY":
            raise ValueError("not a numpy file")
        major, minor = f.read(2)
        if (major, minor) != (1, 0):
            raise ValueError("unsupported npy version")

        header_len = struct.unpack("<H", f.read(2))[0]
        header = f.read(header_len)
        if b"'descr': '<f4'" not in header:
            raise ValueError("unexpected dtype")

        data = array.array("f")
        data.frombytes(f.read())
        return data


def threshold_runs(samples, threshold=0.4):
    runs = []
    current = samples[0] > threshold
    start = 0

    for idx, value in enumerate(samples[1:], 1):
        high = value > threshold
        if high != current:
            runs.append((current, start, idx, idx - start))
            current = high
            start = idx

    runs.append((current, start, len(samples), len(samples) - start))
    return runs


def recover_exponent_bits(runs):
    bits = []
    idx = 0

    while idx < len(runs):
        high, _start, _end, high_len = runs[idx]
        if not high or high_len != 220:
            raise ValueError(f"unexpected operation run: {runs[idx]}")

        gap_len = runs[idx + 1][3]
        if gap_len == 25:
            if idx + 2 >= len(runs):
                raise ValueError("missing multiply run")
            next_high, *_rest, next_len = runs[idx + 2]
            if not next_high or next_len != 220:
                raise ValueError(f"unexpected multiply run: {runs[idx + 2]}")

            bits.append("1")
            idx += 3

            if idx < len(runs):
                separator_high, *_rest, separator_len = runs[idx]
                if separator_high or separator_len != 135:
                    raise ValueError(f"unexpected separator: {runs[idx]}")
                idx += 1

        elif gap_len == 135:
            bits.append("0")
            idx += 2
        else:
            raise ValueError(f"unexpected gap length: {gap_len}")

    return "".join(bits)


def parse_values(text):
    values = {}
    for name in ("N", "e", "c"):
        match = re.search(rf"^{name} = (\d+)", text, re.MULTILINE)
        if not match:
            raise ValueError(f"missing {name}")
        values[name] = int(match.group(1))
    return values["N"], values["e"], values["c"]


def solve(trace_path, output_text):
    samples = load_npy_float32(trace_path)
    runs = threshold_runs(samples)
    bits = recover_exponent_bits(runs)
    d = int(bits, 2)

    N, e, c = parse_values(output_text)
    m = pow(c, d, N)
    plaintext = m.to_bytes((m.bit_length() + 7) // 8, "big")

    return {
        "runs": len(runs),
        "bits": len(bits),
        "ones": bits.count("1"),
        "rsa_check": pow(m, e, N) == c,
        "plaintext": plaintext,
    }

후보 탐색은 따로 하지 않습니다. 트레이스 구간 길이가 일정하므로 예외 처리를 걸어 두고 한 번만 스캔하면 됩니다. 구간 길이가 예상과 다르면 바로 실패하도록 둔 것도 같은 이유입니다.

결과

실행 결과 6176개의 run에서 2047비트의 exponent를 복구했습니다. 그중 1비트는 1041개였고, RSA 검증도 통과했습니다.

text

runs=6176 bits=2047 ones=1041
rsa_check=True
hs{squ4re_4nd_mult1ply_l34ks_3v3ry_b1t_0f_y0ur_pr1v4t3_d}

flag는 다음과 같습니다.

text

hs{squ4re_4nd_mult1ply_l34ks_3v3ry_b1t_0f_y0ur_pr1v4t3_d}

Overview

aaa is a crypto challenge that uses a side-channel trace recorded during RSA decryption. The provided code performs modular exponentiation with the private exponent d, and the public key values N, e and the ciphertext c are given separately.

The conditions I confirmed are as follows.

Category: crypto
Goal: recover the private exponent d from the trace and decrypt c.
Verification: check that pow(m, e, N) == c holds for the decrypted plaintext m.

The branch in the decryption function is the key. Each bit of d decides whether a multiplication happens, so reading the operation pattern from the trace recovers the whole d.

Challenge analysis

The values used below:

N: the RSA modulus.
e: the RSA public exponent, 65537.
c: the ciphertext to decrypt.
d: the private exponent to recover from the trace.
samples: the array of float32 samples in the trace.
run: a contiguous segment split by the threshold.

The provided decryption function is:

python

def modexp_leaky(base, exp, mod):
    result = 1
    for bit in bin(exp)[2:]:
        result = (result * result) % mod
        if bit == '1':
            result = (result * base) % mod
    return result

This is left-to-right square-and-multiply over the exponent bits. It performs one square for every bit and an additional multiply only when the bit is 1.

text

bit 0: square
bit 1: square, multiply

So if square and multiply can be distinguished in the trace, each bit can be read off directly. Splitting the actual samples at a threshold of 0.4 cleanly separates high-power operation segments from low-power gaps.

text

High-power operation segment: 220 samples
Short gap between square and multiply: 25 samples
Gap before the next exponent bit: 135 samples

These length differences make the bit decision rule simple.

text

220 high, 25 low, 220 high, 135 low -> bit 1
220 high, 135 low                   -> bit 0

Key idea

The information needed here is each bit of d. There is no need to find a mathematical weakness in RSA or to factor N. The decryption routine itself changes the number of operations based on the bits of d, so the length pattern of the trace is the bit string of the private exponent.

For bit 0, a single square is followed immediately by processing of the next bit. For bit 1, the square is followed by one more multiply, with a short gap between the two operations. So reading the threshold runs from the start, record 1 when an extra operation appears after a short gap, and 0 when it moves on directly through a long gap.

Once the recovered bit string is converted to an integer d, the rest is ordinary RSA decryption.

text

m = c^d mod N

If re-encrypting m with the public key gives back the original c, the d read from the trace is correct.

Solution

Step 1. Segmenting the operations

The trace is an array of floating-point samples, so a threshold has to be chosen first. Trying different values, 0.4 splits every segment into the expected lengths. At this threshold every contiguous high-power segment is 220 samples, and low-power segments only appear as 25 or 135 samples.

The output of this step is a list of runs of the form (state, start, end, length). A true state is an operation segment, a false state a gap.

Step 2. Recovering exponent bits from gap lengths

Every bit starts with a square. So check that the current run is a 220-sample high-power segment, then look at the length of the immediately following low-power segment.

If the low-power segment is 25 samples, it is the short gap between square and multiply. In that case another 220-sample high-power segment must follow, and the bit is 1. After that, one more 135-sample gap, the bit boundary, is consumed.

If the low-power segment is 135 samples, it moved on to the next bit without a multiply, so the bit is 0.

Scanning the whole trace with this rule yields a 2047-bit d.

Step 3. RSA decryption and verification

Converting the recovered bit string with int(bits, 2) gives the private exponent d. Then pow(c, d, N) gives the plaintext integer m, which is converted to bytes.

Checking that the decryption looks like a plausible string is not enough. Since the public key values are given, I checked the following condition.

text

pow(m, e, N) == c

If this is true, the recovered d and plaintext satisfy the RSA relation.

Exploit / Solver

The solver runs these steps:

Read the trace as an array of float32 samples.
Split it into contiguous segments with threshold 0.4.
Recover the bits of d using the 220/25/135 length pattern.
Read the given N, e, c and compute pow(c, d, N).
Verify the result with pow(m, e, N) == c.

The code below is only the core routines.

python

import array
import re
import struct


def load_npy_float32(path):
    with open(path, "rb") as f:
        if f.read(6) != b"\x93NUMPY":
            raise ValueError("not a numpy file")
        major, minor = f.read(2)
        if (major, minor) != (1, 0):
            raise ValueError("unsupported npy version")

        header_len = struct.unpack("<H", f.read(2))[0]
        header = f.read(header_len)
        if b"'descr': '<f4'" not in header:
            raise ValueError("unexpected dtype")

        data = array.array("f")
        data.frombytes(f.read())
        return data


def threshold_runs(samples, threshold=0.4):
    runs = []
    current = samples[0] > threshold
    start = 0

    for idx, value in enumerate(samples[1:], 1):
        high = value > threshold
        if high != current:
            runs.append((current, start, idx, idx - start))
            current = high
            start = idx

    runs.append((current, start, len(samples), len(samples) - start))
    return runs


def recover_exponent_bits(runs):
    bits = []
    idx = 0

    while idx < len(runs):
        high, _start, _end, high_len = runs[idx]
        if not high or high_len != 220:
            raise ValueError(f"unexpected operation run: {runs[idx]}")

        gap_len = runs[idx + 1][3]
        if gap_len == 25:
            if idx + 2 >= len(runs):
                raise ValueError("missing multiply run")
            next_high, *_rest, next_len = runs[idx + 2]
            if not next_high or next_len != 220:
                raise ValueError(f"unexpected multiply run: {runs[idx + 2]}")

            bits.append("1")
            idx += 3

            if idx < len(runs):
                separator_high, *_rest, separator_len = runs[idx]
                if separator_high or separator_len != 135:
                    raise ValueError(f"unexpected separator: {runs[idx]}")
                idx += 1

        elif gap_len == 135:
            bits.append("0")
            idx += 2
        else:
            raise ValueError(f"unexpected gap length: {gap_len}")

    return "".join(bits)


def parse_values(text):
    values = {}
    for name in ("N", "e", "c"):
        match = re.search(rf"^{name} = (\d+)", text, re.MULTILINE)
        if not match:
            raise ValueError(f"missing {name}")
        values[name] = int(match.group(1))
    return values["N"], values["e"], values["c"]


def solve(trace_path, output_text):
    samples = load_npy_float32(trace_path)
    runs = threshold_runs(samples)
    bits = recover_exponent_bits(runs)
    d = int(bits, 2)

    N, e, c = parse_values(output_text)
    m = pow(c, d, N)
    plaintext = m.to_bytes((m.bit_length() + 7) // 8, "big")

    return {
        "runs": len(runs),
        "bits": len(bits),
        "ones": bits.count("1"),
        "rsa_check": pow(m, e, N) == c,
        "plaintext": plaintext,
    }

There is no candidate search. The segment lengths are constant, so a single scan with exception checks is enough, and an unexpected length fails immediately.

Result

The run recovered a 2047-bit exponent from 6176 runs. 1041 of those bits were 1, and the RSA check passed.

text

runs=6176 bits=2047 ones=1041
rsa_check=True
hs{squ4re_4nd_mult1ply_l34ks_3v3ry_b1t_0f_y0ur_pr1v4t3_d}

The flag is:

text

hs{squ4re_4nd_mult1ply_l34ks_3v3ry_b1t_0f_y0ur_pr1v4t3_d}

개요#

문제 분석#

핵심 아이디어#

풀이 과정#

Step 1. 연산 구간 분리#

Step 2. 공백 길이로 exponent 비트 복구#

Step 3. RSA 복호화와 검증#

Exploit / Solver#

결과#

Overview#

Challenge analysis#

Key idea#

Solution#

Step 1. Segmenting the operations#

Step 2. Recovering exponent bits from gap lengths#

Step 3. RSA decryption and verification#

Exploit / Solver#

Result#

개요

문제 분석

핵심 아이디어

풀이 과정

Step 1. 연산 구간 분리

Step 2. 공백 길이로 exponent 비트 복구

Step 3. RSA 복호화와 검증

Exploit / Solver

결과

Overview

Challenge analysis

Key idea

Solution

Step 1. Segmenting the operations

Step 2. Recovering exponent bits from gap lengths

Step 3. RSA decryption and verification

Exploit / Solver

Result