mrdimidium / nanoid

A tiny, secure, URL-friendly, unique string ID generator for Rust
https://docs.rs/nanoid
MIT License
545 stars 29 forks source link

nanoid::format silently truncates the dictionary #9

Closed nbraud closed 4 years ago

nbraud commented 5 years ago

nanoid::format silently truncates the dictionary it's given as input, to the largest power of 2 that's below dictionary.len() (modulo floating-point imprecision):

This causes the resulting value to have lower entropy than expected (i.e. lower guarantees on its uniqueness), when the alphabet's size is not a power of two (with the effect being more pronounced as the difference between the size and the next power of two grows smaller).

Note that the default alphabet has size 64 = 2⁶, so callers using it are not affected.

mrdimidium commented 5 years ago

Hey. Thanks for contributing. I need time to sort out the problem. Tomorrow I will be able to answer in detail :-D

nbraud commented 5 years ago

@nikolay-govorov As I mentionned in #10, I think the initial report is incorrect: I was able to add a debug assert that would catch it, and (after fixing the assert) the tests were still passing, even with non-power-of-2 alphabet lengths.