30
Apr
2012

Plaid CTF 2012 – ECE’s Revenge II

For this challenge we were supposed to reverse engineer the logic of some stuff laid out on 3 breadboards based on a couple of photos. The final goal was to figure out the correct position for 24 dip switches in order to turn a single LED on.

This is the what we had to work with:
breadboard madness!
(luckily there were some additional pictures highlighting specific parts in more detail.. :))

It seems more daunting than it really is, for one .. not *all* dipswitches are actually connected. If you inspect the photos closely you can see that board1 has 6 switches connected, board2 has 5 and board3 only has 4 switches connected.

So, time to dive into this logic and investigate what is what.. we have a couple of chips:


Board 1:
 * CD4048BE -- CMOS Multifunction Expandable 8-Input GateΒ 
 * CD4068BE -- CMOS 8-INPUT NAND AND GATE
 * 74HC86N  -- Quad 2-input EXCLUSIVE-OR gate

Board 2:
 * 74LS86N  -- Quad 2-input Exclusive-OR gate
 * 74LS08N  -- QUAD 2-INPUT AND GATE
 * 74LS32M  -- Quad 2-Input OR Gates
 * 74LS04BN -- Hex inverter

Board 3:
 * 74HC86N -- Quad 2-input Exclusive-OR Gate
 * 74HC58NΒ -- Dual AND-OR gate
 * 74LS04  -- Hex Inverter
 * 74LS08  -- Quad 2-INPUT AND GATE

Scary stuff, right? Not really, most of these chips are multiples of basic logic gates in a single IC package. The most “complex” chip is the CD4048BE, which has a configurable logic outcome based on a couple of control signals (A, B, C,)

After diving into some datasheets to get a (basic) understanding of the chips we figured it was time to properly untangle the wiremess on the picture into something readible -to geeks-, schematics! πŸ™‚ (Click for bigger version)

Board #1

Board #2

Board #3

Et voila, board schematics .. it took a while to get this 100% right.

Board2 has 2 output signals that get fed into board1 again, and board3 has one output signal that gets fed into board1. This way everything is tied together and theoretically there should be only one valid permutation of dipswitch configuration for every board. We quickly determined the 3 external inputs for board1 _should_ be 1 for the final LED to be able to turn on at all, this means we can assume an output signal of [1,1] for board2 and [1] for board3 in our test cases.

But we’re not there yet, now we need to reimplement all this logic in something a computer understands, so we can enumerate all possible settings for the dipswitches in order to recover the one and only correct sequence.

Let’s go with some dirty PHP code:

<?
    error_reporting(E_ALL);

    function board1($s, $board) {
        # 0/0/0 [0] = NOR
        # 1/0/1 [5] = NAND
        # 1/0/0 [4] = AND
        # 0/0/1 [1] = OR
        # 1/1/1 [7] = AND+OR
        # 1/1/0 [6] = AND+NOR
        # 0/1/1 [3] = OR+NAND
        # 0/1/0 [2] = OR+AND

        for($i=0;$i<6;$i++)
            $s[$i] = $s[$i]^1;

        $xor0 = $s[1] ^ $s[2];
        $xor1 = $s[3] ^ $s[2];
        $xor2 = $s[0] ^ $s[1];
        $xor3 = $s[5] ^ 1;

        // config gate
        $i = array(
            $xor3, $xor0, $xor0, $xor0,
            $s[4], $s[4], $s[4], $s[3]
        );

        $chip_func = ($xor1 << 2) | ($s[2] << 1) | $s[2];

        $e = $s[0];

        // this emulates the CD4048BE πŸ˜‰
        switch($chip_func) {
            case 0: // NOR
                $output = ~($i[0] | $i[1] | $i[2] | $i[3] | $i[4] | $i[5] | $i[6] | $i[7] | $e) & 1;
            break;
            case 1: // OR
                $output = ($i[0] | $i[1] | $i[2] | $i[3] | $i[4] | $i[5] | $i[6] | $i[7] | $e);
            break;
            case 2: // OR+AND
                $a = ($i[0] | $i[1] | $i[2] | $i[3]);
                $b = ($i[4] | $i[5] | $i[6] | $i[7]);

                $output = ($a & $b & ($e^1));
            break;
            case 3: // OR+NAND
                $a = ($i[0] | $i[1] | $i[2] | $i[3]) & 1;
                $b = ($i[4] | $i[5] | $i[6] | $i[7]) & 1;

                $output = ~($a & $b & ($e^1));
            break;
            case 4: // AND
                $output = ($i[0] & $i[1] & $i[2] & $i[3] & $i[4] & $i[5] & $i[6] & $i[7] & ($e^1));
            break;
            case 5: // NAND
                $output = ~($i[0] & $i[1] & $i[2] & $i[3] & $i[4] & $i[5] & $i[6] & $i[7] & ($e^1)) & 1;
            break;
            case 6: // AND+NOR
                $a = ($i[0] & $i[1] & $i[2] & $i[3]) & 1;
                $b = ($i[4] & $i[5] & $i[6] & $i[7]) & 1;

                $output = (~($a | $b | $e)) & 1;
            break;
            case 7: // AND+OR
                $a = ($i[0] & $i[1] & $i[2] & $i[3]) & 1;
                $b = ($i[4] & $i[5] & $i[6] & $i[7]) & 1;

                $output = ($a | $b | $e);
            break;
        }

        $and0 = $xor3;
        $and1 = $s[1];
        $and2 = $xor2;
        $and3 = $board[2];
        $and4 = $output;
        $and5 = $board[0];
        $and6 = $board[1];
        $and7 = 1;

        return ($and0 & $and1 & $and2 & $and3 & $and4 & $and5 & $and6 & $and7);
    }

    function board2($s) {
	for($i=0;$i<count($s);$i++)
		$s[$i] ^= 1;

        $and0 = $s[0] & $s[1];

        $xor0 = $s[0] ^ $s[1];
        $xor2 = $s[3] ^ $s[2]; 
        $xor1 = $and0 ^ $xor2;
        $xor3 = $s[4] ^ $s[0];

        $and1 = $xor2 & $and0;
        $and2 = $s[3] & $s[2];
        $and3 = $s[4] & $s[0];

        $or0 = $and1 | $and2;
        $xor4 = $xor3 ^ $or0;

        $and7 = $xor3 & $or0;
        $or1 = $and7 | $and3;

        $and4 = ($xor0^1) & $xor4;
        $and5 = ($or1^1) & $xor1;
        $and6 = $and5 & $and4;

        $otherA = $and6;
        $otherB = $s[0];

	return array($otherA, $otherB);
    }

    function board3($s) {
        $and4 = ($s[0]^1);
        $and5 = ($s[1]) ^ 1;
        $and6 = ($s[2]^1) & ($s[3]^1);
        $and7 = ($s[2]^1) & ($s[3]^1);

        $or0 = $and4 | $and5;
        $or1 = $and6 | $and7;

        $xor0 = $or1 ^ $or0;
        $xor1 = ($s[0]^1) ^ ($s[1]^1);
        $xor2 = 0; // unused output signal
        $xor3 = $xor1 ^ $xor0;

        $and0 = $xor3 & ($s[1]);
        $and1 = $and0 & ($s[0] ^ 1);

        return $and0;
    }

    echo "\nBOARD1:\n";
    for($i=0;$i<=63;$i++) {
        $n = str_split(str_pad(decbin($i), 6, "0", STR_PAD_LEFT));

        for($j=0;$j<=7;$j++) {
            $n2 = str_split(str_pad(decbin($j), 3, "0", STR_PAD_LEFT));
            $o = board1($n, $n2);
            if ($o == 1)
                echo (implode("", $n)).":".implode("", $n2)." = ".board1($n,$n2)."\n";
        }
    }

    echo "\nBOARD2:\n";
    for($i=0;$i<=31;$i++) {
        $n = str_split(str_pad(decbin($i), 5, "0", STR_PAD_LEFT));
        $o = board2($n);
        if ($o[0] == 1 && $o[1] == 1)
            echo (implode("", $n))." = 1,1!!\n";
    }

    echo "\nBOARD3:\n";
    for($i=0;$i<=15;$i++) {
        $n = str_split(str_pad(decbin($i), 4, "0", STR_PAD_LEFT));
        $o = board3($n);
        if ($o == 1)
            echo (implode("", $n))." = 1!!\n";
    }
?>

After lots of iterations and fixups to both the schematics and the script, it eventually produced this:

$ php logic_bla.php 
BOARD1:
101001:111 = 1

BOARD2:
00111 = 1,1!!

BOARD3:
0100 = 1!!
1100 = 1!!

Nice! board3 returns 2 possible values, so looks like we still have a small error here… but even if board3 is completely wrong, that only leaves 16 possibilities. πŸ˜‰

And thus, the final correct bitsetting for all dipswitches is (in board order): 10100100 00111000 01000000 which gives us the flag 1_pr3f3r_p0tat0_ch1p5 !

{3 Responses to “Plaid CTF 2012 – ECE’s Revenge II”}

  1. I was completely thrown by the CD4048BE. The datasheet calls for Vss on Pin 15 (EXPAND) when not in use. Had I overlooked this detail, I could have had another 500 points; the difference between 8th and 7th. πŸ™