wannaShare | Writeups Hack.lu CTF 2021 | Crypto

PHAPHA_JIàN
23:23 08/11/2021

CLB An toàn Thông tin Wanna.One chia sẻ một số Challenges giải được và việc chia sẻ writeup nhằm mục đích giao lưu học thuật. Mọi đóng-góp ý-kiến bọn mình luôn-luôn tiếp nhận qua mail: wannaone.uit@gmail.com hoặc inseclab@uit.edu.vn và fanpage: fb.com/inseclab.

lttn


SILVER WATER INDUSTRIES

Challengge

Đầu tiên mình nc vào server thử

Chẳng tháy nói gì, chỉ hiện lên 1 số nào đó và 20 mảng mỗi mảng lại có 8 con số

OK báy giờ mình sẽ đọc source

package main
import (
    "bufio"
    "crypto/rand"
    "fmt"
    "math"
    "math/big"
    "os"
)
func genN() *big.Int {
    var p *big.Int
    var q *big.Int
    var err error
    for {
        p, err = rand.Prime(rand.Reader, 64)
        if err != nil {
            panic(err)
        }
        res := new(big.Int)
        if res.Mod(p, big.NewInt(4)); res.Cmp(big.NewInt(1)) == 0 {
            break
        }
    }
    for {
        q, err = rand.Prime(rand.Reader, 64)
        if err != nil {
            panic(err)
        }
        res := new(big.Int)
        if res.Mod(q, big.NewInt(4)); res.Cmp(big.NewInt(3)) == 0 {
            break
        }
    }
    N := new(big.Int)
    N.Mul(p, q)
    return N
}
func genX(N *big.Int) *big.Int {
    for {
        x, err := rand.Int(rand.Reader, N)
        if err != nil {
            panic(err)
        }
        g := new(big.Int)
        g.GCD(nil, nil, x, N)
        if g.Cmp(big.NewInt(1)) == 0 {
            return x
        }
    }
}
func encryptByte(b uint8, N *big.Int) []*big.Int {
    z := big.NewInt(-1)
    enc := make([]*big.Int, 8)
    for i := 0; i < 8; i++ {
        bit := b & uint8(math.Pow(2, float64(7-i)))
        x := genX(N)
        x.Exp(x, big.NewInt(2), N)
        if bit != 0 {
            x.Mul(x, z)
            x.Mod(x, N)
        }
        enc[i] = x
    }
    return enc
}
func generateRandomString(n int) string {
    const letters = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz-"
    ret := make([]byte, n)
    for i := 0; i < n; i++ {
        num, err := rand.Int(rand.Reader, big.NewInt(int64(len(letters))))
        if err != nil {
            panic(err)
        }
        ret[i] = letters[num.Int64()]
    }
    return string(ret)
}
func main() {
    N := genN()
    token := []byte(generateRandomString(20))
    fmt.Println(N)
    for _, b := range token {
        fmt.Println(encryptByte(uint8(b), N))
    }
    fmt.Println("")
    reader := bufio.NewReader(os.Stdin)
    input, err := reader.ReadString('\n')
    if err != nil {
        panic(err)
    }
    input = input[:len(input)-1]
    if string(token) == input {
        fmt.Println("flag{<YOUR_FLAG_HERE>}")
    }
}

Vì không quen với go nên mình đọc bài này hơi lâu :((

Để dễ hình dung thì:

flow của đề như sau:

Như vậy thì số đầu tiên nhận được khi nc vào server chính là N`, 20 mảng phía sau chính là 20 két quả sau khi encrypt của các kí tự trong `token

OK vậy giờ muốn recover lại được token, mình cần phải biết hàm encrypt() nó làm gì :

Để dễ nhìn mình viết lại hàm encrypt() bằng python như sau

def encryptByte(b,N):
    z=-1
    enc=[]
    for i in range(8):
        bit=ord(b) & pow(2,7-i)
        x=genX(N)
        x=pow(x,2,N)
        if bit!=0:
            x=(x*z)%N
        enc.append(x)
    return enc

Nhìn vào dễ dàng thấy được các giá trị trong mảng trả về tương ứng với vị trí các bit trong b và sẽ có 2 trường hợp:

Vậy giả sử nếu chúng ta có thể xác đinh được số nào là căn bậc 2 modulo N thì từ đó có thể dễ dàng suy ra được bit của b tại vị trí đó :d -> jacobi symbol :D

from sock import *
from gmpy2 import *
p=Sock('flu.xxx', 20060)
n=int(p.recvline())
print(f"N: {n}")
def filter(s):
    arr=[]
    s=s.split(b' ')
    for i in range(len(s)):
        if i==0:
            tmp=s[i][1:]
            arr.append(int(tmp))
        elif i==7:
            tmp=s[i][:-2]
            arr.append(int(tmp))
        else:
            arr.append(int(s[i]))
    print(arr)
    return arr
def decrypt(nums):
    arr=[]
    for num in nums:
        if  jacobi(num,n)==1:
            arr.append(0)
        else:
            arr.append(1)
    return chr(int("".join([str(x) for x in arr]),2)) 
token=''
for _ in range(20):
    arr=p.recvline()
    arr=filter(arr)
    token+=decrypt(arr)
    print(token)
print(p.recvline())
p.sendline(token)
print(p.recvline())


WHATTHEHECC

Challenge

#!/usr/bin/env python3
import sys
import shlex
import subprocess
from Cryptodome.PublicKey import ECC
from Cryptodome.Hash import SHA3_256
from Cryptodome.Math.Numbers import Integer
import time 
# util
def run_cmd(cmd):
    try:
        args = shlex.split(cmd)
        return subprocess.check_output(args).decode('utf-8')
    except Exception as ex:
        return str(ex)
def read_message():
    return sys.stdin.readline()
def send_message(message):
    sys.stdout.write('### {0}\r\n>'.format(message))
    sys.stdout.flush()
# crypto stuff
def hash(msg):
    h_obj = SHA3_256.new()
    h_obj.update(msg.encode())
    return Integer.from_bytes(h_obj.digest())
def setup(curve):
    key = ECC.generate(curve=curve),
    return key
def blind(msg, pub):
    r = pub.pointQ * hash(msg)
    return r
def sign(r, key):
    r_prime = r * key.d.inverse(key._curve.order)
    date = int(time.time())
    nonce = Integer.random_range(min_inclusive=1,max_exclusive=key._curve.order)
    z = f'{nonce}||{date}'
    R = r_prime + (key._curve.G * hash(z))
    s = (key.d - hash(z)) % key._curve.order
    # return (R, s, z)
    # we can not give away z or this is unsafe: x = s+h(z)
    return R, s
def verify(msg, sig, pub):
    R, s = sig
    if s in [0,1,''] and s > 0:
        return False
    tmp1 = s * pub._curve.G
    tmp2 = - pub.pointQ 
    tmp3 = tmp2 + R
    return tmp1 + tmp3 == hash(msg) * pub._curve.G
## ok ok here we go
def main():
    while True:
        send_message('Enter your command:')
        cmd = read_message().strip()
        if cmd == 'sign':
            send_message('Send cmd to sign:')
            cmd = read_message().strip()
            if(cmd in ['id', 'uname', 'ls', 'date']):
                r = blind(cmd, pubkey)
                sig = sign(r, key)
                send_message(f'Here you go: {sig[0].x}|{sig[0].y}|{sig[1]}|{cmd}')
            else:
                send_message('Not allowed!')
        elif cmd == 'run':
            send_message('Send sig:')
            sig = read_message().strip()
            tmp = sig.split('|')
            if len(tmp) == 4:
                x = int(tmp[0])
                y = int(tmp[1])
                s = int(tmp[2])
                c = tmp[3]
                sig = (ECC.EccPoint(x, y, curve='P-256'), s)
                if(verify(c, sig, pubkey)):
                    out = run_cmd(c)
                    send_message(out)
                else:
                    send_message('Invalid sig!')
            else:
                send_message('Invalid amount of params!')
        elif cmd == 'show':
            send_message(pubkey)
        elif cmd == 'help':
            send_message('Commands: exit, help, show, run, sign')
        elif cmd == 'exit':
            send_message('Bye :) Have a nice day!')
            break
        else:
            send_message('Invalid command!')
if __name__ == '__main__':
    key = setup('P-256')
    pubkey = key.public_key()
    main()

1 Bài ECC cho phép chúng ta run các command nếu có được các signature của command ấy

Đề cũng cho sẵn chúng ta signature của 4 command 'id', 'uname', 'ls', 'date'

Như vậy có thể thấy nếu muốn flag thì ta phải có signature của các command đọc flag :D cat flag chẳng hạn

Ban đầu mình chú ý tới các dòng

date = int(time.time())
nonce = Integer.random_range(min_inclusive=1,max_exclusive=key._curve.order)
z = f'{nonce}||{date}'

Nhìn vào mình nghĩ ngay tới bias nonce và trong đầu mình kiểu : "Thấy mẹ ròi, lại lattice 😥"

Nhưng sau 1 lúc xem kĩ thì mình thấy lúc tính server sử dụng SHA(z) để tính và SHA(z) cùng với order của curve cũng là 256 bit nên mình nghĩ chắc không phải (hoặc có lẽ phải nhưng mình không nhìn ra :(( )

Lúc này mình tìm đến nhưng chổ khác và mình thấy bài này không khó như mình tưởng :v

Nhìn vào hàm sign``verify

Giả sử pubkey là G là secret là d và Q = d*G và z sinh ra từ 3 dòng ở trên

Ví dụ ta muốn sign 1 message m, server sẽ làm như sau:

Signaturec sẽ có dạng R(x)|R(y)|S|m

Ok bây giờ mình sẽ forge signature của cat flag` từ signature của `ls

Từ server mình sẽ có được signatrue của ls, tức là mình đã có được các tham số sau:

Vì công thức verify chỉ tính

Nên vế phải ta hoàn toàn tính được

vậy nhiệm vụ là cần tìm R vs S mới sao cho

Vì vế phải của cả 2 signature ta đề có thể tính được nên ta cũng sẽ tính được giá trị X sao cho:

Vậy lúc này

Hiểu đơn giản thì ta chỉ cần signature của ls` + X là sẽ có được signature của `cat flag

Vậy đơn giản mình chỉ cần giữ nguyên S và lấy R của ls công với điểm X vừa tính ra được, submit lại và get flag :))

Easy đúng hong :hihi

Hơi lười nên mình chỉ viết lại hàm forge thôi, sau đó nhâp tay lên server :(((

import sys
import shlex
import subprocess
from Cryptodome.PublicKey import ECC
from Cryptodome.Hash import SHA3_256
from Cryptodome.Math.Numbers import Integer
import time 
def hash(msg):
    h_obj = SHA3_256.new()
    h_obj.update(msg.encode())
    return Integer.from_bytes(h_obj.digest())
pub = ECC.EccPoint(107574022577513940130512558465327060873205787310786847006619945778082812216463, 15916275444594839428821372321428173508356064540350757394782660883693060315776,curve='P-256')
def forge(x,y,s):
    R=ECC.EccPoint(x, y, curve='P-256')
    target=hash('ls') * pub._curve.G
    tmp1 = s * pub._curve.G
    tmp3=target+(-tmp1)
    new_target=hash('cat flag') * pub._curve.G
    x=new_target+(-target)
    new_tmp1=new_target+(-tmp3)
    Q=tmp3+(-R)
    r=R+x
    return r.x,r.y,s

PS: Mình nghĩ có lẻ đây không là cách giải mong muốn của tác giả 😔

TIN LIÊN QUAN
Cookie Arena được tổ chức bởi Cookie Hân Hoan, một tổ chức giáo dục nhằm phổ biến kiến thức an ninh mạng đến với cộng đồng bằng sự đồng cảm, tươi vui và hài hước. "Xin chào, mình là Gấu aka th3_5had0w đến từ Wanne.One, với tư cách là á...
The Wanna.One Cyber Security Club shares writeup of some solved Challenges with the purpose of academic exchanges. We always welcome and look forward to comments from any of you via email: wannaone.uit@gmail.com FWORD CTF 2021: https://ctftime.org/event/1405 Sat, 28 Aug. 2021, 00:00 ICT — Sun, 29 Aug. 2021, 12:00 ICT Author:...
CLB An toàn Thông tin Wanna.One chia sẻ một số Challenges giải được và việc chia sẻ writeup nhằm mục đích giao lưu học thuật. Mọi đóng-góp ý-kiến bọn mình luôn-luôn tiếp nhận qua mail: wannaone.uit@gmail.com hoặc inseclab@uit.edu.vn và fanpage: fb.com/inseclab. Mochi Nishi vaudeville Description Info: The Dramatis Personae invite...