3 ms·

From TFA: > We knew that we wanted to avoid using integer IDs so that we wouldn’t reveal the count of records in all our table In order to attain that property

From TFA: > We knew that we wanted to avoid using integer IDs so that we wouldn’t reveal the count of records in all our table In order to attain that property the seed must be kept secret, right? A secret that cannot be rotated is hard to work with.

thaumaturgy 4y ago
The seed for an LFSR is just the starting value for its cycle; it can be any value in the cycle, and it's public anyway in that you can think of each output of an LFSR as the "seed" for the next output. But in the case of the "taps", yes, you would want to treat those as a secret if you didn't want someone to predict the next value in the cycle. An LFSR by itself might not be a complete solution for IDs for public consumption, but it does neatly solve the need for pseudo-random non-colliding IDs. Whereas NanoIDs are able to generate values with a ~1% probability of collision over some time period, LFSRs can generate values with a 0% probability of collision over their entire bit space. (And they're composable!) It looks like NanoIDs are entirely random values reduced to a specific alphabet (https://github.com/ai/nanoid/blob/main/index.js https://github.com/ai/nanoid/blob/main/index.js) -- which is approximately similar to: tr -dc _A-Z-a-z-0-9 < /dev/urandom | tr -d '/+oO0lLiI1\n\r' | head -c $num_chars ...but with a really nice collision estimation tool attached. So if you want randomness in your IDs and you still also want to guarantee 0 collisions, then you can always just append a randomly-generated value to the output of the LFSR, and then feed that into whatever widget you want to use to convert it into a public ID, if you think it's necessary. But the edge case of collision prevention at really large scales has always seemed to me to be much harder to solve than the edge case of ID enumeration giving up anything valuable (in a well-designed application).
philsnow 4y ago
Most implementations of generating non-sequential(-appearing) IDs have the property that they generate keys uniformly at random in a different keyspace. An attacker that can gather a large number of IDs can get an arbitrarily-good guess at the number of IDs you've generated. If the attacker can only check whether certain keys exist, they can just pick a 2^N-sized range of your keyspace, look up whether all those keys exist, and extrapolate from that an increasingly good (with higher N) guess of how many IDs you've generated.

thaumaturgy 4y ago

The seed for an LFSR is just the starting value for its cycle; it can be any value in the cycle, and it's public anyway in that you can think of each output of an LFSR as the "seed" for the next output. But in the case of the "taps", yes, you would want to treat those as a secret if you didn't want someone to predict the next value in the cycle. An LFSR by itself might not be a complete solution for IDs for public consumption, but it does neatly solve the need for pseudo-random non-colliding IDs. Whereas NanoIDs are able to generate values with a ~1% probability of collision over some time period, LFSRs can generate values with a 0% probability of collision over their entire bit space. (And they're composable!) It looks like NanoIDs are entirely random values reduced to a specific alphabet (https://github.com/ai/nanoid/blob/main/index.js https://github.com/ai/nanoid/blob/main/index.js) -- which is approximately similar to: tr -dc _A-Z-a-z-0-9 < /dev/urandom | tr -d '/+oO0lLiI1\n\r' | head -c $num_chars ...but with a really nice collision estimation tool attached. So if you want randomness in your IDs and you still also want to guarantee 0 collisions, then you can always just append a randomly-generated value to the output of the LFSR, and then feed that into whatever widget you want to use to convert it into a public ID, if you think it's necessary. But the edge case of collision prevention at really large scales has always seemed to me to be much harder to solve than the edge case of ID enumeration giving up anything valuable (in a well-designed application).

philsnow 4y ago

Most implementations of generating non-sequential(-appearing) IDs have the property that they generate keys uniformly at random in a different keyspace. An attacker that can gather a large number of IDs can get an arbitrarily-good guess at the number of IDs you've generated. If the attacker can only check whether certain keys exist, they can just pick a 2^N-sized range of your keyspace, look up whether all those keys exist, and extrapolate from that an increasingly good (with higher N) guess of how many IDs you've generated.