Short answer: Yes, all passwords.
Long answer: At first sight, you only need to change the secret key of the certificate. But due to several reasons, all passwords are affected. Here's why:
Reason 1: Chained attack
- Someone captured the secret key of the certificate. From that time on, he could decrypt all the traffic to that site.
- If you logged on for whatever service on that website, your password was revealed. Probably the most common service is Webmail, so let's use that as an example.
- Reading your emails, the attacker found out which other services you are using.
- Using the password reset mechanism, the attacker simply reset all the passwords, confirmed the reset emails and deleted those emails of course.
- The attacker now has access to all your services.
- The website owner (whose secret key was stolen) became aware of the security leak and fixes it. The service (we assumed Webmail) is no longer vulnerable.
- The website owner informs you about the leak and asks you to change your password.
- The attacker can still use all the other services as long as you don't notice that you cannot login anymore (because he changed the password). This means: For services which you use often, it's more likely to detect that it was misused. For services you don't use often, you'll not notice.
Therefore you at least have to check each single password, whether it is affected or not.
Good thing on this attack vector: You'll be aware of the issue.
Reason 2: Access to database
- Someone captured the secret key of the certificate. From that time on he could decrypt all the traffic to that site.
- If the admin of the website logged on to do some administration, moderation or whatever, the attacker now has the password of the admin.
- With that password, the attacker gets access to the database.
- Depending on the security of the database, the attacker can read
- the usernames
- the passwords in plaintext (worst case)
- vulnerable password hashes (e.g. MD5 hash, unsalted) (bad case)
- secure salted hashes (best case)
- The attacker calculates the password from the hash
- The website owner fixes the problem
- You are informed by the website owner to change the password.
Since you as the user cannot know how securely the password was stored in the database, you need to consider that the attacker has the password (and username). This is a problem, if you reused the password for other services.
Bad thing: You don't know whether you are affected, because logging in to other services still works (for you and for the attacker).
Only solution: Change all passwords.
Reason 3: not only secrets certificate keys are leaked
I looked at some of the data dumps
from vulnerable sites,
and it was ... bad.
I saw emails, passwords, password hints.
As posted by XKCD #1353:
So the attacker could already have your password in plain text even without access to the database and without chained attack.
The second problem, described by @Iszy, still remains: Wait to change your password until the service has fixed the Heartbleed issue. This is a critical hen-and-egg issue, because you can only reliably change all the passwords, when all services you use are updated.