해시캐시

Hashcash

해시캐시는 이메일 스팸과 서비스 거부 공격을 제한하기 위해 사용되는 업무 증명 시스템이며, 최근에는 채굴 알고리즘의 일부로 비트코인(및 기타 암호화폐)에 사용하는 것으로 더 많이 알려져 있다. 해시캐시는 1997년 애덤 백에[1] 의해 제안되었고, 백의 2002년 논문 "해시캐시 - 서비스 거부 대응 조치"[2]에 더 공식적으로 기술되었다.

배경

"...사용자에게 적당히 어렵지만 다루기 어려운 기능을 계산하도록 요구하는 아이디어...신시아 드워크와 모니 나오르가 1992년 논문 "정크 메일 처리 또는 퇴치하는 것을 통한 프라이싱"[3]에서 제안한 바 있다.

작동 방식

해시캐시는 암호 해시 기반 작업증명 알고리즘으로, 계산에 선택 가능한 양의 작업이 필요하지만, 증명서를 효율적으로 검증할 수 있다. 전자 메일 사용의 경우, 전자 메일 헤더에 해시캐시 스탬프의 텍스트 인코딩이 추가되어 발신인이 전자 메일을 보내기 전에 스탬프를 계산하는 데 약간의 CPU 시간을 소비했음을 증명한다. 다시 말해 발신인이 우표를 생성해 이메일을 보내는 데 일정 시간이 걸린 만큼 스팸 발송자일 가능성은 낮다는 것이다. 수신자는 아주 적은 계산 비용으로 스탬프가 유효한지 확인할 수 있다. 그러나 필요한 특성을 가진 헤더를 찾는 유일한 방법은 답이 나올 때까지 무작위 값을 시도하는 짐승 같은 힘이다. 개별 문자열을 테스트하는 것은 쉬우나, 만족스러운 답은 답을 찾기 위해 상당한 수의 노력이 필요할 정도로 드물다.

사업모델이 메시지당 비용이 매우 적은 다수의 이메일을 보내는 능력에 의존하는 스팸 발송자들은 보내는 스팸마다 적은 비용이 든다면 수익성이 정지될 것이라는 가설이다. 수신자는 송신자가 그러한 투자를 했는지 여부를 확인하고 그 결과를 사용하여 이메일을 필터링할 수 있다.

기술적 세부사항

머리글 선은 다음과 같다.[4] 

X-Hashcash: 1:20:13030600:anni@cypherspace.org::McMybZIhxKXU57jd:ckvi

헤더에는 다음이 포함된다.

  • ver: 해시캐시 형식 버전, 1(버전 0을 대체함).
  • 비트: 해시 코드의 "부분 사전 이미지"(0) 비트 수입니다.
  • 날짜: 메시지가 전송된 시간 형식 YYMMDD[hhmm[ss]].
  • 리소스: 전송 중인 리소스 데이터 문자열(예: IP 주소 또는 이메일 주소)
  • ext: 확장(옵션, 버전 1에서 무시됨).
  • rand: base-64 형식으로 인코딩된 임의 문자 문자열.
  • 카운터: base-64 형식으로 인코딩된 이진 카운터.

헤더에는 수신자의 이메일 주소, 메시지 날짜, 필요한 계산이 수행되었음을 증명하는 정보가 포함되어 있다. 수신자의 전자 메일 주소가 존재하려면 각 수신자에 대해 다른 헤더를 계산해야 한다. 날짜는 수신인이 최근에 수신한 헤더를 기록하고 헤더가 전자 메일 메시지에 고유한지 확인할 수 있도록 허용한다.

발송인측

송신자는 헤더를 준비하고, 초기화 된 카운터 값을 무작위 번호로 추가한다. 그런 다음 헤더의 160비트 SHA-1 해시를 계산한다. 해시의 처음 20비트(즉, 가장 유의한 5개의 16진수)가 모두 0이면 이는 허용 가능한 헤더다. 그렇지 않은 경우, 발신인은 카운터를 증가시키고 해시를 다시 시도한다. 가능한 해시 값 2개160 중 이 기준을 충족하는 해시 값이 2개140 있다. 따라서 해시의 시작에 따라 0이 20개인 헤더를 무작위로 선택할 확률은 2의20 1 in 2(약 10 또는6 100만분의 1)이다. 송신자가 유효한 해시 값을 얻기 위해 노력해야 하는 횟수는 기하 분포에 의해 모델링된다. 따라서 송신자는 유효한 헤더를 찾기 위해 평균 2개의20 값을 시도해야 한다. 해시를 계산하는 데 필요한 시간의 합리적인 추정치를 고려할 때, 이것은 찾는 데 약 1초가 걸릴 것이다. 이 흉포한 힘 접근법보다 더 효율적인 방법은 유효한 헤더를 찾는 것으로 알려져 있다.

데스크톱 PC의 일반 사용자는 해시캐시 문자열을 생성하는 데 필요한 처리 시간 때문에 큰 불편을 겪지 않을 것이다. 하지만 스팸메일 발송자가 많아 스팸메일 발송자가 크게 피해를 볼 것으로 보인다.

수취인측

기술적으로 이 시스템은 다음 단계를 통해 구현된다.

  • 수신자의 컴퓨터가 전체 문자열의 160비트 SHA-1hash를 계산한다(예: "1:20:060408:anni@cypherspace.org::1QTjaYd7niiQA/sc:ePa"이 작업은 1GHz 머신에서 약 2마이크로초가 소요되며, 나머지 전자우편을 수신하는 데 걸리는 시간보다 훨씬 짧은 시간이다. 처음 20비트가 모두 0이 아니면 해시는 무효다. (더 느린 버전은 기계 처리 속도가 증가함에 따라 더 많은 비트가 0이 되어야 할 수 있다.)
  • 수신자의 컴퓨터는 헤더에서 날짜를 확인한다(예: "060408"2006년 4월 8일을 나타낸다. 현재 날짜로부터 2일 이내에 있지 않으면 무효다. (2일 창은 서로 다른 시스템 간의 클럭 스큐와 네트워크 라우팅 시간을 보상한다.)
  • 수신인의 컴퓨터는 해시 문자열의 전자우편 주소가 수신인이 등록한 유효한 전자우편 주소와 일치하는지 또는 수신인이 가입한 메일 목록과 일치하는지 여부를 확인한다. 일치하는 항목을 찾지 못하면 해시 문자열이 유효하지 않다.
  • 수신자의 컴퓨터는 해시 문자열을 데이터베이스에 삽입한다. 문자열이 이미 데이터베이스에 있는 경우(해시 문자열을 재사용하려고 시도 중임을 나타냄) 유효하지 않다.

해시 문자열이 이러한 테스트를 모두 통과하면 유효한 해시 문자열로 간주된다. 이 모든 테스트는 이메일의 본문 내용물을 받는 것보다 훨씬 적은 시간과 디스크 공간이 필요하다.

필요한 노력

이러한 해시 충돌 계산에 필요한 시간은 0비트 숫자에 지수적이다. 따라서 스팸 발송자가 유효한 헤더 라인을 생성하기에 너무 비용이 많이 들 때까지 0비트를 추가(각 추가 0비트로 해시를 계산하는 데 필요한 시간을 두 배로 늘림)할 수 있다.

헤더가 유효한지 확인하는 것은 해싱 연산을 한 번만 하면 되기 때문에 유효한 헤더의 0비트가 아무리 많이 필요하더라도 훨씬 빠르고 항상 같은 시간이 걸린다.

장단점

해시캐시 시스템은 실제 돈이 개입되지 않는다는 합법적인 이메일에 적용되는 소액결제 제안보다 유리하다. 송신자와 수신자 모두 지불할 필요가 없으므로 소액결제 시스템과 관련된 행정 문제와 전자우편 요금 청구와 관련된 도덕적 문제는 전적으로 회피된다.

반면, 해시캐시는 보내는 각 이메일에 잠재적으로 유의미한 계산 자원을 지출해야 하기 때문에, 고객이 유효한 헤더에 컴퓨팅을 소비하기를 원하는 평균 시간의 이상적인 양을 조정하기는 다소 어렵다. 이는 로우엔드 임베디드 시스템으로부터의 접근성을 희생시키거나 또는 적대적인 호스트가 스팸으로부터 효과적인 필터를 제공할 만큼 충분히 도전받지 않는 위험을 실행한다는 것을 의미할 수 있다.

해시캐시는 메일 사용자 에이전트와 스팸 필터에서도 구현이 꽤 간단하다. 중앙 서버가 필요하지 않다. 해시캐시는 점진적으로 배치될 수 있다. 추가 해시캐시 헤더는 그것을 이해하지 못하는 메일 클라이언트에 의해 수신될 때 무시된다.

한 그럴듯한 분석은[5] 다음 중 한 가지 사례만 있을 가능성이 높다고 결론 내렸다: 보낸 사람의 처리 능력 부족으로 인해 스팸 메일이 막히거나, 스팸 메일이 여전히 통과될 수밖에 없다. 각각의 예로는, 각각 일부 서버가 엄청난 양의 합법적인 전자 메일을 보내는 중앙집중식 전자 메일 토폴로지(메일 목록과 같은)와 스팸 발송자가 처리 능력을 엄청나게 높일 수 있는 봇넷 또는 클러스터 팜이 있다.

이 문제들의 대부분은 다루어질 수 있다. 예를 들어 봇넷은 사용자가 높은 CPU 부하를 알아차리고 대응 조치를 취하기 때문에 더 빨리 만료될 수 있으며, 메일링 목록 서버는 가입자의 호스트의 화이트리스트에 등록되어 해시캐시 과제에서 벗어날 수 있다. 그러나 그것들은 여전히 해결해야 할 해시캐시 배치에 심각한 장애물을 나타낸다.[citation needed]

또 다른 예상된 문제는 무어의 법칙에 따라 컴퓨터가 계속해서 빨라진다는 것이다. 따라서 필요한 계산의 난이도는 시간이 지남에 따라 증가해야 한다. 그러나 개발도상국들은 오래된 하드웨어를 사용하게 될 것으로 예상할 수 있는데, 이는 그들이 이메일 시스템에 참여하는 것이 점점 더 어려워질 것이라는 것을 의미한다. 이는 최신 하드웨어를 구입할 여유가 없는 선진국의 저소득 개인에게도 적용된다.

해시캐시와 마찬가지로, 암호화폐는 해시함수를 업무 증명 시스템으로 사용한다. 암호화폐의 상승으로 ASIC 기반 채굴기에 대한 수요가 생겨났다. 대부분의 가상화폐가 SHA-256 해시함수를 사용하지만 동일한 ASIC 기술을 사용해 소비자 CPU보다 3배 빠른 크기의 해시캐시솔러를 만들 수 있어 스팸메일 발송자의 계산 장애물이 줄어들었다.

적용들

비트코인 채굴

수신인에 의존해 악의적인 송신자를 저지하기 위한 작업량을 수동으로 설정하는 메일 어플리케이션의 해시캐시와는 대조적으로 비트코인 암호화폐 네트워크는 경쟁적인 비트코인 채굴을 가능하게 하기 위해 해시 기반의 작업 증명 과제를 다르게 채택하고 있다. 비트코인 광부가 네트워크상에서 사용자들로부터 확인되지 않은 거래를 수집하는 컴퓨터 프로그램을 운영한다. 이들 블록은 함께 "블록"을 형성하여 광부에게 지불할 수 있지만, 블록은 그것의 해시가 네트워크의 난이도 목표를 충족시키는 경우에만 네트워크에 의해 받아들여진다. 따라서 해시캐시(hashcash)에서와 마찬가지로 광부들은 블록에 포함될 때 허용되는 해시가 되는 "noce"를 무력으로 발견해야 한다.

해시캐시와는 달리 비트코인의 난이도 대상은 해시에 최소 선행 0을 명시하지 않는다. 대신 해시는 (매우 큰) 정수로 해석되며, 이 정수는 목표 정수보다 작아야 한다. 비트코인 네트워크가 주기적으로 난이도 조절을 해야 연속 블록 간 평균 10분을 유지할 수 있기 때문이다. 선행 0만 고려한다면 난이도가 2배 또는 반감될 수 있어 평균 블록 시간의 작은 변화에 대응하여 조정이 크게 오버슈트 또는 언더슈팅될 수 있다. 그래도 대상의 선행 0 수는 현재 난이도의 좋은 근사치로 작용한다. 2020년 1월 블록 #614525는 선행 0이 74개였다.

스팸 필터

해시캐시는 자동화된 스팸 필터링 시스템으로 잘못된 긍정의 잠재적인 해결책으로 사용되는데, 합법적인 사용자들은 우표를 채굴하는 데 소요되는 추가 시간으로 인해 거의 불편을 겪지 않을 것이기 때문이다.[6] SpamAssin은 버전 2.70부터 해시캐시 스탬프를 확인할 수 있었고, 유효하고, 낭비되지 않는 해시캐시 스탬프에 대해 음수 점수(즉, 스팸일 가능성이 낮음)를 할당했다. 그러나 해시캐시 플러그인은 기본적으로 설정되어 있지만, 사용하기 전에 해시캐시 리소스 필드와 일치해야 하는 주소 패턴의 목록으로 구성할 필요가 있다.[7]

클라이언트 전자 메일 보내기

SourceForge의 Penny Post 소프트웨어 프로젝트는[8] Mozilla Thunderbird 이메일 클라이언트에서 해시캐시를 구현한다.[9] 이 프로젝트는 발신자에게 단 1페니만 지불하는 전통적인 우편 서비스의 과거 이용가능성을 위해 명명되었다. 이러한 우편 서비스에 대한 정보는 Penny Post를 참조하라.

전자우편 소인

Microsoft는 또한 CSRI(Coorded Spam Reduction Initiative)의 일환으로 해시캐시, Email Postmark와 유사하지만 호환되지 않는 현재 사용되지[10] 않는 개방형 사양을 설계 및 구현했다.[11][12] 해시캐시의 마이크로소프트 이메일 소인 변형은 마이크로소프트 메일 인프라 구성 요소인 Exchange, 아웃룩 및 Hotmail에서 구현된다. 해시캐시와 마이크로소프트의 이메일 소인의 형식 차이는 소인이 수신인 외에 본체를 해시하고, 수정된 SHA-1을 해시함수로 사용하고 여러 개의 서브 퍼즐을 사용하여 작업 분산 증빙을 줄인다는 것이다.

블로그

이메일과 마찬가지로 블로그도 스팸 댓글의 희생양이 되는 경우가 많다. 일부 블로그 소유자들은 JavaScript 언어로 작성된 해시캐시 스크립트를 사용하여 댓글 스팸 발송자의 속도를 줄였다.[13] 일부 스크립트(wp-hashcash 등)는 해시캐시를 구현한다고 주장하지만, 대신 클라이언트에게 일치하는 키를 생성하도록 강요하기 위해 자바스크립트 난독화에 의존한다. 그러나 이것은 약간의 처리 능력을 필요로 하지만, 해시캐시 알고리즘이나 해시캐시 스탬프를 사용하지 않는다.

지적 재산.

해시캐시는 특허를 받지 않았으며, 참조 구현과[14] 다른 구현의 대부분은 무료 소프트웨어다. 해시캐시는 많은 Linux 배포에 포함되거나 이용 가능하다.

RSA는 (해시캐시가 아닌) 클라이언트-퍼즐을 설명한 RFC의[16] 맥락에서 클라이언트-퍼즐에[15] 대한 IPR 진술을 IETF에 제출하였다. RFC는 제목에 해시캐시를 포함시켰고 참조된 해시캐시를 포함시켰지만, 여기서 설명하는 메커니즘은 클라이언트-퍼즐과 더 유사한 알려진 솔루션 쌍방향 도전이다. 해시캐시는 상호 작용하지 않기 때문에 알려진 해결책을 가지고 있지 않다. 어떤 경우든 RSA의 IPR 문장은 해시캐쉬가 클라이언트-퍼즐 출판물[17](1997년 3월)보다[1] 앞서기 때문에(1999년 2월) 해시캐시에 적용할 수 없으며, 클라이언트-퍼즐 특허 출원[18] US7197639(2000년 2월)는 해시캐시에 적용할 수 없다.

참고 항목

메모들

  1. ^ a b "A partial hash collision based postage scheme" (Txt). Hashcash.org. Retrieved 13 October 2014.
  2. ^ "Hashcash - A Denial of Service Counter-Measure" (PDF). hashcash.org. 1 August 2002. Retrieved 2 January 2019.
  3. ^ Dwork, Cynthia; Naor, Moni (18 May 2001). "Pricing via Processing or Combatting Junk Mail". Advances in Cryptology - Crypto '92. Lecture Notes in Computer Science. Springer. 740: 139–147. doi:10.1007/3-540-48071-4_10. ISBN 978-3-540-57340-1.
  4. ^ "hashcash - hashcash anti-spam / denial of service counter-measure tool" (Txt). Hashcash.org. Retrieved 13 October 2014.
  5. ^ "Hashcash proof-of-work paper" (PDF). Hashcash.org. Retrieved 13 October 2014.
  6. ^ "Hashcash FAQ". Hashcash.org. 26 June 2003. Retrieved 11 February 2014.
  7. ^ "Mail::SpamAssassin::Plugin::Hashcash - perform hashcash verification tests". spamassassin.apache.org. Retrieved 11 November 2021.
  8. ^ "Penny Post software project on SourceForge". Pennypost.sourceforge.net. Retrieved 13 October 2014.
  9. ^ "Penny Post: What do you mean by Postage Stamp?". Pennypost.sourceforge.net. 16 June 2008. Retrieved 11 February 2014.
  10. ^ "Discontinued features and modified functionality in Outlook 2010". Office.microsoft.com. Retrieved 13 October 2014.
  11. ^ "Email Postmark Validation Algorithm" (PDF). Download.microdoft.com. Retrieved 13 October 2014.
  12. ^ "The Coordinated Spam Reduction Initiative: A Technology and Policy Proposal" (PDF). Archived from the original (PDF) on 21 October 2013. Retrieved 11 February 2014.
  13. ^ WP-Hashcash, Wordpress 블로그 소프트웨어의 플러그인 Eliott Back이 JavaScript로 작성한 해시캐시와 유사한 시설을 구현하는 웨이백 머신에 2005-10-27 보관
  14. ^ "C reference implementation". hashcash.org. Retrieved 13 October 2014.
  15. ^ "RSA Security Inc. has submitted a patent application (US Serial No. 09/496,824)" (Txt). Ietf.org. Retrieved 13 October 2014.
  16. ^ "SIP Computational Puzzles". Tools.ietf.org. Retrieved 13 October 2014.
  17. ^ "Client Puzzles" (PDF). Retrieved 13 October 2014.
  18. ^ "Client-puzzle patent filing". Retrieved 13 October 2014.

참조

  • Adam Back, 2002년 8월 기술 보고서(PDF) "해시캐시 - 서비스 거부 대응 측정"
  • Ben Laurie와 Richard Clayton, "Proof-of-Work"이 효과가 없음을 증명한다, WEIS 04. (PDF)
  • Dwork, C. 및 Naor, M.(1992) "정크 메일 처리 또는 격투를 통한 제조", Crypto '92, 페이지 139–147(PDF)

외부 링크