I stumbled across an interesting link that made me think about a solid serial number system based on strong cryptography. Cryptography discourages systems based on secret algorithms, and relies on open algorithms and secret keys. So let us develop a serial number generation/verification system with the same usability as the one in the linked article but without any secret algorithms.
First, our serial numbers should have the form
XXXX-XXXX-XXXX-XXXX-XXXX
where X – an uppercase english letter A..Z; to prevent user’s confusion let us exclude the letter O which looks like zero, so in the end we have 25 possible letters in 20 positions, that is BigInteger.Pow(25, 20) = $1D6329F1C35CA4BFABB9F561 combinations. Next, we want to work with full bytes; this reduces the possible serial keys to 11 byte-long numbers; also we want to use 2 bytes of serial key as a key checksum; this leaves us with 9 bytes, and we have 9*8 = 72-bit serial keys. That should be strong enough against full keyspace search attack on our system.
Suppose you are a micro-ISV and expecting to sell up to 100 copies of you software; then you need to generate 100 72-bit keys and embed their hashes into the executable (if it will turn out later that you need more copies it is not a problem – just recompile your executable with more keys next time; the same way you can revoke leaked keys – by not including them in the next release).
To derive 72-bit keys I use 128-bit master key and AES encryption algorithm as a pseudorandom function. Note that the 128-bit master key is actually the only secret in the system, everything else is calculated. It is worthwhile to generate the master key, for example, by tossing a coin 128 times.
For hashing I use SHA256 hash function. I also use CRC16 algorithm to calculate the key checksums.
The verification is 2-phase process. First, it converts a serial number in 20-letter format entered by user into a 11-byte serial key, calculates the checksum of the first 9 bytes and compares it with the last 2 bytes (this prevents user from mistyping his serial number). Second, it hashes the 9-byte key and checks that the hash exists in the keyhash table.
And now the challenge. The last TForge release (0.74) includes full source code of console application with the serial number system described above, in the Demos\Challenge subfolder. The key generation code is also included, though it is not used in the application and could be kept secret; the only thing I keep secret is 128-bit master key used.
Build the application with Delphi or Lazarus/Free Pascal.
One of the valid serial numbers is:
AVVH-GJCX-YVWM-EHUE-YMRL
Try to find other valid serial number(s).
The Programming Works 
Attacks on Serial Numbers rarely go after the actual recovery of the private key. The most common attack on a serial number system is to simply disassemble the code that checks for a valid key and skip it.
Then you try to obscure that code, and the attacker uses a reverse debugger. If you move the check from the client to the server, then the attacker moves from attacking the code that checks the serial number to the code that validates the response from the server.
At some point you will reach a point of diminishing returns. When this point is reached, you will annoy your paying customers more than they are willing to be annoyed. So while the strength of AES-128 may comfort some people, it is beside the actual point when used to secure, say, software serial numbers.
The weakness in any such system is seldom the cryptography itself. Side channel attacks may exist in some specific implementations, but whenever we apply a strong algorithm like AES-128, and our implementation is in x86 assembler instructions, it’s not too hard to find and defeat that code.
Warren
Instead going to such a length to build a good serial number generation system. Can’t we just use GUID and shuffel them to get a unique serial number?
GUIDs are just unique; strong keys or serial numbers should be indistinguishable from uniformly chosen from the key space. I don’t know GUID generation algorithm, but if you want to derive keys from GUIDs I would recommend to do it by applying HMAC algorithm to GUIDs, or just use standard PBKDF2 key derivation algorithm, that is for example THMAC.MD5.DeriveKey(..) method in TForge; there is no need to “slow down” hashing by using many rounds with GUIDs, the purpose of using HMAC here is to get more uniformly distributed keys.
Do not bother with hashing or private keys, just use pure cryptographic random. Client side checks are the usual target anyway, and on the server side, pure random will just beat anything else, the only cost is disk space, but even with 128 bits per key, it’s going to be minimal anyway unless you sell billions of licenses (but then you can afford an extra datacenter or two, hehe)
Guid are not strongly random, do not attempt to randomize them through hashing or key derivation, you just risk missing something… Just use cryptographic random, it’s designed for that 🙂
PS: by “cryptographic random”, I mean the OS-provided cryptographic random generators (CryptGenRandom in Windows, /dev/random in Linux).
But in your scheme, a hacker would not bother with defeating your algorithm:
– a working key can be disseminated if the hacker just stole it or does not care
– the hash check can be bypassed through patching the test, so that any key works, or the hash table patched to accept a key like “LOLZ-LOLZ-LOLZ-CRCC”
The client-side check does not really need to go beyond CRC, since it’s easily defeated anyway. The actual checks need to be server-side, and then you need some actual server-side services so that the app can not just be wrapped in a ThinApp or similar container (with embedded fake server)
Warren is right. One of my products is HexLicense (hexlicense.wordpress.com) serial components for Delphi, and I can tell you right now that serial management is a bit more intricate than just dealing with serial number generation. I dont write that in a negative way, but your approach to serial number generation is one of the first thoughts that people have when dealing with this subject. They think “hey, maybe i can use SSL/Certificate signing to do the grunt work for me?”, if only that was the case 🙂
The rules i setup for my product was:
1. All serial numbers should be unique
2. All serial blocks should be non-linear
3. All serial numbers should mathematically verifiable back to a root-key
4. Serial numbers should avoid classical serial formulas (*1, *2)
5. Each serial segement (number block) should be unique to its collection
*1: Egyptian “double-up” lookup tables etc. of the 80’s and 90’s,
*2: PI / irrational number based generators for “sum and match” type schemes). Works, but easy to hack and takes forever to generate 1000 valid serial numbers.
As you can imagine this was quite a challenge. I am no more experienced than others when it comes to maths so i had to read up on a few topics first. But my strength is in problem solving and finding unusual solutions to unusual problems. In this case though, i had to create an unusual problem – but deliver it as a easy to use solution (if that makes sense). So i ended up with a hybrid engine, partly mathematical, partly mechanical and partly just clever organization based on experience. I was after all a hacker for 10+ years on the Amiga and Atari back in the 90’s, so i know a few tools of the trade so to speak.
The non-linear aspect was the hardest; where you should never be able to produce the next valid serial number by just incresing parts of the serial. you wont believe how many serial numbers can just be inc’ed and you get the next valid license 🙂
Also, each serial section (block of numbers and letters) should always be unique to its collection. Why? This makes it harder for brute-force scripts that attack a generator by first collecting similarities, then analysing the dissimilar aspects and create a “hack” formula from that (essentially resulting in a “keygen”). Which is what Warren is talking about. They dont go after the root-key, but rather analyzes the X valid serials to find a numeric “pattern” they can mimic.
The only way to break that, is by non-linear serial numbers — which are all dissimilar in all aspects.
If they cant do this, they try to locate the ASM code which validates in order to disable that.
Having worked with the problem, it quickly became clear to me that the human factor is the only way to maintain healthy protection and sales. So i urge customers to never ever put all their eggs in one basket. Never generate all your serial numbers from the same root key (or a single crack will devestate your entire production line). Always generate a new root-key per 100 serials (or 1000 depending on your sales and volume). You may also want to generate a unique root key for vendors, discount codes and so on. Just to make it harder for hackers and warez sites to dominate your products.
It must be understood that “the time hackers spend bypassing your licenses” is your window of revenue. The more time-gaps you can create, the more potential to earn on your investment before another hack is released. So in this particular case — time really is money in the true sense of the phrase.
All in all i’m happy with my product. I have found no key-generators able to match it, although that will happen sooner or later (hence frequent updates to the scheme) -and of all my customers i have only one reported “crack”. Ironically, they were unable to create a keygen for it, but instead had to spend a few days disassembling the entire application, isolate a single component in a huge delphi application, then spend time figuring out how to disable all callbacks, threads and so on. They must have spent at least 3-5 days doing that, which is a success in software terms.
Also, there is a difference between serial number generation, management and software protection. When generating serial numbers, like the code you hint to (and also the idea of using SSL for the grunt work), there are many aspects you have to take into account:
1. Being able to calculate a serial number back to its root key for validation
2. Being able to easily map a serial to a product line
3. Match minimum requirements of online software vendors (payEx being the most irritating of them all)
Also, regarding SSL and certificates: The idea is good to begin with, but as you probably know, this has been cracked ages ago. The only reason SSL “works”, is because when you use it online the encryption is rotated and applied cyclical to the date. In other words, the encryption changes for each block of data, hence cracking a single block becomes futile – because by the time you have that, the encryption for the next block is already obsolete and long gone.
But data which “stands still” is a whole different ballgame, and here hackers have special SSL and certificate crack programs which will decode your stuff faster than you can say cheese.
So my advice is to only use SSL/Cerificate encryption/signing as a basis for a more elaborate scheme. And ofcourse, never ever share the technical information with anyone.
Or, buy a pre-made solution from someone 🙂