- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
def constant_time_compare(val1, val2):
"""
Returns True if the two strings are equal, False otherwise.
The time taken is independent of the number of characters that match.
"""
if len(val1) != len(val2):
return False
result = 0
for x, y in zip(val1, val2):
result |= ord(x) ^ ord(y)
return result == 0
Вообще охуеть. Не совпало в первом символе гигабайтной строки.
А прочитаешь, на первый взгляд вроде как улучшение: алгоритм не зависит от некоего M.
Жаль питонистам еще брейки не завезли.
utils.crypto же!
Это функция для сравнения всяких ключей и паролей. Надо сравнивать все символы, чтобы было невозможно использовать время работы функции для определения числа правильных символов при переборе.
Но косяк в ней всё равно есть. Если длины разные, то значение возвращается сразу.
Да и хер с ним, если честно. Хакер, скорее всего, и без этого знает, что там какой-нибудь sha-256 длиной 256 бит.
Об этом и речь. Надо проверить как можно быстрее, и только если НЕ совпало - поставить sleep/сделать N итераций чтоб получилось фиксированное.
Тут где-то уже обсуждали на примере линуксов.
Почему?
>Все равно это не константное время. Оно прямо зависит от количества символов в строке.
Оно не зависит от позиции первого несовпадающего символа, я хз как это правильно записать.
Θ(n)
Для криптографических задач важно, чтобы данные проверялись одинаковое время и хакер не мог с помощью статистики быстро подобрать токены, пароли итд
Вы или O(N) снимите или crypto наденьте. Константным временем там и пахнет.
Пароли сравнивать - хреновая идея (т.к. подразумевает хранение пароля в открытом или обратимо зашифрованном виде). А сравниваться будут, скорее всего, какие-нибудь хеши или рандомные блоки известной и постоянной (ну ок, зависящей от настроек) длины. Время тут константное в том смысле, что оно зависит только от этой константной длины, но никак не зависит от значений бит в самих строках.
но все равно ахинея. время сравнения скажем 256 бит хэшей (== 32 байта), тем более на современном железе, незначительно и сравнимо, например, с временем выполнения пролога/эпилога функции. вкинь один быстрый syscall и о длине совпадающих символом можно только гадать на картах.
Да не должны быть они интернированы... Это же довольно дорогая операция, и память жрёт. Часть строк - запросто может. Но никак не все.
Но не нужно. В чем смысл интернировать всё подряд, включая временные переменные, которые живут пару функций, и никто никогда не будет их сравнивать?
Для литералов это имеет смысл. Для остальных строк - нет.
> отнимает время при создании
Именно.
Другими словами: нахера такие хеш-таблицы вообще нужны, если из них нельзя получить то, о чем так долго говорили большевики? Деревья будут предпочтительнее всегда.
O(1) от количества записей в таблице. Но O(M) от длины строк-ключей (расчет хеша, допроверка для борьбы с коллизиями).
> Деревья будут предпочтительнее всегда.
А у деревьев еще больше сравнений. Так что не всегда.
> нахера такие хеш-таблицы вообще нужны
Ну хеш-таблицы ведь далеко не везде юзают. К примеру, в реалтаймовых приложениях, вставка в дерево за log(N) может быть предпочительней амортизированного O(1) у хеш табличек. Для огромных дисковых структур, не влезающих в память, деревья тоже предпочительней.
Интернированые строки нужно хранить в структуре с быстрым доступом - а остальные объекты не нужно? Если это делается на уровне языка, а не силами добровольцев, то на памяти это вообще никак не отразится. Примеры: V8 (NodeJS) и Луа. И ничего, живут как-то.
> Чтобы сгенерировать хеш, нужно прочитать всю строку целиком.
На коротких строках, с которые обычно встречаются на практике в виде ключей это не сильно ощутимо.
Если же смотреть контексте интернирования, то тут выгоднее повторно использовать ссылки на строки большей длины.
Ну и если строка немутабельная, то посчитать хеш придется всего 1 раз, и таким образом за O(1) проверять отсутствие строки в кеше. А ведь можно сделать и джва хеша, что прилично снизит вероятность полного сопоставления.
Кстати мы не так давно тут с Тарасом обсуждали префиксные деревья.
Орально обсуждали?
>>Очко сильно раздолбано
>>Орально обсуждали
Не, это не в стиле Тараса. Непохоже на него.
"""
Returns True if the two strings are equal, False otherwise.
The time taken is independent of the number of characters that match.
"""
time.sleep(random(500))
return val1==val2