Approximate GCD Explained: عندما يختبئ الـSecret Prime داخل حسابات عادية

🇺🇸EN🇸🇦AR
• 9 min read • #Approximate GCD, #Lattice Cryptanalysis, #LLL, #Cryptography, #Homomorphic Encryption, #CTF

تخيل إنك خبيت مفتاح بيتك جوه كرة بولينج، وبعدها حطيت ألف كرة بولينج شبهها قدام البيت. أمان جدًا، صح؟ المشكلة إن الكرات مش هتفضل "متطابقة" لو حد قرر يوزنها واحدة واحدة. أول ما يلاحظ إن كل الكرات قريبة جدًا من نفس الوزن، موضوع إخفاء المفتاح انتهى تقريبًا.

ده بالضبط اللي بيحصل لما حد يعمل نظام تشفير من عنده، يضرب Secret Prime في رقم عشوائي، يضيف شوية noise، وبعدها يقرر إن كده اخترع cryptography.

الرياضيات هنا لها اسم: Approximate GCD problem، وهو جزء أساسي من مجموعة من الـschemes المبنية على أعداد صحيحة. لو اخترت حجم الـnoise بشكل غلط، كل النظام ممكن يقع باستخدام laptop وlattice reduction algorithm فقط.

المقالة دي بتشرح ما هي Approximate GCD، وليه ناس كتير بتعيد اختراعها بطريقة سيئة، وإزاي ممكن تكسرها لما تكون الـparameters مضبوطة بشكل سيئ، والأهم، إزاي ما تكونش أنت الشخص اللي يلاقي الـSecret Prime بتاعه في writeup لحد تاني.

ما هي Approximate GCD أصلًا؟

الـGCD العادي قديم ومعروف: عندك رقمين وعايز تعرف أكبر رقم يقسمهم الاتنين. Approximate GCD بيسأل سؤال ألطف شوية، لكن أخطر: لو عندك مجموعة أرقام، وكل رقم قريب من multiple لقيمة سرية واحدة، هل تقدر تسترجع القيمة السرية دي؟

بشكل رسمي، عندك عينات بالشكل ده:

x_i = p * q_i + r_i

هنا p هو الـsecret اللي بتحاول تحميه، اعتبره مثلًا مفتاح خاص، وq_i هو random multiplier كبير ويتغير كل مرة، وr_i هو "noise" صغير مضاف عشان يخلي استرجاع p أصعب.

لو r_i كان دائمًا صفر، فاسترجاع p هيكون مجرد:

gcd(x_1, x_2, ...)

وده trivial. الـnoise هو المفروض يكون الجزء اللي بيخلي المشكلة صعبة.

نفس الفكرة دي موجودة في أساس integer-based homomorphic encryption، وهي schemes تسمح لك تعمل operations على encrypted data من غير ما تفك التشفير أولًا.

الـencrypted bit الواحد ممكن يبقى بالشكل ده:

c = p * q + 2 * r + b

p هو الـsecret prime، وq هو randomness على مستوى الـnoise، وr هو random noise صغير، وb هو الـbit الفعلي اللي بتحاول تخبيه، إما 0 أو 1.

وجود 2 * r هنا مقصود. لأنه يخلي:

c mod 2

يفضل مساويًا للـbit بعد إزالة الجزء المرتبط بـp.

فكرة لطيفة على الورق. لكن أمان الـscheme كله معتمد على حاجتين: إن r يكون صغير بشكل كافي، وإن p يكون كبير بشكل كافي بحيث ما نقدرش نفصلهم عن بعض.

لماذا يهمك هذا أصلًا؟

غالبًا مش هتكتب "Approximate GCD" في job description عندك، وده طبيعي. أصلًا أغلب الناس اللي بيبنوا custom encryption مش سمعوا عنه، ودي هي المشكلة.

نوع المشاكل ده بيظهر كل ما حد يعمل واحدة من الحاجات دي:

  • يبني custom encryption بدل ما يستخدم audited library، لمجرد إن استخدام big primes وrandomness بيديه إحساس إن الـscheme "عبقري"
  • يطبق homomorphic نظام تشفير من paper من غير ما يلتزم بالـparameter sizes الفعلية
  • يضيف "noise" لمجرد الـobfuscation ويفترض إن noise معناها security
  • يختار أحجام الـnoise والـmultipliers بناءً على الإحساس، بدل ما تكون مبنية على إثبات أمان فعلية

النتيجة هنا مش مجرد leak صغير. ممكن تسترجع الـsecret key بالكامل، وبالتالي أي قيمة اتعمل لها encryption بنفس الـkey.

مش تسريب جزئي. الموضوع ممكن يكون انهيار كامل وصامت ويمكن إثباته رياضيًا، والمهاجم مش محتاج يعرف كل تفاصيل الـimplementation من البداية. يكفيه عدد كافي من عينات معمولة تحت نفس الـsecret.

مثال عملي: كسر Bit Cipher معمول يدويًا

خلينا نبني نسخة افتراضية من scheme مشابهة، ونشوف بالضبط فين بتبدأ تقع.

البداية

عندنا مشروع جانبي صغير بيعمل encrypt لكل bit من secret message بشكل منفصل.

الـ"encryption" لبت واحد شكلها كده:

from Crypto.Util.number import getPrime
import random

class BitCipher:
    def __init__(self, prime_bits=1024):
        self.p = getPrime(prime_bits)

    def encrypt_bit(self, bit):
        q = random.randint(self.p, self.p**2)
        r = random.randint(2**256, 2**512)
        return self.p * q + 2 * r + bit

    def encrypt_message(self, message: str):
        bits = "".join(f"{ord(c):08b}" for c in message)
        return [self.encrypt_bit(int(b)) for b in bits]

من بعيد، الموضوع شكله معقول من بعيد. Prime كبير، وrandom multiplier كبير، وnoise حجمه محترم.

والـcomments في الكود الأصلي كانت بتتكلم عن "noise rituals" و"entropy harvested from chaos".

شعر. مش تشفير.

الفكرة وراء الـattack

هنا النقطة المهمة فعلًا:

p حجمه 1024 bits، بينما الـnoise r ممكن يوصل تقريبًا إلى 512 أو 513 bits.

يعني الـnoise حوالي نصف حجم الـsecret.

عشان Approximate GCD تكون صعبة فعلًا، الـnoise لازم يكون صغير جدًا مقارنة بالـsecret، ويفضل يكون مربوط بـsecurity parameter حقيقي، مش "نصف عدد الـbits لأن الرقم شكله كبير ومطمّن".

ولما يبقى عندك مئات الـencrypted bits، يعني ciphertext لكل bit من الرسالة، مش محتاج تخمن p.

تقدر تستخرجه.

الـAttack خطوة بخطوة

  1. التعرّف على شكل المعادلة. المعادلة: 
    c = p*q + 2r + b
    هي تقريبًا العلامة الكلاسيكية على Approximate GCD / integer-FHE structure. أول ما تشوف custom cipher بيعمل: 
    secret * big_random + small_random
    فأنت عرفت تقريبًا عيلة الـattack اللي هتدور عليها.
  2. بناء Kernel Lattice. خد مجموعة من الـciphertexts: 
    c_1, ..., c_d
    وابنِ lattice مصمم لإيجاد integer vectors اسمها u تحقق: 
    u · c = 0
    ده بيتم باستخدام scaling trick: بتحط identity matrix بجانب نسخة scaled بشكل ضخم من قيم الـciphertext، وبعدها تشغل lattice reduction باستخدام LLL. لأن الـscaling factor ضخم جدًا، الـreduced basis بتتجبر على تصفير الـciphertext component، وده بيديك basis حقيقية لـ"kernel" الخاص بمتجه الـciphertexts.
  3. خلّي الـnoise يكشف نفسه. كل vector u موجود في الـkernel يحقق: 
    u · c = 0
    وده معناه إن: 
    u · r
    لازم يكون multiple صحيح تمامًا لـ p . ولو قيم عناصر u صغيرة بشكل كافي، فإن u · r هيكون أصغر من p في القيمة المطلقة. والـmultiple الوحيد لـ p اللي قيمته المطلقة أصغر من p هو 0 . إذًا: 
    u · r = 0
    من غير ما تحتاج تخمن.
  4. حل متجه الـnoise. بعد ما تجمع عدد كافي من العلاقات دي، متجه الـnoise الحقيقي r يبدأ يتحدد داخل lattice أصغر للـresidual. في العادة تقدر توصل إلى من الرتبة 2، بسبب الاتجاهين اللي ما تمش التخلص منهم بالكامل، وهما اتجاه الـciphertext واتجاه متبقٍ واحد للـnoise. بعد كده reduction ثانية أصغر، مع حقيقة إن كل r_i لازم يكون رقم موجب وصغير، بتقفل المسألة وتحدد قيم الـnoise نفسها.
  5. استرجاع الـprime. لما تعرف r بدقة، تقدر تحسب: 
    p = gcd(c_1 - r_1, c_2 - r_2, ...)
    لأن الـالـrandom multipliers q_i عشوائية، فعمليًا نادر جدًا ما يكون بينها common factor إضافي غير p نفسه. والـGCD هينظف لك الموضوع.
  6. فك تشفير كل شيء. دلوقتي عندك p . كل ciphertext يقدر يتحول إلى bit بالشكل ده: 
    bit = (c mod p) mod 2
    لأن 2r دائمًا even، وطالما r < p فالبت الحقيقي يطلع كما هو. طبّق ده على كل bit مشفّر، والرسالة كلها هتظهر.

ولا خطوة من دول احتاجت brute force، ولا guessing للـprime، ولا أي ضعف في prime generation نفسها.

الـprime كان سليم.

المشكلة كانت في noise budget.

والـlattice reduction حولت "مخفي" إلى "محسوب" في وقت قليل جدًا.

أفكار مرتبطة

  • تقليل الـnoise أكثر من كده يخلي الـattack أسهل، مش أصعب، لأن المسافة بين "صغير كفاية عشان يختفي داخل المعادلة" وبين "حجم الـsecret الحقيقي" بتكبر.
  • إعادة استخدام نفس الـsecret prime مع عدد كبير من الـciphertexts هي اللي خلت الـattack عملية. عدد قليل من الـعينات ممكن يكون كفاية، والمئات فقط خلت بناء الـlattice أريح.
  • لو استبدلت الـعملية الضرب المصممة يدويًا دي بـFHE library حقيقية ومعاها parameters مختارة بناءً على إثبات أمان، فسلسلة الـattack دي بتتوقف، لأن نسبة الـnoise إلى الـsecret اللي يفرضها الـproof بتقفل المساحة اللي الـlattice محتاجاها.

أمثلة على كود ضعيف

الكود الضعيف: الـnoise يمثل نسبة كبيرة من bit length الخاص بالـsecret، ونفس الـsecret بيتم reuse عبر عدد كبير من الـencryptions المستقلة.

# VULNERABLE: noise (up to 512 bits) is way too large relative to
# the 1024-bit secret, and the same secret is reused for every bit.
class BitCipher:
    def __init__(self, prime_bits=1024):
        self.p = getPrime(prime_bits)

    def encrypt_bit(self, bit):
        q = random.randint(self.p, self.p**2)
        r = random.randint(2**256, 2**512)      # <- noise is far too big
        return self.p * q + 2 * r + bit

الكود بعد الإصلاح: ما تبنيش cryptography من الصفر. استخدم maintained وpeer-reviewed cryptography library لأي حاجة محتاجة أمان حقيقي.

ولو أنت بتجرب homomorphic encryption تحديدًا، استخدم audited library مثل Microsoft SEAL أو OpenFHE أو TFHE-rs، وسيب اختيار الـparameters للناس اللي شغلت في المجال ده فعلًا، مش random noise range اخترته لأن الأرقام شكلها كبير بما يكفي.

# PATCHED: use audited primitives. If you need to hide a bit or a
# message, use authenticated symmetric encryption, full stop.
from cryptography.fernet import Fernet

key = Fernet.generate_key()
cipher = Fernet(key)
token = cipher.encrypt(b"the actual secret message")

أيوه، الكود أصغر وأملّ.

وده هو المطلوب أصلًا.

الحماية: إزاي ما تقعش في Approximate GCD

  1. ماتخترعش نظام تشفير من عندك لحاجة مهمة. حتى لو كانت "أداة داخلية صغيرة". الأدوات الصغيرة عندها موهبة غريبة في إنها توصل بعد فترة لحاجة مهمة جدًا.
  2. لو لازم تطبق cryptosystem منشور، التزم بالـparameters كما هي. الـإثبات أمان بتاعة الـscheme مبنية على نسبة noise-to-secret محددة. غيّر النسبة، والـproof والـsecurity يمشوا معاها.
  3. ماتستخدمش نفس الـsecret عبر عينات كثيرة في noise-based scheme. كل sample إضافي هو equation جديدة يقدر المهاجم يدخلها إلى الـlattice.
  4. استخدم secrets بدل random لأي حاجة security-relevant في Python. مش دي كانت الـالثغرة الرئيسية هنا، لكن random الافتراضي في Python مبني على Mersenne Twister، وده مش cryptographically secure، واسترجاع الـstate من مخرجاته هو نوع هجوم كامل لوحده.
  5. خلي حد يراجع الكود. خمس دقائق من شخص شاف Approximate GCD writeup قبل كده كان ممكن تكتشف المشكلة دي قبل ما الـالكود يطلع أصلًا.

نقاط الفحص والمراجعة

لو بتراجع code ووجدت أي حاجة من دول، وقف واسأل أسئلة صعبة:

  • فيه "secret" بيتضرب في large random number، وبعدها بيتضاف له random أصغر بهدف "obfuscation"
  • comments معمولة باستعارات عن "noise" و"chaos" و"entropy rituals" بدل reference لـpaper أو standard فعلي
  • مفيش reference لـcryptographic scheme معروف وله إثبات أمان
  • نفس الـsecret key مستخدمة مع عشرات أو مئات الـciphertexts المستقلة

الخلاصة

Approximate GCD مش مجرد academic curiosity غريبة محدش بيستخدمها.

دي جزء أساسي من الأساس الرياضي وراء أبحاث integer-based homomorphic encryption، والمشكلة نفسها فعلًا صعبة لما الـparameters تتختار بشكل صحيح.

المشكلة مش في الـmath.

المشكلة لما حد يقرأ paper بسرعة، ينسخ المعادلة، وبعدها يحدد حجم الـnoise بعينه لأن "نصف الـbit length" شكله conservative كفاية.

ماكانش كذلك.

الـlattice مش فارق معاها أنت كنت واثق قد إيه.

أفضل custom cipher هو الـcipher اللي ما كتبتوش أصلًا.

المراجع