Problem
In gimbal_uuid.c, UUIDs are generated with the following:
// Implemented per RFC4122 section 4.4
GBL_EXPORT GBL_RESULT GblUuid_initV4(GblUuid* pSelf) {
GBL_CTX_BEGIN(NULL);
GBL_CTX_VERIFY_POINTER(pSelf);
// First initialize all bytes to random/psuedo-random numbers
for(unsigned b = 0; b < GBL_UUID_BYTE_COUNT; ++b) {
pSelf->bytes[b] = gblRandRange(0, 255);
}
where gblRandRange(0,255)
resolves to
GBL_EXPORT int gblRandRange(int min, int max) {
GBL_ASSERT(max <= RAND_MAX);
static GblBool seeded = GBL_FALSE;
if(!seeded) GBL_UNLIKELY {
srand((unsigned)gblSeed(0));
seeded = GBL_TRUE;
}
return (rand() % (max - min + 1)) + min;
}
The C standard library rand()
will typically only have a $2^{32} -1$ long period before it begins repeating for any given seed.
The issue arises, because generating multiple random numbers, and concatenating them, does not increase randomness. Since a PRNG's output is determinate, for any given seed, every next value is determinate.
Also, there is no reseeding after it is initially seeded.
In the following program I wrote which basically implements the same behavior
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <stdint.h>
#define SIZE 16
int main(void)
{
srand(time(NULL));
uint8_t reference[SIZE] = {0};
uint8_t current[SIZE] = {0};
printf("Reference: ");
for(int i = 0; i < SIZE; i++)
{
reference[i] = (uint8_t)(rand() % 256);
printf("%02X ", reference[i]);
}
printf("\nFinding duplicates...\n");
clock_t start = clock();
for(uint64_t i = 1; i < UINT64_MAX; i++)
{
for(int j = 0; j < SIZE; j++)
current[j] = (uint8_t)(rand() % 256);
if(!memcmp(reference, current, SIZE))
{
printf("Duplicate found after %llu generations\n", i);
printf("Duplicate: ");
for(int k = 0; k < SIZE; k++) printf("%02X ", current[k]);
printf("\n");
break;
}
}
clock_t end = clock();
float sec = (float)(end-start) / CLOCKS_PER_SEC;
printf("CPU time: %.3f seconds.\n", sec);
return 0;
}
Gives the following output
Reference: 51 82 D7 92 DF 69 AB B6 D1 B4 A1 8E 60 0E C8 B9
Finding duplicates...
Duplicate found after 1048576 generations
Duplicate: 51 82 D7 92 DF 69 AB B6 D1 B4 A1 8E 60 0E C8 B9
CPU time: 0.157 seconds.
Solution
To generate proper UUIDs with all the necessary bits of randomness, implementing a 128-bit PRNG yourself will likely be the best option. An LFSR or an LCG are commonly used in PRNGs.
In addition, you could also find out a scheme for reseeding your RNG in-between number generations, that could help too.