Будет ли работать этот алгоритм запутывания для сокращения URL?
ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ: Я не спрашиваю, как сократить URL-адрес (я уже реализовал найденный ответ "биективная функция" ЗДЕСЬ, использующий строку в кодировке base-62). Вместо этого я хочу расширить эту реализацию, чтобы запутать сгенерированную строку так, чтобы это было так:
А) не легко угадываемая последовательность, и
Б) все еще биективно.
Вы можете легко рандомизировать свой набор символов base-62, но проблема в том, что он все еще увеличивается, как и любое другое число в любой другой базе. Например, одна возможная постепенная прогрессия может быть {aX9fgE, aX9fg3, aX9fgf, aX9fgR, … ,}
Я придумала технику запутывания, которая меня устраивает с точки зрения требования А), но я лишь частично уверена, что она удовлетворяет требованиям Б). Идея заключается в следующем:
Единственное, что гарантированно изменится в инкрементальном подходе, это "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) ".
Любые дыры, которые вы можете найти, будут оценены.
4 ответа
Если вы честно хотите, чтобы о них было трудно догадаться, сделайте это просто.
Начните с обычного алгоритма шифрования, работающего в режиме счетчика. Когда вы получите URL-адрес для сокращения, увеличьте свой счетчик, зашифруйте его, преобразуйте результат во что-нибудь, используя печатные символы (например, base 64), и поместите исходный URL-адрес и сокращенную версию в свою таблицу, чтобы вы могли получить исходный URL-адрес из сокращенная версия при необходимости.
Единственный реальный вопрос на тот момент - какой алгоритм шифрования использовать. Это, в свою очередь, зависит от вашей модели угроз. Я не вижу точно, что вы получаете, делая укороченные URL-адреса трудными для угадывания, поэтому я немного сомневаюсь в модели угроз.
Если вы хотите, чтобы это было немного сложно угадать, вы можете использовать что-то вроде 40-битной версии RC4. Это довольно легко сломать, но достаточно, чтобы большинство людей не беспокоилось.
Если вы хотите немного больше безопасности, вы можете перейти к DES. Это было сломано, но даже в такой поздний срок это довольно много работы.
Если вы хотите больше безопасности, чем это, вы можете использовать AES.
Обратите внимание, что по мере повышения безопасности сокращенный URL-адрес становится длиннее. RC4-40 начинается с 5 байтов, DES 7 байтов и AES с 32 байтами. В зависимости от того, как вы конвертируете в печатный текст, это будет немного расширяться.
Я попытался решить ту же проблему (в php) и в конечном итоге с этими функциями:
- хэширование идентификатора строки с помощью своего рода алгоритма Фейстеля
- применение биективной функции для сжатия целого числа
Так что для А): это не так легко угадать (для меня), так как вы не можете увеличить строку, чтобы получить следующую запись без алгоритма
А для Б): насколько я понимаю, это на 100% биективно.
Спасибо @Nemo за наименование сети feistel, которая привела меня к первой функции, с которой я связался.
Другой вариант - использовать конструкцию Luby-Rackoff (см. Также здесь), которая является способом генерации псевдослучайной перестановки из псевдослучайной функции.
Вам просто нужно выбрать "круглую функцию" F. F должен взять в качестве ввода ключ K и блок битов, вдвое меньший того, что вы кодируете. F должен выводить блок битов также вдвое меньше, чем вы кодируете.
Затем вы просто запускаете конструкцию Luby-Rackoff (также известную как "сеть Фейстеля") в течение четырех раундов, каждый из которых использует свой K.
Конструкция гарантирует, что результатом является биективное отображение, и его будет трудно инвертировать при условии, что F трудно инвертировать.
Если вы пытаетесь не допустить, чтобы люди сканировали URL-адреса, я думаю, что у Ника Джонсона правильная идея, что вам нужно убедиться, что ваше URL-пространство не является плотным.
Вот простая идея: возьмите свой URL и добавьте к нему несколько случайных символов. Затем запустите его с помощью алгоритма сжатия - я бы попробовал кодирование диапазона (вы, вероятно, сможете указать основу, если найдете хорошую библиотеку). Это должно быть сжимаемо до первоначальной формы и должно как влиять на локальность, так и делать кодированное пространство более разреженным.
Тем не менее, я полагаю, что почти все средства сокращения URL хранят хеш-таблицу с состоянием на стороне сервера. Как еще вы собираетесь без потерь сжать 100-символьный URL в 5 или 6 символов?