بٹ کوائن بلاکچین پر ای سی ڈی ایس اے میں ایک کمزور لین دین اور لیٹیس اٹیک کی مدد سے ہمیں بی ٹی سی کوائنز کی ایک نجی کلید ملی

 

ہم گرڈ حملے کے بارے میں کیا جانتے ہیں؟

شروع کرنے کے لیے،  بیضوی وکر ڈیجیٹل سگنیچر الگورتھم (ECDSA)  ایک عام ڈیجیٹل دستخطی اسکیم ہے جسے ہم اپنے کوڈ کے بہت سے جائزوں میں دیکھتے ہیں۔ اس میں کچھ مطلوبہ خصوصیات ہیں، لیکن سائڈ چینل اٹیک کے ساتھ پرائیویٹ کلید کو بازیافت کرنا بہت نازک بھی ہو سکتا ہے جو ایک سے بھی کم خفیہ باتوں کو ظاہر کرتا ہے۔

ECDSA ڈیجیٹل سگنیچر الگورتھم کی ایک خاص شکل ہے  (DSA)۔ DSA ایک کافی عام ڈیجیٹل دستخطی اسکیم ہے، جس کی وضاحت تین الگورتھم سے ہوتی ہے: کلیدی جنریشن، دستخط، اور تصدیق۔ کلیدی نسل الگورتھم نجی اور عوامی چابیاں تیار کرتا ہے۔  پرائیویٹ کلید دستخط بنانے کے لیے ذمہ دار ہے۔  اور عوامی کلید دستخطوں کی تصدیق کے لیے ذمہ دار ہے۔  دستخط الگورتھم ان پٹ کے طور پر ایک پیغام اور ایک نجی کلید لیتا ہے اور ایک دستخط تیار کرتا ہے۔ تصدیقی الگورتھم ان پٹ کے طور پر ایک پیغام، ایک دستخط، اور ایک عوامی کلید لیتا ہے اور  true یا  کی قدر لوٹاتا ہے false، یہ بتاتا ہے کہ آیا دستخط درست ہے۔

DSA کسی بھی ریاضیاتی گروپ کے لیے بیان کیا گیا ہے، اور یہ اسکیم تب تک محفوظ ہے جب تک کہ مجرد لوگارتھم کا مسئلہ اس گروپ کے لیے مشکل ہو۔ عام طور پر استعمال ہونے والا گروپ عددی ماڈیول ایک پرائم نمبر p ہے۔

اس گروپ کے ساتھ ہمارے پاس ایک گروپ جنریٹر جی اور کچھ خفیہ نگاری سے محفوظ  ہیش  فنکشن  Hہوگا۔ ہم یہ فرض کر سکتے ہیں  p , g اور  H عام علم ہو گا۔

کلیدی جنریشن پہلے تصادفی طور  x پر modulo integers سے  ایک قدر منتخب کرکے کام کرتی ہے p ۔ پھر قیمت کا حساب لگایا جاتا ہے۔ y = g^x mod p

دستخط کی نجی کلید ہے  x ، اور عوامی کلید ہے  y ۔ دستخط کرنے والی کلید کو خفیہ رکھا جانا چاہیے، کیونکہ یہ وہی ہے جو دستخط کرنے کی اجازت دیتا ہے۔

دستخطی الگورتھم پیغام  m اور خفیہ کلید x سے ایک دستخط بناتا ہے۔ سب سے پہلے، ایک بے ترتیب گروپ عنصر پیدا ہوتا ہے  k ۔ یہ ایک غیر معمولی طور پر جانا جاتا ہے، جو حملوں کے وقت اہم ہے.

پھر اقدار کا حساب لگایا جاتا ہے  r = g^k mod p اور s = ( k^-1 ( H ( m ) + xr )) mod p

یہاں  k^- 1 ، الٹا گروپ ہے، اور  H ( m ) ہیش ایم کی کمپیوٹنگ کا نتیجہ ہے، اور نتیجہ کو عددی ماڈیولو p کے طور پر تشریح کرتا ہے۔

دستخط کو ایک جوڑے کے طور پر بیان کیا گیا ہے  ( r , s )۔ (نوٹ: اگر  r یا  قدروں میں سے کوئی ایک کے sبرابر ہے  0تو الگورتھم نئی قدر کے ساتھ دوبارہ شروع ہوتا ہے  k )۔

تصدیقی الگورتھم کو ان پٹ کے طور پر ایک دستخط  ( r , s )، ایک پیغام  m اور ایک عوامی کلید موصول ہوتی ہے۔ چلو  ŝ = s^-1 ، پھر الگورتھم صحیح ہو جاتا ہے اگر اور صرف اگر  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  اب بھی ایک بے ترتیب قدر modulo integers ہو  p گی۔ اب عوامی کلید  y کو اب بھی بطور شمار کیا جاتا ہے  y = g^x ، سوائے اس کے کہ g اب بیضوی وکر پر ایک نقطہ ہے۔ اس کا مطلب یہ ہے کہ 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اس نقطہ کا -coordinate لیتے ہیں اور اس کا اپنی قدر سے موازنہ کرتے ہیں  r ۔

 دوبارہ استعمال شدہ نانس سے  خفیہ چابیاں کی بازیافت NONCES

اب جب کہ ہم سمجھتے ہیں کہ یہ کیا ہے  اور یہ کیسے کام کرتا ہے، آئیے اس کی نزاکتECDSA  کا مظاہرہ کریں  ۔ ایک بار پھر، چونکہ یہ ایک ڈیجیٹل دستخطی اسکیم ہے، اس لیے یہ ضروری ہے کہ  خفیہ کلید  پیغام پر دستخط کرنے والے شخص کے علاوہ کسی اور کو ظاہر نہ کی جائے۔

تاہم، اگر دستخط کنندہ کبھی دستخط جاری کرتا ہے اور استعمال شدہ نانس بھی جاری کرتا ہے،  حملہ آور فوری طور پر خفیہ کلید  کو بازیافت کرسکتا  ہے۔

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

اس لیے، دستخط کنندہ کو نہ صرف اپنی  نجی کلید کو خفیہ رکھنا چاہیے ، بلکہ ان کی تمام نونسز جو انھوں نے تخلیق کی ہیں وہ خفیہ ہیں۔

یہاں تک کہ اگر دستخط کنندہ ہر ایک کو خفیہ رکھتا ہے  ، اگر وہ غلطی سے ایک نونس کو دہراتا ہے  (  مختلف  پیغامات کے لیے بھی)،  خفیہ کلید  کو بھی  فوری طور پر بازیافت کیا جا سکتا ہے ۔NONCES NONCES

آئیے  ( r , s 1 ) اور  پیغامات پر  اور   (بالترتیب) ایک ہی نانس سے  ( r , s 2 ) بنائے گئے دو دستخط ہوں   - چونکہ ان میں ایک ہی نونس ہے، اس لیے r کی قدریں ایک جیسی ہوں گی، اس لیے حملہ آور کے لیے اس کا پتہ لگانا بہت آسان ہے: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))

ایک بار جب ہم اوپر والے فارمولے کا استعمال کرتے ہوئے نونس  k کو بازیافت کر لیتے ہیں، تو ہم پہلے بیان کردہ حملے کو انجام دے کر نجی کلید کو بازیافت کر سکتے ہیں۔

آئیے ایک لمحے کے لیے اس کو ہضم کر لیں۔

اگر  کبھی دستخط نہ کرنے کا انکشاف NONCES  کیا جاتا ہے تو،  خفیہ کلید کو فوری طور پر  بازیافت کیا جاسکتا ہے ، جس  سے ہماری پوری دستخطی اسکیم ٹوٹ جاتی ہے ۔

اس کے علاوہ، اگر دو نونسز کبھی بھی دہرائی جاتی ہیں، چاہے پیغامات کچھ بھی ہوں،  حملہ آور  آسانی سے اس کا پتہ لگا سکتا ہے اور فوری طور پر  خفیہ کلید کو بازیافت کر سکتا ہے ، اور ہماری پوری اسکیم کو دوبارہ توڑ دیتا ہے۔

یہ بہت نازک ہے اور یہ صرف  ہلکے حملے ہیں !

لیکن ایک  نیا  لاٹیس اٹیک  ہے جس کو بڑی تفصیل سے بیان کیا گیا ہے  (جوآخم بریٹنر اور نادیہ ہیننگر)Йоахим Брайтнер и Надя Хенингер 

دستاویز  [پی ڈی ایف] :  متعصبانہ بے حسی: کرپٹو کرنسیوں میں کمزور ECDSA دستخطوں کے خلاف جعلی حملے

Bitcoin blockchain میں، ہمیں ایک خاص لین دین ملا:

لین دین:  08d917f0fee48b0d765006fa52d62dd3d704563200f2817046973e3bf6d11f1f

بٹ کوائن ایڈریسز کے لیے:  15N1KY5ohztgCXtEe13BbGRk85x2FPgW8E

اور ہم جعلی دستخطوں کو ضرب دینے اور گرڈ لگانے میں کامیاب ہو گئے۔

جہاں  GOOGLE COLAB  میں پیکجز کی تنصیب کے ساتھ  Python اسکرپٹ  algorithmLLL.py استعمال کرتے ہوئے

انسٹال کریں >> SAGE + ECDSA + BITCOIN + الگورتھم LLL

 ہم میں ایک کمزور لین دین سے  حاصل  Private Key کرنے  میں کامیاب ہو گئے ۔Bitcoin WalletECDSA

تنصیب

باش اسکرپٹ چلائیں: lattice.sh

HEX فارمیٹ میں نتیجہ پرائیویٹ کلید مل گئی!

فائل: ONESIGN.txt (ECDSA دستخط R, S, Z ویلیو)

ہم نے Python اسکرپٹ algorithmLLL.py کے لیے جعلی دستخطوں کا پرچار کیا۔

فائل: PRIVATEKEY.txt

فائل: ADDRESS.txt

بٹ ایڈریس ویب سائٹ پر پرائیویٹ کلید کو چیک کرنا

نجی کلید مل گئی!

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

0.001 بی ٹی سی

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

یہ ویڈیو  CRYPTO DEEP TECH پورٹل  کے لیے BITCOIN کریپٹو کرنسی میں کمزور ECDSA دستخطوں کے خلاف ڈیٹا اور secp256k1 بیضوی وکر کرپٹوگرافی کی مالی حفاظت کو یقینی بنانے کے لیے بنائی گئی تھی۔

ویڈیو:  https://youtu.be/YP4Xj6gUcf4

ٹیلیگرام :  https://t.me/cryptodeeptech

ماخذ:  https://cryptodeep.ru/lattice-attack