Satu transaksi lemah di ECDSA pada blockchain Bitcoin dan dengan bantuan Lattice Attack kami menerima Kunci Pribadi untuk koin BTC

 

Apa yang kita ketahui tentang serangan lattice attack?

Untuk memulainya,  algoritma tanda tangan digital kurva elips (ECDSA)  adalah skema tanda tangan digital umum yang kami lihat di banyak ulasan kode kami. Ini memiliki beberapa properti yang diinginkan, tetapi juga bisa sangat rapuh untuk memulihkan kunci pribadi dengan serangan saluran samping yang mengungkapkan kurang dari satu bit nonce rahasia.

ECDSA adalah bentuk khusus dari algoritma tanda tangan digital  (DSA). DSA adalah skema tanda tangan digital yang cukup umum, yang didefinisikan oleh tiga algoritma: pembuatan kunci, tanda tangan, dan verifikasi. Algoritme pembangkitan kunci menghasilkan kunci privat dan publik;  kunci pribadi bertanggung jawab untuk membuat tanda tangan;  dan kunci publik bertanggung jawab untuk memverifikasi tanda tangan.  Algoritma tanda tangan mengambil pesan dan kunci pribadi sebagai masukan dan menghasilkan tanda tangan. Algoritme verifikasi mengambil pesan, tanda tangan, dan kunci publik sebagai input dan mengembalikan nilai  true atau  false, yang menunjukkan apakah tanda tangan itu valid.

DSA didefinisikan untuk setiap grup matematika, dan skema ini aman selama masalah logaritma diskrit sulit untuk grup itu. Grup yang umum digunakan adalah bilangan bulat modulo bilangan prima p.

Bersama dengan grup ini, kita akan memiliki generator grup g dan beberapa   fungsi  hashH yang aman secara kriptografis . Kita bisa berasumsi bahwa  p , g dan  H akan menjadi pengetahuan umum.

Pembuatan kunci bekerja dengan terlebih dahulu memilih nilai secara acak  x dari bilangan bulat modulo  p . Kemudian dihitung nilainya y = g^x mod p

Kunci pribadi dari tanda tangan adalah  x , dan kunci publiknya adalah  y . Kunci penandatanganan harus dirahasiakan, karena itulah yang memungkinkan tanda tangan dibuat.

Algoritme tanda tangan membuat tanda tangan dari pesan  m dan kunci rahasia x . Pertama, elemen grup acak dihasilkan  k . Ini dikenal sebagai nonce, yang penting dalam hal serangan.

Kemudian nilainya dihitung  r = g^k mod p dan s = ( k^-1 ( H ( m ) + xr )) mod p

Di sini  k^- 1 , adalah grup terbalik, dan  H ( m ) merupakan hasil komputasi hash m, dan menafsirkan hasilnya sebagai modulo p integer.

Tanda tangan didefinisikan sebagai sepasang  ( r , s ). (Catatan: jika salah satu  r atau  nilai ssama dengan  0, algoritme dimulai ulang dengan nilai baru  k ).

Algoritme verifikasi menerima tanda tangan  ( r , s ), pesan,  m dan kunci publik y sebagai masukan. Misalkan  ŝ = s^-1 , maka algoritma mengembalikan nilai true jika dan hanya jika  r , s ≠ 0 и r = ( g H ( m ) y r ) ŝ .

Pemeriksaan validasi ini berfungsi karena  g^H( m ) y^r = g^H(m)+ xr = g^ks, dan oleh karena itu (g^H(m)y^r)^ŝ = g^k = r

Skema tanda tangan digital dianggap aman jika tidak dapat dipalsukan.

Kekekalan memiliki arti kriptografi formal, tetapi pada tingkat tinggi itu berarti Anda tidak dapat membuat tanda tangan tanpa mengetahui kunci rahasia (kecuali jika Anda telah menyalin tanda tangan yang sudah ada yang dibuat dari kunci rahasia). Terbukti tidak  DSAmungkin untuk dipalsukan dengan asumsi  log diskrit  .

DSA didefinisikan di atas grup matematika. Ketika  DSA digunakan dengan grup kurva elips sebagai grup matematika ini, kami menyebutnya  ECDSA. Grup kurva eliptik  terdiri dari titik-titik kurva eliptik, yang merupakan pasangan  ( x , y ), yang memenuhi persamaan  y^2 = x^3 + ax + b untuk beberapa  a , b . Untuk posting blog ini, yang perlu Anda ketahui adalah bahwa menggunakan kurva elips Anda dapat menentukan grup hingga, yang berarti Anda mendapatkan generator grup,  g (titik kurva eliptik) , dan operasi  penjumlahan  dan  perkalian titik  persis seperti ini sama seperti Anda bisa dengan bilangan bulat. Karena mereka membentuk grup hingga, generator,g , akan memiliki urutan yang terbatas,  p. Posting blog ini tidak akan menjelaskan atau mengharuskan Anda untuk mengetahui cara  kerja operasi kurva eliptik ini .

ECDSA bekerja sama dengan  DSA, tetapi dengan grup yang berbeda. Kunci rahasia x  masih akan berupa bilangan bulat modulo nilai acak  p . Sekarang kunci publik  y masih dihitung sebagai  y = g^x , kecuali bahwa g sekarang merupakan titik pada kurva eliptik. Ini berarti bahwa y juga akan menjadi titik pada kurva eliptik (sebelumnya y adalah bilangan bulat modulo p ). Perbedaan lainnya adalah bagaimana kita menghitung nilai r . Kami masih menghasilkan k nonce acak sebagai modulo p integer seperti sebelumnya. Kami akan menghitung  g^k , tetapi sekali lagi, g adalah titik dari kurva elips, dan, oleh karena itu,  g^k juga. Oleh karena itu, kita dapat menghitung  ( x^k , y^k ) = g^k dan mengatur  r = x^k . Sekarang artinya s dapat dihitung seperti sebelumnya, dan kami mendapatkan tanda tangan kami  ( r , s ), yang masih merupakan modulo integer  p , seperti sebelumnya. Untuk memeriksa, kita perlu mengoreksi fakta bahwa kita menghitung  r sedikit berbeda.

Jadi, seperti sebelumnya, kita  menghitung  nilai  ( g^H(m)y^r)^ŝ , tetapi sekarang nilai tersebut adalah sebuah titik pada kurva eliptik, jadi kita mengambil  xkoordinat - dari titik tersebut dan membandingkannya dengan nilai kita  r .

Pemulihan  kunci rahasia  dari nonces yang digunakan kembali NONCES

Sekarang setelah kita memahami apa itu  ECDSA dan bagaimana cara kerjanya, mari kita tunjukkan  kerapuhannya . Sekali lagi, karena ini adalah skema tanda tangan digital, sangat penting bahwa  kunci rahasia  tidak pernah diungkapkan kepada siapa pun selain orang yang menandatangani pesan.

Namun, jika penandatangan pernah mengeluarkan tanda tangan dan juga mengeluarkan nonce yang digunakan,  penyerang  dapat segera memulihkan  kunci rahasia .

Katakanlah saya melepaskan tanda tangan  ( r , s ) untuk sebuah pesan  m dan secara tidak sengaja menemukan bahwa saya telah menggunakan nonce  k .

Karena  s = ( k^-1 ( H ( m ) + xr )), kita dapat dengan mudah menghitung kunci rahasia:

s = (k^-1(H(m) + xr))

ks = H(m) + xr

ks – H(m) = xr

x = r^-1(ks – H(m))

Oleh karena itu, penandatangan tidak hanya harus merahasiakan  kunci pribadi mereka , tetapi semua nonce yang pernah mereka buat adalah rahasia.

Bahkan jika penandatangan merahasiakan setiap  nonce NONCES , jika dia secara tidak sengaja mengulangi satu  nonce NONCES  (bahkan untuk pesan yang berbeda),  kunci rahasia  juga dapat  segera dipulihkan .

Biarkan  ( r , s 1 ) dan  ( r , s 2 ) jadilah dua tanda tangan yang dibuat pada pesan  m 1 dan  m 2 (masing-masing) dari nonce yang sama  k - karena mereka memiliki nonce yang sama, nilai r akan sama, jadi ini sangat mudah bagi penyerang untuk mendeteksi:

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))

Setelah kami memulihkan nonce  k menggunakan rumus di atas, kami dapat memulihkan kunci pribadi dengan melakukan serangan yang dijelaskan sebelumnya.

Mari kita cerna ini sejenak.

Jika  nonce NONCES penandatanganan  pernah diungkapkan,  kunci rahasia dapat segera  dipulihkan , yang  merusak seluruh skema tanda tangan kami .

Juga, jika dua nonce berulang, tidak peduli apa pesannya,  penyerang  dapat dengan mudah mendeteksi ini dan segera  memulihkan kunci rahasia , sekali lagi merusak seluruh skema kami.

Ini cukup rapuh dan hanya  serangan ringan !

Namun ada  Lattice Attack baru   yang telah dijelaskan dengan sangat detail  (Joachim Breitner dan Nadia Heninger)Йоахим Брайтнер и Надя Хенингер 

Dokumen  [PDF] :  Bias Nonce Sense: Serangan Kisi terhadap Tanda Tangan ECDSA yang Lemah dalam Mata Uang Kripto

Di blockchain Bitcoin, kami menemukan transaksi tertentu:

transaksi:  08d917f0fee48b0d765006fa52d62dd3d704563200f2817046973e3bf6d11f1f

untuk Alamat Bitcoin:  15N1KY5ohztgCXtEe13BbGRk85x2FPgW8E

dan kami berhasil melipatgandakan tanda tangan palsu dan menerapkan kisi-kisi

di mana menggunakan  algoritma skrip  PythonLLL.py  dengan pemasangan paket di  GOOGLE COLAB

INSTALL >> SAGE + ECDSA + BITCOIN + algoritma LLL

Kami berhasil mendapatkan  Private Key dari  Bitcoin Wallet satu transaksi lemah di  ECDSA.

Instalasi

Jalankan skrip Bash: lattice.sh

Hasil dalam format HEX Kunci pribadi ditemukan!

File: ONESIGN.txt (Nilai Tanda Tangan ECDSA R, S, Z)

Kami menyebarkan tanda tangan palsu untuk algoritma skrip PythonLLL.py

File: PRIVATEKEY.txt

File: ADDRESS.txt

Memeriksa kunci pribadi di situs web bitaddress

Kunci pribadi ditemukan!

https://www.blockchain.com/btc/address/15N1KY5ohztgCXtEe13BbGRk85x2FPgW8E

0,001 BTC

ADDR: 15N1KY5ohztgCXtEe13BbGRk85x2FPgW8E
WIF:  5JCAmNLXeSwi2SCgNH7wRL5qSQhPa7sZvj8eDwxisY5hJm8Uh92
HEX:  31AFD65CAD430D276E3360B1C762808D1D051154724B6FC15ED978FA9D06B1C1 

Video ini dibuat untuk  portal CRYPTO DEEP TECH  untuk memastikan keamanan finansial data dan kriptografi kurva eliptik secp256k1 terhadap tanda tangan ECDSA yang lemah dalam cryptocurrency BITCOIN

Video:  https://youtu.be/YP4Xj6gUcf4

Telegram :  https://t.me/cryptodeeptech

Sumber:  https://cryptodeep.ru/lattice-attack