Virgil Security, Inc. corporate blog
Cryptography
Algorithms
Mathematics
Comments 41
0
Надеюсь вы понимаете, что:
Нам даже хранить её не надо, мы можем её расшифровать и сопоставить оригинальной нормальной айдишке, бекенд вообще может не знать о том, что мы с ID извращаемся.

Полностью убивает идею
чтобы вы не могли брутфорсом получить все новые и старые видосики, так же это не редкость на разных файлообменниках и вообще везде где нужно предотвратить или хотя бы затруднить возможность прямого перебора значений.

Это называется security through obscurity и не является защитой вообще. Либо алгоритма генерации нет вообще(с допуском на качество рандом генератора) и вы храните в своей базе, либо это можно перебирать, только способ перебора сходу не очевиден. Насколько важно на самом деле защитить от перебора? Если не важно совсем то можно открытый id показывать, если хоть сколько то важно, то надо защищать нормально.

EDIT:
Мать моя женщина, это секьюрити компания написала.
+6
При чем тут security through obscurity? Я могу в открытую опубликовать алгоритм шифрования ID, но ключ останется у меня. И это никак не ослабит защиту от прямого перебора. Хочется перебирать все возможные варианты — никто не запрещает, но по порядку это сделать не получится, придется шерстить весь диапазон.
0
Да, с BPS будет нормально, согласен. Из предложенных методов безопасен первый и последний. Возможно стоит в статье сделать какой-то доп акцент на это.
0
А там написано «от самых простых до криптографически стойких». Чтобы больше не было путаницы, перенес random в конец
0

Там все способы безопасны при достаточном размере диапазона и случайных параметрах. Просто варианты с шифрованием и истинным радномом достаточно защищены "от дурака".

+2
Статья хорошая, применение — хотя бы даже генерировать номера скрэтч-карт для оплаты чего-либо.
+1
Для реализации псевдосоучайных идентификаторов можно использовать http://hashids.org реализованную на большинстве языков. Но она не совместима со словом «security» о чем честно написано в README
0
В частности эта библиотека использовалась для передачи идентификатора пользователя для выбора шардирования, и идентификатора сущности.
+4
Длинный же, хочется покороче. Гуиды обычно напоказ не выставляют, не красиво
+1

Гуиды можно в алфавите побольше кодировать, например, с base-64 получится "80XQyRzi0EaXHbkuvCq4PA". Тоже длинно, но чуть менее ужасно, чем "c9d045f3-e21c-46d0-971d-b92ebc2ab83c". :)

+1
Из гуида лишнее можно просто вырезать. Учитывая что распределение бит равномерное и независимое, это никак не ослабляет его свойств.
+2
True random надо предгенерировать на свободных машинах заранее, тогда клиенту не надо будет ждать лишний раз.
0
Ради айдишек городить такую инфраструктуру, мне кажется, никто не будет, проще заюзать BPS. К тому же, у него есть один интересный побочный эффект — смена ключа мгновенно меняет все видимые ID на другие. Не уверен, что это прям крутое преимущество, но где-то может пригодиться, например чтоб кеши какие то сбросить
+2
Есть еще замечательные алгоритмы, наподобие Blum Blum Shub.
Он просто красив в своем исполнении. Доказано его сведение к Quadratic residuosity problem, что позволяет считать его криптографически стойким. + обладает возможностью получения произвольного элемента последовательности по номеру без вычисления предыдущих.
Скорость только не радует, но все-равно он шикарен.
0
Разве получится с его помощью генерить криптостойкие 32 или 64битные последовательности? Если будем брать не все биты, то не сможем восстановит�� оригинальный номер, а если брать маленькие простые числа, то их факторизовать можно чуть ли не на бумажке
0
Числа нужно брать большие, чтобы получить криптостойкий результат. Почему мы не сможем восстановить оригинальный номер? В данном алгоритме последовательность получается из одного или нескольких наименее значащих бит каждого из чисел.
+2
Если я правильно прочитал вики, алгоритм позволяет узнать любой член последовательности из изначального состояния, но не наоборот. Т.е. условно, получив из ID = 5 её представление 2348203948, которое мы показываем пользователю, мы обратно сделать не сможем, придется где-то хранить это представление в дополнение к оригинальной ID.
0
А, вот вы о чем. Я понял. Да, хранить придется видимо…
0
а еще, я так понимаю, не факт, что они не повторятся, еще и на повторы надо смотреть
0
Возможно меня заплюют, но чем плох банальный XOR sha-1 от текущего времени с точностью до миллисекунды, и sha-1 большого рандомного числа? Размером такого id? Просто насколько я понимаю — вероятность того что у двух юзеров в одну и ту же миллисекунду выпадут одинаковые рандомные числа — насколько ничтожна, что можно ей пренебречь.
0
Размерчик, да. Желательно, чтобы ID поместилась хотя бы в int64
0
Ну свернуть криптостойким хешом то можно до любого размера, в любом случае вероятность пересечения будет зависеть от размера id.
+1
т. е. все равно надо будет смотреть, не пересекается ли. А это уже можно свести к последнему варианту
0
Этот вариант очень хорош, мы в одном проекте который уже в продакшене используем такой метод.
string = userId + getLongTime + SecureRandom.(«seed»);
secureStr = encodeBase64(string)
На выходе получаем что-то типа этого "[B@43a53fe7" и коротко и очень быстро генерит (мы так генерим токены авторизации)
+3
Логично предположить, что правильным ответом был тот, что с наименьшим ID в пределах вопроса

Объясните логику пожалуйста.
+1
Ленивые преподы сначала заводили в админке правильный ответ, а потом неправильные, у правильного ID была наименьшей. Потом в исходнике страницы просто смотрели какой из вариантов ответа наименьший, он чаще всего и был правильным
+1
Я так тест на уроке истории в школе взломал, причём в докомпьютерную эпоху. Просто обратил внимание, что значения правльных ответов (годы событий) идут в строго возрастающем порядке, что сильно сократило количество возможных вариантов ответов для вопросов.
0
Мне вот еще интересно, как генерировать такие строковые id, если наложены дополнительные ограничения для человекочитаемости — например, отсутствие в итоговой строке буквы «l», поскольку она похожа на единицу. Тупо проверять и перегенерировать, если что?
+2
Должно быть просто, если использовать подход с алгоритмом BPS из предыдущей статьи.
Если делать всё честно, то:

1) Определяете свой алфавит, его размер будет основанием системы счисления, base
2) Определяете сколько символов у вас будет в айдишке Назовем длину len. Если 10, то максимальная айдишка это base^10 -1.
3) Заводите массив интов, размером с len, но в котором значения могут быть лишь в диапазоне 0..base-1

Всё, основа готова. Зашифрованный массив получится такой же длины, а значения в нём будут индексами букв из вашего алфавита.

Чтобы получить следующее значение, вам нужно инкрементнуть массив, это делается буквально двумя строчками кода

func increment(counter []byte, base int) {
	for i := len(counter) - 1; i >= 0; i-- {
		counter[i] = (counter[i] + 1) % base
		if counter[i] != 0 {
			break
		}
	}
}


Но вообще, вся эта свистопляска с основаниями нужна по сути только в части вывода при шифровани и ввода при зашифровывании. Внутри там всё равно используется bigInt, если немного подковырять, можно работать напрямую с ним, минуя ненужные преобразования.

И если всё сделать правильно, получится преобразование ID -> ваш алфавит и обратно безо всяких лишних проверок
+1
К стати, можно воспользоваться библиотекой humanhash и сконвертировать полученные страшные хеши в последовательности английских слов для лучшего запоминания.
0
Только надо помнить, что если «страшные хеши» сконвертировать библиотекой humanhash, то разным «страшным хешам» могут соответствовать _одинаковые_ последовательности английских слов, т.к. humanhash — это хеширование, в котором байты бьются на блоки и каждый блок ужимается до одного байта операцией xor, а потом эти байты по таблицам заменяются на слова.
0
Эх, криптографы…

Проблема криптостойкости генераторов случайных чисел уже обсуждалась и не раз. Почитайте, например, вот эту публикацию и не изобретайте велосипеды:
https://habrahabr.ru/company/mailru/blog/273147/

Естественно, никаких маппингов из коротких последовательных ID в длинные быть не должно — они заведомо ненадёжны. Только True Random.

Каждую ID мы генерим абсолютно случайно какой-нибудь железкой и проверяем в базе, что такой еще нет и тогда пишем. Но это надо лезть в базу каждый раз, чтобы проверить, со временем генерация будет всё медленней и прочие проблемы.

Я бы не назвал это проблемой. Потому что вероятность коллизии (повторения значения 64-битного счётчика) будет крайне мала. Не получилось вставить строку в базу из-за уже существующего ключа — не вопрос, сгенерировали новый, на производительности это не скажется ну вообще никак.

Либо другой вариант генерации ID: просто прибавлять к текущему значению счётчика случайное значение в достаточно большом диапазоне. Тогда проверять на совпадение ID не нужно будет.
0
При чем тут криптостойкость ГПСЧ? ГПСЧ абсолютно не обязательно генерируют неповторяющиеся последовательности, а статья как раз про них.
Цель статьи показать, что генерировать неповторяющиеся числа не по порядку можно разными способами и абсолютно не обязательно далать это криптостойко. Но можно и упороться, про это как раз два последних способа.
-1
Цель статьи показать, что генерировать неповторяющиеся числа не по порядку можно разными способами и абсолютно не обязательно далать это криптостойко.

При том, что вы несколько раз в статье указывали на важность невозможности последовательного перебора значений ID.
0
я писал в заголовке
предотвратить или хотя бы затруднить возможность прямого перебора значений


Все описанные в статье способы как минимум затрудняют прямой перебор значений просто потому что идут не по порядку, как максимум делают это криптостойкими способами. Что не так то?
-1
Все описанные в статье способы как минимум затрудняют прямой перебор значений просто потому что идут не по порядку

Про «security through obscurity» уже писали. Для школьных тестов сойдёт, для банковских операций — увы, нет.

Что не так то?

Что криптостойкий и простой в реализации метод почему-то не оказывается предпочтительным.
+4
Я ни один из методов не рекомендую, я просто о них рассказал, а какой из них предпочтительней решать разработчикам. Разве где-то написано «генерим ID для банковских транзакций»? Я еще раз напоминаю, статья о том, что есть много абсолюто разных способов решать одну и ту же задачу — генерировать числа не по порядку без повторений.
Only those users with full accounts are able to leave comments., please.