Генеруємо псевдовипадкові ID а-ля Youtube

Привіт, %username%! Буває необхідно генерувати ID не підряд, причому щоб вони гарантовано не повторювалися. На youtube це використовується для того, щоб ви не могли брутфорсом отримати все нові і старі видосики, так само це не рідкість на різних файлообмінниках і взагалі скрізь, де потрібно запобігти або хоча б утруднити можливість прямого перебору значень.


Приміром, у системі moodle, яка використовувалася у нас в універі для тестування студентів, ID відповідей були інкрементний і наскрізними на всю базу. Логічно припустити, що правильною відповіддю був той, що з найменшим ID в межах питання. Загалом, проблем з тестами у нас не було. Потім вони перейшли на GUID, але я до того моменту вже випустився, хехе.

Давайте розглянемо кілька способів генерації таких обмежених по довжині послідовності від найбільш простих до криптографічно стійких.

Спосіб номер 0. Random
Самий тру підхід в плані криптостійкості (навіть теоретично нічого не передбачити), але незручний у господарстві. Кожну ID ми генера абсолютно випадково якоюсь залізякою і перевіряємо в базі, що такої ще немає і тоді пишемо. Але це треба лізти в базу кожний раз, щоб перевірити, згодом генерація буде все повільніше і інші проблеми. Я поставив цей спосіб на перше місце, тому що тут 0 математики.

Кільце вирахувань
Точніше, мультиплікативна група кільця вирахувань. Насправді простіше, ніж звучить. Поясню картинкою:

image
Бачите, ступеня трійки тут йдуть по порядку.
1, 2, 3, 4, 5, 6, а результат залишку від ділення — немає
3, 2, 6, 4, 5, 1. Але все одно в підсумку всі числа від 1 до 6 присутні.

7 називається модулем, а 3 — первообразным коренем (генератором). Щоб це працювало, модуль повинен бути виду:
image
де p — просте число більше двох. Модулі для нас — максимальні значення ID, які ми можемо згенерувати з їх допомогою.

Чим не підхід для генерації псевдовипадкових айдишек? Беремо ID по порядку, зводимо генератор ступінь цієї ID і беремо залишок по модулю. Для досить великих модулів вийде цілком собі.

Це, до речі, майже Діффі Хэллман, тільки в менших масштабах. До речі, ті хто генерил ручками параметри DH для веб серверів, знають, що це процес нешвидкий. Саме тому, що шукати первісний корінь для великих чисел непросто.

Лінійний конгруэнтный метод
Популярна штука як дефолтних генераторів випадкових чисел в багатьох мовах програмування, але абсолютно не криптостойкая. Ось її формула:

image
При правильно підібраних параметрах забезпечує період рівний m.

А якщо в якості m вибрати просте число, то навіть c можна викинути при певних умовах, період буде максимальним або близьким до нього.

Недоліки очевидні — потрібно шукати спец числа, та й не факт що вони будуть кратні розміру байта. Ну і передбачити наступний член послідовності, знаючи попередні, можна, це довели математики.

Лінійні регістри зсуву зі зворотнім зв'язком
Абсолютно чудові конструкції, які дозволяють генерувати псевдовипадкові послідовності шляхом перексоривания всього декількох біт. Які біти ксорить визначає многочлен, що лежить в основі LFSR. Якщо він примітивний, то послідовність вийде максимальною.

Ці примітивні многочлени не так-то просто генерувати, приблизно як шукати прості числа. Але знайшлася таки відмінна програмка primpoly, яка вміє знаходити примітивні многочлени заданої ступеня. Навіть може виводити списком всі можливі примітивні многочлени якщо передати параметр a, наприклад, Primpoly.exe -a 2 64.

Якщо нам потрібна ID розміром 8 байт, приблизно як на Youtube, то ось самий мінімальний поліном x ^ 64 + x ^ 4 + x ^ 3 + x + 1.

Як ним користуватися:

У нас є будь 64битное число, крім нуля. Ми ксорим між собою 64 біти, 4, 3 і 1. Одиниця в поліномі означає, що числа зсувається вправо на 1 біт, а результат ксора поміщається в старший біт.

Приклад реалізації на C:

bit = ((lfsr >> 0) ^ (lfsr >> 60) ^ (lfsr >> 61) ^ (lfsr >> 63) ) & 1;
lfsr = (lfsr >> 1) | (bit << 63);

Зсув на 0 дає нам біт 64, зсув на 1 біт 63 і т. д. Якщо цей код виконувати в нескінченному циклі, то в результаті ми прийдемо до того значення, з якого починали.

А якщо прогнати число через кілька регістрів з різними многочленів, передбачити таку послідовність буде досить складно навіть математично підкованим товаришам. До речі, на принципі комбінації LFSR побудовані алгоритми шифрування GSM трафіку A5/1 і A5/2, правда їх вже поламали, але тим не менш.

Мінус такого підходу в тому, що ми можемо отримувати ID лише послідовно, не знаючи наперед, яка буде «через одну». Тому переходимо до наступного.

Оборотні функції
Або ще назвемо їх ізоморфні. Ось тут взагалі нескінченну кількість варіантів, все обмежується лише вашою фантазією і бажанням накрутити складність процесу, результатом якого є ваша айдишечка.

Наприклад, візьмемо функції σ0 і σ1 з SHA-256, які одному 32битному числа зіставляють інше 32битное (f1 і f2 вони називаються в описі потокового шифру HC-128).

image
image

>>> це циклічний зсув, >> це просто зсув вправо.

Ось цитата від товаришів, які досліджували ці функції:
The σ0 and σ1 GF(2)- linear mappings are one to one (in order to check this property, we computed the 32x32 GF(2) matrices representing σ0 and σ1, and checked that the kernel of this matrix was restricted to the null vector).
З неї зрозуміло, що вони ізоморфні (one to one), можна самим не перевіряти. Ми навіть можемо зворотну функцію не будувати, просто всі числа в циклі проганяємо через одну або іншу, або обидві, або кілька разів одну, потім іншу пару раз, ну ви зрозуміли. І отримуємо все ID в діапазоні 32 біт в псевдовипадковому порядку, про який знаємо тільки ми.

Таких функцій понапридумувати, як ви розумієте, можна базилион і комбінувати як завгодно. Але поки що, це теж не криптостійкий спосіб. Та й отримати назад, якщо потрібно, оригінальну ID по-простому не вийде.

Криптостойкая генерація послідовностей ID будь-якого розміру
Ви не повірите, але все вже придумано за нас, я навіть статтю про це писав.

Тільки тут у нас не номери кредиток, а числа розміром скільки нам потрібно. Від 16 до 192 біт з кроком в 1 біт для одного раунду алгоритму BPS. Ми беремо основа системи таке яке нам потрібно, не обов'язково кратне 8. В алгоритмі ліміт на максимальне підстава 65536, але ніщо не заважає зробити більше, технічно там в одну половинку мережі фейстеля поміщається 96 біт. Або взагалі не готувати зробити підстава 256 і просто шифрувати стільки байт скільки їх у вашій айдишке.

Отже, налаштовуємо BPS на це підстава, ключ для AES, IV(Tweak) і проганяє всі оригінальні ID від 1 до основа системи — 1» через цей BPS. Потім те, що вийшло обертаємо в який-небудь base58 і ось вам готова красива айдишечка.

Нам навіть зберігати її не треба, ми можемо її розшифрувати і зіставити оригінальної нормальної айдишке, бекенд взагалі може не знати про те, що ми з ID извращаемся.

Такі справи.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.