Hashcash

Hashcash — система доказательства правильности работы, используемая с целью уменьшения количества спама и DoS-атак. Позднее стала использоваться в bitcoin и других криптовалютах[1], как часть алгоритма анализа данных. Система Hashcash была предложена в мае 1997 года Адамом Бэком.[2]

Принцип работы

Hashcash — это алгоритм доказательства правильности работы, требующий выборочного объёма данных для вычислений, но при этом доказательство может быть эффективно подтверждено. У пользователей электронной почты к заголовку добавляется текстовая кодировка отметки hashcash, подтверждающая, что перед отправкой было затрачено некоторое время для вычисления отметки. Другими словами, отправитель тратит некоторое время на вычисление отметки и отправку, что несвойственно спамерам. Получатель может ценой небольших вычислительных мощностей подтвердить валидность отметки. Единственным известным способом подобрать заголовок с необходимыми параметрами является полный перебор. И, хотя тестирование одной строки достаточно просто, при достаточно малом количестве удовлетворительных ответов для поиска ответа потребуется достаточно большое количество попыток. Гипотеза состоит в том, что спамеры, чья бизнес-модель основана на их способности отправлять большое количество писем с очень низкими затратами на сообщение, перестанут получать выгоду, даже если стоимость каждого спама, который они посылают, небольшая. Получатели могут проверить, исполнил ли отправитель эту процедуру и использовать результаты, чтобы помочь фильтрам электронной почты.

Технические детали

Заголовок отметки выглядит следующим образом:[3]

X-Hashcash: 1:20:1303030600:adam@cypherspace.org::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:adam@cypherspace.org::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]

E-mail клиенты

The Penny Post[7] на SourceForge реализует Hashcash для email клиента Mozilla Thunderbird.[8] Проект назвал в честь доступного почтового сервиса, стоившего отправителю лишь одного пенни. (О подобных почтовых сервисах можно прочитать на странице Penny Post).

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).

См. также

Примечания
  1. Криптовалюты в реальном времени. Investing.com.
  2. A partial hash collision based postage scheme (Txt). Hashcash.org. Дата обращения: 13 октября 2014.
  3. hashcash - hashcash anti-spam / denial of service counter-measure tool (Txt). Hashcash.org. Дата обращения: 13 октября 2014.
  4. Hashcash proof-of-work paper (PDF). Hashcash.org. Дата обращения: 13 октября 2014.
  5. Hashcash FAQ. Hashcash.org (26 июня 2003). Дата обращения: 11 февраля 2014.
  6. SpamAssassin: Tests Performed: v3.3.x (недоступная ссылка). Spamassassin.apache.org (21 декабря 2006). Дата обращения: 11 февраля 2014. Архивировано 16 февраля 2014 года.
  7. Penny Post software project on SourceForge. Pennypost.sourceforge.net. Дата обращения: 13 октября 2014.
  8. Penny Post: What do you mean by Postage Stamp?. Pennypost.sourceforge.net (16 июня 2008). Дата обращения: 11 февраля 2014.
  9. Discontinued features and modified functionality in Outlook 2010. Office.microsoft.com. Дата обращения: 13 октября 2014.
  10. Email Postmark Validation Algorithm (PDF). Download.microdoft.com. Дата обращения: 13 октября 2014.
  11. The Coordinated Spam Reduction Initiative: A Technology and Policy Proposal (PDF). Дата обращения: 11 февраля 2014. Архивировано 21 октября 2013 года.
  12. WP-Hashcash, a plugin for Wordpress blog software Архивировано 27 октября 2005 года. that implements a Hashcash-like facility, written in JavaScript, by Elliott Back
  13. C reference implementation. hashcash.org. Дата обращения: 13 октября 2014.
  14. RSA Security Inc. has submitted a patent application (US Serial No. 09/496,824) (Txt). Ietf.org. Дата обращения: 13 октября 2014.
  15. SIP Computational Puzzles. Tools.ietf.org. Дата обращения: 13 октября 2014.
  16. Client Puzzles. Дата обращения: 13 октября 2014.
  17. Client-puzzle patent filing. Google.com. Дата обращения: 13 октября 2014.

Литература
  • 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)

Ссылки
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.