[OT] Can a combinatorial hardware circuit solve a crypto problem?
Georgi Guninski
guninski@guninski.com
Thu Oct 2 04:42:12 PDT 2014
DISCLAIMER: I am noob at electronics, this is crazy or
at best a fishing expedition...
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 neither inputs nor inputs (basically
loop the circuit $f$).
Power on.
Measure (possibly with oscilloscope) $i_j=o_j$.
If you are lucky to hit stable state, 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 the question is not entirely insane, is there better
forum?
---
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.
The engineer told me these circuits don't make
sense in electronics. (So what?).
I wouldn't trust a software simulation for this,
might be wrong.
The experiments were too simple, so it is
possible electric current to solve easy problems
and not solve hard problems.
More information about the cypherpunks
mailing list