In this paper, we develop an information theoretic differential side-channel attack. An embedded device containing a secret key is modeled as a black box with a leakage function whose output is captured by an adversary through the noisy measure- ment of a physical observable e.g. the power consumed by the device. We assume only that the measured values depend somehow on the leakage and thus on the word being processed by the device. Without any knowledge on the particular dependency, this fact is exploited to mount a side-channel attack. We build a distinguisher which uses the Mutual Information between the observed and the leaked values as a statistical test. The Mutual Information is maximal when the hypothetical key guessed by the attacker equals the key in the device. Our approach is confirmed by experimental results. We perform power analysis on an embedded device using our Mutual Information based distinguisher and show that the correct key is clearly distinguishable. Finally, our approach allows to com- pute a good estimate of the minimal number of traces required to perform a successful attack and gives an upper bound on the information leakage in a single observation.