I'm reading an article about authenticated encryption algorithm - PAEQ.

It uses a permutation function AESQ, which has transormations from AES. And there is written about MegaSBoxes, which contain 4 rounds of AES transformation. So, there are 1 active MegaSBox in 4 rounds and 5 active MegaSBox in 8 rounds (because of branch number - 5).

So, the question is what is a branch number and why there are 5 MegaSBoxes, not 2?

More info in this paper (section 3.2.3, after lemma 3).

  • 2
    $\begingroup$ Please add a citation or link to the article you are reading for context. $\endgroup$
    – otus
    Feb 26, 2016 at 12:14
  • $\begingroup$ @asukaev: A paper in which branch number is involved is: www.mathnet.or.kr/mathnet/kms_tex/982865.pdf $\endgroup$ Feb 26, 2016 at 15:42

1 Answer 1


In AES, the MixColumns transform as a branch number of 5, this is because a change to a single byte input causes 4 of the output bytes to change. Like branches of a tree, 1+4=5. This is because MixColumns uses an MDS matrix for multiplications against the input.

AESQ operates on entire 128-bit blocks, which are further broken down into AES round operations. 2 AES round operations create full diffusion of the 128-bit block, so a single AESQ round consists of 2 AES rounds, in 4 parallel paths, followed by a shuffle operation so that 4 bytes from every AES round group go to a different group for the next round. What I am callling an AESQ round here is the output of a shuffle to the next shuffled output, I believe they call this 2 rounds in the paper.

Because the 2 AES rounds offer full diffusion, the branching of AESQ is a change 1 AES input block resulting in a change to 4 bytes of each AES output block. I color coded the blocks to show the distribution of modified bytes due to a change in any input byte over a single AESQ round (built from 8 AES rounds).

enter image description here

Therefore, just like in AES, we need 2 AESQ rounds for full diffusion of a single bit change to the the 512-input. This involves 16 AES rounds and 2 shuffle operations. This is considered MegaMixColumns plus MegaSubBytes, with a branch number of 5. This is called 4 rounds in the paper.

  • $\begingroup$ and why there are 5 MegaSBoxes in 8 rounds? In 4 rounds - 1. So, there might be 2 MegaSBoxes in 8? $\endgroup$
    – asukaev
    Feb 27, 2016 at 19:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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