Generating Keys

[Chu]

Hello all. Let's say that I have a fancy new program, and want to use the incredibly broken "key" system as a simple piracy detection mechanicism (i.e. enter your key to install the program). I want the keys to be able to be checked offline, so no random keys + "internet activation" here.

It's pretty much gaurenteed that if the program becomes popular, someone will just lift the key checker out of the code to release a keygen. To make their life harder, I want each upgrade I release to recheck the key with stricter rules, which should hopefully catch a lot of generated keys.

Obviously, I'm looking for a seried of functions f1(x)..fn(x) s.t. f1(x) exists in f2(x) exists in f3(x) . . . exits in fn(x). Also fn(x) has to be able to work in a modular space of about 36^32(a reasonable alphanumeric keyspace) with about a .0001% chance of a random key being a code, while f1(x) needs to let me assign at least 1M keys.

Now, how do I go about building this sort of function?

-Chu

P.S., this is purely theoritical. I'm a CS/MA major and was thinking about this problem for a bit, and no obvious solutions were coming to mind.

 

[buleyb]

Well, although I smell homework...


before you go into too much thought about functional keyspace, if you aren't doing any verification over the internet, how does protection against generated keys protect from people sharing one valid key, everywhere?

 

[Chu]

Originally posted by: buleyb
Well, although I smell homework...


before you go into too much thought about functional keyspace, if you aren't doing any verification over the internet, how does protection against generated keys protect from people sharing one valid key, everywhere?

It doesn't ::shrug:: Just from my own experience with, ahem, unlicenced software, most keys that come with pirated releases are flagged as bad during updates as special cases. Doesn't stop casual copies amongst friends, but all those deviance copies would be flagged as bad.

-Chu

 

[martind1]

Doesn't stop casual copies amongst friends, but all those deviance copies would be flagged as bad.

No, How would they be flagged as bad?

if they are all using 1 'legit' key, nto a generated one, then the key will be correct under all parameters you use.

the only way to knwo more than one copy is in use is to have the key verify list it somewhere and when someone tried to activate using it, then it could check against the list.

all the algorithms in the world don't verify keys that are already beign used.


I coudl give you my win98 serial right now and it will work for your install.

 

[Mark R]

My solution to this problem would be to use an installation key which contains within it the details of the key's purchaser. Additionally, with the key is a cryptographic signature which is used to verify the authenticity of the key.

The advantage of this system is that even if your released program is reverse engineered by pirates, all they will get is the public key used to verify the installation key. The private key needed to generate the installation keys is kept locked away on your own PC. This way the only way to pirate the software is to distribute keys that are already in use - as these are personalised with visible personal information there is a strong incentive for legitimate users not to distribute their keys.

The disadvantage is that the size of the key makes manual entry difficult, or impractical for useful levels of security - this means that keys have to be distributed electronically - either on disc or by electronic transfer.

 

[martind1]

still won't work. you can pass around a valid key. you need to verify it on your own server to ensure the key only gets used once. It is the ONLY way.

 

[sao123]

Start with probability functions...

1) Figure out how many keys you need.
1,000,000 valid keys / max .0001 probability of being valid = 10,000,000,000 keys total.
(Assuming all alpha numeric characters...) 36^7 will validate your numbers...so
lets do a 7 char key.... 36^7 will allow 7.8 * 10^10 Keys. makes your random probability of a good key no greater than 1 * 10^-4.


2)Now you have to think in base 36.
F(X) = F(y1) ... F(y2) ... F(yZ) where Z is however long your Key is.
To simplify things...lets group items.

Example in my 5x2 key... a simple function would be like this.
F(X) = F(y0y1) * F(y2y3) * F(y4y5) * F(y6)

Then is becomes a system of linear equations... where A,B,C,D are some randomly chosen constants
F(Y0Y1) = [y0 * y1 ] % ( 10 ) = A
F(Y2Y3) = [y2 * y3 ] % ( 10 ) = B
F(Y4Y5) = [y4 * y5 ] % ( 100 ) = C
F(Y6) = y6 % 5 = D

[(36^2) % 10] * [(36^2) % 10] * [(36^2) % 100] * [36 % 5]
129 * 129 * 12 * 5 = 998460 valid key combinations.

Example:
A=5 B=8 C=69 D=3
Assume 1-9 = 1-9. 0 = 10. A-Z = 11-36. % = mod by function.

QE -
(27*5) = 135 ... 135 % 10 = 5.
3H
(3 * 18) = 48 ... 48 % 10 = 8.
CC
(13 * 13) = 169 ... 169 % 100 = 69.
V
33 % 5 = 3
QE - 3H - CC - V is a valid code. There are exactly 998460 valid key combinations.


----more to follow later.

 

[martind1]

still, none if this works. there needs to be verification that a key has not already been verified. You will not get that part to work unless you send it somewehre to verify it as being original.

 

[DrPizza]

why wouldn't someone just lift the key checker out of future versions that you release? It seems you're suggesting that there's software that will allow keys for old versions to work with newer versions of the software. While this is usually true in going from version 3.0 to 3.1 to 3.2, the keys (in my experience) are worthless once version 4.0 is released.

But, honestly, I think some degree of piracy is unavoidable. And, there's got to be some point where the expense of fighting the piracy exceeds the value to the company. Of course, you can't just allow anyone and everyone to pirate your software, but at the same time, you can't make use of the software so restrictive that you'll alienate your customers. (remember last year's tax software that wouldn't allow you to reformat your hard drive and reinstall the software? A lot of people were annoyed by that, even before the company cleared up the issue).

Personally, I think the best thing to do would be have software verify the key in the software from time to time on the internet. To get users to not mind such an obtrusive measure, market the newest release with that feature for less money than the previous releases and claim it's cheaper because it fights piracy better. Then, if two people are trying to use the same key, the software is disabled.

 

[buleyb]

And remember, many products have succeeded because of piracy, only to later implement online verification schemes and lure cash from hooked customers...

 

[martind1]

Originally posted by: buleyb
And remember, many products have succeeded because of piracy, only to later implement online verification schemes and lure cash from hooked customers...

What's up counter-strike.

 

[Chu]

I really didn't want this thread to turn into a discussion on the best way to stop piracy, lord knows this isn't it. Also as for if a certain amount of piracy is desirable, well that really doesn't belong in this forum either.

-Chu

P.S., I found what seems to be a good solution. Take some message, and then encrypt it using El-Gammal or some other encryption scheme where one message maps to more then one encoded message. Then after each version, eliminate some of the valid encoded messages by getting stricter and stricter about which "random" seeds you used to cypher with.

 

[sao123]

my example key used 7 alpha numeric (A-N) characters.

using more complex linear equations and using a standard 5x5 microsoft key code will either increase the number of valid codes or decrease the probability of finding a code using a brute force generator.

for example keeping 1M codes, a 5x5 25 A-N code will decrease the probability of finding a ranom code to like 10 ^ -18 with 1M valid codes.

 

[Cogman]

I would essencially create my own numeric system, it should not go 12345, insteads something random like 35241 while keeping each value the same, like 3 = 1, 5 = 2, 2 = 3, ext... this also allows the incorperation of letters so it could be 3A54V1. After giving each letter a number, I would take say, six digets per box, then Just do some random math functions. say box1 has the letters 843FE2 and those numbers added up are equivlent to 60, well box2 has say 293AB4, for those numbers to be acreate lets say you have to multiply the first for and add the last 2 and it must = 60, or 1/3 of sixty if you want to make this more complicated. But the point still stands, to make this good you are going to have to chew up the string and check for each individual charactors value. (which really isnt to bad, but could get lengthy if you make a long alpha-numerical alphabet)

 

[AbsolutDealage]

Originally posted by: Cogman
I would essencially create my own numeric system, it should not go 12345, insteads something random like 35241 while keeping each value the same, like 3 = 1, 5 = 2, 2 = 3, ext... this also allows the incorperation of letters so it could be 3A54V1. After giving each letter a number, I would take say, six digets per box, then Just do some random math functions. say box1 has the letters 843FE2 and those numbers added up are equivlent to 60, well box2 has say 293AB4, for those numbers to be acreate lets say you have to multiply the first for and add the last 2 and it must = 60, or 1/3 of sixty if you want to make this more complicated. But the point still stands, to make this good you are going to have to chew up the string and check for each individual charactors value. (which really isnt to bad, but could get lengthy if you make a long alpha-numerical alphabet)

This is not a secure encryption method, and could very easily be broken down by a simple cryptographic attack.

 

[martind1]

ya, with mathmatics, this would be broken quite easily. with or without windtalkers.

 

[Chu]

Most of the posted solutions are missing the point Giving a function that fits a certain probability distribution is easy, the hard part is giving a series of functions so the keyspace keeps shrinking. Actuially now that I've been thinking about it that's pretty easy too. What is hard is giving a series of functions so the keyspace keps shrinking AND the keys have a random distribution.

 

[ZeroNine8]

You talk about further restricting the key checker with future releases, my question is why wouldn't you go ahead and release it initially with the most strict key checker in place. It's not like you will be losing valid keys since you plan on this in the future, so I can't se any reason to release a 'weak' check now followed by more restrictive ones later. Besides, with nothing like internet verification of keys, you're just gonna have pirated copies passed around with the valid keys supplied with the software, which you cannot control with anything like you plan on using.

 

[sao123]

s.t. f1(x) exists in f2(x) exists in f3(x) . . . exits in fn(x). Also fn(x) has to be able to work in a modular space of about 36^32(a reasonable alphanumeric keyspace) with about a .0001% chance of a random key being a code, while f1(x) needs to let me assign at least 1M keys.

Unfortunately, mathematically I dont believe what you want is possible.

The key space is defined as 36^(num of characters)
In a series of functions F1(x) F2(x) F3(x) ... if every valid key in f1(x) exists in f2(x) exists in f3(x) . . . exits in fn(x) then the functional series is increasing not decreasing... blah blah blah. The only way to decrease a functional series is to start with a max number of terms and remove them 1 at a time.

What is hard is giving a series of functions so the keyspace keps shrinking AND the keys have a random distribution

So what you want is to create a set of legal keys (fit the functional series) and then use a random subset of that as official keys (actually enabled as working). Then change some parameters in the function so that the legal keys becomes closer in size to the official keys every time a new series function is generated. Well thats stupid, in a perfect scenerio, there would be no more valid keys than official keys. Meaning there exists no way to generate unofficial keys.

why wouldn't you go ahead and release it initially with the most strict key checker in place.

EXACTLY.

 

[DrPizza]

Without encrypting this idea, simply do the following.

Keys can be any number between 1 and 1 million.
On the first release, all even numbers work.
On the second release, only numbers divisible by 4 work.
On the 3rd release, only the numbers divisible by 8 work. (or you could be more restrictive and they'd have to be divisible by 12 or 20 or some other multiple of 4.)

etc.

Is this all you're asking for?

(Of course, scale it up higher than divisible by 2. Since you desire a .0001% chance of a random key being a code, your initial divisor would be at least 36^32/1000000. But, that would allow wayyyyyyy more than a million valid keys. Thus, you could pick a number a few orders of magnitude higher than that to thwart brute force attacks)

 

[Mday]

keys can be generated based on serial numbers found on machines. the ones that are most common are processor or HDD. small programs are even compiled with the information within the executable prior to download (purchased).

 

[Cogman]

Just real quick, how would my method be broken easily? Though I relize It may not be the most effective for sending secret messages, if they dont know what value each number is, what the value is supposed to add, subtract, or taken to the 42 power and equal to, how can they find the exact number?

 

[buleyb]

Originally posted by: Cogman
Just real quick, how would my method be broken easily? Though I relize It may not be the most effective for sending secret messages, if they dont know what value each number is, what the value is supposed to add, subtract, or taken to the 42 power and equal to, how can they find the exact number?

Lets look at it this way, because I don't have the time for a long response now, maybe when I get to work.

You're entire scheme isn't based off picking a good key, but picking a key and using it in a system you believe the attacker to not be privy to. You cannot make this a requirement. You have to assume that the attacker knows everything about this algorithm except the key you choose, otherwise you are just fooling yourself. And a quick glance at your idea says a given key with the algorithm known makes brute force a great possibility.