그리드 공격에 대해 무엇을 알고 있습니까?
우선 타원 곡선 디지털 서명 알고리즘 (ECDSA) 은 많은 코드 리뷰에서 볼 수 있는 일반적인 디지털 서명 체계입니다. 그것은 몇 가지 바람직한 속성을 가지고 있지만 1비트 미만의 비밀 nonce를 드러내는 부채널 공격으로 개인 키를 복구하는 데 매우 취약할 수도 있습니다.
ECDSA디지털 서명 알고리즘의 특별한 형태입니다(DSA).DSA키 생성, 서명 및 확인의 세 가지 알고리즘으로 정의되는 상당히 일반적인 디지털 서명 체계입니다. 키 생성 알고리즘은 개인 및 공개 키를 생성합니다. 개인 키는 서명 생성을 담당합니다. 공개 키는 서명 확인을 담당합니다. 서명 알고리즘은 메시지와 개인 키를 입력으로 받아 서명을 생성합니다. 확인 알고리즘은 메시지, 서명 및 공개 키를 입력으로 사용하고 서명이 유효한지 여부를 나타내는true또는 값을 반환합니다.false
DSA 는 모든 수학적 그룹에 대해 정의되며 이 체계는 해당 그룹에 대해 이산 로그 문제가 어려운 한 안전합니다. 일반적으로 사용되는 그룹은 정수 모듈로 소수 p입니다.
이 그룹과 함께 그룹 생성기 g 및 일부 암호학적으로 안전한 해시 함수 가 H있습니다. 우리는 그것을 가정할 수 p , g 있으며 H 일반적인 지식이 될 것입니다.
x 키 생성은 먼저 모듈로 정수에서 값을 무작위로 선택하여 작동합니다 p . 그런 다음 값이 계산됩니다. y = g^x mod p
서명의 개인 키는
x이고 공개 키는y입니다. 서명 키는 서명을 허용하기 때문에 비밀로 유지해야 합니다.
서명 알고리즘은 메시지 m 와 비밀 키 x 에서 서명을 생성합니다. 먼저 랜덤 그룹 요소가 생성됩니다 k . 이것을 논스(nonce)라고 하며 이는 공격과 관련하여 중요합니다.
그런 다음 값이 계산 r = g^k mod p 되고 s = ( k^-1 ( H ( m ) + xr )) mod p
여기서 k^- 1 는 역군이며 H ( m ) 해시 m을 계산하고 그 결과를 정수 모듈로 p로 해석한 결과입니다.
서명은 의 쌍으로 정의됩니다 ( r , s ). (참고: r 또는 값 중 하나가 와 s같으면 0알고리즘은 의 새 값으로 다시 시작됩니다 k .
검증 알고리즘은 서명 ( r , s ), 메시지 m 및 공개 키 y를 입력으로 받습니다. Let ŝ = s^-1 , 다음 경우에만 알고리즘이 true 를 반환합니다 r , s ≠ 0 и r = ( g H ( m ) y r ) ŝ .
이 유효성 검사는 g^H( m ) y^r = g^H(m)+ xr = g^ks, 따라서 작동합니다.(g^H(m)y^r)^ŝ = g^k = r
디지털 서명 체계는 위조될 수 없는 경우 안전한 것으로 간주됩니다.
불변성은 공식적인 암호화 의미를 갖지만 높은 수준에서 이는 비밀 키를 알지 않고는 서명을 만들 수 없음을 의미합니다(비밀 키에서 생성된 이미 존재하는 서명을 복사하지 않는 한). 이산 로그DSA 를 가정하면 위조가 불가능한 것으로 입증되었습니다 .
DSA 수학적 그룹에 대해 정의됩니다. DSA 이 수학 그룹으로 타원 곡선 그룹과 함께 사용할 때 이를 이라고 합니다 ECDSA. 타원 곡선 그룹 은 의 쌍인 타원 곡선 점으로 구성되며 일부 ( x , y )방정식을 충족합니다 . 이 블로그 게시물에서 알아야 할 것은 타원 곡선을 사용하여 유한 그룹을 정의할 수 있다는 것입니다. 즉, 그룹 생성기, (타원 곡선 점) 및 덧셈 및 도트 곱셈 연산 은 사용자와 동일합니다. 정수로 할 수 있습니다. 그들은 유한 그룹, 발전기를 형성하기 때문에,y^2 = x^3 + ax + ba , bg g , 유한 차수를 갖습니다 p. 이 블로그 게시물에서는 이러한 타원 곡선 작업 이 어떻게 작동하는지 설명하거나 요구하지 않습니다 .
ECDSA 와 동일 DSA하지만 다른 그룹과 함께 작동합니다. 비밀 키 x 는 여전히 임의의 값 모듈로 정수 p 입니다. 이제 공개 키 는 g가 이제 타원 곡선의 한 점이라는 점을 제외하고 y 여전히 로 계산됩니다 . y = g^x이것은 y가 타원 곡선의 한 점이기도 함을 의미합니다(이전에는 y가 정수 모듈로 p였습니다). 또 다른 차이점은 r 값을 계산하는 방법입니다. 우리는 여전히 이전과 같이 정수 모듈로 p로 임의의 논스 k를 생성합니다. 우리는 계산할 것입니다 g^k . 그러나 다시 g 는 타원 곡선의 한 점이며, 따라서 g^k 또한입니다. 따라서 우리는 계산 ( x^k , y^k ) = g^k 하고 설정할 수 있습니다 r = x^k . 이제 의미 s 이전과 같이 계산할 수 있으며 이전과 같이 ( r , s )여전히 정수 모듈로 인 서명을 얻 p 습니다. r 확인하려면 조금 다르게 계산했다는 사실을 수정해야 합니다 .
따라서 이전과 같이 의 값을 계산
( g^H(m)y^r)^ŝ하지만 이제 그 값은 타원 곡선의 한 점이므로x해당 점의 -좌표를 가져와 의 값과 비교합니다r.
재사용된 nonce에서 비밀 키 복구 NONCES
이제 이것이 무엇 ECDSA 이며 어떻게 작동하는지 이해했으므로 취약성 을 입증해 보겠습니다 . 다시 말하지만, 이것은 디지털 서명 방식이므로 비밀 키 는 메시지에 서명하는 사람 외에는 절대 공개되지 않아야 합니다.
그러나 서명자가 서명을 발행하고 사용된 nonce도 발행하면 공격자 는 즉시 비밀 키 를 복구할 수 있습니다 .
( r , s ) 메시지에 대한 서명을 해제 m 하고 실수로 내가 nonce 를 사용했다는 것을 발견 했다고 가정해 보겠습니다 k .
s = ( k^-1 ( H ( m ) + xr )), 비밀 키를 쉽게 계산할 수 있기 때문에 :
s = (k^-1(H(m) + xr))
ks = H(m) + xr
ks – H(m) = xr
x = r^-1(ks – H(m))
따라서 서명자는 개인 키를 비밀 로 유지해야 할 뿐만 아니라 그들이 생성한 모든 nonce도 비밀로 유지해야 합니다.
서명자가 각 nonce
NONCES를 비밀 로 유지하더라도 실수로 하나 의 nonceNONCES를 반복하면 (심지어 다른 메시지에 대해서도) 비밀 키 도 즉시 복구 할 수 있습니다 .
메시지 및 (각각) 동일한 nonce에서 생성된 두 개의 서명을 하자 - 동일한 nonce ( r , s 1 ) 를 갖기 때문에 r 값은 동일하므로 공격자가 감지하기가 매우 쉽습니다.( r , s 2 )m 1m 2k
s1 = k^-1(H(m1) + xr) and s2 = k^-1(H(m2) + xr)
s1 – s2 = k^-1(H(m1) – H(m2))
k(s1 – s2) = H(m1) – H(m2)
k = (s1 – s2)^-1(H(m1) – H(m2))
위의 공식을 사용 하여 nonce를 복구한 후에 k 는 앞에서 설명한 공격을 수행하여 개인 키를 복구할 수 있습니다.
이것을 잠시 소화해 봅시다.
서명 nonce
NONCES가 공개되면 비밀 키 를 즉시 복구 할 수 있으며 이는 전체 서명 체계 를 깨뜨 립니다.
또한 두 개의 nonce가 반복되면 메시지가 무엇이든 공격자 가 이를 쉽게 감지하고 즉시 비밀 키를 복구하여 전체 체계를 다시 깨뜨릴 수 있습니다.
그것은 매우 약하고 단지 가벼운 공격 입니다!
그러나 매우 자세히 설명된 새로운 격자 공격 이 있습니다 (Joachim Breitner 및 Nadia Heninger).Йоахим Брайтнер и Надя Хенингер
문서 [PDF] : Biased Nonce Sense: Cryptocurrencies의 약한 ECDSA 서명에 대한 격자 공격
비트코인 블록체인에서 우리는 특정 거래를 발견했습니다:
거래: 08d917f0fee48b0d765006fa52d62dd3d704563200f2817046973e3bf6d11f1f
비트코인 주소: 15N1KY5ohztgCXtEe13BbGRk85x2FPgW8E
우리는 가짜 서명을 곱하고 그리드를 적용했습니다.
GOOGLE COLAB 에서 패키지 설치와 함께 Python 스크립트 algorithmLLL.py 사용
설치 >> SAGE + ECDSA + BITCOIN + 알고리즘 LLL
우리 는 하나의 약한 거래에서 에 도달
Private Key했습니다 .Bitcoin WalletECDSA
개인 키를 찾았습니다!
https://www.blockchain.com/btc/address/15N1KY5ohztgCXtEe13BbGRk85x2FPgW8E
ADDR: 15N1KY5ohztgCXtEe13BbGRk85x2FPgW8E
WIF: 5JCAmNLXeSwi2SCgNH7wRL5qSQhPa7sZvj8eDwxisY5hJm8Uh92
HEX: 31AFD65CAD430D276E3360B1C762808D1D051154724B6FC15ED978FA9D06B1C1 이 비디오는 BITCOIN 암호화폐의 약한 ECDSA 서명에 대한 데이터 및 secp256k1 타원 곡선 암호화의 재정적 보안을 보장하기 위해 CRYPTO DEEP TECH 포털을 위해 제작되었습니다.
동영상: https://youtu.be/YP4Xj6gUcf4
No comments:
Post a Comment