User:Diklasp/sandbox

This is the user sandbox of Diklasp. A user sandbox is a subpage of the user's user page. It serves as a testing spot and page development space for the user and is not an encyclopedia article. Create or edit your own sandbox here. Other sandboxes: Main sandbox | Template sandbox Finished writing a draft article? Are you ready to request review of it by an experienced editor for possible inclusion in Wikipedia? Submit your draft for review!

The rebound attack is a tool in the

The basic idea of the attack is to observe a certain differential characteristic in a block cipher (or in a part of it) or a permutation. Finding values fulfilling the characteristic is achieved by choosing the values the middle, that necessarily realize part of it, and fulfilling the remainder of the characteristic in a probabilistic manner. The rebound attack consists of 2 phases:

1. The inbound (or match in the middle) phase , covers the part of the differential that is difficult to satisfy in a probabilistic way. The goal here is to find many solutions for this part of the characteristic with a low average complexity. The inbound phase may be repeated several times to obtain more starting points for the outbound phase.
2. In the outbound phase each solution of the inbound phase is propagated outwards in both directions, trying to find a solution for the entire characteristic.

For example, if ${\displaystyle E}$ is a block cipher, we'll consider its internal structure as 3 sub-ciphers, ${\displaystyle E=E_{fw}\circ E_{in}\circ E_{bw}}$. The inbound phase is covered by the middle part ${\displaystyle E_{in}}$ . The outbound phase passes the outputs of the inbound phase through ${\displaystyle E_{fw}}$ and ${\displaystyle E_{bw}}$.

Detailed Description of The Attack on Block Ciphers

Consider a substitution – permutation block cipher, like AES, composed of alternating layers of S-Boxes and linear transformations. The goal in the inbound phase should, is that from a few active bytes in the input and output of the phase, we reach a state with a larger number of active bytes in the input and output of an S-Box (the middle of the phase). Then we try to find values to connect these differences. In the outbound phase, we propagate the differentials and the values backwards and forwards, and try to find a collision (or a near collision).

Truncated differential Characteristic on 4.5 rounds Whirlpool hash function.

${\displaystyle E_{bw}}$
${\displaystyle E_{in}}$
${\displaystyle E_{fw}}$

Pre-computation

The rebound attack requires that we save a pre-computed lookup table for the S-box differences: input - output bytes differentials → possible pairs that cause that differential transition. The table is called the difference distribution table (DDT). Not all input \ output differences pairs have a non zero probability, however, for possible transitions, there is an even number of possible pairs (since (x,y) and (y,x) produce the same difference).

Step 1:

1. Select a difference at random for each active byte in the output of the phase. By propagating it backwards to the output of the S-Box we get a full active state.
2. Choose at random a difference for the active byte of each column in the input of the phase. Propagate the differences forwards to get a full active state in the input of the S-Box.

Step 2:

1. For each input \ output difference, check if the differential transition is possible (using the difference distribution table). If not, repeat the first step.
2. If the difference is possible, there are least 2 pairs of values that satisfy it. That means that if the number of bytes in a state is n, there are at least 2^n possible solutions.

The Inbound Phase

The goal of this phase is to find pairs of values that fulfill a certain truncated differential characteristic according to a specific sequence of active bytes (For example, in the 4.5 rounds attack on Whirlpool we look for a sequence of active bytes as follows: 8 → 64 → 8. The differential probability of such characteristic is very high. Therefore, to find the exact differences and a pair of values that fulfill them, one needs to use the degree of freedom of choosing the values and the differences to find a solution. The inbound phase includes the following steps:

The Outbound Phase

The outbound phase completes the truncated differential characteristic in a probabilistic way. The probability for the success of the propagation in this phase depends on the number of active bytes in the truncated differential in ${\displaystyle E_{fw}}$ and ${\displaystyle E_{bw}}$. For example in the 4.5 attack on Whirlpool the truncated differential characteristic of the form 1 → 8 → 64 → 8 → 1 → 1 (where the numbers refer to the number of active bytes in the state). That means that the propagation of the differences through the MixRows transformation of round 1 and 4 should transform the 8 active bytes to a single active byte (See Figure 2). In their paper Mendel, Rechberger, Schläffer and Thomsen approximated the probability of this transformation as 2⁵⁶. Since the propagation is both in the backwards and forwards directions the probability of this phase in 2^-112 (which means that 2¹¹² solutions for the inbound phase are needed).

Results

On their paper from 2009 (See reference) Mendel, Rechberger, Schlaffer and Thomsen applied the attack on several hash functions. The results of their attacks are specified in the following table .

External Links

• The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl by Florian Mendel, Christian Rechberger, Martin Schlaffer, and Soren S. Thomsen (Fast Software Encryption 2009: 260-276)
• The Rebound Attack on Reduced Grøstl Hash Function by Florian Mendel, Christian Rechberger, Martin Schlaffer, and Soren S. Thomsen (The Cryptographer's Track at RSA Conference 2010: 350-365)
• Rebound Attack on the Full Lane Compression Function by Krystian Matusiewicz, María Naya-plasencia, Ivica Nikolic, Yu Sasaki and Martin Schläffer, (ASIACRYPT '09 Proceedings of the 15th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology Pages 106 – 125)
• Unaligned Rebound Attack - Application to Keccak by Alexandre Duc, Jian Guo, Thomas Peyrin, Lei Wei (IACR Cryptology ePrint Archive Year 2011 / 420 )
• How to Improve Rebound Attacks by María Naya-Plasencia FHNW, Windisch, Switzerland (CRYPTO'11 Proceedings of the 31st annual conference on Advances in cryptology Pages 188-205)
• The Rebound Attack and Subspace Distinguishers: Application to Whirlpool by Mario Lamberger, Florian Mendel, Christian Rechberger, Vincent Rijmen, and Martin Schläffer( IACR Cryptology ePrint Archive, Year. 2010 /198).
• Cryptanalysis of AES based hash functions A PHd theses by Martin Schläffer