For a 128 Bit Block Kalyna Cipher we get 2 Round Diffusion Avalanche Property Similar to AES
If you flip one bit in a Round will lead to 50% bits (Full State) to be flipped after two rounds
∗ SB ∗ SR ∗ MC ∗∗∗∗∗∗∗∗ XK ∗∗∗∗∗∗∗∗
∗∗∗∗∗∗∗∗ SB ∗∗∗∗∗∗∗∗ SR ∗∗∗∗∗∗∗∗ MC ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ XK ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗
Procedure (128 Bit Block Size)
First Round - 1 Bit to 4 Bytes
SubBytes (1 Bit to 1 Byte) - 8-bit S-box. Thus if one bit change, the 8 bits of the byte are likely to change. With this step, each bit of a byte depend of each other. It will stay in the same Cell of the Matrix
ShiftRows (1 Byte to 1 Byte (Shifted)) - This modification on the byte is then translated to another cell in the row through the state via ShiftRows (still 1 byte affected)
MixColumns (1 Byte to 4 Bytes) - 1 ByteChange is diffused across the whole Column
moved from 1 byte affected to 4 bytes affected).
Second Round - 4 Bytes to 16 (4 x 4) Bytes
The full state due to the nice coverage provided by Shift Rows and Mix columns.
Thus after 2 rounds, each bit has an influence on the full state.
2 Round Differential Trail - Greedy Algorithm
The above property of Diffusion Avalanche will be very useful in increasing the number of active S-Boxes from 1 to all the 16 Cells by the end of 2 rounds.
Lets start with one active S-Box and chose an input difference αsuch that it leads to the output difference βwith maximal non-trivial differential probability Δmaxπ
Pr[απ1β]=Δmaxπ1=2−5
α SB β SR β MC 8ββ5βββ4β7β6β XK 8ββ5βββ4β7β6β
8ββ5βββ4β7β6β SB ∗∗∗∗∗∗∗∗ SR ∗∗∗∗∗∗∗∗ MC ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ XK ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗
Differential Shortcut Attack
In AES we exploit the Diffusion Avalanche to form a 6 Round Differential Shortcut Attack
This attack takes advantage of the inverse of Two Round Diffusion Avalanche in AES can theoretically break it.
Each Bit of Round Output depends on every bit from Two Rounds Ago
If you Flip One Bit in the output roughly 50% will flip in the input Two Rounds Ago
Since we'll basically be using Inverse ShiftRow and Inverse MixColumns which still add to 2 Round Diffusion Avalanche
However this cannot be done in Kalyna as we have the following problems
Key Invertibility
Unlike AES we cannot invert and get the master key from any of the Round Keys in Kalyna Cipher
This is because of the very complex Key Expansion Process in Kalyna Cipher
However, it allows recovery of odd-round keys from even-round keys and vice-versa.
Modulo Addition 264
Another issue is say even if we inverted the six rounds in the 6 Round Shortcut attack, we have another Non-Linear Operation - Modulo Addition used in Pre-Whitening Phase.
We cannot reverse this operation and still track the differential trail as we don't know how the differential trail changes with this operation.
4 Different S-Boxes
We have 4 different S-Boxes used based on the row number in the State.
Hence these have different Differential Tables (DDT) and lead to different Differential Trails make it very complex to track.
Low Probability
AES also has this unique property where every Input Differential α=0had a corresponding Output Differential βsuch that their characteristic leads to maximal differential probability
Pr[αSβ]=ΔmaxS=2−6∀α=0
Hence there is a total of 255 times AES S-Box leads to Differential uniformity - 4
This is useful in keeping the Differential Trail probability High - 2−24 for 3 Round trail
However Kalyna doesn't have such property and hence we cannot assure high probability Differential trail in the Shortcut attack.