E4syCTF Writeup

trick OR flag?(Crypto)

配布ファイルをダウンロードするとPythonファイルと暗号文が渡されます

ฅ^-ﻌ-^ฅ < Happy Halloween! I gave you my sweets:
public_key:[57, 114, 228, 194, 126, 252, 242, 222]
encrypted_flag:[588, 674, 1000, 884, 578, 560, 608, 1126, 482, 782, 578, 704, 944, 1000, 1150, 594, 816, 720, 690, 806, 690, 1184, 1010, 1000, 1150, 1000, 1252, 816, 816, 788, 1000, 1150, 1252, 816, 778, 816, 1150, 468, 690, 594, 594, 816, 962, 1150, 690, 962, 1150, 932, 962, 564, 536, 1000, 564, 806, 932, 1136]

solver

問題文に「knapsack」と記述がある通りナップサック暗号で作成されています。
Lenstra–Lenstra–Lovász格子基底簡約アルゴリズム・格子簡約アルゴリズムを使って簡単なベクトルにして復号することが出来ます

# solver.py
import random
from typing import List
import numpy as np

# fpylllが利用できない場合の代替実装
try:
    from fpylll import LLL, BKZ, IntegerMatrix
    FPYLLL_AVAILABLE = True
except ImportError:
    FPYLLL_AVAILABLE = False
    print("警告: fpylllがインストールされていません。簡易版のLLL実装を使用します。")

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def modinv(a, m):
    # 拡張ユークリッド互除法
    g, x, y = extended_gcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def extended_gcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = extended_gcd(b % a, a)
        return (g, x - (b // a) * y, y)

def simple_lll_reduction(matrix):
    """
    簡易版のLLL還元アルゴリズム
    """
    matrix = np.array(matrix, dtype=float)
    n, m = matrix.shape
    
    # Gram-Schmidt直交化
    def gram_schmidt(B):
        n, m = B.shape
        B_star = np.zeros_like(B)
        mu = np.zeros((n, n))
        
        for i in range(n):
            B_star[i] = B[i].copy()
            for j in range(i):
                mu[i, j] = np.dot(B[i], B_star[j]) / np.dot(B_star[j], B_star[j])
                B_star[i] -= mu[i, j] * B_star[j]
        
        return B_star, mu
    
    # LLL還元のメインループ
    k = 1
    while k < n:
        B_star, mu = gram_schmidt(matrix)
        
        # Size reduction
        for j in range(k-1, -1, -1):
            if abs(mu[k, j]) > 0.5:
                q = round(mu[k, j])
                matrix[k] -= q * matrix[j]
                for i in range(j):
                    mu[k, i] -= q * mu[j, i]
                mu[k, j] -= q
        
        # Lovász condition
        if np.dot(B_star[k], B_star[k]) >= (0.75 - mu[k, k-1]**2) * np.dot(B_star[k-1], B_star[k-1]):
            k += 1
        else:
            # Swap
            matrix[[k-1, k]] = matrix[[k, k-1]]
            k = max(1, k-1)
    
    return matrix.astype(int)

def lll_attack(ciphertext: int, public_key: List[int]) -> List[int]:
    """
    LLL/BKZ攻撃を使用してナップサック暗号を解読
    """
    n = len(public_key)
    
    # 格子の基底行列を作成
    # 各行は [public_key[i], 0, ..., 0, 1, 0, ..., 0] の形式
    # 最後の行は [ciphertext, 0, ..., 0, 0, ..., 0, -1]
    matrix = []
    
    # 公開鍵の行を追加
    for i in range(n):
        row = [0] * (n + 1)
        row[i] = 1
        row[n] = public_key[i]
        matrix.append(row)
    
    # 暗号文の行を追加
    row = [0] * (n + 1)
    row[n] = -ciphertext
    matrix.append(row)
    
    if FPYLLL_AVAILABLE:
        # fpylllを使用
        A = IntegerMatrix.from_matrix(matrix)
        LLL.reduction(A)
        
        # 短いベクトルを探す
        for i in range(A.nrows):
            row = A[i]
            if row[n] == 0:
                solution = []
                valid = True
                for j in range(n):
                    if row[j] == 0 or row[j] == 1:
                        solution.append(row[j])
                    else:
                        valid = False
                        break
                if valid and sum(solution) > 0:
                    return solution
    else:
        # 簡易版LLLを使用
        reduced_matrix = simple_lll_reduction(matrix)
        
        # 短いベクトルを探す
        for i in range(len(reduced_matrix)):
            row = reduced_matrix[i]
            if row[n] == 0:
                solution = []
                valid = True
                for j in range(n):
                    if row[j] == 0 or row[j] == 1:
                        solution.append(row[j])
                    else:
                        valid = False
                        break
                if valid and sum(solution) > 0:
                    return solution
    
    return None

def bkz_attack(ciphertext: int, public_key: List[int], block_size: int = 10) -> List[int]:
    """
    BKZ攻撃を使用してナップサック暗号を解読
    """
    n = len(public_key)
    
    # 格子の基底行列を作成
    matrix = []
    
    # 公開鍵の行を追加
    for i in range(n):
        row = [0] * (n + 1)
        row[i] = 1
        row[n] = public_key[i]
        matrix.append(row)
    
    # 暗号文の行を追加
    row = [0] * (n + 1)
    row[n] = -ciphertext
    matrix.append(row)
    
    if FPYLLL_AVAILABLE:
        # fpylllを使用
        A = IntegerMatrix.from_matrix(matrix)
        BKZ.reduction(A, BKZ.Param(block_size=block_size))
        
        # 短いベクトルを探す
        for i in range(A.nrows):
            row = A[i]
            if row[n] == 0:
                solution = []
                valid = True
                for j in range(n):
                    if row[j] == 0 or row[j] == 1:
                        solution.append(row[j])
                    else:
                        valid = False
                        break
                if valid and sum(solution) > 0:
                    return solution
    else:
        # fpylllが利用できない場合はLLL攻撃を使用
        print("BKZ攻撃にはfpylllが必要です。LLL攻撃を使用します。")
        return lll_attack(ciphertext, public_key)
    
    return None

def brute_force_attack(ciphertext: int, public_key: List[int]) -> List[int]:
    """
    小さなナップサック問題に対する総当たり攻撃
    """
    n = len(public_key)
    
    # 2^n通りの組み合わせを試す
    for i in range(2**n):
        bits = [(i >> j) & 1 for j in range(n)]
        if sum(bit * pk for bit, pk in zip(bits, public_key)) == ciphertext:
            return bits
    
    return None

def attack_knapsack(ciphertext: List[int], public_key: List[int]) -> str:
    """
    ナップサック暗号に対する攻撃を実行
    """
    plaintext_bytes = []
    
    for s in ciphertext:
        # まず総当たり攻撃を試す（小さな問題の場合）
        bits = brute_force_attack(s, public_key)
        
        # 総当たりが失敗した場合はLLL攻撃を試す
        if bits is None:
            bits = lll_attack(s, public_key)
        
        # LLL攻撃が失敗した場合はBKZ攻撃を試す
        if bits is None:
            bits = bkz_attack(s, public_key)
        
        if bits is None:
            print(f"攻撃に失敗しました: 暗号文 {s}")
            return None
        
        # ビット列をバイトに変換
        byte = 0
        for bit in bits:
            byte = (byte << 1) | bit
        plaintext_bytes.append(byte)
    
    return bytes(plaintext_bytes).decode()

if __name__ == "__main__":
    public_key=[57, 114, 228, 194, 126, 252, 242, 222]
    encrypted=[588, 674, 1000, 884, 578, 560, 608, 1126, 482, 782, 578, 704, 944, 1000, 1150, 594, 816, 720, 690, 806, 690, 1184, 1010, 1000, 1150, 1000, 1252, 816, 816, 788, 1000, 1150, 1252, 816, 778, 816, 1150, 468, 690, 594, 594, 816, 962, 1150, 690, 962, 1150, 932, 962, 564, 536, 1000, 564, 806, 932, 1136]

    # LLL/BKZ攻撃
    print(f"\n=== LLL/BKZ攻撃を実行 ===")
    attacked = attack_knapsack(encrypted, public_key)
    if attacked:
        print(f"攻撃による復号結果: {attacked}")
    else:
        print("攻撃に失敗しました")

E4syCTF{JUCK's_delicious_sweets_were_hidden_in_knapsack}

spining-cat(Reversing)

「o」「i」「a」で構成された.cファイルとヘッダファイルが配布されます

#include <stdio.h>
#include <string.h>
#include ".cat.h"

oiao oiiaoiia oi
 oiai flag ao iiai oa oo oi
  aaaa iio aaaa iio aaaa iio aaaa iio aaaa iio aaaa iio aaaa oio aaa o
  aaaa iio aaaa iio aaaa iio aaaa iio aaaa iio aaa iio aaa o
  aaaaa iio aaaa iio aaa iio aaa iio aaa iio aaa iio aaa o
  aaaaa iio aaaa iii ai aaa iio aaa ia iio aaa o
  aaaaa oio aaaa oio aaaa oio aaaa oio aaa oio aaa oio aaa o
  aaaaa oio aaaa oio aaaa iio aaa iio aaa iio aaa iio aaa o
  aaaaa oio aaaa oio aaaa oio aaaa o
  aaaaa iio aaaa iio aaaa iio aaa iio aaa iio aaa o
  aaaaa oio aaaa oio aaaa oio aaa o
  aaaaa oio aaaa oio aaaa oio aaaa iio aaa iio aaa iio aaa o
  aaaaa oio aaaa oio aaaa oio aaaa iio aaa iio aaa iio aaa o
  aaaa iio aaaa iio aaaa iio aaaa iio aaaa iio aaaa iio aaa iio aaa iio aaa iio aaa iio aaa o
  aaaa iio aaaa iio aaaa iio aaaa iio aaa iio aaa iio aaa iio aaa iio aaa o
  aaaaa oio aaaa oio aaaa oio aaa o
  aaaaa oio aaaa oio aaaa oio aaaa iio aaa iio aaa iio aaa o
  aaaaa oio aaaa oio aaaa oio aaaa iio aaa iio aaa iio aaa o
  ai aaa iio aaa iio aaa iio aaa iio aaa ia iii ai aaaa iio aaa iio aaa iio aaa ia o
  aaaaa oio aaa oio aaa oio aaa oio aaa oio aaa o
  aaaaa iio aaaa iio aaa o
  aaaa iio aaaa iio aaaa iio aaaa iio aaaa iio aaaa iio aaaa iio aaa iio aaa iio aaa o
  aaaaa oio aaaa oio aaaa oio aaaa iio aaa iio aaa iio aaa o
  aaaa iio aaaa iio aaaa iio aaaa iio aaaa iio aaa iio aaa o
  aaaa iio aaaa iio aaaa iio aaaa iio aaa iio aaa iio aaa iio aaa iio aaa o
  aaaa iio aaaa iio aaaa iio aaaa iio aaaa oio aaa oio aaa o
  aaaa iio aaaa iio aaaa iio aaaa iio aaaa oio aaa o
  aaaa iio aaaa iio aaaa iio aaaa iio aaaa oio aaa o
  ai aaa iio aaa iio aaa iio aaa ia iii ai aaaa iio aaa iio aaa iio aaa ia o
  aaaaa oio aaa oio aaa oio aaa oio aaa oio aaa o
  aaaaa oio aaa o
  aaaa iio aaaa iio aaaa iio aaaa iio aaaa iio aaa iio aaa o
  aaaaa iio aaaa iio aaaa oio aaa oio aaa oio aaa oio aaa o
  aaaaa oio aaa oio aaa oio aaa oio aaa oio aaa o
  aaaaa iio aaa iio aaa iio aaa iio aaa iio aaa o
  aaaa iio aaaa iio aaaa iio aaaa iio aaaa iio aaa iio aaa iio aaa o
  aaaaa oio aaa oio aaa oio aaa oio aaa oio aaa o
  aaaa iio aaaa iio aaaa iio aaaa iio aaaa iio aaa iio aaa iio aaa o
  aaaaa iio aaaa iio aaa iio aaa o
  aaaaa iio aaa iio aaa iio aaa iio aaa iio aaa o
  aaaaa iio aaaa o
  aaaaa iio aaaa o
  aaaaa iio aaa iio aaa iio aaa iio aaa iio aaa o
  aaaaa iio aaaa o
  aaaa iio aaaa iio aaaa iio aaaa iio aaaa iio aaaa oio aaa oio aaa oio aaa o
  aaaaa iio aaaa iio aaaa iio aaaa oio aaa oio aaa oio aaa oio aaa oio aaa
 io i

 oiai input ao iiai oa i
 oiiaoaia ai iaii o input ia i
 oiiaoiaa ai oiao count oo ooooo i count aa iiai  i count iioiio ia oi
  oiiaoiai ai flag ao count oa aa input ao count oa ia oi
   oiiaoaii ai aiaia ia i
   a aaa i
  io
 io

 oiiaoaii ai aiaio ia i
 a ooooo i

io

#ifndef CAT_H
#define CAT_H

#define oiiaoiia main()
#define oiiaoaia scanf
#define oiiaoaii printf
#define oiiaoiaa for
#define oiiaoiai if

#define o ,
#define i ;
#define a return
#define oi {
#define io }
#define ao [
#define oa ]
#define ai (
#define ia )

#define oo =
#define aa !=

#define iio +  
#define iioiio ++
#define iii  * 
#define oio - 

#define oiai char
#define oiao int
#define iaii "%44c"

#define ooooo 0
#define aaa 1
#define aaaa 10
#define aaaaa 100
#define iiai 44

#define aiaia "wrong.\n"
#define aiaio "correct :)\n"


#endif

solver

gccでコンパイルしたのちstringsもしくはデコンパイラを使って見つけることが出来ます
GDBでmainの中身を見ていくと0x1151あたりから0x7b46544379733445({FTCys4E)が出てくるのでこの部分に埋め込まれている事が分かります

E4syCTF{OIIA-OIIA_oII4-0114_c4t_i5_5pinnin9}

Common Language(Reversing)

exeファイルが配布されるので解析する問題

solver

メモ帳か何かで強引に開くと「Console Write ReadLine」と断片的にdotnetの文法が出てきます。
dotnetのデコンパイラであるdnSpyで開くとすぐにflagが表示されます

E4syCTF{d0tn3t_h4s_4_CLR_50_634utifu1...}

最後に

3問全てに共通して言える事として問題の質がかなり低かったように感じます…(ぽちさんごめんなさい)
その攻撃手法をﾁｮｯﾄﾜｶﾙようにならないと作問はできないので修業します…
E4syCTFに参加していただきありがとうございました！！