3/26-27 に開催していた LINE CTF 2022 にチーム WreckTheLine で参加しました。結果は 8th/665 でした。
去年 web 問が面白かった覚えがあったので web 問に結構力を入れましたが、分からず…結局チームの強い人に解いてもらいました。自分は crypto 全部と各ジャンルの比較的簡単な問題を解きました。久しぶりに生活リズムが崩壊するまで楽しみました。 以下解いた問題についての writeup です。
crypto
lazy-STEK
9 solves
main.go
package main
import (
"bufio"
"crypto/aes"
"crypto/rand"
"crypto/sha256"
"crypto/sha512"
"crypto/tls"
"fmt"
"log"
"net"
"github.com/andreburgaud/crypt2go/ecb"
)
func main() {
var key0 [32]byte
var key1 [32]byte
var zero_value = [16]byte{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}
// Generate key0
_, err := rand.Read(key0[:])
if err != nil {
fmt.Println("error:", err)
return
}
// I'm lazy, so I generate key1 from key0. key1 = SHA256( AES_ECB_ENC(0, SHA512(key0)[16:32]) )
tmp_value := sha512.Sum512(key0[:])
key0_ticket_encryption_aes_key := tmp_value[16:32]
block, err := aes.NewCipher(key0_ticket_encryption_aes_key)
if err != nil {
panic(err)
}
ecb_mode := ecb.NewECBEncrypter(block)
ecb_mode.CryptBlocks(key1[:16], zero_value[:])
key1 = sha256.Sum256(key1[:16])
cert, err := tls.LoadX509KeyPair("./secret/cert.pem", "./secret/key.pem")
if err != nil {
log.Fatal(err)
}
cfg := &tls.Config{
Certificates: []tls.Certificate{cert},
}
cfg.SetSessionTicketKeys([][32]byte{
key0,
key1,
})
listener, err := tls.Listen("tcp", ":8000", cfg)
if err != nil {
log.Fatal(err)
}
defer listener.Close()
for {
conn, err := listener.Accept()
if err != nil {
log.Println(err)
continue
}
go handleConnection(conn)
}
}
func handleConnection(conn net.Conn) {
defer conn.Close()
r := bufio.NewReader(conn)
for {
msg, err := r.ReadString('\n')
if err != nil {
log.Println(err)
return
}
println(msg)
n, err := conn.Write([]byte(""))
if err != nil {
log.Println(n, err)
return
}
}
}gcm_ticket.go
//This patch is provided under the 3-Clause BSD License, the original license of Golang.
/*
Copyright (c) 2009 The Go Authors. All rights reserved.
Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are
met:
* Redistributions of source code must retain the above copyright
notice, this list of conditions and the following disclaimer.
* Redistributions in binary form must reproduce the above
copyright notice, this list of conditions and the following disclaimer
in the documentation and/or other materials provided with the
distribution.
* Neither the name of Google Inc. nor the names of its
contributors may be used to endorse or promote products derived from
this software without specific prior written permission.
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
// This code was created based on src/crypto/tls/ticket.go (L131-L200) in Go1.7.1.
// original: https://github.com/golang/go/blob/go1.7.1/src/crypto/tls/ticket.go#L132-L200
// If you want to experiment with this patch, please use a virtual environment that you can throw away, such as Docker.
// e.g. https://hub.docker.com/layers/golang/library/golang/1.17.1/images/sha256-8f4773d3be4e83da2198ae437191f8d9dffb30507714f0b727d0daf222377886
const FLAG string = "LINECTF{...}"
func (c *Conn) encryptTicket(state []byte) ([]byte, error) {
fmt.Println("called custom encryptTicket function!")
if len(c.ticketKeys) == 0 {
return nil, errors.New("tls: internal error: session ticket keys unavailable")
}
// write FLAG in certicicate
new_state := make([]byte, len(state)+len([]byte(FLAG)))
sessionState := new(sessionStateTLS13)
if ok := sessionState.unmarshal(state); !ok {
return nil, errors.New("tls: failed to unmarshal ticket data")
}
sessionState.certificate.Certificate = append(sessionState.certificate.Certificate, []byte(FLAG))
new_state = sessionState.marshal()
// allocate memory
encrypted := make([]byte, ticketKeyNameLen+aes.BlockSize+len(new_state)+sha256.Size)
keyName := encrypted[:ticketKeyNameLen]
iv := make([]byte, aes.BlockSize)
// Select Session Ticket Encryption Key (STEK).
// aesKey is generated with following formula
// aesKey = SHA512(STEK)[16:32]
// ref: https://github.com/golang/go/blob/go1.17.1/src/crypto/tls/common.go#L758-L764
rand.Seed(time.Now().UnixNano())
index := rand.Intn(2)
key := c.ticketKeys[index]
copy(keyName, key.keyName[:])
block, err := aes.NewCipher(key.aesKey[:])
if err != nil {
return nil, errors.New("tls: failed to create cipher while encrypting ticket: " + err.Error())
}
// I'm lazy, so I generate IV from aesKey.
h := sha256.New()
h.Write(key.aesKey[:])
iv = h.Sum(nil)[:16]
if 0 == index {
copy(iv[12:], []byte{0xaa, 0xaa, 0xaa, 0xaa})
} else {
copy(iv[12:], []byte{0xbb, 0xbb, 0xbb, 0xbb})
}
copy(encrypted[ticketKeyNameLen:ticketKeyNameLen+aes.BlockSize], iv[:16])
aesgcm, err := cipher.NewGCM(block)
if err != nil {
return nil, errors.New("tls: failed to create cipher while GCM session for encrypting ticket: " + err.Error())
}
// AES-128-GCM_ENC(nonce=iv[:12](12-octet), plaintext=raw_ticket, aad=keyName(16-octet)+iv(16-octet))
ciphertext := aesgcm.Seal(nil, iv[:12], new_state, encrypted[:ticketKeyNameLen+aes.BlockSize])
copy(encrypted[ticketKeyNameLen+aes.BlockSize:], ciphertext)
return encrypted, nil
}
func (c *Conn) decryptTicket(encrypted []byte) (plaintext []byte, usedOldKey bool) {
if len(encrypted) < ticketKeyNameLen+aes.BlockSize+sha256.Size {
return nil, false
}
tagsize := 16
keyName := encrypted[:ticketKeyNameLen]
iv := encrypted[ticketKeyNameLen : ticketKeyNameLen+aes.BlockSize]
ciphertext := encrypted[ticketKeyNameLen+aes.BlockSize : len(encrypted)-sha256.Size+tagsize]
keyIndex := -1
for i, candidateKey := range c.ticketKeys {
if bytes.Equal(keyName, candidateKey.keyName[:]) {
keyIndex = i
break
}
}
if keyIndex == -1 {
return nil, false
}
key := &c.ticketKeys[keyIndex]
block, err := aes.NewCipher(key.aesKey[:])
if err != nil {
return nil, false
}
aesgcm, err := cipher.NewGCM(block)
if err != nil {
return nil, false
}
pt, err := aesgcm.Open(nil, iv[:12], ciphertext, encrypted[:ticketKeyNameLen+aes.BlockSize])
if err != nil {
return nil, false
}
return pt, keyIndex > 0
}上記ファイルと .pcap ファイルが与えられます。フラグは client 側で AES-GCM で暗号化されて送信されています。
TLS 通信がよくわからんのでどこを見ればいいのかわからなかったのですが、 iv の末尾が aaaaaaaa や bbbbbbbb となっているはずなのでこれらの文字列を wireshark で探すと、 pre_shared_key -> Pre-Shared Key extension -> PSK Identity というところに暗号化されたもの (gcm_ticket.go 内の encrypted に相当) がありました。全部で3つありました。
256f6e3b40c2c006f26dbe24b70c6ed6e875cec70f64aac0de67af2caaaaaaaa450abecfee723cdbe4393bbcf56add91e283615eaa6a5899906a138ce3dbe632ab778328029499c12eceefa0589945f7f3801748be3daa06ace2e682a77649da535f7235aa7ecb60bf0e3d6b7c1012e192411e29e6494c2fa05ce2c5d08d4698a05ffb5fa9ad2b2550737cea3b19ccacfdd93e7d3c3f6e641d5f8793b17261047b160c9acaf891577ef700000000000000000000000000000000
256f6e3b40c2c006f26dbe24b70c6ed6e875cec70f64aac0de67af2caaaaaaaa450abecfee723cdbe4393bbce26a50c35bd4b250c5395150b62c27d76e20535dea6a129d08c1c31e89475b79d36e45f7f3801748be3daa06ace2e682a77649da535f7235aa7ecb60bf0e3d6b7c1012e192411e29e6494c2fa05ce2c5d08d4698a05ffb5fa9ad2b2550737cea3b19ccacfdd93e7d3c3f6e641d5f1f668e1af6844a40e4cbdb6132cbd39500000000000000000000000000000000
ffd08593ad673b9005296a50f603af28c336d16a10aac82969a59560bbbbbbbb6fe550ba6db4b6a2af74f6f0454d82d959daa387f694685dec4c1ff7c36e40d3b9fe6e4fd41596035a594f8b599b89c47c84aa66d6d63ef3999de5041f0c3b7598b1811012399575a0c442c1c364f669ecf7fd5dfbb06bc37fd830c03e3dde20c98bc747d74d0ac196936f364c2e81338fca4bdb193d52e19f23295fc9e7546288a7464baa258fcd554200000000000000000000000000000000gcm_ticket.go をみると、最初の16bytesが keyName (これは何？)、次の16bytesが iv、そのあとが AES-GCM による暗号・タグとなることがわかります。 go で適当に実験をすると go の AES-GCM は後半16bytesがタグであることがわかります。
- keyName
256f6e3b40c2c006f26dbe24b70c6ed6
256f6e3b40c2c006f26dbe24b70c6ed6
ffd08593ad673b9005296a50f603af28
- iv
e875cec70f64aac0de67af2caaaaaaaa
e875cec70f64aac0de67af2caaaaaaaa
c336d16a10aac82969a59560bbbbbbbb
- cipher text
450abecfee723cdbe4393bbcf56add91e283615eaa6a5899906a138ce3dbe632ab778328029499c12eceefa0589945f7f3801748be3daa06ace2e682a77649da535f7235aa7ecb60bf0e3d6b7c1012e192411e29e6494c2fa05ce2c5d08d4698a05ffb5fa9ad2b2550737cea3b19ccacfdd93e7d3c3f6e641d5f
450abecfee723cdbe4393bbce26a50c35bd4b250c5395150b62c27d76e20535dea6a129d08c1c31e89475b79d36e45f7f3801748be3daa06ace2e682a77649da535f7235aa7ecb60bf0e3d6b7c1012e192411e29e6494c2fa05ce2c5d08d4698a05ffb5fa9ad2b2550737cea3b19ccacfdd93e7d3c3f6e641d5f
6fe550ba6db4b6a2af74f6f0454d82d959daa387f694685dec4c1ff7c36e40d3b9fe6e4fd41596035a594f8b599b89c47c84aa66d6d63ef3999de5041f0c3b7598b1811012399575a0c442c1c364f669ecf7fd5dfbb06bc37fd830c03e3dde20c98bc747d74d0ac196936f364c2e81338fca4bdb193d52e19f23
- tag
8793b17261047b160c9acaf891577ef7
1f668e1af6844a40e4cbdb6132cbd395
295fc9e7546288a7464baa258fcd5542整理してみると iv が同じものが存在しています。 AES-GCM では nonce の使いまわしをすることで署名計算に使われる を計算できてしまうことが知られています (例えば こちらの記事 や こちらの writeup が参考になります)。なのでまずはこれを求めます。
from binascii import unhexlify
from hashlib import sha256, sha512
from Crypto.Cipher import AES
from Crypto.Util.number import bytes_to_long, long_to_bytes
X = GF(2).polynomial_ring().gen()
poly = X ** 128 + X ** 7 + X ** 2 + X ** 1 + 1
F = GF(2 ** 128, name='a', modulus=poly)
R.<x> = PolynomialRing(F)
def tobin(x, n):
x = Integer(x)
nbits = x.nbits()
assert nbits <= n
return x.bits() + [0] * (n - nbits)
def frombin(v):
return int("".join(map(str, v)), 2)
def toF(x):
x = frombin(tobin(x, 128))
return F.fetch_int(x)
def fromF(x):
x = x.integer_representation()
x = frombin(tobin(x, 128))
return x
key_name = unhexlify("256f6e3b40c2c006f26dbe24b70c6ed6")
iv = unhexlify("e875cec70f64aac0de67af2caaaaaaaa")
ct0 = unhexlify("450abecfee723cdbe4393bbcf56add91e283615eaa6a5899906a138ce3dbe632ab778328029499c12eceefa0589945f7f3801748be3daa06ace2e682a77649da535f7235aa7ecb60bf0e3d6b7c1012e192411e29e6494c2fa05ce2c5d08d4698a05ffb5fa9ad2b2550737cea3b19ccacfdd93e7d3c3f6e641d5f")
ct1 = unhexlify("450abecfee723cdbe4393bbce26a50c35bd4b250c5395150b62c27d76e20535dea6a129d08c1c31e89475b79d36e45f7f3801748be3daa06ace2e682a77649da535f7235aa7ecb60bf0e3d6b7c1012e192411e29e6494c2fa05ce2c5d08d4698a05ffb5fa9ad2b2550737cea3b19ccacfdd93e7d3c3f6e641d5f")
tag0 = toF(bytes_to_long(unhexlify("8793b17261047b160c9acaf891577ef7")))
tag1 = toF(bytes_to_long(unhexlify("1f668e1af6844a40e4cbdb6132cbd395")))
Cs0 = []
Cs1 = []
Cs0.append(toF(bytes_to_long(key_name)))
Cs0.append(toF(bytes_to_long(iv)))
Cs1.append(toF(bytes_to_long(key_name)))
Cs1.append(toF(bytes_to_long(iv)))
for i in range(0, len(ct0), 16):
Cs0.append(toF(bytes_to_long(ct0[i: i+16].ljust(16, b"\x00"))))
Cs1.append(toF(bytes_to_long(ct1[i: i+16].ljust(16, b"\x00"))))
Cs01 = [Cs0[i] + Cs1[i] for i in range(len(Cs0))]
PR.<x> = PolynomialRing(F)
f = Cs01[2] * x**9 + Cs01[3] * x**8 + Cs01[4] * x**7 + (tag0 + tag1)
roots = f.roots()最後の roots のどちらかが に相当します。
とりあえず を求めましたがこれをどう使うのでしょうか。問題ソースコード中のコメントに注目すると、 server 側の key0, key1 を使って AES の key が計算されていること、 key1 が key0 を使って定義されていることがわかります。特に key1 は client 側の AES key を使って AES(0) から計算されており、先程求めた から計算可能です。
for root in roots:
H = root[0]
enc_0 = long_to_bytes(fromF(H))
key1 = sha256(enc_0).digest()
aes_key = sha512(key1).digest()[16:32]
if sha256(aes_key).digest()[:12].hex() == "c336d16a10aac82969a59560":
print("found")
breakこれで key1 から求まるほうの AES の key がわかりました (iv の末尾が bbbbbbbb のほう)。これを使って復号を試みます。
cipher = AES.new(aes_key, mode=AES.MODE_ECB)
iv = unhexlify("c336d16a10aac82969a59560")
ct = unhexlify("6fe550ba6db4b6a2af74f6f0454d82d959daa387f694685dec4c1ff7c36e40d3b9fe6e4fd41596035a594f8b599b89c47c84aa66d6d63ef3999de5041f0c3b7598b1811012399575a0c442c1c364f669ecf7fd5dfbb06bc37fd830c03e3dde20c98bc747d74d0ac196936f364c2e81338fca4bdb193d52e19f23")
pt = b""
for i in range(0, len(ct), 16):
ct_block = ct[i: i+16]
D = toF(bytes_to_long(ct_block.ljust(16, b"\x00")))
C = D + toF(bytes_to_long(cipher.encrypt(iv + int(i//16+2).to_bytes(4, "big"))))
pt_block = long_to_bytes(fromF(C))[:len(ct_block)]
pt += pt_block
print(pt)LINECTF{N0nc3_r3us3_je0p4rd1ze_Hk3y_that_is_us3d_f0r_auth3nt1cat1on}
この問題は深夜 (というか早朝) に解いたのですが、眠さの限界のせいか server 側の key から client 側の AES key を求めるところでバグらせまくって死んでました。 key1 の長さを16bytesと勘違いしていたり、sha256をもう一回かけなきゃいけないのを忘れていたり、 AES-GCM に関係ないところで…
問題自体はコメントが丁寧に書かれていて親切だったと思います (.pcap にする必要があったのかは不明)。
Forward-or
43 solves
main.py
from present import Present
from Crypto.Util.strxor import strxor
import os, re
class CTRMode():
def __init__(self, key, nonce=None):
self.key = key # 20bytes
self.cipher = DoubleRoundReducedPresent(key)
if None==nonce:
nonce = os.urandom(self.cipher.block_size//2)
self.nonce = nonce # 4bytes
def XorStream(self, data):
output = b""
counter = 0
for i in range(0, len(data), self.cipher.block_size):
keystream = self.cipher.encrypt(self.nonce+counter.to_bytes(self.cipher.block_size//2, 'big'))
if b""==keystream:
exit(1)
if len(data)<i+self.cipher.block_size:
block = data[i:len(data)]
block = data[i:i+self.cipher.block_size]
block = strxor(keystream[:len(block)], block)
output+=block
counter+=1
return output
def encrypt(self, plaintext):
return self.XorStream(plaintext)
def decrypt(self, ciphertext):
return self.XorStream(ciphertext)
class DoubleRoundReducedPresent():
def __init__(self, key):
self.block_size = 8
self.key_length = 160 # bits
self.round = 16
self.cipher0 = Present(key[0:10], self.round)
self.cipher1 = Present(key[10:20], self.round)
def encrypt(self, plaintext):
if len(plaintext)>self.block_size:
print("Error: Plaintext must be less than %d bytes per block" % self.block_size)
return b""
return self.cipher1.encrypt(self.cipher0.encrypt(plaintext))
def decrypt(self, ciphertext):
if len(ciphertext)>self.block_size:
print("Error: Ciphertext must be less than %d bytes per block" % self.block_size)
return b""
return self.cipher0.decrypt(self.cipher1.decrypt(ciphertext))
if __name__ == "__main__":
import sys, os
sys.path.append(os.path.join(os.path.dirname(__file__), './secret/'))
from keyfile import key
from flag import flag
# load key
if not re.fullmatch(r'[0-3]+', key):
exit(1)
key = key.encode('ascii')
# load flag
flag = flag.encode('ascii') # LINECTF{...}
plain = flag
cipher = CTRMode(key)
ciphertext = cipher.encrypt(plain)
nonce = cipher.nonce
print(ciphertext.hex())
print(nonce.hex())present.py
'''
Python3 PRESENT implementation
original code (implementation for python2) is here:
http://www.lightweightcrypto.org/downloads/implementations/pypresent.py
'''
'''
key = bytes.fromhex("00000000000000000000")
plain = bytes.fromhex("0000000000000000")
cipher = Present(key)
encrypted = cipher.encrypt(plain)
print(encrypted.hex())
>> '5579c1387b228445'
decrypted = cipher.decrypt(encrypted)
decrypted.hex()
>> '0000000000000000'
'''
class Present:
def __init__(self,key,rounds=32):
"""Create a PRESENT cipher object
key: the key as a 128-bit or 80-bit rawstring
rounds: the number of rounds as an integer, 32 by default
"""
self.rounds = rounds
if len(key) * 8 == 80:
self.roundkeys = generateRoundkeys80(byte2number(key),self.rounds)
elif len(key) * 8 == 128:
self.roundkeys = generateRoundkeys128(byte2number(key),self.rounds)
else:
raise (ValueError, "Key must be a 128-bit or 80-bit rawstring")
def encrypt(self,block):
"""Encrypt 1 block (8 bytes)
Input: plaintext block as raw string
Output: ciphertext block as raw string
"""
state = byte2number(block)
for i in range(self.rounds-1):
state = addRoundKey(state,self.roundkeys[i])
state = sBoxLayer(state)
state = pLayer(state)
cipher = addRoundKey(state,self.roundkeys[-1])
return number2byte_N(cipher,8)
def decrypt(self,block):
"""Decrypt 1 block (8 bytes)
Input: ciphertext block as raw string
Output: plaintext block as raw string
"""
state = byte2number(block)
for i in range(self.rounds-1):
state = addRoundKey(state,self.roundkeys[-i-1])
state = pLayer_dec(state)
state = sBoxLayer_dec(state)
decipher = addRoundKey(state,self.roundkeys[0])
return number2byte_N(decipher,8)
def get_block_size(self):
return 8
# 0 1 2 3 4 5 6 7 8 9 a b c d e f
Sbox= [0xc,0x5,0x6,0xb,0x9,0x0,0xa,0xd,0x3,0xe,0xf,0x8,0x4,0x7,0x1,0x2]
Sbox_inv = [Sbox.index(x) for x in range(16)]
PBox = [0,16,32,48,1,17,33,49,2,18,34,50,3,19,35,51,
4,20,36,52,5,21,37,53,6,22,38,54,7,23,39,55,
8,24,40,56,9,25,41,57,10,26,42,58,11,27,43,59,
12,28,44,60,13,29,45,61,14,30,46,62,15,31,47,63]
PBox_inv = [PBox.index(x) for x in range(64)]
def generateRoundkeys80(key,rounds):
"""Generate the roundkeys for a 80-bit key
Input:
key: the key as a 80-bit integer
rounds: the number of rounds as an integer
Output: list of 64-bit roundkeys as integers"""
roundkeys = []
for i in range(1,rounds+1): # (K1 ... K32)
# rawkey: used in comments to show what happens at bitlevel
# rawKey[0:64]
roundkeys.append(key >>16)
#1. Shift
#rawKey[19:len(rawKey)]+rawKey[0:19]
key = ((key & (2**19-1)) << 61) + (key >> 19)
#2. SBox
#rawKey[76:80] = S(rawKey[76:80])
key = (Sbox[key >> 76] << 76)+(key & (2**76-1))
#3. Salt
#rawKey[15:20] ^ i
key ^= i << 15
return roundkeys
def generateRoundkeys128(key,rounds):
"""Generate the roundkeys for a 128-bit key
Input:
key: the key as a 128-bit integer
rounds: the number of rounds as an integer
Output: list of 64-bit roundkeys as integers"""
roundkeys = []
for i in range(1,rounds+1): # (K1 ... K32)
# rawkey: used in comments to show what happens at bitlevel
roundkeys.append(key >>64)
#1. Shift
key = ((key & (2**67-1)) << 61) + (key >> 67)
#2. SBox
key = (Sbox[key >> 124] << 124)+(Sbox[(key >> 120) & 0xF] << 120)+(key & (2**120-1))
#3. Salt
#rawKey[62:67] ^ i
key ^= i << 62
return roundkeys
def addRoundKey(state,roundkey):
return state ^ roundkey
def sBoxLayer(state):
"""SBox function for encryption
Input: 64-bit integer
Output: 64-bit integer"""
output = 0
for i in range(16):
output += Sbox[( state >> (i*4)) & 0xF] << (i*4)
return output
def sBoxLayer_dec(state):
"""Inverse SBox function for decryption
Input: 64-bit integer
Output: 64-bit integer"""
output = 0
for i in range(16):
output += Sbox_inv[( state >> (i*4)) & 0xF] << (i*4)
return output
def pLayer(state):
"""Permutation layer for encryption
Input: 64-bit integer
Output: 64-bit integer"""
output = 0
for i in range(64):
output += ((state >> i) & 0x01) << PBox[i]
return output
def pLayer_dec(state):
"""Permutation layer for decryption
Input: 64-bit integer
Output: 64-bit integer"""
output = 0
for i in range(64):
output += ((state >> i) & 0x01) << PBox_inv[i]
return output
def byte2number(i):
""" Convert a string to a number
Input: byte (big-endian)
Output: long or integer
"""
return int.from_bytes(i, 'big')
def number2byte_N(i, N):
"""Convert a number to a string of fixed size
i: long or integer
N: length of byte
Output: string (big-endian)
"""
return i.to_bytes(N, byteorder='big')
def _test():
import doctest
doctest.testmod()
if __name__ == "__main__":
_test()key が [0-3]{20} という形式になっており、 DoubleRoundReducedPresent は前半10bytesの key で Present.encrypt 、さらに後半10bytes の key で Present.encrypt を行います。
key の探索空間の広さがぱっとみだと です。しかし以下の方法で まで計算量を落とすことができ、これは十分計算可能な量となります。
nonce が既知なので10bytesの key の全パターンで Present.encrypt(nonce) をした結果を列挙できます。さらに平文の先頭8bytesが LINECTF{ であることを使って DoubleRoundReducedPresent.encrypt の最初のブロック結果がわかっています。そこで DoubleRoundReducedPresent.encrypt の結果をある10bytesの key で Present.decrypt した結果が、先程全列挙した Present.encrypt(nonce) に存在していれば、そのときの key は実際に使われた key ということになります。
この方法で key を特定し、復号してフラグを得ました。
solve.py
from binascii import unhexlify
from itertools import product
from tqdm import tqdm
ciphertext = unhexlify("3201339d0fcffbd152f169ddcb8349647d8bc36a73abc4d981d3206f4b1d98468995b9b1c15dc0f0")
nonce = unhexlify("32e10325")
inp = nonce + (0).to_bytes(4, 'big')
encs0 = {}
for key_tuple in tqdm(product("0123", repeat=10), total=4**10):
key = ("".join(key_tuple)).encode()
cipher = Present(key, 16)
encs0[cipher.encrypt(inp)] = key
out = strxor(b"LINECTF{", ciphertext[:8])
for key_tuple in tqdm(product("0123", repeat=10), total=4**10):
key = ("".join(key_tuple)).encode()
cipher = Present(key, 16)
tmp = cipher.decrypt(out)
if tmp in encs0:
key1 = key
key0 = encs0[tmp]
key = key0 + key1
print(key)
break
cipher = CTRMode(key, nonce=nonce)
cipher.decrypt(ciphertext)LINECTF{|->TH3Y_m3t_UP_1n_th3_m1ddl3<-|}
Baby crypto revisited
48 solves
ECDSA の のペアが複数与えられています。
典型的な HNP だし、この形式どこかで見たなと思ったら、去年の LINE CTF でほぼ同じ問題が出ていました。去年は の値が小さすぎて上位ビットの情報を使わなくても解けてしまったのですが、今年はちょっとビット数が増えており上位ビットを使う必要がありそうです。それだけの差分なので去年の script をコピペし、上位ビットの情報を取り入れるだけで解けました。これは…
solve.sage
from binascii import unhexlify
from Crypto.Util.number import long_to_bytes, bytes_to_long
import re
with open("./Babycrypto_revisited_b1f108dea290b83253b80443260b12c3cadc0ed7.txt") as f:
buf = f.read()
rs = []
ss = []
ks = []
hs = []
for r, s, k, h in re.findall(r"(0x[0-9a-f]*) (0x[0-9a-f]*) (0x[0-9a-f]*) (0x[0-9a-f]*)", buf):
rs.append(int(r, 16))
ss.append(int(s, 16))
ks.append(int(k, 16))
tmp_h = h[2:]
if len(tmp_h) % 2 == 1:
tmp_h = "0" + tmp_h
hs.append(bytes_to_long(unhexlify(tmp_h)))
# https://neuromancer.sk/std/secg/secp160r1
p = 0xffffffffffffffffffffffffffffffff7fffffff
a = 0xffffffffffffffffffffffffffffffff7ffffffc
b = 0x1c97befc54bd7a8b65acf89f81d4d4adc565fa45
EC = EllipticCurve(GF(p), [a, b])
G = EC(0x4a96b5688ef573284664698968c38bb913cbfc82, 0x23a628553168947d59dcc912042351377ac5fb32)
n = 0x0100000000000000000001f4c8f927aed3ca752257
h = 0x1
m = len(rs)
M = matrix(QQ, m+2, m+2)
order = n
B = 2**150
for i in range(m):
M[i, i] = QQ(order)
M[m, i] = QQ(pow(ss[i], -1, order) * rs[i])
M[m+1, i] = -QQ(pow(ss[i], -1, order) * hs[i] - ks[i])
M[m, m] = QQ(B) / QQ(order)
M[m+1, m+1] = QQ(B)
C = M.LLL()
for i in range(m+2):
if abs(C[i][-1]) != B:
continue
d = ZZ(C[i][-2] * order / B)
if C[i][-1] < 0:
d = -d
for j in range(m):
kl = (int(pow(ss[j], -1, order) * rs[j] * int(d)) + int(pow(ss[j], -1, order) * hs[j])) % order
print(kl, ks[j])
print(hex(d))
# or order - dLINECTF{0xd77d10fec685cbe16f64cba090db24d23b92f824}
去年の自分の writeup のアクセス数が増えてて、それはそうという気持ちになりました。現場からは以上です。
X Factor
102 solves
比較的小さい数字と、それを RSA で署名したもののペアがいくつか与えられています。
単純には解けないのですが、与えられた数字を素因数分解してみると、似たような素数の積で表されていることがわかります。存在する素数は9種類で署名のペアは7種類あります。これらを使って線形に求めます。
solve.sage
n = 0xa9e7da28ebecf1f88efe012b8502122d70b167bdcfa11fd24429c23f27f55ee2cc3dcd7f337d0e630985152e114830423bfaf83f4f15d2d05826bf511c343c1b13bef744ff2232fb91416484be4e130a007a9b432225c5ead5a1faf02fa1b1b53d1adc6e62236c798f76695bb59f737d2701fe42f1fbf57385c29de12e79c5b3
mcs = [
(0x945d86b04b2e7c7, 0x17bb21949d5a0f590c6126e26dc830b51d52b8d0eb4f2b69494a9f9a637edb1061bec153f0c1d9dd55b1ad0fd4d58c46e2df51d293cdaaf1f74d5eb2f230568304eebb327e30879163790f3f860ca2da53ee0c60c5e1b2c3964dbcf194c27697a830a88d53b6e0ae29c616e4f9826ec91f7d390fb42409593e1815dbe48f7ed4),
(0x5de2, 0x3ea73715787028b52796061fb887a7d36fb1ba1f9734e9fd6cb6188e087da5bfc26c4bfe1b4f0cbfa0d693d4ac0494efa58888e8415964c124f7ef293a8ee2bc403cad6e9a201cdd442c102b30009a3b63fa61cdd7b31ce9da03507901b49a654e4bb2b03979aea0fab3731d4e564c3c30c75aa1d079594723b60248d9bdde50),
(0xa16b201cdd42ad70da249, 0x9444e3fc71056d25489e5ce78c6c986c029f12b61f4f4b5cbd4a0ce6b999919d12c8872b8f2a8a7e91bd0f263a4ead8f2aa4f7e9fdb9096c2ea11f693f6aa73d6b9d5e351617d6f95849f9c73edabd6a6fde6cc2e4559e67b0e4a2ea8d6897b32675be6fc72a6172fd42a8a8e96adfc2b899015b73ff80d09c35909be0a6e13a),
(0x6d993121ed46b, 0x2b7a1c4a1a9e9f9179ab7b05dd9e0089695f895864b52c73bfbc37af3008e5c187518b56b9e819cc2f9dfdffdfb86b7cc44222b66d3ea49db72c72eb50377c8e6eb6f6cbf62efab760e4a697cbfdcdc47d1adc183cc790d2e86490da0705717e5908ad1af85c58c9429e15ea7c83ccf7d86048571d50bd721e5b3a0912bed7c),
(0x726fa7a7, 0xa7d5548d5e4339176a54ae1b3832d328e7c512be5252dabd05afa28cd92c7932b7d1c582dc26a0ce4f06b1e96814ee362ed475ddaf30dd37af0022441b36f08ec8c7c4135d6174167a43fa34f587abf806a4820e4f74708624518044f272e3e1215404e65b0219d42a706e5c295b9bf0ee8b7b7f9b6a75d76be64cf7c27dfaeb),
(0x31e828d97a0874cff, 0x67832c41a913bcc79631780088784e46402a0a0820826e648d84f9cc14ac99f7d8c10cf48a6774388daabcc0546d4e1e8e345ee7fc60b249d95d953ad4d923ca3ac96492ba71c9085d40753cab256948d61aeee96e0fe6c9a0134b807734a32f26430b325df7b6c9f8ba445e7152c2bf86b4dfd4293a53a8d6f003bf8cf5dffd),
(0x904a515, 0x927a6ecd74bb7c7829741d290bc4a1fd844fa384ae3503b487ed51dbf9f79308bb11238f2ac389f8290e5bcebb0a4b9e09eda084f27add7b1995eeda57eb043deee72bfef97c3f90171b7b91785c2629ac9c31cbdcb25d081b8a1abc4d98c4a1fd9f074b583b5298b2b6cc38ca0832c2174c96f2c629afe74949d97918cbee4a),
]
ms, cs = zip(*mcs)
set(sum([[p for p, _ in factor(ms[i])] for i in range(7)], []))
ps = [2, 61, 197, 811, 947, 970111, 2098711, 2854343, 9605087]
target = 0x686178656c696f6e
# target == 2 * 197 * 947 * 2098711 * 9605087
target_coeff = [1, 0, 1, 0, 1, 0, 1, 0, 1]
coeffs = []
for i in range(7):
m = ms[i]
pes = factor(m)
coeff = [0] * len(ps)
for p, e in pes:
coeff[ps.index(p)] = e
coeffs.append(coeff)
M = matrix(coeffs)
t = vector(target_coeff)
c = M.solve_left(t)
sign = 1
for i in range(len(c)):
sign *= pow(cs[i], c[i], n)
print(sign)LINECTF{a049347a7db8226d496eb55c15b1d840}
ss-puzzle
221 solves
ss_puzzle.py
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# 64 bytes
FLAG = b'LINECTF{...}'
def xor(a:bytes, b:bytes) -> bytes:
return bytes(i^j for i, j in zip(a, b))
S = [None]*4
R = [None]*4
Share = [None]*5
S[0] = FLAG[0:8]
S[1] = FLAG[8:16]
S[2] = FLAG[16:24]
S[3] = FLAG[24:32]
# Ideally, R should be random stream. (Not hint)
R[0] = FLAG[32:40]
R[1] = FLAG[40:48]
R[2] = FLAG[48:56]
R[3] = FLAG[56:64]
Share[0] = R[0] + xor(R[1], S[3]) + xor(R[2], S[2]) + xor(R[3],S[1])
Share[1] = xor(R[0], S[0]) + R[1] + xor(R[2], S[3]) + xor(R[3],S[2])
Share[2] = xor(R[0], S[1]) + xor(R[1], S[0]) + R[2] + xor(R[3],S[3])
Share[3] = xor(R[0], S[2]) + xor(R[1], S[1]) + xor(R[2], S[0]) + R[3]
Share[4] = xor(R[0], S[3]) + xor(R[1], S[2]) + xor(R[2], S[1]) + xor(R[3],S[0])
# This share is partially broken.
Share[1] = Share[1][0:8] + b'\x00'*8 + Share[1][16:24] + Share[1][24:32]
with open('./Share1', 'wb') as f:
f.write(Share[1])
f.close()
with open('./Share4', 'wb') as f:
f.write(Share[4])
f.close()xor でガチャガチャやっています。フラグの先頭は LINECTF{ なことと Share1, Share4 の値からすべての値が求まります。
solve.py
from pwn import xor
with open("./Share1", "rb") as fp:
share_1 = fp.read()
with open("./Share4", "rb") as fp:
share_4 = fp.read()
def xor(a:bytes, b:bytes) -> bytes:
return bytes(i^^j for i, j in zip(a, b))
flag_0 = b"LINECTF{"
flag_3 = xor(share_1[:8], share_4[:8], flag_0)
flag_1 = xor(share_1[16:24], share_4[16:24], flag_3)
flag_2 = xor(share_1[24:32], share_4[24:32], flag_0)
flag_4 = xor(share_4[:8], flag_3)
flag_5 = xor(share_4[8:16], flag_2)
flag_6 = xor(share_4[16:24], flag_1)
flag_7 = xor(share_4[24:32], flag_0)
flag = flag_0 + flag_1 + flag_2 + flag_3 + flag_4 + flag_5 + flag_6 + flag_7LINECTF{Yeah_known_plaintext_is_important_in_xor_based_puzzle!!}
Web
Memo Drive
42 solves
index.py
import os
import hashlib
import shutil
import datetime
import uvicorn
import logging
from urllib.parse import unquote
from starlette.applications import Starlette
from starlette.responses import HTMLResponse
from starlette.routing import Route, Mount
from starlette.templating import Jinja2Templates
from starlette.staticfiles import StaticFiles
logger = logging.getLogger()
logger.setLevel(logging.DEBUG)
templates = Jinja2Templates(directory='./')
templates.env.autoescape = False
def index(request):
context = {}
memoList = []
try:
clientId = getClientID(request.client.host)
path = './memo/' + clientId
if os.path.exists(path):
memoList = os.listdir(path)
context['request'] = request
context['ip'] = request.client.host
context['clientId'] = clientId
context['memoList'] = memoList
context['count'] = len(memoList)
except:
pass
return templates.TemplateResponse('/view/index.html', context)
def save(request):
context = {}
memoList = []
try:
context['request'] = request
context['ip'] = request.client.host
contents = request.query_params['contents']
path = './memo/' + getClientID(request.client.host) + '/'
if os.path.exists(path) == False:
os.makedirs(path, exist_ok=True)
memoList = os.listdir(path)
idx = len(memoList)
if idx >= 3:
return HTMLResponse('Memo Full')
elif len(contents) > 100:
return HTMLResponse('Contents Size Error (MAX:100)')
filename = str(idx) + '_' + datetime.datetime.now().strftime('%Y%m%d%H%M%S')
f = open(path + filename, 'w')
f.write(contents)
f.close()
except:
pass
return HTMLResponse('Save Complete')
def reset(request):
context = {}
try:
context['request'] = request
clientId = getClientID(request.client.host)
path = './memo/' + clientId
if os.path.exists(path) == False:
return HTMLResponse('Memo Null')
shutil.rmtree(path)
except:
pass
return HTMLResponse('Reset Complete')
def view(request):
context = {}
try:
context['request'] = request
print(request)
clientId = getClientID(request.client.host)
print(f"{request.url.query = }")
print(f"{request.query_params[clientId] = }")
print("".join(request.query_params.keys()))
if '&' in request.url.query or '.' in request.url.query or '.' in unquote(request.query_params[clientId]):
raise
filename = request.query_params[clientId]
print(f"{filename = }")
path = './memo/' + "".join(request.query_params.keys()) + '/' + filename
f = open(path, 'r')
contents = f.readlines()
f.close()
context['filename'] = filename
context['contents'] = contents
except:
pass
return templates.TemplateResponse('/view/view.html', context)
def getClientID(ip):
key = ip + '_' + os.getenv('SALT')
return hashlib.md5(key.encode('utf-8')).hexdigest()
routes = [
Route('/', endpoint=index),
Route('/view', endpoint=view),
Route('/reset', endpoint=reset),
Route('/save', endpoint=save),
Mount('/static', StaticFiles(directory='./static'), name='static')
]
app = Starlette(debug=False, routes=routes)
if __name__ == "__main__":
logging.info("Starting Starlette Server")
uvicorn.run(app, host="0.0.0.0", port=11000)別ディレクトリに格納されている flag ファイルを読み出す問題です。
明らかに view 関数の処理が怪しい ("".join(requestquery_params.keys()) とかする必要ある？？ unquote も一部にしか使われてない) ので、そこに注目しました。
def view(request):
context = {}
try:
context['request'] = request
print(request)
clientId = getClientID(request.client.host)
print(f"{request.url.query = }")
print(f"{request.query_params[clientId] = }")
print("".join(request.query_params.keys()))
if '&' in request.url.query or '.' in request.url.query or '.' in unquote(request.query_params[clientId]):
raise
filename = request.query_params[clientId]
print(f"{filename = }")
path = './memo/' + "".join(request.query_params.keys()) + '/' + filename
f = open(path, 'r')
contents = f.readlines()
f.close()
context['filename'] = filename
context['contents'] = contents
except:
pass
return templates.TemplateResponse('/view/view.html', context)いろいろな query を試しましたが、上手くいかず…
library 特有の問題だったりするのかな？と思い、 starlette の github issue を探しました。すると https://github.com/encode/starlette/issues/1325 が見つかりました。 ; が query の区切り文字 (& の代わり) になってしまうというバグ報告です。 https://python-security.readthedocs.io/vuln/urllib-query-string-semicolon-separator.html を見ると python の一部のバージョンでこのバグが発現するみたいです。 Dockerfile を見ると python のバージョンは3.9.0であり、これもバグのあるバージョンの一つです。
これを利用し、 /view?CLIENT_ID=flag;/%2e%2e/ のような query を投げると、 CLIENT_ID/../flag のファイルを読み込むことができます。
LINECTF{The_old_bug_on_urllib_parse_qsl_fixed}
Pwn
ecrypt
105 solves
root 権限の flag ファイルを読む問題。 fix 問が出てるしやたら solves 数が多いのでなにか抜け穴があるのだろうと思いあれこれ試すと、 su root が通りました。
LINECTF{WOW!_powerful_kernel_oor_oow}
Rev
rolling
19 solves
apk ファイルが与えられます。ひとまず apktool d rolling.apk をします。
smali_classes2/me/linectf/app/MainActivity.smali を見ると、入力が IINECFT{youtube.com/watch?v=dQw4w9WgXcQ} と一致しているか確認しているように見えます。フラグの形式違うけど…？と思いながら submit するも当然弾かれました。
上記ファイルをもう少し注意深く見ると、 lib/arm64-v8a/libnative-lib.so を読み込んで、その中でフラグを check しているようです。というわけで .so ファイルの reversing をします。
deep 関数内でフラグチェックを行っています。 meatbox, soulbox, godbox で各文字を計算した結果がメモリ上の値と一致しているかをチェックしています。メモリ上の値をとりあえず持ってきます。
# 各列は meatbox, soulbox, godbox, 各行は各文字を表す
[
["07", "18", "10"],
["0f", "1c", "12"],
["05", "0a", "07"],
["0b", "02", "0f"],
["12", "06", "08"],
["13", "0a", "07"],
["05", "09", "0b"],
["06", "0f", "0f"],
["11", "04", "13"],
["13", "01", "0e"],
["03", "0b", "00"],
["01", "01", "09"],
["09", "02", "08"],
["13", "01", "0e"],
["01", "01", "0c"],
["09", "05", "10"],
["01", "12", "0a"],
["08", "0b", "12"],
["11", "04", "13"],
["01", "01", "0c"],
["13", "01", "0e"],
["12", "00", "0e"],
["08", "0b", "12"],
["01", "0f", "0b"],
["03", "0b", "00"],
["01", "01", "0c"],
["07", "05", "04"],
["08", "0b", "12"],
["08", "18", "0f"],
["08", "18", "0f"],
["0e", "1c", "0f"],
["01", "12", "0a"],
["10", "15", "11"],
["01", "01", "0c"],
["06", "16", "0a"],
["08", "0b", "12"],
["11", "04", "13"],
["01", "12", "0a"],
["01", "01", "0c"],
["0e", "1c", "0f"],
["01", "12", "0a"],
["01", "01", "0c"],
["03", "0b", "00"],
["09", "02", "08"],
["04", "0d", "10"],
["01", "01", "0c"],
["06", "16", "0a"],
["04", "0d", "10"],
["04", "0d", "10"],
["11", "0f", "05"],
["07", "17", "02"]
]meatbox とかは既知の何かなのかと思ってググりましたが、特に何も見つからず… (ゲームが元ネタっぽい？)
動作を追うのはとても大変だったので、 aarch64 を qemu とかで実行してその上で gdb でデバッグしようと考えました。しかしクロスコンパイルが上手くいかず、環境準備なども含め5時間ぐらい溶かしてしまいました… (誰かやり方わかる人いたら教えてください、全力で募集しています)
あまりに時間が溶けて自暴自棄になり、上の暗号化結果だけから平文を求められないかを試しました。例えば頻度を見ると ["01", "01", "0c"] がたくさんあるため、これは _ になりそう。 ABCCDEF (同じアルファベットは同じ文字が入ることを表す) という単語は問題文中にある rolling という文字になりそう。2文字、3文字と続くところは in the とかになりそう。といった感じです。英語として存在する言い回しがあるかなどを検索しながら頑張ると、フラグがある程度求まりました。
encs = [
L ["07", "18", "10"],
I ["0f", "1c", "12"],
N ["05", "0a", "07"],
E ["0b", "02", "0f"],
C ["12", "06", "08"],
T ["13", "0a", "07"],
F ["05", "09", "0b"],
{ ["06", "0f", "0f"],
w ["11", "04", "13"],
a ["13", "01", "0e"],
t ["03", "0b", "00"],
c ["01", "01", "09"],
h ["09", "02", "08"],
a ["13", "01", "0e"],
_ ["01", "01", "0c"],
k ["09", "05", "10"],
n ["01", "12", "0a"],
o ["08", "0b", "12"],
w ["11", "04", "13"],
_ ["01", "01", "0c"],
a ["13", "01", "0e"],
b ["12", "00", "0e"],
o ["08", "0b", "12"],
u ["01", "0f", "0b"],
t ["03", "0b", "00"],
_ ["01", "01", "0c"],
r ["07", "05", "04"],
o ["08", "0b", "12"],
l ["08", "18", "0f"],
l ["08", "18", "0f"],
i ["0e", "1c", "0f"],
n ["01", "12", "0a"],
g ["10", "15", "11"],
_ ["01", "01", "0c"],
d ["06", "16", "0a"],
o ["08", "0b", "12"],
w ["11", "04", "13"],
n ["01", "12", "0a"],
_ ["01", "01", "0c"],
i ["0e", "1c", "0f"],
n ["01", "12", "0a"],
_ ["01", "01", "0c"],
t ["03", "0b", "00"],
h ["09", "02", "08"],
e ["04", "0d", "10"],
_ ["01", "01", "0c"],
d ["06", "16", "0a"],
e ["04", "0d", "10"],
e ["04", "0d", "10"],
p ["11", "0f", "05"],
} ["07", "17", "02"]
]とりあえず全部小文字のまま提出しましたが、当然弾かれます…不定性は小文字・大文字・leet にあります。submit でブルートフォースすればなんとかなりそうだけど、流石にルール違反 (時間をかけてやれば scoreboard server への攻撃には該当しないかもだが、流石に自重した) なのでやめました。これはどうしようもない。
ということでここまでわかったけどなんかいい方法ある？とチームに雑に投げたら、 angr でやったけど上手く行かなかった script が共有されました。自分は angr に詳しくないので何をやっているかは不明なのですが、 godbox などを呼んだあとの q0 register の値だけは正しい値を格納していそうなことだけわかりました。これを使って大文字小文字leetそれぞれを入力したときの値を調べることでフラグを調べました。
LINECTF{watcha_kn0w_ab0ut_r0ll1ng_d0wn_1n_th3_d33p}
筋肉だけで結構惜しいところまで求まっていた。
TODO: angr スクリプトある程度理解してここに追記する。なんなら angr で自動で解きたい (ここまでできてるなら解けるはずでしょ)
復習
Pwn: trust code
TODO: pwn っぽいことしなくても AES-CBC の特性を上手く使えば任意シェルコード送れそう、と思っているところでチームの人が正攻法で突破してくれたので、自分でも解き直してみる。
Rev: rolling
TODO: angr でちゃんと解く