Can I use a differential that can be traced through the whole cipher with 100% probability? I'm trying to attack a very simple cipher using differential cryptanalysis as a way of becoming familiar with this method. The cipher is so simple that I've found a differential which I can trace through all the rounds of the cipher with 100% probability (it is not 0 of course).

I've read/watched a few tutorials and if I've understood them correctly recovering the last subkey works as follows:


Find $\Delta_X$ which you can trace with high probability.
Choose two plaintexts such $X_1$ and $X_2$ that $X_1 \oplus X_2 = \Delta_X$
Encrypt them, getting $Y_1$ and $Y_2$.
Try to brute force last round's key. For each key: Decrypt the last round for both ciphertexts, getting $Z_1$ and $Z_2$. If $\Delta_Z=Z_1 \oplus Z_2$ is the same as you predicted form $\Delta_X$ the key can be correct. It gets one point.
Repeat it for different plaintext pairs.
The key that has the highest score is probably the correct one.


Maybe I've misunderstood something about DC, if so, the remainder of this question is probably nonsense. That's why I've described what I think differential cryptanalysis is.

But if it's correct:

Key doesn't influence the differential (it holds with 100% prob.) so whatever key I try while decrypting the last round, the differential on it's input is always as expected. Thus I can't eliminate any keys.

This seems suspicious to me - if a differential holds with 100% prob. the cipher is weak, right? Can a cipher be so weak that some attack doesn't work on it? It seems quite strange...
Usually differential cryptanalysis relies on something called the "wrong key randomization hypothesis", which is the assumption that decryption of the last round with the wrong key results in a random difference at the beginning of the last round, while decryption with the correct key will result in the expected difference with the probability of the differential (which hopefully is sufficiently high or low as to be distinguishable from a random difference).  However, if there is a probability one differential going through the entire cipher then by definition that means that decryption with any key will lead to the same difference.

You might try linear cryptanalysis instead.  A probability 1 linear characteristic through the entire cipher will give you 1 bit of the key with just a single known plaintext (Edit to add: poncho adds a good clarification - the probability 1 linear characteristic must involve at least one key bit to be useful for Matsui's algorithm one).  If for some reason there is no linear characteristic through the entire cipher, then you could try differential-linear cryptanalysis using that probability 1 differential through most of the cipher and a short linear characteristic at the end.