Hashcash
Hashcash — система доказательства правильности работы, используемая с целью уменьшения количества спама и DoS-атак. Позднее стала использоваться в bitcoin и других криптовалютах[1] как часть алгоритма анализа данных. Система Hashcash была предложена в мае 1997 года Адамом Бэком[2].
Принцип работы
[править | править код]Протокол Hashcash требует, чтобы отправитель электронного письма в специальном заголовке X-Hashcash разместил уникальный для каждого письма набор символов, который является результатом относительно длительного расчёта, данными для которого служит как текст письма, так и адреса отправителя/получателя. Это не позволяет копировать заголовок X-Hashcash даже для писем с одинаковым содержимым, но с разными адресами получателей, а также служит доказательством того, что на создание и отправку именно данного сообщения было затрачено некоторое время. При этом получателю для проверки полученного в заголовке значения требуется затратить значительно меньше ресурсов по сравнению с затратами отправителя, а сообщения без оговоренного заголовка предлагалось отклонять и не пересылать получателю. При обычном использовании электронной почтой не так уж значительно увеличится время отправки нескольких писем. Но необходимость выполнять большие вычисления выступает значительным препятствием при отправке большого числа сообщений, характерных при спаме или DoS-атаке. Если попытаться сформировать заголовок не используя заданную в алгоритме длительную процедуру, а ориентируясь лишь на быстрый принцип проверки результата, то единственным известным способом подобрать заголовок является полный перебор среди всех возможный значений, что приводит к высокой нагрузке на устройство злоумышленника и всё равно может занять значительное время.
Гипотеза эффективности Hashcash основывается на том, что траты на вычисления у злоумышленника станут большими и это сильно снизит или устранит потенциальную выгоду от проведения рассылки.
Технические детали
[править | править код]Заголовок отметки выглядит следующим образом:[3]
X-Hashcash: 1:20:1303030600:[email protected]::McMybZIhxKXu57jd:FOvXX
Заголовок содержит:
ver: Версию hashcash, 1 (которая заменила версию 0). bits: Число "предварительных" (нулевых) битов в хешированном коде. date: Время, в которое сообщение было отправлено, в формате ГГММДД[ччмм[сс]]. resource: Данные об отправителе, например, IP-адрес или адрес E-mail. ext: Расширение (опционально; игнорируется в версии 1). rand: Строка случайных чисел, закодированная в формате [[Base64|base-64]]. counter: Двоичный счётчик, закодированный в формате base-64.
Заголовок содержит адрес получателя, дату сообщения, информацию, подтверждающую, что все требуемые вычисления осуществлены. Присутствие адреса получателя требует пересчитывать заголовок для другого. Дата позволяет получателю учитывать заголовки недавно полученных писем и убедиться, что заголовок пришедшего сообщения уникален.
На стороне отправителя
[править | править код]Отправитель подготавливает заголовок и добавляет к нему случайное число. Затем он вычисляет 160-битный SHA-1-хеш заголовка. Если первые 20 бит хэша — нули, то этот заголовок приемлемый. В противном случае отправитель увеличивает значение счётчика и пробует ещё раз. Из 2160 возможных значений хеша 2140 удовлетворяют этому критерию. Таким образом, вероятность того, что случайно выбранный хеш будет начинаться с 20 нулей — 1 к 220. Количество попыток, которые отправитель вынужден произвести, прежде чем получит валидное значение хеша, моделируется геометрическим распределением. Следовательно, отправитель в среднем должен попробовать 220 (чуть более миллиона) случайных чисел, чтобы найти правильный заголовок. Учитывая разумные оценки времени, необходимого для вычисления хеша, это займёт около 1 секунды. В то же время, нет эффективного метода поиска валидного заголовка, кроме перебора.
Обычный пользователь ПК не будет испытывать значительных проблем из-за времени, необходимого на генерацию строки hashcash. В то же время спамеры будут испытывать существенные проблемы, так как отправляют очень большое число писем.
На стороне получателя
[править | править код]Технически система реализована следующими шагами:
компьютер получателя высчитывает 160-битный SHA-1-хеш целой строки (например, "1:20:060408:[email protected]::1QTjaYd7niiQA/sc:ePa"). Это занимает около двух микросекунд на 1-ГГц процессоре, что намного меньше, чем время, необходимое на загрузку оставшейся части e-mail сообщения. Если первые 20 бит ненулевые, хеш является недействительным (в последних версиях может потребоваться большее число нулевых битов, так как вычислительные мощности растут).
Компьютер получателя проверяет дату в заголовке (например, "060408", что означает 8 апреля 2006 г.). Если разница с текущей датой более двух дней, хеш является недействительным (двухдневное окно компенсирует разницу во времени и время перемещения по сети между различными системами).
Компьютер получателя проверяет, совпадает ли e-mail в строке хеша с каким-либо e-mail адресом, зарегистрированным получателем или с любым адресом из списка тех, на которые получатель подписан. Если совпадения отсутствуют, хеш является недействительным.
Компьютер получателя добавляет хеш-строку в базу данных. Если такая строка уже присутствует в базе (тем самым, выясняется, что произошла попытка заново использовать хеш-строку), хеш является недействительным.
Если хеш-строка прошла все тесты, она считается валидной. Все эти тесты не занимают большого количества времени и места на диске, по сравнению с получением основной части e-mail письма.
Необходимые затраты
[править | править код]Время, необходимое на вычисление подобных коллизий хеша, экспоненциально растёт с увеличением числа нулевых битов. То есть нулевые биты могут добавляться до тех пор, пока создание новых валидных хеш-строк не станет слишком дорогим для спамеров (удваивая время, необходимое на вычисление хеша каждым дополнительным нулём). Подтверждение того, что заголовок валидный, требует одинакового времени. При этом неважно, сколько нулей необходимо для валидного заголовка, так как требуется только одна операция хеширования.
Преимущества и недостатки
[править | править код]Система hashcash имеет преимущество перед микроплатежными предложениями, применяемыми к электронной почте, так как не предполагает привлечения реальных денег. Ни отправитель, ни получатель не должны платить. Таким образом избегаются все административные вопросы, связанные с микроплатежами.
С другой стороны, hashcash требует значительных вычислительных ресурсов, расходующихся на отправку каждого сообщения. Довольно сложно удачно подобрать среднее время, которое клиенты готовы тратить на вычисление заголовка. Это может означать, что встраиваемые системы низкого уровня либо жертвуют доступностью, либо не обеспечивают достаточной защиты от враждебных хостов, чтобы эффективно фильтровать спам.
Hashcash достаточно просто реализовать для пользовательских почтовых агентов и спам-фильтров. Не требуется наличия центрального сервера. Система может быть последовательно применена — дополнительный заголовок hashcash игнорируется, когда он получен почтовым клиентом, не понимающим его.
Один из анализов[4] пришёл к выводу, что, вероятнее всего, либо почта будет застревать из-за нехватки вычислительной мощности отправителя, либо спам все равно будет проходить. Примеры каждого включают, соответственно, централизованную топологию электронной почты (например, список рассылки), в которой некоторым серверам нужно отправить огромное количество законной электронной почты; и бот-сети или кластерные фермы, с которой спамеры могут чрезвычайно увеличить свою мощность обработки. Большинство из этих проблем может быть решено. Например, бот-сети могут обнаруживаться быстрее, потому что пользователи замечают высокую нагрузку на процессор и могут принять ответные меры, а серверы, использующие список рассылки, могут быть зарегистрированы в белых списках абонентских клиентов и, таким образом, освобождаются от проблем Hashcash. Но, в целом, они представляют собой серьёзные препятствия для развёртывания Hashcash, которые ещё предстоит решить.
Ещё одна прогнозируемая проблема состоит в том, что компьютеры продолжают наращивать мощность в соответствии с законом Мура. Таким образом, сложность необходимых вычислений должна быть увеличена. Тем не менее, развивающиеся страны продолжат использовать старое оборудование, что означает, что они будут испытывать трудности при работе в системе электронной почты. Это также относится к лицам с низким уровнем доходов в развитых странах, которые не могут позволить себе новейшее оборудование.
Применение
[править | править код]Биткойн
[править | править код]Hashcash концептуально схож с системами проверки правильности, используемыми в «Биткойн». Если в почтовых применениях предполагается, что получатель вручную контролирует объём работ систем проверки правильности работы для выигрыша в вычислительной мощности по закону Мура, то биткойн представляет p2p-сеть, которая внутренне автоматически регулирует объём работ. Также, в отличие от почты, где используются 20 бит (порядка 1 млн попыток для успешного поиска), биткойн использует 67,5 бит (необходимо порядка 200 млн триллионов попыток) и меняющийся критерий сложности, чтобы сгенерировать один из блоков, которые создаются каждые 10 минут. В биткойне скорректировали алгоритм, добавив поддержку работы с долями бит (первоначальная спецификация HashCash ограничивалась корректировкой целых степеней числа 2), тем самым удалось достичь более высокой точности.
Фильтры спама
[править | править код]Hashcash используется как потенциальное решение проблемы ложного срабатывания автоматических спам-фильтров, так как обычный пользователь не испытывает проблем с дополнительным временем, необходимым для отметки[5].
SpamAssassin проверяет наличие отметок hashcash начиная с версии 2.70, присваивая отрицательные баллы (то есть считает менее похожим на спам) неиспользованным ранее отметкам hashcash. В версии 3.3x (последняя версия на момент написания) система даёт бонусные баллы для любых 20-битных и более отметок (максимум −5 баллов для 26-битных и более отметок). Однако, за уже использованную отметку записывается небольшой штраф[6].
Email-клиенты
[править | править код]The Penny Post[7] на SourceForge реализует Hashcash для email-клиента Mozilla Thunderbird[8]. Проект назван в честь почтовой системы[англ.], где отправка писем стоит всего один пенни.
Email Postmark
[править | править код]Microsoft также спроектировал и реализовал ныне устаревшую[9] открытую спецификацию, аналогичную hashcash, но несовместимую с ней — Email Postmark[10], ставшую частью Coordinated Spam Reduction Initiative (CSRI)[11]. Вариант hashcash, предложенный Microsoft, реализован в компонентах почтовых сервисов Microsoft, таких как Exchange, Outlook и Hotmail. Разница в формате между отметками hashcash и Microsoft в том, что отметка Microsoft хеширует также основную часть письма, а также использует модифицированный SHA-1 в качестве хеш-функции.
Блоги
[править | править код]Весьма похожим образом блоги становятся жертвами спама в комментариях. Некоторые владельцы блогов использовали hashcash-скрипты, написанные на JavaScript, чтобы замедлить комментарии спамеров[12]. Некоторые скрипты (такие, как wp-hashcash) претендуют на реализацию Hashcash, но зависят от запутывания средствами JavaScript, заставляя клиента генерировать соответствующий ключ; в то время как это требует некоторой вычислительной мощности, они не используют алгоритм Hashcash или Hashcash-отметки.
Интеллектуальная собственность
[править | править код]Hashcash не запатентован, а эталонная реализация[13] и большинство других реализаций являются свободно распространяемым ПО. Hashcash включён или доступен для многих дистрибутивов Linux. RSA сделал IPR заявления в IETF о client-puzzles алгоритмах[14] в контексте RFC[15], описывающем различные client-puzzles (не hashcash). RFC включил hashcash в статью и упомянул алгоритм, но механизм, описанный в ней, решает скорее интерактивную задачу, которая больше похожа на Client-Puzzles. Hashcash не интерактивен и, следовательно, не имеет известных решений. В любом случае, IPR утверждение RSA не может быть применено к hashcash, так как hashcash предшествует[2] (март 1997) публикации Client-puzzle[16] (февраль 1999) и патентной заявке US7197639[17] (февраль 2000).
См. также
[править | править код]Примечания
[править | править код]- ↑ Криптовалюты в реальном времени. Investing.com. Дата обращения: 9 августа 2017. Архивировано 9 августа 2017 года.
- ↑ 1 2 A partial hash collision based postage scheme (Txt). Hashcash.org. Дата обращения: 13 октября 2014. Архивировано 24 сентября 2015 года.
- ↑ hashcash - hashcash anti-spam / denial of service counter-measure tool (Txt). Hashcash.org. Дата обращения: 13 октября 2014. Архивировано 3 марта 2016 года.
- ↑ Hashcash proof-of-work paper (PDF). Hashcash.org. Дата обращения: 13 октября 2014. Архивировано 15 января 2016 года.
- ↑ Hashcash FAQ. Hashcash.org (26 июня 2003). Дата обращения: 11 февраля 2014. Архивировано 12 октября 2013 года.
- ↑ SpamAssassin: Tests Performed: v3.3.x. Spamassassin.apache.org (21 декабря 2006). Дата обращения: 11 февраля 2014. Архивировано из оригинала 16 февраля 2014 года.
- ↑ Penny Post software project on SourceForge. Pennypost.sourceforge.net. Дата обращения: 13 октября 2014. Архивировано 21 августа 2008 года.
- ↑ Penny Post: What do you mean by Postage Stamp? Pennypost.sourceforge.net (16 июня 2008). Дата обращения: 11 февраля 2014. Архивировано 19 февраля 2014 года.
- ↑ Discontinued features and modified functionality in Outlook 2010. Office.microsoft.com. Дата обращения: 13 октября 2014. Архивировано 18 октября 2014 года.
- ↑ Email Postmark Validation Algorithm (PDF). Download.microdoft.com. Дата обращения: 13 октября 2014. Архивировано 26 ноября 2015 года.
- ↑ The Coordinated Spam Reduction Initiative: A Technology and Policy Proposal (PDF). Дата обращения: 11 февраля 2014. Архивировано 21 октября 2013 года.
- ↑ WP-Hashcash, a plugin for Wordpress blog software Архивировано 27 октября 2005 года. that implements a Hashcash-like facility, written in JavaScript, by Elliott Back
- ↑ C reference implementation. hashcash.org. Дата обращения: 13 октября 2014. Архивировано 9 декабря 2015 года.
- ↑ RSA Security Inc. has submitted a patent application (US Serial No. 09/496,824) (Txt). Ietf.org. Дата обращения: 13 октября 2014. Архивировано 26 сентября 2008 года.
- ↑ SIP Computational Puzzles. Tools.ietf.org. Дата обращения: 13 октября 2014. Архивировано 3 марта 2016 года.
- ↑ Client Puzzles. Дата обращения: 13 октября 2014. Архивировано 4 марта 2016 года.
- ↑ Client-puzzle patent filing. Google.com. Дата обращения: 13 октября 2014. Архивировано 8 декабря 2015 года.
Литература
[править | править код]- Adam Back, «Hashcash — A Denial of Service Counter-Measure», technical report, August 2002 (PDF).
- Ben Laurie and Richard Clayton, «'Proof-of-Work' Proves Not to Work», WEIS 04. (PDF).
- Dwork, C. and Naor, M. (1992) «Pricing via Processing or Combating Junk Mail», Crypto '92, pp. 139—147. (PDF)