CertCoin: A NameCoin Based Decentralized Authentication System 6.857 Class Project 한글번역 진행중.
1 Abstract
인증은 모든 형태의 원격 통신에 필수적입니다. 인증의 부재는 중간자 공격 (man-in-the-middle attack)의 문을 열어 주며, 핵심 순간에 수행된다면 전체 상호 작용을 파괴 할 수 있습니다. 현재 인터넷 인증 방식에는 인증 기관 및 신뢰 웹이 포함됩니다. 이러한 접근법은 모두 중요한 단점이 있습니다. 전자는 신뢰할 수있는 제 3 자에게 의존하여 중앙 실패 지점을 도입하고, 후자는 진입 장벽이 높습니다. Certcoin은 대체, 공개 및 분산 인증 방식을 제안합니다. Certcoin의 핵심 아이디어는 도메인 및 관련 공개 키의 공개 원장을 유지하는 것입니다. Certcoin 구성표와 스마트 폰과 같이 제한된 저장 용량을 갖춘 장치에서 Certcoin을보다 쉽게 사용할 수 있도록 여러 가지 최적화 방법을 설명합니다. 우리의 최적화는 암호화 누적 기 및 분산 해시 테이블과 같은 도구를 사용합니다.
2 Existing Approaches to Authentication
1976 년에 공개 키 암호가 출현하기 전에는 대부분의 보안 메시지 전송이 이전에 일부 비밀 키 K를 공유 한 두 당사자 모두에게 의존하는 대칭 암호화 프로토콜을 사용하여 수행되었습니다. 공격자가 비밀 키를 추측 할 가능성은 매우 낮기 때문에 이 구조에서 인증은 간단합니다. K로 암호화 된 모든 개별 메시지는 인증 된 사용자로 간주됩니다. 그러나 통신하기 전에 키를 교환하는 것은 많은 수의 엔티티가 네트워크에 자유롭게 가입하고 탈퇴 할 수 있어야하며 네트워크상의 다른 엔티티와 안전하게 통신 할 수 있어야하는 인터넷과 같은 동적 환경에서는 비실용적입니다. 엔티티들의 수가 증가함에 따라 각 쌍의 엔티티가 자신의 공유 키를 빠르게 설정하는 것은 실행 불가능하게된다 [11].
공개 키 암호화는이 확장 성 문제를 해결합니다. ; 그러나 인증은 훨씬 간단합니다. 전통적인 공개 키 시스템에서 사용자는 메시지 수신자의 공개 키를 검색하고 해당 키로 암호화 한 다음 자체 서명 키로 메시지에 서명합니다. 그러면 수신자는 메시지를 해독 할 수있는 유일한 사람입니다. 그 사람은 비밀 암호 해독 키를 가진 유일한 소유자이기 때문입니다. 이 설정은 사전 키 협약의 필요성을 없애 주지만, 모든 엔티티가 이제 암호화를 생성 할 수 있기 때문에 발신자를 인증해야하는 문제가 발생합니다. 그는 디지털 서명을 기반으로 보낸 사람의 공개 키를 확인할 수 있지만 보낸 사람의 신원을 결정하기 위해 공개 키만 사용할 수는 없습니다 [21].
PKI (Public Key Infrastructure) 개념은 메시지 보낸 사람의 신원을 확인해야하는 필요성에서 비롯되었습니다. PKI는 일반적으로 각 개체의 공개 키를 증명하는 인증서를 발급합니다. 또한 PKI는 비밀 키가 유실되었거나 관련 개인이 악의적 인 것으로 간주 될 때 공개 키가 손상된 경우 인증서를 해지 할 수 있습니다. 현재 가장 일반적으로 사용되는 두 가지 접근 방식은 중앙 집중식의 신뢰할 수있는 제 3 자 인증 기관 (CA)과 종종 피플 - 피어 인증의 분산 네트워크 (Phil Zimmerman의 작성자 인 Phil Zimmerman PGP)
2.1 인증 기관
일반적으로 인증 기관 (CA)은 일반적으로보다 일반적인 선택으로 사용자 네트워크에 대한 디지털 인증서를 제공하고 관리하는 신뢰할 수있는 제 3 자 역할을합니다. 이를 수행하기 위해 CA에는 사용자 신원을 확인하고 Distinguish Name (DN, 예 : Google 또는 Facebook)을 할당하고 DN과 함께 공개 키를 기록하는 일종의 등록 프로세스가 있어야합니다. 이러한 레코드에는 데이터 암호화 또는 서명 확인 여부와 상관없이 키 용도에 대한 표시뿐만 아니라 만료 날짜가 포함됩니다. CA는 두 가지 목적을 수행합니다. 즉, 사용자가 특정 공개 키를 보유하고 사용자에 해당하는 공개 키의 조회를 용이하게하는지 확인하는 것을 용이하게합니다. 검증은 각 사용자에게 발급 된 인증서를 통해 수행됩니다. 그 인증서는 CA가 서명 한 "사용자 x가 공개 키 PK를 보유하고있는"형식의 진술입니다. 조회는 모든 사용자가 다른 개인의 공개 키를 요청하도록 허용하여 수행됩니다. 그런 다음 요청자는 해당 개인과 지식에 대한 지식이 없음을 증명함으로써 개인이 해당 비밀 키를 보유하고 있는지 확인할 수 있습니다. CA는 신뢰할 수있는 사람이 인증서를 신뢰해야하기 때문에 궁극적으로 네트워크 신뢰 에이전트 역할을합니다 [16].
이러한 레코드에는 데이터 암호화 또는 서명 확인 여부와 상관없이 키 용도에 대한 표시뿐만 아니라 만료 날짜가 포함됩니다. CA는 두 가지 목적을 수행합니다. 즉, 사용자가 특정 공개 키를 보유하고 사용자에게 해당하는 공개 키의 조회를 용이하게하는지 확인하는 것을 용이하게합니다. 검증은 각 사용자에게 발급 된 인증서를 통해 수행됩니다. 그 인증서는 CA가 서명 한 "사용자 x가 공개 키 PK를 보유하고있는"형식의 진술입니다. 조회는 모든 사용자가 다른 개인의 공개 키를 요청하도록 허용하여 수행됩니다. 그런 다음 요청자는 해당 개인과 지식에 대한 지식이 없음을 증명함으로써 개인이 해당 비밀 키를 보유하고 있는지 확인할 수 있습니다. CA는 신뢰할 수있는 사람이 인증서를 신뢰해야하기 때문에 궁극적으로 네트워크 신뢰 에이전트 역할을합니다 [16].
많은 엔티티는 비밀 키가 유실 된 경우 안전하게 비밀 키를 백업하고자 할 수 있습니다. 이를 수행하는 프로세스를 키 복구라고하며 오늘날의 많은 CA가 제공하는 기능입니다. 해독 키가 손실되면 민감한 데이터 또는 중요한 데이터가 영구적으로 손실 될 수 있습니다. 다른 한편, 서명 키의 손실은 상대적으로 중요하지 않습니다. 이전에 서명 된 메시지는 여전히 공개 키로 검증 될 수 있으며 (취소되지 않았다고 가정) 사용자는 서명을 계속하기 위해 새 키 쌍을 간단히 얻을 수 있습니다. 또한 CA와 서명 키를 백업하면 CA가 키 소유자로 가장 할 수 있습니다. 따라서 CA가 서명 키가 아닌 암호 해독 키를 백업하는 것이 가장 적합합니다 [13]. 따라서 모든 사용자는 두 기능에 동일한 키 쌍을 사용하는 대신 두 개의 키 쌍 (암호화 및 서명)을 생성해야합니다.
최근에는 너무 많은 신뢰가 CA에 배치되고 있음을 보여주는 수많은 사건이있었습니다. CA는 해킹 당했고 (예 : DigiNotar 사건), 고객 (예 : TrustWave 사건)에 하위 루트 인증서를 발행하여 고객이 자체적으로 인증서를 발급 할 수있게했습니다.
이러한 사고를 방지하기위한 한 가지 방법은 CA의 작업에 투명성을 도입하는 것입니다. Google CertiPate 투명성 프로젝트 [3]는 정확하게 이것을 시도합니다. 그들은 세계적으로 독립된 서버를 숫자 (예 : ≤ 1000)에 대한 공용 추가 전용 로그를 유지할 것을 제안합니다. 이러한 각 로그 서버는 별도의 CA에 의해 실행될 수 있습니다. 그런 다음이 로그는 다른 공개적으로 실행되는 서버에 의해 의심스러운 인증서가 있는지 모니터하고 모든 사람이 실행할 수있는 경량의 감사 소프트웨어로 일관된 동작을 감사합니다. 이렇게하면 도메인의 소유자가 자신의 도메인에 대해 발급 된 모든 인증서를 볼 수있게되어 모든 잘못된 인증서를 발견 할 수 있습니다.
2.2 Web of Trust
실제로 사용되는 두 번째 주요 PKI는 PGP Trust of Web (WoT)입니다. 이 시스템에서는 인증이 완전히 분산되어 있습니다. 사용자는 자신의 공개 키에 서명함으로써 신뢰할 수있는 다른 사람들을 지정할 수 있습니다. 그렇게함으로써 사용자는 자신의 공개 키와 신뢰할 수있는 것으로 간주되는 엔티티의 디지털 서명을 포함하는 인증서를 누적합니다. 그런 다음 인증서는 자신이 신뢰하는 사람의 서명이 포함되어 있는지 확인할 수있는 경우 당사자가 신뢰할 수 있습니다 [21].
이 시스템은 중앙 집중식 장애 지점을 없애기 때문에 분산 된 성격을 활용합니다. 그러나 신원 또는 원격 사용자가 네트워크에 가입하는 것은 일반적으로 신원을 확인하고 공개 키를 처음 서명 한 사람과 만나는 것이 일반적이므로 만나야합니다. 또한 CA와 달리 WoT는 키 복구를 처리 할 방법이 없습니다. 사용자는 개인 키가 분실되거나 손상된 경우 자신의 인증서를 철회하도록 임명 된 다른 사용자를 자신의 "지정된 취소 자"로 선택하는 것으로 제한됩니다. 이러한 변화에도 불구하고, Trust of Web은 상당한 수정없이 거의 25 년 동안 성공적으로 운영되었습니다.
2.3 Certcoin: the Best of Both Worlds
투명한 인증 기관과 웹 신뢰의 장점을 통합 한 시스템 인 Certcoin을 소개합니다. Google CertiPate 투명성 프로젝트와 마찬가지로 Certcoin은 완전히 공개되고 감사가 가능합니다. WoT와 마찬가지로 Certcoin은 분산되어 있으며 단일 실패 지점이 없습니다. 우리는 3 절에서 Certcoin 프로토콜의 세부 사항을 제공합니다.
3 The Fundamental Certcoin Protocol(기본 Certcoin 프로토콜)
Bitcoin을 기반으로 한 새로운 분산 형 공개 키 인프라를 제안합니다. 주어진 신원 또는 도메인에 해당하는 공개 키를 신뢰할 수 있고 영구적으로 게시하는 기능은 인증 방법이 간단합니다. Bitcoin과 다른 cryptocurrencies는 정확히 같은 게시판을 구현합니다.
우리는 Namecoin [2] 위에 프로젝트를 분기하고 CertCoin 트랜잭션이 블록 체인에 제대로 구축되도록 병합 된 마이닝 프로토콜을 활용하여 Certcoin을 구축 할 것을 제안합니다. Namecoin은 .bit 주소에 대한 분산 DNS로 작동하도록 설계된 cryptocurrency입니다. 도메인 등록 및 업데이트를 지원하는 세 가지 유형의 트랜잭션 (이름 신규, 이름 갱신 및 이름 갱신)이 있습니다. 새로운 이름은 일반적으로 Namecoin이 0.01 단위 인 반면 나머지는 무료입니다.
3.1 Registering a Domain with Certcoin(Certcoin으로 도메인 등록)
"온라인" 비밀 키는 웹 사이트를 호스팅하는 서버와주고받는 메시지를 인증하는 데 사용됩니다. 이 비밀 키는 Certcoin에서 웹 사이트를 인증하는 데 사용되는 기본 키이기도합니다. 인증의 일부로 해당 키 지식에 대한 증거가 필요할 것입니다.
"오프라인" 비밀 키는 인터넷에 연결된 장치에 저장된 결과 온라인 키가 직면하게 될 보안 위협과 동일한 보안 위협에 취약하지 않은 안전한 장소에 저장됩니다. 이 기본 키는 보안 위반이나 키 손상의 경우 새 키를 서명하거나 취소하는 데 주로 사용됩니다. 이에 대해서는 4.2 절에서 더 자세히 설명 할 것이다.
도메인에 대해 새 키를 만들면 같은 유형의 이전 키로 서명됩니다. 이렇게하면 언제든지 도메인에 등록 된 두 유효한 키를 일련의 서명 된 문을 통해 도메인에 등록 된 처음 두 키 쌍으로 추적 할 수 있습니다.
3.2 Updating a Public Key Corresponding to a Domain(도메인에 해당하는 공개 키 업데이트)
도메인 d에 해당하는 공개 키 pkold를 새로운 공개 키 pknew (동일한 온라인 / offline 형식)로 변경하는 것은 게시로 수행됩니다.
우리 게시판으로 이동합니다. 여기서 σ는 보안 디지털 서명 알고리즘입니다. 우리는 여기에서 디지털 서명을 활용하여 새로운 공개 키가 이전 공용 키에 해당하는 비밀 키 보유자 만 게시 할 수 있도록합니다. 이 업데이트 트랜잭션은 서명이 pkold로 검증 된 경우에만 처리됩니다.
3.3 Verifying / Looking Up a Public Key(공개 키 확인 / 검색)
공개 또는 온라인 유형의 공개 키 pk가 도메인 d에 해당하는지 확인하는 것은 블록 체인을 탐색하고 다음을 확인하는 것입니다.
• 도메인 d가 정확히 한 번 등록되었습니다.
• d에 해당하는 공개 키에 대한 후속 업데이트의 모든 서명은 d의 이전 공개 키로 검증합니다.
• 마지막 업데이트로 pk가 d에 해당하는 공개 키가되고
• 도메인 d의 소유자라고 주장하는 사용자는 a zero-knowledge proof of knowledge를 사용하여 pk에 해당하는 비밀 키 sk를 알고 있습니다.
도메인 d에 해당하는 공개 키 pk (offline 또는 online 유형 중 하나)를 찾으려면 블록 체인을 탐색하고 다음을 수행해야합니다.
• 도메인 d가 정확히 한 번 등록되었는지 확인합니다.
• d에 해당하는 공개 키에 대한 후속 업데이트의 모든 서명이 이전 공개 키로 검증되었는지 확인합니다.
• d에 해당하는 공개 키에 대한 최종 업데이트를 찾고 업데이트가 발생한 공개 키 pk를 저장합니다.
• 도메인 d의 소유자라고 주장하는 사용자가 지식 지식이없는 지식을 사용하여 pk에 해당하는 비밀 키 sk를 알고 있는지 확인합니다. 제로 지식 지식 지식이 유효한 경우, pk를 리턴하십시오. 그렇지 않으면 ⊥를 돌려 준다.
4 Key Recovery and Revocation(키 복구 및 해지)
완전 기능 인증 시스템은 키 해지 및 복구를위한 일부 기능을 제공해야합니다. 특정 비밀 키가 손상되거나 도난 당하거나 단순히 만료 될 수 있습니다.이 경우 키 소유자는 이전 키를 폐기하고 새 키를 가져와야합니다. 마찬가지로 암호는 잊어 버릴 수 있으며 특정 복구 방법이 필요할 수 있습니다. 전통적인 인증 기관 시스템에서는 이러한 목적 중 하나를 달성하기 위해 단순히 고객 지원 부서에 전화 할 수 있습니다. 그러나 분산화 된 시스템에서는 처음부터 기계에 폐기 및 복구 메커니즘을 구축해야합니다.
4.1 Key Recovery(키 복구)
사용자가 도메인에 대한 비밀 / 공개 키 쌍을 생성하면 Certcoin은 비밀 키가 최소한 3 개의 신뢰할 수있는 "친구"사이에서 공유되는 복구 시스템(e.g. using the Shamir secret sharing paradigm [22])을 설정해야하며 재구성을 위해 최소 2 개의 임계 값이 필요합니다. 또한 향상된 보안을 위해 각 신뢰할 수있는 친구는 다른 사람의 신원을 알지 않아야합니다. 실제로는 다른 사람을 신뢰하기를 원하지 않는 사용자는 "친구"를 자신이 만든 여러 가지 Certcoin 계정으로 지정하여 이러한 보안 목표를 달성 할 수 있습니다. Bitcoin 지갑 관리 플랫폼 인 Armory [12]에서도 이와 비슷한 기술을 사용합니다. 여기서 Armory [12]는 지갑의 열쇠가 비밀리에 복구가 가능하도록 공유합니다.
4.2 Key Revocation(키 폐지)
전통적인 공개 키 인프라에서 인증서는 특정 연령대에 만료되거나 인증서 폐기 목록 (CRL) [10]에 추가되거나 온라인 인증서 상태 프로토콜 (OCSP) [14]을 통해 폐기됩니다.
Certcoin은 lifetime 가치를 창출 할 수 있습니다. 각 공개 키는 관련 타임 스탬프를 가지며 공개 키가 Lifetime 보다 이전에 생성 된 경우 연령만으로 거부해야합니다. 공용 키는 전통적인 PKI와 마찬가지로 이유 코드(reason code)를 사용하여 수동으로 해지 할 수 있습니다. 원인 코드는 "지정되지 않음", "키 손상", "CA 손상", "변경된 상태", "대체 된 상태"또는 "작동 중지"중 하나 일 수 있습니다.
항상 각 도메인에는 두 개의 연결된 비밀 키가 있습니다. 하나는 online 이고 다른 하나는 offline 인 것입니다. 서로 다른 State의 타협은 서로 다른 방식으로 대응 될 수 있습니다. Google은 공격자가 키에 액세스하고 공격자가 키를 도용하는 (즉, 도메인 소유자가 멀리있는 키에 액세스하는) 경우를 구분합니다.
• 공격자가 하나의 비밀 키만 액세스 할 수 있는 경우 : 실제 도메인 소유자는 여전히 자신의 비밀 키 모두에 액세스 할 수 있으며 두 키를 사용하여 작성한 하나의 키와 서명하려고 시도한 다른 키를 폐기하는 상태의 서명에 서명 할 수 있습니다. 그런 다음 도메인 소유자가 현재 두 키 쌍을 사용하여 손상된 키를 업데이트합니다. 마지막으로, 두 가지 이전 보안 키는 손상된 키의 모든 향후 작업을 무효로하는 문에 서명하는 데 사용됩니다. 이렇게 하면 실제 도메인 소유자는 다시 두 개의 비협조적인 키의 유일한 소유자가되며 공격자는 무효화 된 키에만 액세스 할 수 있습니다. 이 모든 진술은 블록 체인에 트랜잭션으로 게시되며 공개적으로 검증 할 수 있습니다. 블록이 많은 문이 하나의 블록에 나타날 수 있기 때문에 동일한 블록에서 해지 된 키 (자매 키로 서명되지 않은 키)로 서명 된 모든 새 키는 블록 내의 타임 스탬프에 관계없이 자동으로 무효화됩니다. 이렇게하면 공격자가 이전 키를 취소 할 때 바로 제어 할 수있는 새 키에 침입 할 수 없게됩니다.
• 공격자가 온라인 비밀 키를 도용 한 경우 : 도메인 소유자가 온라인 비밀 키에 대한 모든 액세스 권한을 잃고 공격자가 도메인 소유자가 키 복구 시스템을 통해 키를 복구하지 못하도록 관리합니다. 모든 비밀 키는 온라인 비밀 키에 의해 생성 된 모든 서명에 대해 거부권을 행사하기 때문에 모두 손실되지 않습니다. 도메인 소유자는 offline 비밀 키를 사용하여 손상된 온라인 키로 서명 된 모든 키를 무효로하는 명령문에 서명하고 손상된 키 자체를 해지 할 수 있습니다. 다음으로, 도메인 소유자는 새로운 온라인 비밀 키를 생성하기 위해 offline 비밀 키를 사용할 수 있습니다. 그런 다음 저장 공간을 확보하기 위해 비밀 키를 반환한다.
• 공격자가 온라인 및 오프라인 키 모두에 액세스 할 수있는 경우 : 도메인 소유자는 여전히 두 키에 액세스 할 수 있습니다. 두 사람은 실제 도메인 소유자와의 상대를 구별 할 수있는 방법이 없으므로 두 키를 모두 사용하여이 키로 서명 된 현재 및 미래의 진술을 모두 무효화하는 성명서에 서명 할 수 있습니다.
• 공격자가 두 비밀 키를 훔친 경우 : 도메인 소유자가 더 이상 자신의 키에 액세스 할 수 없으며 Certcoin 프로토콜 내에서 그러한 상황을 처리 할 방법이 없습니다.
위에서 설명한 방식으로 비밀 키 손상을 해결하려면 먼저 손상을 발견해야합니다.
5 Cutting Down on Storage: Accumulators for Key Verification(저장 공간 절약 : 키 확인 용 축압기)
Certcoin을 배치하는 데있어서 한 가지 중요한 문제는 모든 Certcoin 사용자가 전체 블록 체인을 저장해야하는 것입니다. Bitcoin 블록 체인은 현재 16GB이며, 월 약 1GB의 속도로 증가하고있는 것으로 보입니다 [1]. Certcoin을 순진하게 구현하려면 검증을 수행하는 모든 장치 또는 엔터티에 대용량 저장 용량이 필요합니다. 그러나 이것이 항상 가능한 것은 아닙니다. 예를 들어 스마트 폰의 브라우저에는 사용 가능한 많은 저장 공간이 없을 수도 있습니다.
등록 된 도메인 및 키의 현재 상태 (즉, 도메인에서 현재 키까지의 맵) 만 유지하면 조금 더 나아질 수 있습니다. 여전히 등록 된 도메인 수에는 선형적인 저장 공간이 필요하지만 전체 블록 체인을 순회하는 것과는 달리 검사 당 일정한 시간 만 필요합니다. 또한 Bitcoin 프로토콜 [20]을 사용하여 추가 블록을 검증 할 수 있도록 블록 체인의 마지막 몇 블록을 저장해야합니다. 나머지 블록은 포함 된 공개 키 업데이트를 확인한 후 내용이 저장 상태를 업데이트하는 데 사용 된 후에 폐기됩니다. 그러나 등록 된 도메인 수가 선형화 된 저장 공간은 여전히 비현실적입니다. 스마트 폰의 브라우저는이를 지원할 수 없습니다.
우리는 Certcoin 저장 요구 사항을 낮추기 위해 Accumulator [15]의 사용을 제안합니다. Accumulator는 세트의 구성원을 테스트하는 데 사용되는 디지털 객체입니다. Accumulator 는 형식 (d, pk) 또는 형식 (d, pk, exp)의 튜플을 저장합니다. 여기서 d는 도메인이고, pk는 공개 키이고, exp는 선택적 만료 날짜입니다. 그런 다음 Accumulator 는 pk가 d에 등록되었는지 여부를 결정하는 데 사용될 수 있습니다. 대응하는 비밀 키 sk의 지식은 여전히 zero-knowledge proof 을 통해 증명 될 필요가있다. 이 절에서는 암호화 Accumulator를 설명하고 Certcoin에서 이 암호화 Accumulator를 사용하는 방법에 대해 설명합니다.
5.1 Cryptographic Accumulator Definitions(암호 누산기 정의)
디지털 서명에 대한 분산 형 대안으로서 암호화 Accumulator의 사용은 Benaloh와 de Mare에 의해 1994 년에 처음 기술되었다. Accumulator는 일련의 요소를 일정한 크기로 표현한 것입니다. Accumulator에 요소를 추가하면 증인이 생성되어 해당 요소가 추가되었음을 입증하는 데 사용할 수 있습니다. 보다 공식적으로, Accumulator 스키마는 4 개의 다항식 시간 알고리즘으로 구성됩니다.
• Gen (1^k) → a
보안 매개 변수 k가 주어진 경우 빈 Accumulator의 초기 값과 추가 매개 변수를 생성합니다.
• Add (a, y) → (a', w)
누산기 a의 현재 상태와 y 가산 값을 취하고 해당 증인 w뿐만 아니라 Accumulator a'의 새로운 상태를 반환합니다.
• WitAdd (w, y) → w'
증인 w의 현재 상태와 새로운 값 y를 Accumulator에 가산하여 갱신 된 증인 w'을 반환한다.
• Ver (a, y, w) → {0,1}
Accumulator a의 현재 상태, a의 멤버가 확인되는 값 y 및 y가 a에 있는 것의 증인 w 그리고 y가 a에있는 것처럼 보이는 경우 1을 반환하고 그렇지 않으면 0을 반환합니다.
Accumulator는 다음과 같은 속성이있는 경우 안전합니다.
• Correctness(정확성) : 값 y가 일치하는 것의 최신 증인은 항상 최신 Accumulator에서 y의 멤버 자격을 확인하는 데 사용할 수 있습니다. 좀 더 공식적으로, 모든 유효한 값 y와 유효한 값 [y1, ..., yl1], [y1, ..., yl2]의 추가 집합
• Soundness(건전성) : y 멤버십에 대한 검증이 성공하는 방식으로 Accumulator에 추가되지 않은 값 y에 대한 증인 w를 제작하는 것은 어렵습니다. 보다 공식적으로, oracles a에서 Add 및 WitAdd 블랙 박스 액세스가있는 어떠한 확률적인 polynomial-time 공격자 A에 대해
여기서 y는 Add를 호출하지 않은 A의 요소이고, a는 공격자가 Add에 대한 모든 호출을 한 후에 Accumulator의 상태이며, negl은 보안 매개 변수에서 무시할 수있는 함수입니다.
Accumulator에서 추가 속성이 필요할 수 있습니다.
• Compactness : Accumulator의 바람직한 특성은 얼마나 많은 항목이 추가 되더라도 작게 유지된다는 것입니다. Accumulator는 크기가 일정하면 (즉, 포함하는 요소의 수에 관계없이) 작다. 일부 Accumulator는 포함하는 요소의 수와 로그 적으로 증가합니다.
• Dynamism : 2002 년 Jan Camenisch와 Anna Lysyanskaya [9]는 삭제 알고리즘 Del과 증인 업데이트 알고리즘 WitDel을 사용하여 Accumulator에서 요소 삭제를 지원하는 동적 Accumulator의 개념을 도입했습니다.
• 보편성 (Universality) : 2007 년 Jiangtao Li, Ninghui Li와 Rui Xue [18]는 보편적 인 Accumulator의 개념을 소개했다. 보편적 인 Accumulator는 멤버쉽 증명 이외에 비회원 증명을 지원하는 Accumulator이다.
• Strength: • 장점 : 2008 년 Philippe Camacho, Alejandro Hevia, Marcos Kiwi 및 Roberto Opazo [7]는 Accumulator 관리자를 신뢰할 만한 것으로 간주하지 않는 강력한 Accumulator 개념을 소개하였다. 강한 Accumulator는 5.2.1 절에 설명 된 RSA Accumulator에서와 같이 Accumulator 생성 또는 유지 관리에 트랩 도어 정보를 사용할 수 없습니다.
5.2 Cryptographic Accumulator Constructions(암호화 Accumulator 구조)
RSA 구성, Bilinear Map 구성 및 Merkle Hash Tree 구성을 포함하여 여러 가지 알려진 Accumulator 구조가 있습니다. Bilinear Map 구조의 속성은 RSA 구조의 속성과 비슷하므로이 백서에서는 이에 대해 자세히 설명하지 않습니다. 또한 우리는 이러한 Accumulator 이외에 블룸 필터 (Bloom Filter)는 증인을 활용하지 않기 때문에 기술적으로 암호화 Accumulator가 아니지만 효율적인 멤버십 테스트에도 사용할 수 있어 고려한다. 그림 1의 표에는 이러한 모든 구성의 일부 속성이 요약되어 있습니다.
5.2.1 The RSA Accumulator(RSA 누산기)
Benaloh와 de Mare [5]는 해쉬 함수 h : X × Y → X 인 준 환원 해쉬 함수로부터 Accumulator를 구성 할 것을 제안했다. 모든 x ∈ X와 y1, y2 ∈ Y에 대해
순서는이 해시 함수의 적용에 중요하지 않으므로 h(x, {y1, y2, ..., yn}) 를 h(h(...h( h(x ,y1), y2)...), yn).로 표시한다.
Accumulator는 고정 된 x로 시작하여 값 yi가 h에 반복적으로 적용되어 집합에 추가 될 수 있습니다. h가 단방향 함수일 경우 집합의 yi 값은 h(w, yi) = a 의 검사에 의해 주어진 증인 w = h(x, {yj} j != i)에서 Accumulator에 테스트 될 수 있다. 이것은 분명하다: 값 yi가 합법적으로 a에 추가되었다면 유효한 w = h (x, {yj} j != i)가 유지되었을 것이다. 이것은 또한 h는 단방향이기 때문에, 값 w와 yi는 주어진 a만을 얻는 것이 어렵다.
Zn* 의 거듭 제곱은 단방향 및 준 가변 (quasi-commutative)이며 다음과 같이 암호화 Accumulator를 구성하는 데 사용할 수 있습니다.
v를 충돌 방지 해시 함수(collision-resistant hash function)라고합시다.
v를 사용하는 것은 y = yi yj에 대한 명백한 증인 제조 공격(obvious witness fabrication attack)을 방지하기 위해 필요하며, 여기서 yi 및 yj는 Accumulator에 합법적으로 추가됩니다.
이 구성은 n의 인수 분해가 적에게 알려지지 않은 경우에만 안전합니다. 즉, n의 인수 분해는 trap door입니다. 그러나 이 trap door는 Accumulator를 사용하지 않고 Accumulator를 만드는 데만 필요합니다. Add, WitAdd 및 Ver 알고리즘은 모두 n의 인수 분해를 모른 채 수행 될 수 있습니다. 따라서 Gen가 trap door 정보를 사용하기 때문에 RSA Accumulator가 강력한 Accumulator가 아닌 반면 안전한 방식으로 Gen를 수행하고 (아마도 다중 사용자 계산을 통해) Accumulator에 결과 Accumulator를 제공함으로써 강력한 Accumulator manager를 만들 수 있습니다.
Jan Camenisch와 Anna Lysyanskaya [9]는 RSA 누산기를 동적으로 만드는 방법을 제시한다. 다음과 같이 삭제 알고리즘 Del 및 추가 미러링 모니터 업데이트 알고리즘 WitDel을 설명합니다.
Del과 WitDel은 Gen과 마찬가지로 trap door에 대한 지식이 필요합니다.
5.2.2 The Merkle Hash Tree Accumulator
Jiangtao Li, Ninghui Li와 Rui Xue [18]는 Merkle Hash Trees의 건축과 유사한 방식으로 Accumulator를 건설 할 것을 제안했다. 그들의 논문에서 제시된 구성은 보편적으로 설계 되었기 때문에 더 복잡하고 다소 효과적입니다. 보편성이 Certcoin Accumulator의 매우 중요한 자산이라고 생각하지 않기 때문에 비공식적으로 Merkle 해시 트리 구조의 약간 더 단순한 버전을 제시합니다.
h가 충돌 방지 해시 함수라 하자. 트리 깊이 i (i는 1부터 log(n) 까지의 집합의 원소)와 거의 같은 수준에서 이 Accumulator는 log (n) 평형 Merkle Hash Tree 뿌리의 목록을 유지하며, 여기서 n은 Accumulator의 요소 수이다.
a = [r1, ..., rlog (n)]이라 하자.
6 Cutting Down on Storage: Distributed Hash Tables for Key Lookup(저장소 축소 : 키 조회를 위한 분산 해시 테이블)
암호화 Accumulator는 대용량 저장 오버 헤드를 발생시키지 않고 공개 키를 검증하는 문제를 해결합니다. 이제는 비슷한 제한이있는 공개 키를 가져 오는 문제로 넘어갑니다. Certcoin의 디자인은 인증과 배포를 명확하게 구분합니다. 도메인 구매 및 공개 키는 블록 체인에 저장되어 공개적으로 확인할 수있는 자격 증명 소스를 생성합니다. 불행히도 블록 체인은 본질적으로 키 - 값 검색을 지원하지 않으므로 동적 쿼리를 원활하게 수행 할 수 없습니다. 기존의 CA는 일반적으로 자체 인증 키 서버 역할을하므로 네트워크가 다른 사용자의 공개 키를 검색하도록 쿼리할 수 있습니다. 실용적인 PKI가되기 위해서는 CertCoin이 선택한 ID에 대한 공개 키를 효율적으로 검색하기위한 자체 인터페이스도 제공해야합니다. 이를 달성하기 위해 우리의 솔루션은 인증 된 DHT를 사용하여 구입 한 도메인 모음에 의해 유지 관리되는 탄력적이고 분산 된 키 서버를 만드는 방법을 제안합니다. 따라서 Certcoin의 배포 메커니즘은 자체 유지 키 전달 서비스를 만들기 위해 Kademlia DHT [19]의 고유 한 속성 중 일부를 사용합니다.
표준 형식에서 Kademlia는 인증되지 않아 중독, 라우팅 및 Sybil 공격에 취약합니다. 그러나 아래에서는 Certcoin의 블록 체인에 저장된 인증 데이터를 활용하여 각각 예방 방법을 설명합니다. 물론 우리는 도메인을 구입했는지 여부에 상관없이 모든 당사자가 Certcoin의 공개 키에 액세스 할 수 있기를 원합니다. 따라서 키 조회 요청을 인증하지 않기로 선택합니다. 이러한 요청의 읽기 전용 특성으로 인해 외부 공격자가 이 RPC를 악용하여 키 - 값 쌍을 변경할 수 없습니다. 따라서이 절의 나머지 부분에서는이 작업을 인증 문제에서 제외합니다.
6.1 Design of the Kademlia Distributed Hash Table(Kademlia 분산 해시 테이블 설계) // https://github.com/pRivAte12/kademila-kor
Kademlia가 제공하는 많은 바람직한 특성은 라우팅 테이블을 업데이트하기 위해 최소의 통신 오버 헤드를 발생시키는 대칭 라우팅 프로토콜의 결과입니다. Kademlia가 제공하는 많은 바람직한 특성은 라우팅 테이블을 업데이트하기 위해 최소의 통신 오버 헤드를 발생시키는 대칭 라우팅 프로토콜의 결과입니다. 이 프로토콜은 네트워크를 통해 전송 된 모든 패킷이 실행 가능한 노드 및 라우트의 상태에 대한 유용한 정보를 포함하도록 설계되었습니다. 따라서 Kademlia는 다른 노드에서 지속적으로 통신하고 사용자로부터 질의하여 장애를 자동으로 라우팅합니다. 따라서 Kademlia는 다른 노드에서 지속적으로 통신하고 사용자로부터 질의하여 장애를 자동으로 라우팅합니다.
또한 Kademlia는 라우팅 테이블에서 가장 오래된 활성 노드를 유지하려고 시도하여 노드 장애가 가동 시간과 반비례한다는 사실을 활용하여 가장 신뢰할 수있는 노드에 대한 경로가 위에 설명 된대로 네트워크의 다른 라우팅 테이블로 전파되도록 합니다 . 그런 다음 계속 증가하는 다른 라우팅 테이블에서 그 존재가 유지되는 방법으로 DHT의 노드가 온라인 상태를 유지하는 것이 가장 좋습니다. DHT의 응답 시간은 대상에 도달하는 데 필요한 숫자 홉에 따라 달라 지므로 신뢰할 수없는 노드는 공개 키에 액세스하려는 클라이언트에 대해 쿼리 응답을 느리게합니다. 이는 6.2.3에서 더 자세히 논의 된 Kademlia의 핵심 검색 프로토콜에 대한 Certcoin의 수정에 의해 시행됩니다.
모든 노드는 가능한 경로마다 k 개의 가능한 라우팅 값을 유지합니다. 이들 노드들 각각 사이에서 엔트리가 반복되지 않는다고 가정하면, 노드가 키에 도달 할 수 없다는 확률은 (2^-k)^k = 2^-k^2이다. 이것은 발신자의 테이블에있는 모든 k 노드가 임의의 노드로 들어오는 메시지나 나가는 메시지없이 자신의 라우팅 테이블에서 k 개의 실패를 갖도록 요구합니다. 그러나 중복은 확실히 발생해야하지만 네트워크의 라우팅 테이블이 본질적으로 가장 안정적인 노드를 저장한다는 사실에 의해 설정됩니다. 앞서 언급했듯이 라우팅 테이블은 보내거나받은 모든 메시지로 업데이트됩니다. 결과적으로 공격자가 구멍을 만들어야하는 평균 시간 간격이 비례하여 줄어들 기 때문에 더 많은 요청이 이루어짐에 따라 네트워크가 더욱 안전하게됩니다.
또한 Kademlia의 라우팅 프로토콜은 액세스 빈도에 따라 값을 분산하는 캐싱 메커니즘을 사용하도록 수정 될 수 있습니다. 네트워크의 많은 부분이 값을 복제 할 것이므로 더 많은 인기 키를 공격자가 목표로 삼기가 더 어려워 질 것입니다. 이를 달성하기 위해 필요한 추가 공간은 최소한이며 노드는 캐시 된 값을 계속 전파하는 노드가 많아짐에 따라 소스로 직접 트래픽이 감소하는 것을 볼 수 있기 때문에 노드가 참여할 수 있습니다.
6.2 Kademlia for Certcoin(Certcoin을위한 Kademlia)
6.2.1 Authenticated RPCs(인증 된 RPC)
앞서 언급했듯이 인증되지 않은 DHT는 중독 및 라우팅 공격에 취약합니다. 다행스럽게도 노드가 Kademila의 RPC에 서명하도록 요구함으로써 쉽게 보호 할 수 있습니다. 우리는 노드 u에서 시작된 표준 메시지 M을 다음과 같이 Certcoin의 DHT에 적합한 인증 메시지 MAuth로 변환하는 방법부터 설명합니다.
PKu 및 WitnessPKu를 포함하면 수신자는 누적기를 사용하여 보낸 사람의 진 본성을 즉시 확인할 수 있습니다. 노드가 인증되지 않은 메시지를 라우팅을 업데이트하는 데 사용해서는 안되며, 이는 중독 공격을 유도하기 때문입니다. 따라서 노드가 특정 키에 대해 DHT 외부에서 인증되지 않은 쿼리를 수신하면 노드는 재귀 적이며 인증 된 키 검색 시퀀스를 시작하지만 해당 라우팅 테이블을 업데이트하기 위해 메시지를 무시합니다. 물론 대상 경로까지의 노드는 검증 된 RPC를 사용하여 테이블을 업데이트해야합니다
6.2.2 Node ID Assignment(노드 ID 할당)
더 많은 압박은 잘 알려진 시빌 공격에 대해 방어이다. 공격자는 대개 ID 공간의 특정 영역을 타겟팅 할 수있는 다수의 ID를 만들 수 있습니다. 인증 기관의 존재 여부를 결정할 수있는 응용 프로그램에서는 일반적으로 등록 프로세스를 통해 개체와 ID의 일대일 매핑을 보장함으로써 해결됩니다. CA의 교체가 Certcoin의 궁극적 인 목표이기 때문에 이것이 유효한 해결책이 아니라는 것은 분명합니다. 다행스럽게도 Certcoin과 블록 체인의 통합은 이미 등록 서비스를 제공합니다. 그런 다음 DHT는 H (도메인 이름, 공개 키 서명, 블록 타임 스탬프)에 해당하는 노드 ID를 만듭니다. 여기서 H는 단방향이며 충돌 방지입니다.
임의의 사용자가 작성한 쿼리에 대한 DHT의 응답을 보여주는 Certcoin의 대체 키(alternate key) 검색 프로토콜의 예입니다.
6.2.3 Key Retrieval(키 검색)
노드가 단순히 자신을 제거하고 네트워크의 나머지 부분에 키를 배포하지 못하게하려면 키 조회에 응답하는 모든 노드가 그 키와 연관된 호스트 이름의 하트 비트 메시지(물론 배열 경계 검사 포함)에 대한 응답을 수신 할 수있을 때만 응답해야합니다. 노드는 이를 수행하지 않으면 엔티티가 떠나도록 허용하고 나머지 노드에 응답 요청의 부담을가하므로이 확인을 수행 할 인센티브를 갖습니다. 또한 서버는 하트 비트 메시지에 응답해야하며, 그렇지 않으면 사용자는 해당 사이트의 공개 키를 검색 할 수 없습니다.
DHT 외부로 전달되는 쿼리 응답을 다른 인증 된 RPC와 똑같이 구성해야하므로 키 조회 절차의 보안을 강화할 수 있습니다. 이를 통해 누구나 부정확 한 응답을 게시함으로써 악의적 인 노드를보고 할 수 있습니다. 노드가이를 인식하게되면, 라우팅 테이블에서 노드 끝 노드를 즉시 제거해야합니다. 또한 호스트 이름과 연관된 값을 저장하는 모든 노드는 상기 키에 대한 요청을 존중하지 않아야합니다.
DHT 외부로 전달되는 쿼리 응답을 다른 인증 된 RPC와 똑같이 구성해야하므로 키 조회 절차의 보안을 더욱 강화할 수 있습니다. 이를 통해 누구나 부정확 한 응답을 게시함으로써 악의적 인 노드를보고 할 수 있습니다. 노드가 이를 인식하게되면, 라우팅 테이블에서 상한 노드를 즉시 제거해야합니다. 또한 호스트 이름과 연관된 값을 저장하는 모든 노드는 상기 키에 대한 요청을 존중하지 않아야합니다.
7 Conclusion
결론적으로, 우리는 Certcoin이 인증서 기관과 PGP Trusts of Web을 대신 할 수있는 실행 가능한 PKI라고 믿습니다. 우리의 구성은 내재 된 내결함성, 중복성 및 투명성을 비롯하여 완전히 분산 된 아키텍처에서 이익을 얻습니다. 그럼에도 불구하고 Certcoin은 인증서 생성, 해지, 연결 및 복구를 포함하여 완전한 기능을 갖춘 인증 기관의 예상 기능을 지원합니다. 도메인 구매 및 전송은 간단한 Bitcoin 트랜잭션으로 수행되어 Miner들에게 incentivize를 지급합니다. Certcoin은 암호화 어큐뮬레이터를 사용하여 도메인 인증을위한 일정한 크기의 저장소를 유지 관리합니다.이 저장소는 최근 인터넷 사용 추세에 따라 더욱 중요 해지고 있습니다. 마지막으로, 우리의 설계는 CertCoin을 성능에 민감한 응용 프로그램에보다 실용적으로 만들어주는 효율적인 키 검색을 제공하는 자체 유지, 신뢰할 수있는 키 배포 메커니즘의 필요성을 해결합니다. 또한 Certcoin은 신뢰할 수있는 제 3 자의 필요성 및 제한된 접근성과 같은 현재 PKI에 내재 된 많은 문제를 해결합니다.
우리는 미래에 Certcoin을 구현하여 우리의 결과를 경험적으로 발견하고 그 실행 가능성을 입증 할 수있는 추가 최적화를 모색 할 계획입니다.