В протоколе, который проектирую, само явление "как ввод логина/пароля" на веб-сайте уходит "в отставку". Аутентификацию предлагается проводить через дополнительные HTTP-заголовки по протоколу SRP.
Сервер себя идентифицирует не по доменному имени (как это принято в SSL), а по идентификатору, который выбирает сам. Как результат, появляется понятие не сайта, а "приложения", которое может быть распределено по нескольким доменам, или, наоборот, несколько приложений (даже от разных вендоров) сконцентрироваться в пределах одного домена.
Конечно, в такой схеме любой сайт, заманивший пользователя к себе, может попытаться использовать чужой идентификатор и потребовать "авторизоваться" (аналог фишина в моей версии протокола). Но т.к. SRP требует от сторон взаимной проверки, сервер злоумышленника не сможет прикинуться легальным, и клиент это выявит (пп. 9-12 протокола).
Не получится и проксировать запросы через себя, подменяя информацию. Хотя прослушивать сможет. Но сам акт авторизации никак не выдает ключевую информацию, и уж тем более пароль. Обратите внимание, что там на первом этапе вообще передаются случайные числа, из которых получить исходный ключ или верификатор клиента невозможно, даже если решить задачу дискретного логарифма.
Кроме того, в дальнейшем полученный сессионный ключ предлагается использовать для подписи запросов клиента и сервера. Тем самым мешая проксирующему серверу "навязать" неверные данные.
Вообще, я предлагаю стандартизировать большинство процессов, связанных с аутентификацией (регистрация, замена ключей, логин/логаут, предоставление/отзыв доступов сторонним интернет-приложениям, резервный план восстановления учеток и другое), освободив разработчиков от это "рутины". Но это тема большой отдельной статьи.
Ага. Это полбеды. А ещё есть такая штука, как StoneGate, у которой заявлено "инспекция HTTPS-трафика со скоростью 40Мб/с". И она вскрывает трафик без всяких предварительных установок сертификатов. Автору самому "больно щелкнули по носу", когда он усомнился в таком. Так что я сейчас немного настороженно отношусь к т.н. гражданской криптографии.
И кстати, интернет в российских школах некоторых регионов тоже также фильтруется - через установку корневого сертификата. Ключевые слова: InsideSystems и Ростелеком.
1кв.мм меди может без проблем пропустить 8А. Он будет конечно греться, но выделяемое тепло будет успевать отводиться. А если взять многожильный медный кабель с сечением провода 2400А/8А = 300 кв. мм (примерно 1см толщина проводящего слоя) как он себя поведет? Или тупое масштабирование здесь не работает?
Хотя если исследователи работают над подобной задачей, значит не работает. "Но почему?" - кто может объяснить?
А вот подловили) Я ошибся, конечно. По расписанию правильнее вернуть +1 00:00:30.000. И мой алгоритм вернёт, и реализации других авторов - вернут ровно тоже.
Если использовать родную реализацию Грегорианского календаря в C# и Java (javascript, php), они вам не позволят установить 60-ю секунду: автоматически приведут дату к следующему часу. На этом у некоторых в javascript основана техника определения максимальной даты в месяце: устанавливаем 0-е марта и, вуаля, получаем последний день февраля.
В моей кастомной имплементации календаря, можно установить 60-ю секунду. Но тут сработает матчер расписания, заставив сбросить на "ноль". А нулем у нас здесь будет "30".
Я про ваш бинарный поиск) У меня всегда с ним не складывалось: с первого раза без ошибок написать не могу. Хотя часто применяю. А getPrev вылез бы на тестах, которые я пока не стал делать, удовлетворившись getNext для замеров скорости.
Я предварительно погонял новый класс сравнивая с BitMap. Что хочу сказать? При интервалах свыше 10-ти, уверено начинает лидировать битмап. При интервалах от 2-х до 4-х ваш класс сильно обгоняет битмап на поиске, но чуть проигрывает на матчинге. Другое кол-во ещё не гонял.
Найти параметры, при которых можно уверенно сказать, что тут лучше битмап, а тут нет - трудно.
На производительность обоих классов влияют:
процент заполнения всего диапазона значениями (например, для "0-99,900-999" - 20%)
количество диапазонов в списке (два, как в примере выше, четыре: "1-3,50-79,100-200,800-810")
распределение ("кучкование") чисел по диапазону (если они распределены равномерно, и средняя длина пробега от одного значения до другого скажем от 3-х до 5-ти, то битмапа выигрывает)
Так что тут ситуация: "и хочется, и колется". Можно скрестить ужа с ёжом: объединить классы HashMapMatcher и BitMapMatcher. У первого O(1) на поиск и матчинг. Но ограничение по длине диапазона (чтобы уместить в одну 64-битную переменную).
Если интересно, я чуть позже опубликую на гитхабе классы, которыми измерял. Чтобы Вы могли сами проверить. А то вдруг я просчитался.
Сделал Ваш реализацию. Скоро залью на гит. По предварительным прогонам такой класс хорошо обгоняет битмап на поиске (1:4), но чуть проигрывает на матчинге (20%). Гонял для расписания миллисекунд "1-10,12-18,21-30,941-1000".
А Вы крут, если в комментариях способны написать код, который сразу работает) Я думал: концепт, а-н нет - рабочая версия) Мой почтение.
Я думал изначально реализовать подобный класс, но отказался по следующим причинам:
диапазоны должны быть упорядочены по возрастанию
диапазоны не должны пересекаться
диапазоны должны быть заданы без шага
Но с другой стороны:
их можно отсортировать, после парсинга, когда построили модель
их можно объединять, если отказаться от шага != 1
если не отказываться от шага != 1, то тогда забить на п. 2
Нужно промерить при разных комбинациях расписания: процент заполнения, степень покрытия и "кучкования" значений. Найти оптимальные значения, при которых данный класс станет выгоднее.
Для этого есть генератор (см. конец статьи). Судя по бенчмаркам - генерирует следующее значение за 100нс. Но это, повторюсь, на моем компьютере и это Java, а не ассемблер.
Обратите внимание, что getNextEvent работает в среднем за 500нс, а next() у генератора, использующего точно такой же алгоритм - за 100нс.
Очередное подтверждение, что производительность сильно падает на Григорианском календаре, который я уже и так оптимизировал, пожертвовав некоторой точностью.
Я попробую и позже опубликую в проекте CronHabrDemo. На всякий случай, опишите подробнее предлагаемую Вами структуру. Чтобы у нас не было расхождений во взаимопонимании.
Но у меня есть подозрение, что битмап снова выиграет, ибо упорядоченный массив диапазонов заставит "скакать" по памяти, что сильно сказывается на производительности.
Чтобы поломать алгоритм. Не все играют по правилам. Особенно взломщики.
это уже не будет стандартная хеш-функция
Вот с этого и начинаются взломы. Попытка что-то применить не стандартным образом, неожиданно для его разработчика. Например, с этого и начинались исследования криптоаналитиков по поиску механизмов генераций коллизий для SHA-1. Сначала, для специально подобранных векторов инициализаций удавалось найти коллизии. Потом уже был вскрыт общий алгоритм целенаправленной выработки коллизий для стандартной SHA-1. По этим фактам есть соответствующие публикации.
Ниже уже ответил про Ваше заблуждение относительно невозможности вызвать функцию с числом аргументов, превышающих её определение.
Это заявка на отдельную статью) Разрешите, я кратко?
После первичной инициализации генератора "Вихрь Мерсенна", получение следующих 624 чисел сводится к 6 сдвиговым и логическим операциям на число. Через каждые 624 числа (начиная с нулевого), идет "перемешивание", влекущее к необходимости выполнить 227 раундов по 6 логических и сдвиговых операций, и 397 раундов по 5 логических и сдвиговых операций. Итого: 3347 операцийчерез каждые 624 числа. Это справедливо для "стандартных" (рекомендуемых) параметров алгоритма.
Теперь SHA-2 (256 бит). В основном цикле производится 64 раунда по 26 арифметико-логических и сдвиговых операций. Перед основным циклом производится 48 раундов по 13 арифметико-логических и сдвиговых операций. Итого: 2288 операций на каждый хеш.
Таким образом, при выдаче каждого n*624 (n = 0, 1, ...) числа, Вихрь Мерсенна будет примерно в 1,5 раза медленнее SHA-2 (256), а при выдаче остальных чисел - Вихрь будет примерно более чем в 300 раз быстрее.
Андрей Львович, а я не агитирую Вас немедленно всё бросить, и переписать ту часть протокола, которая к протоколу-то не сильно относится. Ага, особенно под влиянием изречений неизвестного сетевого анонимуса. Я не критикую, а интересуюсь: почему было выбрано именно такое решение. И дело не вычислительной трудоёмкости. Я ожидал услышать от Вас что-то в духе: "мы проанализировали различные схемы генерации ключевой информации, и пришли к выводу, что криптостойкость (иные требуемые параметры: скорость, предсказуемость) предложенной схемы, превышает криптостойкость классических схем генерации на базе ГПСЧ. Вот анализ здесь, и здесь...".
Что ж, Вы уже достаточно ответили по данному вопросу. Думаю, эту ветку можно закрыть.
Всё верно. Поэтому сразу же отбрасывал такое "решение" в корзину. Вы высказали интерес к моим соображениям по поводу "альтернативных" реализаций ("Мне интересно"). И я честно привел, сразу оговорившись, что нигде не утверждал, что знаю "как лучше", а писал: "...тут же приходит на ум...". При этом не утверждал категорически, что не существуют кейсы (о которых сам не знаю), где ваш протокол был бы хорош и не мог бы заменён на иные существующие.
Ну хорошо. Как поступать, согласно вашему протоколу, если ключ одного из участников (x_i, P_i) будет скомпрометирован?
Включение/исключение приводит к замене группового общедоступного ключа, а также персональных секретов участников. При исключении необходимо отказаться от ранее использованного долговременного секрета β...
Если я правильно понял Ваш вопрос.
В протоколе, который проектирую, само явление "как ввод логина/пароля" на веб-сайте уходит "в отставку". Аутентификацию предлагается проводить через дополнительные HTTP-заголовки по протоколу SRP.
Сервер себя идентифицирует не по доменному имени (как это принято в SSL), а по идентификатору, который выбирает сам. Как результат, появляется понятие не сайта, а "приложения", которое может быть распределено по нескольким доменам, или, наоборот, несколько приложений (даже от разных вендоров) сконцентрироваться в пределах одного домена.
Конечно, в такой схеме любой сайт, заманивший пользователя к себе, может попытаться использовать чужой идентификатор и потребовать "авторизоваться" (аналог фишина в моей версии протокола). Но т.к. SRP требует от сторон взаимной проверки, сервер злоумышленника не сможет прикинуться легальным, и клиент это выявит (пп. 9-12 протокола).
Не получится и проксировать запросы через себя, подменяя информацию. Хотя прослушивать сможет. Но сам акт авторизации никак не выдает ключевую информацию, и уж тем более пароль. Обратите внимание, что там на первом этапе вообще передаются случайные числа, из которых получить исходный ключ или верификатор клиента невозможно, даже если решить задачу дискретного логарифма.
Кроме того, в дальнейшем полученный сессионный ключ предлагается использовать для подписи запросов клиента и сервера. Тем самым мешая проксирующему серверу "навязать" неверные данные.
Вообще, я предлагаю стандартизировать большинство процессов, связанных с аутентификацией (регистрация, замена ключей, логин/логаут, предоставление/отзыв доступов сторонним интернет-приложениям, резервный план восстановления учеток и другое), освободив разработчиков от это "рутины". Но это тема большой отдельной статьи.
Ага. Это полбеды. А ещё есть такая штука, как StoneGate, у которой заявлено "инспекция HTTPS-трафика со скоростью 40Мб/с". И она вскрывает трафик без всяких предварительных установок сертификатов. Автору самому "больно щелкнули по носу", когда он усомнился в таком. Так что я сейчас немного настороженно отношусь к т.н. гражданской криптографии.
И кстати, интернет в российских школах некоторых регионов тоже также фильтруется - через установку корневого сертификата. Ключевые слова: InsideSystems и Ростелеком.
Это в дополнение к Вашему комментарию.
Deleted
А вот вопрос к специалистам.
1кв.мм меди может без проблем пропустить 8А. Он будет конечно греться, но выделяемое тепло будет успевать отводиться. А если взять многожильный медный кабель с сечением провода 2400А/8А = 300 кв. мм (примерно 1см толщина проводящего слоя) как он себя поведет? Или тупое масштабирование здесь не работает?
Хотя если исследователи работают над подобной задачей, значит не работает. "Но почему?" - кто может объяснить?
Ветка list-matcher https://github.com/KaminskyIlya/HabrCronDemo/tree/list-matcher
А вот подловили) Я ошибся, конечно. По расписанию правильнее вернуть +1 00:00:30.000. И мой алгоритм вернёт, и реализации других авторов - вернут ровно тоже.
Если использовать родную реализацию Грегорианского календаря в C# и Java (javascript, php), они вам не позволят установить 60-ю секунду: автоматически приведут дату к следующему часу. На этом у некоторых в javascript основана техника определения максимальной даты в месяце: устанавливаем 0-е марта и, вуаля, получаем последний день февраля.
В моей кастомной имплементации календаря, можно установить 60-ю секунду. Но тут сработает матчер расписания, заставив сбросить на "ноль". А нулем у нас здесь будет "30".
Я про ваш бинарный поиск) У меня всегда с ним не складывалось: с первого раза без ошибок написать не могу. Хотя часто применяю. А getPrev вылез бы на тестах, которые я пока не стал делать, удовлетворившись getNext для замеров скорости.
Я предварительно погонял новый класс сравнивая с BitMap. Что хочу сказать? При интервалах свыше 10-ти, уверено начинает лидировать битмап. При интервалах от 2-х до 4-х ваш класс сильно обгоняет битмап на поиске, но чуть проигрывает на матчинге. Другое кол-во ещё не гонял.
Найти параметры, при которых можно уверенно сказать, что тут лучше битмап, а тут нет - трудно.
На производительность обоих классов влияют:
процент заполнения всего диапазона значениями (например, для "0-99,900-999" - 20%)
количество диапазонов в списке (два, как в примере выше, четыре: "1-3,50-79,100-200,800-810")
распределение ("кучкование") чисел по диапазону (если они распределены равномерно, и средняя длина пробега от одного значения до другого скажем от 3-х до 5-ти, то битмапа выигрывает)
Так что тут ситуация: "и хочется, и колется". Можно скрестить ужа с ёжом: объединить классы HashMapMatcher и BitMapMatcher. У первого O(1) на поиск и матчинг. Но ограничение по длине диапазона (чтобы уместить в одну 64-битную переменную).
Если интересно, я чуть позже опубликую на гитхабе классы, которыми измерял. Чтобы Вы могли сами проверить. А то вдруг я просчитался.
Сделал Ваш реализацию. Скоро залью на гит. По предварительным прогонам такой класс хорошо обгоняет битмап на поиске (1:4), но чуть проигрывает на матчинге (20%). Гонял для расписания миллисекунд "1-10,12-18,21-30,941-1000".
А Вы крут, если в комментариях способны написать код, который сразу работает) Я думал: концепт, а-н нет - рабочая версия) Мой почтение.
Я думал изначально реализовать подобный класс, но отказался по следующим причинам:
диапазоны должны быть упорядочены по возрастанию
диапазоны не должны пересекаться
диапазоны должны быть заданы без шага
Но с другой стороны:
их можно отсортировать, после парсинга, когда построили модель
их можно объединять, если отказаться от шага != 1
если не отказываться от шага != 1, то тогда забить на п. 2
Нужно промерить при разных комбинациях расписания: процент заполнения, степень покрытия и "кучкования" значений. Найти оптимальные значения, при которых данный класс станет выгоднее.
В принципе, да, можно запилить.
Прошу прощения, заработался, не увидел вашу статью в потоке.
Для этого есть генератор (см. конец статьи). Судя по бенчмаркам - генерирует следующее значение за 100нс. Но это, повторюсь, на моем компьютере и это Java, а не ассемблер.
Обратите внимание, что getNextEvent работает в среднем за 500нс, а next() у генератора, использующего точно такой же алгоритм - за 100нс.
Очередное подтверждение, что производительность сильно падает на Григорианском календаре, который я уже и так оптимизировал, пожертвовав некоторой точностью.
Поддерживается. Есть, например, такой тест: "*.*.* * *:*:*.1,2,3-5,10-20/3". Посмотрите все тесты.
Для таких случаев используются HashMapMatcher и BitMapMatcher.
Допускаю, что где-то промахнулся в своих изысканиях. Не смог реализовать ваш алгоритм, ибо специфика C++.
А попробуйте, пожалуйста, такие расписания:
"*.02.29 6 12:00:00" для даты "01.01.2021 12:00:00.000" (ожидается "29.02.2048 12:00:00.000")
"*.*.27-32/2 1 12:14:34" для даты 31.01.2021 12:14:33.177 (ожидается "29.03.2021 12:14:34.000")
"*.*.20-32/5 5 12:14:34" для даты "31.01.2021 12:14:33.177" (ожидается "30.04.2021 12:14:34.000")
И померьте скорость, увеличивая начальную дату с шагом в секунду/миллисекунду/час.
Я попробую и позже опубликую в проекте CronHabrDemo. На всякий случай, опишите подробнее предлагаемую Вами структуру. Чтобы у нас не было расхождений во взаимопонимании.
Но у меня есть подозрение, что битмап снова выиграет, ибо упорядоченный массив диапазонов заставит "скакать" по памяти, что сильно сказывается на производительности.
Коллега, Вы изумительны! Прочитать по диагонали статью, до конца не разобравшись в коде, найти ошибку! Снимаю шляпу.
Исправил: ошибка была в классе LastDayOfMonthProxy:
Уже после публикации статьи, прочитывая код нашел ещё одну ошибку. Как говорил @PsyHaSTe "копипаста - зло".
Исправлю, опубликую фикс.
Чтобы поломать алгоритм. Не все играют по правилам. Особенно взломщики.
Вот с этого и начинаются взломы. Попытка что-то применить не стандартным образом, неожиданно для его разработчика. Например, с этого и начинались исследования криптоаналитиков по поиску механизмов генераций коллизий для SHA-1. Сначала, для специально подобранных векторов инициализаций удавалось найти коллизии. Потом уже был вскрыт общий алгоритм целенаправленной выработки коллизий для стандартной SHA-1. По этим фактам есть соответствующие публикации.
Ниже уже ответил про Ваше заблуждение относительно невозможности вызвать функцию с числом аргументов, превышающих её определение.
Если будете столь любезны и дадите ссылку (можно в личку), обязательно почитаю.
Это заявка на отдельную статью) Разрешите, я кратко?
После первичной инициализации генератора "Вихрь Мерсенна", получение следующих 624 чисел сводится к 6 сдвиговым и логическим операциям на число. Через каждые 624 числа (начиная с нулевого), идет "перемешивание", влекущее к необходимости выполнить 227 раундов по 6 логических и сдвиговых операций, и 397 раундов по 5 логических и сдвиговых операций. Итого: 3347 операций через каждые 624 числа. Это справедливо для "стандартных" (рекомендуемых) параметров алгоритма.
Теперь SHA-2 (256 бит). В основном цикле производится 64 раунда по 26 арифметико-логических и сдвиговых операций. Перед основным циклом производится 48 раундов по 13 арифметико-логических и сдвиговых операций. Итого: 2288 операций на каждый хеш.
Таким образом, при выдаче каждого n*624 (n = 0, 1, ...) числа, Вихрь Мерсенна будет примерно в 1,5 раза медленнее SHA-2 (256), а при выдаче остальных чисел - Вихрь будет примерно более чем в 300 раз быстрее.
Андрей Львович, а я не агитирую Вас немедленно всё бросить, и переписать ту часть протокола, которая к протоколу-то не сильно относится. Ага, особенно под влиянием изречений неизвестного сетевого анонимуса. Я не критикую, а интересуюсь: почему было выбрано именно такое решение. И дело не вычислительной трудоёмкости. Я ожидал услышать от Вас что-то в духе: "мы проанализировали различные схемы генерации ключевой информации, и пришли к выводу, что криптостойкость (иные требуемые параметры: скорость, предсказуемость) предложенной схемы, превышает криптостойкость классических схем генерации на базе ГПСЧ. Вот анализ здесь, и здесь...".
Что ж, Вы уже достаточно ответили по данному вопросу. Думаю, эту ветку можно закрыть.
Вы предложили решение, ущербность которого
Всё верно. Поэтому сразу же отбрасывал такое "решение" в корзину. Вы высказали интерес к моим соображениям по поводу "альтернативных" реализаций ("Мне интересно"). И я честно привел, сразу оговорившись, что нигде не утверждал, что знаю "как лучше", а писал: "...тут же приходит на ум...". При этом не утверждал категорически, что не существуют кейсы (о которых сам не знаю), где ваш протокол был бы хорош и не мог бы заменён на иные существующие.
Ну хорошо. Как поступать, согласно вашему протоколу, если ключ одного из участников (x_i, P_i) будет скомпрометирован?
На многих языках программирования это вполне нормальный трюк)
Но это уже оффтопик, не имеющий отношение к начальной теме)
Да. Прошу меня простить, ошибся. Как Вы сказали, был не аккуратен.
Уже. Проверил. Увидел где ошибся.