Hashcash - это система доказательства работы, используемая для ограничения спама в электронной почте и атак типа «отказ в обслуживании» , а в последнее время стала известна своим использованием в биткойнах (и других криптовалютах ) как части алгоритма майнинга. Hashcash был предложен в 1997 году Адамом Бэком [1] и более формально описан в статье Бэка 2002 года «Hashcash - противодействие отказу в обслуживании». [2]
Задний план
Идея «... требовать от пользователя вычисления умеренно сложной, но не трудноразрешимой функции ...» была предложена Синтией Дворк и Мони Наор в их статье 1992 года «Ценообразование посредством обработки или борьбы с нежелательной почтой». [3]
Как это работает
Hashcash - это алгоритм доказательства работы на основе криптографического хэша, который требует выбора объема работы для вычисления, но доказательство может быть эффективно проверено. При использовании электронной почты текстовое кодирование штампа хэш-кеша добавляется к заголовку сообщения электронной почты, чтобы доказать, что отправитель потратил умеренное количество процессорного времени на расчет штампа перед отправкой электронной почты. Другими словами, поскольку отправителю потребовалось определенное время для создания штампа и отправки электронного письма, маловероятно, что он является спамером. Получатель может с незначительными вычислительными затратами проверить действительность штампа. Однако единственный известный способ найти заголовок с необходимыми свойствами - это перебор случайных значений, пока не будет найден ответ; хотя проверить отдельную строку легко, удовлетворительные ответы достаточно редки, и для поиска ответа потребуется значительное количество попыток.
Гипотеза состоит в том, что спамеры, чья бизнес-модель основана на их способности отправлять большое количество электронных писем с очень небольшой стоимостью за сообщение, перестанут быть прибыльными, если будет взиматься даже небольшая плата за каждый рассылаемый ими спам. Получатели могут проверить, вложил ли отправитель такие деньги, и использовать результаты для фильтрации электронной почты.
Технические подробности
Строка заголовка выглядит примерно так: [4]
X-Hashcash: 1: 20: 1303030600: [email protected] :: McMybZIhxKXu57jd: ckvi
Заголовок содержит:
- ver : версия формата Hashcash, 1 (заменяет версию 0).
- биты : количество битов «частичного предварительного изображения» (ноль) в хешированном коде.
- дата : время отправки сообщения в формате
YYMMDD[hhmm[ss]]
. - ресурс : передаваемая строка данных ресурса , например IP-адрес или адрес электронной почты.
- ext : Расширение (необязательно; игнорируется в версии 1).
- rand : строка случайных символов, закодированная в формате base-64 .
- counter : двоичный счетчик, закодированный в формате base-64.
Заголовок содержит адрес электронной почты получателя, дату сообщения и информацию, подтверждающую, что требуемые вычисления были выполнены. Наличие адреса электронной почты получателя требует, чтобы для каждого получателя вычислялся отдельный заголовок. Дата позволяет получателю записывать заголовки, полученные недавно, и гарантировать, что заголовок уникален для сообщения электронной почты.
Сторона отправителя
Отправитель подготавливает заголовок и добавляет значение счетчика, инициализированное случайным числом. Затем он вычисляет 160-битный хэш SHA-1 заголовка. Если первые 20 битов (т. Е. 5 наиболее значимых шестнадцатеричных цифр) хеш-функции все нули, то это приемлемый заголовок. В противном случае отправитель увеличивает счетчик и снова пытается получить хеш. Из 2160 возможных хеш-значений есть 2140 хеш-значений, которые удовлетворяют этому критерию. Таким образом, вероятность случайного выбора заголовка, который будет иметь 20 нулей в качестве начала хеша, составляет 1 из 2 20 (примерно 10 6 , или примерно один из миллиона). Количество попыток отправителя получить допустимое значение хеш-функции моделируется геометрическим распределением . Следовательно, отправителю в среднем придется пробовать 2 20 значений, чтобы найти действительный заголовок. Учитывая разумные оценки времени, необходимого для вычисления хэша, его поиск может занять около секунды. Известно, что нет более эффективного метода поиска допустимого заголовка, чем этот метод грубой силы.
Обычный пользователь настольного ПК не будет испытывать значительных неудобств из-за времени обработки, необходимого для генерации строки Hashcash. Однако спамеры значительно пострадают из-за большого количества отправляемых ими спамерских сообщений.
Сторона получателя
Технически система реализована со следующими этапами:
- Компьютер получателя вычисляет 160-битный хэш SHA-1 всей строки (например, ). Это занимает около двух микросекунд на машине с частотой 1 ГГц, что намного меньше времени, необходимого для получения остальной части электронного письма. Если первые 20 бит не все равны нулю, хеш недействителен. (Более поздние версии могут потребовать большего количества битов для обнуления по мере увеличения скорости машинной обработки.)
"1:20:060408:[email protected]::1QTjaYd7niiQA/sc:ePa"
- Компьютер получателя проверяет дату в заголовке (например
"060408"
, которая представляет дату 8 апреля 2006 г.). Если он не в течение двух дней после текущей даты, он недействителен. (Двухдневное окно компенсирует перекос часов и время сетевой маршрутизации между разными системами.) - Компьютер получателя проверяет, соответствует ли адрес электронной почты в строке хэша любому из допустимых адресов электронной почты, зарегистрированных получателем, или соответствует ли он любому из списков рассылки, на которые подписан получатель. Если совпадение не найдено, хеш-строка недействительна.
- Компьютер получателя вставляет хеш-строку в базу данных. Если строка уже находится в базе данных (указывая, что предпринимается попытка повторно использовать строку хеширования), она недействительна.
Если хеш-строка проходит все эти тесты, она считается действительной хеш-строкой. Все эти тесты занимают гораздо меньше времени и места на диске, чем получение основного содержимого электронного письма.
Требуемые усилия
Время, необходимое для вычисления такого хеш-коллизии, экспоненциально зависит от количества нулевых битов. Таким образом, можно добавлять нулевые биты (удваивая количество времени, необходимое для вычисления хэша с каждым дополнительным нулевым битом), пока спамерам не станет слишком дорого создавать допустимые строки заголовков.
Подтверждение того, что заголовок действителен, происходит намного быстрее и всегда занимает одинаковое количество времени, независимо от того, сколько нулевых битов требуется для действительного заголовка, поскольку для этого требуется только одна операция хеширования.
Преимущества и недостатки
Система Hashcash имеет преимущество перед предложениями по микроплатежам, применяемыми к законной электронной почте, в том, что не используются реальные деньги. Ни отправителю, ни получателю не нужно платить, таким образом, полностью устраняются административные проблемы, связанные с любой системой микроплатежей, и моральные вопросы, связанные с взиманием платы за электронную почту.
С другой стороны, поскольку Hashcash требует затрат потенциально значительных вычислительных ресурсов на каждое отправляемое электронное письмо, довольно сложно настроить идеальное количество среднего времени, в течение которого клиенты должны потратить на вычисление действительного заголовка. Это может означать принесение в жертву встроенных систем начального уровня или риск того, что враждебные хосты не будут иметь достаточной защиты, чтобы обеспечить эффективный фильтр от спама.
Hashcash также довольно просто реализовать в почтовых пользовательских агентах и фильтрах спама. Центральный сервер не требуется. Hashcash можно развертывать постепенно - дополнительный заголовок Hashcash игнорируется, когда он получен почтовыми клиентами, которые его не понимают.
Один правдоподобный анализ [5] пришел к выводу, что вероятен только один из следующих случаев: либо электронная почта, не являющаяся спамом, застрянет из-за недостаточной вычислительной мощности отправителя, либо электронная почта со спамом обязательно будет проходить. Примеры каждого включают, соответственно, централизованную топологию электронной почты (например, список рассылки ), в которой некоторый сервер должен отправлять огромное количество законных сообщений электронной почты, и ботнеты или кластерные фермы, с помощью которых спамеры могут значительно увеличить свою вычислительную мощность. .
Большинство из этих проблем можно решить. Например, бот-сети могут истекать быстрее, потому что пользователи замечают высокую загрузку ЦП и принимают контрмеры, а серверы списков рассылки могут быть зарегистрированы в белых списках на хостах подписчиков и, таким образом, избавлены от проблем с хеш-кешем. Но они представляют собой серьезные препятствия для развертывания hashcash, которые еще предстоит устранить. [ необходима цитата ]
Другая предполагаемая проблема заключается в том, что компьютеры продолжают работать быстрее в соответствии с законом Мура . Таким образом, сложность требуемых расчетов со временем должна возрасти. Однако можно ожидать, что развивающиеся страны будут использовать устаревшее оборудование, а это означает, что им будет все труднее участвовать в системе электронной почты. Это также относится к людям с низким доходом в развитых странах, которые не могут позволить себе новейшее оборудование.
Как и hashcash, криптовалюты используют хеш-функцию в качестве своей системы доказательства работы. Рост криптовалюты создал спрос на майнинговые машины на базе ASIC . Хотя большинство криптовалют используют хэш-функцию SHA-256 , та же технология ASIC может использоваться для создания решателей хэш-кеша, которые на три порядка быстрее, чем ЦП потребителя, что снижает вычислительные трудности для спамеров.
Приложения
Биткойн майнинг
В отличие от хэш- кеша в почтовых приложениях, которые полагаются на то, что получатели вручную устанавливают объем работы, предназначенный для сдерживания злонамеренных отправителей, сеть криптовалюты Биткойн использует другую задачу доказательства работы на основе хешей, чтобы обеспечить конкурентоспособный майнинг биткойнов . Биткойн-майнер запускает компьютерную программу, которая собирает неподтвержденные транзакции от пользователей в сети. Вместе они могут образовывать «блок» и приносить вознаграждение майнеру, но блок принимается сетью только в том случае, если его хэш соответствует целевой сложности сети. Таким образом, как и в случае с хеш-кешем , майнеры должны с помощью грубой силы обнаружить «одноразовый номер», который при включении в блок дает приемлемый хэш.
В отличие от hashcash, цель сложности Биткойна не указывает минимальное количество ведущих нулей в хеш-коде. Вместо этого хеш интерпретируется как (очень большое) целое число, и это целое число должно быть меньше целевого целого числа. Это необходимо, потому что сеть Биткойн должна периодически корректировать свой уровень сложности, чтобы поддерживать среднее время 10 минут между последовательными блоками. Если бы учитывались только ведущие нули, то сложность можно было бы только удвоить или уменьшить вдвое, что привело бы к значительному перерегулированию или недооценке в ответ на небольшие изменения среднего времени блока. Тем не менее, количество ведущих нулей в цели служит хорошим приближением к текущей сложности. В январе 2020 года в блоке 614525 было 74 ведущих нуля.
Спам-фильтры
Hashcash используется в качестве потенциального решения для ложных срабатываний с помощью автоматизированных систем фильтрации спама, поскольку легальные пользователи редко будут испытывать неудобства из-за дополнительного времени, необходимого для добычи штампа. [6] SpamAssassin может проверять отметки Hashcash, начиная с версии 2.70, присваивая отрицательную оценку (т.е. менее вероятно, что это спам) для действительных неизрасходованных отметок Hashcash. Однако, хотя плагин hashcash изначально не включен по умолчанию, он все равно должен быть настроен со списком шаблонов адресов, которые должны совпадать с полем ресурса Hashcash, поэтому он фактически не работает по умолчанию.
Почтовые клиенты
Программный проект Penny Post [7] на SourceForge реализует Hashcash в почтовом клиенте Mozilla Thunderbird . [8] Проект назван в честь исторической доступности традиционных почтовых услуг, которые обходятся отправителю всего в один пенни; см. Penny Post для получения информации о таких почтовых услугах в истории.
Почтовый штемпель по электронной почте
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], в котором описаны клиентские головоломки (не хэш-кэш). RFC включал hashcash в заголовок и ссылался на hashcash, но описанный в нем механизм представляет собой интерактивную задачу с известным решением, которая больше похожа на Client-Puzzles; hashcash не интерактивен и поэтому не имеет известного решения. В любом случае заявление RSA о правах интеллектуальной собственности не может применяться к hashcash, потому что hashcash предшествовал [1] (март 1997 г.) публикации «client-puzzles» [16] (февраль 1999 г.) и патенту US7197639 [17] (февраль 2000 г.).
Смотрите также
- Пенни Блэк (исследовательский проект)
Заметки
- ^ a b «Схема почтовых отправлений на основе частичных коллизий хешей» (Txt) . Hashcash.org . Проверено 13 октября 2014 года .
- ^ «Hashcash - Противодействие отказу в обслуживании» (PDF) . hashcash.org. 1 августа 2002 . Проверено 2 января 2019 .
- ^ Дворк, Синтия; Наор, Мони (18 мая 2001 г.). «Ценообразование посредством обработки или борьбы с нежелательной почтой» . Достижения в криптологии - Crypto '92 . Конспект лекций по информатике. Springer. 740 : 139–147. DOI : 10.1007 / 3-540-48071-4_10 . ISBN 978-3-540-57340-1.
- ^ "hashcash - средство противодействия спаму / отказу в обслуживании hashcash" (Txt) . Hashcash.org . Проверено 13 октября 2014 года .
- ^ «Документ с подтверждением работы Hashcash» (PDF) . Hashcash.org . Проверено 13 октября 2014 года .
- ^ «Часто задаваемые вопросы по Hashcash» . Hashcash.org. 26 июня 2003 . Проверено 11 февраля 2014 .
- ^ «Программный проект Penny Post на SourceForge» . Pennypost.sourceforge.net . Проверено 13 октября 2014 года .
- ^ "Penny Post: Что вы имеете в виду под почтовой маркой?" . Pennypost.sourceforge.net. 16 июня 2008 . Проверено 11 февраля 2014 .
- ^ «Снятые с производства и измененные функции в Outlook 2010» . Office.microsoft.com . Проверено 13 октября 2014 года .
- ^ «Алгоритм проверки почтовых марок» (PDF) . Download.microdoft.com . Проверено 13 октября 2014 года .
- ^ «Скоординированная инициатива по сокращению спама: предложение по технологиям и политике» (PDF) . Архивировано из оригинального (PDF) 21 октября 2013 года . Проверено 11 февраля 2014 .
- ^ WP-Hashcash, плагин для программного обеспечения блога Wordpress. Архивировано 27 октября 2005 г. на Wayback Machine, которое реализует средство, подобное Hashcash, написанное на JavaScript, Эллиотт Бэк.
- ^ «Эталонная реализация C» . hashcash.org . Проверено 13 октября 2014 года .
- ^ «RSA Security Inc. подала заявку на патент (серийный номер США 09/496 824)» (Txt) . Ietf.org . Проверено 13 октября 2014 года .
- ^ "Вычислительные головоломки SIP" . Tools.ietf.org . Проверено 13 октября 2014 года .
- ^ «Пазлы для клиентов» (PDF) . Проверено 13 октября 2014 года .
- ^ «Подача патента на головоломку клиента» . Проверено 13 октября 2014 года .
Рекомендации
- Адам Бэк, «Hashcash - противодействие отказу в обслуживании», технический отчет, август 2002 г. (PDF) .
- Бен Лори и Ричард Клейтон, «Доказательство работы» не работает », WEIS 04. (PDF) .
- Дворк, К. и Наор, М. (1992) «Ценообразование посредством обработки нежелательной почты или борьбы с ней», Crypto '92, стр. 139–147. (PDF)
Внешние ссылки
- Домашняя страница Hashcash
- Избавьтесь от спама с помощью hashcash Статья Дэвида Мертца о hashcash, его приложениях и реализации на Python
- Записка RSA IPR для IETF о hashcash (2004 г.)