It is Interstate, from Font Bureau.

Hey Dan, how are you?!?

I deeply believe in your know-how, but are you sure about that?

http://www.myfonts.com/fonts/fontbureau/interstate/

I'm doing great! Back in Offenbach, for the moment at least…

The Karstadt logo sure looks like Interstate to me… here is a comparison image:

The K and the S do look a little tweaked… especially the S!

They definitely use Interstate in some of their advertising and graphics (see http://www.fontblog.de/neue-karstadt-schrift-albertina – in German; the picture is in Albertina, but Interstate is mentioned in the text)

I don't really see Interstate in the logo - the proportions are quite different, not just on the K and the S.
It almost looks like a mishmash of different sources, with the special K, s and low R.
You may want to take a look at Gotham Ultra and then start tweaking.

Certainly a long way from the Karstadt I knew with back in Duesseldorf.