Цвет и надежное конструирование CAPTCHA

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

Вместе с тем в тестах CAPTCHA (Completely Automated Public Turing Test to Tell Computers and Humans Apart), стандартном механизме, применяемом на многих сайтах для борьбы со спамом и другими злоупотреблениями, неудачный выбор цвета может отрицательно сказаться на безопасности. Рассмотрим широко распространенные текстовые CAPTCHA со сложными искажениями символов, которые позволяют сделать символьную строку неразличимой для алгоритмов распознавания образов, но сохранить ее узнаваемость для человека.

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

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

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

Цветные CAPTCHA

Одним из первых цветных тестов был разработанный в Университете Карнеги-Меллон тест Gimpy-r (рис. 1, a), которым пользовалась компания Yahoo для защиты своих онлайн-сервисов. Преобладающий цвет искаженных символов (часто черный) в каждом тесте всегда был наименее интенсивным из всех использованных и никогда не применялся как фоновый, что облегчало извлечение и распознавание текста программой. На рис. 1, б показан текст, извлеченный программой, которая просто выбирает только черные пикселы. Цветной фон, выбранный для надежности, бесполезен — он может только запутать человека и тем самым снизить удобство использования теста.

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

Рис. 1. Два ранних (около 2001 года) теста CAPTCHA: а — первоначальный тест Gimpy-r; б — символьная строка, извлеченная с помощью программы; в — тест EZ-gimpy; г — тест с извлеченными только черными пикселами. И начальное изображение, и извлеченный текст обеспечивают один и тот же уровень надежности

Успех сегментации Gimpy-r методом заливки цветом (color filling segmentation, CFS) оказался стопроцентным. Принцип данного метода состоит в распознавании каждого связного большого элемента, который часто соответствует индивидуальному символу (или штриху). Алгоритм сначала находит любой черный пиксел на изображении (рис. 1, б), а затем обходит всех его черных соседей, пока не будут найдены все соединенные черные пикселы, — это означает, что компонент идентифицирован и сегментирован. Затем распознается черный пиксел за пределами области с уже найденными компонентами и начинается новый обход для идентификации следующего компонента. Это продолжается до тех пор, пока не будут обнаружены все черные компоненты. Метод, по сути, подобен заливке каждого связного компонента своим цветом — в конечном итоге каждый черный компонент окрашен в определенный цвет, и число использованных цветов — это и есть количество черных компонентов на изображении.

После сегментации распознавание каждого символа стандартными способами уже не вызывает труда. Например, с помощью нейросети удавалось добиваться успеха примерно в 95% случаев при распознавании индивидуальных символов, сильно искаженных различными способами. Таким образом, тесты Gimpy-r взламывались с общей долей успеха примерно 81% (~100% * 0,95), хотя смысл CAPTCHA в том, чтобы не дать боту добиться уровня успеха больше 0,01%, а если можно свести взлом CAPTCHA к задаче распознавания индивидуальных символов в тесте, то значит, что тест дефектен.

Конструктивный дефект Gimpy-r наблюдался и в EZ-gimpy (рис. 1, в, г) — еще одном раннем CAPTCHA, разработанном той же командой Университета Карнеги-Меллон и также применявшимся Yahoo.

Гэбриел Мой и его коллеги разработали методы оценки искажений для взлома Gimpy-r (доля успеха — 78%) и EZ-Gimpy (99%). Грег Мори и Джитендра Малик взламывали EZ-Gimpy с долей успеха 92% с помощью сложных алгоритмов распознавания объектов. Однако оба эти исследования больше были ориентированы на развитие алгоритмов компьютерного зрения, чем на выявление конструктивных дефектов CAPTCHA. Методология извлечения символьной строки, ее сегментации и реорганизации индивидуальных символов стандартна для процедур анализа защищенности CAPTCHA, но она также может указать на конструктивные дефекты.

Изъяны, подобные обнаруженным в Gimpy-r, присутствовали в CAPTCHA с полутоновыми изображениями, в которых есть точки черного цвета, белого и разных оттенков серого, например тест Securimage (рис. 2, а), сгенерированный opensource-сервисом www.phpcaptcha.org. Посредством распознавания всех пикселов цвета переднего плана (белого) были успешно извлечены все символы строки (рис. 2, б). Затем с помощью метода CFS автоматически со стопроцентным успехом были распознаны все индивидуальные символы. Таким образом, схема была успешно взломана. С другой стороны, в этом случае полутоновые изображения, похоже, не ухудшают читаемости.

Рис. 2. CAPTCHA-тесты Securimage: а — схема, в которой используется полутоновое изображение; б — текст, извлеченный программой взлома. Во второй схеме (в) используются случайно расположенные дуги, пересекающие и соединяющие символы, но текст (г) по-прежнему удается извлечь. И оригинальные изображения, и извлеченные программой взлома обеспечивают одинаковый уровень надежности. (Эти схемы были созданы в 2008 году, а взломаны в 2009-м)

Еще в одной схеме Securimage (рис. 2, в) применяются случайно расположенные дуги, пересекающие и соединяющие символы для защиты против сегментационных атак. В этой схеме используются три цвета: белый для фона изображения, бледно-лиловый для символьной строки и голубой для дуг. Поскольку эти цвета остаются неизменными, идентификация и удаление дуг тривиальны. Вначале определяются (по цвету) участки дуг вне символов (то есть, не пересекающие их) и удаляются путем замены их цвета на фоновый белый. Затем цвет оставшихся участков дуг заменяется на цвет символов (рис. 2, г). После этого метод CFS обеспечивает стопроцентный успех сегментации, а существующие технологии распознавания символов могут определить символы с долей успеха 95%.

Чтобы сделать тесты более привлекательными внешне, в некоторых CAPTCHA соседние символы имеют разные цвета. Пример такой схемы — тест Cryptograph (доступный в виде плагина WordPress и как сервис на www.captcha.fr), показанный на рис. 3, а. Однако эта особенность дизайна, как выяснилось, является фатальной для безопасности.

Рис. 3. Некорректное использование цвета в различных CAPTCHA-тестах: а — тесты Cryptographp; б — они же после удаления фонового шума; в —окончательные сегментированные результаты; г — два образца тестов FreeCap; д — два LinkedIn имеют похожие проблемы с надежностью. (Cryptographp был создан в 2006 году, а FreeCap — в 2003 году; оба были взломаны в 2007 году, а схема LinkedIn — в 2009-м)

В первоначальных тестах в качестве шума использовались случайные окружности или пересекающиеся линии. Однако с удалением такого шума проблем не возникает, поскольку толщина посторонних фигур и линий значительно отличается от толщины символов. На рис. 3, б показаны изображения после удаления шума. Обычно трудно сегментировать перекрывающиеся символы, и имеющиеся данные указывают на то, что в текстовых CAPTCHA для надежности следует использовать, например, именно этот устойчивый к сегментации механизм. Но поскольку у каждого символа в данной схеме свой цвет, то путем выбора всех пикселов одинакового цвета можно эффективно сегментировать перекрывающиеся символы (рис. 3, в). Этот метод был проверен на 50 тестах, сгенерированных сервисом Cryptographp, и в 100% случаев сегментация оказалась успешной. В среднем сегментация каждого теста выполнялась на стандартном настольном компьютере всего за 60 мс — любой компетентный взломщик может без труда обойти эту схему.

Похожая ошибка наблюдалась и у FreeCap (рис. 3, г), еще одного популярного CAPTCHA. В данной схеме соседние буквы имеют разные цвета, что упрощает сегментацию соприкасающихся и перекрывающихся символов, которая иначе была бы очень сложной. Заметим, что разработчик FreeCap весьма сведущ в вопросах безопасности — ему принадлежит авторство статьи о распространенной атаке, при которой простое повторное использование известного идентификатора сеанса теста позволяло обходить некоторые ранние CAPTCHA.

И наконец, та же ошибка наблюдалась в тестах CAPTCHA, недавно использовавшихся на сайте LinkedIn. На образцах тестов, взятых оттуда (рис. 3, д), вначале был задействован метод огрубления, уменьшающий число цветов на изображениях. Затем распознавалась область с перекрывающимися или соприкасающимися символами. После этого удалось с легкостью отделить U от V и L от H путем выбора всех пикселов одинакового цвета в областях, содержащих символы.

На примере схемы BotBlock (рис. 4, а) можно видеть, что некорректное применение сложных сочетаний цветов в CAPTCHA может вызвать проблемы и с читаемостью, и с надежностью. В данной схеме используются случайные последовательности букв, появляющиеся в различных местах в каждом тесте. Здесь применяется сложный метод генерации расцветки: фон состоит из множества цветовых блоков случайной формы, причем и на фоне, и на переднем плане могут быть одинаковые цвета. Однако из-за такой цветовой схемы даже людям с нормальным зрением часто трудно различить символы теста, а для людей с расстройствами зрения, в частности с дальтонизмом, это еще сложнее. Отметим, что цветовой слепоте подвержены примерно 8% взрослых мужчин и 1% женщин в Северной Америке и Европе. Наиболее распространенная форма дальтонизма — трудности в различении красного и зеленого.

Рис. 4. CAPTCHA-тест BotBlock: а — первоначальные примеры теста; б — символы, автоматически извлеченные программой. Изображения (а) и (б) обеспечивают одинаковый уровень надежности. (Дата первого использования данного теста неизвестна, но взломать его удалось в 2007 году.)

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

Черно-белые CAPTCHA

Рассмотрим теперь два черно-белых теста: первый до недавнего времени применялся на Megaupload.com, одном из крупнейших файлообменных сайтов, ныне прекратившем свою деятельность, а второй — от BotDetect, коммерческого сервиса CAPTCHA, который, как утверждают его операторы, широко применяется на крупных сайтах. Оказалось, что даже такое простое сочетание цветов, как в этих CAPTCHA, может иметь свои изъяны.

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

Рис. 5. CAPTCHA-тест сайта Megaupload: а — четыре примера теста с ответами NAQ6, VUX6, GMW7 и ZYB9; б — те же тесты, но с отключенной гештальтфункцией. (Когда первый раз использовалась эта схема, неизвестно, но взломать ее удалось в 2009 году.)

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

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

Второй этап атаки — идентификация и извлечение общих белых компонентов, то есть областей соединения соседних символов. Вначале с помощью метода CFS были распознаны все белые компоненты. Затем был исключен фон основного изображения (то есть область, внешняя по отношению к символьной строке) — он является самым большим по числу пикселов белым компонентом. На рис. 6, в показаны оставшиеся после этого белые компоненты. С помощью эвристических алгоритмов также были исключены с большой долей успеха петли, являющиеся частью символов (например, А, Q и 6), и петли, возникающие при соединении двух символов. В частности, такая петля образуется при соединении V и U во втором примере на рис. 5, а. На рис. 6, г показано, что были успешно идентифицированы все общие белые компоненты.

Рис. 6. Сегментационная атака на CAPTCHA-тест Megaupload: а — оригинальное изображение, б — из него извлечены все черные компоненты (с удалением небольшого объема черного шума). Затем были (в) извлечены все белые компоненты, исключая фон, и (г) извлечены перекрывающиеся белые компоненты путем удаления петель. Наконец, (д) черные и общие белые компоненты были объединены для формирования индивидуальных символов

На последнем шаге белые компоненты помещаются в верное место для объединения с соответствующими черными компонентами с целью формирования каждого полного символа. Ясно, что n символов при горизонтальном соединении дают n-1 областей соединения между ними и что общие белые компоненты, помещенные по вертикали близко друг к другу, принадлежат одной области соединения. Таким образом, для примера, имеющего всего четыре символа (рис. 6), справедливо следующее:

• все общие белые компоненты внутри первой области соединения и все черные компоненты слева от нее можно объединить для образования первого символа;
• все общие белые компоненты внутри первой и второй области соединения и все черные компоненты между ними можно объединить для образования второго символа;
• все общие белые компоненты внутри второй и третьей области соединения и все черные компоненты справа от нее можно объединить для образования четвертого символа.

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

Данная атака обеспечила успех сегментации в более чем 78% случаев, и в среднем на ее выполнение для каждого теста на стандартном настольном компьютере уходило 120 мс. Из этого следует, что тест CAPTCHA Megaupload (с помощью сегментации и последующего распознавания) можно взломать с уровнем успеха 63,7% (~78,25% * 0,95).

CAPTCHA-тест BotDetect выполнен по шахматной схеме. Как видно из рис. 7, а, символы как будто сливаются с шахматной доской. Каждый символ разделен на множество черных и белых компонентов, и все буквы смешиваются и соединяются с клетками доски — разработчики рассчитывали, что благодаря этому распознать их программным способом будет нельзя, однако это можно сделать с помощью простой атаки. Вначале распознается каждая клетка шахматной доски. Если большинство пикселов в ней черные, все они перекрашиваются в белые, а белые, наоборот, в черные. Если большинство пикселов в клетке белые, то она оставляется без изменений. На рис. 7, б показано, что программа успешно извлекла все символы. Определение местонахождения и распознавание каждого символа тривиальны — эта схема дефектна.

Рис. 7. CAPTCHA-тест BotDetect: а — образцы теста; б — автоматически извлеченный из них текст. (Данная схема была создана в 2006 году, взломать ее удалось в 2009 году)

Уроки

Грамотно применять цвета в тестах CAPTCHA непросто — многие тесты, от самых ранних схем до новейших, в том числе известные схемы LinkedIn, Megaupload и BotDetect, имеют фатальные уязвимости ввиду непродуманного использования цвета. При употреблении сложных, замысловатых цветовых схем может пострадать удобство использования. Например, учитывая существование разных видов дальтонизма, довольно сложно определить, какие цветные изображения создадут сложности для дальтоников.

Принцип атак на CAPTCHA можно обобщить, представив их в виде следующих шагов: отделение переднего плана от фона; идентификация соединенных компонентов на переднем плане и, при необходимости, разделение их на индивидуальные символы; распознавание индивидуальных символов.

Можно предложить следующие рекомендации по использованию цвета:

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

***

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

В недавних версиях ряда широко распространенных CAPTCHA все эти рекомендации учтены и сложные цветовые схемы не используются:

• на сайте Microsoft отдано предпочтение простой цветовой схеме, в которой сам текст темно-синего цвета, а фон — светло-серый;
• в сервисах Google используется только один цвет (зеленый, красный или синий) для символьных последовательностей и белый фон;
• на сайтах Yahoo применяются только черно-белые CAPTCHA;
• в системе reCAPTCHA тоже используется черно-белая схема (reCAPTCHA — новая разработка изобретателей Gimpy-r и EZ-gimpy).

Известно, что при дизайне пользовательских интерфейсов лучше избегать «эффекта Лас-Вегаса» — использования слишком большого числа цветов. Этот же принцип применим и к текстовым CAPTCHA, однако в данном случае он влияет не только на удобство пользования, но и на безопасность.

Ахмад Салах Эль Ахмад (ahmad.salah-el-ahmad@ncl.ac.uk) — аспирант, Джефф Ян (jeff.yan@ncl.ac.uk) — преподаватель школы компьютерных наук Ньюкаслского университета, Вай Инь Нг (w.ng@cantab.net) — профессор информационной инженерии Китайского университета Гонконга.