The really messed up part is that the app has basically every permission turned on AND ships with some on-contract phones. So although I had never once opened the app, it was running in the background on an old POS HTC I had. Pretty sure that's where they got every contact ever.
