Насколько вероятно столкновение токена с библиотекой секретов Python? - PullRequest
1 голос
/ 17 марта 2020

Насколько вероятна коллизия с токенами, сгенерированными с использованием библиотеки секретов Python (https://docs.python.org/3/library/secrets.html)?

Похоже, никаких упоминаний их уникальности.

1 Ответ

3 голосов
/ 18 марта 2020

Модуль secrets предназначен для получения секретных данных, т. Е. Информации, которая не может быть предсказана или проанализирована

Модуль секретов обеспечивает доступ к большинству безопасный источник случайности, который обеспечивает ваша операционная система.

Как правило, ОС будет использовать несколько источников энтропии для генерации битов. например, идентификатор процесса, идентификатор потока, время ввода мыши / клавиатуры, счетчики ЦП, системное время и т. д. c.

До тех пор, пока количество энтропии достаточно велико для количества генерируемых битов (и снова ОС использует много источников и постоянно накапливает энтропию), следует ожидать равномерного распределения всех значений. Поэтому, если вы сгенерируете 32-битный ключ, вы должны ожидать увидеть каждое из 4294967296 значений с одинаковой частотой.

Чтобы оценить, как долго мы ожидаем столкновения, мы, по сути, смотрим на проблему Birthday . В общем, если значения распределены равномерно, а число значений равно n, следует ожидать, что столкновение произойдет после генерации около sqrt(n) значений (хотя в действительности это немного больше).

Вы можете проверить это с помощью быстрой программы тестирования производительности

import secrets

def find_collision(b):
    tokens = set()
    while True:
        token = secrets.token_bytes(b)
        if token in tokens:
            return len(tokens)
        tokens.add(token)

b = 4
samples = 100
l = [find_collision(b) for i in range(samples)]
avg = sum(l)/len(l)

print(f'n = {2**(b*8)}, sqrt(n) = {2**(b*8/2)}')
print(f'on average, with a {b} byte token, a collision occurs after {avg} values')
n = 4294967296, sqrt(n) = 65536.0
on average, with a 4 byte token, a collision occurs after 75797.78 values

secrets не ставит никаких целей и не претендует на уникальность, так как цель состоит в том, чтобы генерировать высокую энтропию, random байтов, которые должно быть невозможно предсказать или перепроектировать. Добавление ограничений в модуль для предотвращения дубликатов по своей сути сделает его более предсказуемым. Кроме того, secrets передает вам эти байты в потоке, исходя из того, что вы берете то, что вам нужно, и используете его как хотите, поэтому предотвращение дублирования не имеет большого смысла в качестве основной задачи. Это отличается от чего-то вроде UUID, который имеет фиксированную ширину и предназначен для использования в качестве переносного идентификатора и распознанного типа данных.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...