# Twofish MDS and PHT

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?

• where do you get the information that says the branch number of the PHT is 3? May 10 '16 at 10:24
• 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.
– J.D.
May 10 '16 at 11:10
• @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. May 10 '16 at 18:04
• Note that the pht is defined on 2 blocks of 4 bytes each, so its a bit complicated. Will formulate an answer later. May 11 '16 at 7:41
• @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. May 11 '16 at 10:12

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$.
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$).