Есть страница вида /order/123456. 123456 это идентификатор чего-либо. Страница не требует авторизации, в то же время нежелательно, чтобы кто-то мог угадывать валидные идентификаторы, поэтому идентификатор генерируется случайно от 1 до N. Пусть в базе M записей (например миллион). Пусть злоумышленник делает t попыток отгадать (например 1000 в секунду или 86400 * 1000 * 365 * 10 = 315,3 млрд за 10 лет). Пусть хочется, чтобы шанс отгадать хоть один идентификатор был <= 1%. Как правильно посчитать N для таких входных данных?
Я посчитал, у меня непонятная формула получилась. Шанс не угадать в 1 раз (1 — M/N) = (N-M)/N, во второй раз (N-M)/N * (1 — M/(N-1)) = ((N-M)(N-M-1))/(N(N-1)), в t-й раз [(N-M)*(N-M-1)*(N-M-(t-1)]/[N*(N-1)*...*(N-(t-1))] = [(N-M)! * (N-t)!] / [(N-M-t)! * N!]. И чего мне теперь с этими факториалами делать я не понимаю.
В принципе вопрос можно переформулировать как длина идентификатора сессии, там по сути такие же условия, есть M активных сессий, длина идентификатора N, есть атака с подбором сессии.
Здравствуйте, vsb, Вы писали:
vsb>Есть страница вида /order/123456. 123456 это идентификатор чего-либо. Страница не требует авторизации, в то же время нежелательно, чтобы кто-то мог угадывать валидные идентификаторы, поэтому идентификатор генерируется случайно от 1 до N.
Здравствуйте, vsb, Вы писали:
vsb>В принципе вопрос можно переформулировать как длина идентификатора сессии, там по сути такие же условия, есть M активных сессий, длина идентификатора N, есть атака с подбором сессии.
Здравствуйте, vsb, Вы писали:
vsb>Есть страница вида /order/123456. 123456 это идентификатор чего-либо. Страница не требует авторизации, в то же время нежелательно, чтобы кто-то мог угадывать валидные идентификаторы, поэтому идентификатор генерируется случайно от 1 до N. Пусть в базе M записей (например миллион). Пусть злоумышленник делает t попыток отгадать (например 1000 в секунду или 86400 * 1000 * 365 * 10 = 315,3 млрд за 10 лет). Пусть хочется, чтобы шанс отгадать хоть один идентификатор был <= 1%. Как правильно посчитать N для таких входных данных?
За одну попытку, вероятность угадать будет — M/N. Соотвественно за t — t*M/N. Ну и осталось посчитать число N для удовлетворившей бы вас вероятности p — N = t*M/p. формула не очень точна, тк не учитывает уменьшения кол-ва вариантов при последующих попытках, но при N существенно превышающих t, думаю этим можно пренебречь.
Здравствуйте, Sharov, Вы писали:
vsb>>Есть страница вида /order/123456. 123456 это идентификатор чего-либо. Страница не требует авторизации, в то же время нежелательно, чтобы кто-то мог угадывать валидные идентификаторы, поэтому идентификатор генерируется случайно от 1 до N.
S>А почему не сделать guid?
GUID это 128 битов. Может быть можно обойтись меньшим числом. В частности интересует 72 бита (12 символов в base64).
Здравствуйте, vsb, Вы писали:
vsb>Здравствуйте, Sharov, Вы писали:
vsb>>>Есть страница вида /order/123456. 123456 это идентификатор чего-либо. Страница не требует авторизации, в то же время нежелательно, чтобы кто-то мог угадывать валидные идентификаторы, поэтому идентификатор генерируется случайно от 1 до N.
S>>А почему не сделать guid?
vsb>GUID это 128 битов. Может быть можно обойтись меньшим числом. В частности интересует 72 бита (12 символов в base64).
Зато крайне затруднительно отгадать. В у нутрях можно mapping на человеческий id сделать.
Здравствуйте, wildwind, Вы писали:
vsb>>GUID это 128 битов. Может быть можно обойтись меньшим числом. В частности интересует 72 бита (12 символов в base64).
W>Ты байты на дисках экономишь? Или этот ID будут по телефону диктовать?
Я всё экономлю, что можно экономить без дополнительных усилий.
Здравствуйте, vsb, Вы писали:
vsb>Здравствуйте, wildwind, Вы писали:
vsb>>>GUID это 128 битов. Может быть можно обойтись меньшим числом. В частности интересует 72 бита (12 символов в base64).
W>>Ты байты на дисках экономишь? Или этот ID будут по телефону диктовать?
vsb>Я всё экономлю, что можно экономить без дополнительных усилий.
Здравствуйте, vsb, Вы писали:
vsb>В принципе вопрос можно переформулировать как длина идентификатора сессии, там по сути такие же условия, есть M активных сессий, длина идентификатора N, есть атака с подбором сессии.
Если нужно, чтобы не угадали, это задача решается вот так:
/order/12345&hmac=1e4f23
Или вот так:
/order/1e4f2312345
Или вот так:
order_id = 12345
hmac_value = hmac(order_id) //1e4f23
display_order_id = rc4(hex(hmac_value) ++ hex(order_id)) // что-то вроде 1aee1516ba
Здравствуйте, scf, Вы писали:
scf>Здравствуйте, vsb, Вы писали:
vsb>>В принципе вопрос можно переформулировать как длина идентификатора сессии, там по сути такие же условия, есть M активных сессий, длина идентификатора N, есть атака с подбором сессии.
scf>Если нужно, чтобы не угадали, это задача решается вот так: scf>/order/12345&hmac=1e4f23
scf>Или вот так: scf>/order/1e4f2312345
scf>Или вот так: scf>order_id = 12345 scf>hmac_value = hmac(order_id) //1e4f23 scf>display_order_id = rc4(hex(hmac_value) ++ hex(order_id)) // что-то вроде 1aee1516ba
scf>Незачем базу насиловать.
