Пользователь
0,0
рейтинг
10 июня 2011 в 15:33

Разработка → Взлом матановой капчи на C# — это просто!

.NET*
В этом топике я хочу вам рассказать о взломе т.н. «матан-капчи», пример которой был представлен в недавнем топике Матановая капча на PHP — это просто!.
Прочитав статью автора об этой замечательной капче, мне захотелось написать программу для её распознавания, как говорится just for fun ;)


Начнем со стандартной подготовительной процедуры, а именно: поиска уязвимостей. Уязвимости, помеченные курсивом не используются при распознавании.

Слабые стороны:
  1. Черные символы на белом фоне.
  2. Отсутствие шумов и других артефактов (например линий).
  3. Символы никогда не пересекаются.
  4. Всегда одинаковый шрифт.
  5. Под интегралом всегда 4 слагаемых.
  6. Степени и множители состоят из одной цифры.
  7. Степени и множители находятся в диапазоне от 2 до 5.
К сильным сторонам можно отнести:
  1. Наличие нелинейных искажений.
  2. Возможное отсутствие степени или множителя x.
  3. Иногда, dx слипаются в один символ.
  4. Меняется ширина капчи.
Составим алгоритм распознавания:
  1. Получить битовое изображение капчи.
  2. Пронумеровать все символы.
  3. Найти координаты верхнего и нижнего пределов.
  4. Распознать символы, составляющие пределы, используя нейронную сеть.
  5. Найти первый символ подынтегрального выражения.
  6. Поочередно распознавая символы, двигаться вправо до последнего символа.
  7. Решить полученный интеграл.

Исходная капча




Битовое изображение


За единицу будем считать пиксель, чья яркость по цветовой модели HSB < 0.8, за ноль, соответственно >= 0.8. После этого, капча примет следующий вид:


Нумерация символов


Для того чтобы пронумеровать все символы, используем простейший рекурсивный алгоритм Flood fill для выделения связных областей по 8 направлениям.
public int FloodFill(ref int[,] source, int num, int x, int y)
{
    if (source[x, y] == -1)
    {
        source[x, y] = num;
        FloodFill(ref source, num, x - 1, y - 1);
        FloodFill(ref source, num, x - 1, y);
        FloodFill(ref source, num, x - 1, y + 1);

        FloodFill(ref source, num, x, y - 1);
        FloodFill(ref source, num, x, y + 1);

        FloodFill(ref source, num, x + 1, y - 1);
        FloodFill(ref source, num, x + 1, y);
        FloodFill(ref source, num, x + 1, y + 1);
        return ++num;
    }
    return num;
}

...

int num = 1;
for (int x = 0; x < CaptchaWidth; x++)
    for (int y = 0; y < CaptchaHeight; y++)
        num = FloodFill(ref bit, num, x, y);

Распознавание символов


Учитывая нелинейные искажения и отличающийся размер символов лучшим вариантом для их распознавания, будет искусственная нейронная сеть. Что бы немного облегчить задачу, я воспользовался бесплатной библиотекой Fast Artificial Neural Network Library. Она написана на C++, и хороша тем, что имеет интерфейсы практически под все популярные языки программирования, включая и C#.

Все символы, перед распознаванием приводятся к одному размеру: в данном случае 16px x 21px.
Таким образом, на вход нейронной сети будет подаваться массив из 336 элементов (16*21). Каждый элемент задает цвет соответствующего пикселя целым числом: 0 или 1.
Средний слой состоит из 130 нейронов. А на выходе массив из 14 элементов с вещественными значениями от 0 до 1, соответствующими числам от 0 до 9, знаку +, d, x, и слипшемуся dx.

Обучение проходило на 3090 образцах, среди которых больше всего символов «x» и меньше всего «d». Несмотря на это, процесс обучения на моём C2D e6750 занял всего 40 секунд.
Код для обучения НС:
static void Main(string[] args)
{
    NeuralNet net = new NeuralNet();
    //Указываем слои нейронной сети
    uint[] layers = { 336, 130, 14 };
    net.CreateStandardArray(layers);
    //Устанавливаем случайные веса
    net.RandomizeWeights(-0.1, 0.1);
    net.SetLearningRate(0.7f);
    //Загружаем данные для обучения НС
    TrainingData data = new TrainingData();
    data.ReadTrainFromFile("train.tr");
    //Обучаем сеть
    net.TrainOnData(data, 1000, 0, 0.001f);
    //Сохраняем готовую НС в файл
    net.Save("skynet.ann");
}

Структура текстового файла train.tr:
num_train_data num_input num_output
inputdata seperated by space
outputdata seperated by space
...
inputdata seperated by space
outputdata seperated by space

Примеры символов, передающихся на распознавание:


Распознавание интеграла


Сперва найдем и распознаем пределы. Верхний может состоять из 1-2 цифр, причем максимальное значение равно 10. Нижний находится в диапазоне от 0 до -10.
Облегчим задачу нейронной сети:
  • Если верхний предел состоит из двух цифр, то это 10 (нижний из трех).
  • Минус распознаем алгоритмически по пороговому значению высоты символа.
  • При распознавании, не будем учитывать выходы НС, не соответствующие цифрам.
Найдем знак интеграла, просто двигаясь вправо от левой границы с отступом от верхней границы в половину высоты капчи. Все, что правее – подынтегральное выражение.
Зная номер интеграла, количество объектов на капче, и то, что эти объекты пронумерованы слева направо, дальнейшим последовательным распознаванием символов мы получим примерно следующую строку «5x5+x5-4x2+4x5dx». Предварительно упростим работу парсеру выражения — приведем её к виду "+5x5+x5-4x2+4x5".
Некоторые закономерности позволяют легко получить итоговые данные для решения интеграла:
  • Знаки "+" и "-" разделяют слагаемые.
  • Цифры после «x» – степень.
  • И т.д.
На выходе получим 2 массива с множителями и степенями x. Дальнейшее решение интеграла трудностей уже не представляет.

Вместо заключения


Качество распознавания всей капчи впечатляет: 93,8% на выборке в 500 штук!



Скачать готовую программу, демонстрирующую решение интеграла можно здесь. Или вместе с исходниками (+ программа для обучения нейросети и обучающая выборка) здесь.
Надеюсь, ни мой сервер, ни сервер хабраюзера grishkaa не ляжет под хабраэффектом ;)
Брюхов Дмитрий @globik
карма
99,5
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (88)

  • +28
    Если эти капчи уже так легко вкрыть…

    то я боюсь подумать какие капчи будут через пару лет…

    Мне придется наверно еще и потанцевать — чтобы где то зарегаться!
    • +4
      СМС с мобильного телефона
      • –9
        Платно, но удобно.

        Пока редко кто хочет брать такую услугу… я ее уже какой год предоставляю!
        • +1
          серьезные ребята вроде liqpay и прочих договариваются с подобными смс биллингами, думаю со временнем будет подобный сервис авторизации вроде saas.
          Это где же такие капчи на сайтах? это просто ад!
          • +2
            • 0
              ну вообще отлично возьму на вооружение :)
              • 0
                ай нет не буду, я думал бесплатно) а там Стоимость обслуживания данной системы составляет 0,02 дол. — один отправленный SMS пароль а если кто то устроит распределенную атаку? это же разорится можно.
                1000 авторизаций в минуту = 20$
                60000 авторизаций в час = 1200$ = попадалово на деньги
                • 0
                  Вот в этом то и вся проблема однако есть например сервис www.tropo.com/pricing/
                  который сейчас бесплатен для разработчиков так что побаловаться все таки можно
        • НЛО прилетело и опубликовало эту надпись здесь
          • +2
            Это уже проблема России а не самой системы. Я работаю с такими системами. В Израиле. И если я передам кому то номер, или сниму с человека который не записывался, меня так засудят что мои дети будут расплачиваться.

            А вообще система удобная. У меня регистрация идет через телефон. Человек получает пароль, вводит на сайте и все. У меня голова не болит — никакого спама + возможность регистрации только с Израиля. А стоимость — примерно 0.2$ получается за SMS.
      • +6
        Ага, прощай анонимность.
        • +1
          Надо всего лишь купить симку за 100 рублей в подозрительном месте, самый простой телефон и отъехать в соседний город и оттуда послать сообщение. Сам вот опасался регистрироваться с помощью мобильного телефона, но этот метод мне помог. Важно включить телефон только в пункте назначения, отправить смс и выключить телефон там же, потому что есть база IMEI аппаратов, хотя ей и мало пользуются, но она есть.
          • 0
            По-моему, это уже паранойя, простите
    • +10
      Microsoft Kinnect капча =)
      • +1
        Вот ведь вы подали сейчас кому-то идею) Ждём, через где-нибудь неделю на хабре появится пост о такой капче %)
        • +4
          А чуть позже и готовое решение для подбора MS Kinect капчи
          • +1
            Робот, вытанцовывающий капчу перед кинектом? =)
    • +33
      Матановую кэпчу надо использовать наоборот
      надо поставить несобственный интеграл по поверхности. Если прошёл — значит бот))
    • +5
      А с каки пох компьютер стал хуже человека считать уравнения? Изначальный смысл подобных капч несколько странен, нужны капчи на нелинейную логику;)
      • 0
        Думаю, что подойдет решение интеграла/производной в _символьном_ виде:)
        • 0
          Конечно нет, производная в символьном виде пишется вообще любым студентом. А интеграл wolfram возьмёт лучше и быстрее любого студента.
          • 0
            Мда, я забыл, что можно прикрутить какую-либо из математических библиотек и щелкать как орешки…
            Тогда как выход — либо абстрактные образы либо эмоции…
    • –1
      «Мама ну я же просто танцую!»
    • 0
      если только на сайте любителей танцев)
    • 0
      Так ведь изначально сложность этой капчи — преувеличена. Я бы вообще не называл такой вариант капчей, скорее это антикапча: она в разы проще именно для машины, чем для человека. Сложная капча должна быть именно устойчивой для распознавания символов машинными средствами и быть простой с точки зрения получения ответа. А тут как раз распознание максимально простое. Как и писал автор, это было сделано для развлечения, а не как пример обхождения защиты сложной капчи
    • 0
      «уже так легко вкрыть»

      автор использовал что-то, чего нельзя было использовать раньше?
  • +7
    skynet_0.001.ann доставляет, спасибо :)
  • 0
    Добейте до вставки картинки из буфера через Ctrl+V и будет полезная штука
    • 0
      хотя хм… выборка понадобится обычная еще
  • +5
    Неделя капчи же
  • +23
    Матановая капча была обречена на провал :)
    Математические вычисления — это то, с чем компьютер справляется лучше всего, над этим работают уже больше 50 лет.
    Чтобы создать непобедимую капчу, нужно искать в другом напрвлении… Например, эмоции. Из 100 картинок выбрать приятную.
    • +25
      Приятная — понятие растяжимое) Вот мне приятно расчлененное тело в луже кишок и крови…
      P.S. Простите за испорченный аппетит
      • +21
        Что-то мне мясца захотелось от выших слов.
      • +2
        Ну, красота требует жертв
      • +3
        По результатам капчи составят психологический портрет и сразу отнесут в нужную маркетинговую группу — будут вам потом мясорубки в рекламе показывать :)
        • +2
          > По результатам капчи составят психологический портрет…

          … и сразу редиректят в подходящий раздел сайта! Находка для порно-ресурсов :)
    • +7
      Правильно, нужно выбирать ту сферу для капчи, в которой машина разбирается хуже всего.

      Например, из предложенных силиконовых и натуральных сисек выбрать только силиконовые. Это будет успех в капчестроении.
      • 0
        ХОТЕТ!
      • +14
        • +5
          Не ожидал от себя такого, но я угадал 19 из 20 )) Хорошая капча!
        • +1
          Я угадал 18 из 20.
          Для ReCaptcha примерно 15 из 20.
        • +1
          19 из 20. Надеялся что натуральный загар есть признак натуральности груди. (номер 2)
          • +2
            Почти все на втором номере запороли :)
            • 0
              Завалился на 10-ой
            • 0
              18/20, запоролся на 4 и 5.
        • +3
          Угадал только 15 из 20. Наверно я оптимист )
        • +1
          19 из 20. Почему-то девятая смутила…
          • 0
            Согласен, девятая с подвохом! 19/20 )
        • 0
          Я слабак — 16 из 20
          • 0
            Неужели я бот?
      • 0
        Котокапча. Есть несколько фоток с животными, нужно выбрать те, что с котами.
        • 0
          Была на Рапидшаре подобная — надо было написать, сколько на картинке котов среди собак. Вот только они были настолько сильно деформированы, что были очень похожи на оных собак…

          А вообще по сути тоже можно распознать. Сложно будет распознать если фотки со всё время разными котами (например из Гугла — но там тож как то фильтровать надо)
          • 0
            Захламляем гугл фотками собак с тегами кошка — и капчу убирают как нерабочую )
    • 0
      Ага, 99 мужиков и одна девушка. Пидоры и девченки не пройдут.
      • +2
        Ага, девченки вообще не существуют. Поэтому 100% не пройдут.
        • +3
          К сожаленью, на 9 девчонок по статистике сотни девчят… :(
    • 0
      на сайте киевстара для отправки смс давно уже используется капча из 9 картинок из которых нужно выбрать 4 картинки с живой природой(цветы, животные, птицы итд)
      www.kyivstar.ua/sms/
    • +1
      Из 100 картинок выбрать другой сервис или сайт. Ну его на фиг.
  • +13
    Напомнило виндовый распознователь.
    <img src="" alt=«image»/>
    • НЛО прилетело и опубликовало эту надпись здесь
      • +7
        Win+R -> mip.exe
      • 0
        Эта штука встроена в семерку
  • 0
    Была неделя Dropbox'а, а эта неделю походу неделя капчи :D
    • +3
      А до этого была неделя «пробелы vs табы»
    • +1
      Сложность капчи увеличивается вдвое.
  • +1
    Круто! =)
  • 0
    Даёшь канакапчу!
    • +3
      Топик в сыром виде уже в черновиках. Завтра-послезавтра будет :)
  • –6
    Одни строят, другие ломает… Не понимаю…
    • +2
      В жизни так всегда. Вирусы vs антивирусы. Админы vs хакеры ну и т.д. Инь-янь короче :-)
  • 0
    К сожалению, Ваш сервер все таки упал. Обе ссылки не работают.
    • +1
      Перезалил на народ.
      • 0
        Спасибо!
  • +5
    Из этой штуки можно сделать мобильное приложение для решения уравнений, с захватом с фотокамеры, школьники и студенты оторвут. Может быть полезно и инженерам. В big bang вроде про такой стартап снимали.
    • 0
      Ну только в Big Bang они дифуры распознавали. Хотя и то и то пригодилось бы учащимся =)
    • 0
      Я уже давно жду приложение для android типа mathcad :(
      • 0
        Есть же Вольфрам :)
        • 0
          Для вольфрама нужен интернет, он у нас дорогой
          • 0
            Так не сайт, а приложение, у него потребление трафика наверняка минимальное.
  • +5
    А мне казалось, что матановая капча была рассчитана на целенаправленное отсеивания определённой категории наслеления :)
    (отнюдь не спамеров)
  • 0
    Надо капчу делать из теста на IQ
    • 0
      Из разряда «выберите картинку, которая должна стоять на девятом месте»? долго и нудно. Да и запрограммировать логику для антикапчи тоже, наверняка, не очень сложно же.
  • +1
    Для выделения связных областей было бы оптимальнее использовать последовательную разметку, она сильно быстрее.
    А вообще, конечно, описанный в статье метод крайне капитанский, и было бы интересно услышать как раз про распознавание при помощи нейронной сети, а так же как обработать изображение, где символы перекрываются.
    • 0
      В статье, я понял, они и обрабатываются просто как последовательность символов. В данном случае отличный вариант.
  • 0
    интересно, а разумно ли использовать такую сеть для распознавания текста с документов, например с паспорта РФ?
  • +1
    Хоть для практических целей самому и не нужно, да и вообще против каптч как таковых — но шикарно ведь. Особенно с учетом успешности распознавания. Рукоплескаю. Слышно? Нет… А жаль.
  • 0
    FANN написана не на C++, а на C — думаю, это важно, так как интерфейсы разительно отличаются. Впрочем, API на C++ у нее тоже есть.
  • +1
    globik, спасибо вам за такую хорошую статью, а также за исходные коды. Сам начал изучать нейронные сети, и сейчас получилось «победить» первую капчу в жизни.

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