nreboud/GreHack2019_CTF_challenge.md

## GreHack2019_CTF_challenge.md

      
    Raw
  

              GreHack2019_CTF_challenge.md
            
          
    GreHack2019 CTF challenge

One of the challenges of the GreHack2019 CTF was a white-box.
The White-box has been pushed to the SideChannelMarvels Project.
1. White-box? What is that?

White-box cryptography is presented here : http://www.whiteboxcrypto.com/. If you are not fammilair with the concept, Brecht Wyseur itroduced it well in "white-box cryptography: hiding keys in software", MISC magazine, April 2012
2. GreHack2019 White-box

The GreHack2019 CTF white-box is very classic AES128 white-box implementation. The fact that it implements an AES can be found by having a look to the code and by identifying the 11 rounds or by simply looking to the input sample "Who Is Rijndael".
The algorithm used in the wite-box implementation is mostly straightforward. The state is divided into 32 nibbles of 4 bits that are encodded separately. The encoding functions are randoms 16-byte permutations. They are refreshed after each use.
Each 256-byte table tabulates a basic operation. For instance, the addRoundKey operation is implemented as follows:
For i in [0, 255]:

Decode the two nibbles of i to obtain the decoded i value.
Perform a XOR operation with the subkey byte: i' = i ^ k
Encode each nibble of i' with new encoding functions.

3. OK but how do I break it?

In the allotted time, the easiest way to break it was probably a DFA using the wellknown "Piret and Quisquater 2003" or it's revisited by Giraud and Thillard version.
The state has 5 additional bytes mostly used for mixColumn operations, but it is always handled in order. The positions of the different bytes of the state are not mixed. Therefore, on the first rounds we always have:

[0, 15] -> state of the AES,
[16; 20] -> additional variables,
[21; 42] -> not used in the first rounds.

There is a small anti-DFA mechanism that protects the 3 last rounds of the AES: the state is doubled before entering the mixColumn of round 8.
s[41] = t_696[s[0]];
s[40] = t_697[s[1]];
s[39] = t_698[s[2]];
[...]
s[23] = t_714[s[18]];
s[22] = t_715[s[19]];
s[21] = t_716[s[20]];

From this moment, all the operations are doubled and we used both bytes of the state are and bytes of the redundancy state (positions 21 to 42).
After the last round, the following operations are performed:

each byte state[i] of the state is xored with state[(i+1)%15] and its miror state[41 - ((i+1)%15)]
last addRounKey
compare each byte of the state and its mirror. If they are equal, return it else add it modulo 15.

To circumvent this countermeasure it is thus necessary to inject a fault on a byte of the state and on its mirror. Since the encoding functions are different, we have 1 chance on 256 of obtaining a usable faulted output.
DCA

As there is no masking, DCA attacks have a high probability of success, but they require adequate tools and advanced knowledge. It is using a DCA attack that the only team that managed the challenge proceeded. For more information, visit the Side Channel Marvel Project page.