Writeup for Lazy STEK in LINE CTF 2022

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111

#!/usr/bin/env sage

from sage.all import *
from Crypto.Util.number import long_to_bytes as lb
from Crypto.Util.number import bytes_to_long as bl
from binascii import unhexlify, hexlify
from sage.all import *
import struct
import hashlib

def bytes_to_polynomial(block, a):
    poly = 0
    bin_block = bin(bl(block))[2 :].zfill(128)
    for i in range(len(bin_block)):
        poly += a^i * int(bin_block[i])
    return poly

def polynomial_to_bytes(poly):
    return lb(int(bin(poly.integer_representation())[2:].zfill(128)[::-1], 2))

def convert_to_blocks(ciphertext):
    return [ciphertext[i:i + 16] for i in range(0 , len(ciphertext), 16)]

def xor(s1, s2):
    if(len(s1) == 1 and len(s1) == 1):
        return bytes([ord(s1) ^^ ord(s2)])
    else:
        return bytes(x ^^ y for x, y in zip(s1, s2))

def pad(data):
    if 0 != len(data) % 16:
        data += b"\x00" * (16 - len(data)%16)
    return data

F, a = GF(2^128, name="a", modulus=x^128 + x^7 + x^2 + x + 1).objgen()
R, x = PolynomialRing(F, name="x").objgen()


PSK1 = bytes.fromhex("256f6e3b40c2c006f26dbe24b70c6ed6e875cec70f64aac0de67af2caaaaaaaa450abecfee723cdbe4393bbcf56add91e283615eaa6a5899906a138ce3dbe632ab778328029499c12eceefa0589945f7f3801748be3daa06ace2e682a77649da535f7235aa7ecb60bf0e3d6b7c1012e192411e29e6494c2fa05ce2c5d08d4698a05ffb5fa9ad2b2550737cea3b19ccacfdd93e7d3c3f6e641d5f8793b17261047b160c9acaf891577ef700000000000000000000000000000000")
PSK2 = bytes.fromhex("256f6e3b40c2c006f26dbe24b70c6ed6e875cec70f64aac0de67af2caaaaaaaa450abecfee723cdbe4393bbce26a50c35bd4b250c5395150b62c27d76e20535dea6a129d08c1c31e89475b79d36e45f7f3801748be3daa06ace2e682a77649da535f7235aa7ecb60bf0e3d6b7c1012e192411e29e6494c2fa05ce2c5d08d4698a05ffb5fa9ad2b2550737cea3b19ccacfdd93e7d3c3f6e641d5f1f668e1af6844a40e4cbdb6132cbd39500000000000000000000000000000000")
PSK3 = bytes.fromhex("ffd08593ad673b9005296a50f603af28c336d16a10aac82969a59560bbbbbbbb6fe550ba6db4b6a2af74f6f0454d82d959daa387f694685dec4c1ff7c36e40d3b9fe6e4fd41596035a594f8b599b89c47c84aa66d6d63ef3999de5041f0c3b7598b1811012399575a0c442c1c364f669ecf7fd5dfbb06bc37fd830c03e3dde20c98bc747d74d0ac196936f364c2e81338fca4bdb193d52e19f23295fc9e7546288a7464baa258fcd554200000000000000000000000000000000")


keyName0 = PSK1[:16]
iv0 = PSK1[16:32]

keyName1 = PSK3[:16]
iv1 = PSK3[16:32]


# Set correct values
ct1 = PSK1[32:-32]
C11 = bytes_to_polynomial(pad(ct1[0:16]), a)
C12 = bytes_to_polynomial(pad(ct1[16:32]), a)
C13 = bytes_to_polynomial(pad(ct1[32:48]), a)
C14 = bytes_to_polynomial(pad(ct1[48:64]), a)
C15 = bytes_to_polynomial(pad(ct1[64:80]), a)
C16 = bytes_to_polynomial(pad(ct1[80:96]), a)
C17 = bytes_to_polynomial(pad(ct1[96:112]), a)
C18 = bytes_to_polynomial(pad(ct1[112:122]), a)
T1 = PSK1[-32:-16]
T1_p = bytes_to_polynomial(T1, a)


ct2 = PSK2[32:-32]
C21 = bytes_to_polynomial(pad(ct2[0:16]), a)
C22 = bytes_to_polynomial(pad(ct2[16:32]), a)
C23 = bytes_to_polynomial(pad(ct2[32:48]), a)
C24 = bytes_to_polynomial(pad(ct2[48:64]), a)
C25 = bytes_to_polynomial(pad(ct2[64:80]), a)
C26 = bytes_to_polynomial(pad(ct2[80:96]), a)
C27 = bytes_to_polynomial(pad(ct2[96:112]), a)
C28 = bytes_to_polynomial(pad(ct2[112:122]), a)
T2 = PSK2[-32:-16]
T2_p = bytes_to_polynomial(T2, a)


AD = keyName0 + iv0

len_aad = len(AD)
len_txt = len(ct1)
L = ((8 * len_aad) << 64) | (8 * len_txt); L
L = int(L).to_bytes(16, byteorder='big'); L

L_p = bytes_to_polynomial(L, a)

A1 = bytes_to_polynomial(pad(keyName1), a)
A2 = bytes_to_polynomial(pad(iv1), a)

# Here G_1 is already modified to include the tag
G_1 = (A1 * x^11) + (A2 * x^10) + (C11 * x^9) + (C12 * x^8) + (C13 * x^7) + (C14 * x^6) + (C15 * x^5) + (C16 * x^4) + (C17 * x^3) + (C18 * x^2) +  (L_p * x) + T1_p
G_2 = (A1 * x^11) + (A2 * x^10) + (C21 * x^9) + (C22 * x^8) + (C23 * x^7) + (C24 * x^6) + (C25 * x^5) + (C26 * x^4) + (C27 * x^3) + (C28 * x^2) +  (L_p * x) + T2_p

P = G_1 + G_2


auth_keys = [r for r, _ in P.roots()]
for H, _ in P.roots():
    # print("\nH: " + str(H) + "\n" + str(polynomial_to_bytes(H).hex()))

    Ek0x00 = polynomial_to_bytes(H)        # 16bytes
    key1 = hashlib.sha256(Ek0x00).digest() # 32bytes

    d = hashlib.sha512(key1).digest()      # 64bytes

    # check
    if d[:16] == keyName1:
        aesKey1 = d[16:32]
        print("aesKey1: ", aesKey1, aesKey1.hex())

# aesKey1:  b'\x97I\nrk\xb1\xb5\xf0\xb2\r\x19\x1cF\xeaO\xd7' 97490a726bb1b5f0b20d191c46ea4fd7

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

package main

import (
	"crypto/aes"
	"crypto/cipher"
	"crypto/sha256"

	"fmt"
)

func main() {
	encrypted := []byte{0xff, 0xd0, 0x85, 0x93, 0xad, 0x67, 0x3b, 0x90, 0x5, 0x29, 0x6a, 0x50, 0xf6, 0x3, 0xaf, 0x28, 0xc3, 0x36, 0xd1, 0x6a, 0x10, 0xaa, 0xc8, 0x29, 0x69, 0xa5, 0x95, 0x60, 0xbb, 0xbb, 0xbb, 0xbb, 0x6f, 0xe5, 0x50, 0xba, 0x6d, 0xb4, 0xb6, 0xa2, 0xaf, 0x74, 0xf6, 0xf0, 0x45, 0x4d, 0x82, 0xd9, 0x59, 0xda, 0xa3, 0x87, 0xf6, 0x94, 0x68, 0x5d, 0xec, 0x4c, 0x1f, 0xf7, 0xc3, 0x6e, 0x40, 0xd3, 0xb9, 0xfe, 0x6e, 0x4f, 0xd4, 0x15, 0x96, 0x3, 0x5a, 0x59, 0x4f, 0x8b, 0x59, 0x9b, 0x89, 0xc4, 0x7c, 0x84, 0xaa, 0x66, 0xd6, 0xd6, 0x3e, 0xf3, 0x99, 0x9d, 0xe5, 0x4, 0x1f, 0xc, 0x3b, 0x75, 0x98, 0xb1, 0x81, 0x10, 0x12, 0x39, 0x95, 0x75, 0xa0, 0xc4, 0x42, 0xc1, 0xc3, 0x64, 0xf6, 0x69, 0xec, 0xf7, 0xfd, 0x5d, 0xfb, 0xb0, 0x6b, 0xc3, 0x7f, 0xd8, 0x30, 0xc0, 0x3e, 0x3d, 0xde, 0x20, 0xc9, 0x8b, 0xc7, 0x47, 0xd7, 0x4d, 0xa, 0xc1, 0x96, 0x93, 0x6f, 0x36, 0x4c, 0x2e, 0x81, 0x33, 0x8f, 0xca, 0x4b, 0xdb, 0x19, 0x3d, 0x52, 0xe1, 0x9f, 0x23, 0x29, 0x5f, 0xc9, 0xe7, 0x54, 0x62, 0x88, 0xa7, 0x46, 0x4b, 0xaa, 0x25, 0x8f, 0xcd, 0x55, 0x42, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0}

	pt, _ := decryptTicket(encrypted)
	fmt.Println(pt)
	fmt.Println(string(pt))
}

func decryptTicket(encrypted []byte) (plaintext []byte, usedOldKey bool) {
	// if len(encrypted) < 16+aes.BlockSize+sha256.Size {
	// 	return nil, false
	// }
	tagsize := 16
	// keyName := encrypted[:16]
	iv := encrypted[16 : 16+aes.BlockSize]
	ciphertext := encrypted[16+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 := [16]byte{0x97, 0x49, 0xa, 0x72, 0x6b, 0xb1, 0xb5, 0xf0, 0xb2, 0xd, 0x19, 0x1c, 0x46, 0xea, 0x4f, 0xd7}

	block, err := aes.NewCipher(key[:])
	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[:16+aes.BlockSize])
	if err != nil {
		return nil, false
	}

	return pt, false
}