crypto

Diffie-Hellman

Diffie-Hellman (DH) คือโพรโทคอลแลกเปลี่ยนกุญแจที่ให้สองฝ่ายตกลง shared secret ผ่านช่องทางสาธารณะได้ ความปลอดภัยอยู่บนปัญหา discrete logarithm บทนี้อธิบายกลไก แล้วไล่จุดอ่อนที่พบใน CTF: พารามิเตอร์อ่อน, small subgroup, และ MITM เมื่อไม่มีการยืนยันตัวตน

IntermediateAdvanced#diffie-hellman#dh#key-exchange#discrete-log#mitm#crypto#ctf

1. DH ทำงานอย่างไร

ทั้งสองฝ่ายตกลงค่าสาธารณะ: จำนวนเฉพาะ p และฐาน g จากนั้นแต่ละฝ่ายสุ่มเลขลับของตัวเอง (a และ b) แล้วแลกค่าสาธารณะ A = gᵃ mod p และ B = gᵇ mod p สุดท้ายทั้งคู่คำนวณ shared secret เดียวกันได้: s = Bᵃ = Aᵇ = g^(ab) mod p

DH key exchange

ผู้ดักฟังเห็น p, g, A, B แต่จะหา s ได้ต้องแก้ discrete logarithm (หา a จาก A = gᵃ mod p) ซึ่งยากมากเมื่อ p ใหญ่และเลือกพารามิเตอร์ดี

2. จุดอ่อนที่พบใน CTF

p เล็ก: ถ้า p เล็ก (เช่น < 64-128 บิต) แก้ discrete log ได้ด้วย baby-step giant-step หรือ Pollard's rho ใน SageMath
p−1 smooth: ถ้า p−1 แยกเป็นตัวประกอบเล็กๆ ได้หมด → Pohlig-Hellman แก้ discrete log ได้เร็ว
g เป็น generator ของ subgroup เล็ก: shared secret มีค่าเป็นไปได้น้อย → brute ได้ (small subgroup attack)
ไม่ยืนยันตัวตน: DH ดิบไม่มี authentication → ถูก MITM ได้ (ผู้โจมตีคั่นกลาง แลก key กับทั้งสองฝ่ายแยกกัน)
ค่า A หรือ B = 0, 1, p−1: ทำให้ shared secret คาดเดาได้ ควร validate

แก้ discrete log เมื่อ p เล็ก (SageMath)

# SageMath
p = ...
g = ...
A = ...   # = g^a mod p
F = GF(p)
a = discrete_log(F(A), F(g))   # กู้ secret a
print("a =", a)
# จากนั้น shared secret s = B^a mod p
s = pow(B, a, p)

discrete_log ของ Sage ใช้ Pohlig-Hellman + BSGS อัตโนมัติ ได้ผลเร็วถ้า p−1 smooth

3. MITM เมื่อไม่มี authentication

ถ้าโพรโทคอลไม่ยืนยันตัวตน ผู้โจมตีที่คั่นกลางส่ง public value ของตัวเองให้ทั้งสองฝ่าย ทำให้เกิด shared secret 2 ชุด (Alice↔attacker และ attacker↔Bob) แล้วถอด-เข้ารหัสซ้ำระหว่างส่งต่อ — อ่านและแก้ไขข้อความได้ทั้งหมด นี่คือเหตุผลที่ DH จริงต้องมาคู่กับ signature/certificate (เช่นใน TLS)

โจทย์ CTF แนวนี้มักให้คุณเป็น 'คนกลาง' ที่ควบคุมค่าที่ส่ง — ลองส่ง A = p หรือ A = 1 ดู เพราะจะบังคับ shared secret เป็น 0 หรือ 1 ที่รู้ค่าแน่นอน

4. Quick Reference

s = g^(ab) mod p; เห็น p,g,A,B แต่ต้องแก้ discrete log เพื่อหา secret
p เล็ก / p−1 smooth → discrete_log ใน SageMath (Pohlig-Hellman/BSGS)
g สร้าง subgroup เล็ก → brute shared secret
ไม่มี auth → MITM
ลองส่งค่าพิเศษ A∈{0,1,p−1} เพื่อบังคับ secret
เครื่องมือ: SageMath (discrete_log, factor)

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

สมมติเจอโจทย์ที่ให้ p, g, A, B (หรือ transcript การแลกกุญแจใน pcap/log) มีแค่เครื่อง Kali เปล่าๆ ทำตามนี้ทีละขั้น

1อ่านค่าที่ให้มาก่อน: p, g, A(=gᵃ mod p), B(=gᵇ mod p) จากไฟล์โจทย์หรือ pcap (`wireshark` / `tshark` ถ้าเป็น traffic capture)
2เช็คขนาด p (bit length) ด้วย python: `p.bit_length()` — ถ้าเล็ก (≤ ~128 bit) มีโอกาสสูงที่จะแก้ discrete log ตรงๆ ได้
3เปิด https://sagecell.sagemath.org (ไม่ต้องติดตั้งอะไร) รัน `discrete_log(GF(p)(A), GF(p)(g))` — ถ้า p เล็ก/p−1 smooth จะได้ค่า a กลับมาเร็ว
4sage ช้าเกิน/ไม่ตอบ → เช็คว่า p−1 แยกเป็นตัวประกอบเล็กๆ ได้หมดไหม: `python3 -c "from sympy import factorint; print(factorint(p-1))"` — ถ้า smooth (ตัวประกอบทุกตัวเล็ก) ยืนยันว่า Pohlig-Hellman ใช้ได้จริง
5p ใหญ่มากและ p−1 ไม่ smooth → เปลี่ยนไปเช็ค g แทน: คำนวณ order ของ g ด้วย python (ลอง pow(g, k, p) ไล่ k จนได้ 1) — ถ้า order เล็ก แปลว่า g สร้าง subgroup เล็ก → brute shared secret ได้ตรงๆ
6เช็คว่า A หรือ B เป็นค่าพิเศษไหม (0, 1, หรือ p−1) — ถ้าใช่ shared secret จะคาดเดาได้ทันทีโดยไม่ต้องคำนวณอะไรเลย
7โจทย์ให้เราเป็น 'คนกลาง' ไหม (เช่น proxy ที่ควบคุมค่าที่ส่งได้)? ถ้าโพรโทคอลไม่มีการยืนยันตัวตน (ไม่มี signature/certificate) → ลองส่ง A=1 หรือ A=p เพื่อบังคับ shared secret ให้เป็นค่าที่รู้แน่นอน (MITM)
8ยังไม่ได้ → เช็คว่า p,g เป็นกลุ่มมาตรฐานที่รู้จัก (เช่น RFC 3526 MODP groups) ไหม หรือ p ถูกใช้ซ้ำข้าม session — ค้นหาชื่อ/ค่า p ใน Google เผื่อมี known weakness
9ได้ shared secret s แล้ว → ดูว่าโจทย์ derive AES key จาก s อย่างไร (มักผ่าน SHA256(s) หรือตัด byte บางส่วน) แล้วถอด flag ที่เข้ารหัสต่อด้วย pycryptodome หรือ CyberChef

เจอโจทย์ DH มีแค่ Kali — ไล่ตามนี้

อ่านค่า p, g, A, B ที่ให้มา

ไฟล์โจทย์ / pcap (wireshark, tshark)

p bit length เล็กไหม (≤ ~128 bit)?

✅ เล็ก→→ ลอง discrete_log บน SageMath ตรงๆ

❌ ใหญ่→→ เช็ค p−1 smooth ไหม

p−1 แยกเป็นตัวประกอบเล็กได้หมดไหม (sympy factorint)?

✅ smooth→→ Pohlig-Hellman ผ่าน SageMath

❌ ไม่ smooth→→ เช็ค g/subgroup แทน

g สร้าง subgroup เล็กไหม (order ของ g น้อย)?

✅ order เล็ก→→ brute shared secret ตรงๆ

❌ ไม่รู้/ใหญ่→→ เช็คค่าพิเศษ A/B

A หรือ B เป็น 0, 1, p−1 ไหม?

✅ ใช่→→ secret คาดเดาได้ทันที

❌ ไม่ใช่→→ เช็คว่ามี authentication ไหม

โพรโทคอลมี authentication (signature/certificate) ไหม?

❌ ไม่มี + เราเป็นคนกลางได้→→ MITM: ส่ง A=1 หรือ A=p

✅ มี→→ เหลือแค่ discrete log ตรงๆ

ยังไม่ได้ → เช็คว่า p,g เป็นกลุ่มมาตรฐานที่มี known weakness ไหม

✅ เจอ known weak group→→ ใช้ known attack

❌ ไม่เจอ→→ ได้ secret แล้วไปถอด flag ต่อด้วย AES

derive key จาก shared secret แล้วถอด flag (มักเป็น AES)

ขั้นตอน/งาน	เครื่องมือใน Kali	ติดตั้งเพิ่ม (ถ้าไม่มี)	เครื่องมือออนไลน์
อ่านค่า p,g,A,B จากไฟล์/pcap	cat, wireshark, tshark	-	-
แก้ discrete log เมื่อ p เล็ก/smooth	sage (ถ้าติดตั้งไว้)	conda install sage	sagecell.sagemath.org
แยกตัวประกอบ p−1 เช็ค smooth	python3 (sympy)	pip install sympy	alpertron.com.ar/ECM.HTM
เช็ค order ของ g / subgroup เล็ก	python3	-	-
เช็คว่า p/n อยู่ใน factordb แล้วหรือยัง	-	-	factordb.com
ถอด flag ต่อหลังได้ shared secret (มักเป็น AES)	python3 (pycryptodome)	-	CyberChef (AES Decrypt)

🚑 ถ้าตันสนิท ลองท่าถัดไป: RSA — ถ้าโจทย์จริงๆ ใช้ modulus แบบ RSA ปนมา (มี e,d ด้วยไม่ใช่แค่ p,g) · AES — เกือบทุกโจทย์ DH จบด้วยการเอา shared secret ไป derive key แล้วเข้ารหัส flag ต่อด้วย AES ต้องถอดชั้นนี้ต่อเสมอ · Hash Cracking — ถ้า key ที่ derive มาจาก hash ของ secret ที่สั้น/เดาได้ ลอง brute ค่า secret ตรงๆ แทนแก้ discrete log · Padding Oracle — ถ้า AES ที่ตามมาใช้โหมด CBC และ server เผย error ต่างกัน

หัวข้อที่เชื่อมโยง

โน้ตของฉัน

ยังไม่มีโน้ตสำหรับหัวข้อนี้