# Making complex boolean circuits that give true as output only for a specific combination of boolean inputs

This is my first question on a stack exchange website so please bear with me. I am making challenges for a jeopardy style capture the flag event in my college and I had come across the minetest challenge in the hardware section of google CTF qualifier conducted last year. A clean and organized solution to this problem has been provided by liveoverflow.

I would like to design a simpler version of this problem for my college's CTF event but I am unable to design a complex circuit that gives true output only for a specific combination of inputs. I know that a circuit with this functionality is not very difficult to implement and just needs to represent the following logic:

trueinput1 AND trueinput2 AND ... NOT falseinput1 AND NOT falseinput2 ...


However I want it to be vast and complicated so that participants cannot decode its functionality just by doing a visual analysis. Is there any technique to complicate the boolean logic above and to design a corresponding circuit that looks ugly even for a small number of inputs(32/64).

• use discrete transistors to implement it(pass transistor logic or domino logic for example), I think it would not be easy to decode just by looking. May 27, 2020 at 15:03

One basic strategy would be:

• Choose a function f that is easily computable and collision-free on your input space. This could be anything from AES-encrypting with a fixed key to just XORing with a constant sequence. Or add some constant and take the result modulo some prime. The choice of f will determine how difficult your challenge will be, you can really go wild here.
• Design a circuit C that computes f on the inputs
• Compute f(x) of your desired correct input value (flag) x
• Add a NOT-gate to every output of C that corresponds to a bit that is 0 in f(x). This will make sure that all outputs are 1 if your input matches x (and only then, because f is collision-free).
• Combine all outputs with AND gates to get your final output

How about a bank of ROM chips (PROM, EPROM, EEPROM, or whatever you can find a programmer for)?

Feed the signal into the address pins of the ROMs. Add a simple bit of logic that picks one data bit out from each ROM and ANDs them together.

You can implement arbitrary boolean logic with memory devices:

If we have a function $$\ Y = (A \cdot B) + (\overline C \cdot D)\$$ and assuming I use bit zero as the output state and A = Address bit 0, B = address bit 1, C = address bit 2 and D = address bit 3, then:

I have a function that should be true if address xx11 is present, or if address 10xx is present.

So for all addresses that match that pattern, load a 1 in the memory cell. If the matching pattern is present on the address bits, then the output will be '1'.

This can be expanded to arbitrarily large functions across multiple memory devices if necessary (that requires a bit more work as one of the address inputs would need to be a cascade bit from the next higher order memory device).

I have implemented translation tables this way (such as binary to gray code conversions).

• For multiple devices: Couldn't one of your address bits just be used as a chip select for two memory devices? And then use a decoder to scale it to arbitrarily many. No need for a cascading thing unless I'm missing some nuance. May 27, 2020 at 15:49