Straightline
Crypto challenge from ECW 2023
Straightline
I won’t go into much details in the reverse stuff, you can always ask on the ECW discord or me directly for more details.
The problem
We are given a rust script which is supposed to run in the backend of a webpage. This webpage lets us get a token for our username and we need the token of the username “admin”.
The script implements SHA3 which is a hash algorithm. The main part of the script is the following :
impl Alice {
pub fn init() -> Alice {
let mut key: Key = [0u8; KEY_SIZE];
OsRng.fill_bytes(&mut key);
Alice { key }
}
pub fn gen_token(&self, username: &str) -> Hash {
// hash(key || message)
let mut payload = vec![0u8; self.key.len() + username.as_bytes().len()];
payload[..self.key.len()].copy_from_slice(&self.key);
payload[self.key.len()..].copy_from_slice(username.as_bytes());
alice_hash(&payload)
}
pub fn verify_token(&self, username: &str, token: &Hash) -> bool {
let token_calc = self.gen_token(username);
token_calc == *token
}
}
We can see that a random key of length 16 is prepended to our username, then the sha3 hexdigest of the message is computed. Because to my knowledge the normal SHA3 is safe to every known attack (even length extension) the implementation might be faulty (otherwise they could just import it).
According to wikipedia, sha3 has 5 steps for each round : theta, rho, pi, chi, iota. However our sha3 implementation only have 4 steps, indeed chi is missing.
What can we do with the fact that chi is missing ?
The solution
Wikipedia also tells us something really cool :
χ (chi)
Bitwise combine along rows, using x ← x ⊕ (¬y & z). To be precise, a[i][j][k] ← a[i][j][k] ⊕ (¬a[i][j+1][k] & a[i][j+2][k]). This is the only non-linear operation in SHA-3.
chi is the only non-linear step of sha3.
What this means for us is that now our hash digest can be expressed as a linear combination of the input message bits in GF(2). So basically our robust hash just shuffle the bits and xor them, which is reversible and really weak.
Just a side note : the same thing happens for AES if you remove the s-box.
What was breaking the linearity in chi was the “not” (¬) and the “and” (&) which are not reversible when combined and destroy any linear relation.
The goal is now to get the token for a known username (I choose “m” because why not), recover the key and then forge our admin token.
Because I like sagemath and symbolic variable I decided to implement a symbolic version of sha3 in sagemath and then solve the equations.
Alert messy code incoming.
So we’ll first create 128 variables in GF(2)[x], we put them in some weird 8 bytes little endian because of sha3 devs.
P = PolynomialRing(GF(2),names=",".join(f"x{i}" for i in range(64*2)))
va = list(P.gens())
va = [va[i:i+8] for i in range(56,-1,-8)] + [va[i:i+8] for i in range(56+64,-1+64,-8)]
va = [item for sublist in va for item in sublist]
va = [va[i:i+64] for i in range(0,len(va),64)]
Remember that sha3 takes block of 136 bytes as input so our 128 variables only cover only the first sixteen bytes which are the unknown key.
So we craft our real payload :
def pad(a):
b = a+b"\x06"+b"\x00"*(136-2-(len(a)%136))+b"\x80"
return b
def bytes_to_format(a):
b = [0 for _ in range(200)]
for i,c in enumerate(a):
b[i] = c
b = [int.from_bytes(bytes(b[i:i+8]),"little") for i in range(0,len(b),8)]
return b
payload = va + [list(map(int, bin(a)[2:].zfill(64))) for a in bytes_to_format(pad(b"0123456789abcdefm"))][2:]
We then run the symbolic sha3 algorithm with our payload and store the result as a big bit array, I only take 256 bits of the output because it’s the 256 bits of the real output, what the f_l function returns is the internal state (the full implementation will be in the final solve script):
res = f_l(payload)[:4]
res = res[0]+res[1]+res[2]+res[3]
res looks like this :
[x0 + x1 + x3 + x7 + x8 + x10 + x11 + x14 + x16 + x17 + x19 + x21 + x25 + x27 + x29 + x30 + x35 + x38 + x39 + x41 + x46 + x47 + x50 + x51 + x52 + x53 + x54 + x57 + x61 + x65 + x66 + x67 + x69 + x72 + x74 + x78 + x79 + x80 + x81 + x82 + x85 + x87 + x88 + x89 + x90 + x92 + x93 + x94 + x95 + x96 + x99 + x101 + x102 + x103 + x104 + x107 + x108 + x111 + x120 + x124 + x126, x1 + x2 + x4 + x9 + x11 + x12 + x15 + x17 + x18 + x20 + x22 + x24 + x26 + x28 + x30 + x31 + x32 + x36 + x39 + x42 + x47 + x51 + x52 + x53 + x54 + x55 + x56 + x58 + x62 + x64 + x66 + x67 + x68 + x70 + x72 + x73 + x75 + x79 + x80 + x81 + x82 + x83 + x86 + x88 + x89 + x90 + x91 + x93 + x94 + x95 + x96 + x97 + x100 + x102 + x103 + x105 + x108 + x109 + x121 + x125 + x127, x0 + x2 + x3 + x5 + x10 + x12 + x13 + x16 + x18 + x19 + x21 + x23 + x24 + x25 + x27 + x29 + x31 + x32 + x33 + x37 + x40 + x43 + x52 + x53 + x54 + x55 + x57 + x59 + x63 + x64 + x65 + x67 + x68 + x69 + x71 + x73 + x74 + x76 + x80 + x81 + x82 + x83 + x84 + x87 + x88 + x89 + x90 + x91 + x92 + x94 + x95 + x97 + x98 + x101 + x103 + x106 + x109 + x110 + x112 + x122 + x126, x1 + x3 + x4 + x6 + x8 + x11 + x13 + x14 + x16 + x17 + x19 + x20 + x22 + x25 + x26 + x28 + x30 + x33 + x34 + x38 + x40 + x41 + x44 + x48 + x53 + x54 + x55 + x58 + x60 + x65 + x66 + x68 + x69 + x70 + x72 + x74 + x75 + x77 + x80 + x81 + x82 + x83 + x84 + x85 + x88 + x89 + x90 + x91 + x92 + x93 + x95 + x98 + x99 + x102 + x107 + x110 + x111 + x113 + x120 + x123 + x127 + 1, ... ]
So each output bits is a combination of our symbolic variables in input. Combining this and our token for the user “m”, we can create 256 equations with 128 variables and recover the 128 variables and hence the secret key.
Let’s create de matrix with all our variables :
regex = r"\d+"
bs = [[0 for i in range(128)] for _ in range(256)]
for i in range(256):
for m in list(res[i]):
if "x" in str(m):
l = list(map(int, re.findall(regex,str(m))))
bs[i][l[1]] ^^= 1
else:
goal[i] ^^=1
mat = Matrix(GF(2), bs)
For each line we have a 1 if the variable is used and a 0 if it’s not so the first line looks like this :
[1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0]
Now we can set up our goal vector and solve the equations :
goal = bytes.fromhex("2f8a16e6f4fd98993d1ca13c131515a87eb1adb65806f12725c98fec7599333b") # Comes from the website, I didn't code the connection
goal = "".join(bin(int.from_bytes(goal[i:i+8],"little"))[2:].zfill(64) for i in range(0,len(goal),8))
goal = list(map(int, goal))
assert len(goal) == 256
sol = mat.solve_right(vector(GF(2),goal))
secret = int("".join(list(map(str, sol))),2).to_bytes(16,"big")
Now that we have the secret we can finish the challenge by making our admin token and using it on the website. Because I like to lost time I also implemented a normal sha3 in my solve script (without the chi step).
Solve script:
from Crypto.Util.number import bytes_to_long
import re
regex = r"\d+"
def pad(a):
b = a+b"\x06"+b"\x00"*(136-2-(len(a)%136))+b"\x80"
return b
def rol(a,n):
a = int(a)
n = int(n%64)
return int((a<<n)%2**64 | (a>>(64-n))%2**64)
RC = [
0x0000000000000001, 0x0000000000008082, 0x800000000000808A, 0x8000000080008000,
0x000000000000808B, 0x0000000080000001, 0x8000000080008081, 0x8000000000008009,
0x000000000000008A, 0x0000000000000088, 0x0000000080008009, 0x000000008000000A,
0x000000008000808B, 0x800000000000008B, 0x8000000000008089, 0x8000000000008003,
0x8000000000008002, 0x8000000000000080, 0x000000000000800A, 0x800000008000000A,
0x8000000080008081, 0x8000000000008080, 0x0000000080000001, 0x8000000080008008
]
def iota(a,ir):
a[0] ^^= RC[ir]
return a
def rho(a):
xx = 1
yy = 0
for t in range(24):
a[xx%5+(yy%5)*5] = rol(a[xx%5+(yy%5)*5],(t + 1)*(t + 2)//2)
tmp = xx
xx = yy
yy = int((2*tmp + 3*yy) % 5)
return a
def pi(a):
b = [c for c in a]
for x in range(5):
for y in range(5):
b[x+5*y] = a[(x+3*y)%5 + 5*x]
return b
def theta(a):
c = [0 for _ in range(5)]
for x in range(5):
c[x] = a[x]
for y in range(1,5):
c[x] ^^= a[x+5*y]
d = [0 for _ in range(5)]
for x in range(5):
temp = c[(x+1)%5]
temp = rol(temp,1)
d[x] = temp ^^ c[((5+x)-1) % 5]
for x in range(5):
for y in range(5):
a[x+5*y] ^^= d[x]
return a
def iota_l(a,ir):
a[0] = [aa+rr for aa,rr in zip(a[0],list(map(int, bin(RC[ir])[2:].zfill(64))))]
return a
keccakf_piln = [
10, 7, 11, 17, 18, 3, 5, 16, 8, 21, 24, 4,
15, 23, 19, 13, 12, 2, 20, 14, 22, 9, 6, 1
]
keccakf_rotc = [
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 2, 14,
27, 41, 56, 8, 25, 43, 62, 18, 39, 61, 20, 44
]
def rho_pi_l(a):
t = a[1]
for i in range(24):
j = keccakf_piln[i]
bc = a[j]
a[j] = t[keccakf_rotc[i]:] + t[:keccakf_rotc[i]]
t = bc
return a
def pi_l(a):
b = [c for c in a]
for x in range(5):
for y in range(5):
b[x+5*y] = a[(x+3*y)%5 + 5*x]
return b
def theta_l(a):
c = [[0 for i in range(64)] for _ in range(5)]
for x in range(5):
c[x] = a[x]
for y in range(1,5):
c[x] = [cc+aa for cc,aa in zip(c[x],a[x+5*y])]
d = [[0 for i in range(64)] for _ in range(5)]
for x in range(5):
temp = c[(x+1)%5]
temp = temp[1:]+temp[:1]
d[x] = [tt+cc for tt,cc in zip(temp,c[((5+x)-1) % 5])]
for x in range(5):
for y in range(5):
a[x+5*y] = [aa+dd for aa,dd in zip(a[x+5*y],d[x])]
return a
def f(a):
for ir in range(24):
a = theta(a)
a = rho(a)
a = pi(a)
a = iota(a,ir)
return a
def f_l(a):
for ir in range(24):
print(f"{ir = }")
a = theta_l(a)
a = rho_pi_l(a)
a = iota_l(a,ir)
return a
def bytes_to_format(a):
b = [0 for _ in range(200)]
for i,c in enumerate(a):
b[i] = c
b = [int.from_bytes(bytes(b[i:i+8]),"little") for i in range(0,len(b),8)]
return b
P = PolynomialRing(GF(2),names=",".join(f"x{i}" for i in range(64*2)))
va = list(P.gens())
va = [va[i:i+8] for i in range(56,-1,-8)] + [va[i:i+8] for i in range(56+64,-1+64,-8)]
va = [item for sublist in va for item in sublist]
va = [va[i:i+64] for i in range(0,len(va),64)]
payload = va + [list(map(int, bin(a)[2:].zfill(64))) for a in bytes_to_format(pad(b"adminadminadmin1m"))][2:]
print(payload)
print(bytes_to_format(pad(b"m")))
print([hex(a) for a in f(bytes_to_format(pad(b"m")))])
goal = bytes.fromhex("2f8a16e6f4fd98993d1ca13c131515a87eb1adb65806f12725c98fec7599333b")
goal = "".join(bin(int.from_bytes(goal[i:i+8],"little"))[2:].zfill(64) for i in range(0,len(goal),8))
goal = list(map(int, goal))
assert len(goal) == 256
res = f_l(payload)[:4]
res = res[0]+res[1]+res[2]+res[3]
bs = [[0 for i in range(128)] for _ in range(256)]
for i in range(256):
for m in list(res[i]):
if "x" in str(m):
l = list(map(int, re.findall(regex,str(m))))
bs[i][l[1]] ^^= 1
else:
goal[i] ^^=1
print(bs[0])
mat = Matrix(GF(2), bs)
for i,line in enumerate(mat.transpose()):
if 1 not in line:
print(i,"missing")
print(4%5+11)
sol = mat.solve_right(vector(GF(2),goal))
secret = int("".join(list(map(str, sol))),2).to_bytes(16,"big")
print(secret.hex())
print(b"".join(int(a).to_bytes(8,"little") for a in f(bytes_to_format(pad(secret+b"admin")))[:4]).hex())
Flag : ECW{straightline_3JkVlUzOp77aN2pr}