Spotify password compromised

Question

I have just received an email from what seems to be Spotify (signed by spotify.com), where they suggest my password has been leaked.

This brings up two questions:

1. How did they know I used the same password for both services, if the passwords were properly hashed and salted? Does this imply they are improperly storing the password?
2. Is it possible to find out which service was compromised so I can stop using it/change the password for other services which may have used a similar password*?

The relevant part of the email is shown below

Hi Spotify User

To protect your Spotify account, we've reset your password. This is because we believe it may have been compromised during a leak on another service with which you use the same password.

Don't worry! This is purely a preventative security measure. Nobody has accessed your Spotify account, and your data is secure.

*I know the standard procedure for any password leak is to change every password for everything ever... but I'm only human (and a lazy one too)

---

UPDATE

For the sake of completeness, I contacted Spotify and they responded with:

Unfortunately, we can’t provide any further information about the status of your details on other services.

Answer 1

It's simple enough.

They run a batch job that checks every password in the leaked list and yours matched. That verification is done exactly the same way as when you manually sign in.

As you can see, they then reset your password and notify you.

Answer 2

How did they know I used the same password for both services, if the passwords were properly hashed and salted? Does this imply they are improperly storing the password?

No, it does not. All they need to do is getting your password in clear text from the leak, and then hash it once to see if it match the password they have. So it implies that the (unknown) leaked site stored the passwords improperly, not that Spotify does it.

(It is not sure that they know the passwords match - they could simply be resetting the password for everybody whos email shows up in the leak, just in case. After all, a lot of people reuse passwords.)

Is it possible to find out which service was compromised so I can stop using it/change the password for other services which may have used a similar password*?

Try this neat little service: https://haveibeenpwned.com/

I know the standard procedure for any password leak is to change every password for everything ever... but I'm only human (and a lazy one too)

Believe me, you will save work in the long run by chaning the password on all sites where you used the leaked one. While you are at it, start using a password manager that gives you random and unique passwords - if you are lazy you will love it, since the software does most of the work for you.

Answer 3

I got one of these emails from Spotify too. The thing is, my password is a 30+ character randomly generated one that I have never used anywhere else, and which was last changed four months ago. I also use a unique email address for Spotify, one which has never been used for any other site, nor used for any other purpose. haveibeenpwned.com does not show a compromise of that email address, nor my Spotify username (which I use at one other site, where I use an entirely different email address, and, of course, a different randomly generated password). If there is a problem, it seems likely that it is at Spotify.

Answer 4

It was happened to my friends too, but it was related to Spotify non-official "premium" android app which allowed to use Spotify service with premium features without really paying for it.

So I suggest to change your password because without any reason Spotify wouldn't bother you.