معاملة واحدة ضعيفة في ECDSA على Bitcoin blockchain وبمساعدة Lattice Attack ، تلقينا مفتاح خاص لعملات BTC

 

ماذا نعرف عن هجوم الشبكة؟

بادئ ذي بدء ، فإن  خوارزمية التوقيع الرقمي للمنحنى الإهليلجي (ECDSA)  هي مخطط توقيع رقمي شائع نراه في العديد من مراجعات الكود لدينا. يحتوي على بعض الخصائص المرغوبة ، ولكن يمكن أن يكون أيضًا هشًا للغاية لاستعادة المفتاح الخاص بهجوم القناة الجانبية الذي يكشف أقل من بت واحد من nonce السري.

ECDSA هو شكل خاص من خوارزمية التوقيع الرقمي  (DSA). DSA هو مخطط توقيع رقمي شائع إلى حد ما ، والذي يتم تحديده من خلال ثلاث خوارزميات: إنشاء المفتاح والتوقيع والتحقق. تقوم خوارزمية توليد المفاتيح بإنشاء مفاتيح خاصة وعامة ؛  المفتاح الخاص مسؤول عن إنشاء التوقيعات ؛  والمفتاح العمومي مسؤول عن التحقق من التوقيعات.  تأخذ خوارزمية التوقيع رسالة ومفتاح خاص كمدخلات وتقوم بإنشاء توقيع. تأخذ خوارزمية التحقق رسالة وتوقيعًا ومفتاحًا عامًا كمدخلات وتعيد قيمة  true أو  falseتشير إلى ما إذا كان التوقيع صالحًا أم لا.

DSA يتم تعريفه لأي مجموعة رياضية ، وهذا المخطط آمن طالما أن مشكلة اللوغاريتم المنفصلة صعبة بالنسبة لتلك المجموعة. مجموعة شائعة الاستخدام هي الأعداد الصحيحة modulo a عدد أولي 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 ، وتفسير النتيجة على أنها عدد صحيح modulo 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 + b بالنسبة للبعض  a , b . بالنسبة إلى منشور المدونة هذا ، كل ما تحتاج إلى معرفته هو أنه باستخدام المنحنيات البيضاوية ، يمكنك تحديد مجموعة محدودة ، مما يعني أنك تحصل على منشئ المجموعة  g (نقطة منحنى ناقص) وعمليات  الجمع  والضرب  النقطي  تمامًا كما تفعل أنت يمكن مع الأعداد الصحيحة. نظرًا لأنهم يشكلون مجموعة محدودة ،g ، سيكون لها أمر محدود ،  p. لن يشرح منشور المدونة هذا أو يطلب منك معرفة كيفية  عمل عمليات المنحنى البيضاوي .

ECDSA يعمل بنفس الطريقة  DSAولكن مع مجموعة مختلفة.  سيظل  المفتاح السري  عبارة عن أعداد صحيحة ذات قيمة عشوائية  .  الآن لا يزال يتم حساب  المفتاح العمومي  على أنه  ، باستثناء أن g هي الآن نقطة على المنحنى الإهليلجي. هذا يعني أن y ستكون أيضًا نقطة على المنحنى الإهليلجي (كانت y سابقًا عبارة عن معامل عدد صحيح p). الفرق الآخر هو كيف نحسب قيمة r. ما زلنا نولد عددًا عشوائيًا من الحرف غير المتماثل k كوحدة نمطية صحيحة p كما كان من قبل. سنحسب   ، مرة أخرى ،  نقطة على منحنى ناقص ، وبالتالي   أيضًا. لذلك ، يمكننا الحساب   والتعيين   . الآن المعنى xpyy = g^xg^kgg^k( x^k , y^k ) = g^kr = x^ks يمكن حسابها كما كان من قبل ، ونحصل على توقيعنا  ( r , s )، والذي لا يزال عددًا صحيحًا modulo  p ، كما كان من قبل. للتحقق ، نحتاج إلى تصحيح حقيقة أننا حسبنا  r بطريقة مختلفة قليلاً.

لذلك ، كما في السابق ،  نحسب  قيمة  ( g^H(m)y^r)^ŝ ، ولكن هذه القيمة الآن هي نقطة على المنحنى الناقص ، لذلك نأخذ  x- تنسيق هذه النقطة ونقارنها بقيمة  r .

استعادة  المفاتيح السرية  من الرموز غير المستخدمة المعاد استخدامها 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))

لذلك ، يجب على الموقِّع ألا يحتفظ  بسرية مفتاحه الخاص فحسب ، بل يجب أن تظل جميع الرسائل التي قام بتوليدها سرية.

حتى إذا احتفظ الموقّع بكل  سرية غير متوقعة NONCES ، إذا كرر عن طريق الخطأ مرة واحدة  ( NONCES  حتى مع الرسائل المختلفة) ،   يمكن أيضًا  استرداد المفتاح السري على الفور .

لنكن   توقيعين تم إنشاؤهما على الرسائل  ( 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  على الإطلاق ،  فيمكن  استرداد المفتاح السري على الفور ، مما  يكسر مخطط التوقيع بالكامل .

أيضًا ، إذا تكررت قطعتان ، بغض النظر عن الرسائل ،  يمكن للمهاجم  اكتشاف ذلك بسهولة  واستعادة المفتاح السري على الفور ، مما يؤدي مرة أخرى إلى كسر مخططنا بالكامل.

إنها هشة جدًا وهي  هجمات خفيفة فقط !

لكن هناك  هجوم شبكي جديد   تم وصفه بتفصيل كبير  (يواكيم برايتنر وناديا هينجر)Йоахим Брайтнер и Надя Хенингер 

مستند  [PDF] :  تحيز Nonce Sense: هجمات شبكية ضد تواقيع ECDSA الضعيفة في العملات المشفرة

في Bitcoin blockchain ، وجدنا معاملة معينة:

المعاملة:  08d917f0fee48b0d765006fa52d62dd3d704563200f2817046973e3bf6d11f1f

لعناوين البيتكوين:  15N1KY5ohztgCXtEe13BbGRk85x2FPgW8E

وتمكنا من مضاعفة التواقيع المزيفة وتطبيق الشبكة

حيث يتم استخدام  خوارزمية Python script  algorithmLL.py  مع تثبيت الحزم في  GOOGLE COLAB

تثبيت >> SAGE + ECDSA + BITCOIN + خوارزمية LLL

تمكنا من الوصول  Private Key من  Bitcoin Wallet صفقة ضعيفة واحدة في  ECDSA.

تثبيت

تشغيل البرنامج النصي Bash: lattice.sh

النتيجة في تنسيق HEX تم العثور على المفتاح الخاص!

الملف: ONESIGN.txt (توقيع ECDSA R ، S ، Z Value)

لقد نشرنا تواقيع وهمية لخوارزمية برنامج بايثون النصي LLL.py

الملف: PRIVATEKEY.txt

الملف: ADDRESS.txt

التحقق من المفتاح الخاص على موقع bitaddress

تم العثور على مفتاح خاص!

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

0.001 بيتكوين

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

تم إنشاء هذا الفيديو  لبوابة CRYPTO DEEP TECH  لضمان الأمان المالي للبيانات وتشفير المنحنى البيضاوي secp256k1 مقابل توقيعات ECDSA الضعيفة في عملة البيتكوين المشفرة

فيديو:  https://youtu.be/YP4Xj6gUcf4

برقية :  https://t.me/cryptodeeptech

المصدر:  https://cryptodeep.ru/lattice-attack