По вашему запросу ничего не найдено :(
Убедитесь, что запрос написан правильно, или посмотрите другие
наши статьи:
Последние два года выдались для роутеров MikroTik нелегкими. Они подвергались сканированию, уводились в ботнеты, майнили крипту без ведома хозяев и почти всё это стало возможным благодаря всего одной уязвимости в сервисе www, а точнее – незащищённому открытому 80 порту. (Используется для настройки роутера через web интерфейс)
Мы беспокоимся о своих читателях, поэтому хотим ещё раз предупредить всех обладателей роутеров MikroTik о данной проблеме.
Впервые, информация о том, что в роутерах MikroTik присутствует критическая уязвимость, позволяющая злоумышленнику исполнить произвольный код в случае успешной эксплуатации, появилась на весьма специфичном ресурсе – WikiLeaks, в рамках серии публикаций об средствах, которыми пользуется ЦРУ для взлома электронных девайсов, под названием Vault 7. Эксплоит получил название Chimay Red, точно также называется одно бельгийское пиво, вкусное или нет - не знаем.
Итак, давайте знакомиться – Chimay Red, cheers, друзья!
Вот лишь некоторый список того, на что способен данный эксплойт:
Удаленно выполнить код, в командной строке роутера. Например, перезагрузить устройство без Вашего ведома;
Извлекать пользовательские логины и пароли;
На моделях роутеров с жидкокристаллическим экраном, можно вывести на него какое-нибудь сообщение;
Скрыть все логи устройства;
И даже - заставить роутер играть какую-нибудь монофоническую мелодию. Например, из Super Mario :)
Согласитесь, не очень приятно знать, что кто-то может заставить Ваш роутер "петь" Super Mario.
В общем, для тех, кто не хочет читать дальше сообщаем - MikroTik выпустил прошивки чтобы закрыть эту уязвимость, поэтому если версия RouterOS у Вас ниже 6.37.5 или 6.38.5, то срочно обновитесь!
А мы продолжаем. Благодаря уязвимости Chimay Red, позже стало возможным создание вредоносных инструментов для проведения ряда атак.
VPNfilter
Вредонос, который обнаружило подразделение кибербезопасности Cisco Talos. Помимо роутеров MikroTik, данный вредонос бил и по другим устройствам класса SOHO. Сначала было непонятно, как вредоносные файлы загружались на роутеры MikroTik, однако позже выяснилось, что всему виной может быть уязвимость в сервисе www.
Несмотря на то, что вредонос получил название VPNfilter, ничего общего с технологией VPN он не имеет.
Что умеет VPNfilter:
Подслушивать ваш трафик;
Внедрять вредоносный контент в трафик, проходящий через роутер, и, с помощью этого, устанавливать вредоносное ПО на подключенные устройства;
Тупо выводить роутер из строя;
Извлекать пользовательские пароли и другую чувствительную информацию;
Устанавливать соединения в анонимные сети TOR к командному серверу и делать роутер частью ботнет сети.
Как понять, что Ваше устройство инфицировано:
Ваш роутер устанавливает неидентифицированные соединения по управляющим портам ко внешним неизвестным ресурсам;
Проверить можно на вкладке IP → Firewall → Connections. Там не должно быть соединений от вашего роутера к публичным IP адресам по портам удаленного администрирования, о которых Вы не знаете.
Допустим, внешний адрес Вашего роутера – 91.191.191.91
На Вашем роутере появились следующие директории:
var/run/vpnfilterm
/var/run/vpnfilterw
var/run/torr
var/run/tord
Ваш роутер самопроизвольно отключается, перезагружается, появляются изменения конфигурации, которые Вы не вносили
Как защитить устройство от вредоноса или удалить его, если оно уже заражено:
Итак, если Вы давно не обновлялись и используете старую версию RouterOS, а также у вас открыт доступ по 80 порту из Интернета, то ваше устройство может быть заражено.
Перезагрузить устройство. Однако, данная мера может не помочь, т.к вредонос способен "пережить" перезагрузку. Так что надёжнее будет сделать сброс к заводским настройкам. Предварительно, сохраните конфигурацию устройства
Обновить версию RouterOS на выпущенную после марта 2017 года. Исправления появились в 6.38.5, 6.37.5. Рекомендуется установить последнюю актуальную версию и патчи для Вашего устройства
Сменить пароль, особенно на встроенных профилях (admin). По возможности, отключите устройство от публичной сети, выполняя данный шаг
Настроить Firewall для сервиса www (порт 80). Лучше всего будет запретить использование данного сервиса и обращения к порту 80 из Интернета. Однако, если это невозможно, то необходимо разрешить доступ только с доверенных адресов.
Данный вредонос поразил такое большое количество устройств и вызвал такой большой резонанс, что компания Symantec даже разработала специальный ресурс, позволяющий определить, заражён ли Ваш роутер VPN filter'ом. Инструмент может проверить Ваш роутер на наличие плагина ssler, который вредонос устанавливает на определенной стадии заражения:
Symantec
Просто перейдите по ссылке компьютера, находящегося за роутером, который Вы хотите проверить и нажмите Run VPNfilter Check.
Даже если проверка не выявит признаков заражения ssler, роутер всё равно может быть заражён другими модулями VPNfilter.
Ботнет
Немного иначе обстоят дела с другим "вредоносом", а точнее целым ботнетом - Hajime. Этот ботнет уже попадал в поле зрения исследователей, когда захватывал в свои ряды умные устройства (IoT), однако, в марте 2018 года, ботнет резко переключился на роутеры MikroTik. Это подтверждается тем, что ботнет начал сканировать рандомные подсети по 80 (www) и 8291 (WinBox) порту. Сканирование порта 8291, говорит от том, что оно направлено именно на оборудование MikroTik.
После успешной идентификации устройства, ботнет применял ряд эксплоитов, чтобы ввести его в свои ряды.
Дальше дело пока не заходило, ботнет Hajime пока не был замечен ни в массированных DDoS атаках, ни даже в рассылке спама. Есть даже предположение, что автор Hajime - это добрый хакер (white hat), который укрепляет безопасность систем. Исследователи Symantec нашли в заражённых устройствах зашифрованное сообщение именно такого содержания.
Так или иначе, ещё раз рекомендуем установить последние обновления для Ваших роутеров и регулярно следить, чтобы прошивка была актуальной.
Если Вы подозреваете, что Ваше устройство заражено или просто хотите это проверить, то предлагаем воспользоваться следующим способом.
В интернете есть множество открытых ресурсов, которые следят за вредоносной активностью в сети и ведут соответствующие записи.
Такие ресурсы как:
VirusTotal
AbusedIP
Spamhaus
IBM-X Threat
Cisco Talos
Помогут Вам определить, замечался ли Ваш публичный IP адрес во вредоносной активности.
Просто введите его в строку поиска на соответствующем ресурсе и посмотрите результат.
Данный способ актуален только если у вас статический IP адрес или, если он динамический, то Вы точно знаете когда он менялся.
Алгоритм
– это набор четко сформулированных инструкций, который применяется для решения конкретной задачи. Эти задачи вы можете решать любым удобным для вас способом.
Это значит, что ваш метод, который вы используете для решения задачи, может отличаться от моего, но при этом мы оба должны получить один и тот же результат.
Так как способ решения одной и той же задачи может быть не один, то должен существовать и способ оценить эти решения или алгоритмы с точки зрения оптимальности и эффективности (время, которое требуется для запуска/выполнения вашего алгоритма, и общий объем потребляемой памяти).
Этот этап довольно важный для программистов. Его цель - помочь убедиться, что их приложения работают должным образом, и помочь написать чистый программный код.
И вот здесь на первый план выходит обозначение «О большое». «О большое» - это метрика, которая определяет эффективность алгоритма. Она позволяет оценить, сколько времени занимает выполнение программного кода с различными входными данными, и измерить, насколько эффективно этот программный код масштабируется по мере увеличения размера входных данных.
Что такое «О большое»?
«О большое» показывает сложность алгоритма для наихудшего случая. Для описания сложности алгоритма здесь используются алгебраические выражения.
«О большое» определяет время выполнения алгоритма, показывая, как будет меняться оптимальность алгоритма по мере увеличения размера входных данных. Однако этот показатель не расскажет вам о том, насколько быстро работает ваш алгоритм.
«О большое» измеряет эффективность и оптимальность алгоритма, основываясь на временной и пространственной сложности.
Что такое временная и пространственная сложность?
Один из самых основных факторов, который влияет на оптимальность и эффективность вашей программы – это оборудование, ОС и ЦП, которые вы используете.
Однако при анализе оптимальности алгоритма это не учитывается. Куда важнее учесть временную и пространственную сложность как функцию, которая зависит от размера входных данных.
Временная сложность алгоритма – это то, сколько времени потребуется для выполнения алгоритма в зависимости от размера входных данных. Аналогично пространственная сложность – это то, сколько пространства или памяти потребуется для выполнения алгоритма в зависимости от размера входных данных.
В данной статье мы рассмотрим временную сложность. Эта статья станет для вас своего рода шпаргалкой, которая поможет вам понять, как можно рассчитать временную сложность для любого алгоритма.
Почему временная сложность зависит от размера входных данных?
Для того, чтобы полностью понять, что же такое «зависимость от входных данных», представьте, что у вас есть некий алгоритм, который вычисляет сумму чисел, основываясь на ваших входных данных. Если вы ввели 4, то он сложит 1+2+3+4, и на выходе получится 10; если вы ввели 5, то на выходе будет 15 (то есть алгоритм сложил 1+2+3+4+5).
const calculateSum = (input) => {
let sum = 0;
for (let i = 0; i <= input; i++) {
sum += i;
}
return sum;
};
В приведенном выше фрагменте программного кода есть три оператора:
Давайте посмотрим на картинку выше. У нас есть три оператора. При этом, так как у нас есть цикл, то второй оператор будет выполняться, основываясь на размере входных данных, поэтому, если на входе алгоритм получает 4, то второй оператор будет выполняться четыре раза. А значит, в целом алгоритм выполнится шесть (4+2) раз.
Проще говоря, алгоритм будет выполняться input+2 раза; input может быть любым числом. Это говорит о том, что алгоритм выражается в терминах входных данных. Иными словами, это функция, которая зависит от размера входных данных.
Для понятия «О большое» есть шесть основных типов сложностей (временных и пространственных):
Постоянное время: O1
Линейное время: On
Логарифмическое время: On log n
Квадратичное время: On2
Экспоненциальное время: O2n
Факториальное время: On!
Прежде чем мы перейдем к рассмотрению всех этих временных сложностей, давайте посмотрим на диаграмму временной сложности «О большого».
Диаграмма временной сложности «О большого»
Диаграмма «О большого» - это асимптотические обозначение, которое используется для выражения сложности алгоритма или его оптимальности в зависимости от размера входных данных.
Данная диаграмма помогает программистам определить сценарий наихудшего случая, а также оценить время выполнения и объем требуемой памяти.
Следующий график иллюстрирует сложность «О большого»:
Глядя на приведенную выше диаграмму, можно определить, что O1 – постоянное время выполнения алгоритма, является наилучшим вариантом. Это означает, что ваш алгоритм обрабатывает только один оператор без какой-либо итерации. Дальше идет Olog n , что тоже является неплохим вариантом, и другие:
O1 – отлично/наилучший случай
Olog n – хорошо
On – удовлетворительно
On log n – плохо
On2, O2n, On! – ужасно/наихудший случай
Теперь вы имеете представление о различных временных сложностях, а также можете понять, какие из них наилучшие, хорошие или удовлетворительные, а какие плохие и наихудшие (плохих и наихудших временных сложностей следует избегать).
Следующий вопрос, который может прийти на ум: «какой алгоритм какую сложность имеет?» И это вполне логичный вопрос, ведь эта статья задумывалась как шпаргалка. ?
Когда ваши расчеты не зависят от размера входных данных, то это постоянная временная сложность - O1.
Когда размер входных данных уменьшается в два раза, например, при итерации, обработке рекурсии и т.д., то это логарифмическая временная сложность - Olog n .
Когда у вас один цикл в алгоритме, то это линейная временная сложность - On.
Когда у вас есть вложенные циклы, то есть цикл в цикле, то это квадратичная временная сложность - On2.
Когда скорость роста удваивается при каждом добавлении входных данных, то это экспоненциальная временная сложность - O2n.
Давайте перейдем к описанию временных сложностей. Для каждой будут приведены примеры. Отмечу, что в примерах я использовал JavaScript, но если вы понимаете принцип и что из себя представляет каждая временная сложность, то не имеет значения, какой язык программирования вы выберите.
Примеры временных сложностей «О большого»
Постоянное время: O1
Когда алгоритм не зависит от размера входных данных n, то говорят, что он имеет постоянную временную сложность порядка O1. Это значит, что время выполнения алгоритма всегда будет одним и тем же, независимо от размера входных данных.
Допустим, что задача алгоритма – вернуть первый элемент массива. Даже если массив состоит из миллиона элементов, временная сложность будет постоянной, если использовать следующий подход для решения задачи:
const firstElement = (array) => {
return array[0];
};
let score = [12, 55, 67, 94, 22];
console.log(firstElement(score)); // 12
Приведенная выше функция выполняет лишь один шаг, а это значит, что функция работает за постоянное время, и ее временная сложность O1.
Однако, как уже было сказано, разные программисты могут найти разные способы решения задачи. Например, другой программист может решить, что сначала надо пройти по массиву, а затем уже вернуть первый элемент:
const firstElement = (array) => {
for (let i = 0; i < array.length; i++) {
return array[0];
}
};
let score = [12, 55, 67, 94, 22];
console.log(firstElement(score)); // 12
Это просто пример – вряд ли кто-то будет решать эту задачу таким способом. Но здесь уже есть цикл, а значит алгоритм не будет выполняться за постоянное время, здесь в игру вступает линейное время с временной сложностью On.
Линейное время: On
Линейная временная сложность возникает, когда время работы алгоритма увеличивается линейно с размером входных данных. Когда функция имеет итерацию по входному значению n, то говорят, что она имеет временную сложность порядка On.
Допустим, алгоритм должен вычислить и вернуть факториал любого числа, которое вы введете. Это значит, что если вы введете число 5, то алгоритм должен выполнить цикл и умножить 1·2·3·4·5, а затем вывести результат – 120:
const calcFactorial = (n) => {
let factorial = 1;
for (let i = 2; i <= n; i++) {
factorial = factorial * i;
}
return factorial;
};
console.log(calcFactorial(5)); // 120
Тот факт, что время выполнения алгоритма зависит от размера входных данных, подразумевает наличие линейной временной сложности порядка On.
Логарифмическое время: Olog n
Это чем-то похоже на линейную временную сложность. Однако здесь время выполнения зависит не от размера входных данных, а от их половины. Когда размер входных данных уменьшается на каждой итерации или шаге, то говорят, что алгоритм имеет логарифмическую временную сложность.
Такой вариант считается вторым сверху списка лучших, так как ваша программа работает лишь с половиной входных данных. И при всем при этом, размер входных данных уменьшается с каждой итерацией.
Отличный пример – функция бинарного поиска, которая делит отсортированный массив, основываясь на искомом значения.
Допустим, что нам надо найти индекс определенного элемента в массиве с помощью алгоритма бинарного поиска:
const binarySearch = (array, target) => {
let firstIndex = 0;
let lastIndex = array.length - 1;
while (firstIndex <= lastIndex) {
let middleIndex = Math.floor((firstIndex + lastIndex) / 2);
if (array[middleIndex] === target) {
return middleIndex;
}
if (array[middleIndex] > target) {
lastIndex = middleIndex - 1;
} else {
firstIndex = middleIndex + 1;
}
}
return -1;
};
let score = [12, 22, 45, 67, 96];
console.log(binarySearch(score, 96));
Приведенный выше программный код демонстрирует бинарный поиск. Судя по нему, вы сначала получаете индекс среднего элемента вашего массива, дальше вы сравниваете его с искомым значением и, если они совпадают, то вы возвращаете этот индекс. В противном случае, если они не совпали, вы должны определить, искомое значение больше или меньше среднего, чтобы можно было изменить первый и последний индекс, тем самым уменьшив размер входных данных в два раза.
Так как на каждой такой итерации размер входных данных уменьшается в два раза, то данный алгоритм имеет логарифмическую временную сложность порядка Olog n .
Квадратичное время: On2
Когда в алгоритме присутствуют вложенные циклы, то есть цикл в цикле, то временная сложность уже становится квадратичной, и здесь нет ничего хорошего.
Представьте, что у вас есть массив из n элементов. Внешний цикл будет выполняться n раз, а внутрениий – n раз для каждой итерации внешнего цикла, и, соответственно, общее количество итераций составит n2. Если в массиве было 10 элементов, то количество итераций будет 100 (102).
Ниже приведен пример, где сравниваются элементы для того, чтобы можно было вывести индекс, когда найдутся два одинаковых:
const matchElements = (array) => {
for (let i = 0; i < array.length; i++) {
for (let j = 0; j < array.length; j++) {
if (i !== j && array[i] === array[j]) {
return `Match found at ${i} and ${j}`;
}
}
}
return "No matches found ?";
};
const fruit = ["?", "?", "?", "?", "?", "?", "?", "?", "?", "?"];
console.log(matchElements(fruit)); // "Match found at 2 and 8"
В этом примере есть вложенный цикл, а значит, здесь будет квадратичная временная сложность порядка On2.
Экспоненциальное время: O2n
Экспоненциальная временная сложность появляется, когда скорость роста удваивается с каждым добавлением входных данных n, например, когда вы обходите все подмножества входных элементов. Каждый раз, когда единицу входных данных увеличивают на один, то количество итераций, которые выполняет алгоритм, увеличиваются в два раза.
Хороший пример – рекурсивная последовательность Фибоначчи. Допустим, дано число, и необходимо найти n-ый элемент последовательности Фибоначчи.
Последовательность Фибоначчи – это математическая последовательность, в которой каждое число является суммой двух предыдущих; первые два числа – 0 и 1. Третье число – 1, четвертое – 2, пятое – 3 и т.д. (0, 1, 1, 2, 3, 5, 8, 13, …).
Соответственно, если вы введете число 6, то выведется 6-й элемент в последовательности Фибоначчи – 8:
const recursiveFibonacci = (n) => {
if (n < 2) {
return n;
}
return recursiveFibonacci(n - 1) + recursiveFibonacci(n - 2);
};
console.log(recursiveFibonacci(6)); // 8
Приведенный выше алгоритм задает скорость роста, которая удваивается каждый раз, когда добавляются входные данные. А значит, данный алгоритм имеет экспоненциальную временную сложность порядка O2n.
Заключение
Из данной статьи вы узнали, что такое временная сложность, как определить оптимальность алгоритма с помощью «О большого», а также рассмотрели различные временные сложности с примерами.
Почитайте предыдущую статью про безопасность передачи данных.
Некоторые из самых ранних криптографических систем включали обертывание бумагой цилиндра определенного размера. Цилиндр должен был каким-то образом переноситься между двумя участниками зашифрованной связи, чтобы противник не захватил его. В более поздние годы блоки ключей физически переносились между двумя конечными точками зашифрованной системы. Некоторые из них были организованы таким образом, чтобы определенная страница использовалась в течение определенного периода времени, а затем вырывалась и уничтожалась, заменена новой страницей на следующий день. Другие были разработаны таким образом, чтобы каждая страница в блокноте использовалась для шифрования одного сообщения, после чего страница вырывалась и заменялась одноразовым блокнотом.
Концепция одноразового блокнота была перенесена в современный мир с системами аутентификации, которые позволяют пользователю создавать код, который используется один раз, а затем отбрасывается, чтобы быть замененным новым кодом в следующий раз, когда пользователь попытается аутентифицироваться. Любая система, использующая код, который используется один раз, по-прежнему называется одноразовым блокнотом (one-time pad).
В современном мире есть другие способы обмена криптографическим материалом, будь то использование общего секретного ключа или получение закрытого ключа.
Во многих случаях в криптографии легче объяснить, как что-то работает, на тривиальных примерах. В следующих пояснениях Фаина и Дима будут двумя пользователями, которые пытаются обмениваться защищенной информацией, причем Фаина является инициатором и отправителем, а Дима - получателем.
Обмен публичными ключами
Фаина хотела бы отправить сообщение Диме таким образом, чтобы его мог прочитать только Дима. Для этого ей нужен открытый ключ Димы (помните, что у нее не должно быть доступа к закрытому ключу Димы). Где она может получить эту информацию? Она могла:
Спросить об этом у Димы напрямую. Это может показаться простым, но в реальной жизни это может быть очень сложно. Как, например, она может быть уверена, что действительно общается с Димой?
Найти открытый ключ Димы в открытой базе данных ключей (на сервере ключей). Опять же, это кажется простым, но как она узнает, что нашла нужный ключ или кто-то не разместил ложный ключ для Димы на этом конкретном сервере?
Эти две проблемы можно решить с помощью какой-то системы репутации. Например, в случае открытого ключа Дима может попросить нескольких своих друзей, которые хорошо его знают, подписать его открытый ключ, используя свои закрытые ключи. Их подпись на его открытом ключе, по сути, гласит: "Я знаю Дмитрия, и я знаю, что это его открытый ключ". Фаина может изучить этот список друзей, чтобы определить, кому из них она может доверять. Основываясь на этом исследовании, Фаина может определить, что она либо верит, что этот конкретный ключ является ключом Димы, либо нет.
В этой ситуации Фаина сама решает, сколько и какого рода доказательств она примет. Должна ли она, например, признать, что ключ, который у нее есть, на самом деле принадлежит Диме, потому что:
Она напрямую знает одного из друзей Димы и верит, что этот третий человек скажет ей правду.
Она знает кого-то, кто знает одного из друзей Димы, и доверяет своему другу, чтобы он рассказал ей правду о друге Димы, и, следовательно, доверяет другу Димы рассказать правду о Диме и его ключе.
Она знает нескольких человек, которые знают нескольких друзей Димы, и принимает решение доверять этому ключу Димы, основываясь на свидетельствах нескольких человек.
Такая система называется паутиной доверия. Общая идея заключается в том, что доверие имеет разные уровни транзитивности. Концепция транзитивного доверия несколько противоречива, но идея, лежащая в основе сети доверия, заключается в том, что, если вы получаете достаточно доказательств, вы можете создать доверие в паре человек/ключ. Примером такого рода паутины доверия является система Pretty Good Privacy, где люди встречаются на конференциях, чтобы перекрестно подписывать ключи друг друга, создавая паутину транзитивных доверительных отношений, на которые можно положиться, когда их общение переходит в сферу только электронных.
Другой вариант - владелец сервера ключей может каким-то образом провести расследование в отношении Дмитрия и определить, действительно ли он тот, кем он себя выдает, и действительно ли это его ключ. Самый яркий пример такого решения в "реальном мире" - это нотариус. Если вы подписываете документ перед нотариусом, он проверяет наличие какой-либо формы удостоверения личности (подтверждающей, кто вы), а затем наблюдает, как вы физически подписываете документ (проверяя ваш ключ).
Этот вид проверки называется центральным источником доверия (или аналогичным - хотя в нем почти всегда есть слово "централизованный") или инфраструктурой открытого ключа (Public Key Infrastructure -PKI). Решение зависит от доверия Фаины процессу и честности централизованного хранилища ключей.
Обмен закрытыми ключами
Учитывая, что криптография с симметричным ключом обрабатывается намного быстрее, чем криптография с открытым ключом, в идеале вы хотели бы зашифровать любые давно существующие или большие потоки с использованием симметричного общего секретного ключа. Но, если не считать физического обмена ключами, как можно обмениваться одним закрытым ключом между двумя устройствами, подключенными по сети? Рисунок 1 демонстрирует это.
На рисунке выше:
Предположим, А начинает процесс. A зашифрует одноразовый номер, случайное число, которое используется один раз в процессе, а затем выбрасывается (по сути, одноразовый номер представляет собой форму одноразового блокнота), используя открытый ключ B. Поскольку одноразовый номер был зашифрован с помощью открытого ключа B, теоретически только B может расшифровать одноразовый номер, поскольку только B должен знать закрытый ключ B.
B, после расшифровки одноразового номера, теперь отправит новый одноразовый номер в A. Он может включать исходный одноразовый номер A или исходный одноразовый номер A плюс некоторая другая информация. Дело в том, что A должен точно знать, что исходное сообщение, включая одноразовый номер A, было получено B, а не какой-либо другой системой, действующей как B. Это обеспечивается B, включая некоторую часть информации, которая была зашифрована с использованием его открытого ключа, поскольку B - единственная система, которая могла его расшифровать.
A и B, используя одноразовые номера и другую информацию, обмениваемую до этого момента, вычисляют закрытый ключ, который затем используется для шифрования / расшифровки информации, передаваемой между двумя системами.
Описанные здесь шаги несколько наивны. Есть лучшие и более безопасные системы, такие как протокол Internet Key Exchange (IKE).