HKCERT-CTF 2020 Sign in Please 請登入

(9)
Sign in Please 請登入
500 Points / 1 Solves

Author

Blackb6a

Solver

T0022 Member 3

Description

I have implemented a secure authentication system. You can't eavesdrop the passwords, can you?

我發明了一個安全的身份驗證系統。反正沒有人能竊聽密碼吧。

nc tertiary.pwnable.hk 50001

Files

chall.py

Analyze

Basically, the challenge is asking for the answer (auth) to the hash given the pbox and the salt, which we do not know in advance.

Also, we are given the function (spy) to test out the hash calculated using our input (pbox and salt) and the unknown password.

The whole string to test is 20-byte long, which composes of the random password (16 bytes) generated at the beginning of the connection and the salt (4 bytes), and the string gets shuffled by the given pbox.

def permutate(payload, pbox):
    return bytes([payload[x] for x in pbox])

Simply speaking, it is returning [payload[pbox[0]], payload[pbox[1]], payload[pbox[2]], ..., payload[pbox[len(pbox) - 1]]] in the form of bytes.

Notice that the permutate process only retrieves the characters with the index given in the pbox, it does not check for the length of the pbox, or any repetition in the pbox.

So initially I would think that it would be useful using a rainbow table to recover the password.

The 16-byte password is generated by encoding a random 12-byte integer using base64, so only the 64 characters used in base64 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/") are possible to appear in the password part.

For example, if we send

$[0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1]$ as the pbox, it is supposed to permutate the payload to a 2-distinct(1-if-duplicated)-character-only string (

$[p[0],p[1],p[0],p[1],...]$), which generated hash can be checked against our rainbow table of every "2-character combination repeated 10 times" (only

$64\times 64=4096$ combinations) to obtain the first 2 characters of the password.

We have only 10 iterations available to test, so at least 2 characters have to be recovered per iteration to recover the password.

A program is created to test this type of pbox, but 'no way!' in the exception part appears.

To find out the issues, we can see that there is a verification check to the pbox.

assert len(set(pbox)) == 20
assert len(salt) == 4

It means that we can only use 4 characters for the salt, and pbox should contain exactly 20 different integers as indices.

I was wondering if I can use different integers to obtain the same element from the payload array. The only possible integers I can think of is negative indices for counting from the end (e.g. 2 and -18 corresponding to the same element in a 20-byte payload)

However, we only have control over the 4-byte salt. So at most we can use 8 bytes for the known characters in the payload, and the remaining 12 bytes are in the password, thus at least 6 elements have to be loaded from the password part.
(e.g. pbox =

$[0,1,2,3,4,5,16,17,18,19,-1,-2,-3,-4,-15,-16,-17,-18,-19,-20]$)
To create a rainbow table for 6 characters, we have to store

${64}^6=2^{36}=68719476736$ values which takes so much time which makes this method impractical.

So the idea of negative indices is abandoned.

So it seems that our last resort is the SHA256 algorithm.

SHA256, which generates a 256-bit hash as indicated in the name, algorithm breaks the payload into 512-bit (64-byte) blocks. The initial hash array is a 256-bit constant split into 8 parts for calculation. The initial hash array for the next block is the hash calculated from the previous block. As it seems that the default hashlib library does not provide the feature to use custom initial hash values, so I crafted my SHA256 library according to the SHA-2 documentation.

Before the calculation, the payload is first padded to the length of a multiple of 512 bits (64 bytes). A '1' bit is appended to the payload first, then '0' bits are appended until there are still 64 bits to a multiple of 512 (

$\text{length}\equiv 448(\text{mod }512)$), then the 64-bit representation of the length of the payload (in bits) is added at the end.

For the default 20-byte payload, the padded payload should appear as below:

+---------------------+------------------+-------------------------------+------------------+
| the 20-byte payload | 128 (0b10000000) | 42-bytes of null (0b00000000) | 160 (0b10100000) |
+---------------------+------------------+-------------------------------+------------------+

where

$160\text{ bits}=20\times 8\text{ bits}$, and 128 is equivalent to a '1' bit and 7 '0' bits.

Therefore, if a length extension attack is carried out to calculate the hash, we have to use the second block.

Also, the content of the first block should not be modified in order to have a known initial hash.
which means, we need chr(128), chr(0) and chr(160) in the salt in order to have the pbox-permutated result containing these bytes.
The order is not important for the pbox, so by default we can use

$[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19]$
as after pbox-permuatation the order of the payload remains the same (and so the first 16-byte is the password we want, which is convenient to us).

Therefore, we carry out our first test using

$[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19]$
as the pbox, and the salt explained below (which is not important in this stage).

(Notice that the assert check only checks for 20 distinct values in pbox, but not repeating elements, so we can definitely send a pbox of more than 20 elements as the input.)

The hash returned is the initial hash array of the 2nd block in SHA256.

To construct the 2nd block that contains our desired value, we would like to use 2 bytes from the password as the start of this block, so each time we can recover 2 bytes of the password after comparing the returned hash from the system to our rainbow table.

The structure of the 2nd block:

+----+----+
| p1 | p2 |
+----+----+

where

$p1$ and

$p2$ are the tested part of the password.
The padded block should appear as below: (Notice that in total we have to send a

$512+2\times 8={210}_{16}$ bits string).

+----+----+------------------+-------------------------------+----------------+-----------------+
| p1 | p2 | 128 (0b10000000) | 59-bytes of null (0b00000000) | 2 (0b00000010) | 16 (0b00010000) |
+----+----+------------------+-------------------------------+----------------+-----------------+

The block size is

$1+1+1+59+1+1=64\text{ bytes}(=512\text{ bits})$

Therefore, the rainbow table is generated using the tested hash received from the server as the initial hash, and

$[c1]+[c2]+[128]+[0]\times 59+[2,16]$
, where

$[c1]$ and

$[c2]$ are substituted by each possible pairs of characters in base64, as the padded payload.

Notice that to achieve that, we have to disable the padding procedure of the SHA256 function, which also seems to be impossible with the default python hashlib library.

After generating the hash table, the next step is to send the pbox and salt.

The supposed content of the payload after permutated by the pbox is

$p1$ and

$p2$ appended just after the first block.
Also, as mentioned before, the pbox can be much longer as long as exactly 20 different elements are found in it.
Besides, the salt has to be crafted carefully so we can have chr(128), chr(0) and chr(160) in the permutated payload.

My chosen salt is

$[0,160,2,128]$ (2 is not used as the input actually)

The custom pbox is created as follows to construct desired pre-padded payload:

$[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19]$ +

$[19]$ (corresponding to 128) +

$[16]$ (corresponding to null bytes)

$\times 42$ +

$[17]$ (corresponding to 160) +

$[n,n+1]$ (the two characters in password we crack)
in these 8 iterations, we have to test all the 16 characters in password, so n corresponds to

$[0,2,4,6,8,10,12,14]$ in these 8 iterations.

After receiving the 8 hashes and comparing them to the rainbow table, the password is recovered, and we have only 1 allowed iteration left.

Therefore, we have to do the authentication this time.

The system provides a random pbox and salt. We can directly copy the functions (parse_pbox and permutate) in the given source code to calculate the permutated payload and the required hash value, and send it to the server.

After that, the flag should be shown if nothing is wrong. Solved.

Example Output

AKACgA==
b'\x00\xa0\x02\x80'
4
[x] Opening connection to tertiary.pwnable.hk on port 50001
[x] Opening connection to tertiary.pwnable.hk on port 50001: Trying 18.163.58.67
[+] Opening connection to tertiary.pwnable.hk on port 50001: Done
b'[cmd] '
b'[pbox] '
b'[salt] '
b'935229df4a638142892d4d18601258858fc1bee30fbec9ce6fa28e5a47d39edd'
b'[cmd] '
b'[pbox] '
b'[salt] '
b'[cmd] '
b'[pbox] '
b'[salt] '
b'[cmd] '
b'[pbox] '
b'[salt] '
b'[cmd] '
b'[pbox] '
b'[salt] '
b'[cmd] '
b'[pbox] '
b'[salt] '
b'[cmd] '
b'[pbox] '
b'[salt] '
b'[cmd] '
b'[pbox] '
b'[salt] '
b'[cmd] '
b'[pbox] '
b'[salt] '
b'[cmd] '
b'[pbox] '
b'[salt] '
b'[hash] '
b'[flag] hkcert20{d0_y0u_feel_s3cur3_wh3n_s19nin9_in?}\n'
[*] Closed connection to tertiary.pwnable.hk port 50001

The source code is given in the Walkthrough Part.

Walkthrough (Codes)

sign in.py (the comments are used to test whether my library works properly)

from pwn import *
import base64, sha256, os
import hashlib

# rainbow table
salt = bytes([0, 160, 2, 128])
salt64 = base64.b64encode(salt).decode()

# test extension
#print(sha256.sha_256("a"*1))
#print(sha256.sha_256(b"a" + bytes([128]) + b"\0" * 61 + bytes([8]) + b"b", True, True))
#print(sha256.sha_256(b"b" + bytes([128]) + b"\0" * 60 + b"\2" + bytes([8]), False, True, i=sha256.sha_256("a"*1)))
#passwordt = base64.b64encode(os.urandom(12))
#print(passwordt + salt)
#init1 = sha256.sha_256(passwordt + salt, byts = True)
#print(sha256.bytes2string(init1))
#init2 = sha256.sha_256(passwordt + salt + bytes([128]) + b'\0' * 42 + bytes([160]) + b'ab', byts = True)
#print(sha256.bytes2string(init2))
#print(sha256.bytes2string(sha256.sha_256(b'ab' + bytes([128]) +  b'\0' * 59 + bytes([2, 16]), pads = False, byts = True, i=init1)))

print(salt64)
print(base64.b64decode(salt64))
print(len(base64.b64decode(salt64)))
rainbow = [""] * (64*64)
def parse_pbox(payload):
    return list(map(int, payload[1:-1].split(',')))


def permutate(payload, pbox):
    return bytes([payload[x] for x in pbox])

per = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/" 


r = remote('tertiary.pwnable.hk', 50001)

password = ""
# get 1 block hash
print(r.recvuntil('[cmd] '))
r.sendline("spy")
print(r.recvuntil('[pbox] '))
r.sendline(str([i for i in range(20)]))
print(r.recvuntil('[salt] '))
r.sendline(salt64)
r.recvuntil('[hash] ')
password = r.recvuntil('\n')[:-1]
print(password)
# break password into bytes
password = [int(password[i:i+8],16) for i in range(0,len(password),8)]

# rainbow table
for ic in range(64):
    for jc in range(64):
        i = per[ic]
        j = per[jc]
        rainbow[ic * 64 + jc] = sha256.bytes2string(sha256.sha_256((i + j).encode() + bytes([128]) + b'\0' * 59 + bytes([2, 16]), False, True, password))
real = ""
for j in range(8):
    print(r.recvuntil('[cmd] '))
    r.sendline("spy")
    print(r.recvuntil('[pbox] '))
    r.sendline(str([i for i in range(20)] + [19] + [16] * 42 + [17] + [j*2, j*2+1]))
    print(r.recvuntil('[salt] '))
    r.sendline(salt64)
    r.recvuntil('[hash] ')
    result = r.recvuntil('\n')[:-1]
    ind = rainbow.index(result.decode())
    real += per[ind // 64] + per[ind%64]
    
print(r.recvuntil('[cmd] '))
r.sendline("auth")
print(r.recvuntil('[pbox] '))
pbox = parse_pbox(r.recvuntil('\n')[:-1].decode())
print(r.recvuntil('[salt] '))
salt = base64.b64decode(r.recvuntil('\n')[:-1])
print(r.recvuntil('[hash] '))
permutated_password = permutate(real.encode() + salt, pbox)
r.sendline(hashlib.sha256(permutated_password).hexdigest())
print(r.recvuntil('\n'))
r.close()

sha256.py

initial_hash_values=[
0x6a09e667,0xbb67ae85,0x3c6ef372,0xa54ff53a,
0x510e527f,0x9b05688c,0x1f83d9ab,0x5be0cd19
]

sha_256_constants=[
0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5,
0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3,
0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc,
0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7,
0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13,
0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3,
0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5,
0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208,
0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
]

def int_to_bytes(x: int) -> bytes:
    return x.to_bytes((x.bit_length() + 7) // 8, 'big')
def int_from_bytes(xbytes: bytes) -> int:
    return int.from_bytes(xbytes, 'big')

def pad(a, pads=True, byts=False):
    le = len(a) << 3
    if byts:
        a = int_from_bytes(a)
    else:
        a = int_from_bytes(a.encode())
    if pads:
        a = (a << 1) + 1
        a = (a << (512 - (le + 65)%512))
        a = (a << 64) + le
    else:
        if le%512 > 0:
            a = (a << (512 - le%512))
    s = hex(a)[2:]
    s = ("0" * 128 + s)[-((len(s)-1)-(len(s)-1)%128+128):]
    #print(s)
    return [int(s[i:i+8],16) for i in range(0,len(s),8)]

INT_MAX = (1 << 32) - 1

def rr(i, p):
    return (INT_MAX & (i << (32-p))) | (i >> p) 

def sha_256(s, pads=True, byts=False, i=initial_hash_values):
    ha = i.copy()
    W = [0] * 64
    bi = pad(s, pads, byts)
    for i in range(0, len(bi), 16):
        a, b, c, d, e, f, g, h = ha
        for j in range(64):
            if j < 16:
                W[j] = bi[j+i]
                #print(j, W[j])

            else:
                w = W[j-15]
                s0 = rr(w, 7) ^ rr(w, 18) ^ (w >> 3)
                w = W[j-2]
                s1 = rr(w, 17) ^ rr(w, 19) ^ (w >> 10)
                # print(s0, s1)
                W[j] = INT_MAX & (W[j-16] + s0 + W[j-7] + s1)
                # print(W[j])
                # input()
            S0 = rr(a, 2) ^ rr(a, 13) ^ rr(a, 22)         
            S1 = rr(e, 6) ^ rr(e, 11) ^ rr(e, 25)
            ch = (e & f) ^ ((INT_MAX - e) & g)
            temp1 = INT_MAX & (h + S1 + ch + sha_256_constants[j] + W[j])
            #print(temp1)
            maj = (a&b)^(a&c)^(b&c)
            temp2 = INT_MAX & (S0 + maj)
            #print(temp2)

            h, g, f, e, d, c, b, a = g, f, e, INT_MAX & (d + temp1), c, b, a, INT_MAX & (temp1 + temp2)
            #print(a,b,c,d,e,f,g,h)
            #input()
        ha = [INT_MAX & (ha[k] + [a,b,c,d,e,f,g,h][k]) for k in range(8)]
    return ha
    
def bytes2string(b):
    s = ""
    for i in range(8):
        s += ("0" * 8 + hex(b[i])[2:])[-8:]
    return s    

Provided Source File(s)

chall.py

# Challenge written by Mystiz.
# Signature: PHNjcmlwdD5jb25zb2xlLmxvZygnVEhJUyBDSEFMTEVOR0UgSVMgV1JJVFRFTiBGT1IgSEtDRVJUIENURiBBTkQgSVMgTk9UIEZPUiBGUkFOS0lFIExFVU5HIFRPIFBMQUdBUklaRS4nKTwvc2NyaXB0Pg==

import base64
import hashlib
import os
import random

from secret import flag


def parse_pbox(payload):
    return list(map(int, payload[1:-1].split(',')))


def permutate(payload, pbox):
    return bytes([payload[x] for x in pbox])


class Server:
    def __init__(self, password):
        assert len(password) == 16
        self.password = password

    def preauth(self):
        pbox = list(range(20))
        salt = os.urandom(4)
        random.shuffle(pbox)
        return pbox, salt

    def auth(self, pbox, salt, hashed_password):
        permutated_password = permutate(self.password + salt, pbox)
        return hashlib.sha256(permutated_password).hexdigest() == hashed_password


class Client:
    def __init__(self, password):
        self.password = password

    def spy(self, pbox, salt):
        assert len(set(pbox)) == 20
        assert len(salt) == 4
        password = self.password
        permutated_password = permutate(password + salt, pbox)

        hashed_password = hashlib.sha256(permutated_password).hexdigest()
        print(f'[hash] {hashed_password}')


def main():
    password = base64.b64encode(os.urandom(12))

    s = Server(password)
    c = Client(password)

    for _ in range(10):
        command = input('[cmd] ')
        try:
            if command == 'spy':
                pbox = parse_pbox(input('[pbox] '))
                salt = base64.b64decode(input('[salt] '))
                c.spy(pbox, salt)
            elif command == 'auth':
                pbox, salt = s.preauth()
                print(f'[pbox] {pbox}')
                print(f'[salt] {base64.b64encode(salt).decode()}')
                hashed_password = input('[hash] ')
                if not s.auth(pbox, salt, hashed_password):
                    raise Exception('No!')
                print(f'[flag] {flag}')
        except:
            print('no way!')


if __name__ == '__main__':
    main()

Flag

hkcert20{d0_y0u_feel_s3cur3_wh3n_s19nin9_in?}

Do you feel secure when signing in?