XOR Cipher

1. XOR คืออะไร และทำไมถึงสำคัญ

XOR (exclusive OR) คือการดำเนินการระดับบิตที่ให้ผลลัพธ์เป็น 1 เมื่อบิตสองตัวต่างกัน และเป็น 0 เมื่อเหมือนกัน เขียนแทนด้วยสัญลักษณ์ ⊕ มันเป็นหัวใจของ stream cipher, one-time pad และเป็นองค์ประกอบภายใน block cipher อย่าง AES ด้วย

สิ่งที่ทำให้ XOR มีค่าในเชิงรหัสคือ 3 คุณสมบัติ ต่อไปนี้ ซึ่งเป็นรากฐานของทุกเทคนิคถอดรหัสในบทนี้:

• Self-inverse: A ⊕ B ⊕ B = A — XOR ด้วยค่าเดิมซ้ำจะได้ค่ากลับคืน นี่คือเหตุผลที่ encrypt และ decrypt ใช้การดำเนินการเดียวกัน
• Identity: A ⊕ 0 = A — XOR กับศูนย์ไม่เปลี่ยนค่า
• Zeroing: A ⊕ A = 0 — XOR กับตัวเองได้ศูนย์ คุณสมบัตินี้ทำให้กู้ key ได้เมื่อรู้ plaintext บางส่วน

2. สังเกตอย่างไรว่าเป็น XOR

• ciphertext เป็น hex หรือ base64 ที่ถอดออกมาแล้วเป็น byte กระจายทั่ว ไม่ใช่ ASCII อ่านได้
• ความยาว ciphertext เท่ากับ plaintext เป๊ะ (stream cipher ไม่ขยายความยาว)
• โจทย์ใบ้คำว่า key, repeating, stream, หรือให้ key มาบางส่วน
• เมื่อ XOR ciphertext กับตัวมันเองเลื่อนตำแหน่ง แล้วเห็น pattern ซ้ำ — สัญญาณของ repeating-key
• byte ที่ปรากฏบ่อยผิดปกติ อาจเป็น key XOR กับ space (0x20) เพราะ space พบบ่อยสุดในข้อความอังกฤษ

3. Single-byte XOR — brute force

กรณีง่ายที่สุด: ทั้งข้อความถูก XOR ด้วย byte เดียว (key 1 ตัว) มี key เป็นไปได้แค่ 256 ค่า (0x00–0xFF) จึง brute force ได้ทันที เคล็ดลับคือต้องให้คะแนนผลลัพธ์แต่ละ key โดยอัตโนมัติ แทนที่จะไล่ดูตาเปล่า 256 แบบ วิธีให้คะแนนที่ดีคือนับความถี่ตัวอักษรเทียบกับภาษาอังกฤษ (ETAOIN SHRDLU) หรือดูสัดส่วน printable ASCII

import binascii

ct = binascii.unhexlify("1b37373331...")  # ใส่ ciphertext hex

# ความถี่ตัวอักษรอังกฤษโดยประมาณ
FREQ = {' ':13,'e':12,'t':9,'a':8,'o':7,'i':7,'n':7,'s':6,'h':6,'r':6}

def score(b: bytes) -> float:
    return sum(FREQ.get(chr(c).lower(), 0) for c in b)

best = (None, -1, b"")
for k in range(256):
    out = bytes(c ^ k for c in ct)
    s = score(out)
    if s > best[1]:
        best = (k, s, out)

print(f"key=0x{best[0]:02x}  ->  {best[2]}")

4. Known-plaintext — กู้ key ตรงๆ

ถ้ารู้ plaintext ส่วนใดส่วนหนึ่ง (เรียกว่า crib) เช่นรู้ว่าข้อความขึ้นต้นด้วย flag{ หรือไฟล์เป็น PNG ที่ขึ้นต้นด้วย magic bytes คงที่ — สามารถกู้ key ได้ทันทีจากสูตร K = P ⊕ C เพราะ XOR ส่วนที่รู้ของ plaintext กับ ciphertext ตำแหน่งเดียวกัน จะได้ key ออกมาตรงๆ

ct = bytes.fromhex("....")
crib = b"flag{"           # plaintext ที่รู้ (อยู่ต้นข้อความ)

key = bytes(c ^ p for c, p in zip(ct, crib))
print("recovered key bytes:", key)

# ถ้า key สั้นและซ้ำ (repeating-key) key ที่ได้คือ pattern ที่วนซ้ำ
# ลองใช้ key นี้ถอดทั้งข้อความ
dec = bytes(ct[i] ^ key[i % len(key)] for i in range(len(ct)))
print(dec)

เทคนิคนี้ทรงพลังมากกับไฟล์ที่มี header คงที่: PNG (\x89PNG), PDF (%PDF), ZIP (PK\x03\x04), ELF (\x7fELF) — รู้ magic bytes ก็ได้ key ส่วนต้นมาฟรี

5. Repeating-key XOR — หาความยาว key

เมื่อ key สั้นกว่าข้อความและถูกวนซ้ำ (repeating-key / Vigenère แบบ byte) การโจมตีมี 2 ขั้น: (1) หาความยาว key ก่อน แล้ว (2) แตกปัญหาเป็น single-byte XOR หลายชุด ขั้นแรกใช้ Hamming distance (จำนวนบิตที่ต่างกันระหว่างสอง block) — ความยาว key ที่ถูกต้องจะให้ค่า normalized Hamming distance ต่ำที่สุด เพราะ block ที่ XOR ด้วย key เดียวกันจะมีลักษณะทางสถิติคล้ายกัน

1. 1เดาความยาว key (keysize) ตั้งแต่ 2 ถึง ~40
2. 2สำหรับแต่ละ keysize: แบ่ง ciphertext เป็น block ขนาด keysize แล้วคำนวณ Hamming distance เฉลี่ยระหว่าง block หารด้วย keysize (normalize)
3. 3keysize ที่ให้ค่าต่ำสุดคือผู้สมัครที่ดีที่สุด
4. 4transpose: จับ byte ตำแหน่งเดียวกันของทุก block มารวมกลุ่ม (ได้ keysize กลุ่ม)
5. 5แต่ละกลุ่มคือ single-byte XOR — brute force หา byte ของ key ทีละตำแหน่ง
6. 6ประกอบ key ทุก byte แล้วถอดทั้งข้อความ

def hamming(a: bytes, b: bytes) -> int:
    return sum(bin(x ^ y).count("1") for x, y in zip(a, b))

def best_keysizes(ct: bytes, lo=2, hi=40, top=3):
    scores = []
    for ks in range(lo, hi + 1):
        blocks = [ct[i*ks:(i+1)*ks] for i in range(4)]  # ใช้ 4 block แรก
        dist = 0; pairs = 0
        for i in range(len(blocks)):
            for j in range(i + 1, len(blocks)):
                if len(blocks[i]) == ks and len(blocks[j]) == ks:
                    dist += hamming(blocks[i], blocks[j]); pairs += 1
        if pairs:
            scores.append((dist / pairs / ks, ks))
    scores.sort()
    return [ks for _, ks in scores[:top]]

print(best_keysizes(ct))  # คืน keysize ที่น่าจะถูก 3 อันดับแรก

6. Many-time pad (key ซ้ำ — ความผิดพลาดคลาสสิก)

ถ้า key ถูกใช้ซ้ำกับหลายข้อความ (เรียก many-time pad / two-time pad) จะรั่วข้อมูลร้ายแรง เพราะ C1 ⊕ C2 = P1 ⊕ P2 — key หายไป เหลือแต่ XOR ของ plaintext สองอัน จากนั้นใช้เทคนิค crib-dragging (ลากคำที่น่าจะมี เช่น ' the ') ไปตามตำแหน่งต่างๆ เพื่อค่อยๆ กู้ทั้งสองข้อความ

7. Decision Tree — เจอ XOR ทำยังไงต่อ

8. เครื่องมือ & การติดตั้ง

pip install xortool
# ใช้งาน:
xortool -c 20 cipher.bin       # เดา key + ถอด
xortool -l 8 -c 20 cipher.bin   # ระบุ keysize = 8

CyberChef (เปิดในเบราว์เซอร์) มี operation XOR และ XOR Brute Force ที่ลากวางได้ เหมาะกับงานเร็วๆ และทดลอง key หลายแบบ ส่วนงานจริงจังแนะนำเขียน Python เองเพื่อคุม scoring

9. ตัวอย่างโจทย์ CTF จริง

โจทย์ A (single-byte): ได้ hex string มา 1 บรรทัด โจทย์บอกว่า 'XOR'd against a single character' — brute 256 ค่าแล้ว score ด้วย frequency ผลที่อ่านออกคือ flag

โจทย์ B (repeating-key): ไฟล์ base64 ยาว ถอด base64 ได้ binary — รู้ว่าเป็น repeating-key XOR ใช้ Hamming distance พบ keysize=29 transpose แล้ว single-byte แต่ละกลุ่ม ได้ key เป็นประโยคภาษาอังกฤษ (โจทย์คลาสสิกแนว Cryptopals Set 1 Challenge 6)

โจทย์ C (crib): ได้ไฟล์ XOR ที่รู้ว่าเดิมเป็น PNG — XOR magic bytes 89 50 4E 47 กับ 4 byte แรกของ ciphertext ได้ key ส่วนต้น แล้วขยายผลกู้ทั้งไฟล์

10. Quick Reference

• P ⊕ K = C · C ⊕ K = P · P ⊕ C = K — รู้สอง หาที่สาม
• single-byte: brute 256 + scoring (frequency หรือ printable)
• crib/magic bytes: K = P ⊕ C กู้ key ทันที
• repeating-key: Hamming distance → keysize → transpose → single-byte
• key ซ้ำหลายข้อความ: C1 ⊕ C2 = P1 ⊕ P2 → crib dragging
• เครื่องมือเร็ว: xortool -c 32 และ CyberChef

🧭 จับมือทำทีละขั้น (มีแค่ Kali) + ถ้าติดไปไหนต่อ

สมมติได้ ciphertext ที่เป็น hex หรือ base64 มา decode ชั้นนอกแล้วเป็น byte สุ่มไม่ใช่ตัวอักษรที่อ่านออก มีแค่เครื่อง Kali เปล่าๆ ทำตามนี้ทีละขั้น

1. 1decode ชั้นนอกก่อนให้ได้ raw bytes: hex ใช้ `bytes.fromhex(s)` (python) หรือ `xxd -r -p`; base64 ใช้ `base64 -d`
2. 2เช็คความยาว: ถ้าความยาวตรงกับ plaintext ที่คาดไว้พอดี (ไม่ขยาย/บีบ, ไม่ใช่ทวีคูณของ 16 เป๊ะเสมอ) → สงสัย XOR/stream cipher
3. 3ลอง single-byte brute force ก่อนเสมอ (เร็วสุด แค่ 256 ค่า): รัน python loop + scoring ตามโค้ดด้านบน หรือเปิด https://gchq.github.io/CyberChef ลาก 'XOR Brute Force' มาวาง
4. 4รู้ format ของ plaintext ไหม (เช่นไฟล์ PNG/ZIP/PDF หรือ flag ขึ้นต้น 'flag{')? ถ้ารู้ → known-plaintext attack: `K = C ⊕ magic_bytes` กู้ key ตรงๆ (ดูตาราง magic bytes ด้านบน)
5. 5ไม่มี crib ให้ใช้ → สงสัยว่าเป็น repeating-key: หา keysize ด้วย Hamming distance (python loop 2-40 ตามโค้ดด้านบน) หรือรัน `pip install xortool` แล้ว `xortool -c 20 cipher.bin`
6. 6ได้ keysize แล้ว → transpose ciphertext เป็นกลุ่มตาม keysize แล้ว brute single-byte แต่ละกลุ่มแยกกัน ประกอบ key ทีละ byte
7. 7มีหลาย ciphertext ที่สงสัยว่าใช้ key เดียวกันไหม (many-time pad)? ถ้ามี → XOR สองก้อนเข้าด้วยกัน (`C1 ⊕ C2 = P1 ⊕ P2`) แล้ว crib-drag คำที่คาดว่าน่าจะมี เช่น `' the '`
8. 8ผลลัพธ์ดูไม่ใช่ข้อความเลย (เป็น byte สุ่มต่อเนื่อง) → ทบทวนว่า decode ชั้นนอกถูกจริงไหม (hex/base64 สลับกันไหม, มี URL-safe base64 ไหม)
9. 9ความยาว ciphertext เป็นทวีคูณของ 16 เสมอ (ไม่ว่า input จะยาวเท่าไร) → นี่อาจไม่ใช่ XOR แต่เป็น AES block cipher → ไปหัวข้อ AES แทน
10. 10ได้ผลอ่านออกแล้ว → เช็ค flag format ให้ตรงกับที่โจทย์กำหนด แล้วส่งคำตอบ