I cannot comment on how Stripe does this but I can tell you exactly how [Braintree][1] does it (because that is where I work). If I had to guess, Stripe probably uses a similar method.

In the Braintree API, we offer a [unique number identifier for a credit card][2]. This identifier is a random opaque token that will always be the same for card number stored in our system. The seed for this number is different per merchant in our system so you cannot compare them across merchants.

When a new card comes in, we look it up by comparing it to a hashed + salted column. If it matches that existing column we know we can return the same unique number identifier. If it doesn't match any existing record, we use a cryptographically secure pseudo-random number generator to create a new unique number identifier and ensure it doesn't conflict with an existing one.

This way the hashed + salted value never leaves our backend but we can still provide a way for a merchant to uniquely identify stored credit cards.


  [1]: https://www.braintreepayments.com/
  [2]: https://developers.braintreepayments.com/javascript+ruby/reference/objects/credit-card