4
$\begingroup$

Twofish was an AES candidate and it uses $4 \times 4$ Matrix as MDS followed by a PHT.

The Branch Number of MDS and PHT is 5 and 2 Respectively.

from formula

$Branch~Number = Minimum~of~[HammingWeight(Input) + HammingWeight(Output)]$

Now if i want to represent the MDS and PHT with a black box operation with a branch number of $X$, what could be the value of $X$?

will it be $X = 5 + 2 = 7$

will it be $X = 2$ (because of the minimum of branch numbers of MDS and PHT i.e 5 and 2)

will it be $X = 5$ (because of the maximum of branch numbers of MDS and PHT i.e 5 and 2)

since i can not bruteforce the whole $2^{64}$ input space to find it, so any efficient method to find branch number for both the operations combined?

$\endgroup$
  • $\begingroup$ where do you get the information that says the branch number of the PHT is 3? $\endgroup$ – Richie Frame May 10 '16 at 10:24
  • $\begingroup$ As Richie Frame intimated, the branch number of the PHT is 2. To see why, if $PHT(A,B) = 2A+B,A+B$, consider a situation where only the most significant bit of $A$ is differentially active before the PHT. $\endgroup$ – J.D. May 10 '16 at 11:10
  • $\begingroup$ @J.D. Thanks alot for the correction, i overlooked the case you mentioned. Any idea or help about the problems i mentioned in the question? One thing more, in case of an 4x4 MDS, if i brute force whole input space of 2^32 and finds the minumum value of addition of input and output hamming wieghts as 7, then can it be said to have brance number of 7? on the other hand every where a 4x4 MDS is said to have optimal branch number of 5. $\endgroup$ – khan May 10 '16 at 18:04
  • $\begingroup$ Note that the pht is defined on 2 blocks of 4 bytes each, so its a bit complicated. Will formulate an answer later. $\endgroup$ – kodlu May 11 '16 at 7:41
  • $\begingroup$ @kodlu will be waiting for some help. what i have in mind is to brute force all the inputs with Hamming Weight of 8 and below, and then see the branch number of the result of MDS & PHT combined as one operation. If all the branch numbers are above 7, then i can treat the MDS & PHT operation combined as a single operation with branch number of 7. $\endgroup$ – khan May 11 '16 at 10:12
3
$\begingroup$

I'm not sure about your definition, so let's take branch number in terms of the byte-wise differential branch number, i.e. the branch number of a function $F(x)$ is $$\mathcal{B}_{F(x)} = \min_{a,b \neq a}\{ w(a \oplus b) + w(F(a) \oplus F(b))\}$$ where $w(x)$ is the number of non-zero bytes in $x$.

In this case, the branch number of the Twofish round function can be no greater than 5.

To see why, consider the situation where the PHT only has a branch number of 2 - i.e. if you start the PHT with only the most significant bit of word $A$ being differentially active (defining the PHT as $PHT(A,B) = 2A+B,A+B$). In that case, after the PHT only a single byte is active (the byte containing the most significant bit of $A+B$).

Now go back to the situation just before the PHT and think about performing the round function in reverse. There is a single 32-bit word that is active, and of that word only a single byte is active. Applying the MDS layer in reverse, this translates into 4 bytes being differentially active at the start of the round function. So the Twofish round function has a branch number of at most 4+1 bytes.

But ... is the branch number less than 5? That I don't know, though it would seem difficult for it to be so given that the branch number of each MDS is 5. There would have to be a scenario where few active bytes before the MDS translate into many active bytes prior to the PHT which then translates into few active bytes after the PHT. Ruling out such a scenario would prove that the branch number was in fact 5.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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