Хэшкэш
Hashcash — это система доказательства работы , используемая для ограничения спама в электронной почте и атак типа «отказ в обслуживании» . Hashcash был предложен в 1997 году Адамом Бэком. [1] и более формально описан в статье Бэка 2002 года «Hashcash — меры противодействия отказу в обслуживании». [2] В Hashcash клиент должен несколько раз объединить случайное число со строкой и хэшировать эту новую строку. Затем ему приходится делать это снова и снова, пока не будет найден хеш, начинающийся с определенного количества нулей. [3]
Фон
[ редактировать ]Идея «... потребовать от пользователя вычисления умеренно сложной, но вполне разрешимой функции...» была предложена Синтией Дворк и Мони Наор в их статье 1992 года «Ценообразование посредством обработки или борьбы с нежелательной почтой». [4]
Как это работает
[ редактировать ]Hashcash — это криптографический алгоритм доказательства работы на основе хэша, для вычисления которого требуется определенный объем работы, но доказательство можно эффективно проверить. электронного письма добавляется текстовая кодировка штампа hashcash, При использовании электронной почты к заголовку чтобы доказать, что отправитель потратил небольшое количество процессорного времени на расчет штампа перед отправкой электронного письма. Другими словами, поскольку отправителю потребовалось определенное время для создания штампа и отправки электронного письма, маловероятно, что он является спамером. Получатель может с незначительными вычислительными затратами проверить подлинность штампа. Однако единственный известный способ найти заголовок с необходимыми свойствами — это перебор случайных значений, пока не будет найден ответ; хотя тестирование отдельной строки несложно, удовлетворительные ответы встречаются настолько редко, что для поиска ответа потребуется значительное количество попыток.
Гипотеза состоит в том, что спамеры, чья бизнес-модель основана на их способности отправлять большое количество электронных писем с очень низкой стоимостью одного сообщения, перестанут быть прибыльными, если за каждый отправленный ими спам придется платить хотя бы небольшую стоимость. Получатели могут проверить, сделал ли отправитель такие инвестиции, и использовать результаты для фильтрации электронной почты.
Технические детали
[ редактировать ]Строка заголовка выглядит примерно так: [5]
X-Hashcash: 1:20:1303030600:[email protected]::McMybZIhxKXu57jd:ckvi
Заголовок содержит:
- ver : версия формата Hashcash, 1 (которая заменяет версию 0).
- биты : количество битов «частичного прообраза» (нулевых) в хеш-коде.
- дата : время отправки сообщения в формате
YYMMDD[hhmm[ss]]. - ресурс : передаваемая строка данных ресурса, например, IP-адрес или адрес электронной почты.
- ext : Расширение (необязательно; игнорируется в версии 1).
- rand : строка случайных символов, закодированная в формате base-64 .
- счетчик : двоичный счетчик, закодированный в формате Base-64.
Заголовок содержит адрес электронной почты получателя, дату сообщения и информацию, подтверждающую, что необходимые вычисления были выполнены. Наличие адреса электронной почты получателя требует, чтобы для каждого получателя вычислялся отдельный заголовок. Дата позволяет получателю записывать недавно полученные заголовки и гарантировать, что заголовок уникален для сообщения электронной почты.
Сторона отправителя
[ редактировать ]Отправитель подготавливает заголовок и добавляет значение счетчика, инициализированное случайным числом. Затем он вычисляет 160-битный SHA-1 хэш заголовка. Если все первые 20 битов (т. е. 5 старших шестнадцатеричных цифр) хеша — нули, то это приемлемый заголовок. Если нет, то отправитель увеличивает счетчик и снова пытается хешировать. из 2 160 возможные значения хеша, их 2 140 хеш-значения, удовлетворяющие этому критерию. Таким образом, вероятность случайного выбора заголовка, который будет иметь 20 нулей в начале хеша, равна 1 из 2. 20 (ок. 10 6 или примерно один на миллион). Количество раз, которое отправителю необходимо попытаться получить допустимое значение хеш-функции, моделируется геометрическим распределением . Следовательно, отправителю в среднем придется попробовать 2 20 значения, чтобы найти действительный заголовок. Учитывая разумные оценки времени, необходимого для вычисления хеша, на его поиск уйдет около одной секунды. Неизвестно более эффективного метода поиска действительного заголовка, чем этот метод грубой силы.
Обычный пользователь настольного ПК не будет испытывать значительных неудобств из-за времени обработки, необходимого для генерации строки Hashcash. Однако спамеры существенно пострадают из-за большого количества отправленных ими спам-сообщений.
Сторона получателя
[ редактировать ]Технически система реализуется в следующие этапы:
- Компьютер получателя вычисляет 160-битный SHA-1 хэш всей строки (например,
"1:20:060408:[email protected]::1QTjaYd7niiQA/sc:ePa"). На машине с частотой 1 ГГц это занимает около двух микросекунд, что намного меньше времени, чем время, необходимое для получения остальной части электронной почты. Если первые 20 бит не все равны нулю, хэш недействителен. (В более поздних версиях может потребоваться больше битов, равных нулю, поскольку скорость обработки машины увеличивается.) - Компьютер получателя проверяет дату в заголовке (например,
"060408", что соответствует дате 8 апреля 2006 г.). Если дата не позднее двух дней с текущей даты, она недействительна. (Двудневное окно компенсирует рассогласование часов и время сетевой маршрутизации между различными системами.) - Компьютер получателя проверяет, соответствует ли адрес электронной почты в хэш-строке какому-либо из действительных адресов электронной почты, зарегистрированных получателем, или любому из списков рассылки, на которые подписан получатель. Если совпадение не найдено, хэш-строка недействительна.
- Компьютер получателя вставляет хеш-строку в базу данных. Если строка уже находится в базе данных (что указывает на попытку повторного использования хэш-строки), она недействительна.
Если хеш-строка проходит все эти тесты, она считается допустимой хеш-строкой. Все эти тесты занимают гораздо меньше времени и дискового пространства, чем получение основного содержимого электронного письма.
Требуемые усилия
[ редактировать ]Время, необходимое для вычисления такой коллизии хэшей, экспоненциально зависит от количества нулевых битов. Таким образом, можно добавлять дополнительные нулевые биты (удваивая время, необходимое для вычисления хеша с каждым дополнительным нулевым битом), пока спамерам не станет слишком дорого генерировать действительные строки заголовка.
Подтверждение правильности заголовка происходит намного быстрее и всегда занимает одинаковое количество времени, независимо от того, сколько нулевых битов требуется для допустимого заголовка, поскольку для этого требуется только одна операция хеширования.
Преимущества и недостатки
[ редактировать ] | Этот раздел нуждается в дополнительных цитатах для проверки . ( Август 2010 г. ) |
Система Hashcash имеет преимущество перед предложениями микроплатежей , применимыми к законной электронной почте, поскольку при этом не используются реальные деньги. Ни отправителю, ни получателю не нужно платить, поэтому полностью исключаются административные проблемы, связанные с любой системой микроплатежей, и моральные проблемы, связанные с взиманием платы за электронную почту.
С другой стороны, поскольку Hashcash требует затрат потенциально значительных вычислительных ресурсов на каждое отправляемое электронное письмо, довольно сложно настроить идеальное среднее время, которое клиенты должны тратить на вычисление действительного заголовка. Это может означать, что придется пожертвовать доступностью недорогих встроенных систем или рискнуть тем, что враждебные хосты не смогут обеспечить эффективный фильтр от спама.
Hashcash также довольно просто реализовать в почтовых пользовательских агентах и спам-фильтрах. Центральный сервер не требуется. Hashcash можно развертывать постепенно — дополнительный заголовок Hashcash игнорируется, когда он получен почтовыми клиентами, которые его не понимают.
Один правдоподобный анализ [6] пришел к выводу, что вероятен только один из следующих случаев: либо электронная почта, не являющаяся спамом, застрянет из-за недостаточной вычислительной мощности отправителя, либо спамовая электронная почта обязательно все равно пройдет. Примеры каждого из них включают, соответственно, централизованную топологию электронной почты (например, список рассылки ), в которой некий сервер должен отправлять огромное количество законных электронных писем, а также ботнеты или кластерные фермы, с помощью которых спамеры могут значительно увеличить свою вычислительную мощность. .
Большинство из этих проблем можно решить. Например, ботнеты могут исчезнуть быстрее, потому что пользователи замечают высокую нагрузку на процессор и принимают контрмеры, а серверы списков рассылки могут быть зарегистрированы в белых списках на хостах подписчиков и, таким образом, избавлены от проблем с хеш-кэшем.
Другая прогнозируемая проблема заключается в том, что компьютеры продолжают работать быстрее в соответствии с законом Мура . Таким образом, сложность требуемых вычислений должна со временем увеличиваться. Однако можно ожидать, что развивающиеся страны будут использовать старое оборудование, а это означает, что им будет все труднее участвовать в системе электронной почты. Это также относится к людям с низкими доходами в развитых странах, которые не могут позволить себе новейшее оборудование.
Как и hashcash, криптовалюты используют хэш-функцию в качестве системы доказательства работы. Рост популярности криптовалют создал спрос на машины для майнинга на базе ASIC . Хотя большинство криптовалют используют хеш-функцию SHA-256 , ту же самую технологию ASIC можно использовать для создания решателей хеш-кэша, которые на три порядка быстрее потребительских процессоров, что снижает вычислительные трудности для спамеров.
Приложения
[ редактировать ]Майнинг биткойнов
[ редактировать ]В отличие от hashcash в почтовых приложениях, которые полагаются на то, что получатели вручную устанавливают объем работы, предназначенный для сдерживания злонамеренных отправителей, сеть криптовалюты Биткойн использует другую доказательства работы задачу на основе хэша, чтобы обеспечить конкурентоспособный майнинг биткойнов . Майнер биткойнов запускает компьютерную программу, которая собирает неподтвержденные транзакции от пользователей в сети. Вместе они могут сформировать «блок» и принести майнеру оплату, но блок принимается сетью только в том случае, если его хэш соответствует целевому уровню сложности сети. Таким образом, как и в случае с hashcash, майнеры должны методом перебора обнаружить «nonce» , который, будучи включенным в блок, приводит к приемлемому хешу.
В отличие от hashcash, целевая сложность Биткойна не определяет минимальное количество ведущих нулей в хеше. Вместо этого хеш интерпретируется как (очень большое) целое число, и это целое число должно быть меньше целевого целого числа. Это необходимо, поскольку сеть Биткойн должна периодически корректировать уровень сложности, чтобы поддерживать среднее время между последовательными блоками 10 минут. Если бы учитывались только ведущие нули, то сложность можно было бы только удвоить или уменьшить вдвое, что привело бы к значительному превышению или понижению корректировки в ответ на небольшие изменения среднего времени блока. Тем не менее, количество ведущих нулей в цели служит хорошим приближением к текущей сложности. В январе 2020 года в блоке №614525 было 74 ведущих нуля.
Спам-фильтры
[ редактировать ]Hashcash использовался в качестве потенциального решения проблемы ложных срабатываний с помощью автоматизированных систем фильтрации спама, поскольку законные пользователи редко будут испытывать неудобства из-за дополнительного времени, которое требуется для майнинга штампа. [7] SpamAssassin мог проверять наличие марок Hashcash начиная с версии 2.70 до версии 3.4.2, присваивая отрицательную оценку (т. е. с меньшей вероятностью спама) действительным, неизрасходованным маркам Hashcash. Однако, хотя плагин hashcash включен по умолчанию, его все равно необходимо настроить со списком шаблонов адресов, которые должны соответствовать полю ресурса Hashcash, прежде чем он будет использоваться. [8] SpamAssassin Поддержка была удалена из ствола 26 июня 2019 г., что затронуло версию 3.4.3 и последующие версии. [9]
Почтовые клиенты
[ редактировать ]Программный проект Penny Post [10] на SourceForge реализует Hashcash в почтовом клиенте Mozilla Thunderbird . [11] Проект назван в честь исторической доступности традиционных почтовых услуг, которые обходились отправителю всего в один цент; см. Penny Post для получения информации о таких почтовых службах в истории.
Почтовый штемпель электронной почты
[ редактировать ]Microsoft также разработала и внедрила устаревшую версию [12] открытая спецификация под названием «Почтовый штемпель электронной почты». Это похоже на Hashcash. [13] Это было частью инициативы Microsoft по скоординированному сокращению спама (CSRI). [14] Вариант почтового штемпеля Microsoft для Hashcash реализован в компонентах почтовой инфраструктуры Microsoft Exchange, Outlook и Hotmail. Различия в формате между Hashcash и почтовым штемпелем электронной почты Microsoft заключаются в том, что почтовый штемпель хеширует не только получателя, но и тело письма, использует модифицированный SHA-1 в качестве хеш-функции и использует несколько подзагадок для уменьшения отклонений в доказательстве работы.
Блоги
[ редактировать ]Как и электронная почта, блоги часто становятся жертвами спама в комментариях . Некоторые владельцы блогов использовали скрипты hashcash, написанные на языке JavaScript , чтобы замедлить работу спамеров в комментариях. [15] Некоторые скрипты (например, wp-hashcash) утверждают, что реализуют hashcash, но вместо этого зависят от обфускации JavaScript, чтобы заставить клиента сгенерировать соответствующий ключ; хотя для этого требуется определенная вычислительная мощность, он не использует алгоритм hashcash или штампы hashcash.
Репутация
[ редактировать ]На цифровом рынке поставщики услуг могут использовать hashcash для создания репутации и привлечения клиентов. Чтобы создать репутацию, поставщик услуг сначала выбирает открытый ключ в качестве своего идентификатора, а затем методом перебора обнаруживает одноразовый номер, который при объединении с идентификатором приводит к получению хеш-дайджеста с несколькими ведущими нулями. Чем больше нулей, тем выше репутация. [16]
Интеллектуальная собственность
[ редактировать ]Hashcash не запатентован, а эталонная реализация [17] и большинство других реализаций являются свободными программами. Hashcash включен или доступен для многих дистрибутивов Linux .
RSA сделала IETF заявление о защите прав интеллектуальной собственности по поводу клиентских головоломок [18] в контексте RFC [19] там описаны клиентские головоломки (не hashcash). RFC включил hashcash в заголовок и упомянул hashcash, но описанный в нем механизм представляет собой интерактивную задачу с известным решением, которая больше похожа на Client-Puzzles; hashcash неинтерактивен и поэтому не имеет известного решения. В любом случае заявление RSA о защите прав интеллектуальной собственности не может применяться к hashcash, поскольку hashcash появился раньше. [1] (март 1997 г.) издание клиентских головоломок. [20] (февраль 1999 г.) и заявка на патент US7197639 на клиентские головоломки. [21] (февраль 2000 г.).
См. также
[ редактировать ]Примечания
[ редактировать ]- ^ Jump up to: а б «Схема почтовых отправлений на основе частичной коллизии хэшей» (Txt) . Hashcash.org . Проверено 13 октября 2014 г.
- ^ «Hashcash — меры противодействия отказу в обслуживании» (PDF) . hashcash.org. 1 августа 2002 года . Проверено 2 января 2019 г.
- ^ https://www.csc.kth.se/utbildning/kth/kurser/DD143X/dkand12/Group5Mikael/final/Jonatan_Landsberg_and_Anton_Lundqvist.pdf
- ^ Дворк, Синтия; Наор, Мони (18 мая 2001 г.). «Ценообразование посредством обработки или борьбы с нежелательной почтой». Достижения криптологии — КРИПТО' 92 . Конспекты лекций по информатике. Том. 740. Спрингер. стр. 139–147. дои : 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.org. 26 июня 2003 года . Проверено 11 февраля 2014 г.
- ^ «Mail::SpamAssassin::Plugin::Hashcash — выполнить тесты проверки hashcash» . spamassassin.apache.org . Проверено 11 ноября 2021 г.
- ^ «Ошибка 7728 — Удаление поддержки HashCash из магистрали» . Проверено 22 сентября 2023 г.
- ^ «Проект программного обеспечения Penny Post на SourceForge» . Pennypost.sourceforge.net . Проверено 13 октября 2014 г.
- ^ «Пенни Пост: Что вы подразумеваете под почтовой маркой?» . Pennypost.sourceforge.net. 16 июня 2008 г. Архивировано из оригинала 19 февраля 2014 г. Проверено 11 февраля 2014 г.
- ^ «Функции, прекращенные и измененные в Outlook 2010» . Office.microsoft.com . Проверено 13 октября 2014 г.
- ^ «Алгоритм проверки почтового штемпеля электронной почты» (PDF) . скачать.microsoft.com . Проверено 13 октября 2014 г.
- ^ «Инициатива по скоординированному сокращению спама: предложение по технологии и политике» (PDF) . Архивировано из оригинала (PDF) 21 октября 2013 года . Проверено 11 февраля 2014 г.
- ^ WP-Hashcash, плагин для программного обеспечения для блогов Wordpress. Архивировано 27 октября 2005 г. на Wayback Machine , который реализует функцию, подобную Hashcash, написанную на JavaScript Эллиотом Бэком.
- ^ Рахимпур, Сонбол; Хаббазян, Маджид (3 мая 2021 г.). «Испорченная репутация с применением при проектировании сторожевых вышек» . Международная конференция IEEE по блокчейну и криптовалюте (ICBC) 2021 года . IEEE. стр. 1–9. arXiv : 2012.10825 . дои : 10.1109/icbc51069.2021.9461123 . ISBN 978-1-6654-3578-9 . S2CID 229340600 .
- ^ «Эталонная реализация 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, его приложениях и реализации на Python
- Примечание RSA IPR для IETF о hashcash (2004 г.)