Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

This is a follow up question to this question: Crack cryptographic hash functions using Toffoli gates?.

Suppose there is a hash function $$H(x)=y,$$ where $x$ is the input of the function and $y$ is the hash of $x$. Now, suppose we have made an emulating software that emulates $H(x)$ using Toffoli gates. This new function can be denoted by $$T(x)=(y,z),$$ where $z$ is the garbage. Now toffoli gates are reversible, so we can make a function $$T^{-1}(y,z)=x.$$ Now the problem is that we do not know $z$, because it was lost during the calculation of $H(x)$.

Now we can choose any random (but valid) garbage $z'$ and calculate $$T^{-1}(y,z')=x'.$$ Now by definition of $T^{-1}$, we have $T(x')=(y,z')$; and so $$H(x')=y.$$ So we have found a collision (if not the original value).


I know very less about cryptography, and I know something must be wrong in the above but I cannot find out what is wrong. So, please tell me what is wrong. I do not have the neccesary information and software to test this procedure.


Example

This is a very simple example. More complicated examples can be difficult to calculate by hand.

Suppose $x\in(0,1)$ and $H(x)=x\land1$. Now we will try to reverse the output $H(x)=0$. Now let's denote the toffoli gate by $G(x,y,z)$. The function $H(x)=x\land 1$ can be converted into $$T(x)=(y,z) \rightarrow G(x,1,0)=(y,z_1,z_2).$$ Reverse of this is $$T^{-1}(y,z)=(x) \rightarrow G^{-1}(y,z_1,z_2)=(x,1,0).$$ We have $y=1$. Let's choose $z'=(1,0)$. Now calculate $$T^{-1}(1,(1,0))=1 \Leftarrow G^{-1}(1,1,0) = (1,1,1).$$ So, we have $H(1)=1$. This is the answer! (Because $1\land1=1$)

share|improve this question
1  
I think you need additional inputs with fixed value when rewriting the circuit using toffoli's. When you reverse the circuit you don't get back those fixed values. –  CodesInChaos Feb 11 at 12:06
    
@CodesInChaos Sorry, I couldn't understand that. Could you please provide an example? –  Kartik Feb 11 at 12:07
    
I guess the new function has to be denoted as $T(x, c) = (y, z)$ where $c$ is a constant. So $T^{-1}$ will give you a $x,c$ pair, but with an invalid $c$. –  CodesInChaos Feb 11 at 12:08
    
@CodesInChaos But $c$ can be hard coded in $T(x,c)$ and we can convert it to $T(x)$ again. –  Kartik Feb 11 at 12:11
    
You can't hardcode it if you want to support all possible values of $x,z$. Garbage values of $z$ won't match the fixed $c$. –  CodesInChaos Feb 11 at 12:49

3 Answers 3

up vote 4 down vote accepted

The question errs precisely at the point when it writes: $$\text{and so }H(x')=y.$$

Problem is: that holds for $x'$ matching some garbage $z'$, including $z'=z$, and perhaps other garbage $z'$, but we do not know which garbage (or $z$ unless we know $x$), and I see no reason that it holds for $x'$ obtained from any garbage $z'$ except for trivial $H$; and in the question $z'$ is random.

The only constructive process (as opposed to search) that I can think of to exhibit garbage $z'$ such that $H(x')=y$ is clause resolution or some improvement of that, well known to be exponential, as well as its sequential alternative.


Or otherwise said, my understanding of Toffoli-gate equivalent circuits (still limited, but improved in the process of making the present answer) is that they really are of the form $T(x,z)\mapsto(y,z)$ where it is easy to deduce $z$ from $x$ such that $H(x)=y$ holds, but not to deduce $z$ from $y$ such that $H(x)=y$ holds. Or, if we insist on the $T(x)\mapsto(y,z)$ notation, that is use $z$ built from inputs taken from $x$, we need $x$ to exhibit $z$.

share|improve this answer
    
We have reversed $T$ and got $x'$ so it should hold for any valid garbage. (Because we have got $x'$ by reversing $y,z'$) –  Kartik Feb 11 at 12:46
    
Wait a minute, I'll upload an example. –  Kartik Feb 11 at 12:56
    
I added an example. –  Kartik Feb 11 at 13:19
    
@Kartik: I agree that in your example, what you wrote holds. That's because your example reduces to $H(x)=x$, which we could write with zero gates and no garbage. Problem is, you can't prove an assertion by example. You can disprove it, however. Try something a tad more complex, like $y_0=H(x)=(x_0\land\bar{x_1})\lor(\bar{x_0}\land x_1)$, which unless I err requires at least one bit of garbage. –  fgrieu Feb 11 at 14:07
1  
I think you're right. I'm still trying. If I can't get it till tomorrow, I will accept your answer. –  Kartik Feb 11 at 17:10

Your basic problem is, that your circuit would require infinite many output bits (to be precise, the garbage is infinite). The input for each gate is 3 bit, and you end up with 3 bit. You can duplicate bits in a circuit (by using it as input to multiple gates), but you can NEVER throw away bits or reduce the circuits information. This means, that the output size is at least as large as the input size.

Now the real problem: Hash functions are able to handle potentially any integer input or any size. How do you construct a circuit with infinitely many bits as both input and output? Surely you need also infinitely many gates for such a circuit, because they can not handle a statement like "if there is another block, do this".

Even if you just consider fixed size input, hash functions are highly nonlinear functions (and with a lot of rounds mostly). My guess would be that the number of gates in your circuit are approximately exponential to the size of the input.

share|improve this answer
    
This problem can be avoided if we use a emulating software that automatically creates a fixed size circuit for 1-bit and checks it, then 2 bits, and so on. (A kind of brute force for the length of input. It should be able to stop at 30 bytes, because even the strongest passwords are not 30 chars long) –  Kartik Feb 12 at 5:13
    
You understood something wrong there. You can't just suppose that you can handle 1 bit of input, then 2 and so on, in the reverse design. Anyway, it still stands that you can not throw away information, and the function is highly nonlinear. Even if you can set up the gates for a single input block, the number of gates and trash bits in the out will be way too high. Two basic examples in pseudo-code, where you create extra trash bits (which will carry through to the end): "a=a+b;" and "int i= 0" ... "i=1". –  tylo Feb 12 at 14:51

While trying to reverse the 'hash' that was mentioned in one of the comments, I discovered the real problem. In short, the problem of finding the valid garbage is bigger than the problem of finding the input. That is, the procedure is correct, but it makes the problem more difficult than the original.

The detailed explanation

Suppose you are trying to reverse a 'hash' which includes $x\land \neg x$. This can be represented by the toffoli hash $g(x,g(1,1,x),0)$. Now there are two problems, first that the amount of garbage is much larger than the amount of input, and the second is that if we try to use an invalid garbage, it will lead to a contradiction . In real hashes also it could lead to contradictions. Even if try to track the valid garbages, it would be equivalant to solving the hash. So it is easier to brute force the input than to find a garbage which is valid. Also, there is the problem of variable length input but that can be solved by an emulating software.

share|improve this answer
    
Yes. I think that you'll now agree that if you choose a random garbage $z'$ as in the question, you can compute $x'=T^{-1}(y,z')$ as in the question, but are unlikely to have $H(x')=y$ as in the question for anything except trivial $H$. Also: the only constructive process (as opposed to search) that I can think to find garbage $z'$ such that $H(x')=y$ is clause resolution, well known to be exponential. –  fgrieu Feb 12 at 9:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.