Section 4.3 - 4.4

I'm still unclear to how exactly differential cryptanalysis works. Just like DES it seems very magical and things "just work" without any formal proof. I don't understand how all the XORing manages to remove the key from the message and are we assuming that the adversary has access to our S-box or is the S-box universal? This was something I wasn't sure about either while reading the DES section. The lemma regarding the cycle of length n was cool because of the way it was used to proof DES is closed under composition. It didn't strike me as obvious at first but now I see how it makes sense.