Obfuscated State Machine Explained: لما يتحول الـVerifier إلى متاهة

تخيل أنك كتبت كلمة سر صحيحة، لكن بدل ما يسألك البرنامج: “هل الكلمة تساوي القيمة الصحيحة؟”، قرر أن يحول كل حرف إلى bits، ثم يمشي بك في شارع فيه مئات التقاطعات، وكل تقاطع يغير قواعد المرور، وبعضها يطلب منك أيضًا إثباتات رياضية بـ256-bit integers.

هذا تقريبًا ما يحدث في بعض الـcustom binary verifiers.

من الخارج، البرنامج يبدو كأنه مجرد برنامج صغير يأخذ input ويطبع Success أو Failed. من الداخل، يمكن أن يكون عبارة عن State Machine كبيرة متخفية داخل عشرات أو مئات الدوال، مع dictionary lookups، lazy initialization، وقيود حسابية إضافية تجعل الـbrute force فكرة سيئة جدًا.

في هذا المقال سنفكك الفكرة من الصفر: كيف تكتشف الـstates، كيف تستخرج الـgraph، لماذا لا يكفي تحليل الـbranches وحده، وكيف تحوّل المسار الصحيح مرة أخرى إلى input صالح.

What Is an Obfuscated State Machine, Anyway?

الـState Machine العادية بسيطة جدًا:

State A + input 0 -> State B
State A + input 1 -> State C

كل ما تحتاجه هو معرفة الحالة الحالية والـinput حتى تعرف إلى أين تنتقل.

الـobfuscated verifier يفعل الشيء نفسه، لكنه يخفي كل شيء خلف طبقات من الـruntime والـfunction calls.

بدل أن تجد:

if (input[i] == 'A')
    state = 12;
else
    state = 57;

قد تجد شيئًا أقرب إلى:

input bytes
   ↓
bit string
   ↓
2-bit chunk
   ↓
AA lookup
   ↓
dispatcher
   ↓
next handler
   ↓
state update
   ↓
another handler

وهنا تبدأ المشكلة. البرنامج لم يعد يخبرك “القيمة الصحيحة هي X”. هو يخبرك بطريقة ملتوية جدًا: “أثبت أنك قادر على المرور عبر كل الحالات بالترتيب الصحيح”.

الفكرة الأساسية

في أحد الأنماط الشائعة لهذا التصميم، يوجد جدول نتائج يحتوي على قيم ابتدائية مثل:

0xffffffff

لكل state.

عندما يتم الوصول إلى state معيّن، يتم تغيير خانته إلى قيمة تدل على أنه زار هذه الحالة.

في النهاية، يمر verifier على الجدول:

هل ما زالت هناك خانة لم تتم زيارتها؟

ثم يقرر النجاح أو الفشل حسب منطق البرنامج المحيط بهذه العملية.

وهذا يعطيك clue مهم جدًا: بدل أن تبحث عن string مخفية، ابحث عن مكان تسجيل الزيارات.

Why Should You Care?

هذا النوع من الـverification يهمك في reverse engineering لأنه يغيّر طريقة التفكير بالكامل.

• البحث عن strcmp قد لا يفيدك.
• البحث عن الـflag داخل .rdata قد يعطيك لا شيء.
• الـbranches قد تكون صحيحة، لكن ترتيبها الخفي قد يعتمد على runtime data.
• وجود Success! لا يعني أن هناك secret string مقابلة لها.
• بعض الحالات قد تضيف قيودًا رياضية قبل أن تسمح بالانتقال التالي.

باختصار، أنت لا تحاول “العثور على السر”. أنت تحاول إعادة بناء القواعد التي تقرر أي input يستطيع عبور النظام بالكامل.

Worked Example: من Binary غامض إلى Graph مفهوم

لنفترض أن لدينا verifier يحتوي على 224 حالة.

كل handler يبدو كدالة ضخمة، وبعضها يبدأ بنمط مشابه:

cmp dword ptr [result_array + index*4], 0xffffffff

الـindex هنا مهم جدًا. إذا عرفت الـresult array وعرفت الـindex، تستطيع ربط الدالة بالـstate الذي تمثله.

1. Locate the result array

أول خطوة هي العثور على المكان الذي يحتوي على قيم الزيارة.

عمليًا، ابحث عن references إلى:

0xffffffff

بالقرب من repeated comparisons.

بعد تحديد عنوان الـarray، يمكنك تحويل:

[result_array + 0*4]
[result_array + 1*4]
[result_array + 2*4]
...

إلى:

State 0
State 1
State 2
...

هذه الخطوة وحدها تحوّل مئات الدوال من فوضى إلى objects يمكن تسميتها.

2. Map each state to its handler

بعد معرفة عنوان الـarray، نبحث عن تعليمات مثل:

cmp dword ptr [rip+disp32], 0xffffffff

نحل الـRIP-relative displacement، ثم نرى هل العنوان الناتج داخل الـresult array.

لو كان كذلك، نستطيع حساب الـslot:

slot = (target - array_va) // 4

الآن أصبح لدينا mapping:

slot 0   -> handler_0
slot 1   -> handler_1
slot 2   -> handler_2
...
slot 223 -> handler_223

وهنا يبدأ الـreverse engineering الحقيقي.

3. Discover the input alphabet

الـverifier لا يستهلك الـinput كـbytes مباشرة.

في هذا التصميم يتم تحويل كل byte إلى bits، ثم استهلاك الـbitstream على chunks صغيرة. المثال الأكثر وضوحًا هو 2-bit chunks:

00
01
10
11

وبالتالي كل state يمكن أن يملك حتى أربع وجهات محتملة.

مبدئيًا يمكنك تمثيلها هكذا:

State 17
 ├── 00 -> State 81
 ├── 01 -> State 9
 ├── 10 -> State 143
 └── 11 -> State 52

لكن توجد trap مهمة جدًا.

The Dictionary Trap

الـ2-bit values ليست بالضرورة مرتبطة دائمًا بنفس الـkey.

البرنامج يستخدم AA أو dictionary للوصول إلى الـtransition، وقد يتم استبدال هذا الـmapping أثناء التشغيل.

مثلًا، في البداية قد يكون:

0 -> 00
1 -> 01
2 -> 10
3 -> 11

ثم يتم تحميل mapping جديد:

0 -> 10
1 -> 11
2 -> 00
3 -> 01

لو استخرجت الـbranches من ترتيب ظهورها في الـdisassembly، قد تحصل على graph خاطئ تمامًا.

الحل هو تتبع الـkey نفسه.

الفكرة:

current_ecx = key
        ↓
AA lookup
        ↓
transition target

ليس:

first branch = 0
second branch = 1
...

هذه واحدة من أكثر الأخطاء إزعاجًا في هذا النوع من التحليل، لأن الـgraph الناتج يبدو منطقيًا حتى وهو غلط.

4. Reconstruct the Graph

بعد تتبع الـkeys والـlookup calls، يمكنك بناء graph حقيقي:

graph = {
    0: {0: 14, 1: 72, 2: 19, 3: 41},
    1: {0: 91, 1: 10, 2: 33, 3: 77},
    # ...
}

يمكنك عندها التعامل مع الـverifier كمشكلة graph بدل مشكلة assembly.

والـgoal يصبح:

ابدأ من الـentry state
اتبع transition صالح
لا تعُد إلى state زارته سابقًا
واستمر حتى يتم تغطية كل الحالات المطلوبة

في design يعتمد على زيارة كل الحالات، تصبح المسألة قريبة من Hamiltonian Path.

5. The Second Layer: BigInt Constraints

هنا يصبح الـverifier أكثر خبثًا.

بعض الحالات لا تختار الـnext state فقط. قبل ذلك، تحدث accumulator كبيرًا.

الفكرة العامة:

accumulator += SHA256(state_byte)

حيث يتم تفسير ناتج SHA-256 كـ256-bit integer.

ثم، في مجموعة محددة من الـstates، يتم تطبيق قيد:

accumulator mod M == expected_constant

إذن المسار الصحيح يجب أن يحقق شرطين في الوقت نفسه:

Graph constraint
+
Arithmetic constraint

وهذا يفسر لماذا قد تجد graph يبدو قابلًا للحل، لكن كل المسارات المنطقية تفشل في النهاية.

انتبه للـendianness

من الأخطاء الشائعة جدًا افتراض أن SHA-256 هنا مجرد مجموعة bytes يتم جمعها بطريقة عشوائية.

في هذا النمط، القيمة تتحول إلى BigInt بترتيب محدد. يجب أن تتحقق من الطريقة التي يبني بها الـbinary القيمة، خصوصًا عند:

bytes
   ↓
hex string
   ↓
"0x..."
   ↓
BigInt parser

أحيانًا فرق صغير في التفسير يجعل جميع القيود تبدو مستحيلة، بينما المشكلة أصلًا أنك أدخلت القيمة بترتيب خاطئ.

6. Search the Path

بعد استخراج الـgraph والقيود، لا تبدأ بـbrute force على كل bytes.

ابدأ بالـstates.

أبسط solver يمكن أن يكون DFS مع backtracking:

def dfs(state, visited, path):
    if len(visited) == total_states:
        return path

    for key, nxt in graph[state].items():
        if nxt in visited:
            continue

        if violates_constraint(nxt, path):
            continue

        result = dfs(
            nxt,
            visited | {nxt},
            path + [(nxt, key)]
        )

        if result:
            return result

    return None

في الحالات الأصعب، استخدم heuristics مثل تجربة العقد ذات الخيارات الأقل أولًا.

الفكرة ليست أن تجعل الـCPU يجرب كل possible string. أنت تجعل الـgraph نفسه يستبعد معظم الاحتمالات.

7. Convert the Path Back to Input

بعد إيجاد المسار، لديك sequence من الـkeys أو transitions.

لو كان كل transition يمثل 2 bits:

pairs = {
    0: "00",
    1: "01",
    2: "10",
    3: "11",
}

bits = "".join(pairs[key] for key in path_keys)

ثم تحوّل الـbits إلى bytes:

data = bytes(
    int(bits[i:i+8], 2)
    for i in range(0, len(bits), 8)
)

إذا كان لديك mapping متغير بين chunks، يجب تطبيق mapping الصحيح لكل chunk بدل استخدام dictionary واحد ثابت.

وهذه النقطة مهمة جدًا. أحيانًا تكون قد وجدت الـpath الصحيح، لكن conversion النهائي ينتج input غلط لأنك تجاهلت permutation الخاصة بكل chunk.

8. Validation

لا تعتبر الـsolver ناجحًا لمجرد أنه أعطاك sequence طويلة.

يجب أن تتحقق من:

✓ بدأ من entry state الصحيح
✓ كل transition استخدم key صالح
✓ لا يوجد state تكرر في المكان الذي يمنعه التصميم
✓ كل custom arithmetic constraint تحقق
✓ كل chunk فُسّر باستخدام AA mapping الصحيحة
✓ الـinput الناتج يعيد نفس المسار عند تشغيل verifier
✓ البرنامج يصل إلى Success

أفضل validation هي تشغيل input الناتج داخل البرنامج نفسه بدل الاعتماد على solver فقط.

Vulnerable Code Examples

المشكلة هنا ليست “ثغرة” تقليدية في سطر C واحد. الخلل هو تصميم verifier يمكن عكسه إلى graph قابل للتحليل.

نسخة سيئة: منطق التحقق قابل لإعادة البناء

def verify(user_input):
    state = 0
    visited = set()

    for chunk in split_into_chunks(user_input):
        key = lookup_key(chunk)
        state = transitions[state][key]

        if state in visited:
            return False

        visited.add(state)

    return len(visited) == TOTAL_STATES

هذا خطر عندما تكون كل بيانات transitions والقواعد موجودة داخل العميل بشكل قابل للاستخراج.

نسخة أفضل: لا تضع secret verifier كاملًا على الجهاز

def verify(server, user_input):
    proof = build_minimal_proof(user_input)
    return server.verify(proof)

الفكرة هنا ليست أن الـclient يجب أن يصبح مستحيلًا على reverse engineer. الفكرة أن السر الحقيقي والقيمة الحاسمة للتحقق لا ينبغي أن تعيش بالكامل على جهاز المهاجم.

Defense / How to Fix

1. لا تعتمد على obfuscation كطبقة أمان أساسية. إذا كانت قاعدة التحقق موجودة بالكامل على client، افترض أن أحدًا سيقرأها.

2. احتفظ بالـsecret material خارج الـbinary. استخدم server-side verification أو secure hardware-backed secrets عندما يناسب النظام.

3. لا تجعل success condition تعتمد على graph مكشوف بالكامل. الـobfuscation يزيد تكلفة التحليل، لكنه لا يثبت السرية.

4. قلل المعلومات المفيدة في الـsymbols والـstrings والـstatic data. أسماء functions الواضحة والـdebug artifacts تجعل reconstruction أسهل.

5. استخدم cryptographic verification عندما تحتاج authenticity. إذا كان لديك value يجب إثباتها دون كشف secret، صمّم بروتوكولًا يعتمد على cryptography بدل puzzle قابل لإعادة البناء.

6. اختبر verifier ضد reverse engineering. جرّب بنفسك IDA أو Ghidra أو Binary Ninja، وتأكد مما يمكن للمهاجم استنتاجه من binary فقط.

Testing / Audit Points

عند مراجعة verifier مشابه، ابحث عن هذه المؤشرات:

ما تبحث عنه	لماذا يهم
Array من 0xffffffff أو sentinel values	قد يمثل visited-state table
مئات الدوال المتشابهة	مؤشر على generated state handlers
Repeated AA/map lookups	قد تكون transition dispatch
2-bit أو N-bit chunks	يشير إلى encoded input alphabet
BigInt أو 256-bit arithmetic	قد توجد قيود إضافية على path
SHA-256 داخل verifier	قد تستخدم hash-derived state updates
Success بدون secret string واضح	النجاح قد يعتمد على traversal وليس comparison
Lazy-init guards	تساعد على ربط slots بالدوال

Common Myths

“وجود Obfuscation يعني أن السر لا يمكن استخراجه”

لا.

Obfuscation يرفع تكلفة التحليل، لكنه لا يغيّر حقيقة أن الـbinary يحتوي على منطق التحقق نفسه.

“لو لم أجد الـflag داخل strings فهو غير موجود”

ليس بالضرورة.

قد لا تكون هناك flag string أصلًا. قد يكون المطلوب input يولد sequence صحيحة من transitions.

“Graph كبير يعني brute force مستحيل”

ليس دائمًا.

Graph كبير مع قيود قوية قد يكون أسهل من string brute force لأن القيود تستبعد مسارات ضخمة بسرعة.

“أي transition ظاهر في assembly يمثل key بالترتيب نفسه”

هذا بالذات خطأ شائع عندما يوجد dynamic dictionary أو AA permutation.

Final Thoughts

هذا النوع من الـverifiers يعطيك درسًا ممتازًا في reverse engineering: أحيانًا أفضل طريقة لفهم الـassembly هي أن تتوقف عن رؤيته كتعليمات منفردة وتبدأ في رؤيته كنظام.

الدوال تصبح states.

الـAA lookups تصبح transitions.

الـbit chunks تصبح alphabet.

والـBigInt constraints تصبح guard conditions.

وبمجرد أن تحول كل ذلك إلى graph، يبدو الـmonster أقل رعبًا بكثير.

الـobfuscation قد يجعل الطريق أطول، لكنه لا يستطيع تغيير الرياضيات التي يسير عليها الطريق.