Generating registration codes

Question

I'm looking for a best practices and security analysis of some code I've written to generate registration codes and avoid duplicates.

The class assigns numeric values to the letters A-Z and 0-9 and then uses that mapping to generate 16 character codes that must conform to the following parameters:

• Codes must sum to 256 characters
• must not contain duplicate, repeating, or sequential characters
• must not be a previous generated code.

public class RegistrationCodeManager
{
    private Dictionary<char, int> characterValues;
    private HashSet<string> generatedCodes; 

    public RegistrationCodeManager()
    {
        characterValues = new Dictionary<char, int>();
        AssignCharacterValues();
        generatedCodes = LoadGeneratedCodes();
    }

    public string GenerateCode()
    {
        Random random = new Random();
        string code = "";

        while (code == "" || !ValidateCode(code) || generatedCodes.Contains(code))
        {
            List<char> characters = new List<char>(characterValues.Keys);
            characters.Shuffle(random);

            code = "";
            int sum = 0;

            for (int i = 0; i < 16; i++)
            {
                char c = characters[i];
                int value = characterValues[c];
                code += c;
                sum += value;
            }

            if (sum != 256 || generatedCodes.Contains(code))
                code = "";
        }

        generatedCodes.Add(code);
        SaveGeneratedCodes();

        return code;
    }

    public bool ValidateCode(string code)
    {
        if (code.Length != 16)
            return false;

        if (code.Distinct().Count() != 16)
            return false;

        for (int i = 0; i < code.Length - 1; i++)
        {
            if (Math.Abs(characterValues[code[i]] - characterValues[code[i + 1]]) == 1)
                return false;
        }

        return true;
    }

    private void AssignCharacterValues()
    {
        // Assign numerical values to A-Z and 0-9
        int value = 1;
        for (char c = 'A'; c <= 'Z'; c++)
        {
            characterValues[c] = value;
            value++;
        }

        for (char c = '0'; c <= '9'; c++)
        {
            characterValues[c] = value;
            value++;
        }
    }

    private HashSet<string> LoadGeneratedCodes()
    {
        HashSet<string> codes = new HashSet<string>();

        try
        {
            if (File.Exists("generated_codes.txt"))
            {
                string[] lines = File.ReadAllLines("generated_codes.txt");
                codes = new HashSet<string>(lines.Distinct());
            }
        }
        catch (Exception e)
        {
            MessageBox.Show("Error loading generated codes: " + e.Message);
        }

        return codes;
    }

    private void SaveGeneratedCodes()
    {
        try
        {
            File.WriteAllLines("generated_codes.txt", generatedCodes);
        }
        catch (Exception e)
        {
            MessageBox.Show("Error saving generated codes: " + e.Message);
        }
    }
}
public static class Extensions
{
    public static void Shuffle<T>(this IList<T> list, Random random)
    {
        int n = list.Count;
        while (n > 1)
        {
            n--;
            int k = random.Next(n + 1);
            T value = list[k];
            list[k] = list[n];
            list[n] = value;
        }
    }
}

Any advice on best practices or security enhancements is most welcome.

Answer 1

a quality product starts with the requirements

must conform to the following parameters ...

I know this is a Code review site, not Requirements review. But I'm just gonna come out and say it. That second requirement, "must not contain duplicate, repeating, or sequential characters", is either silly or not well motivated. That is, nowhere in the submission do we see "recite over telephone", "human factors", or other business-level goals enunciated, justifying the constraints. Also, how did the "repeating" aspect sneak into the spec? Given that it is redundant with "duplicate". Constraining the allowed codes means we get less entropy in those 16 15 random characters. Writing down the various rationales would let us reconsider them two years down the road when revving the product. Ok, end of rant. It is what it is. We will code to that.

(And you didn't mean "codes must sum to 256 characters". Rather you intended to describe sum of corresponding values.)

I imagine we're sending ~ 5 bits per printable character, rather than 6, so helpdesk can recite "zero oscar one lima ..." to new users. Admitting upper + lower letters would send roughly one more bit per character.

---

show dataflow with an assignment

    public RegistrationCodeManager()
    {
        characterValues = new Dictionary<char, int>();
        AssignCharacterValues();

Uggh! The ctor assigns, and then evaluates for side effects.

Now, AssignCharacterValues is a lovely identifier, very descriptive, I thank you for that. But there's no need for that. Much nicer to GetCharacterValues, or GenerateCharacterValues:

    public RegistrationCodeManager()
    {
        characterValues = GenerateCharacterValues();

This makes the initialization more obvious, to even the casual reader.

---

external storage

        generatedCodes = LoadGeneratedCodes();

Wow, that looks expensive, a big malloc! (Assuming you'll have lots of customers, which hopefully this code is geared towards.)

We expect to make slightly more than one probe of the hash map per generated code. Now, I don't know how big a batch of codes you will generate per run, the OP didn't spell that out. But if it is "small", consider turning the "load everything!" routine into a "check for this specific code" predicate, to save on RAM.

Consider turning the generated_codes.txt file into an RDBMS table, perhaps using sqlite. Or copy its lines into a table. Then you can make repeated, efficient probes using a unique index.

On which topic, that lines.Distinct() expression really makes me nervous. The source-of-truth for those business records is potentially corrupted by duplicate records? Which we silently ignore? Recommend you tidy that up, so you can assert that all lines are unique.

---

when in doubt, sort

    private void SaveGeneratedCodes()    
            ...
            File.WriteAllLines("generated_codes.txt", generatedCodes);

Serializing in arbitrary hash order seems inconvenient. Suppose you're reviewing yesterday's daily backup, and you notice today's file has a slightly longer length. It would be natural to ask "what changed?", perhaps as part of the "I have an angry customer on line 3" issue you're researching.

Or perhaps you occasionally store a snapshot of the file in git. For example, to support unit tests.

To make diff more useful, it would be nice to sort those codes before serializing them.

---

don't swallow exceptions

        catch (Exception e)
        {
            MessageBox.Show("Error loading generated codes: " + e.Message);
        }
        return codes;
        ...
        }
        catch (Exception e)
        {
            MessageBox.Show("Error saving generated codes: " + e.Message);
        }

I don't understand why it comes within the single responsibility of either of these routines to offer a friendly diagnostic UX. Wouldn't it be better to just let them throw, let the error bubble up the call stack?

The contract was to return a well-formed set of valid codes, or to have the side effect of persisting codes. For the caller to blithely continue on as if the contract had been fulfilled is to make the caller violate his contract. I note that no calling code checks for missing codes. Or put another way, it looks like an empty codes file is valid, and that's indistinguishable from a disk drive that's on fire.

---

    public string GenerateCode()
    {
        Random random = new Random();         

Wow, that's a lot of re-seeding going on. That's not how we use a PRNG. Seed it once, perhaps from high-quality entropy, and then keep using it for the rest of the run.

As coded, it only increases the risk of replaying old PRNG values.

        while (code == "" || !ValidateCode(code) || generatedCodes.Contains(code))

I don't get the first disjunct.

I mean, the empty string is not of length 16, so it's not a valid code. The validate predicate will reject it at once. Why special case it here?

checksum

I can imagine many UX and automated scenarios where it's desirable to notice a typo in an ISBN number, credit card number, or registration code, before starting some expensive process. Supporting a checksum makes sense to me.

            if (sum != 256 || ... )

This is very nice rejection sampling. Alas, it is rather expensive.

We want an average character value of 16. We roll a pretty fair 36-sided dice, so expected value of each roll would be 19. Therefore, valid codes will have more "A"'s than "Z"'s, will be light on digits, and there's actually less than a 1-in-256 chance of accepting a code as valid. The whole approach seems on the crazy side. Here are some alternatives, in descending order of desirability.

1. compute a checksum

Roll 15 random characters. Then just deterministically compute what the final one must be. Require that the sum of values shall be congruent to zero modulo 36. This is a change to the requirements.

2. use a real hash

A simple sum (addition, XOR, ...) seems like trouble, it won't catch transpositions injected by human typists. There are perfectly good hash functions that are resistant to such effects; just use one. And again, deterministically compute the final character so that hash mod 36 is zero. This is a change to the requirements.

3. use a crypto hash

Roll a 15-character string, and compute sha3(code) (or whatever, just not MD5). Take some convenient number of hash prefix bits, perhaps 64, and compute prefix mod 36 to determine the 16th character. This is a change to the requirements. You have the flexibility of prepending a secret pepper if you wish to prevent outsiders from making up codes that on the surface appear to be possibly valid. And with all of these, in the rare case that "dup character" is violated we can simply begin again from scratch.

4. fix what you have

Roll 16 random characters. Likely the resulting code is not valid, and likely the average value exceeds 16. If it's less than 16, re-roll (because I'm lazy). Otherwise assign the positive quantity surplus = sum(values) - 256.

Now iterate to drive the surplus to zero by looping approximately surplus times.

• Pick a random index.
• Decrement the character value, with "A" wrapping around to "9".

Verify the sum is now 256 (the surplus is zero).

Full disclosure: There's kind of a detail associated with that wrap-around step, if you're unlucky enough to land on "A". You could just reject such an index. Alternatively, increment surplus by 36, and we'll have some more looping to do.

This approach does not imply a change to the requirements.

However, it does noticeably reduce the entropy of each valid code. If we were allowed to choose each of the 16 characters freely, a registration code would have almost 83 bits of entropy. If rejection sampling discarded exactly 1/256-th of that space, we would be left with 75 bits of entropy. Since the required average of 16 is definitely less than 19, the strength of each registration code is even less than 75 bits, because characters near "Z" are less likely. Adopting an alternate approach, perhaps the third one, would result in significantly stronger registration codes without altering the end user experience.

Answer 2

To start, you're using the wrong random number generator; see the current crypto RNG. That's one of the biggest security risks here.

Handling of generated_codes.txt might also be risky but this is unclear in context. It's plain-text and not encrypted, and there's no evidence that you're enforcing strict file permissions.

Answer 3

• private global fields should starts with underscore _generatedCodes to distnguish between local and global fields.
• It's a bad practice to load files with dynamic size that could grow over the time and fill up your memory with unnecessary data, instead read the file line by line, or better yet, use a database of choice.
• Random should be declared as global static field to enforce unique results.
• GenerateCode this should only generate the code, and only validate code nullity and existence.
• ValidateCode you don't need to validate everything in the generated code, as code requirements are fixed, so all generated codes will always have the same length with the same alphanumeric values, you only want to check wither it exists in the store or not, the rest of validation should be only used with what's coming from the outside (when reading outside data source or parsing a code).
• If you're generating codes for security purpose, then you should consider a secured alternative than Random such as SHA256 or RNGCryptoServiceProvider.
• You can use RNGCryptoServiceProvider and Base32 which would give you a close result of your alphanumeric requirement, as Base32 uses (A-Z, 2-7). (if I'm not mistaken using byte[32] with RNGCryptoServiceProvider and hashing it with base32 would give approximately 256 string characters).
• Shuffle can be omitted if you use a crypto provider.
• You can use ConcurrentStack as a cache, and generate a fixed a small amount of codes, stack them at the cache, to be ready for use, and when your cache has one item left, you can refill it with codes as a background worker process.So, the there won't be a delay for next callers.
• Since you don't need to read all file, you can use File.AppendAllLines instead , and just feed it with the new codes.