Proxy Re-signature 알고리즘 개발

Pairing-friendly Elliptic Curve 를 이용한 Proxy re-signature 알고리즘을 생각 해 보았다.

문제 없을까...? 아는 사람 댓글 부탁드립니다.. :)

 

r’ size = 96 bytes

s’ size = 96 bytes

total = 192 bytes (1536-bits, rsa-2048 보다는 작음)

 

 

 

 

 

 

---

 

이전 버전

 

 

---

 

**주의** 이 알고리즘엔 심각한 취약점이 있습니다.

 

1. First signature는 누구나 위조할 수 있습니다

Alice 공개키를 A=aG 라고 합시다.

메시지 m에 대해 h=H(m) 라고 할 때,

공격자는 Alice 비밀키 a를 몰라도 임의의 t∈Zr 를 고른 뒤 s=t, R=tA−hG 로 만들면 됩니다.

그러면 검증식은 다음처럼 항상 성립합니다.

e(A,sQ)=e(A,tQ)=e(tA,Q)

반면 zh⋅e(R,Q)=e(hG,Q)⋅e(tA−hG,Q)=e(tA,Q) 따라서 e(A,sQ)=zhe(R,Q) 가 됩니다.

 

즉, 공격자는 다음만 알고 있으면 됩니다.

A=aG,G,Q,h=H(m)

Alice의 비밀키 a도, nonce k도 필요 없습니다. 이것은 완전한 existential forgery입니다.

이 문제의 핵심은 h=H(m)가 R이나 공개키에 바인딩되어 있지 않고, 검증자가 R을 자유로운 선형 보정항으로 받아들이기 때문입니다.

2. Re-signing key도 노출됩니다

원본 Alice 서명과 재서명 결과가 모두 관찰 가능하면,

S′=s⋅rk_ab

이므로 누구나 rk_ab=s^( −1 )S′ 를 계산할 수 있습니다.

 

즉, 원본 서명 (R,s)와 재서명 (R′,S′)가 한 쌍만 공개되어도 re-signing key가 유출됩니다.

 

이것은 proxy re-signature에서 치명적인 문제입니다. Ateniese–Hohenberger 논문도 기존 BBS 방식의 한계로, 원본 signature와 변환 signature를 보면 proxy에 저장된 re-signature key에 해당하는 정보를 복구할 수 있어 proxy의 의미가 사라진다고 지적합니다.

 

 

왜 당시엔 저리 간단한 공격방법을 생각치 못했는지...ㅠㅠ

 

수정한 후속 글:

https://jsty.tistory.com/389

Proxy Re-signature (jclab-prs-2601)