Будет ли работать этот алгоритм запутывания для сокращения URL?

Question

ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ: Я не спрашиваю, как сократить URL-адрес (я уже реализовал найденный ответ «биективная функция» ЗДЕСЬ , использующий строку в кодировке base-62). Вместо этого я хочу расширить эту реализацию, чтобы запутать сгенерированную строку, чтобы она выглядела как

A) не легко угадываемая последовательность , а

B) все еще биективен.

Вы можете легко рандомизировать свой набор символов base-62, но проблема в том, что он все еще увеличивается, как и любое другое число в любой другой базе. Например, одна из возможных последовательных последовательностей может быть {aX9fgE, aX9fg3, aX9fgf, aX9fgR, … ,}

Я придумала технику запутывания, которой я доволен с точки зрения требования A) , но я лишь частично уверена, что она удовлетворяет B) . Идея такова:

Единственное, что гарантированно изменится в инкрементальном подходе, это "1-е место" (я буду использовать десятичную терминологию по соображениям практичности). В приведенном выше примере последовательности это будет {E, 3, f, R, …}. Поэтому, если каждый символ в наборе base-62 имеет свой уникальный номер смещения (скажем, его расстояние от «нулевого символа»), то вы можете применить смещение символа «1 место» к остальной части строки.

Например, допустим, набор base-5 с символами {A, f, 9, p, Z, 3} (в порядке возрастания от 0 до 5). Каждый из них будет иметь уникальное смещение от 0 до 5 соответственно. Подсчет будет выглядеть как {A, f, 9, p, Z, 3, fA, ff, f9, fp, …} и так далее. Таким образом, алгоритм, когда ему присваивается значение fZ3p, будет смотреть на p и, имея смещение +3, переставит строку в Zf9p (предполагая, что набор base-5 представляет собой круговой массив). Следующим инкрементным числом будет fZ3Z, а при смещении Z, равном +4, алгоритм возвращает 39pZ. Эти переставленные результаты будут переданы пользователю в качестве его / ее «уникального URL», который никогда не увидит фактическую base-62 строку в кодировке.

Этот подход, безусловно, кажется обратимым; просто посмотрите на последний символ и выполните ту же перестановку с отрицательным смещением. И я думаю, что по этой причине он все еще должен быть биективным. Но я не знаю, верно ли это ? Есть ли какие-либо крайние / угловые случаи, которые я не рассматриваю?

РЕДАКТИРОВАТЬ: Мои намерения в большей степени ориентированы на длину сокращенного URL, чем на безопасность шаблона. Я понимаю, что существует множество решений, включающих криптографические функции, блочные шифры и т. Д. Но я хотел бы подчеркнуть, что я не спрашиваю лучший способ достижения A) , а скорее, « - мой подход смещения, удовлетворяющий B) ».

Будем благодарны за любые найденные дыры.

Answer 1

Если вы честно хотите, чтобы о них было сложно догадаться, сделайте это просто.

Начните с обычного алгоритма шифрования, работающего в режиме счетчика. Когда вы получите URL-адрес для сокращения, увеличьте свой счетчик, зашифруйте его, преобразуйте результат во что-нибудь, используя печатные символы (например, основание 64), и поместите исходный URL-адрес и сокращенную версию в вашу таблицу, чтобы вы могли получить исходный URL-адрес из сокращенная версия при необходимости.

Единственный реальный вопрос на данный момент - какой алгоритм шифрования использовать. Это, в свою очередь, зависит от вашей модели угрозы. Я не вижу точно, что вы получаете, делая укороченные URL-адреса трудными для угадывания, поэтому я немного не уверен в модели угрозы.

Если вы хотите сделать легкое угадывание, вы можете использовать что-то вроде 40-битной версии RC4. Это довольно легко сломать, но достаточно, чтобы большинство людей не беспокоилось.

Если вы хотите немного больше безопасности, вы можете перейти к DES. Это было сломано, но даже на этом позднем выходе из строя это довольно немного работы.

Если вы хотите больше безопасности, чем это, вы можете использовать AES.

Обратите внимание, что по мере повышения безопасности сокращенный URL-адрес становится длиннее. RC4-40 начинается с 5 байтов, DES 7 байтов и AES с 32 байтами. В зависимости от того, как вы конвертируете в печатный текст, это будет немного расширяться.

Answer 2

Я пытался решить ту же проблему (в php) и в конечном итоге с этими функциями:

• хэширование идентификатора строки с помощью некоторого алгоритма фейстела
• применение биективной функции для сжатия целого числа

То же самое для A): это не так легко угадать (для меня), поскольку вы не можете увеличить строку, чтобы получить следующую запись без алгоритма

А для Б): насколько я понимаю, это на 100% биективно.

Спасибо @Nemo за присвоение имени сети feistel, которая привела меня к первой функции, с которой я связался.

Answer 3

Другой вариант - использовать конструкцию Luby-Rackoff (см. Также здесь ), которая является способом генерации псевдослучайной перестановки из псевдослучайной функции.

Вам просто нужно выбрать «круглую функцию» F. F должен принять в качестве ввода клавишу K и блок битов, вдвое меньший того, что вы кодируете. F должен выдавать на выходе блок битов, также вдвое меньший, чем вы кодируете.

Затем вы просто запускаете конструкцию Luby-Rackoff (он же "Сеть Фейстеля") в течение четырех раундов, каждый раунд использует различную K.

Конструкция гарантирует, что результатом является биективная карта, и ее будет трудно инвертировать при условии, что F трудно инвертировать.

Answer 4

Если вы пытаетесь не допустить, чтобы люди сканировали URL-адреса, я думаю, что у Ника Джонсона правильная идея, что вам нужно убедиться, что ваше URL-пространство не является плотным.

Вот простая идея: возьмите свой URL и добавьте к нему несколько случайных символов. Затем запустите его с помощью алгоритма сжатия - я бы попробовал кодирование диапазона (вы, вероятно, можете указать основу, если найдете хорошую библиотеку). Это должно быть сжимаемо до первоначальной формы и должно влиять на локальность и делать кодированное пространство более разреженным.

Тем не менее, я полагаю, что почти все средства сокращения URL хранят хеш-таблицу с состоянием на стороне сервера. Как еще вы собираетесь без потерь сжать 100-символьный URL в 5 или 6 символов?