CTFtime.org

Parallel-The-M0le

by zommiommy / Tower of Hanoi

Rating:

Parallel-The-M0le

This programs is a flag-hasher that spawns 14 threadss and apply operations to the flag (in a random order), it print the results, then it re-apply these operation in a slightly different order to a new copy of the flag and print it.

In particular if at the first step it executes the functions:

result1 = f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14

then the second step it execute:

result2 = f1 f2 f3 f4 f5 f6 f14 f13 f12 f11 f10 f9 f8 f7

Since the functions are all injective, we can write the inverse and bruteforce the sequence of 7 functions that applied in a reverse order on result1 and result2 produces the same result.

Once we found this ""collision"" we can bruteforce the last 7 functions until we find a string that starts with ptm{.

// All the functions reversed from the binary, and their inverse.

fn func1(mut flag: Vec<u8>) -> Vec<u8> {
    let mut buffer = vec![0, 0, 0, 0];
    let mut i  = 0;
    while i < flag.len() {
        for j in 0..4 {
            buffer[j] = flag[j + i];
        }

        buffer.swap(3, 0);
        buffer.swap(1, 0);

        for j in 0..4 {
            flag[j + i] = buffer[j];
        }
        i += 4;
    }
    flag
}

fn func1_inv(mut flag: Vec<u8>) -> Vec<u8> {
    let mut buffer = vec![0, 0, 0, 0];
    let mut i  = 0;
    while i < flag.len() {
        for j in 0..4 {
            buffer[j] = flag[j + i];
        }

        buffer.swap(1, 0);
        buffer.swap(3, 0);

        for j in 0..4 {
            flag[j + i] = buffer[j];
        }
        i += 4;
    }
    flag
}

fn func2(mut flag: Vec<u8>) -> Vec<u8> {
    let l = flag.len();
    for i in 0..(l / 2) {
        flag[i] ^= flag[l - i - 1];
    }
    flag
}

fn func2_inv(mut flag: Vec<u8>) -> Vec<u8> {
    let l = flag.len();
    for i in 0..(l / 2) {
        flag[i] ^= flag[l - i - 1];
    }
    flag
}

fn func3(mut flag: Vec<u8>) -> Vec<u8> {
    for i in 0..16 {
        let t = i & 7;
        flag[i] = flag[i] << t | flag[i] >> (8 - t);
    }
    flag
}

fn func3_inv(mut flag: Vec<u8>) -> Vec<u8> {
    for i in 0..16 {
        let t = 8 - (i & 7);
        flag[i] = flag[i] << t | flag[i] >> (8 - t);
    }
    flag
}


fn func4(mut flag: Vec<u8>) -> Vec<u8> {
    let l = flag.len();
    for i in 0..(l / 2) {
        flag[l - i - 1] ^= flag[i];
    }
    flag
}

fn func4_inv(mut flag: Vec<u8>) -> Vec<u8> {
    let l = flag.len();
    for i in 0..(l / 2) {
        flag[l - i - 1] ^= flag[i];
    }
    flag
}

fn func5(mut flag: Vec<u8>) -> Vec<u8> {
    let buffer = b"{reverse_fake_flag}ptm".to_vec();
    for i in 0..16 {
        flag[i] ^= buffer[i];
    }
    flag
}

fn func5_inv(mut flag: Vec<u8>) -> Vec<u8> {
    let buffer = b"{reverse_fake_flag}ptm".to_vec();
    for i in 0..16 {
        flag[i] ^= buffer[i];
    }
    flag
}

fn func6(mut flag: Vec<u8>) -> Vec<u8> {
    for i in 0..16 {
        flag[i] = !flag[i];
    }
    flag
}

fn func6_inv(mut flag: Vec<u8>) -> Vec<u8> {
    for i in 0..16 {
        flag[i] = !flag[i];
    }
    flag
}

fn func7(mut flag: Vec<u8>) -> Vec<u8> {
    for i in 0..16 {
        let mut val = flag[i];
        let mut j = 7;
        let mut tmp = val >> 1;
        while tmp != 0 {
            val = val << 1 | tmp & 1;
            tmp = tmp >> 1;
            j -= 1;
        }
        flag[i] = val << (j & 0x1F);
    }
    flag
}

fn func7_inv(mut flag: Vec<u8>) -> Vec<u8> {
    for i in 0..16 {
        let mut val = flag[i];
        let mut j = 7;
        let mut tmp = val >> 1;
        while tmp != 0 {
            val = val << 1 | tmp & 1;
            tmp = tmp >> 1;
            j -= 1;
        }
        flag[i] = val << (j & 0x1F);
    }
    flag
}

fn func8(mut flag: Vec<u8>) -> Vec<u8> {
    flag.reverse();
    flag
}

fn func8_inv(mut flag: Vec<u8>) -> Vec<u8> {
    flag.reverse();
    flag
}

fn func9(mut flag: Vec<u8>) -> Vec<u8> {
    for i in 0..16 {
        flag[i] += 42;
    }
    flag
}

fn func9_inv(mut flag: Vec<u8>) -> Vec<u8> {
    for i in 0..16 {
        flag[i] -= 42;
    }
    flag
}

fn func10(mut flag: Vec<u8>) -> Vec<u8> {
    for i in 0..16 {
        flag[i] = flag[i] >> 4 & 0xf | flag[i] << 4;
    }
    flag
}

fn func10_inv(mut flag: Vec<u8>) -> Vec<u8> {
    for i in 0..16 {
        flag[i] = (flag[i] >> 4) & 0xf | flag[i] << 4;
    }
    flag
}


fn func11(mut flag: Vec<u8>) -> Vec<u8> {
    for i in 0..16 {
        flag[i] = (
                ((flag[i] & 1) << 4) 
                | flag[i] * 2 & 0x80
                | ((flag[i] & 0x10) << 2)
                | ((flag[i] & 0x4) << 3)
            ) >> 4
            | ((flag[i] & 0x2) << 3) 
            | flag[i] & 0x80
            | flag[i] * 2 & 0x40
            | ((flag[i] & 0x8) << 2);
    }
    flag
}

// we are lazy so to invert the Func11 we just save every input-output pair
const FUNC11MAP: [u8; 256] = [0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85, 2, 3, 6, 7, 18, 19, 22, 23, 66, 67, 70, 71, 82, 83, 86, 87, 8, 9, 12, 13, 24, 25, 28, 29, 72, 73, 76, 77, 88, 89, 92, 93, 10, 11, 14, 15, 26, 27, 30, 31, 74, 75, 78, 79, 90, 91, 94, 95, 32, 33, 36, 37, 48, 49, 52, 53, 96, 97, 100, 101, 112, 113, 116, 117, 34, 35, 38, 39, 50, 51, 54, 55, 98, 99, 102, 103, 114, 115, 118, 119, 40, 41, 44, 45, 56, 57, 60, 61, 104, 105, 108, 109, 120, 121, 124, 125, 42, 43, 46, 47, 58, 59, 62, 63, 106, 107, 110, 111, 122, 123, 126, 127, 128, 129, 132, 133, 144, 145, 148, 149, 192, 193, 196, 197, 208, 209, 212, 213, 130, 131, 134, 135, 146, 147, 150, 151, 194, 195, 198, 199, 210, 211, 214, 215, 136, 137, 140, 141, 152, 153, 156, 157, 200, 201, 204, 205, 216, 217, 220, 221, 138, 139, 142, 143, 154, 155, 158, 159, 202, 203, 206, 207, 218, 219, 222, 223, 160, 161, 164, 165, 176, 177, 180, 181, 224, 225, 228, 229, 240, 241, 244, 245, 162, 163, 166, 167, 178, 179, 182, 183, 226, 227, 230, 231, 242, 243, 246, 247, 168, 169, 172, 173, 184, 185, 188, 189, 232, 233, 236, 237, 248, 249, 252, 253, 170, 171, 174, 175, 186, 187, 190, 191, 234, 235, 238, 239, 250, 251, 254, 255];

fn func11_inv(mut flag: Vec<u8>) -> Vec<u8> {
    for i in 0..16 {
        flag[i] = FUNC11MAP[flag[i] as usize];
    }
    flag
}

fn func12(mut flag: Vec<u8>) -> Vec<u8> {
    for i in 0..16 {
        flag[i] = !(flag[i] ^ i as u8);
    }
    flag
}

fn func12_inv(mut flag: Vec<u8>) -> Vec<u8> {
    for i in 0..16 {
        flag[i] = !(flag[i] ^ i as u8);
    }
    flag
}

fn func13(mut flag: Vec<u8>) -> Vec<u8> {
    for i in 0..16 {
        flag[i] += i as u8;
    }
    flag
}

fn func13_inv(mut flag: Vec<u8>) -> Vec<u8> {
    for i in 0..16 {
        flag[i] -= i as u8;
    }
    flag
}

fn func14(mut flag: Vec<u8>) -> Vec<u8> {
    for i in 0..16 {
        if (flag[i] < b'A') || (b'Z' < flag[i]) {
            if (b'`' < flag[i]) && (flag[i] < b'{') {
                flag[i] = flag[i] - 0x20;
            }
        } else {
            flag[i] = flag[i] + 0x20;
        }
    }
    flag
}

fn func14_inv(mut flag: Vec<u8>) -> Vec<u8> {
    for i in 0..16 {
        if (flag[i] < b'A') || (b'Z' < flag[i]) {
            if (b'`' < flag[i]) && (flag[i] < b'{') {
                flag[i] = flag[i] - 0x20;
            }
        } else {
            flag[i] = flag[i] + 0x20;
        }
    }
    flag
}


const INV_FUNCTIONS: [fn(Vec<u8>) -> Vec<u8>; 14] = [
    func1_inv,
    func2_inv,
    func3_inv,
    func4_inv,
    func5_inv,
    func6_inv,
    func7_inv,
    func8_inv,
    func9_inv,
    func10_inv,
    func11_inv,
    func12_inv,
    func13_inv,
    func14_inv
];
// the two results that are used to bruteforce the flag
const RESULT1: [u8; 16] = [
    42,
    173,
    46,
    90,
    73,
    251,
    45,
    154,
    219,
    144,
    141,
    208,
    14,
    180,
    140,
    138,
];
const RESULT2: [u8; 16] = [
    102,
    7,
    171,
    97,
    159,
    117,
    176,
    39,
    47,
    60,
    30,
    179,
    63,
    233,
    237,
    175,
];

// find the sequence of seven functions that in opposite order yields the same output using result1 and result2 as inputs
fn brute_step_1() -> Vec<u8> {
    for i1 in 0..14 {
        for i2 in 0..14 {
            for i3 in 0..14 {
                for i4 in 0..14 {
                    for i5 in 0..14 {
                        for i6 in 0..14 {
                            for i7 in 0..14 {
                                let mut x: u64 = 0;
                                x |= 1 << i1;
                                x |= 1 << i2;
                                x |= 1 << i3;
                                x |= 1 << i4;
                                x |= 1 << i5;
                                x |= 1 << i6;
                                x |= 1 << i7;
                                if x.count_ones() != 7 {
                                    continue;
                                }

                                let r1 = INV_FUNCTIONS[i1](RESULT1.to_vec());
                                let r1 = INV_FUNCTIONS[i2](r1);
                                let r1 = INV_FUNCTIONS[i3](r1);
                                let r1 = INV_FUNCTIONS[i4](r1);
                                let r1 = INV_FUNCTIONS[i5](r1);
                                let r1 = INV_FUNCTIONS[i6](r1);
                                let r1 = INV_FUNCTIONS[i7](r1);

                                let r2 = INV_FUNCTIONS[i7](RESULT2.to_vec());
                                let r2 = INV_FUNCTIONS[i6](r2);
                                let r2 = INV_FUNCTIONS[i5](r2);
                                let r2 = INV_FUNCTIONS[i4](r2);
                                let r2 = INV_FUNCTIONS[i3](r2);
                                let r2 = INV_FUNCTIONS[i2](r2);
                                let r2 = INV_FUNCTIONS[i1](r2);

                                if r1 == r2 {
                                    println!("{:?}", r1);
                                    println!("{:?}", vec![i1, i2, i3, i4, i5, i6, i7]);
                                    
                                    return r1;
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    panic!("Brute force step 1 failed");
}

// bruteforce the remaining sequence of 7 functions that yields an ouput that starts with `ptm{`
fn brute_step_2(reference: Vec<u8>){
    for i1 in 0..14 {
        for i2 in 0..14 {
            for i3 in 0..14 {
                for i4 in 0..14 {
                    for i5 in 0..14 {
                        for i6 in 0..14 {
                            for i7 in 0..14 {
                                let mut x: u64 = 0;
                                x |= 1 << i1;
                                x |= 1 << i2;
                                x |= 1 << i3;
                                x |= 1 << i4;
                                x |= 1 << i5;
                                x |= 1 << i6;
                                x |= 1 << i7;
                                if x.count_ones() != 7 {
                                    continue;
                                }

                                let r1 = INV_FUNCTIONS[i1](reference.to_vec());
                                let r1 = INV_FUNCTIONS[i2](r1);
                                let r1 = INV_FUNCTIONS[i3](r1);
                                let r1 = INV_FUNCTIONS[i4](r1);
                                let r1 = INV_FUNCTIONS[i5](r1);
                                let r1 = INV_FUNCTIONS[i6](r1);
                                let r1 = INV_FUNCTIONS[i7](r1);

                                if r1.starts_with(b"ptm{") {
                                    for x in r1 {
                                        print!("{}", x as char);
                                    }
                                    print!("\n");
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

fn main() {
    // check that the setup is sane
    let r1 = RESULT1.to_vec();
    assert_eq!(r1, func1_inv(func1(r1.clone())));
    assert_eq!(r1, func2_inv(func2(r1.clone())));
    assert_eq!(r1, func3_inv(func3(r1.clone())));
    assert_eq!(r1, func4_inv(func4(r1.clone())));
    assert_eq!(r1, func5_inv(func5(r1.clone())));
    assert_eq!(r1, func6_inv(func6(r1.clone())));
    assert_eq!(r1, func7_inv(func7(r1.clone())));
    assert_eq!(r1, func8_inv(func8(r1.clone())));
    assert_eq!(r1, func9_inv(func9(r1.clone())));
    assert_eq!(r1, func10_inv(func10(r1.clone())));
    assert_eq!(r1, func11_inv(func11(r1.clone())));
    assert_eq!(r1, func12_inv(func12(r1.clone())));
    assert_eq!(r1, func13_inv(func13(r1.clone())));
    assert_eq!(r1, func14_inv(func14(r1.clone())));
    
    // run the bruteforce
    brute_step_2(brute_step_1());
}

Which gives the result:

$ time cargo run --release
[159, 91, 170, 77, 137, 115, 185, 199, 151, 69, 59, 246, 125, 88, 183, 111]
[7, 8, 13, 3, 9, 11, 6]
ptm{brut¸Õë­öñ¸ò
ptm{brut¸Õë­öñ¸ò
ptm{brut¸Õë­öñ¸ò
ptm{brut¸Õë­öñ¸ò
ptm{brut3_f0rc3}
ptm{brut3_f0rc3}
ptm{brut¸Õë­öñ¸ò
ptm{brut¸Õë­öñ¸ò
ptm{brut¸Õë­öñ¸ò
ptm{brut¸Õë­öñ¸ò
ptm{brut3_f0rc3}
ptm{brut¸Õë­öñ¸ò
ptm{brutÌ ÏÌ
ptm{brutÌ ÏÌ
ptm{brutÌ ÏÌ
ptm{brut3_f0rc3}
ptm{brut3_f0rc3}
ptm{brut3_f0rc3}
ptm{brut¸Õë­öñ¸ò
ptm{brut¸Õë­öñ¸ò
ptm{brut3_f0rc3}
ptm{brut¸Õë­öñ¸ò
ptm{brutÌ ÏÌ
ptm{brut3_f0rc3}
ptm{brutÌ ÏÌ
ptm{brutÌ ÏÌ
ptm{brutÌ ÏÌ
ptm{brutÌ ÏÌ
ptm{brutÌ ÏÌ
ptm{brutÌ ÏÌ
ptm{brutÌ ÏÌ
ptm{brutÌ ÏÌ
ptm{brutÌ ÏÌ
ptm{brutÌ ÏÌ
cargo run --release  5.36s user 0.01s system 99% cpu 5.390 total
Original writeup (https://gist.github.com/zommiommy/507abb7be594e213bd114146634390a0).

Comments