Tukukkk

I need to generate sets of 10 bytes unique IDs. These sets can be quite big (i.e. 10000 values) and are checked by a limited-memory device for validity. So someone enters one of the IDs in the device, and the device should be able to discern whether the ID is genuine (generated by me).

The basic way would be to store in the device's memory the same set of IDs and check against the list, but I can't use all of that memory.

A second way I thought would be to use a CRC or a hash function: for instance all the IDs whose CRC is X are enabled. The problem here is that I should iterate through all the possible combination of IDs to find the ones giving the right CRC.

Ideally, I would like to find one/two functions that work like this:

 uint8_t * generate_ID(uint16_t index);

 bool is_valid validate_key(uint8_t * ID);

 //optional

 uint16_t index find_index(uint8_t * ID);



 //example

 //generate id value from index 0

 uint8_t ID[10] = generate_ID(0)

 //id is now {0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x0e, 0x0d, 0x0c, 0x0b}



 bool is_valid = validate_key(ID);

 //is_valid is True

 uint16_t index = find_index(ID);

 //index is now 0

 ID[0] = 0xff; //change ID with random value

 is_valid = validate_key(ID);

 //is_valid is now False



 //BONUS: use also a "seed" value, so that I can differentiate through sets of ids:

 uint8_t * generate_ID(uint16_t index, uint16_t seed);

 bool is_valid validate_key(uint8_t * ID, uint16_t seed);

find_index() is optional because once I know the key is valid I can simply iterate through all indexes to find the matching index.

Basically, the generate_ID() function should be complex enough so that it won't be easily guessable if not knowing a decent amount of ID, yet able to be computed on an embedded CPU with limited horsepower (Cortex M0)

A 10 byte key is not enough to make anything secure.

You need a secure hash function such as SHA2-256 whose output is 32-byte in length. SHA2 can easily be implemented on most systems.

Your key needs two parts:

[text + hash]

The first part is like a "username" and the second part is like a "password"

You also need a "secret key". This key is an array of bytes which is stored in your software. You then add the "secret key" to your "username". Find the SHA2 hash for the resulting string. Now you have an output that is the length of original text + 32 bytes for the hash.

You can use this key as a unique verifiable ID.

To test they key's authenticity, take the "username" part and add your secret key. Take SHA2 of that string, the result should match "password"

If secrecy and uniqueness is not a big issue then you can use MD5 whose output is 16 bytes. Change plain text to binary so it can store more information in fewer bytes, and your final key will be only 20 bytes. You could cut that down a bit more but reducing to 10 bytes is not recommended.

Here is an example. I used SHA2 implementation from this link:
https://github.com/B-Con/crypto-algorithms (I am not sure if it works on a big-endian machine)

Any SHA2 implementation should work.

void sha2(BYTE* dst, const BYTE* src, int len)

{

    SHA256_CTX ctx;

    sha256_init(&ctx);

    sha256_update(&ctx, (const BYTE*)src, len);

    sha256_final(&ctx, (BYTE*)dst);

}



void create_verifiable_id(const BYTE* source, BYTE *uid)

{

    BYTE hash[32];

    sha2(hash, source, ID_SIZE);



    //combine source + hash

    memcpy(uid, source, ID_SIZE);

    memcpy(uid + ID_SIZE, hash, 32);

}



int test_verfiable_id(const BYTE *uid)

{

    BYTE hash[32];

    sha2(hash, uid, ID_SIZE);



    //hash should match the second part of uid

    return memcmp(hash, uid + ID_SIZE, 32) == 0;

}



int main(void)

{

    //use a number from 0 to 0xFFFFFFFF, store in buf (4 bytes)

    //this is the "plain text" portion

    int number = 0x12345678;

    BYTE buf[ID_SIZE];

    for(int i = 0; i < sizeof(buf); i++)

    {

        buf[i] = number & 0xFF;

        number >>= 8;

    }



    //add sha2 to "plain text" to make verifiable id

    BYTE verifiable_id[32 + ID_SIZE];

    create_verifiable_id(buf, verifiable_id);



    printf("UID as hex string:n");

    for(int i = 0; i < 32 + ID_SIZE; i++)

        printf("%02X", verifiable_id[i] & 0xFF);

    printf("n");



    printf("Test (should succeed): %dn", test_verfiable_id(verifiable_id));



    //change verifiable_id and test it again

    verifiable_id[0]++;

    printf("Test (should fail): %dn", test_verfiable_id(verifiable_id));

    return 0;

}

One very simple way to do this is with a modular multiplicative inverse, as I describe in my blog post here: http://blog.mischel.com/2017/06/20/how-to-generate-random-looking-keys/.

The idea is that you map the numbers from 1 to some number x so that each number generates a unique value within that same range. So, for example, the mapping might be:

1 -> 9875

2 -> 362

3 -> 5247

...

This is a reversible calculation. So if f(1) => 9875, then g(9875) => 1.

In the code shown in the blog post, you can change the mapping by modifying the x and m values.

If you want the keys to be alphanumeric, then you need to encode them after generating the integer. And then you'll have to decode them back to an integer after the user enters it and before you try to validate.

So, for your validation, set m to a very large number. Set x appropriately, preferably a prime number larger than m. Generate the first 10,000 keys using those values. On the device that is supposed to validate these numbers, just supply the x and m values, and the maximum index (i.e. 10,000).

So a user enters the key they were given. You run the reverse of the key generation and get a number between 1 and 10,000. You know that the number is valid. If your reverse calculation returns a number that's less than 1 or greater than 10,000, then that key isn't valid.

You could extend this to multiple devices by just giving each device the start and end values that it considers valid. The reverse key calculation is the same, regardless.

This technique ensures uniqueness. Security is ... mostly through obscurity. If somebody knows the algorithm being used, including the x and m values, and knows the range of numbers that a device is set to accept, then he could generate keys to defeat the system. Whether that's a problem is something only you can answer. What is the risk of somebody trying to defeat your system, and what is the cost if they succeed?