Brute Forcing Credit Card Numbers

PCI Regulations allow merchants to store the first 6 digits plus the last 4 digits of a customer's credit card number. Ever wonder just how secure that is?

Well, without knowing anything else, if a credit card is stored as 1234-56xx-xxxx-1234, the possible missing middle digits range from 00-0000 to 99-9999, roughly one million (1,000,000) possible combinations. That seems very tough to guess (without being detected).

However, credit card numbers all implement Luhn's Algorithm, which is a special mathematical formula that uses the last digit in the number as a check digit. Not all of the 1,000,000 middle combinations will pass Luhn's check. Turns out (since modulus 10 math is involved), the quantity of missing middle number combinations is at most 100,000 possibilities, not a million. Luhn's reduces the complexity by an order of magnitude.

So, what if an attacker can get just one more digit somehow? Well, it's only 10^4 combinations then: 10,000 possibilities. What if they can get two more digits? The math follows this formula: 10 ^ (n-1). Here's the table:

6 digits	10 ^5 = 100,000
5 digits	10^4 = 10,000
4 digits	10^3 = 1,000
3 digits	10^2 = 100
2 digits	10^1 = 10
1 digit*	10^0 = 1

* It makes sense, if you're missing a single digit, Luhn's will help you recover it. That is the purpose of that algorithm originally.

Now, as far as practical applications for abusing the knowledge of Luhn's Algorithm on a PCI acceptably-formatted credit card number are concerned ... 100,000 attempted transactions to brute force a card number by a single merchant will certainly be detected and the merchant's ability to process any transaction will be in jeopardy. So, an attacker with access to a merchant account is probably not a valid threat to model.

For an attacker to attempt to make purchases at varying merchants with this brute force scheme and everything but the middle 6 digits, the attacker will also have to have the billing address and potentially the CVV code. That makes the problem significantly harder. But as the attacker can discover missing digits from the middle six, the problem becomes easier. If the victim is well chosen, and the attacker can do something like shoulder surf at a point of sale machine to visually see and remember a digit or two or three, then the problem gets noticeably easier. If the attacker can do that, the attacker can probably also guess the billing address and name. There's still that pesky CVV code, though (that's another 3 digits which compounds things).

Realistically, though, for an attacker to get that much information on a victim, the victim would probably have to be oblivious or have an extremely large line of credit to make it worthwhile.

For the rest of us, we're fairly safe with the PCI rules of first 6 plus last 4 digits being public knowledge.

Check this out for yourself. Here's the source code for a very simple C# console application that will take whatever first 6 plus last 4 digits you provide it, and churn out all of the possible middle combinations. Here is the inspiration for the C# Luhn's implementation. [Sorry about the code formatting.]

using System;
using System.Linq;

namespace Luhn
{
public class Luhn
{
private static int _middle = -1;
private static int _counter;
private static int _places;

public static void Main(string[] args)
{
if (!args.Any())
{
PrintUsage();
return;
}

var cc = args[0].Replace("-", "").Replace(" ", "").Replace("x", "X");

if (cc.Length != 16)
{
Console.WriteLine("input is not correct length.");
PrintUsage();
return;
}

_places = cc.Length - cc.Replace("X", "").Length;
var limit = Math.Pow(10, _places);

Console.WriteLine("Places: {0}", _places);
Console.WriteLine("Limit: {0}", limit);

while (_middle < limit)
{
var s = FindNext(cc);
if (!PassesLuhnCheck(s)) continue;
Console.WriteLine("Valid: {0}", s);
_counter++;
}

Console.WriteLine("\r\nFound {0} potential matches for {1}", _counter, args[0]);
}

private static void PrintUsage()
{
Console.Write("Usage: luhn.exe [credit card number]\r\n"
+ " in format like 1234-56xx-xxxx-1234\r\n"
+ " or like 1234-5678-xxxx-1234, etc.\r\n\r\n");
}

private static string FindNext(string number)
{
_middle++;
var middle = _middle.ToString();
while (middle.Length < _places)
{
middle = "0" + middle;
}
return (number.Replace(GetPlaceHolder(), middle));
}

private static string GetPlaceHolder()
{
var s = "";
for (var i = 0; i < _places; i++)
{
s += "X";
}
return s;
}

private static bool PassesLuhnCheck(string number)
{
var deltas = new[] { 0, 1, 2, 3, 4, -4, -3, -2, -1, 0 };
var checksum = 0;
var chars = number.ToCharArray();
for (var i = chars.Length - 1; i > -1; i--)
{
var j = chars[i] - 48;
checksum += j;
if (((i - chars.Length) % 2) == 0)
checksum += deltas[j];
}

return ((checksum % 10) == 0);
}
}
}