# Can a combinatorial hardware circuit with no inputs solve a crypto problem?

I am noob at electronics but in short I am interested in stable states of circuit with no inputs which represents a boolean formula.

Let $f$ be some hash function, say md5. Restrict the size of input to be equal to the output (128 bits for md5).

Cryptographer told be it is open problem if there is solution to $f(x)=x$ (treated as sequence of bits).

Implement $f$ as pure combinatorial circuit (NO CLOCK), with 128 $i_k$ inputs and 128 outputs $o_k$.

For all $j$, connect $i_j$ with $o_j$ so the circuit doesn't have inputs(basically loop the circuit $f$).

Power on.

Measure (possibly with oscilloscope) $i_j=o_j$.

If you are lucky to hit stable state (logically consistent), you have solved $f(x)=x$.

In an unstable stable (no solution), maybe one will measure very high frequency.

Probably this is well studied, though an engineer couldn't find reference for the general case.

1. Are there references for this?

2. If it fails why will it fail?

3. If a solution exists is it known for how long it will be found?

4. If this makes sense, would please someone try it on something simple, though not entirely trivial?

Partial experimental results:

It wasn't easy, but me convinced an engineer to test it on bare metal.

Take $n$ inverters (logical negation) and loop them in a cycle (basically this corresponds to the cycle graph $C_n$).

There are no input and no outputs.

For even $n$ the circuit has exactly 2 stable states.

For odd $n$, there is no stable state since the boolean formula is unsatisfiable.

The engineer worked with NAND gates on a stand.

Experimentally, for $n=4$, the engineer reached stable state. Depending on which NAND gates he chose, the stable state differed.

For $n=3$ there was no stable state. The voltage was in the middle between logical 0-1, possibly with high frequency which his oscilloscope couldn't measure.

I wouldn't trust a software simulation for this, might be wrong.

The experiments were too trivial, so it is possible electric current to solve easy problems and not solve hard problems.

Someone suggested this is "adiabatic bruteforce", though still can't find the right search terms.

• This question is the only result that comes up searching for "adiabatic bruteforce". Commented Oct 6, 2014 at 14:49
• @GiulioMuscarello google doesn't index everything. In response to essentially the same question, check the thread, "adiabatic representation of brute force" Commented Oct 6, 2014 at 14:52
• You do in fact have inputs, at the very least those encoded in the design of the system itself. It is entirely possible to solve problems by building a custom circuit for each one, but it's rather inefficient compared to loading inputs into an engine generic to a particular type of problem. Most illustratively, consider an FPGA, where one critical input is a configuration file which controls which internal gates or look-up-tables feed which others. Often FPGA designs have traditional "inputs" - but it's also possible to change their configuration at runtime for each problem. Commented Oct 6, 2014 at 15:01
• What kind of crypto problem are you trying to solve? f(x) = x? f(x) = y with a fixed value of y? ... Commented Oct 6, 2014 at 17:03

## 2 Answers

The general field of digital logic without a clock is asynchronous logic. Research has been done in this area but it hasn't really been commercialised.

Your cryptographic example might fail for two reasons:

• it may find a cycle, possibly a long one, that produces a sequence of values but does not converge on the desired solution. This is a mathematical aspect of the problem rather than an implementation detail.

• If you use regular logic and don't have some system for keeping signal propagation in sync, you won't compute the right thing at all, as some parts of the answer will be ready before others, which in turn will perturb the input. See the "Muller C-element" for a solution to this.

Your engineer should have told you that you were reinventing the "ring oscillator". These are often used in conjunction with phase-locked-loops to produce high frequency digital clocks that are some multiple of an input clock without using a high-frequency crystal.

• Thank you. What about the other questions? Would you please give reference to peer reviewed papers for as close as what I am asking? In defense of the engineer, she told me "Odd # of inverters is essentially the same as X". I didn't care about X and didn't include it in the questions -- these are just experimental results about the questions. Commented Oct 6, 2014 at 14:48
• Commented Oct 6, 2014 at 15:08
• Is there a rough estimate for the time of state change? Probably this will depend on the implementation. Commented Oct 7, 2014 at 6:45

You're wrongly assuming that such a machine would always loop through all the possible inputs; this isn't the case. You might enter a loop that does not span through the entire input space.

For example, let's try to solve this cryptographical problem:

Let H(n) be a hash function, defined thus: H(n) = n + 2. This function takes four bits in and returns four bits. Any carry bit (eg. 15 + 2 = 17 = 10001) is ignored (in our case, H(17) = 1 = 0001)
Find x such that H(x) = 3.

You build a circuit representing the behaviour of H(n): it takes four inputs, and four outputs. Its current output is 0000. Now, you wire the inputs I1, I2, I3, I4 to the outputs O1, O2, O3, O4. What happens?

Instant 0: the output is 0000 [0].
Instant 1: the output is 0010 [2].
Instant 2: the output is 0100 [4].
Instant 3: the output is 0110 [6].
Instant 4: the output is 1000 [8].
Instant 5: the output is 1010 [10].
Instant 6: the output is 1100 [12].
Instant 7: the output is 1110 [14].

Instant 8: the output is 0000 [0].
Instant 9: the output is 0010 [2].
...

See where this is going? The circuit will loop through only a few states, and may never reach the solution.

Now, I thought of a trivial example to illustrate this concept, but this also works for real hashing functions like MD5 or SHA1.

Let I = {0x00...01, 0x00...02, ... 0xff...ff} be the list of 256-bit unsigned integers, and let S(x): I -> I be the SHA256 hashing function.

Apply S(x) to each element in I. You are extremely likely to find collisions: that is, two values that hash to the same value (say H(0x00...01) = H(0xEE...EE)). If a collision exists, then the set I is larger than its image with respect to S: that is, there are elements in I which don't have a counterimage, meaning they can't be obtained by hashing a 256-bit value.

TLDR: It might be mathematically impossible to solve a problem using your method.

• Have you tried this on metal/silicon? Why it's current output is 0000? Commented Oct 6, 2014 at 15:34
• Huh, I am not assuming "such a machine would always loop through all the possible inputs" Commented Oct 6, 2014 at 15:38
• 0000 is just an example. A circuit will have a particular bootup value. Don't get hung up on particular numbers, the point is that the system may get stuck in a loop that doesn't cover the solution space. Commented Oct 6, 2014 at 15:39
• @pjc50 as I wrote, I am not interested in software simulations. Would you please test this specific counterexample on hardware -- probably this won't be hard for an expert. Commented Oct 6, 2014 at 15:46
• Giulio Muscarellom, what does your analysis suggest for 3 inverters in a loop? Commented Oct 6, 2014 at 16:01