Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list] 
Message-ID: <20110518232930.GA5976@openwall.com>
Date: Thu, 19 May 2011 03:29:30 +0400
From: Solar Designer <solar@...nwall.com>
To: john-users@...ts.openwall.com
Subject: Re: Help with 14 - 16 digit CC's stored in MD5 hash

On Wed, May 18, 2011 at 02:44:07PM -0400, brad@...ystems.com wrote:
> I do not believe that IINs are public data.

They appear to be semi-public.  Here's a database for sale, for $500:

http://www.binbase.com/search.html

(with limited online lookups as a demo).

Also, this Wikipedia page has some IIN ranges:

http://en.wikipedia.org/wiki/Bank_card_number

A few of them include the first 6 digits.

Here's an external mode filter() that will add the Luhn algorithm digit
to arbitrary all-digit strings.  It's optimized for speed, not for size
nor simplicity, yet is still not as fast as I would have liked it to be.

It may be faster to generate the all-digit strings with an external mode
on its own, adjusting the Luhn digit as necessary.

[List.External:Append_Luhn_Digit]
int map1[0x100], map2[0x1fff];

void init()
{
	int i;

	map1[0] = ~0x7fffffff;
	i = 1;
	while (i < 0x100)
		map1[i++] = 0x01000000;
	i = -1;
	while (++i < 10)
		map1['0' + i] = i + ((i * 2 % 10 + i / 5) << 12);
	i = -1;
	while (++i < 0x1fff) {
		if (i % 10)
			map2[i] = '9' + 1 - i % 10;
		else
			map2[i] = '0';
	}
}

void filter()
{
	int i, o, e;

	i = o = e = 0;
	while ((o += map1[word[i++]]) >= 0) {
		if ((e += map1[word[i++]]) >= 0)
			continue;
		if (((o | e) & 0x7fffffff) >= 0x01000000)
			return; // Not all-digit, leave unmodified
		word[i--] = 0;
		word[i] = map2[(e & 0xfff) + (o >> 12)];
		return;
	}
	if (((o | e) & 0x7fffffff) >= 0x01000000)
		return; // Not all-digit, leave unmodified
	word[i--] = 0;
	word[i] = map2[(o & 0xfff) + (e >> 12)];
}

Here's a slightly simpler but slower revision of the filter() function:

void filter()
{
	int i, sum[2];

	i = sum[0] = sum[1] = 0;
	while ((sum[i & 1] += map1[word[i]]) > 0)
		i++;
	sum[i & 1] &= 0x7fffffff;
	if ((sum[0] | sum[1]) >= 0x01000000)
		return; // Not all-digit, leave unmodified
	word[i] = map2[(sum[i & 1] & 0xfff) + (sum[~i & 1] >> 12)];
	word[++i] = 0;
}

These use the same trick: compute the length and four sums in parallel
(in two SIMD'ish variables or array elements).  Then whether the length
is even or odd determines which two of the four sums are actually used.
Checks for non-digits and for NUL are packed into the SIMD'ish values as
well.  So it's 1 bit for NUL, 7 bits for counting non-digits, 12 bits
for one partial sum, 12 bits for the other.

Alexander

Powered by blists - more mailing lists

Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.