Backdoor Designer Key Recovery in LowMC-M

Question

The paper https://eprint.iacr.org/2020/986.pdf proposed a framework for embedding a malicious backdoor in LowMC cipher, that will later help the designer to recover the secret key in the known-plaintext attack setting.

As the framework is scalable, suppose a cipher with 16 bit block size of 3 rounds is constructed. The framework generates the necessary constant parameters (RC, key matrices, linear layer matrices etc.) for designing a cipher along with deterministic differential characteristics for key recovery. For the above setting with 2 differential characteristics embedded, it generates as

How the designer knowing the tweak pairs and the Plaintext differences can be able to recover the key in a short span of time in contrast to an attacker not knowing any of these parameters.

How the key can be recovered using plain differential cryptanalysis in this setting, I am confused or not getting the elaboration presented on page 17 and page 19? Will the designer be able to recover the round keys or the main key being input to cipher?

According to the article, only one differential characteristics (tweak pair) is able to recover the key, but for enhanced security more should be embedded? How one differential characteristics (tweak pair) embedded over r-1 round will be able to recover the key?

Answer 1

This would be done by a last round attack. The attacker would collect a crib of known pairs of inputs that differ by the plaintext difference (01010001101011 in your example). They would then run through $2^{16}$ guesses for the last round key, for each guess they would be able calculate the difference between each pair in round $r-1$ (by running just one round of the decryption process) and look for instances of the target difference (0111101010100100 in your case). In cases where they had guessed incorrectly, the target difference would not show up (or perhaps once); in the case of a correct guess the target would show up repeatedly.

Once the last round key is known, this drastically cuts down the number of main keys that could have produced it and (depending on key schedule) the main keys that are possible can then be exhausted.