Spotify says my password is compromised on another service

[trailer]

I got an e-mail from spotify saying "Please update your Spotify password". In the body of the e-mail it says "To protect you 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."

The links in the e-mail all go to either spotify.com or wl.spotify.com. Could it be phising?

I have visited spotify.com and changed my password through the web-site. But I have a couple of issues with this e-mail:

1. All my passwords are unique. There is no way my spotify password matches any of my other passwords.

2. Even if my password was not unique, Spotify should only have a salted hash of the password. There is no way that same hash exists together with my e-mail anywhere else.

3. They are saying that my password is compromised during a leak on another service. How would Spotify know this? They don't know my password, they don't know where I have accounts...

What does this all mean? Has Spotify lost my password, and they are blaming it on "another service"?

[Maria_B]

Hi @trailer!

Welcome to the Spotify Community, we're glad to see you're part of the band.

Don't worry, our Accounts team can take a closer look at this. You can get in touch with them from any of our social media help sites: @SpotifyCares on Twitter and Spotify Cares on Facebook. Just send them a private message with your account's email address and username.

You can also use our Contact Form to get email support.

Don't hesitate to drop us a message if you need us again.

All the best.