# WU KMACTF 2023
## Crypto
### Schnorr
chal.py

import random
import time
from flag import FLAG

p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
g = 0x2
q = 0x7fffffff800000008000000000000000000000007fffffffffffffffffffffff
assert pow(g, q, p) == 1


def challenge(rounds=64):
    random.seed(int(time.time()))
    x = int.from_bytes(FLAG, "big")
    y = pow(g, x, p)
    print("Prove you know x, such that pow({0}, x, {1}) == {2}".format(g, p, y))
    try:
        for i in range(rounds):
            print("[+] Round {0}/{1}".format(i+1, rounds))
            t = int(input("t = "))
            c = random.randint(1, q-1)
            print("c = {0}".format(c))
            s = int(input("s = "))
            if pow(g, s, p) == (t*pow(y, c, p)) % p:
                continue
            else:
                return False
    except:
        return False

    return True


if __name__ == "__main__":
    is_verified = challenge()
    if is_verified:
        print(FLAG)
    else:
        print("Better luck next time, hackers!")

https://en.wikipedia.org/wiki/Proof_of_knowledge#Schnorr_protocol
- Trong chall này thì sử dụng Schnorr protocol, và yêu cầu nhập `t` và `s` thỏa mãn điều kiện để vượt qua thử thách 64 lần để đạt được flag.
- Để thỏa điều kiện `pow(g, s, p) == (t * pow(y, c, p)) % p` thì mình chọn s bằng bất kì số nào từ `(1,p-1)` và tính `t`= y^-c từ `c` đoán được từ `random.seed(int(time.time()))`.

solved.py:

from pwn import *
import random
import time
p = 115792089210356248762697446949407573530086143415290314195533631308867097853951
g = 2
q = 57896044605178124381348723474703786765043071707645157097766815654433548926975
y = 61252110398173126436323285216974857619112851968123774381188703220254043681646


r=remote("103.163.25.143",60124)
random.seed(int(time.time()))

data = r.recv()
print(data)
s=p-1
for i in range(64):
    c = random.randint(1, q-1)
    t=pow(y,-c,p)
    r.sendline(str(t).encode())
    print(r.recv().decode())
    r.sendline(str(s).encode())
    print(r.recv().decode())
r.interactive()

### SSS Voting I
main.go:

package main

import (
	"encoding/hex"
	"fmt"
	"log"
	"math/big"
	"math/rand"
	"net"
	"os"
)

const (
	HOST = "localhost"
	PORT = "1337"
	TYPE = "tcp"
	FLAG = "KMACTF{flag}"
)

func tamper(conn net.Conn, original []*big.Int) {
	conn.Write([]byte("Original votes (each vote is encoded in 64 hex characters):\n"))
	for _, ori := range original {
		buf := make([]byte, 32)
		ori.FillBytes(buf)
		conn.Write([]byte(hex.EncodeToString(buf)))
	}

	conn.Write([]byte("\nTampered votes:\n"))
	buf := make([]byte, 64*len(original))
	_, err := conn.Read(buf)
	if err != nil {
		conn.Close()
		return
	}

	for idx, tamper := range original {
		_, ok := tamper.SetString(string(buf[idx*64:idx*64+64]), 16)
		if !ok {
			conn.Close()
			return
		}
	}
}

func main() {
	listen, err := net.Listen(TYPE, HOST+":"+PORT)
	if err != nil {
		log.Fatal(err)
		os.Exit(1)
	}
	// close listener
	defer listen.Close()
	for {
		conn, err := listen.Accept()
		if err != nil {
			log.Fatal(err)
			os.Exit(1)
		}
		go handleRequest(conn)
	}
}

func handleRequest(conn net.Conn) {
	n := 10 // number of voters
	k := 5  // number of authorities
	t := 2  // `threshold` the scheme requires t + 1 honest authorities to derive the final result

	conn.Write([]byte("[+] Public ID of available authorities:\n"))
	authorities := make([]*authority, k)
	for i := 0; i < k; i++ {
		authorities[i] = init_authority()
		conn.Write([]byte(fmt.Sprintf("%d\n", authorities[i].id)))
	}

	voters := make([]*voter, n)
	for i := 0; i < n; i++ {
		voters[i] = init_voter(t, rand.Intn(2) == 1)
		voters[i].votes = make([]*big.Int, k)
		for j := 0; j < k; j++ {
			voters[i].votes[j] = voters[i].eval(authorities[j].id)
		}
	}

	conn.Write([]byte("[+] One voter is being hacked.\n"))
	tamper(conn, voters[0].votes)

	// voters send votes to authorities
	for i := 0; i < k; i++ {
		votes := make([]*big.Int, n)
		for j := 0; j < n; j++ {
			votes[j] = voters[j].votes[i]
		}
		authorities[i].votes = votes
	}

	rand.Shuffle(len(authorities), func(i, j int) {
		authorities[i], authorities[j] = authorities[j], authorities[i]
	})

	ids := get_ids(authorities[:t+1])
	votes := get_votes(authorities[:t+1])
	result := lagrange_interpolate(ids, votes)

	if result.Cmp(big.NewInt(1337)) == 0 {
		conn.Write([]byte(fmt.Sprintf("[*] There are 1337 votes, seems like someone is hacking! :( The flag is %s\n", FLAG)))
	} else {
		if result.Cmp(big.NewInt(int64(n))) != 1 {
			conn.Write([]byte(fmt.Sprintf("[*] We got %d yes from everyone.\n", result)))
		} else {
			conn.Write([]byte(fmt.Sprintf("[*] We got %d yes. Suspicious...\n", result)))
		}
	}
	conn.Close()
}

operator.go:

package main

import (
	"crypto/rand"
	"math/big"
)

type (
	// voter will submit votes
	voter struct {
		poly  []*big.Int
		agree bool
		votes []*big.Int
	}

	// authority will count the votes
	authority struct {
		id    *big.Int
		votes []*big.Int
	}
)

// random polynomial of degree d
func init_voter(d int, agree bool) *voter {
	poly := make([]*big.Int, d+1)
	poly[0] = big.NewInt(0)
	if agree {
		poly[0] = big.NewInt(1)
	}

	for i := 1; i <= d; i++ {
		buf := make([]byte, 32)
		rand.Read(buf)
		poly[i] = new(big.Int).SetBytes(buf)
	}
	return &voter{poly: poly, agree: agree}
}

func init_authority() *authority {
	buf := make([]byte, 32)
	rand.Read(buf)
	return &authority{id: new(big.Int).SetBytes(buf)}
}

func (voter *voter) eval(authority_id *big.Int) *big.Int {
	p := new(big.Int).SetBytes([]byte{255, 255, 255, 255, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255})
	vote := big.NewInt(0)
	id := big.NewInt(1)
	for _, coef := range voter.poly {
		tmp := new(big.Int).Mul(coef, id)
		vote.Add(vote, tmp)
		id.Mul(id, authority_id)
		id.Mod(id, p)
	}
	vote.Mod(vote, p)
	return vote
}

func (authority *authority) count_votes() *big.Int {
	p := new(big.Int).SetBytes([]byte{255, 255, 255, 255, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255})
	result := big.NewInt(0)
	for _, vote := range authority.votes {
		result.Add(result, vote)
	}
	result.Mod(result, p)
	return result
}

func get_ids(authorities []*authority) []*big.Int {
	ids := make([]*big.Int, len(authorities))
	for i := 0; i < len(authorities); i++ {
		ids[i] = authorities[i].id
	}
	return ids
}

func get_votes(authorities []*authority) []*big.Int {
	votes := make([]*big.Int, len(authorities))
	for i := 0; i < len(authorities); i++ {
		votes[i] = authorities[i].count_votes()
	}
	return votes
}

func lagrange_interpolate(ids, votes []*big.Int) *big.Int {
	p := new(big.Int).SetBytes([]byte{255, 255, 255, 255, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255})
	if len(ids) != len(votes) {
		return nil
	}

	sum := big.NewInt(0)
	for i := 0; i < len(votes); i++ {
		tmp := votes[i]
		for j := 0; j < len(ids); j++ {
			if i != j {
				neg := new(big.Int).Neg(ids[j])
				neg.Add(neg, p)
				tmp.Mul(tmp, neg)
				neg.Add(neg, ids[i])
				neg.ModInverse(neg, p)
				tmp.Mul(tmp, neg)
			}
		}
		sum.Add(sum, tmp)
		sum.Mod(sum, p)
	}
	return sum
}

- Bài này cho hai file golang, hàm `handleRequest` nó tạo phiếu bầu từ các người bỏ phiếu và gửi cho các tổ chức đếm phiếu tương ứng. Hàm `tamper` được gọi để can thiệp vào phiếu bầu của một người bỏ phiếu cụ thể.
Yêu cầu chúng ta nhập vào một `Tampered votes` ,
nó sử dụng phương pháp nội suy Lagrange để khôi phục các giá trị votes ban đầu. Sau đó được so sánh với 1337 nếu bằng thì sẽ trả về flag.
- Việc của chúng ta là can thiệp vào số phiếu bầu sao cho thỏa điều kiện bằng 1337 số phiếu bầu.Để tính `Tampered votes` ta thực hiện phép tính `(votes + 1332) % (2 ** 256)` và gửi cho sever để nhận flag
solved.py:

while True:
    r = connect('103.163.25.143', 60125)

    p = 115792089210356248762697446949407573530086143415290314195533631308867097853951
    (r.recv())
    (r.recvline_startswith(b'Original votes '))
    votes = r.recvline().strip().decode()
    def compute_tampered_votes(votes):
        tampered = ''
        for i in range(5):
            tampered += str(hex((int(votes[:64], 16) + 1332)%(2**256))[2:].zfill(64))
            votes = votes[64:]
        return tampered

    tampered_votes = compute_tampered_votes(votes)
    # print(tampered_votes)
    (r.recv())
    r.send(tampered_votes.encode())
    flag=r.recv().decode()
    print(flag)
    if 'KMACTF' in flag:
        break
    r.close()

### SSS Voting II
main.go

package main

import (
	"encoding/hex"
	"fmt"
	"log"
	"math/big"
	"math/rand"
	"net"
	"os"
)

const (
	HOST = "localhost"
	PORT = "1337"
	TYPE = "tcp"
	FLAG = "KMACTF{flag}"
)

func tamper(conn net.Conn, original []*big.Int) {
	conn.Write([]byte("Original votes (each vote is encoded in 64 hex characters):\n"))
	for _, ori := range original {
		buf := make([]byte, 32)
		ori.FillBytes(buf)
		conn.Write([]byte(hex.EncodeToString(buf)))
	}

	conn.Write([]byte("\nTampered votes:\n"))
	buf := make([]byte, 64*len(original))
	_, err := conn.Read(buf)
	if err != nil {
		conn.Close()
		return
	}

	for idx, tamper := range original {
		_, ok := tamper.SetString(string(buf[idx*64:idx*64+64]), 16)
		if !ok {
			conn.Close()
			return
		}
	}
}

func main() {
	listen, err := net.Listen(TYPE, HOST+":"+PORT)
	if err != nil {
		log.Fatal(err)
		os.Exit(1)
	}
	// close listener
	defer listen.Close()
	for {
		conn, err := listen.Accept()
		if err != nil {
			log.Fatal(err)
			os.Exit(1)
		}
		go handleRequest(conn)
	}
}

func handleRequest(conn net.Conn) {
	n := 10 // number of voters
	k := 5  // number of authorities
	t := 2  // `threshold` the scheme requires t + 1 honest authorities to derive the final result

	conn.Write([]byte("[+] Public ID of available authorities:\n"))
	authorities := make([]*authority, k)
	for i := 0; i < k; i++ {
		authorities[i] = init_authority()
		conn.Write([]byte(fmt.Sprintf("%d\n", authorities[i].id)))
	}

	voters := make([]*voter, n)
	for i := 0; i < n; i++ {
		voters[i] = init_voter(t, rand.Intn(2) == 1)
		voters[i].votes = make([]*big.Int, k)
		for j := 0; j < k; j++ {
			voters[i].votes[j] = voters[i].eval(authorities[j].id)
		}
	}

	// voters send votes to authorities
	for i := 0; i < k; i++ {
		votes := make([]*big.Int, n)
		for j := 0; j < n; j++ {
			votes[j] = voters[j].votes[i]
		}
		authorities[i].votes = votes
	}

	rand.Shuffle(len(authorities), func(i, j int) {
		authorities[i], authorities[j] = authorities[j], authorities[i]
	})

	conn.Write([]byte(fmt.Sprintf("[+] Authority %d is being hacked.\n", authorities[0].id)))
	tamper(conn, authorities[0].votes)

	ids := get_ids(authorities[:t+1])
	votes := get_votes(authorities[:t+1])
	result := lagrange_interpolate(ids, votes)

	if result.Cmp(big.NewInt(1337)) == 0 {
		conn.Write([]byte(fmt.Sprintf("[*] There are 1337 votes, seems like someone is hacking! :( The flag is %s\n", FLAG)))
	} else {
		if result.Cmp(big.NewInt(int64(n))) != 1 {
			conn.Write([]byte(fmt.Sprintf("[*] We got %d yes from everyone.\n", result)))
		} else {
			conn.Write([]byte(fmt.Sprintf("[*] We got %d yes. Suspicious...\n", result)))
		}
	}
	conn.Close()
}

operator.go:

package main

import (
	"crypto/rand"
	"math/big"
)

type (
	// voter will submit votes
	voter struct {
		poly  []*big.Int
		agree bool
		votes []*big.Int
	}

	// authority will count the votes
	authority struct {
		id    *big.Int
		votes []*big.Int
	}
)

// random polynomial of degree d
func init_voter(d int, agree bool) *voter {
	poly := make([]*big.Int, d+1)
	poly[0] = big.NewInt(0)
	if agree {
		poly[0] = big.NewInt(1)
	}

	for i := 1; i <= d; i++ {
		buf := make([]byte, 32)
		rand.Read(buf)
		poly[i] = new(big.Int).SetBytes(buf)
	}
	return &voter{poly: poly, agree: agree}
}

func init_authority() *authority {
	buf := make([]byte, 32)
	rand.Read(buf)
	return &authority{id: new(big.Int).SetBytes(buf)}
}

func (voter *voter) eval(authority_id *big.Int) *big.Int {
	p := new(big.Int).SetBytes([]byte{255, 255, 255, 255, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255})
	vote := big.NewInt(0)
	id := big.NewInt(1)
	for _, coef := range voter.poly {
		tmp := new(big.Int).Mul(coef, id)
		vote.Add(vote, tmp)
		id.Mul(id, authority_id)
		id.Mod(id, p)
	}
	vote.Mod(vote, p)
	return vote
}

func (authority *authority) count_votes() *big.Int {
	p := new(big.Int).SetBytes([]byte{255, 255, 255, 255, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255})
	result := big.NewInt(0)
	for _, vote := range authority.votes {
		result.Add(result, vote)
	}
	result.Mod(result, p)
	return result
}

func get_ids(authorities []*authority) []*big.Int {
	ids := make([]*big.Int, len(authorities))
	for i := 0; i < len(authorities); i++ {
		ids[i] = authorities[i].id
	}
	return ids
}

func get_votes(authorities []*authority) []*big.Int {
	votes := make([]*big.Int, len(authorities))
	for i := 0; i < len(authorities); i++ {
		votes[i] = authorities[i].count_votes()
	}
	return votes
}

func lagrange_interpolate(ids, votes []*big.Int) *big.Int {
	p := new(big.Int).SetBytes([]byte{255, 255, 255, 255, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255})
	if len(ids) != len(votes) {
		return nil
	}

	sum := big.NewInt(0)
	for i := 0; i < len(votes); i++ {
		tmp := votes[i]
		for j := 0; j < len(ids); j++ {
			if i != j {
				neg := new(big.Int).Neg(ids[j])
				neg.Add(neg, p)
				tmp.Mul(tmp, neg)
				neg.Add(neg, ids[i])
				neg.ModInverse(neg, p)
				tmp.Mul(tmp, neg)
			}
		}
		sum.Add(sum, tmp)
		sum.Mod(sum, p)
	}
	return sum
}

-
solved.py:

from pwn import *
p = 115792089210356248762697446949407573530086143415290314195533631308867097853951

while 1:
    s = connect('103.163.25.143', 60126)
    ids = []
    s.recvline_startswith(b'[+] Public ID of available authorities:')
    for i in range(5):
        ids.append(int(s.recvline().strip().decode()))

    id_hacked = int(s.recvline_startswith(b'[+] Authority').strip().decode().split(' ')[-4])
    ids.remove(id_hacked)
    
    tmp = (p - ids[1])*(p - ids[2]) % p
    tmp = tmp*pow((p - ids[1] + id_hacked)*(p - ids[2] + id_hacked), -1, p) % p
    
    s.recvline_startswith(b'Original votes ')
    votes = s.recvline().strip().decode()

    fake_votes = votes[:-64]
    fake_votes += str(hex(((int(votes[-64:], 16)) + 1333*pow(tmp, -1, p))%p))[2:].zfill(64)
    s.sendlineafter(b'Tampered votes:\n', fake_votes.encode())
    
    a = s.recv()
    print(a)
    if b'KMA' in a:
        s.interactive()
    s.close()

> KMACTF{c0ngr4ts!_h4ck3r_:grin:_:grin:_:grin:}

### Only Lord Can Go REVENGE
chall.py:

from Crypto.Util.number import *
import random

print(
"""
     )      (           (       )                   (       )                
  ( /(  (   )\ )  (     )\ ) ( /(   *   )  *   )    )\ ) ( /(             )  
  )\()) )\ (()/(  )\   (()/( )\())` )  /(` )  /((  (()/( )\())  (   (  ( /(  
|((_)\(((_) /(_)|((_)   /(_)|(_)\  ( )(_))( )(_))\  /(_)|(_)\   )\  )\ )(_)) 
|_ ((_)\___(_)) )\___  (_))   ((_)(_(_())(_(_()|(_)(_))__ ((_) ((_)((_|(_)   
| |/ ((/ __/ __((/ __| | |   / _ \|_   _||_   _| __| _ \ \ / / \ \ / /|_  )  
  ' < | (__\__ \| (__  | |__| (_) | | |    | | | _||   /\ V /   \ V /  / /   
 _|\_\ \___|___/ \___| |____|\___/  |_|    |_| |___|_|_\ |_|     \_/  /___|  
                                                                             
"""
)

m = 94472212093594626131047436978697575439604582025155253003497324934058676105592120465477333165162440542344704938026733015754449262871298725480530709273109987324093054515772972278276237630988938655113525659250415319555533704569076292929214171706312390225710667281502861122029038648478773963282271762064453388333
a = getPrime(128)
b = getPrime(256)
c = getPrime(512)
d = random.randrange(1,m)
e = random.randrange(1,m)

print("I will give u only 4 lucky numbers :>")
for i in range(4):
    y = (a*d + b*e + c) % m
    print(f"Lucky number {i+1}: {y}")
    e = d
    d = y

print("Now show off your guessing skills, ego ._.")

for i in range(23):
    y = (a*d + b*e + c) % m
    guess = int(input("Guess: "))
    if guess == y:
        print(f'Nai xuw !!! Remain: {23-i-1}/23')
    else:
        print("Luck is only for those who try, if you don't understand that, then get out !!!")
        exit(0)
    e = d
    d = y

print("WOW, I rly want how do u can guess all correctly, plz sharing w me :<")
print('KMACTF{mao_phac?}')

solved.py:

from pwn import *
from sage.all import *

r = remote('103.163.25.143', 60127)

y_arr = []
for i in range(4):
    r.recvuntil(f'Lucky number {i+1}: '.encode())
    y = int(r.recvline())
    y_arr.append(y)

m = 94472212093594626131047436978697575439604582025155253003497324934058676105592120465477333165162440542344704938026733015754449262871298725480530709273109987324093054515772972278276237630988938655113525659250415319555533704569076292929214171706312390225710667281502861122029038648478773963282271762064453388333
M = Matrix([
  [(y_arr[1] - y_arr[0])*(2**1024), 1, 0, 0], 
  [(y_arr[2] - y_arr[1])*(2**1024), 0, 1, 0], 
  [(y_arr[3] - y_arr[2])*(2**1024), 0, 0, (2**1024)], 
  [m*(2**1024), 0, 0, 0],
])

L = M.LLL()
b,a = abs(L[3][1]), abs(L[3,2])
c = (y_arr[3] - a*y_arr[2] - b*y_arr[1]) % m
print(c)

print(f'[+] FOUND a,b,c !!!')
print(f'[+] {a = }')
print(f'[+] {b = }')
print(f'[+] {c = }')

for i in range(23):
    y = (a*y_arr[-1] + b*y_arr[-2] + c) % m
    r.sendlineafter(b'Guess: ', str(y).encode())
    print(r.recvline())
    y_arr.append(y)

r.interactive()

> KMACTF{LLL_c0m3_b4ck_t0_KMA_?}