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

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

В настоящей заметке я расскажу о том, как можно построить систему оптического распознавания структурной информации, опираясь на алгоритмы, применяющиеся в обработке изображений и их реализации в рамках библиотеки OpenCV. За описанием системы стоит активно развивающийся open source проект Imago OCR, который может быть непосредственно полезен в распознавании химических структур, однако в заметке я не буду говорить о химии, а затрону более общие вопросы, решение которых поможет в распознавании структурированной информации различного рода, например таблицы или графики.

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

После анализа подобранных паролей к LinkedIn появилась идея создать генератор паролей, совмещенный с валидатором, не допускающим легко подбирающиеся пароли. Простейшего анализа на длину, наличие специальных символов здесь не достаточно — некоторые пароли можно легко собрать из очень вероятных «кусочков» и на их перебор уходит существенно меньшее время, нежели теоретически заявленное. И гарантий, что программа-генератор не выдаст вам подобный пароль нет — случайность, она на то и случайность. Мое творение не претендует на полное решение вопроса, скорее это повод для размышлений, но оно вполне работоспособно (исходники и небольшой разбор тоже присутствуют).

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

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

В этой заметке я расскажу как написать довольно неплохого бота для Google AI Challenge. Примечательно, что сложные технологии связанные с ИИ не понадобятся, а базовая реализация умещается в тысячу строчек кода на языке C++. Сами методы в совокупности могут быть рассмотрены как некоторый Generic алгоритм, и на базе них можно построить бота, учитывающего некоторые стратегические особенности, который возможно будет играть еще лучше. В любом случае — хороший «быстрый старт» для тех, у кого пока ничего не получилось.

Продолжая мучить хеши, добытые с antichat (да кому они нужны?) не удержался от создания достаточно быстрого средства, автоматически применяющего рассмотренные в статье методы. Теперь уже в ход пошли видеокарты, и на подбор 60% паролей достаточно было перекура. При скорости перебора over 100 mpwd/s, применении гибридной техники и частотного анализа это не кажется удивительным результатом, что в общем-то наконец должно заставить пересмотреть отношение к способам хранения паролей тех, кто все еще не озаботился этим. Ниже небольшое рассуждение о примененном подходе и, конечно, сама программа.

На размышления о необходимости генерации псевдослучайных паролей меня натолкнула достаточно безрадостная статистика взлома паролей, созданных при помощи МОЗГ v1.0; однако взять какой-то первый попавшийся программный генератор паролей и с помощью него поменять все пароли — выглядит безрассудством. Я не проводил детальный анализ готовых программ-генераторов, однако расскажу некоторые достаточно простые, но познавательные факты, связанные с математикой генерации псевдослучайных чисел хорошего качества, которые позволят выбрать нужную программу самостоятельно.

Как вы уже слышали Брайан Кребс недавно проводил аудит паролей, полученных после взлома antichat.ru (сама база была получена где-то год назад и уже не актуальна!). Честно говоря, не очень понимаю чем занимались его видеокарты 18 дней, победив только 44% паролей. Мне на довольно скромном железе удалось подобрать 77% паролей за 8 часов. Исходя из таких несколько пугающих цифр, особенно для сайта тематически связанного с информационной безопасностью, у меня есть несколько рекомендаций о том какие пароли никогда не следует использовать, дабы они не были подобраны за пару минут.

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

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

В статье расскажу как достаточно быстро перечислить связные объекты на бинарном растре. Этот алгоритм мы использовали для распознавания изображений и текстов; он отличается от подобных высокой скоростью обработки (на картинках до 3200x2400, с некоторыми оговорками, он отрабатывает за миллисекунды) и доступностью в понимании (при наличии некоторых знаний C++). Отмечу, что исходная картинка будет трактоваться алгоритмом как «только для чтения» (зачем портить то, с чем могут работать другие методы), и в связи с этим, алгоритму потребуется небольшое количество дополнительной памяти. Кроме того, внешние контуры являются полезным объектом для анализа и векторизации изображений.

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

Редакционное расстояние, или расстояние Левенштейна — метрика, позволяющая определить «схожесть» двух строк — минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую. В статье излагается метод вычисления редакционного расстояния при использовании небольшого объема памяти, без существенной потери скорости. Данный подход может быть применен для больших строк (порядка 10⁵ символов, т.е. фактически для текстов) при получении не только оценки «схожести», но и последовательности изменений для перевода одной строки в другую.

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

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

Представляю программку пусть и редкой применимости, но несомненной полезности: блокировка/разблокировка клавиатуры по движению аппаратного слайдера. Соответственно и работать будет только там, где он есть, и нету сенсорного экрана (иначе я бы посоветовал S2U2). И такие девайсы еще остались, например Toshiba G500, а может еще какие другие.

Время прошло, теперь я точно знаю, что не собираюсь поддерживать проект, однако, быть может, он кому-то ещё пригодится. Речь идет о некогда относительно широко известной программе для подбора паролей по хеш-значению — UDC. Реализация хеш-функций до сих пор имеет конкурирующие по скорости показатели, а алгоритмы могут иметь академическую ценность (как демострация методов из статьи о Time-memory trade off, например).

Соответственно исходники, бинарники и окружение и вычлененный Hybrid Rainbow.

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

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

Хорошо студентам, для них чего только не придумали, и Imagine Cup и Hack Day и Chaos Constructions, и это только первое, что в голову пришло. А что же делать талантливым (или считающим себя таковыми) школьникам?

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

Под катом Вы увидите 6 мегабайт фотографий счастливых ребят и их поделий, приправленных моими отстраненными размышлениями на тему образования и обзором работ в секциях «Техника» и «Computer Science».