Забавно, но факт, как спустя многие годы мы наступаем на одни и те же грабли. И когда всё-таки наступит тот момент, когда эти сельскохозяйственные инструменты закончатся на нашем пути? Или мы, по крайней мере, начнём их замечать?

Как я уже не раз упоминал в своих статьях, меня всегда интересовали истории, хоть как-то связанные с безопасностью. Не знаю, как так получилось, но де-факто так и есть. Я, конечно, долго, а в конкретной ситуации длинно, могу рассуждать по этому поводу, но навряд ли кого-то это заинтересует. Тем более хабр — не совсем то место, где это было бы уместно.

Итак, о чём это я? Ах да, информационная безопасность. Одним из интересных аспектов проблем безопасности (причём не только информационной) всегда был и остаётся вопрос социальной инженерии. По большей части моё знакомство с этим термином произошло относительно давно, и насколько я помню, впервые я увидел это словосочетание в каком-то самопальном переводе книги Стивена Леви. Однако если этот термин рассмотреть пристальнее, то его корни уходят куда глубже. На мой немного предвзятый взгляд, более яркой иллюстрации навыков социальной инженерии, чем в незабвенных шедеврах звёзд советской журналистики о похождениях «идейного борца за денежные знаки», не существует.

Через несколько лет после прочтения «героев компьютерной революции» мне попалось «искусство обмана» Митника и Саймона тоже в достаточно отвратном переводе. Это потом, уже где-то в 2005, был издан более или менее приличный русскоязычный вариант. Сейчас не буду приводить каких-то цитат из прочитанного, но помню, что необычно было читать про поиск в мусоре каких-то «бумажек» с записанными паролями к учёткам или про наивные телефонные разводы. И всё это так и осталось бы забавными историями давно минувших дней, если бы идентичные методы не работали и сегодня. Опять же, в который раз история учит только тому, что ничему не учит, и всё свежепридуманное — это хорошо забытое «старое».

История парадоксальна и её выверты порой удивительны. Что общего у Манхэттенского проекта и компьютерных игр? 65 лет назад была продемонстрирована первая многопользовательская видеоигра с графическим интерфейсом — Tennis for Two. Это была достаточно простая для современного избалованного пользователя игра в теннис, похожая на классическую аркаду 1970-х годов, только появилась на десяток лет раньше и являлась побочным продуктом национальной лаборатории Брукхейвена. Автором игры был физик Уильям Хигинботэм.

Много лет спустя в интервью Фрэнку Ловесу он вспоминал, что в то время, работая над экспозицией, он осознал, насколько статичными было большинство научных экспонатов. Будучи главой контрольно-измерительного отдела лаборатории, он намеревался изменить это недоразумение.

Ни для кого не секрет, что современные горизонты информационной безопасности простираются далеко за границы компьютерных систем, но так было не всегда. На заре появления информационных систем вопросам безопасности уделялось не самое пристальное внимание. Естественно, что в начале большее значение имела разработка и внедрение самих систем. Упрощение и ускорение обработки и обмена информацией были в приоритете. Более того, низкая насыщенность компьютерными системами и крайне ограниченный круг допущенных к ним людей не предвещали никаких серьёзных проблем, связанных с вопросами их безопасности.

Даже спустя годы после формирования основной структуры глобальной информационной сети вопросы безопасности оставались вторичными. Однако когда на подмостки этого театра начали выходить юные дарования с чрезмерной тягой к изучению нового, мир оказался к этому не готов. Потребовалось несколько десятков лет, чтобы выявить критические слабости систем и раскрыть тонкости технологий, лежащих в фундаменте Интернета и его приложений. Если вы посмотрите на то, для чего был разработан интернет и для чего он на самом деле используется сейчас, вы увидите, что он никогда не задумывался как инструмент коммерции.

Лавинообразный рост количества интернет-компаний, который в итоге привёл к одному из самых известных экономических кризисов, помимо негативных последствий фактически послужил становлению глобальной сети. Хотя больше принято критиковать доткомовский бум, именно в это время сформировалась транспортная система глобальной сети.

Эпоха интернета в детских штанишках богата множеством историй. Многие из них послужили побудительными мотивами для самых разных вещей, но меня всегда больше всего интересовали истории, так или иначе затрагивающие вопросы безопасности. Некоторые действия, которые сегодня однозначно трактуются как преступления, не всегда были таковыми, и сегодня я расскажу историю, последствия которой навсегда изменили облик сети.

В комментариях к моей статье о вычислительной сложности игр и в личных беседах проявился явный интерес к поведенческим играм антагонистической природы, однако тут не всё так просто. Такие игры несут значительную вероятностную нагрузку и простые подходы к сложности неприменимы (прошу прощения за каламбур). Тем не менее многие игры такого характера также не раз становились предметом исследований, в результате которых были разработаны математические модели этих игр.

В сегодняшней статье речь пойдёт об игре, о которой я, к своему стыду, узнал всего лет пятнадцать назад, хотя она появилась ещё в 1986 году и стала достаточно популярной уже в середине 90-х. Сегодня найти человека, который ничего не знал бы об этой игре, практически невозможно. Я говорю о «Мафии».

«Мафия» — клубная командная психологическая пошаговая ролевая игра, созданная в 1986 году студентом МГУ Дмитрием Давыдовым, базируется на культурно-исторической теории советского психолога Л. С. Выготского. В Википедии достаточно подробно описана сама игра и её варианты, но существуют и классические правила.

В общем, различные варианты игры похожи, и все участники разделены на две конкурирующие фракции: красная команда — «мирные жители», чёрная команда — «мафия». Цель игры состоит в том, чтобы уничтожить группу противника. Игра состоит из двух последовательных фаз (дневной и ночной) и определённого набора действий. Члены мафии обладают определёнными фичами (знают друг друга, убивают ночью), тогда как «мирных жителей» больше. Оказывается, что относительно небольшое количество членов «мафии», т. е. пропорциональное квадратному корню из общего числа игроков, даёт равные шансы на выигрыш для обеих групп. Кроме того, игра сильно зависит от чётности общего числа игроков.

В одной из предыдущих статей я уже затрагивал тему IoT. В этой статье речь тоже пойдёт об этой концепции. При этом топик опять же затрагивает вопросы безопасности, но в более широком смысле.

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

Многие устройства IoT также являются частью концепции домашней автоматизации и, соответственно, в той или иной мере обладают схожими преимуществами и недостатками. Пожалуй, главной «ахиллесовой пятой» обеих концепций являются вопросы обеспечения безопасности, и если ранее до массового распространения этих технологий на безопасность как большинству пользователей, так и производителей было плевать с высокой колокольни, то сегодня эта проблема носит достаточно острый характер. В 2021 году количество устройств IoT превысило 13,8 миллиарда, и ожидается, что к 2025 году их число как минимум удвоится. Такое количество разнородных подключённых устройств и объём данных, которыми они обмениваются, заставляют нервничать многих специалистов по безопасности. Этот вопрос становится ещё более существенным, когда понимаешь, что более 90% всего трафика между устройствами IoT не зашифровано.

В результате хорошо известные угрозы и атаки, такие как распределённый отказ в обслуживании (DDoS) и «человек посередине» (Man-in-the-Middle, MitM), достаточно легко и непринуждённо применяются для компрометации систем IoT. Хотя DDoS является самой популярной атакой на системы вообще, в сфере IoT MitM может её затмить. Если первая метафорически сравнима с ударом дубиной по голове, то вторая — это укол шпагой. Атаки MitM обычно более сложны, чем другие, и их трудно идентифицировать. Обычно они включают в себя широкий спектр мероприятий, в которых злоумышленник располагается в центре коммуникации, перехватывая контроль над каналами связи.

В 2014 году профессор математики Стэнфордского университета Марьям Мирзахани в одной из своих лекций упомянула интересную математическую головоломку, но не стала давать её решение. Спустя годы появились различные вариации задачи. Однако сначала речь пойдёт о первоисточнике.

Головоломка относится к классу так называемых «бильярдных задач», изучаемых в области динамических систем. Решение текущей задачи принадлежит профессору математики университета Джонса Хопкинса Эмили Рил.

Рассмотрим квадратную комнату в плоскости XY, и пусть A («ассасин») и T («цель») — две произвольные, но фиксированные точки внутри комнаты. Предположим, что комната схожа по физическим характеристикам с бильярдным столом, так что любой «выстрел» А рикошетит от стен, причём угол падения равен углу отражения. Можно ли заблокировать любой возможный «выстрел» А в Т, разместив конечное количество аналогичных по свойствам точек («телохранителей») в комнате?

В последнее время я часто писал о вычислительной сложности, алгоритмах и моделях (например 1, 2, 3). Вычислительные модели лежат в основе вычислительной науки и не только её, и всё же немногие обладают чётким представлением о том, что такое вычислительная модель на самом деле. Это программное обеспечение? Или алгоритм? Как это связано с математическими моделями? Какие языки или обозначения подходят для описания вычислительной модели? Сделает ли ИИ вычислительные модели устаревшими? В процессе обсуждения с некоторыми товарищами сформулировалось достаточно подробное и, надеюсь, понятное описание, которое я и хотел бы представить в этой статье.

Любое научное вычисление предполагает применение одной или нескольких вычислительных моделей. Некоторые из этих моделей кажутся настолько очевидными, что иной раз трудно признать их в таком качестве. С другой стороны, некоторые модели настолько сложны, что кажутся самой сутью компьютерных наук и квинтэссенцией программного обеспечения. Существуют также разделы вычислительной науки, в частности, биоинформатика, которые делают упор на методы решения проблем, а не на модели, представляющие лежащие в их основе явления, и, как следствие, почти не затрагивают сами модели. Но модели в любом случае существуют в виде предположений об изучаемых системах, которые неявно заложены в алгоритмах решения задач.

Если свести процесс научного исследования к его основам, то он предполагает создание и итеративное совершенствование моделей, описывающих эмпирические наблюдения. Таким образом, модели и наблюдения являются основными понятиями науки. Две давние специализации многих дисциплин — это теоретик, придумывающий и совершенствующий модели, и практик, проектирующий конкретные установки для проведения наблюдений.

За последние десять лет масса технологий, имеющих хоть какое-либо отношение к информационным, претерпела массу изменений. Более того, многие сферы жизни, изначально не имеющие к IT никакого отношения, также преобразились до неузнаваемости и приобрели некий IT-шный бэкграунд. Немаловажную роль в этих процессах информатизации сыграла концепция Интернета вещей (IoT). С самого появления этой концепции было понятно, что она серьёзно повлияет на все сферы деятельности человека, экономические и социальные процессы, а спустя несколько лет после её появления технология оказалась на карандаше Национального разведывательного совета США и была занесена в список «подрывных инноваций».

По мере развития технологии IoT, ставшей устойчивой тенденцией на протяжении последних десяти лет, она наполнялась технологическим содержанием и практическими стандартами. При этом до некоторого времени комплексная информационная безопасность этой технологии вообще никого не интересовала. Если внедрялись какие-то меры безопасности, то по крайне остаточному принципу. Учитывая, что изначально никто никаких специальных стандартов для устройств IoT не разрабатывал, в основном использовали то, что было. Понятно, что «взрослые» варианты стандартов подходят для IoT не в полной мере. Требуются технологии, обладающие высокой производительностью в ограниченных средах. Устройства IoT связаны достаточно жёсткими ограничениями по питанию, памяти и вычислительным ресурсам.

Если добавить к этому ненадёжные каналы связи, каналы с потерями, сильно ограниченные полосы пропускания и крайне динамичную сетевую топологию, то становится совсем кисло.

Почти десять лет назад были описаны атаки, эксплуатирующие непреднамеренный и нежелательный побочный эффект динамической памяти с произвольным доступом (DRAM), так называемый rowhammer. За это время неоднократно появлялись новые эксплойты для повышения привилегий, так или иначе использующие этот эффект. Его особенность заключается в том, что ячейки памяти электрически взаимодействуют между собой и непроизвольно могут изменять состояние своих соседей. Проблема заключается в высокой плотности современных интегральных схем. В дальнейшем были разработаны различные аппаратные методы защиты (например, target row refresh, TRR), однако по мере того как производители внедряли средства защиты, менялись и атакующие паттерны для их обхода.

Основной «ударной» силой этих атак стал двойной шаблон double-sided hammering, использующий целенаправленную активацию двух соседствующих с «жертвой» строк DRAM. Эволюция этой идеи привела к созданию фаззера Blacksmith, рвущего все существующие средства защиты практически на всех устройствах DDR4 как тузик грелку. Хотя касательно TRR вообще всё достаточно мутно, поскольку гарантии безопасности механизмов, встроенных в эту защиту, не получилось изучить в полном объёме из-за их проприетарного характера. Существует много исследований, подвергающих сомнению заверения производителей о надёжности данной защиты.

На сегодняшний день большинство предложений по полноценной защите от rowhammer либо нецелесообразны для массового развёртывания, либо недостаточны для предотвращения любых атак подобного рода.

Недавно у rowhammer был обнаружен ещё один вектор применения. Он также напрямую касается информационной безопасности, только вот совсем с другой её стороны, и речь пойдёт о конфиденциальности.

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

Массивное распараллеливание и разделение общих задач, обеспечиваемое совместной работой простых механизмов, намного эффективнее и экономичнее использования одного более сложного. По этому поводу со времён товарища Форда ни у кого вопросов не возникает. А если посмотреть соревнования F1, то там это кажется настолько органичным, что будто по-другому и нельзя.

Важным аспектом роевых моделей является то, что управление по определению децентрализовано и распределено между членами роя, что также повышает надёжность и отказоустойчивость всей системы. Помимо этого, немаловажными качественными характеристиками таких систем являются их гибкость и масштабируемость.

Локализация является важной задачей для автономных мобильных роботов, чтобы они могли успешно перемещаться в целевые местоположения в своей среде. Обычно это делается в роботоцентрической манере, когда робот поддерживает карту с собой в центре.

Эффективность передвижения достигается за счёт алгоритмов планирования движения на основе сенсорных датчиков. При этом очень многое зависит как от оптимальности алгоритмов, так и от количества сенсорной информации (точной информации о координатах положения, угловых координатах, времени или одометрии). Среди множества алгоритмов выделяется целое семейство так называемых «алгоритмов жука», характеризующихся относительной простотой и эффективностью. В этой статье речь пойдёт именно о таком алгоритме, при котором единственным датчиком, дающим какую-то реальную информацию, является датчик интенсивности опорного сигнала, исходящего от цели.

Предположим, робот передвигается по городу, пытаясь добраться до базы. Он может перемещаться, не зная своих точных координат, и чтобы было интереснее, предположим, что никакая визуальная информация ему недоступна. В таком сеттинге существует не только неопределенность в отношении положения, но и в отношении окружающей среды. Какую информацию он мог бы использовать, чтобы добраться до цели? База посылает опорный сигнал, а у нашего героя имеется прибор, регистрирующий его интенсивность. Какова эффективная стратегия, позволяющая роботу успешно добраться до базы?

В 2015 году математик Ласло Бабай представил свой более эффективный алгоритм, решающий задачу изоморфизма графов (Graph Isomorphism, GI) за квазиполиномиальное время. На Хабре даже есть статья, освещающая это событие. Однако в дальнейшем сам учёный признал некоторую ошибочность своего подхода, что всё равно не повлияло на отношение большинства математиков к его открытию, поскольку даже получившийся вариант, решающий задачу за субэкспоненциальное время, оказался эффективнее существующих алгоритмов. Тем не менее учёный не остановился на этом и обнаружил ошибку. Опубликованные исправления алгоритма всё-таки привели к решению задачи изоморфизма за квазиполиномиальное время.

Проблема изоморфизма графов требует алгоритмов, которые могут определить, являются ли два графа структурно идентичными. На протяжении десятилетий эта задача занимала особый статус как одна из немногих естественно возникающих задач, уровень сложности которых трудно определить. Многие годы исследователи пытались выяснить, к чему она относится. Даже сейчас неизвестно, к какому классу относится задача, а абстрактно задачу рассматривают как нечто среднее — сложнее, чем P, но легче NP. Задачу из теории графов можно обобщить до общей проблемы изоморфизма, в смежных областях математики существуют идентичные задачи, например изоморфизм конечных групп.

Конфиденциальность и безопасность в сети никогда не были актуальней, чем сегодня. Компании, госслужащие и частные лица сталкиваются со всё более высокими рисками, чем когда-либо прежде. Киберпреступность, злоупотребления со стороны властных структур и банальный шпионаж процветают не только в голливудских фильмах. Финансовая информация, деанонимизация личности, коммерческие патенты или просто конфиденциальные сообщения, — каждому есть что терять, даже если ему нечего скрывать. Одним из самых популярных вариантов решения этого вопроса является использование шифрования. За последние годы PGP, а затем и OpenPGP стали стандартом почти для всех подписанных или зашифрованных электронных писем в мире.

Несмотря на то, что исследования в области постквантовой криптографии с каждым днём набирают обороты, практическое приложение полученных результатов очень лениво внедряется в реальные продукты. Во многом это связано с небезосновательными опасениями по поводу своевременности и практичности этого. Многие специалисты считают этот процесс преждевременным. Однако учёные настойчиво разрабатывают различные постквантовые приложения. Как знатный параноик и перестраховщик, я, скорее, нахожусь на стороне вторых, поскольку отчётливо представляю себе тот день, когда произойдёт технологический прорыв и в то же мгновение большинство криптографических схем прикажут долго жить, накрывшись респектабельным медным тазиком реализаций алгоритма Шора. Массовой истерии не избежать, например, как сейчас с генеративным ИИ. В отличие от тех же проблем с внезапно слишком умным ИИ, практическое приложение которого ещё не до конца осознано и варится в котле общественных мнений с явными попытками ограничения неконтролируемого развития, со скачком в квантовых вычислениях подобный номер вряд ли пройдёт. Всё, что может быть взломано, будет взломано, и мир погрузится в хаос...

Возможно, всё не так страшно, но бережёного бог бережёт, поэтому чем раньше начнут внедряться постквантовые системы, тем вероятнее шанс избежать неприятных последствий этого технологического рывка. Сегодня существует несколько подходов к реализации такой защиты. Хотя, пожалуй, самый реалистичный в ближайшем будущем подход будет основываться на криптографии на основе хэшей. Примером такой системы является схема с открытым ключом в виде хэш-дерева Меркла, разработанная ещё в 1979 году и основанная на идеях Лэмпорта и Диффи.

В предыдущей статье мы рассмотрели сложность некоторых игр и головоломок. Данная тема вызвала некоторый интерес, вот и продолжение. В комментариях некоторые читатели высказали свои пожелания, которые я постарался учесть.

В первой статье и правда по справедливому замечанию avsmal «не хватает каких-то более строгих и конкретных утверждений», но не стоит забывать, что любой даже самый нудный материал нужно стараться подать интересно. В прошлый раз я пожертвовал структурой и конкретностью в пользу читабельности и привлечения интереса к теме. Сильно «душные» статьи заходят с большим скрипом и больше отпугивают читателя.

Прежде всего, нужно отметить, что теория вычислительной сложности анализирует сложность различных алгоритмических задач, а теория вычислимости — какие проблемы могут быть решены с помощью алгоритмов. Теория сложности рассматривает проблемы, которые в принципе могут быть решены алгоритмически, и пытается установить экстремумы ресурсов, необходимых для их решения. Это важно, потому что некоторые проблемы в принципе могут быть решаемы, но требовать неосуществимого количества ресурсов.

Перед вами перевод эссе Марка Андриссена, одного из влиятельнейших людей в технологическом мире. Один из пяти пионеров Интернета, награждённых премией королевы Елизаветы в области техники за «выдающиеся достижения в инженерии, изменившие мир», по совместительству создатель Mosaic, сооснователь Netscape Communications и венчурного фонда Andreessen Horowitz по состоянию на апрель 2023 года занимающего первое место в списке венчурных компаний по версии AUM.

Наступила эра искусственного интеллекта, и люди сходят с ума. К счастью, я здесь, чтобы сообщить хорошие новости: ИИ не уничтожит мир, а, наоборот, может его спасти.

В этой статье продолжим тему решения криптографических задач с ресурса MysteryTwister. И сегодня на очереди любопытный шифр, далёким предком которого является квадрат Полибия. Мы познакомимся с трёхраздельным шифром Феликса Деластеля. Что интересно информации об этом энтузиасте  криптографии очень мало в английском и французском сегментах сети (Деластель — француз), а в русскоязычном о нём почти нет совсем, хотя наверняка человеком он был очень неординарным. Почему я так решил? Да потому, что Феликс Деластель по роду профессиональной деятельности не имел к криптографии совершенно никакого отношения, поскольку всю жизнь проработал в порту Сен-Мало и криптографией занимался факультативно. Тогда как ранее и позже криптография была уделом учёных, профессиональных военных и дипломатов. Биографических данных о нём очень мало, но одно известно точно: на рубеже XIX и XX веков Деластель написал книгу "Traite Elementaire de Cryptographie" (Базовый трактат по криптографии), в которой он описывал системы шифрования, которые создал.

В сегодняшнем мире доминирует индийско-арабская десятичная система. И эта система, принятая почти в каждом обществе, представляет собой то, что большинство людей считают «числами». Десятичная система оперирует числами, выраженными цифровой базой от 0 до 9. Но существуют значимые альтернативы, и они столь же разнообразны, как и культуры, к которым принадлежат. В 1994 году группа инуитских учащихся под руководством преподавателя изобрели новую систему счисления.

«Кактовикские цифры», названные в честь населённого пункта на Аляске, где они были созданы, выглядят совершенно иначе, чем цифры десятичной системы, и функционируют совсем по-другому. Они как нельзя лучше подходят для скоростной визуальной арифметики с использованием традиционной двадцатеричной системы устного счета инуитов.

Ранее в блоге FirstVDS уже была статья с разбором решения криптографической задачи с MysteryTwister. В этом топике разберём задачу с довольно многозначительным названием «Из России с любовью» ("From Russia with Love"). Автор задачи Sansibar.

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

Есть несколько причин смотреть на игры как на нечто большее, чем просто на развлечения. Как станет яснее по ходу дела, многие игры основаны на сложных вычислительных задачах, хотя зачастую и с более низким «входным барьером», поскольку они редко требуют наличия формального образования.