Generate a unique, random friend code from a user ID algorithmically

Question

I am looking for a way to generate a random, unique 9 digit friend code for a user from a sequential user ID. The idea behind this is so people can't enumerate users by searching the friend codes one by one. If there are 1000 possible codes and 100 registered users, searching a random code should have a 10% chance of finding a user.

A possible way to do this is to generate a code randomly, check if the code is already in use, and if it is, try again. I am looking for an approach (mostly out of curiosity) where the friend code is generated algorithmically and is guarenteed to be unique for that user ID first try.

Specifically, given a range of numbers (1 to 999,999,999), running the function on this number should return another number in the same range, which is paired and unique to the input number. This pairing should only differ if the range changes and/or an input seed to the randomness changes.

An individual should ideally not be able to easily reverse engineer the user ID from the friend ID without knowing the seed and algorithm (or having a very large pool of samples and a lot of time - this does not need to be cryptographically secure), so simply subtracting the user ID from the maximum range is not a valid solution.

Here is some c# code that accomplishes what I am after by generating the entire range of numbers, shuffling the list, then retrieving a friend ID by treating the user ID as the list index:

int start = 1; // Starting number (inclusive)
int end = 999999999; // End number (inclusive)
Random random = new Random(23094823); // Random with a given seed

var friendCodeList = new List<int>();
friendCodeList.AddRange(Enumerable.Range(start, end + 1)); // Populate list

int n = friendCodeList.Count;

// Shuffle the list, this should be the same for a given start, end and seed
while (n > 1)
{
    n--;
    int k = random.Next(n + 1);
    int value = friendCodeList[k];
    friendCodeList[k] = friendCodeList[n];
    friendCodeList[n] = value;
}

// Retrieve friend codes from the list
var userId = 1;
Console.WriteLine($"User ID {userId}: {friendCodeList[userId]:000,000,000}");

userId = 99999999;
Console.WriteLine($"User ID {userId}: {friendCodeList[userId]:000,000,000}");

userId = 123456;
Console.WriteLine($"User ID {userId}: {friendCodeList[userId]:000,000,000}");

User ID 1: 054,677,867 User ID 99999999: 237,969,637 User ID 123456: 822,632,399

Unfortunately, this is unsuitable for large ranges - this program takes 8GB of RAM to run, with a 10 or 12 digit friend code it would not be feasible to pre-generate the list either in memory or a database. I am looking for a solution that does not require this pre-generation step.

I am interested in solutions that use either a seeded random number generator or bitwise trickery to achieve this, if it is possible. The above function is reversible (by searching the values of the list) but the solution does not need to be.

Answer 1

Quick mathematics lesson!

You're thinking of developing a way to map one integer value (the original "secret" UserId value) to another (the (encrypted) "public" value) and back again. This is exactly what a block-cipher does (except each "block" is usually 16 bytes big instead of being a single character or integer value). So in other words, you want to create your own cryptosystem.

_{(Note that even if you're thinking of converting UserId 123 into a string instead of an integer, for example, a YouTube Video Id like "dQw4w9WgXcQ") - it's still an integer: because every scalar value stored in a computer, including strings, can be represented as an integer - hence the "illegal primes" problem back in the late-1990s).}

And the biggest, most important take-away from any undergraduate-level computer-science class on cryptography is never create your own cryptosystem!.

With that out of the way...

Provided that security is not a top-concern...

...and you're only concerned with preventing disclosure of incrementing integer Id values (e.g. so your visitors and users don't see how many database records you really have) then use a Hashids library: https://hashids.org/

• For .NET, use this NuGet package: https://www.nuget.org/packages/Hashids.net/
• Overview for .NET: https://hashids.org/net/
• Project page: https://github.com/ullmark/hashids.net

In your code, construct a single Hashids object (I'd use a public static readonly field or property - or better yet: a singleton injectable service) and use the .Encode method to convert any integer int/Int32 value into a string value.

To convert the string value back to the original int/Int32, use the .Decode method.

_{As an aside, I don't like how the library is called "Hashids" when hashes are meant to be one-way functions - because the values are still reversible - albeit by using a secret "salt" value (why isn't it called a "key"?) it isn't really a hash, imo.}

---

If security really matters...

Then you need to treat each integer value as a discrete block in a block cipher (not a stream-cipher, because each value needs to be encrypted and decrypted independently by itself).

For the purposes of practicality, you need to use a symmetric block cipher with a small block-size. Unfortunately many block ciphers with small block sizes aren't very good (TripleDES has a block size of 64-bits - but it's weak today), so let's stick with AES.

AES has a block-size of 128 bits (16 bytes) - that's the same as two Int64 integers concatenated with each other. Assuming you use base64url encoding on a 16-byte value then your output will be 22 characters long (as Base64 uses 6 bits per character). If you're comfortable with strings of this length then you're all set. The shortest URL-safe string you can generate from a 128-bit value is 21 (hardly an improvement at all) because Base-73 is the most you can safely use in a URL that will survive all modern URL-transmission systems (never automatically assume Unicode is supported anywhere when dealing with plaintext).

It is possible to adapt AES to generate smaller output block-sizes, but it won't work in this case because using techniques like CTR Mode mean that the generated output needs to include extra state information (IV, counter, etc) which will end-up taking up the same amount of space as was gained.

Here's the code:

Very important notes:

• This uses CBC Mode - which means the same input results in the same output (that's required by-design!). CBC is useful when encrypting blocks independently.
• This re-uses the same IV - this is intentional and actually desirable for this application - but generally speaking do not reuse IVs when using AES for any other purpose and make sure you understand what you're doing.
*

private static readonly Byte[] _key = new Byte[] { }. // Must be 128, 192 or 256 bits (16, 24, or 32 bytes) in length.

private static readonly Byte[] _iv = new Byte[8]; // You could use the default all-zeroes.

// Note that this method works with Int32 arguments.
private static Byte[] ProcessBlock( Byte[] inputBlock, Boolean encrypt )
{
    Byte[] outputBlock;

    using( Aes aes = Aes.Create() )
    {
        aes.Key = _key;
        aes.IV  = _iv;

        using( ICryptoTransform xform = encrypt ? aes.CreateEncryptor() : aes.CreateDecryptor() )
        {
            outputBlock = xform.TransformFinalBlock( inputBlock, 0, inputBlock.Length );
        }
    }
}

public static Byte[] EncryptInteger( Int64 value )
{
    Byte[] inputBlock = new Byte[16];
    inputBlock[0] = (Byte)(value >>  0 & 0xFF);
    inputBlock[1] = (Byte)(value >>  8 & 0xFF);
    inputBlock[2] = (Byte)(value >> 16 & 0xFF);
    inputBlock[3] = (Byte)(value >> 24 & 0xFF);
    inputBlock[4] = (Byte)(value >> 32 & 0xFF);
    inputBlock[5] = (Byte)(value >> 40 & 0xFF);
    inputBlock[6] = (Byte)(value >> 48 & 0xFF);
    inputBlock[7] = (Byte)(value >> 56 & 0xFF);

    return ProcessBlock( inputBlock, encrypt: true );
}

public static Int64 DecryptInteger( Byte[] block )
{
    Byte[] outputBlock = ProcessInteger( value, encrypt: false );

    return
        (Int64)outputBlock[0] <<  0 |
        (Int64)outputBlock[1] <<  8 |
        (Int64)outputBlock[2] << 16 |
        (Int64)outputBlock[3] << 24 |
        (Int64)outputBlock[4] << 32 |
        (Int64)outputBlock[5] << 40 |
        (Int64)outputBlock[6] << 48 |
        (Int64)outputBlock[7] << 56;
};

public static String EncryptIntegerToString( Int64 value ) => Convert.ToBase64String( EncryptInteger( value ) ).Replace( '+', '-' ).Replace( '/', '_' );

public static Int64 DecryptIntegerFromString( String base64Url )
{
    if( String.IsNullOrWhiteSpace( base64Url ) ) throw new ArgumentException( message: "Invalid string.", paramName: nameof(base64Url) );

    // Convert Base64Url to Base64:
    String base64 = base64Url.Replace( '-', '+' ).Replace( '_', '/' );

    Byte[] block = Convert.FromBase64String( base64 );
    return DecryptInteger( block );
}

Answer 2

A simple method like this can produce a long sequence of numbers provided you get the constants right.

ulong Next(ulong current)
{
    unchecked
    {
        return (999_999_937L * current + 383_565_383L) % 999_999_999L;
    }
};

From memory, this kind of function can produce a sequence of 999_999_999 digits if the values in the function are chosen correctly.

My test code shows that this method can produce 500_499 numbers without repeating.

My computer can produce the entire sequence in just under 9 milliseconds so it is a fairly fast algorithm.

The first ten elements of this sequence (with leading '0's padded) is:

383565383, 602511613, 027845340, 657154301, 639998680, 703647183, 757439993, 422285770, 201847617, 869013116

---

5_960_464 * current + 383_565_383L gives a sequence length of 1_000_998 before repetition.