วิธีเอาชนะ PoW ของ kernelCTF ของ Google ด้วย AVX512

 (anemato.de)
2 คะแนน โดย GN⁺ 2025-05-31 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • ทีม Crusaders of Rust ค้นพบบั๊ก use-after-free ในตัวจัดตารางแพ็กเก็ตของ Linux และพัฒนาเอ็กซ์พลอยต์ขึ้นมา
  • ในการแข่งขัน Google kernelCTF ทีมพยายามทำการปรับแต่งประสิทธิภาพระดับสูงเนื่องจาก จำเป็นต้องมีวิธีแก้ PoW (Proof of Work) ที่รวดเร็ว
  • ด้วย แอสเซมบลีที่เขียนเองและการปรับแต่ง SIMD โดยใช้คำสั่ง AVX512IFMA ทีมทำความเร็วได้เกือบ 7 เท่าเมื่อเทียบกับอิมพลีเมนเทชัน Python/GMP และ Rust เดิม
  • มีการจูนอย่างละเอียดตั้งแต่ หลักการทำงาน การคำนวณแบบโมดูลาร์ การจัดการหน่วยความจำ และการใช้รีจิสเตอร์ จนลดเวลาในการประมวลผล PoW ลงเหลือ 0.21 วินาที
  • สุดท้ายทีมส่งผลงานเข้า kernelCTF สำเร็จด้วย เวลาสั้นที่สุดเป็นประวัติการณ์ (3.6 วินาที) หลังจากนั้นนโยบาย PoW ก็ถูกยกเลิกอย่างเป็นทางการ

ภาพรวมและจุดมุ่งหมาย

  • ในเดือนพฤษภาคม 2025 William Liu และ Savy Dicanosa จากทีม Crusaders of Rust พบช่องโหว่ use-after-free ใน Linux และเข้าร่วมการแข่งขัน kernelCTF ของ Google
  • บทความนี้กล่าวถึง กระบวนการปรับแต่ง เพื่อแก้การตรวจสอบ PoW (Proof of Work) ให้เร็วขึ้น และส่งผลงานให้ไวกว่า ทีมความปลอดภัยระดับโลก อื่น ๆ ในการแข่งขันชิงบั๊กบาวน์ตีที่มีเวลาจำกัด

ขั้นตอนการส่ง kernelCTF และฉากหลังของการแข่งขัน

  • kernelCTF เป็นการแข่งขันที่มี เงินรางวัลก้อนใหญ่ ทำให้ ทีมความปลอดภัยมืออาชีพ จากทั่วโลกเข้าร่วมอย่างจริงจัง ทั้งด้านระบบส่งอัตโนมัติและการปรับแต่ง PoW
  • ในแต่ละรอบการส่ง (เปิดทุก 2 สัปดาห์) จะมี เพียงทีมที่เร็วที่สุดทีมเดียวเท่านั้นที่ได้รับรางวัล
  • ขั้นตอนการส่งมีดังนี้:
    • เชื่อมต่อเข้าเซิร์ฟเวอร์ตามเวลาที่กำหนด
    • แก้ PoW ซึ่งใช้เวลาหลายวินาที
    • รอ VM บูต
    • รันโค้ดเอ็กซ์พลอยต์และดึง flag
    • ส่ง Google Form
  • ช่วงหลังมีสถิติส่ง flag สำเร็จใน 4.5 วินาที แต่แค่ PoW กับการบูต VM ก็ใช้เวลา 6.5 วินาทีแล้ว จึงจำเป็นต้องเร่งความเร็วการแก้ PoW

การวิเคราะห์อัลกอริทึม PoW (VDF-Sloth) และการปรับแต่งระยะแรก

  • PoW ของ kernelCTF ใช้ verifiable delay function แบบคำนวณเชิงลำดับชื่อ sloth VDF
    • สำหรับจำนวนเต็มขนาด 1280 บิต x จะทำการคำนวณ ยกกำลังสองแบบโมดูลาร์และกลับบิต ซ้ำ ๆ
  • แม้อิมพลีเมนเทชันเดิม (Python+gmpy และ Rust) จะไม่สามารถได้ประโยชน์จากการขนานหลายคอร์ และ GMP ก็ถูกปรับแต่งมาดีพอสมควรอยู่แล้ว
  • อย่างไรก็ตาม ทีมใช้ข้อเท็จจริงที่ว่าการคำนวณโมดูลาร์อิงกับจำนวนเมอร์แซนน์ 2^1279-1 เพื่อสร้างอิมพลีเมนเทชันโมดูลาร์แบบแมนนวลใน C++ ที่เร็วกว่าเดิม และเพิ่มประสิทธิภาพได้จนเหลือ 1.9 ถึง 1.4 วินาที

การเปลี่ยนผ่านครั้งใหญ่สู่ AVX512IFMA และอิมพลีเมนเทชัน SIMD ความเร็วสูงมาก

  • หลังจากนั้นทีมมุ่งไปที่ ISA แบบ AVX512 และโดยเฉพาะ AVX512IFMA ซึ่งมีคำสั่ง คูณและสะสมแบบ 52 บิต
  • ทีมแบ่งจำนวน 1280 บิตออกเป็น limb ขนาด 52 บิต เพื่อเร่งความเร็วด้วย SIMD ให้สูงสุด (25 limb → ใช้ zmm รีจิสเตอร์ 4 ตัว)
  • มีการปรับจูนระดับล่างซ้ำแล้วซ้ำอีก ทั้งเรื่องสมมาตรของการคำนวณ modular square, accumulation mask, memory broadcast, การจัดสรรรีจิสเตอร์ และการเปรียบเทียบแบบไร้ branch
  • ใช้ ASM (inline assembly) เพื่อป้องกันปัญหา register spill/reload ที่ไม่มีประสิทธิภาพจากคอมไพเลอร์ และด้วยการปรับแต่ง broadcast กับ masking จึงดันความเร็วสุดท้ายลงมาได้ถึง 0.21 วินาที

การทำระบบส่ง PoW อัตโนมัติและสถานการณ์จริงในการแข่งขัน

  • ในการส่งจริง ทีมใช้ เซิร์ฟเวอร์ Google Cloud แบบ Zen 5 (ภูมิภาค Amsterdam) เพื่อลด latency ของเครือข่ายไปยัง Google Form
  • ด้วยโปรแกรมส่งอัตโนมัติ (แพตช์คำขอ POST ของ Google Form และปรับแต่งร่วมกันภายในทีม) ทีมจึงส่ง flag สำเร็จใน 3.6 วินาที ซึ่งเป็นสถิติสั้นที่สุดเท่าที่เคยมีมา
  • ต่อมา ผู้ดูแล kernelCTF ประกาศ ยกเลิกนโยบาย PoW อย่างเป็นทางการ ทำให้หลุดพ้นจากการแข่งขันด้านการปรับแต่ง PoW และสามารถเปิดเผยเทคนิคได้

รายละเอียดการอิมพลีเมนต์ขั้นสูง

การปรับแต่งการคำนวณแบบโมดูลาร์

  • การคำนวณโมดูโล 2^1279-1 (จำนวนเฉพาะ) ถูกแทนที่ด้วยการเลื่อนบิตและการคำนวณเลขคณิตพื้นฐานไม่กี่ครั้ง ทำให้ได้การคำนวณโมดูลาร์ที่เร็วกว่า GMP มาตรฐานมาก

Big-int squaring บน AVX512IFMA

  • ใช้คำสั่งคูณและสะสมแบบ 52 บิตของ AVX512 (vpmadd52luq, vpmadd52huq) เพื่อคูณและสะสม limb แบบขนานทีละ 8 ตัว
  • เนื่องจากโครงสร้างมี 25 limb จึงกระจายไปบน zmm 4 ตัว และออกแบบตรรกะให้ลดการ masking/accumulation ที่ไม่จำเป็นให้เหลือน้อยที่สุด

การจัดวางข้อมูลและการใช้รีจิสเตอร์

  • ใช้การจัดวางข้อมูลแบบเป็นชั้นตามออฟเซ็ต การย้ายข้อมูลระหว่างรีจิสเตอร์ (valignq, broadcast) และเทคนิคอื่น ๆ เพื่อลดคอขวดของ SIMD
  • เพิ่มจำนวน accumulator เป็น 2 เท่าเพื่อให้ได้ throughput สูงสุดโดยไม่ต้องรอหน่วยคูณ
  • ทำ carry propagation เท่าที่จำเป็นขั้นต่ำเท่านั้น

ระบบส่งอัตโนมัติขั้นสุดท้ายและการทำงานร่วมกัน

  • มีการจัดวางสมาชิกทีมเพื่อโจมตีในช่วงเวลากลางดึก พร้อมปรับแต่งตำแหน่งเครือข่ายและการรัน exploit
  • ในการส่งจริง ทุกอย่างถูกทำอัตโนมัติอย่างต่อเนื่อง ตั้งแต่แก้ PoW, รันเอ็กซ์พลอยต์, ใส่ flag ไปจนถึงส่งคำขอ POST ไปยัง Google Form

บทสรุปและความหมาย

  • การปรับแต่ง PoW ของ kernelCTF เป็นงานที่ต้องอาศัยความเข้าใจฮาร์ดแวร์อย่างลึกซึ้งระดับผ่าตั้งแต่บิต หน่วยความจำ รีจิสเตอร์ และ CNN
  • เมื่อไม่มีนโยบาย PoW แล้ว จุดแข่งขันก็จะเหลือเพียง ความเร็วของเครือข่ายและเอ็กซ์พลอยต์ล้วน ๆ
  • กรณีนี้แสดงให้เห็นถึง การบรรจบกันของการแฮ็กในโลกจริงกับการประมวลผลสมรรถนะสูง และองค์ความรู้ด้านการปรับแต่งอัลกอริทึมพร้อมโค้ดโอเพนซอร์สก็น่าจะยังมีประโยชน์ต่อชุมชนนักวิจัยต่อไป

หมายเหตุและภาคผนวก

  • มีการเปิดเผยโค้ดทั้งหมดของอัลกอริทึม PoW และฟังก์ชันแปลงข้อมูล (GMP <-> อาร์เรย์ 52 บิต), การคำนวณโมดูลาร์บน SIMD และโค้ด ASM ที่ใช้จูนประสิทธิภาพ
  • แม้จะเป็นโค้ดแบบ “ลุยจริง” ที่พัฒนาอย่างเข้มข้นภายในเวลาประมาณ 12 ชั่วโมงและนำไปใช้ภาคสนามทันที แต่ก็เปิดซอร์สภายใต้สัญญาอนุญาต GNU AGPL 3.0
  • หากมีคำถามหรืออยากร่วมมือด้าน VDF สามารถติดต่อได้ทาง Discord(@forevermilk)

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2025-05-31
ความคิดเห็นบน Hacker News

  • ทีมที่ชนะทำเวลาได้ 3.6 วินาที และอันดับ 2 ทำได้ 3.73 หรือ 3.74 วินาที จึงทำให้นึกว่าอันดับ 2 ก็น่าจะปรับแต่ง PoW หรืออาจใช้ FPGA ด้วยเช่นกัน เมื่อเทียบกับการส่งงานด้วย FPGA ก่อนหน้านี้ที่ใช้เวลาเกิน 4 วินาที ก็น่าเสียดายที่ผู้เขียนไม่ได้พูดถึงว่าผลงานอันดับ 2 ในสัปดาห์นี้อาจเป็นสถิติระดับประวัติการณ์เหมือนกัน

  • วิธีนี้ให้ความรู้สึกว่าคล้ายมากกับแนวทางที่ใช้ใน implementation ของ RSA ที่ปรับแต่งสำหรับ AVX-512 เพราะ RSA ก็ต้องคำนวณการยกกำลังขนาดใหญ่มากเช่นกัน งานวิจัยนี้(https://dpitt.me/files/sime.pdf)อธิบายเทคนิค windowing และการปรับขนาดหน้าต่างแบบยืดหยุ่นได้ ส่วน implementation ของ RSA บน AVX-512 จะเพิ่มการเก็บผลคูณไว้ในตารางช่วง [0..2^{window-size}) เพื่อเรียกใช้ผลในแต่ละหน้าต่าง ดูตัวอย่างจริงได้ใน rsaz-2k-avx512.pl ของ aws-lc

    • น่าเสียดายที่ถ้าเคยเห็นข้อมูลพวกนี้ล่วงหน้าก็น่าจะใช้เป็นแนวทางพัฒนาได้ บน Zen 5 คาดหวัง throughput การคูณได้ 2 เท่าจากการใช้ zmm register แต่ในโค้ดเดิมมีการแปลง mask register ไปเป็น GPR ซึ่งไม่มีประสิทธิภาพบน Zen 4/5 จึงสงสัยว่าจำเป็นจริงหรือไม่ที่การ propagate carry ต้องทำในรอบเดียวทั้งหมด ในโค้ดจริงใช้สมมติฐานว่าจะเกิด carry แค่ครั้งเดียวแล้วจึงวนซ้ำ ซึ่งช่วยลด latency ได้ในกรณีส่วนใหญ่ แม้ยังคงมีความเป็นไปได้ของ timing attack จาก branch อยู่ก็ตาม

  • สำหรับข้ออ้างที่ว่า AVX512 รองรับบน CPU ฝั่งผู้บริโภคมาหลายเจเนอเรชัน จำได้ว่าก่อน Rocket Lake (รุ่น 11) นั้น AVX512 มีให้ใช้เฉพาะในรุ่น enthusiast, Xeon และโปรเซสเซอร์มือถือบางตัวเท่านั้น หลังรุ่น 12 ที่เริ่มใช้ P/E core มันก็ถูกปิดการใช้งานและหายไปภายในไม่กี่เดือน มีการคาดการณ์ว่าถ้า AMD ประสบความสำเร็จกับ AVX512, Intel ก็จะนำกลับมาอีกครั้ง ส่วนตัวใช้งาน i9-11900 อยู่

    • CPU รุ่น 12 ที่เป็น P-core ไม่ได้รองรับหรือโฆษณา AVX512 เลย และถูกปิดไว้เป็นค่าเริ่มต้น เพราะพื้นที่ถูกใช้ไปกับ E-core ทำให้ทั้ง CPU ไม่มี AVX512 ติดมาจริง ๆ มีเพียงทางอ้อมผ่านตัวเลือกใน BIOS ที่ปิด E-core แล้วเปิด AVX512 บนคอร์ที่เหลือได้ แต่ก็ต้องแลกกับการเสีย E-core ไป
    • ในเอกสารเทคนิค Intel AVX10 ล่าสุด(https://cdrdv2.intel.com/v1/dl/getContent/784343) Intel ระบุให้ 512-bit AVX เป็นมาตรฐานทั้งบน P-core และ E-core เป็นการออกจากแนวทางที่จำกัดไว้แค่ 256-bit และเป็นสัญญาณว่า AVX-512 กำลังจะกลับมาสู่ CPU ผู้บริโภคอย่างจริงจัง ไม่ใช่เฉพาะฝั่งเซิร์ฟเวอร์ ซึ่งตีความได้ว่า Intel กำลังเดินตามการขยาย AVX-512 ของ AMD

  • มีความสงสัยต่อธรรมชาติของการแข่งขัน CTF โดยมองว่าควรใช้วิธีแบ่งเงินรางวัลให้ทุกทีมที่ส่ง flag ได้ภายในช่วงเวลาที่กำหนด แทนการแข่งขันด้านความเร็วในการส่ง

    • แต่รูปแบบแบบนั้นอาจทำให้เกิด metagame ที่ผู้เข้าร่วมไม่เปิดเผยข้อมูล exploit ทันที และเก็บไว้สำหรับรอบถัดไปแทน ส่งผลให้การรายงานอย่างฉับไวลดลง อีกทั้งยังอาจก่อให้เกิดผลข้างเคียงจากการแข่งขันที่ไม่สร้างสรรค์ เช่น การวางกลยุทธ์เรื่องจังหวะเวลาส่ง
    • โครงสร้าง metagame จะเปลี่ยนไป และอาจทำให้บางคนยิ่งหมดแรงจูงใจจนไม่คิดจะส่งผลงานเข้า kernelCTF เลยด้วยซ้ำ

  • ถ้าเข้าใจไม่ผิด นี่คือ proof of work 4 วินาทีและมีโครงสร้างการจ่ายเงินเดือนละครั้ง จึงสงสัยว่าในแต่ละเดือนมี exploit จำนวนมากและมีการแข่งขันดุเดือดขนาดนั้นเลยหรือไม่

    • เซิร์ฟเวอร์เปิดทุก 2 สัปดาห์ และ PoW มีไว้เพื่อเพิ่มความหน่วงเล็กน้อยเพื่อป้องกันการยิงคำขอจำนวนมากเกินไป ส่วน public CTF ก็มักแข่งขันกันหนักจนบางครั้งมีความพยายามแบบคล้าย DDoS ด้วย หลังจากนั้น Google ก็ลบขั้นตอน proof of work ออก
    • มีความเห็นว่าภาพลักษณ์เรื่องความปลอดภัยของเคอร์เนล Linux แท้จริงแล้วเป็นเพียงภาพฝัน
    • CTF ครั้งนี้ไม่ใช่การโจมตีแบบ remote code execution แต่เป็น exploit สำหรับการยกระดับสิทธิ์จากผู้ใช้ธรรมดาไปเป็น root ซึ่งบั๊กยกระดับสิทธิ์นั้นพบได้บ่อยจริง ๆ

  • เป็นความท้าทายที่น่าทึ่ง แต่ก็ให้ความรู้สึกว่าความซับซ้อนและความชวนขำของอุปสรรคเพื่อจะชนะมันสูงมาก เหมือนเครื่องจักรแบบ Rube Goldberg

  • ถ้าอยากรู้เพิ่มเติมเกี่ยวกับส่วน base-52 ที่กล่าวถึงในบทความ แนะนำให้อ่านโพสต์นี้ที่กำลังเป็นประเด็นวันนี้(https://news.ycombinator.com/item?id=44132673)

  • คณิตศาสตร์มันเท่มาก

  • มีการแนะนำ sloth ซึ่งเป็น VDF (Verifiable Delay Function) ที่ใช้ใน proof of work โดยต้องอาศัยการคำนวณยาวต่อเนื่องเพื่อพิสูจน์การผ่านของเวลา แต่ผลลัพธ์สามารถตรวจสอบได้อย่างรวดเร็ว การคำนวณมีลักษณะเป็นลำดับต่อกัน จึงไม่สามารถลด runtime ได้แม้ใช้หลายคอร์ จึงมีคำถามว่าสิ่งนี้อาจกลายเป็นตลาดใหม่ให้ผู้ผลิต CPU ได้หรือไม่ พร้อมเสนอแนวคิดเรื่องคำสั่งเฉพาะสำหรับการวน sloth และผลลัพธ์ของมัน รวมถึงฟังก์ชันป้องกันการโอเวอร์คล็อกระดับฮาร์ดแวร์ อีกไอเดียหนึ่งคือให้ CPU ตรวจสอบ uptime ของตัวเองแล้วลงลายเซ็นพร้อม challenge ซึ่งคล้ายแนวคิด proof of stake ที่ยังคงใช้ CPU ทำงานจริงไปพร้อมกับพิสูจน์การครอบครอง CPU เป็นเวลา n วินาที

  • สงสัยว่าฟังก์ชัน Python ในบล็อกเทียบเท่ากับ implementation ของ Google PoW อย่างไร เพราะตามได้ค่อนข้างยาก

    • ในโค้ดของ Google ค่า exponent = (p + 1) // 4 มีค่าเป็น 2^1277 ดังนั้นการยกตัวเลขขึ้นด้วยเลขชี้กำลังมหึมาขนาดนั้นต้องมีการยกกำลังสอง 1277 ครั้ง และฟังก์ชัน Python ก็ทำสิ่งนี้จริง ๆ ถ้าค่าเริ่มต้นคือ x แต่ละครั้งที่ยกกำลังสองก็จะคูณเลขชี้กำลังเป็น 2 เท่าไปเรื่อย ๆ จนสุดท้ายกลายเป็น 2^1277 และนี่คือหลักการของมัน