[OT] Can a combinatorial hardware circuit solve a crypto problem?
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.
On 10/2/14, Georgi Guninski <guninski@guninski.com> wrote:
DISCLAIMER: I am noob at electronics, this is crazy or at best a fishing expedition... ... If you are lucky to hit stable state, you have solved $f(x)=x$.
what you are describing in a round about way is an adiabatic representation of brute force. the jury is out, and certainly not with existing fabrication, but potentially 2^64 cost for a 128 bit key. this is why TOP SECRET demands 256 bit keys. (also Grover's algorithm, among other reasons?) "the literature" should be enlightening, given these terms to key on. best regards,
On Thu, Oct 02, 2014 at 12:24:17PM -0700, coderman wrote:
On 10/2/14, Georgi Guninski <guninski@guninski.com> wrote:
DISCLAIMER: I am noob at electronics, this is crazy or at best a fishing expedition... ... If you are lucky to hit stable state, you have solved $f(x)=x$.
what you are describing in a round about way is an adiabatic representation of brute force. the jury is out, and certainly not with existing fabrication, but potentially 2^64 cost for a 128 bit key. this is why TOP SECRET demands 256 bit keys. (also Grover's algorithm, among other reasons?)
"the literature" should be enlightening, given these terms to key on.
best regards,
Thanks. By "existing fabrication" do you mean we can't manufacture good enough circuit for this purpose (modulo time 2^64)? What is considered wire on the circuit in practice is resistor and the wires will have different resistances which might influence the unorthodoxal experiment?
participants (2)
-
coderman
-
Georgi Guninski