# CSAW CTF Qual 2021

## Forgery (127 solves, 405pts)

Felicity and Cisco would like to hire you as an intern for a new security company that they are forming. They have given you a black box signature verification system to test out and see if you can forge a signature. Forge it and you will get a passphrase to be hired!

:::spoiler **Source Code**

from Crypto.Util.number import getPrime
from random import randint
from math import gcd

with open("flag.txt",'r') as f:
	flag = f.read()

p = getPrime(1024)
g = 3
MASK = 2**1024 - 1

def gen_keys():
	x = randint(1, p-2)
	y = pow(g, x, p)
	return (x, y)

def sign(answer: str, x: int):
	while True:
		m = int(asnwer, 16) & MASK
		k = randint(2, p-2)
		if gcd(k, p - 1) != 1:
			continue 
		r = pow(g, k, p)
		s = (m - x*r) * pow(k,-1,p-1) % (p - 1)
		if s == 0:
			continue
		return (r,s)

def verify(answer: str, r: int, s: int, y: int):
	m = int(answer, 16) & MASK
	if any([x <= 0 or x >= p-1 for x in [m,r,s]]):
		return False
	return pow(g, m, p) == (pow(y, r, p) * pow(r, s, p)) % p

def main():
	x, y = gen_keys()
	print(f"Server's public key (p,g,y): {p} {g} {y}")
	print("Who do you think is the tech wizard: Felicity or Cisco or both? Please answer it with your signnature (r,s)")
	print('Answer: ')
	answer = input()
	print('r: ')
	r = int(input())
	print('s: ')
	s = int(input())
	answer_bytes = bytes.fromhex(answer)

	if b'Felicity' not in answer_bytes and b'Cisco' not in answer_bytes and b'both' not in answer_bytes:
		print("Error: the answer is not valid!")
	elif verify(answer, r, s, y):
		if b'Felicity' in answer_bytes:
			print("I see you are a fan of Arrow!")
		elif b'Cisco' in answer_bytes:
			print("I see you are a fan of Flash!")
		else:
			print("Brown noser!")
		print(flag)
	else:
		print("Error: message does not match given signature")

if __name__ == "__main__":
	main()

:::

### Overview

The server asks you to provide a tuple $(m, r, s)$ such that the corresponding bytes of $m$ contains a keyword and $$ g^{m \pmod{2^{1024}}} \equiv y^r \times r^s \pmod{p} $$

### Valid Signature Forgery

First of all, we need to find, at least, a valid tuple $(m, r, s)$. However, computing the discrete log of $y$ seems impossible. Notice that the constructable power of $y$ is $1$, a reasonable choice of $(r,s)$ is $$ (y, \quad -y \pmod{p-1}) $$

Now, for LHS, we need $0 < m < p-1$ with $g^{m} \equiv 1 \pmod{p}$. One may take $m = \frac{p-1}{2}$ and hope it works :D

### Sign Message Containing Given Keyword

This is quite straightforward. Because the server only cares the residue of $m$ divided by $2^{1024}$, we simply change our $m$ to $$ Cisco \times 2^{1064} + \frac{p-1}{2} $$

### Capture the Flag

if pow(g, (p-1) // 2, p) != 1:
        r.close()
        print("3 is primitive root of p G_G")
        exit()

answer = (p-1) // 2 + bytes_to_long(b"Ciscoo" + b"\x00" * 133)

r.sendline(hex(answer)[2:])
r.sendline(str(y))
r.sendline(str(p-1-y))

r.recvuntil("I see you are a fan of Flash!")
r.recvline()

flag = r.recvline()
print(flag)

:::success
flag{7h3_4rr0wv3r53_15_4w350M3!}
:::

## ECC Pop Quiz (63 solves, 478 pts)

Your crypto professor has taught y'all about ECC and now, here's a pop quiz regarding some of the attacks on it. See if you can pass the quiz!

### Overview

1. Smart Attack
2. Moving Attack
3. Singular Curve

### Capture the Flag

:::success
flag{4Ll_0f_tH353_4tT4cK5_R3lY_0N_51mPl1FY1n9_th3_D15cr3t3_l09_pr08l3m}
:::

## Bits (24 solves, 497 pts)

I wrote this oracle in rust so that it can't sue companies over java stuff.

:::spoiler **Source Code**

use std::io::BufRead;
use getrandom::getrandom;
use rug::{
    rand::{RandGen,RandState},
    Integer
};
use sha2::{Sha256,Digest};
use aes::{Aes256,Aes256Ctr,NewBlockCipher,cipher::{FromBlockCipher,StreamCipher}};
use generic_array::GenericArray;

// Secret sauce
// N = p*q; p ≡ q ≡ 3 (mod 4); p, q prime
use hardcore::{dlog, N, G, ORDER, FLAG};

struct SystemRandom;
impl RandGen for SystemRandom {
    fn gen(&mut self) -> u32 {
        let mut buf: [u8; 4] = [0; 4];
        let _ = getrandom(&mut buf).unwrap();
        ((buf[0] as u32) << 24) | ((buf[1] as u32) << 16) | ((buf[2] as u32) << 8) | (buf[3] as u32)
    }
}

fn encrypt_flag(shared: Integer) {
    let mut hasher = Sha256::new();
    hasher.update(shared.to_string());
    let key = hasher.finalize();
    let mut cipher = Aes256Ctr::from_block_cipher(
        Aes256::new_from_slice(&key.as_slice()).unwrap(),
        &GenericArray::clone_from_slice(&[0; 16])
        );
    let mut flag = FLAG.clone();
    cipher.apply_keystream(&mut flag);
    println!("FLAG = {}", flag.iter().map(|c| format!("{:02x}", c)).collect::<String>());
}

fn main() {
    println!("+++++++++++++++++++++++++++++++++++++++++++++++\n\
              + I hear there's a mythical oracle at Delphi. +\n\
              +++++++++++++++++++++++++++++++++++++++++++++++\n");
    let mut sysrng = SystemRandom;
    let mut rnd = RandState::new_custom(&mut sysrng);
    let d = Integer::from(&*ORDER).random_below(&mut rnd);
    let publ = Integer::from(&*G).pow_mod(&d, &*N).unwrap();
    let nbits = ORDER.significant_bits();
    let alice = Integer::from(&*G).pow_mod(&Integer::from(&*ORDER).random_below(&mut rnd), &*N).unwrap();
    println!("N = {}\nG = {}\npubl = {}\nalice = {}\nnbits = {}",
        *N,
        *G,
        publ,
        alice,
        nbits);
    encrypt_flag(alice.pow_mod(&d, &N).unwrap());
    for line in std::io::stdin().lock().lines() {
        let input = line.unwrap().parse::<Integer>().unwrap();
        match dlog(input.clone()) {
            None => println!("-1"),
            Some(x) => {
                assert!(G.clone().pow_mod(&x, &*N).unwrap() == input % &*N);
                assert!(x < *ORDER);
                assert!(x >= 0);
                println!("{}", x.get_bit(nbits - 123) as i32)
            }
        }
    }
}

:::

### Overview

The server uses static generator and modulus $g, N$ and generates two public keys $A, B$ as follows: $$ A = g^{r_1}, \quad B = g^{r_2} \pmod{N} $$

where $r_1, r_2$ are two random numbers. Then the server calculates the shared secret $$A^{r_2} = g^{r_1r_2} = B^{r_1} \pmod{N} $$ and use it to encrypt the flag by AES256 in CTR mode.

The server also provides a discrete-log oracle. For a given input $y$, it finds $x$ so that $$ g^{x} \equiv y \pmod{N} $$ If no such $x$, then it returns $-1$. Otherwise, it return $$ \begin{cases} 1 \quad & \textit{if} \quad x \& 2^{883} > 0 \\ 0 \quad & \textit{otherwise} \end{cases} $$

###

To decrypt the flag, it suffices find the secret exponent $r_1$. Notice that one may get a bit of $$r_1 + k \pmod{Ord_{N}(g)} $$ by sending $A \times g^{k} \pmod{N}$ to the oracle.

### Retrieve LSBs of $r_1$

Suppose the binary representation of $r_1$ is $b_{n}b_{n-1}\dots b_{0}$ or equivalently, $$ r_1 = \sum\limits_{i=0}^{n}{b_{i}\cdot 2^{i}} $$ Further, let $m$ be the smallest index such that $$ b_m \neq 0, \quad m > 883 $$ The key observation is $$ r_1 - \left(\sum\limits_{i=a+1}^{883}{b_i\cdot 2^{i}} + 2^{a}\right) = \begin{cases} \\ \\ \sum\limits_{i=m+1}^{1006}{b_i\cdot 2^{i}} + \sum\limits_{i=a}^{m-1}{\cdot 2^{i}} + \sum\limits_{i=0}^{a-1}{b_i\cdot 2^{i}} & \quad \textit{if} \quad b_a = 0 \\ \\ \sum\limits_{i=884}^{1006}{b_i\cdot 2^{i}} + \sum\limits_{i=0}^{a-1}{b_i\cdot 2^{i}} & \quad \textit{if} \quad b_a = 1 \end{cases} $$ So the oracle returns $1$ iff $b_{a} = 0$ and we can sequentially determine the lower bits of $r_1$

d_lsb = 0

for i in range(nbits - 123, -1, -1):
    k = d_lsb | (1 << i)
    payload = (A * pow(g, -k, N)) % N

    r.sendline(str(payload))

    _ = r.recvline()
    if b"0" in _:
        d_lsb |= (1 << i)

### Binary Search MSBs of $r_1$

Note that $$ Ord_{N}(g) \ \mid \ \phi(N) < N $$ We know that the bit-lengths of $Ord_{N}(g), N$ are $1006, 1007$, respectively. One may expect that $Ord_{N}(g)$ is exactly $\phi(N) = N - p - q + 1$ and it follows that the MSBs of $Ord_{N}(g)$ and that of $N$ are the same.

For convenience, we define two functions $MSBs$ and $LSBs$ by the following rules: $$ MSBs(x) = \left\lfloor\frac{x}{2^{884}}\right\rfloor, \quad LSBs(x) = x \pmod{2^{884}} $$

To apply binary search, we need to distinguish whether $MSBs(r_1)+MSBs(k)$ is larger than $MSBs(Ord_{N}(g))$. The following process will only work for the case that $883$-th bit of $Ord_{N}(g)$ equals to $0$.

We're going to find $MSBs(Ord_{N}(g))-MSBs(r_1)$ by binary search. Begin with bounds $L, H = 0, MSBs(Ord_{N}(g))$

* Each time, we send $$A \times g^{-LSBs(r_1)} \times g^{m \cdot 2^{884}} \pmod{N}$$ where $m=\lfloor\frac{L+H}{2}\rfloor$
* If $MSBs(r_1) + m \le MSB(Ord_{N}(g))$, then it's clear that the oracle returns $0$.
* Otherwise, the oracle returns the $883$-th bit of the following number $$ M = (MSBs(r_1)+m) \times 2^{884}-Ord_{N}(g) $$ which equals to $$ (MSBs(r_1)+m-MSBs(Ord_{N}(g))-1) \times 2^{884} + (2^{884}-LSBs(Ord_{N}(g))) $$ Assume the binary representation of $LSBs(Ord_{N}(g))$ is $c_{883}c_{882}\dots c_{0}$ Then $LSBs(M)$ is $$2^{884}-LSBs(Ord_{N}(g)) = \sum\limits_{i=0}^{883}(1-c_{i})\cdot 2^{i} + 1$$ Because $c_{883} = 0$, the oracle returns $1$
* Update $L, H$ according to the output

T = (A * pow(g, -d_lsb, N)) % N

L, H = 0, ord_msb

while L + 1 < H:

    mid = (L + H) // 2
    k = mid * (1 << (nbits - 123 + 1))
    payload = T * pow(g, k, N)

    r.sendline(str(payload))

    _ = r.recvline().strip()

    if b"1" in _:
        H = mid
    else:
        L = mid

d_msb = ord_msb - L

### Capture the Flag

So we have the secret exponent $$ r_1 = MSBs(r_1) \times 2^{884} + LSBs(r_1) $$ and the shared secret $$B^{r_1} \pmod{N} $$ Let's decrypt the ciphertext!

d = d_msb * (1 << (nbits - 123 + 1)) + d_lsb

shared_secret = pow(B, d, N)

Sha = hashlib.sha256()
Sha.update(str(shared_secret).encode('ascii'))
key = Sha.digest()

cipher = AES.new(key, AES.MODE_CTR, nonce = b"\x00" * 8)
flag = cipher.decrypt(encrypted_flag)
print(pt)

:::success
flag{https://www.youtube.com/watch?v=uhTCeZasCmc}
:::