Любитель головоломок

Джеральд Селби всегда любил загадки: там, где другие видели лишь шум, он стремился найти порядок и гармонию. Работая на фабрике Kellogg's по производству овсяных хлопьев, он занимался анализом материалов для увеличения срока годности продукции. Однажды, изучая хлопья других компаний, Джерри наткнулся на странную последовательность символов на обороте коробки General Mills. Вместо даты и фабрики-производителя там был отпечатан загадочный код. Джерри решил расшифровать его: взяв несколько коробок завтраков Kellogg's и General Mills, он начал сравнивать их влажность, сообразив, что хлопья с примерно одинаковой влажностью должны иметь близкие даты производства. Делая записи на бумаге, он выявил некоторые закономерности. Вскоре ему удалось расшифровать всё, что позволило определить место, дату и время изготовления. В более агрессивной сфере бизнеса «взлом» секретов конкурентов мог бы обернуться огромной выгодой, но не в производстве овсяных хлопьев, поэтому руководство восприняло его открытие без энтузиазма.

Томас Даннинг говорил: «При 300 процентах [прибыли] нет такого преступления, на которое он [капитал] не рискнул бы, хотя бы под страхом виселицы». Эти слова, сказанные в XIX веке, актуальны до сих пор. Компании, которые ведут бизнес в интернете, изобретают все более изощренные способы слежки за пользователями. 

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

Но потом появились Supercookies — довольно липкая штука, которую буквально не обойти. 

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

Как наивность разработчиков создала основы для сбора персональных данных 

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

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

В мире, где роутеры всё больше напоминают перевёрнутых пауков, чем предметы, которые бы хотелось видеть в своей гостиной, есть только несколько устройств, которые можно было бы назвать «знаменитыми». Примерами подобного могут быть AirPort Стива Джобса и mesh-роутеры Eero. Но лавры победителя в этой категории получает модель роутера Linksys, которой уже исполнилось почти 20 лет, и всё благодаря изначально незадокументированной особенности, ставшей чрезвычайно популярной у определённой пользовательской базы. Сегодня мы поговорим о сине-чёрном образце маршрутизатора беспроводного доступа — Linksys WRT54G. Именно этот роутер показал миру, на что должны быть способны беспроводные маршрутизаторы.

1988 год

Linksys был основан двумя иммигрантами из Тайваня Джени и Виктором Цао в 1988 году. По информации в профиле 2004 года на Inc., компания задумывалась как посредник между изобретателями и производителями на рынке Тайваня, но в 1990-х сама занялась производством оборудования, со временем придя к рынку домашних сетей и начав доминировать на нём в начале 2000-х.

Говоря о преимуществах платформы Android, большинство пользователей обычно называют настраиваемость, разнообразие устройств и гибкие цены. И почему-то о безопасности речи нет. Видимо, большинство просто не считает Android безопасным. Самая большая причина может быть в том, что Google Play Store — это открытая площадка: залить туда вредоносное ПО гораздо проще, чем в Apple AppStore. И это действительно случалось. Неоднократно.

Это реальная проблема. Но она связана с недостаточно жёсткой политикой Google на платформе. Хотя, похоже, это постепенно меняется. В любом случае, нужно всегда помнить о том, какому программному обеспечению следует доверять, а какому — нет. На любой платформе.

UPD: схема заменена на вариант с контейнерами из С++11, соавторы — в комментариях ниже

Доброго времени суток!
Некоторым программистам иногда приходит в голову мысль «а не изучить ли мне ассемблер?». Ведь на нем пишут самые (с некоторыми оговорками) маленькие и быстрые программы, да и охота ощутить вкус низкоуровневого программирования берет свое. Ну и для общего развития не повредит.
Мысль эта не обошла стороной и меня. Вдохновившись историей одного байта, я ринулся в бой…

… но оказалось, что найти материал по интересующей теме не так просто, как хотелось бы. Посему решено было создать на хабре пополняющийся пост-индекс статей/книг/мануалов/etc. об этом, несомненно, великом языке.
Под катом находится, собственно, список с краткими комментариями, разбитый по категориям.

UPD
В список начали добавляться ресурсы по программингу микроконтроллеров.

Вдохновленная Shifticida (32 байта) и Самой маленькой гоночной игрой в мире (58 байт), я решила сделать Самую-самую маленькую компьютерную игру для x86. Вместо одной игры получились три. Увы, они не такие крутые, как гоночки, но зато они занимают всего по 30 байт каждая.

IT-шники часто придумывают себе упражнения для ума, пытливый ум постоянно требует разминки. Хочу рассказать об одном из самых жестких и спорных способах – взлом специально защищенных программ-головоломок (Часто их называют crackme).

Одно из мест, где такие головоломки собраны — crackmes.de.

Здесь находятся много интересных программ, на которых можно испробовать свои силы по взлому. Никакого криминала – программы специально написаны для этой цели (так называемые crackme и reverseme);

Часто любят говорить «Все защиты можно взломать». Поковыряв некоторые из crackme вы возможно измените своё мнение.

Для тех, кто читал статью в песочнице: добавил раздел «Можно ли сделать игру меньше?».

Прочитав историю одного байта, вспомнил свою историю.

Когда я учился в школе и только начинал программировать меня очень привлекал ассемблер и оптимизация. А именно — кропотливая оптимизация, с подсчетам тактов и байтов. На летних каникулах у меня с двоюродным братом появилась идея написать самую маленькую игру в мире.

Первый прототип, размером 80 байт, был готов на следующий день. (Поскольку о контроле версий тогда я даже не догадывался, то остается верить воспоминаниям). С этого момента началась моя борьба за байты. Помню, довольно быстро размер был уменьшен до 65 (или около того), дальше каждый байт давался все с большим и большим трудом. К концу лета результат был 58 байт.

Сюжет и управление

Вы несетесь по трассе на грузовике с двумя прицепами. Слева от вас разделительная полоса, справа обочина укрытая травой. На дороге встречаются люди и деревья (может ямы). Ваша задача: не сбивать людей и не врезаться в деревья (не попадать в ямы).
Управление: стрелки влево-вправо — поворот; Esc — пауза.

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

Недавно Евгений Касперский опубликовал в своем блоге запись «Призраки вирус-оперы, или Ситхи Ассемблера», посвященную сверхкомпактным и мощным вредоносным приложениям, обнаруженным недавно, но написанным в стиле 15-летней давности. Мой возраст позволяет помнить этих парней и их блестящую работу – речь ведь не обязательно о создателях вирусов, они были лишь частью программистского сообщества, специализировавшегося на «ручном» написании кода и программировании на ассемблере. Это похоже на Джедаев и Ситхов из мира «Звездных войн» – существ, чье оружие, лазерные мечи, было крайне специфическим и, несмотря на это, воспринималось всеми остальными героями как одно из самых мощных (кроме шуток, спросите Йоду). Увы, похоже, людей, которые помнят этих мастеров-программистов, осталось трое (я, Касперский и Билл Гейтс). А если серьезно – в сегодняшнем мире, где драйвер мышки занимает 50 мегабайт, довольно трудно вообразить, на что способен хакер старой школы при совсем небольшом количестве выделенных ресурсов. Поэтому я решил показать, о чем говорит Евгений, на несколько ином примере – а вы уж решайте, насколько плохи новости об «олдскульных» авторах заразы.

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

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

В конце 2008 года на тогда ещё небольшую петербуржскую компанию вышел один западный медиахолдинг примерно так:
— Это вы там упоролись по хардкору и приспособили SSE-инструкции для реализации кода Рида-Соломона?
— Да, только мы не…
— Да мне пофиг. Хотите заказ?

Проблема была в том, что видеомонтаж требовал адовой производительности, и тогда использовались RAID-5 массивы. Чем больше дисков в RAID-5 — тем выше была вероятность отказа прямо во время монтажа (для 12 дисков — 6%, а для 36 дисков — уже 17-18%). Дроп диска при монтаже недопустим: даже если диск падает в хайэндовой СХД, скорость резко деградирует. Медиахолдигу надоело с криком биться головой о стену каждый раз, и поэтому кто-то посоветовал им сумрачного русского гения.

Много позже, когда наши соотечественники подросли, возникла вторая интересная задача — Silent Data Corruption. Это такой тип ошибок хранения, когда на блине одновременно меняется и бит в основных данных, и контрольный бит. Если речь о видео или фотографии — в целом, никто даже не заметит. А если речь про медицинские данные, то это становится диагностической проблемой. Так появился специальный продукт под этот рынок.

Ниже — история того, что они делали, немного математики и результат — ОС для highload-СХД. Серьёзно, первая русская ОС, доведённая до ума и выпущенная. Хоть и для СХД.

1 августа в офисе Яндекса, открывшемся недавно в Берлине, состоялся финал нашего чемпионата по программированию. И его победителем снова стал известный всем, кто интересуется спортивным программированием, Геннадий Короткевич.

Задания для Алгоритма готовила международная команда. В нее вошли программисты из России, Беларуси, Польши и США. Это специалисты МГУ имени М.В. Ломоносова, Университета Карнеги-Меллон, сотрудники Яндекса и Google. В Яндексе задачи составляли разработчики минского и киевского офиса, а потом проверяли их на своих коллегах. Один из составителей в прошлом году сам был финалистом Алгоритма. Специально для Хабрахабра мы разобрали с авторами все задачи. Кстати, несмотря на то, что соревнование завершено, вы можете попробовать себя в вирутальном контесте.



На победу претендовали многие финалисты. Среди них были победители и призеры АСМ ICPC и TopCoder Open, разработчики Google и Facebook. В финальном раунде сражались призёры Алгоритма-2013 Евгений Капун и Ши Бисюнь, чемпион АСМ ICPC Михаил Кевер, а также один из самых титулованных спортивных программистов мира Пётр Митричев. В этом году побороться за приз решил также Макото Соэдзимо — составитель заданий для Алгоритма-2013 и администратор TopCoder Open.

Борьба за первое место разгорелась между Геннадием Короткевичем и Хосакой Кадзухиро из Токийского университета. Лучший результат — четыре задачи при 66 минутах штрафного времени — показал Короткевич, подтвердив титул чемпиона. Кадзухиро решил столько же задач, но набрал больше штрафного времени (90 минут) и занял второе место. Третье место завоевал Ван Циньши из университета Цинхуа: он решил четыре задачи при 125 минутах штрафа.

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

Некоторое время назад мы поддержали Рутокен ЭЦП в openssl, затем выпустили кроссплатформенный плагин для браузера, а теперь сделали высокоуровневую криптобиблиотеку для встраивания в С++ приложения.

Концептуально данные решения выполнены идентично: используется аппаратная реализация российских криптоалгоритмов на чипе Рутокен ЭЦП, обеспечивается поддержка цифровых сертификатов X.509, запросов на сертификаты PKCS#10, подписанных и зашифрованных сообщений CMS.

Новая библиотека пригодится тем, кто пишет «толстые клиенты», десктопные приложения, свои браузерные плагины и т.п.

Поддерживаемые устройства:

• USB-токен Рутокен ЭЦП
• Смарт-карта Рутокен ЭЦП
• Bluetooth-токен Рутокен ЭЦП
• Trustscreen-устройство Рутокен PINPad
• USB-токен Рутокен WEB (HID)

Основные сценарии применения библиотеки с примерами кода под катом.

Примечание переводчика: я заменил оригинальные обозначения сторон монеты head/tail на аверс/реверс, чтобы не вносить путаницу русскоязычными орёл/решка. На иллюстрации выше слева аверс (head), справа реверс (tail).

Спасение невозможно?

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

Вы правильно поняли из названия, что это не совсем обычное описание алгоритма JPEG (формат файла я подробно описывал в статье «Декодирование JPEG для чайников»). В первую очередь, выбранный способ подачи материала предполагает, что мы ничего не знаем не только о JPEG, но и о преобразовании Фурье, и кодировании Хаффмана. И вообще, мало что помним из лекций. Просто взяли картинку и стали думать как же ее можно сжать. Поэтому я попытался доступно выразить только суть, но при которой у читателя будет выработано достаточно глубокое и, главное, интуитивное понимание алгоритма. Формулы и математические выкладки — по самому минимуму, только те, которые важны для понимания происходящего.

Знание алгоритма JPEG очень полезно не только для сжатия изображений. В нем используется теория из цифровой обработки сигналов, математического анализа, линейной алгебры, теории информации, в частности, преобразование Фурье, кодирование без потерь и др. Поэтому полученные знания могут пригодиться где угодно.

Если есть желание, то предлагаю пройти те же этапы самостоятельно параллельно со статьей. Проверить, насколько приведенные рассуждения подходят для разных изображений, попытаться внести свои модификации в алгоритм. Это очень интересно. В качестве инструмента могу порекомендовать замечательную связку Python + NumPy + Matplotlib + PIL(Pillow). Почти вся моя работа (в т. ч. графики и анимация), была произведена с помощью них.

Внимание, трафик! Много иллюстраций, графиков и анимаций (~ 10Мб). По иронии судьбы, в статье про JPEG всего 2 изображения с этим форматом из полусотни.

Баста карапузики, кончилися танцы.

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

В статье будет показан перехват рукопожатия клиент-точка доступа, перебор паролей как с помощью ЦП, так и ГП, а кроме этого — сводная статистика по скоростям на обычных одиночных системах, кластерах EC2 и данные по разным типам современных GPU. Почти все они подкреплены моими собственным опытом.

К концу статьи вы поймёте, почему ленивый 20-значный пароль из букв a-z на пару солнц более стоек, чем зубодробительный 8-значный, даже использующий все 256 значений диапазона.

Оглавление:
1) Матчасть
2) Kali. Скрытие SSID. MAC-фильтрация. WPS
3) WPA. OpenCL/CUDA. Статистика подбора