License key pattern detection?

Question

This is not a real situation; please ignore legal issues that you might think apply, because they don't.

Let's say I have a set of 200 known valid license keys for a hypothetical piece of software's licensing algorithm, and a license key consists of 5 sets of 5 alphanumeric case-insensitive (all uppercase) characters. Example: HXDY6-R3DD7-Y8FRT-UNPVT-JSKON

Is it possible (or likely) to extrapolate other possible keys for the system?

What if the set was known to be consecutive; how do the methods change for this situation, and what kind of advantage does this give?

I have heard of "keygens" before, but I believe they are probably made by decompiling the licensing software rather than examining known valid keys. In this case, I am only given the set of keys and I must determine the algorithm. I'm also told it is an industry standard algorithm, so it's probably not something basic, though the chance is always there I suppose.

If you think this doesn't belong in Stack Overflow, please at least suggest an alternate place for me to look or ask the question. I honestly don't know where to begin with a problem like this. I don't even know the terminology for this kind of problem.

Answer 1

Assuming that the system is cryptographically strong knowing those keys will do you no good. Now, many such systems are implemented by guys too cheap to buy a real keygen so you might still have a hope.

Just a little back of the envelop estimation says that such a key has 125 (was 800 oops, thanks for catching that) bits of information, if you sampled that space enough you might be able to make some sort of an attack, but you are talking about a huge number of sample points. But hey, what other plans did you have for your spare time?

Even the big guys mess this up, a half dozen years ago there was a mistake in the way MSDN keys were being generated that allowed some sort of brute force attack. You would find guys selling MSDN subscriptions on eBay as part of a corporate licensing bundle. You would submit your info and they would give you a preregistered MSDN account in a couple of days. I am pretty sure they were taking advantage of a bug in the implementation and brute forcing the enrollment until one stuck.

A company I worked for bought one, Microsoft honored it since we were none the wiser when we bought it, but they were interested in the address of the guy who sold it to us.

Answer 2

This is notoriously hard to solve in the general case. However, if

I'm also told it is an industry standard algorithm

if this is the case, you should obtain a list of those "standard algorithms", and analyze them for weaknesses.

My naïve guess is that most key generation is of the form x || hash(x || fixed), where x is a randomly generated value for each key, and fixed is a fixed value. Using this form, keys can be validated quite easily (extract x, calculate hash(x || fixed), see if it matches).

Assuming you knew the exact algorithm used, you'd either have to find a weakness in the algorithm (not likely, unless they are using a hash with known vulnerabilities), brute-force the fixed value, etc.

Given that there are lots of hashes which do not have known vulnerabilities and if you assume that the guys who chose the fixed value where not dumb... this might be a tough cookie unless you have good cryptanalysis skills available.

So the problem is very hard to solve if the guys who designed the algorithm are not dumb. But they might be...