저자: Sylvain Pelissier 편집: Cointime.com 237

퍼블릭 블록체인은 ECDSA 서명에 대한 공격의 오랜 역사를 가지고 있습니다. 모든 트랜잭션이 공개적으로 표시되기 때문에 암호화 공격에 대한 완벽한 테스트 환경을 제공합니다. "A Curious Case of Half-Bitcoin ECDSA Random Numbers"라는 격자 공격이 최근 발표되어 비트코인에서 실험되었습니다. 반반 퐁듀를 좋아하는 스위스 팀으로서 우리는 이 공격을 조사해야 했습니다. 우리는 이전 공격인 "다항식 난수"가 ECDSA 난수를 생성하는 이러한 방식으로도 작동한다는 것을 발견했습니다. 이 백서에서는 이를 수행하는 방법을 설명하고 백서에서 얻은 결과와 비교하는 방법을 보여줍니다.

이전 공격

메시지에 서명하기 위해 ECDSA는 nonce라는 값을 사용합니다. nonce는 임의로 생성되어야 하며 서명할 각 메시지에 대해 고유해야 합니다. 비트코인 및 이더리움의 secp256k1 곡선의 경우 일반적인 nonce 값은 다음과 같습니다.

잘 알려져 있고 잘 연구된 ECDSA의 일반적인 함정은 임시 재사용입니다. 이름에서 알 수 있듯이 nonce가 다른 서명에서 재사용되면 해당 서명에서 개인 키를 복구할 수 있으며, 분명히 블록체인에 적용되는 첫 번째 공격은 nonce 재사용 공격입니다. 두 개의 서로 다른 메시지가 동일한 nonce로 서명되는 즉시 개인 키가 손상됩니다. 이 문제는 일반적으로 RFC 6979에 따라 결정론적 난수를 생성하여 해결됩니다.

그러나 ECDSA nonce는 매우 중요하므로 해당 생성의 편향조차도 개인 키 복구로 이어질 수 있습니다. 따라서 더 독창적인 격자 기반 공격이 나중에 퍼블릭 블록체인에 적용되었습니다. 이러한 공격은 길이가 64, 110, 128 및 160비트인 예상 길이보다 짧은 논스를 복구할 수 있습니다. 예를 들어 다음과 같이 생성된 난수는 격자 기반 공격에 취약합니다.

nonce가 작을수록 공격에 사용되는 격자의 차원이 작아지고 성공적인 공격에 필요한 서명 수가 작아집니다. Biased Random Numbers 논문에 따르면 두 개의 128비트 난수와 3차원 격자는 75%의 성공 확률(개인 키 복구)을 제공합니다. 3개의 170비트 난수와 4차원 격자를 사용하면 95%의 성공 확률을 얻을 수 있습니다. 공격의 변형은 접두사와 접미사를 공유하는 nonce를 발견하는 데에도 적용할 수 있습니다. 예를 들어, 다음과 같이 생성된 난수는 앞서 언급한 공격 및 공통 접미사 구성에 똑같이 취약합니다.

폴리논스

ECDSA를 공격하는 또 다른 방법은 난수 간의 대수적 관계를 가정하는 것입니다. 우리 팀은 알려지지 않은 계수 a_i 사이에 다항식 관계가 있다고 가정하는 Polynonce 공격을 다음과 같은 형식으로 제안했습니다.

k_{n+1} = a_1 k_n + a_0

또는

k_{n+1} = a_2 k_n^2 + a_1 k_n + a_0

그런 다음 Polynonce 공격은 100% 성공 확률로 개인 키를 대수적으로 복구할 수 있지만 선형의 경우 4개의 서명, 2차의 경우 5개의 서명 등이 필요합니다. 공격은 주로 다항방정식 풀기에 의존하기 때문에 격자 기반 공격에 비해 매우 빠르다. 자세한 내용은 다가오는 데프콘(DEFCON) 컨퍼런스에서 공개될 예정이다.

단일 서명

이전의 모든 공격에는 동일한 개인 키에서 적어도 두 개의 서로 다른 서명이 필요했습니다. 그러나 Ledger와 같은 지갑은 단일 개인 키로 트랜잭션에 서명한 다음 개인 키를 변경합니다. 이것은 많은 비트코인 ​​공개 주소가 현재 한 번만 사용되는 이유를 설명합니다. 아래는 P2PKH 트랜잭션으로 제한된 로그 스케일로 표시된 비트코인 ​​전송 데이터(2022년 9월 5일 기준, 블록 752759)의 그래프입니다.

이는 P2PKH 트랜잭션에 사용되는 공개 키의 92%가 한 번만 사용됨을 보여줍니다. 이 기능은 주로 개인 정보 보호를 위한 것이지만 이전 공격으로부터 간접적으로 보호하기도 합니다. 이더리움의 경우 상황이 조금 다릅니다. 151429561개의 고유 키에서 1759432087개의 서명을 분석하고 선형 스케일 플롯을 만들었습니다.

이는 P2PKH 트랜잭션에 사용되는 공개 키의 92%가 한 번만 사용됨을 보여줍니다. 이 기능은 주로 개인 정보 보호를 위한 것이지만 이전 공격으로부터 간접적으로 보호하기도 합니다. 이더리움의 경우 상황이 조금 다릅니다. 151429561개의 고유 키에서 1759432087개의 서명을 분석하고 선형 스케일 플롯을 만들었습니다.

이것은 상당히 다른 상황입니다. 공개 키의 42%는 단일 서명에만 사용되고 22%는 두 서명에 사용되며 13%는 세 서명에 사용됩니다. 따라서 개인정보 보호 방법은 이더리움에서 거의 또는 전혀 적용되지 않는 것으로 보입니다.

절반 절반 난수

메시지 해시의 상위 절반을 사용하여 nonce가 개인 키의 상위 절반과 연결될 때 몇 가지 문제를 일으키는 새로운 공격 방법이 최근 등장했습니다. 즉, 난수 k는 다음과 같이 표현할 수 있습니다.

k = h_{msb} || d_{msb}

이 공격의 참신함은 단일 서명에서 개인 키 d를 복구할 수 있다는 것입니다. 이전의 격자 기반 공격과 유사하게 난수 k에 대한 표현식이 ECDSA 공식에 주입되고 재배열되어 숨겨진 숫자 문제의 인스턴스를 형성합니다. 그런 다음 인스턴스는 BKZ 알고리즘을 사용하여 해결됩니다. 이 기술은 한 번만 사용되는 개인 키로 발행된 트랜잭션을 공격하는 데 단일 서명만 필요하기 때문에 매우 강력합니다. 최적화된 버전의 공격은 99.99%의 성공률로 0.48초 만에 개인 키를 복구할 수 있었습니다. 그것은 매우 강력하지만 저자가 비트코인 ​​블록체인에 대한 공격을 실행하는 데 49년의 CPU가 걸렸습니다.

반반 난수에 폴리논스 적용

Half-Half 공격에 대해 읽는 동안 Polynonce를 사용하여 Half-Half 난수를 사용하여 개인 키를 복구할 수도 있음을 발견했습니다. ECDSA 서명(r, s), 메시지 해시 h 및 개인 키 d의 경우 nonce와 관련된 다음 관계가 있습니다.

k = s^{-1}(h + rd) mod q

이전 하프 하프 공식을 사용하여 생성된 두 개의 난수 k_0 및 k_1이 있는 경우 그 차이는 다음과 같습니다.

k_0 - k_1 = s_0^{-1}h_0 - s_1^{-1}h_1 + (s_0^{-1}h_0 - s_1^{-1}h_1)d = h_{0,msb} - h_{1, msb}

다른 모든 값이 알려진 d에 대한 선형 방정식을 찾았습니다. 이것은 방정식을 풀고 개인 키를 복구하는 매우 빠른 방법을 제공합니다. d. 그러나 Polynonce를 사용하려면 동일한 개인 키에서 두 개의 nonce와 두 개의 서명이 필요합니다. 우리는 이전 공격에 비해 큰 이점을 잃었습니다. 그럼에도 불구하고 이 공격 변종은 매우 빠르기 때문에 다중 서명이 있는 공개 키에 먼저 사용한 다음 나머지 서명에 격자 기반 공격을 사용할 수 있습니다.

방정식의 난수 차이는 h_{0,msb} - h_{1,msb}에만 의존하므로 공식 k_i = h_{i,msb} || c(여기서 c는 a (비밀) 상수) 모든 난수가 생성됩니다. 이것은 더 일반적이지만 Bitcoin의 경우 약간 더 복잡합니다. ECDSA 서명(r, s)에서 시작하여 동일한 메시지의 다른 서명(r, -s)도 유효합니다. Bitcoin은 서명 위조를 방지하기 위해 s의 가장 큰 값을 가진 서명을 거부하므로 -k와 k를 모두 계산해야 합니다. 따라서 우리의 공격에서는 각 nonce의 부호를 추측해야 합니다.

이 구성은 공유 접미사에 대한 격자 공격에 대한 이전 연구에서도 발견되었어야 하지만 성공률은 75%에 불과했습니다.

결과

이전 분석(2022년 9월 5일 현재 블록 752,759)에 사용된 비트코인 ​​블록체인 덤프 파일에 대한 분석을 수행했습니다. 최소 2개의 서명이 있는 3,400만 개의 공개 키를 분석했습니다. 2.7GHz 클럭의 16코어 AMD 프로세서에서는 10분 23초가 걸렸습니다.

우리는 110개의 고유한 개인 키를 성공적으로 찾아 복구했습니다. 예를 들어, 주소

18zg6FG5pu8Bpq73L54AYvB8phTw3qCCR7

거래

우리는 110개의 고유한 개인 키를 성공적으로 찾아 복구했습니다. 예를 들어, 주소

18zg6FG5pu8Bpq73L54AYvB8phTw3qCCR7

거래

f3151fc1b29c117f1e4b67045b2d2901e7c289f596c242d7de123243fb623981

그리고

f7bf1edf9d9cefa8421322c53bb00ecf118f99489171da72a9c11cf8d02b65f8

반반 방법을 사용하여 난수를 생성합니다. 스크립트는 이 주소에 대한 개인 키를 복구할 수 있습니다.

이러한 트랜잭션에 대한 논스를 다시 계산하면 다음과 같은 결과를 얻습니다.

nonce의 최하위 절반이 개인 키의 최상위 절반과 같다는 것을 분명히 알 수 있습니다. 그러나 위에서 언급한 것처럼 우리는 다른 흥미로운 사례를 복구할 수 있었습니다. 동일한 주소에 대해 두 개의 논스를 찾았습니다.

이 경우에는 실제로 다른 알려지지 않은 상수를 찾았기 때문에 개인 키가 관련되지 않습니다. 우리는 또한 이러한 난수를 사용하는 일부 키가 작은 키라는 이전 연구 결과를 확인할 수 있었습니다. 따라서 이러한 키는 웹사이트 https://privatekeys.pw에서 수행한 작업과 유사하게 무차별 대입 방식으로 쉽게 복구할 수 있습니다. 잔액이 0이 아닌 계정을 찾지 못했습니다. 봇이 모니터링하고 잔액이 변경되면 비워집니다.

이 공격은 매우 빠르기 때문에 우리는 준난수 생성의 다른 변형에 대해서도 동일한 공격을 실행했습니다: k = h_{lsb} || d_{msb}, k = d_{msb} || h_{msb} 및 k = d_{msb} || h_{lsb}, 하지만 추가 결과를 찾지 못했습니다.

우리는 또한 이전 공격 중에 수집된 이더리움 데이터 세트에 대해 동일한 공격을 실행했습니다. 공격은 같은 머신에서 49분 11초가 걸렸습니다. 이 공격은 개인 키를 복구하지 못했습니다.

과거의 다양하고 독창적인 난수 생성 구조는 너무 흥미로워서 다른 이국적인 구조가 있는지 궁금했습니다. 이러한 새로운 공격이 새로운 개인 키를 복구하지는 않지만 이전 트랜잭션에서 다른 취약한 난수 생성 알고리즘이 사용되지 않았거나 유사한 방법으로 복구가 가능하다는 의미는 아닙니다. 이러한 문제가 발견되면 자금을 보호하는 가장 좋은 방법은 이전에 거래에 사용되지 않은 새로운 주소로 자금을 이동하고 취약한 주소는 비워 두는 것입니다. 공격 스크립트와 얻은 결과는 Polynonce 공격의 Github 리포지토리에서 사용할 수 있습니다.