I'm supposed to show the complement property of DES ($c=DES(p,k) => \bar c = DES(\bar p, \bar k)$).
My idea was to just start the algorithm with $\bar p$ and see what happens (ignoring the initial permutation for now). I looked at it step by step and got the the point where $R1 = \bar L1 \oplus f(\bar k1, \bar R0)$. So I figured I had to show that $f(\bar k1, \bar R0) = \bar f(k1,R0)$. Is that even right so far? Because I got stuck at the point where the S-Boxes are used. Why would $S(\bar x) = \bar S(x)$?
Somewhere else I read something about a formal prove using induction, but I don't know how I would do that either...