Hashcash - Hashcash

Hashcash это система доказательства работы используется для ограничения электронный спам и атаки отказа в обслуживании, а в последнее время стало известно о его использовании в биткойн (и другие криптовалюты ) как часть алгоритма майнинга. Hashcash был предложен в 1997 году Адам Бэк[1] и более формально описан в статье Бэка 2002 года «Hashcash - противодействие отказу в обслуживании».[2]

Фон

Идея «... требовать от пользователя вычисления умеренно сложной, но не трудноразрешимой функции ...» была предложена Синтия Дворк и Мони Наор в своей статье 1992 года «Ценообразование посредством обработки или борьбы с нежелательной почтой».[3]

Как это устроено

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

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

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

Строка заголовка выглядит примерно так:[4]

X-Hashcash: 1: 20: 1303030600: [email protected] :: McMybZIhxKXu57jd: ckvi

Заголовок содержит:

  • вер: Версия формата Hashcash, 1 (заменяет версию 0).
  • биты: Количество битов «частичного предварительного изображения» (ноль) в хешированном коде.
  • Дата: Время отправки сообщения в формате ГГММДД [ччмм [сс]].
  • ресурс: Строка данных ресурса передается, например, IP-адрес или адрес электронной почты.
  • доб: Расширение (необязательно; игнорируется в версии 1).
  • ранд: Строка случайных символов, закодированных в база-64 формат.
  • прилавок: Двоичный счетчик, закодированный в формате base-64.

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

Сторона отправителя

Отправитель подготавливает заголовок и добавляет значение счетчика, инициализированное случайным числом. Затем он вычисляет 160-битное SHA-1 хэш заголовка. Если первые 20 бит (т. Е. 5 старших шестнадцатеричных цифр) хэша - все нули, то это приемлемый заголовок. Если нет, то отправитель увеличивает счетчик и снова пытается получить хеш. Из 2160 возможных значений хэша, есть 2140 хеш-значения, удовлетворяющие этому критерию. Таким образом, шанс случайного выбора заголовка, который будет иметь 20 нулей в начале хеша, равен 1 к 2.20 (около 106, или примерно один на миллион). Количество попыток отправителя получить действительное хеш-значение моделируется следующим образом: геометрическое распределение. Следовательно, отправителю в среднем придется попробовать 220 значения, чтобы найти допустимый заголовок. Учитывая разумные оценки времени, необходимого для вычисления хэша, это займет около секунды. Известно, что нет более эффективного метода поиска допустимого заголовка, чем этот метод грубой силы.

Обычный пользователь настольного ПК не будет испытывать значительных неудобств из-за времени обработки, необходимого для генерации строки Hashcash. Однако спамеры значительно пострадают из-за большого количества рассылаемых ими спамерских сообщений.

Сторона получателя

Технически система реализована со следующими этапами:

  • Компьютер получателя вычисляет 160-битное SHA-1 хэш всей строки (например, "1: 20: 060408: [email protected] :: 1QTjaYd7niiQA / sc: ePa"). Это занимает около двух микросекунд на машине с частотой 1 ГГц, что намного меньше времени, необходимого для получения остальной части электронного письма. Если не все первые 20 бит равны нулю, хеш-код недействителен. (Более поздние версии могут потребовать большего количества битов для обнуления по мере увеличения скорости машинной обработки.)
  • Компьютер получателя проверяет дату в заголовке (например, "060408", что соответствует дате 8 апреля 2006 г.). Если он не в течение двух дней после текущей даты, он недействителен. (Двухдневное окно компенсирует рассогласование часов и время сетевой маршрутизации между разными системами.)
  • Компьютер получателя проверяет, соответствует ли адрес электронной почты в строке хэша любому из допустимых адресов электронной почты, зарегистрированных получателем, или соответствует ли он любому из списков рассылки, на которые подписан получатель. Если совпадение не найдено, хеш-строка недействительна.
  • Компьютер получателя вставляет хеш-строку в базу данных. Если строка уже находится в базе данных (указывая, что предпринимается попытка повторно использовать строку хеширования), она недействительна.

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

Требуемые усилия

Время, необходимое для вычисления такого хеш-коллизии, составляет экспоненциальный с количеством нулевых битов. Таким образом, можно добавлять нулевые биты (удваивая количество времени, необходимое для вычисления хэша с каждым дополнительным нулевым битом), пока спамерам не станет слишком дорого создавать действительные строки заголовков.

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

Преимущества и недостатки

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

С другой стороны, поскольку Hashcash требует, чтобы потенциально значительные вычислительные ресурсы затрачивались на каждое отправляемое электронное письмо, довольно сложно настроить идеальное количество среднего времени, в течение которого клиенты должны потратить на вычисление действительного заголовка. Это может означать отказ от доступности из-за низкого уровня. встроенные системы или же существует риск того, что враждебные хосты не будут иметь достаточной защиты, чтобы обеспечить эффективный фильтр от спама.

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

Один правдоподобный анализ[5] пришли к выводу, что вероятен только один из следующих случаев: либо электронная почта, не являющаяся спамом, застрянет из-за недостаточной вычислительной мощности отправителя, либо спам-электронная почта обязательно будет проходить. Примеры каждого включают, соответственно, централизованную топологию электронной почты (например, список рассылки ), в котором какой-то сервер должен отправлять огромное количество законный электронные письма и ботнеты или кластерные фермы, с помощью которых спамеры могут значительно увеличить свою вычислительную мощность.

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

Другая предполагаемая проблема заключается в том, что компьютеры продолжают работать быстрее, Закон Мура. Так что сложность требуемых расчетов со временем должна возрасти. Однако можно ожидать, что развивающиеся страны будут использовать устаревшее оборудование, а это означает, что им будет все труднее участвовать в системе электронной почты. Это также относится к людям с низким доходом в развитых странах, которые не могут позволить себе новейшее оборудование.

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

Приложения

Биткойн майнинг

В отличие от хэш-кеша в почтовых приложениях, где получатели вручную устанавливают объем работы, предназначенный для сдерживать злонамеренные отправители, Биткойн криптовалютная сеть использует другой на основе хеширования доказательство работы вызов включить конкурентный биткойн майнинг. Биткойн-майнер запускает компьютерную программу, которая собирает неподтвержденные транзакции от торговцев монетами в сети. С другими данными они могут формировать блок и приносить вознаграждение майнеру, но блок принимается сетью только тогда, когда майнер обнаруживает методом проб и ошибок а "nonce" число, которое при включении в блок дает хеш с достаточным количеством начальных нулевых битов, чтобы соответствовать целевой сложности сети. Блоки, принимаемые от майнеров, формируют биткойн блокчейн это растущий реестр каждой биткойн-транзакции с момента первого создания монеты.

В то время как hashcash использует хэш SHA-1 и требует, чтобы первые 20 из 160 битов хеширования были равны нулю, в доказательстве работы биткойна используются два последовательных SHA-256 хеши и изначально требуемые по меньшей мере первые 32 из 256 хеш-битов равны нулю. Однако сеть биткойнов периодически сбрасывает уровень сложности, чтобы средняя скорость создания блоков составляла 6 в час. По состоянию на январь 2020 г. блок №614525 сеть биткойнов отреагировала на развертывание майнером все более быстрого оборудования для хеширования, ужесточив требование, чтобы первые 74 из 256 хеш-битов были равны нулю.

Спам-фильтры

Hashcash используется как потенциальное решение для ложные срабатывания с автоматизированными системами фильтрации спама, так как законные пользователи редко будут испытывать неудобства из-за дополнительного времени, необходимого для добычи штампа.[6] SpamAssassin может проверять отметки Hashcash, начиная с версии 2.70, присваивая отрицательную оценку (т.е. менее вероятно, что это спам) для действительных неизрасходованных отметок Hashcash. Однако, хотя плагин hashcash изначально не включен по умолчанию, он все равно должен быть настроен со списком шаблонов адресов, которые должны совпадать с полем ресурса Hashcash, поэтому он фактически не работает по умолчанию.

Почтовые клиенты

Программный проект Penny Post[7] на SourceForge реализует Hashcash в Mozilla Thunderbird почтовый клиент.[8] Проект назван в честь исторической доступности обычных почтовых услуг, которые обходятся отправителю всего в один пенни; видеть Пенни Пост для информации о таких почтовых услугах в истории.

Почтовый штемпель

Microsoft также разработала и внедрила устаревший[9] открытая спецификация, похожая на Hashcash, но несовместимая с ней, Email Postmark,[10] в рамках их инициативы по сокращению спама (CSRI).[11] Вариант Hashcash для почтовых марок электронной почты Microsoft реализован в компонентах почтовой инфраструктуры Microsoft Exchange, Outlook и Hotmail. Различия в форматах между Hashcash и почтовыми марками Microsoft заключаются в том, что почтовая марка хеширует тело помимо получателя и использует измененный SHA-1 в качестве хеш-функции и использует несколько подзадач, чтобы уменьшить дисперсию доказательства работы.

Блоги

Как электронная почта, блоги часто становятся жертвой спам в комментариях.Некоторые владельцы блогов использовали скрипты hashcash, написанные на JavaScript язык, чтобы замедлить спамеров комментариев.[12] Некоторые сценарии (например, wp-hashcash) утверждают, что реализуют hashcash, но вместо этого зависят от обфускации JavaScript, чтобы заставить клиента сгенерировать соответствующий ключ; хотя для этого требуется некоторая вычислительная мощность, он не использует алгоритм хеш-кэширования или штампы хэш-кеша.

Интеллектуальная собственность

Hashcash не запатентован, а эталонная реализация[13] а большинство других реализаций - бесплатное программное обеспечение. Hashcash включен или доступен для многих Дистрибутивы Linux.

RSA передала IETF заявления IPR о проблемах клиентов.[14] в контексте RFC[15] которые описывают клиентские головоломки (не hashcash). RFC включал hashcash в заголовок и ссылался на hashcash, но описанный в нем механизм представляет собой интерактивную задачу с известным решением, которая больше похожа на Client-Puzzles; hashcash не интерактивен и поэтому не имеет известного решения. В любом случае инструкция RSA IPR не может применяться к hashcash, потому что hashcash предшествует[1] (Март 1997 г.) публикация "Пазлы для клиентов"[16] (Февраль 1999 г.) и патентная заявка US7197639.[17] (Февраль 2000 г.).

Смотрите также

Примечания

  1. ^ а б «Схема почтовых услуг на основе частичного хеш-коллизии» (Текст). Hashcash.org. Получено 13 октября 2014.
  2. ^ "Hashcash - противодействие отказу в обслуживании" (PDF). hashcash.org. 1 августа 2002 г.. Получено 2 января 2019.
  3. ^ Дворк, Синтия; Наор, Мони (18 мая 2001 г.). «Ценообразование посредством обработки или борьбы с нежелательной почтой». Достижения в криптологии - Crypto '92. Конспект лекций по информатике. Springer. 740: 139–147. Дои:10.1007/3-540-48071-4_10. ISBN  978-3-540-57340-1.
  4. ^ "hashcash - средство противодействия спаму / отказу в обслуживании hashcash" (Текст). Hashcash.org. Получено 13 октября 2014.
  5. ^ "Документ, подтверждающий работу Hashcash" (PDF). Hashcash.org. Получено 13 октября 2014.
  6. ^ «Часто задаваемые вопросы о Hashcash». Hashcash.org. 26 июня 2003 г.. Получено 11 февраля 2014.
  7. ^ «Программный проект Penny Post на SourceForge». Pennypost.sourceforge.net. Получено 13 октября 2014.
  8. ^ «Penny Post: Что вы имеете в виду под почтовой маркой?». Pennypost.sourceforge.net. 16 июня 2008 г.. Получено 11 февраля 2014.
  9. ^ «Снятые с производства и измененные функции в Outlook 2010». Office.microsoft.com. Получено 13 октября 2014.
  10. ^ "Алгоритм проверки почтовых марок" (PDF). Download.microdoft.com. Получено 13 октября 2014.
  11. ^ «Инициатива по согласованному сокращению спама: предложение по технологиям и политике» (PDF). Архивировано из оригинал (PDF) 21 октября 2013 г.. Получено 11 февраля 2014.
  12. ^ WP-Hashcash, плагин для программного обеспечения блогов Wordpress В архиве 2005-10-27 на Wayback Machine который реализует средство, подобное Hashcash, написанное на JavaScript Эллиоттом Бэком
  13. ^ "Эталонная реализация C". hashcash.org. Получено 13 октября 2014.
  14. ^ «RSA Security Inc. подала заявку на патент (серийный номер США 09/496 824)» (Текст). Ietf.org. Получено 13 октября 2014.
  15. ^ "Вычислительные головоломки SIP". Tools.ietf.org. Получено 13 октября 2014.
  16. ^ "Пазлы для клиентов" (PDF). Получено 13 октября 2014.
  17. ^ "Подача патента на головоломку клиента". Получено 13 октября 2014.

Рекомендации

  • Адам Бэк, "Hashcash - A Denial of Service Counter-Measure", технический отчет, август 2002 г. (PDF).
  • Бен Лори и Ричард Клейтон, «Доказательство работы» не работает », WEIS 04. (PDF).
  • Дворк, К. и Наор, М. (1992) «Ценообразование посредством обработки нежелательной почты или борьбы с ней», Crypto '92, стр. 139–147. (PDF)

внешняя ссылка