Hashcash

Hashcash — система доказу виконання роботи, яку використовують для зменшення обсягів спаму і DoS-атак. Пізніше знайшла використання в bitcoin та інших криптовалютах, як частина алгоритму аналізу даних. Система Hashcash була запропонована в травні 1997 року Адамом Беком.

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

Hashcash — це алгоритм доказу виконаної роботи, що вимагає вибіркового обсягу даних для обчислень, але при цьому доказ може бути ефективно підтверджено.

У користувачів електронної пошти до заголовка додається текстова закодована позначка hashcash, що підтверджує, що перед відправленням було витрачено деякий час для обчислення позначки. Іншими словами, відправник витрачає деякий час на обчислення позначки і відправлення, що невластиво спамерам. Отримувач може ціною невеликих обчислювальних потужностей підтвердити правильність позначки.

Єдиний відомий спосіб підібрати заголовок з необхідними параметрами — це повний перебір.

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

Технічні деталі

Закодована позначка має такий вигляд:

X-Hashcash

1:20:1303030600:[email protected]::McMybZIhxKXu57jd: FOvXX

Заголовок містить:

• ver: Версію hashcash, тут версія 1 (яка прийшла на заміну версії 0).
• bits: Кількість нульових бітів в хешованому коді.
• date: Час відправлення повідомлення.
• resource: Реквізити відправника, наприклад IP-адреса або адреса email.
• ext: Розширення (не обов'язкове, ігнорується у версії 1).
• rand: Рядок випадкового числа в форматі Base64.
• counter: Двійковий лічильник, закодований в форматі Base64.

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

На боці відправника

Відправник готує заголовок і додає до нього випадкове число. Потім, він обчислює 160-бітний SHA-1 хеш заголовка. Якщо перші 20 біт заголовка — нулі, то цей заголовок прийнятний. В іншому випадку, відправник збільшує випадкове число і пробує ще раз. З 2¹⁶⁰ можливих значень хешу, 2¹⁴⁰ задовольняють цьому критерію. Таким чином, ймовірність того, що випадково обраний хеш буде починатися з 20 нулів, — 1 до 2²⁰. Кількість спроб, які відправник змушений спробувати, перш ніж отримає валідне значення хешу, моделюється геометричним розподілом. Отже, відправник у середньому повинен спробувати 2²⁰ (трохи більше мільйона) випадкових чисел, щоб знайти правильний заголовок. Враховуючи розумні оцінки часу, необхідного для обчислення хешу, це займе близько 1 секунди. У той же час, немає ефективного методу пошуку валідного заголовка, крім перебору.

Звичайний користувач ПК не буде відчувати значних проблем через часу, необхідного на генерацію рядки hashcash. На противагу цьому, розсилання великої кількості листів (спаму) одночасно стає проблематичним через суттєво вищу витрату енергії на кожен лист.

На боці одержувача

Технічно, система реалізована такими наступними кроками: Комп'ютер одержувача розраховує 160-бітний SHA-1 хеш цілого рядка (наприклад, «1: 20: 060 408: [email protected] :: 1QTjaYd7niiQA / sc: ePa»). Це займає близько двох мікросекунд на 1ГГц процесорі, що набагато менше, ніж час, необхідний на завантаження решти e-mail повідомлення. Якщо перші 20 біт ненульові, хеш є недійсним (в останніх версіях може знадобитися більше число нульових бітів, тому що обчислювальні потужності ростуть). Комп'ютер одержувача перевіряє дату в заголовку (наприклад, «060408», що означає 8 квітня 2006). Якщо різниця з поточною датою більше двох днів, хеш є недійсним (дводенне вікно компенсує різницю в часі, а також час переміщення по мережі між різними системами).

Комп'ютер одержувача перевіряє, чи збігається e-mail в рядку хешу з яким-небудь e-mail адресою, зареєстрованим одержувачем, або з будь-якою адресою зі списку тих, на які одержувач підписаний. Якщо збіги відсутні, хеш є недійсним. Комп'ютер одержувача додає хеш-рядок в базу даних. Якщо такий рядок вже присутній в базі (тим самим, з'ясовується, що відбулася спроба заново використовувати хеш-рядок), хеш є недійсним. Якщо хеш-рядок пройшов всі тести, він вважається валідним. Всі ці тести не займають великої кількості часу і місця на диску в порівнянні з отриманням основної частини e-mail листа.

Необхідні витрати

Час, необхідний на обчислення подібних колізій хешу, експоненціально зростає із збільшенням числа нульових бітів. Тобто нульові біти можуть додаватися до тих пір, поки створення нових валідних хеш-рядків не стане занадто дорогим для спамерів (подвоюючи час, необхідний на обчислення хешу кожним додатковим нулем). Підтвердження того, що заголовок валідний, вимагає однакового часу. При цьому неважливо, скільки нулів необхідно для валідного заголовка, тому що потрібна лише одна операція хешування.

Переваги і недоліки

Система hashcash має перевагу перед мікроплатежнимі пропозиціями, застосовуваними до електронної пошти, тому що не припускає залучення реальних грошей. Ні відправник, ні одержувач не повинні платити. Таким чином, всі адміністративні питання, пов'язані з мікроплатежами, є неактуальними.

З іншого боку, hashcash вимагає значних обчислювальних ресурсів, що використовуються при відправленні кожного повідомлення (це може становити проблему, наприклад, для вбудованих (embedded) систем, що не мають достатньої обчислювальної потужності). Досить складно вдало підібрати середній час, який клієнти готові витрачати на обчислення заголовка.

Hashcash досить просто реалізувати для користувальницьких поштових агентів і спам-фільтрів. Не потрібна наявність центрального сервера. Впровадження системи може бути здійснено крок за кроком: додатковий заголовок hashcash ігнорується, коли він отриманий поштовим клієнтом, що не розуміють його.

У одному з аналізів системи hashcash було зроблено висновок, що лише один з наступних сценаріїв є імовірним: або пошта буде застрягати через брак обчислювальної потужності відправника, або спам все одно буде проходити. Приклади кожного включають, відповідно, централізовану топологію електронної пошти (наприклад, список розсилки), в якому деяким серверам потрібно відправити величезну кількість законною електронної пошти; і бот-мережі або кластерні ферми, використовуючи які спамери можуть суттєво збільшити свою потужність обробки. Більшість з цих проблем можуть бути вирішені. Наприклад, бот-мережі можуть виявлятися швидше, тому що користувачі можуть помітити високе навантаження на процесор і вжити відповідних контр-заходів. Сервери, що реалізують масове (законне) розсилання, можуть бути зареєстровані в білих списках (white lists) одержувачів. Але, в цілому, вони являють собою серйозні перешкоди для розгортання Hashcash, які ще належить вирішити.

Ще одна прогнозована проблема полягає в тому, що комп'ютери продовжують нарощувати потужність відповідно до закону Мура. Таким чином, складність обчислень повинна з часом збільшуватися. Тим не менш, країни, що розвиваються, найімовірніше продовжать використовувати старе обладнання, що означає, що вони можуть відчувати труднощі при користуванні електронною поштою з системою Hashcash. Це також стосується осіб з низьким рівнем доходів у розвинених країнах, які не можуть дозволити собі новітнє обладнання.

Застосування

Bitcoin mining

Hashcash концептуально схожий з системами перевірки правильності, використовуваними в bitcoin. Якщо в поштових застосуваннях передбачається, що одержувач вручну контролює обсяг робіт систем перевірки правильності роботи для виграшу в обчислювальній потужності по закону Мура, то bitcoin представляє p2p мережу, яка внутрішньо автоматично регулює обсяг робіт. Також, на відміну від пошти, де використовуються 20 біт (близько 1 млн спроб для успішного пошуку), bitcoin використовує 67,5 біт (необхідно близько 200 млн трильйонів спроб), щоб аналізувати блок, що включає близько 25 біткоіни, які виробляються кожні 10 хвилин. Bitcoin скорегували алгоритм, додавши підтримку роботи з частками біт (первісна специфікація HashCash обмежувалася коригуванням цілих ступенів числа 2). Тим самим вдалося досягти більш високої точності.

Фільтри спаму

Hashcash використовується як потенційне рішення проблеми помилкового спрацьовування автоматичних спам-фільтрів, так як звичайний користувач не відчуває проблем з додатковим часом, необхідним для позначки.

SpamAssassin перевіряє наявність відміток hashcash починаючи з версії 2.70, привласнюючи негативні бали (тобто вважає менш схожим на спам) невикористаним раніше позначок hashcash. У версії 3.3x (остання версія на момент написання), система дає бонусні бали для будь-яких 20-бітних і більш відміток (максимум, -5 балів для 26-бітних і більш відміток). Однак, за вже використану позначку записується невеликий штраф.

Email Postmark

Microsoft також спроектували і реалізували нині застарілу відкриту специфікацію, аналогічну hashcash, але несумісну з нею — Email Postmark, що стала частиною Coordinated Spam Reduction Initiative (CSRI). Варіант hashcash, запропонований Microsoft реалізований в компонентах поштових сервісів Microsoft, таких як Exchange, Outlook і Hotmail. Різниця у форматі між відмітками hashcash і Microsoft в тому, що відмітка Microsoft хешує також основну частину листа, а також використовує модифікований SHA-1 як хеш-функцію.

Блоги

Вельми схожим чином, блоги стають жертвами спаму в коментарях. Деякі власники блогів використовували hashcash скрипти, написані на JavaScript, щоб уповільнити коментарі спамерів. Деякі скрипти (такі, як wp-hashcash) претендують на реалізацію Hashcash але залежать від заплутування засобами JavaScript, змушуючи клієнта генерувати відповідний ключ; в той час як це вимагає деякої обчислювальної потужності, вони не використовують алгоритм Hashcash або Hashcash позначки.

Інтелектуальна власність

Hashcash не запатентована еталонна реалізація і більшість інших реалізацій є вільно поширюваним ПЗ. Hashcash включений або доступний для багатьох дистрибутивів Linux. RSA зробив IPR заяви в IETF про client-puzzles алгоритмах в контексті RFC, описуючому різні client-puzzles (Не hashcash). RFC включив hashcash в статтю і згадав алгоритм, але механізм, описаний в ній вирішує швидше інтерактивну задачу, яка більше схожа на Client-Puzzles. Hashcash НЕ інтерактивний і, отже, не має відомих рішень. У кожному разі, IPR твердження RSA не може бути застосоване до hashcash, оскільки hashcash передує (березень 1997) публікації Client-puzzle (лютий 1999) та патентній заявці US7197639 (лютий 2000).

Див. також

• DMARC
• Електронна пошта

Посилання

• http://hashcash.org/ [Архівовано 29 вересня 2017 у Wayback Machine.]
• https://web.archive.org/web/20160304110657/http://www.ietf.org/ietf-ftp/IPR/rsa-ipr-draft-jennings-sip-hashcash-00.txt