CTF-Training-Record-2

GXYCTF2019 - CommonModulusAttack

[题目考点]

• Java nextInt() using Truncated LCG

[题目文件]

Click Here to Download

[题解分析]

并不知道和题目名字有什么关系- -

public static void main(String[] paramArrayOfString)
{
  CommonModulusAttack localCommonModulusAttack = new CommonModulusAttack();
  localCommonModulusAttack.oldtest();
  localCommonModulusAttack.initseed();
  localCommonModulusAttack.gen_states();
  for (int i = 0; i < 24; i++) {
    localCommonModulusAttack.lrandout();
  }
  try
  {
    PrintWriter localPrintWriter = new PrintWriter("new.txt", "UTF-8");
    for (int j = 0; j < 24; j++) {
      localPrintWriter.println(byte2hex(localCommonModulusAttack.lrandout()));
    }
    localPrintWriter.close();
  }
  ...

关键代码

// key code (oldtest)
PrintWriter localPrintWriter = new PrintWriter("old.txt", "UTF-8");
for (int i = 0; i < 20; i++)
{
  int j = this.random.nextInt();
  localPrintWriter.println(j);
}
localPrintWriter.close();

// key code (initseed)
Scanner localScanner = new Scanner(Paths.get("flag", new String[0]), "UTF-8");
String str1 = localScanner.next();
String str2 = convert_2_binary(str1);
this.seed = str2; // so what we need is `this.seed`

// key code (generate_init_state)
BigInteger localBigInteger = BigInteger.valueOf(0L);
char[] arrayOfChar1 = this.seed.toCharArray(); // seed's first encryption
for (int k : arrayOfChar1) {
  localBigInteger = localBigInteger.shiftLeft(1);
  if (k == 49) { // k == '1'
    localBigInteger = localBigInteger.xor(new BigInteger(this.seed, 2));
  }
  if (localBigInteger.shiftRight(256) != BigInteger.ZERO) {
    localBigInteger = localBigInteger.xor(new BigInteger("10000000000000000000000000000000000000000000000000000000000000223", 16));
  }
}
return localBigInteger;

// key code (gen_states)
BigInteger localBigInteger1 = generate_init_state(); // what we want(seed after first encryption)
BigInteger localBigInteger2 = BigInteger.valueOf(17L); // param e in RSA
ArrayList localArrayList1 = new ArrayList(24);
ArrayList localArrayList2 = new ArrayList(24);
for (int i = 0; i < 24; i++) {
  BigInteger localBigInteger3 = BigInteger.probablePrime(512, this.random); // p
  BigInteger localBigInteger4 = BigInteger.probablePrime(512, this.random); // q
  BigInteger localBigInteger5 = localBigInteger3.multiply(localBigInteger4); // n
  BigInteger localBigInteger6 = localBigInteger1.modPow(localBigInteger2, localBigInteger5); // c
  localArrayList1.add(localBigInteger5);
  localArrayList2.add(localBigInteger6);
}
try {
  PrintWriter localPrintWriter = new PrintWriter("product", "UTF-8");
  for (int j = 0; j < 24; j++) {
    localPrintWriter.println(((BigInteger)localArrayList1.get(j)).toString());
    this.states.add(localArrayList2.get(j)); // states storing seed after second encryption(RSA)
  }
  localPrintWriter.close();
}

// key code (lrandout)
if (this.stateselse > 0) { // stateselse's initiation is 24
  this.stateselse -= 1;
  BigInteger localBigInteger = (BigInteger)this.states.get(this.statespoint);
  this.statespoint += 1;
  return stateconvert(localBigInteger); // return seed after third encryption(AES)
} // stateconvert contains `encrypt` function
gen_new_states();
return lrandout();

// key code (gen_new_states)
for (int i = 0; i < 24; i++) {
  BigInteger localBigInteger = (BigInteger)this.states.get(this.statespoint - 24 + i); 
  byte[] arrayOfByte = encrypt(localBigInteger);    
  this.states.add(new BigInteger(arrayOfByte));
}
this.stateselse += 24;

// key code (encrypt)
IvParameterSpec localIvParameterSpec = new IvParameterSpec(new byte[16]);
byte[] arrayOfByte1 = new byte[16];
this.random.nextBytes(arrayOfByte1); // using random.nextBytes to genKey for AES
SecretKeySpec localSecretKeySpec = new SecretKeySpec(arrayOfByte1, "AES");
Cipher localCipher = Cipher.getInstance("AES/CBC/NoPadding");
// AES encrypt part

加密链

oldtest先调用了20次java的nextInt()

this.seed经过$GF(2^{256})$下的平方运算后生成state

state通过RSA part生成的24组$(p,q),e=17$，加密得到this.states (len(states == 24))

lrandout先AES/CBC完整加密了一次this.states的24个值，但该次并未更新this.states

由于this.stateselse此时为0，因此执行lrandout会先新生成24个state（即调用gen_new_states）

在旧states后新增一长度为24的states后，用新增的states加密得到的结果即为new.txt中内容

攻击思路

a, b, m均已知，且hidden length仅为16bits的Truncated LCG，直接爆破PRNG_seed的hidden部分即可

得到PRNG_seed后，加密源码后续中所有生成的随机数均可预测

而用到随机数生成的有$p,q$生成及$AES_Encryption$中的genKey

加密部分最后的两次lrandout，再加上其中间的gen_new_states，共调用了三次encrypt（72次AES/CBC的Genkey）

因此所有过程可控，恢复即可

[exp]

SeedAttack.java

public class SeedAttack {
    private long a = 0x5deece66dL;
    private long b = 11L;
    private long m = 0xffffffffffffL;

    public long crack_seed(long d1, long d2) throws Exception {
        for (int i = 0; i <= 0xffff; i++) {
            long seed = (d1 << 16) + i;
            long guess_d2 = (a * seed + b & m) >>> 16;
            if (guess_d2 == d2) {
                System.out.println("[+] PRNG's seed: " + String.valueOf(seed));
                return seed;
            }
        }
        throw new Exception("[!] PRNG crack failed!");
    }

//    public static void main(String[] args) {
//        SeedAttack localSeedAttack = new SeedAttack();
//        long d1 = -1029728314L;
//        long d2 = 1487023297L;
//        try {
//            long seed = localSeedAttack.crack_seed(d1, d2);
//            System.out.println(seed);
//        } catch (Exception e) {
//            System.out.println(e.getMessage());
//        }
//    }
}

CMA.java

import java.util.Random;
import java.io.PrintWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.math.BigInteger;

public class CMA {
    private Random random = new Random();

    public CMA() {
        long PRNG_seed = 0L;
        SeedAttack localSeedAttack = new SeedAttack();
        long d1 = -1029728314L;
        long d2 = 1487023297L;
        try {
            PRNG_seed = localSeedAttack.crack_seed(d1, d2);
//            System.out.println(PRNG_seed);
        } catch (Exception e) {
            System.out.println(e.getMessage());
        }
        this.random.setSeed(PRNG_seed ^ 0x5DEECE66DL);
    }
    // discard trash which generate old.txt
    public void discardTrash() {
        for (int i = 0; i < 19; i++) {
            int j = this.random.nextInt();
        }
    }

    public void genRSA() {
        BigInteger e = BigInteger.valueOf(17L);
        ArrayList<ArrayList> RSA_params = new ArrayList<ArrayList>(24);
        for (int i = 0; i < 24; i++) {
            ArrayList curRSAparams = new ArrayList(2);
            BigInteger p = BigInteger.probablePrime(512, this.random);
            BigInteger q = BigInteger.probablePrime(512, this.random);
            curRSAparams.add(p);
            curRSAparams.add(q);
            RSA_params.add(curRSAparams);
        }
        try {
            PrintWriter localPrintWriter = new PrintWriter("prikey", "UTF-8");
            for (int i = 0; i < 24; i++) {
                ArrayList curRSAparams = RSA_params.get(i);
                String p = curRSAparams.get(0).toString();
                String q = curRSAparams.get(1).toString();
                localPrintWriter.println("(" + p + ", " + q + ")");
            }
            System.out.println("[+] RSA's priKey found");
            localPrintWriter.close();
        } catch (IOException error) {
            error.printStackTrace();
        }
    }

    public static String byte2hex(byte[] paramArrayOfByte)
    {
        StringBuffer localStringBuffer = new StringBuffer(paramArrayOfByte.length * 2);
        for (int i = 0; i < paramArrayOfByte.length; i++)
        {
            if ((paramArrayOfByte[i] & 0xFF) < 16) localStringBuffer.append("0");
            localStringBuffer.append(Long.toString(paramArrayOfByte[i] & 0xFF, 16));
        }
        return localStringBuffer.toString();
    }

    public void genKey() {
        try {
            PrintWriter localPrintWriter = new PrintWriter("AESkey", "UTF-8");
            for (int i = 0; i < 72; i++) {
                byte[] key = new byte[16];
                this.random.nextBytes(key);
                localPrintWriter.println(byte2hex(key));
            }
            System.out.println("[+] AES's key found");
            localPrintWriter.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public static void main(String[] args) {
        CMA exp = new CMA();
        exp.discardTrash();
        exp.genRSA();
        exp.genKey();
    }
}

exp.py

import re
from Crypto.Cipher import AES
from binascii import unhexlify
from Crypto.Util.number import *

def getData():
    pqs = []
    with open('prikey', 'r') as fRSA:
        for line in fRSA:
            pq = re.findall(r"\((.*), (.*)\)", line)[0]
            pqs.append((int(pq[0]), int(pq[1])))
    with open('AESkey', 'r') as fAES:
        key = [unhexlify(line.strip()) for line in fAES]
        key = [key[:24], key[24:48], key[48:]]
    with open('new.txt', 'r') as fCIPHER:
        cipher = [unhexlify(line.strip()) for line in fCIPHER]
    return pqs, key, cipher

def dec1(p, q, c, key1, key2):
    aes2 = AES.new(key2, AES.MODE_CBC, iv=b"\x00"*16)
    c = aes2.decrypt(c)
    aes1 = AES.new(key1, AES.MODE_CBC, iv=b"\x00"*16)
    c = bytes_to_long(aes1.decrypt(c))
    e = 17
    n = p * q
    phi = (p - 1) * (q - 1)
    d = inverse(e, phi)
    m = pow(c, d, n)
    return m

def mul(x):
    a = 0
    for i in bin(x)[2:]:
        a = a << 1
        if (int(i)):
            a = a ^ x
        if a >> 256:
            a = a ^ 0x10000000000000000000000000000000000000000000000000000000000000223
    return a

def dec2(m):
    while True:
        m = mul(m)
        if b"flag" in long_to_bytes(m):
            print(long_to_bytes(m))
            break

def main():
    pqs, key, cipher = getData()
    m = dec1(pqs[0][0], pqs[0][1], cipher[0], key[1][0], key[2][0])
    dec2(m)

if __name__ == '__main__':
    main()

# b'flag{86824087489918371343860652}'

[GxzyCTF2020 - HNP]

[题目考点]

• Hidden Number Problem

[题目文件]

Click Here to Download

[题解分析]

$q\rightarrow 128bits,\quad p\rightarrow 1024bits,\quad q\mid (p-1)$

$g=2^{\frac{p-1}{q}}mod\ p,\quad x\rightarrow priKey,\quad y=g^{x}mod\ p\rightarrow pubKey$

签名: $r=(g^{k}mod\ p)mod\ q,\quad s=k^{-1}(H(m)+xr)mod\ q$

变形可得：$s^{-1}(H(m)+xr)\equiv k(mod\ q)$

假设k存在上界K，则有$|s^{-1}H(m)+(s^{-1}r)x|<K(mod\ q)$

令$A=s^{-1}H(m),\quad B=s^{-1}r$，可建立如下格基：

$$\left[ \begin{matrix} q & ... & ... & 0 & 0 & 0\\ 0 & q & ... & 0 & 0 & 0\\ ... & ... & ... & ... & ... & ...\\ 0 & 0 & ... & q & 0 & 0\\ B_{1} & B_{2} & ... & B_{n} & a & 0\\ A_{1} & A_{2} & ... & A_{n} & 0 & b \end{matrix} \right]$$

下对参数$a,b$取值进行估计$(K=2^{121},n=35)$：

需令$[k_{1},k_{2},…,k_{n},ax,b]$为SVP目标向量

$2^{\frac{n+1}{4}}(q^{n}ab)^{\frac{1}{n+2}}>\sqrt{nK^{2}+(ax)^{2}+b^{2}}$

$2^{18}2^{128\cdot \frac{70}{37}}(ab)^{\frac{2}{37}}>35\cdot 2^{242}+2^{256}a^{2}+b^{2}$

放缩为$2^{260}(ab)^{\frac{2}{37}}>2^{251}+2^{256}a^{2}+b^{2}$

显然在$ab=1$时，令$a=\frac{1}{2^{64}},b=2^{64}$，即明显满足上述不等式（$2^{128}a=b$）

本地作测试：

from hashlib import sha256
from Crypto.Util.number import *

# genKey for DSA
q = getPrime(128)
while True:
    t = getRandomNBitInteger(1024 - 128 - 1)
    p = (t * 2*q + 1)
    if isPrime(p):
        break
e = (p - 1) // q
g = pow(2, e, p)
x = getRandomRange(1, q - 1)
y = int(pow(g, x, p))

def sign(Hm):
    k = getRandomRange(1, 2**121)
    r = int(pow(g, k, p)) % q
    s = (inverse(k, q) * (Hm + x * r)) % q
    return r, s

def crack_x():
    M_list = []
    for i in range(35):
        M_list.append([q * int(i == j) for j in range(37)])
    Hm = int.from_bytes(sha256(b"0xDktb").digest(), 'big')
    As = []
    Bs = []
    for i in range(35):
        r, s = sign(Hm)
        A = (inverse(s, q) * Hm) % q
        B = (inverse(s, q) * r) % q
        As.append(A)
        Bs.append(B)
    Bs = Bs + [1/(2**64), 0]
    As = As + [0, 2**64]
    M_list.append(Bs)
    M_list.append(As)
    M = Matrix(QQ, M_list)
    ML = M.LLL()
    for line in ML:
        if line[-1] == (2**64):
            prikey = (line[-2] * (2**64)) % q
            print("[+] SVP's solution found! prikey = {}".format(prikey))
            return prikey

for i in range(32):
    if x != crack_x():
        print("Failed")

在$K=2^{121},n=35$时，测试成功率可视作100%，但令$K=2^{122}$时，虽然界仍满足，但是成功率有亿点点低（迷惑行为

因此远程获取$k_bits<122$的35组签名数据，即可破解私钥x，本地生成admin的签名，实现越权

[exp]

from sys import argv
from hashlib import sha256
from Crypto.Util.number import *
from binascii import hexlify, unhexlify
from pwn import *
from pwnlib.util.iters import mbruteforce

# context.log_level = 'debug'
# io = remote(argv[1], argv[2])
io = remote("47.115.135.229", "10000")


def proof_of_work():
    io.recvuntil("sha256")
    msg = io.recvline().strip().decode()
    suffix = unhexlify(re.findall(r"XXX \+ ([^\)]+)", msg)[0]).decode("latin-1")
    cipher = re.findall(r"== ([^\n]+)", msg)[0]
    proof = mbruteforce(lambda x: sha256((x + suffix).encode("latin-1")).hexdigest() ==
                        cipher, bytes(range(256)).decode("latin-1"), length=3, method='fixed')
    io.sendlineafter("Give me XXX in hex: ", hexlify(proof.encode("latin-1")))


def get_dsa_params():
    params = io.recvuntil("exit\n").strip().decode()
    p = int(re.findall(r"p = ([0-9]*?)\n", params)[0])
    q = int(re.findall(r"q = ([0-9]*?)\n", params)[0])
    g = int(re.findall(r"g = ([0-9]*?)\n", params)[0])
    y = int(re.findall(r"y = ([0-9]*?)\n", params)[0])
    return {"p":p, "q":q, "g":g, "y":y}


def sign(m):
    io.sendlineafter("$ ", "1")
    io.sendlineafter("Please input your username: ", m)
    io.recvuntil("k.bit_length() == ")
    kbits = int(io.recvline().strip().decode())
    io.recvuntil("Here is your signature in hex: ")
    sig = io.recvline().strip().decode("latin-1")
    r = int(sig[2*len(m):2*(len(m)+20)], 16)
    s = int(sig[2*(len(m)+20):], 16)
    return r, s, kbits


def login_as_admin(pubkey, prikey):
    g, p, q, x = pubkey['g'], pubkey['p'], pubkey['q'], prikey
    k = 114514
    Hm = int.from_bytes(sha256(b"admin").digest(), 'big')
    r = int(pow(g, k, p)) % q
    s = (inverse(k, q) * (Hm + x*r)) % q
    payload = hexlify(b"admin" + long_to_bytes(r).rjust(20, b"\x00") + long_to_bytes(s).rjust(20, b"\x00"))
    io.sendlineafter("$ ", "2")
    io.sendlineafter("Please send me your signature: ", payload)
    io.interactive()


def crack_x(pubkey):
    q, g = pubkey['q'], pubkey['g']
    M_list = []
    for i in range(35):
        M_list.append([q * int(i == j) for j in range(37)])
    m = b"0xDktb"
    Hm = int.from_bytes(sha256(m).digest(), 'big')
    As = []
    Bs = []
    i = 0
    while i < 35:
        r, s, kbits = sign(m)
        if kbits > 121:
            continue
        A = (inverse(s, q) * Hm) % q
        B = (inverse(s, q) * r) % q
        As.append(A)
        Bs.append(B)
        i += 1
        print("[{:0>2d}] k({} bits) found!".format(i, kbits))
    Bs = Bs + [1/(2**64), 0]
    As = As + [0, 2**64]
    M_list.append(Bs)
    M_list.append(As)
    M = Matrix(QQ, M_list)
    ML = M.LLL()
    for line in ML:
        if line[-1] == (2**64):
            prikey = (line[-2] * (2**64)) % q
            print("[+] SVP's solution found! prikey = {}".format(prikey))
            return prikey


def main():
    proof_of_work()
    pubkey = get_dsa_params()
    prikey = crack_x(pubkey)
    context.log_level = 'debug'
    login_as_admin(pubkey, prikey)


if __name__ == '__main__':
    main()
    
'''
dktb@ubuntu:/mnt/hgfs/share/HNP$ sage -¾","m!\x7f" -- 44.596%
                           z¼","ð}","*>","'¿" -- 54.467%
[+] MBruteforcing: Found key: "Ã"
[01] k(121 bits) found!
[02] k(121 bits) found!
[03] k(120 bits) found!
[04] k(121 bits) found!
[05] k(117 bits) found!
[06] k(121 bits) found!
[07] k(121 bits) found!
[08] k(120 bits) found!
[09] k(121 bits) found!
[10] k(121 bits) found!
[11] k(115 bits) found!
[12] k(121 bits) found!
[13] k(119 bits) found!
[14] k(120 bits) found!
[15] k(121 bits) found!
[16] k(121 bits) found!
[17] k(118 bits) found!
[18] k(120 bits) found!
[19] k(121 bits) found!
[20] k(121 bits) found!
[21] k(120 bits) found!
[22] k(121 bits) found!
[23] k(121 bits) found!
[24] k(121 bits) found!
[25] k(121 bits) found!
[26] k(118 bits) found!
[27] k(121 bits) found!
[28] k(116 bits) found!
[29] k(121 bits) found!
[30] k(121 bits) found!
[31] k(120 bits) found!
[32] k(118 bits) found!
[33] k(121 bits) found!
[34] k(121 bits) found!
[35] k(121 bits) found!
[+] SVP's solution found! prikey = 72250087844423678254657706833192856476
[DEBUG] Sent 0x2 bytes:
    b'2\n'
[DEBUG] Received 0x1f bytes:
    b'Please send me your signature: '
[DEBUG] Sent 0x5b bytes:
    b'61646d696e000000005f97da6d7e9faf6a182ff43f3cb4bd1000000000b5a29a7038325fee75abbf8372eccece\n'
[*] Switching to interactive mode
[DEBUG] Received 0x67 bytes:
    b'Welcome, admin\n'
    b'The flag is flag{25903ADB-15B6-44D7-A027-CAE500675EA5}\n'
    b'\n'
    b'1. sign up\n'
    b'2. sign in\n'
    b'3. exit\n'
    b'$ '
Welcome, admin
The flag is flag{25903ADB-15B6-44D7-A027-CAE500675EA5}
'''

[b01lers2020 - Des-MMXX]

[题目考点]

seed = b'secret_sauce_#9'   

def keygen(s):
   keys = []
   for i in range(2020):
      s = sha256(s).digest()
      keys.append(s)
   return keys

keys = keygen(seed)

2020个keys均已知，关注以下加密逻辑：

SECRET = 0xa########e          # remember to erase this later..

def scramble(s):
   ret = "".join( [format(s & 0xfffff, '020b')]*101 )
   ret += "".join( [format(s >> 20, '020b')]*101 )
   return int(ret, 2)
 
def encrypt(keys, msg):
   dk = scramble(SECRET)
   for v in keys:
      idx = dk & 3
      dk >>= 2
      k = v[idx*8:(idx+1)*8]
      cp = DES.new(k, DES.MODE_CBC, bytes(8))  
      msg = cp.encrypt(msg)
   return msg

with open("flag.txt", "rb") as f:
   msg = f.read()

ctxt = encrypt(keys, msg)

scramble使SECRET割裂成了两个20bits，并各自重复101次，在encrypt开头形成4040bits的dk

很明显的中间相遇攻击的逻辑，但buu缺了一对明密文条件…人傻了

于是上ctftime上找了官方仓库里原有的那对明密文，拿到以后直接MEET IN THE MIDDLE即可

[exp]

from hashlib import sha256
from Crypto.Cipher import DES
from tqdm import tqdm

seed = b'secret_sauce_#9'

def keygen(s):
   keys = []
   for i in range(2020):
      s = sha256(s).digest()
      keys.append(s)
   return keys

keys = keygen(seed)

upper_key = keys[1010:][::-1]
lower_key = keys[:1010]
upper_dk = 0x0000e
lower_dk = 0xa0000
pt = b"Attack at DAWN!!"
ct = b"\x15\x08\x54\xff\x3c\xf4\xc4\xc0\xd2\x3b\xd6\x8a\x82\x34\x83\xbe"

orig_ct = ct
upper_side = []
for ud in tqdm(range(0x10000)):
    guess_upper_dk = format((ud << 4) + upper_dk, '020b')
    for i in range(1010):
        _ = (i * 2) % 20
        idx = int(guess_upper_dk[_:_+2], 2)
        k = upper_key[i][idx*8:idx*8+8]
        des = DES.new(k, DES.MODE_CBC, bytes(8))
        ct = des.decrypt(ct)
    upper_side.append(ct)
    ct = orig_ct
'''
100%|████████████████████████████████████████████████████████████████████████████| 65536/65536 [19:31<00:00, 55.93it/s]
'''
orig_pt = pt
lower_side = []
for ld in tqdm(range(0x10000)):
    guess_lower_dk = format(ld + lower_dk, '020b')
    for i in range(1010):
        _ = 18 - ((i * 2) % 20)
        idx = int(guess_lower_dk[_:_+2], 2)
        k = lower_key[i][idx*8:idx*8+8]
        des = DES.new(k, DES.MODE_CBC, bytes(8))
        pt = des.encrypt(pt)
    lower_side.append(pt)
    pt = orig_pt
'''
100%|████████████████████████████████████████████████████████████████████████████| 65536/65536 [19:33<00:00, 55.85it/s]
'''
crash = list(set(upper_side) & set(lower_side))[0]
ud = upper_side.index(crash)
ld = lower_side.index(crash)
SECRET = int(format(ld + lower_dk, '020b') + format((ud << 4) + upper_dk, '020b'), 2)
enc_flag = open("flag.enc", "rb").read()

def scramble(s):
   ret = "".join( [format(s & 0xfffff, '020b')]*101 )
   ret += "".join( [format(s >> 20, '020b')]*101 )
   return int(ret, 2)

dk = scramble(SECRET)
dk = format(dk, '04040b')
i = 0
for v in keys[::-1]:
    idx = int(dk[i:i+2], 2)
    k = v[idx*8:(idx+1)*8]
    des = DES.new(k, DES.MODE_CBC, bytes(8))
    enc_flag = des.decrypt(enc_flag)
    i += 2
enc_flag
# b'pctf{Two_tO_thE_s1xt33n7h?_E4sy-p3asy..}'