Side-Channel ECDSA: لماذا خوارزمية القسمة ما تقدر تخبي سرّك

Side-Channel ECDSA: لماذا خوارزمية القسمة ما تقدر تخبي سرّك

تخيل إنك كتبت سرّك على ورقة، بعدين مزّقت الورقة، وحرّقت القصاصات، ونثرت الرماد في البحر. أمن، صح؟ الحين تخيل إنك سويت كل هذا، بس بعد كل خطوة كنت تشرّح بالتفصيل لشخص واقف جنبك ويحمل دفتر وقلم. هذا بالضبط اللي يصير مع side-channel في البرمجة. السر اختفى، بس “كيف” تعاملت معه لسه مسموع.

هالمقال يشرح ثغرة side-channel محددة في تطبيق ECDSA مخصص يستخدم خوارزمية binary GCD عشان الـ modular inversion. الـ masking ممتاز. المنحنى قياسي. توليد المفتاح سليم. بس خوارزمية القسمة تهمس كل خطوة في الـ trace، وهذا الـ trace كافي عشان نسترجع المفتاح الخاص من توقيع واحد. بنفصص بالضبط كيف ولىش وليش وكيف نعالجها.

طيب، وش هي Side-Channel ECDSA؟

ECDSA (Elliptic Curve Digital Signature Algorithm) هي خوارزمية التوقيع اللي ورا Bitcoin وشهادات TLS وكثير من البنية التحتية اللي تعتمد عليها كل يوم. المعادلة الأساسية:

s = k^(-1) * (z + r*d) mod n

حيث d هو المفتاح الخاص، k هو nonce عشوائي، z هو hash الرسالة، r هو x-coordinate نقطة k*G، وn هو ترتيب المنحنى. إذا تسرّب k (حتى جزئياً)، المفتاح الخاص d يطلع بجبر بسيط. عشان كذا كل تطبيق ECDSA محترم يعامل الـ nonce مثل رموز إطلاق صواريخ.

هجوم side-channel يستغل معلومات تتسرب عبر التنفيذ الفعلي للخوارزمية بدل ما يستغل ضعف رياضي. استهلاك الطاقة، الـ timing، الإشعاعات الكهرومغناطيسية، وفي حالتنا، تتبع استدعاءات الدوال بشكل صريح، كلها تقدر تحمل بيانات سرّة عبر قنوات ما صممها المطوّر عشان تكون آمنة.

الثغرة اللي نتكلم عنها خطيرة لأن التطبيق اختار يكشف الـ trace كميزة (للـ debugging أو الشفافية)، وما يدري إن الـ trace يحمل معلومات كافية عشان نعيد بناء الـ nonce المُموّه mask * k، نحلله لـ عوامل، ونسترجع k، واللي بدوره يعطينا d بسهولة.

ليش تهتم؟

• أي primitive تشفير مخصص يتفرع على بيانات سرّة هو خطر side-channel. إذا الكود فيه if (secret_bit == 1)، أي مهاجم يقدر يراقب الـ branch يقدر يسترجع الـ bit.
• الـ masking ما ينفع إذا الـ mask قابل للملاحظة. ضرب الـ nonce بعامل تمويه عشوائي mask قبل المعالجة هو دفاع قياسي. بس إذا الناتج mask * k قابل للاسترجاع من الـ trace، تحت بس تحلله.
• التحليل (factoring) يرخص كل يوم. رقم 512-bit اللي كان “صعب” قبل عشر سنين الحين يقدر ينحل بـ ECM على جهاز واحد بدقائق لساعات، خصوصاً إذا فيه عوامل صغيرة.
• هذا مو نظري. الهجوم اللي نصفه يشتغل على trace توقيع واحد. ما يحتاج تجميع إحصائي عبر traces متعددة.

السيناريو: تطبيق ECDSA “آمن”

تخيل خدمة توقيع تطبّق ECDSA على منحنى P-256 بالحمايات التالية:

1. تمويه السلم لضرب النقاط: الـ nonce يتم تمويهه كـ k + mask1 * N قبل ضرب النقاط، عشان الـ bit pattern اللي يعالجه الـ double-and-add ما هو bits الـ k.
2. عشوائية الإحداثيات: النقطة الأساسية والنقاط الوسيطة يتم ضرب إحداثياتها الـ Jacobian بأقنعة عشوائية، عشان نمنع التسريب عبر تمثيل النقطة.
3. تمويه الـ nonce للقلب: البسط والمقسوم في حساب التوقيع يتم ضربهما بـ mask2 عشوائي طازج، عشان الـ modular inversion ما يعالج k مباشرة.

هذا شكل دالة التوقيع (مبسّطة بأسماء generic):

def sign(private_key, message_hash):
    k = random_scalar()                    # nonce طازج

    # تمويه لضرب النقاط
    mask1 = random_scalar()
    blinded_k = k + mask1 * N              # k + mask1*N، مو bits الـ k

    R = scalar_mul(blinded_k, randomized(G))
    r = R.x % N

    # تمويه للقلب
    mask2 = random_scalar()
    numerator = mask2 * (message_hash + r * private_key)   # mask2 * (z + r*d)
    denominator = mask2 * k                                   # mask2 * k (bignum كامل!)

    s = div(numerator, denominator, N)
    return (r, s)

يبدو ممتاز، صح؟ ثلاثة أقنعة عشوائية مستقلة، ما فيه تعرّض مباشر لـ k. المشكلة في div().

التسريب: خوارزمية قسمة مخصصة

دالة div() ما تستخدم مكتبة قلب معيارية. تستدعي _binary_division_odd_modulus(a, b, modulus) اللي تطبّق خوارزمية binary GCD للقسمة المعيارية:

def div(a, b, modulus):
    a = a % modulus              # يقلل البسط: mask2*(z+r*d) mod N
    return _binary_division_odd_modulus(a, b, modulus)  # b = mask2*k (غير مقلل!)

لاحظ إن a يتم تقليله mod N (256 bit)، بس b يمرّ كـ bignum كامل 512-bit mask2 * k. هذا يعني إن الـ binary GCD يشتغل على u بـ 512-bit وv = N بـ 256-bit، والـ control flow كله يعتمد على bit pattern بتاع u = mask2 * k.

هذي الخوارزمية مع التعليقات اللي تبيّن وين التسريب:

def _binary_division_odd_modulus(a, b, modulus):
    u = b          # = mask2 * k (512 bit) — السر في bits الـ u
    v = modulus    # = N (256 bit، معروف)
    x1 = a         # = mask2 * (z+r*d) mod N (256 bit)
    x2 = 0

    while u != 1 and v != 1:
        # الحلقة الأولى: تجريد الأصفار اللاحقة من u
        while (u & 1) == 0:
            u = half(u)                       # يسرب: "h" — يخبرك u كان زوجي
            if (x1 & 1) == 0:
                x1 = half(x1)                 # يسرب: "hh" — x1 bit = 0
            else:
                x1 = half(add(x1, modulus))  # يسرب: "hah" — x1 bit = 1

        # الحلقة الثانية: تجريد الأصفار اللاحقة من v
        while (v & 1) == 0:
            v = half(v)                       # يسرب: نفس النمط لـ v/x2

        # الطرح (الاتجاه ما يتم تسريبه مباشرة)
        if u >= v:
            u = sub(u, v)                     # يسرب: "ss"
            x1 = sub(x1, x2)
        else:
            v = sub(v, u)                     # يسرب: "ss" (نفس الـ trace!)
            x2 = sub(x2, x1)

    if u == 1:
        return mod(x1, modulus)              # يسرب: "r"
    return mod(x2, modulus)                  # يسرب: "r"

كل استدعاء لـ half وadd وsub وmod يتم تتبعه. الـ trace هو سلسلة أحرف مثل hhsshahsshahss...r. من هذي السلسلة، المهاجم يقدر يستخرج:

1. عدد التجريدات (كم hh/hah بين علامات ss): هذا يساوي trailing-zero count لـ u أو v في كل خطوة.
2. Bits مكشوفة: كل hh يعني إن القيمة المقابلة x كان LSB=0، وكل hah يعني LSB=1.
3. عدد التكرارات الكلي: عدد أنماط ss.

الهجوم: خطوة بخطوة

الخطوة 1: استرجاع a = mask2 * (z + r*d) mod N

قبل أول v-subtraction (اللي يصير لما u يصغر تحت v = N)، كل الـ subtractions هي u-subtractions وكل التجريدات هي u-strips. خلال هذي المرحلة، x1 يبقى في [0, N)، عشان LSBs تاعه هي مباشرة bits القيمة المعيارية.

المفتاح: بعد K من u-strips، x1_K = (a + N * S) / 2^K حيث S = مجموع الـ bits بأوزان 2^0، 2^1، ...، 2^{K-1}.

عشان x1_K يكون integer صحيح في [0, N)، لازم a + N * S ≡ 0 (mod 2^K)، واللي يعطينا:

a ≡ -N * S (mod 2^K)

حيلة الكشف: جرّب K = 256، 257، 258، … لـ K الصحيح (العدد الفعلي لـ u-strips قبل أول v-sub)، a = -N * S mod 2^K يقع في [0, N). لأي K غلط (اللي يشمل bits من v-strip)، يقع خارج [0, N). عملياً، K واحد بالضبط يشتغل، وهو تقريباً دائماً 256.

الخطوة 2: استرجاع u = mask2 * k (الـ bignum الكامل)

معروف a، احسب u_red = a * s^(-1) mod N = mask2 * k mod N.

بعدين استخدم الانتشار constraint على عدد التجريدات. قبل أول v-sub، كل التجريدات هي u-strips. عدد تجريدات كل block يقيّد bits تاع u_init:

• Block 0: tz(u_init) تجريدات → bits 0 إلى count0-1 هي 0، bit count0 هي 1
• Block K: constraint يتضمن التعبير المتراكم u_K = (u_init + beta) / 2^s، حيث beta وs معروفين من معالجة الـ blocks السابقة

هذا يعطي u_init mod 2^L (عادة L ≈ 257).

أخيراً، طبّق مبرهنة الباقي الصيني (CRT):

• u_init mod 2^L معروف من الانتشار constraint
• u_init mod N = u_red معروف من العلاقة المعيارية

بما إن u_init < N^2 < 2^512 < 2^L * N، CRT يحدد u_init بشكل فريد.

الخطوة 3: تحليل (factor) u_init

u_init = mask2 * k هو رقم بـ ~512-bit. كلا العاملين بـ ~256-bit. استراتيجية التحليل:

1. القسمة التجريبية حتى 10^6: تشيل العوامل الأولية الصغيرة
2. Pollard’s rho (نسخة Brent): يلاقي عوامل حتى ~25 digit
3. Pollard’s p-1: يلاقي عوامل بـ p-1 ناعم
4. ECM (Elliptic Curve Method) مع GMP-ECM: يلاقي عوامل حتى 40 digit بكفاءة، و65 digit بـ curves كافية

عملياً، مزيج من هذي الطرق حلّل الرقم بالكامل. الإختراق المفتاحي كان ECM بـ B1=10^8 اللي لقى عامل أولي بـ 105-bit (32 digit).

الخطوة 4: تعداد القواسم وإيجاد k

مع التحليل الكامل، عدّد كل القواسم تاع u_init اللي تقع في (u_init/N, N) (لأن mask2 = u_init/k < N يعني k > u_init/N). هذا عادة يعطي بس كم مرشح.

لكل مرشح k:

d = (s * k - z) * inverse(r, N) mod N

تحقق عبر فحص d * G == public_key.

أمثلة الكود

خوارزمية القسمة المُتتبَّعة (ضعيفة)

# ضعيف: كل استدعاء half/add/sub يتم تتبعه، يسرب الـ control flow
def binary_division_traced(a, b, modulus):
    u, v, x1, x2 = b, modulus, a, 0
    while u != 1 and v != 1:
        while u % 2 == 0:
            u = trace_half(u)         # يسرب 'h'
            x1 = trace_half(x1) if x1 % 2 == 0 else trace_half(trace_add(x1, modulus))  # يسرب 'h' أو 'ah'
        while v % 2 == 0:
            v = trace_half(v)
            # ... نفس النمط لـ x2
        if u >= v:
            u = trace_sub(u, v)       # يسرب 's'
            x1 = trace_sub(x1, x2)    # يسرب 's'
        else:
            v = trace_sub(v, u)
            x2 = trace_sub(x2, x1)
    return trace_mod(x1 if u == 1 else x2, modulus)

المشكلة: الـ control flow كله محدد بـ bit pattern بتاع u = mask * k، وكل قرار تفرع قابل للملاحظة عبر الـ trace.

القلب بزمن ثابت (مُصحح)

# آمن: استخدم مكتبة قلب معيارية بزمن ثابت
def div_safe(a, b, modulus):
    a = a % modulus
    b_inv = pow(b, -1, modulus)  # Python 3.8+ يستخدم قلب بزمن ثابت
    return (a * b_inv) % modulus

أو، لو لازم تطبّح بنفسك، على الأقل ما تتبعه:

# أفضل: نفس الخوارزمية، بس بدون تتبع العمليات الداخلية
def binary_division_untraced(a, b, modulus):
    u, v, x1, x2 = b, modulus, a, 0
    while u != 1 and v != 1:
        while u % 2 == 0:
            u = u // 2                    # بدون استدعاء تتبع
            x1 = x1 // 2 if x1 % 2 == 0 else (x1 + modulus) // 2
        while v % 2 == 0:
            v = v // 2
            x2 = x2 // 2 if x2 % 2 == 0 else (x2 + modulus) // 2
        if u >= v:
            u, x1 = u - v, x1 - x2
        else:
            v, x2 = v - u, x2 - x1
    return (x1 if u == 1 else x2) % modulus

الحل بسيط: ما تتبع العمليات الداخلية للخوارزميات التشفيرية، والأفضل لا تطبّح الـ modular arithmetic بنفسك.

الدفاع / كيف نصلح

1. ما تتبع internals تشفيرية أبداً. إذا تحتاج debugging traces، حطها وراء flag وقت البناء مطفأ في الإنتاج. والأفضل، ما تتبع crypto إطلاقاً.

2. استخدم مكتبات تشفير مراجَعة. pow(b, -1, N) في Python 3.8+ وOpenSSL وlibsodium ومكتبات معتمدة أخرى تستخدم خوارزميات بزمن ثابت ما تتفرع على بيانات سرّة. الـ binary GCD مالك ما يسوي.

3. ما تمرّر أسرار غير مُقلّلة عبر كود leaky. في الكود الضعيف، b = mask2 * k يمرّ كـ bignum 512-bit غير مقلّل. لو b تم تقليله mod N قبل القسمة، الـ binary GCD بيشتغل على قيمة 256-bit والتسريب بكون مختلف (وإن لسه مو صفر).

4. تحقق إن التمويه يفيد فعلاً. إذا تموّه الـ nonce بـ mask2، تأكد إن الناتج mask2 * k غير قابل للاسترجاع من أي قناة قابلة للملاحظة. في هذي الحالة، الـ control flow تاع الـ binary GCD على الناتج غير المُقلّل يهزم التمويه بالكامل.

5. فكّر في nonces حتمية (RFC 6979). إذا استخدمت nonces حتمية مشتقة من الرسالة والمفتاح الخاص، تشيل متطلب العشوائية الطازجة. بس بعد تحتاج تطبيق بزمن ثابت.

6. راجع كود big-integer المخصص. أي جملة if تتفرع على قيمة مشتقة من السر هي تسريب محتمل. استخدم مقارنات بزمن ثابت (عمليات bitwise) بدل منها.

الخلاصة

المفارقة في هذي الثغرة إن المطورين بوضوح حاولوا يكونوا آمنين. ضافوا ثلاث طبقات عشوائية: تمويه السلم، عشوائية الإحداثيات، وتمويه القلب. استخدموا binary GCD “بزمن ثابت” (ثابت بمعنى إنه دائماً يستدعي point_double وpoint_add في حلقة ضرب النقاط). على الأرجح كانوا حاسّين إنهم ممتازين.

بس بعد ضافوا ميزة trace تسجّل كل استدعاء half وadd وsub جوا خوارزمية القسمة. وخوارزمية القسمة تعالج الناتج غير المقلّل mask2 * k كرقم 512-bit. الـ trace يكشف الـ control flow كامل للـ binary GCD على هذي القيمة 512-bit، واللي يحدد mask2 * k بشكل فريد. من هناك، التحليل يعطي k، وk يعطي d.

الدرس مو “لا تستخدم binary GCD” أو “لا تضيف tracing.” الدرس هو: إذا تطبيقك التشفيري يتفرع على بيانات مشتقة من السر بطريقة قابلة للملاحظة، عندك side channel. تمويه الدخل ما ينفع إذا الـ mask * الناتج قابل للملاحظة. أكثر خوارزمية قسمة أمنًا هي اللي المكتبة القياسية مطبّقتها واختبرتها وراجعتها بالفعل. استخدمها.