ค่าหัวตามหา seed ของเส้นโค้งวงรี NIST

 (words.filippo.io)
1 คะแนน โดย GN⁺ 2023-10-06 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • มีการตั้ง ค่าหัว $12,288 เพื่อค้นหาต้นฉบับของ seed สำหรับ เส้นโค้งวงรี NIST 5 เส้น ที่ใช้อย่างแพร่หลายในวิทยาการเข้ารหัสสมัยใหม่ ซึ่งมาจากค่าที่ NSA จัดหาไว้ตั้งแต่ทศวรรษ 1990
  • เป้าหมายคือ P-192, P-224, P-256, P-384, P-521 ใน FIPS 186-2 และถ้าผู้ชนะเลือกให้จ่ายเป็นการบริจาคแก่หน่วยงานการกุศลสหรัฐแบบ 501(c)(3) จำนวนเงินจะเพิ่มเป็น $36,864 หรือ 3 เท่า
  • เชื่อว่า seed ถูกสร้างโดย Jerry Solinas ในปี 1997 และอาจมาจากการแฮชประโยคภาษาอังกฤษด้วย SHA-1 แต่ข้อความจริงได้สูญหายไปหลังการเปลี่ยนหรืออัปเกรดอุปกรณ์
  • รูปแบบของข้อความยังไม่แน่ชัด ทั้งจุด full stop, การขึ้นบรรทัดใหม่, ตำแหน่งและรูปแบบของตัวนับ รวมถึงการมีชื่อเส้นโค้งอยู่ในข้อความหรือไม่ จึงเสนอให้เริ่มโจมตีจาก รายการแฮชราว 12k รายการ ก่อน
  • หากส่ง pre-seed ได้อย่างน้อย 1 รายการเป็นคนแรก จะได้รับ $6,144 และหากส่งครบทั้ง 5 รายการเป็นคนแรก จะได้อีก $6,144 โดยลำดับการส่งจะตัดสินจากส่วนหัว Received ของเมลเซิร์ฟเวอร์

เป้าหมายของค่าหัวและจำนวนเงินรางวัล

  • เป้าหมายของค่าหัวสาธารณะคือการค้นหา ค่าอินพุตของแฮช (pre-seed) ที่ใช้สร้าง seed ของเส้นโค้งวงรี NIST ทั้ง 5 เส้น
  • ค่าหัวรวมอยู่ที่ $12,288 หรือ 12 Ki$
    • หากผู้ชนะเลือกบริจาคแทนรับเงินสดให้กับหน่วยงานการกุศลสหรัฐแบบ 501(c)(3) ยอดรวมจะเพิ่มเป็น $36,864
  • แฮชเป้าหมายมี 5 ค่า ดังนี้
    • 3045AE6FC8422F64ED579528D38120EAE12196D5
    • BD71344799D5C7FCDC45B59FA3B9AB8F6A948BC5
    • C49D360886E704936A6678E1139D26B7819F7E90
    • A335926AA319A27A1D00896A6773A4827ACDAC73
    • D09E8800291CB85396CC6717393284AAA0DA64BA

เหตุใด seed ของเส้นโค้ง NIST จึงถูกตั้งข้อสงสัย

  • เส้นโค้ง NIST P-192, P-224, P-256, P-384, P-521 ถูกเผยแพร่ใน FIPS 186-2 เมื่อปี 2000 และตามวิธีของ ANSI X9.62 จะนำ seed แบบสุ่มมาแฮชด้วย SHA-1 แล้วใช้ผลลัพธ์บางส่วนไปสร้างพารามิเตอร์บางตัว
  • ระบบเข้ารหัสจำนวนมากใช้เส้นโค้ง NIST โดยเฉพาะ P-256 และ P-384 ที่ใช้กันอย่างแพร่หลาย
    • เส้นโค้งทั้งสองอยู่ใน Commercial National Security Algorithm Suite
    • ยังถูกใช้ในใบรับรอง ECDSA X.509 ที่ปกป้องเว็บจำนวนมากด้วย
  • บทความ NIST curve seed origins ของ Steve Weis สรุปสิ่งที่ทราบเกี่ยวกับ seed แบบสุ่มที่อยู่ในสเปก FIPS 186
    • ดูเหมือนว่า seed จะถูกจัดหาโดย NSA
    • เชื่อว่าถูกสร้างโดย Jerry Solinas ในปี 1997
    • มีความเป็นไปได้ว่าได้มาจากการแฮชประโยคภาษาอังกฤษด้วย SHA-1
  • Jerry Solinas เคยยกตัวอย่าง seed ในลักษณะ SHA1("Jerry deserves a raise.") แต่ข้อความจริงสูญหายไปแล้ว และข้อความใกล้เคียงก็ไม่ตรงกับแฮช

การค้นพบ pre-seed อาจช่วยลดความไม่ไว้วางใจ

  • การประเมินล่าสุดทำให้เส้นโค้ง NIST ดูน่าเชื่อถือมากขึ้นในบางด้าน
    • complete addition formulas ช่วยบรรเทา footgun สำคัญบางอย่าง
    • มีความรู้มากขึ้นเกี่ยวกับวิธีออกแบบอินเทอร์เฟซที่ปลอดภัยกว่า
    • คุณค่าของเส้นโค้งลำดับเฉพาะที่ต้านทานการโจมตีแบบ cofactor ก็ชัดเจนขึ้น
  • อย่างไรก็ตาม ในหมู่คนที่ไม่ได้ทำงานภาคปฏิบัติบางส่วน ยังมีความกังวลว่า NSA อาจเลือก seed เพื่อให้ได้เส้นโค้งที่อ่อนแอโดยเจตนา
  • งานเขียน A riddle wrapped in an enigma ของ Koblitz และ Menezes มองว่า แม้ NSA จะควบคุม seed ได้ทั้งหมด การโจมตีลักษณะนั้นก็ยังไม่น่าเชื่อถือ
    • เพราะจะต้องมีคลาสของเส้นโค้งอ่อนแอขนาดใหญ่มากพอที่ทั้งวงวิชาการและอุตสาหกรรมจะไม่พบเจอตลอด 25 ปี
  • แม้ความกังวลนี้อาจไม่ได้มีมูลมากพอ แต่การค้นพบ pre-seed ก็อาจช่วยลด FUD รอบเส้นโค้ง NIST ได้
  • การค้นหา preimage ภาษาอังกฤษไม่ได้รับประกัน rigidity อย่างสมบูรณ์ แต่จะช่วยเติมชิ้นส่วนที่ขาดหายไปของประวัติศาสตร์คริปโต

เบาะแสที่ทราบเกี่ยวกับค่าอินพุตของแฮช

  • มีความเป็นไปได้สูงว่าอินพุตจะเป็น วลีภาษาอังกฤษ ที่อ้างถึง Jerry Solinas และอาจมีชื่อคนอื่นกับตัวนับรวมอยู่ด้วย
  • เหตุผลที่คาดว่าจำเป็นต้องมีตัวนับ คือสำหรับขนาดบิตของเส้นโค้งนั้น โดยเฉลี่ยแล้วจากแฮช 192 ถึง 521 ค่า จะมีเพียงประมาณ 1 ค่าที่เหมาะสมสำหรับการสร้างเส้นโค้ง
    • สำหรับเส้นโค้งที่ใหญ่ที่สุด ความน่าจะเป็นที่ตัวนับจะ น้อยกว่า 2400 คือ 99%
    • สำหรับ P-256 ก็มี ความน่าจะเป็นที่ตัวนับจะน้อยกว่า 1175
  • seed ของ P-192 และ P-256 เคยปรากฏเป็นตัวอย่างในมาตรฐาน ANSI X9.62 ก่อนหน้า ขณะที่ตัวอื่นเพิ่งปรากฏใหม่ใน FIPS 186-2 จึงอาจมีโครงสร้างประโยคต่างกัน
  • แม้ค่าหัวจะครอบคลุมเฉพาะเส้นโค้ง NIST แบบลำดับเฉพาะทั้ง 5 เส้น แต่หากต้นทุนการทดสอบต่ำ ก็อาจลองตัวอย่างอื่นใน ANSI X9.62 และ seed ของ binary curve ใน FIPS 186-2 ไปพร้อมกันได้
    • ANSI prime192v2, prime192v3, prime239v1, prime239v2, prime239v3 ไม่อยู่ในขอบเขตค่าหัว
    • NIST B-163, B-233, B-283, B-409, B-571 ก็ไม่อยู่ในขอบเขตค่าหัว

รูปแบบสตริงที่เป็นไปได้และรายการโจมตี

  • รูปแบบของสตริงยังคงเป็น ปริศนา
    • ประโยคอาจลงท้ายด้วยจุดหรือไม่ก็ได้
    • อาจมีหรือไม่มีการขึ้นบรรทัดใหม่
    • ตัวนับอาจเป็นเลขฐานสิบ, อาจมี leading zero หรืออาจเป็นไบนารี 16 บิตหรือ 32 บิต
    • ตัวนับอาจอยู่หลังจุด full stop หรือเชื่อมด้วยตัวคั่นแบบอื่น
    • อาจใช้ประโยคเดียวกันแล้วเปลี่ยนตัวนับเพื่อสร้าง seed ทั้งหมด หรืออาจใช้คนละประโยคสำหรับแต่ละ seed
    • ชื่อหรือขนาดของเส้นโค้งอาจรวมอยู่ในข้อความด้วย
  • เนื่องจากความทรงจำของมนุษย์ผิดพลาดได้ง่าย จึงยังเป็นไปได้ว่ารายละเอียดบางส่วนจากคำบอกเล่าทางอ้อมจะไม่ถูกต้อง
  • นอกจากตัวนับแล้ว ยังอาจใช้การแฮชซ้ำแบบ SHA-1(s) หรือ SHA-1(SHA-1(s))
  • อีกความเป็นไปได้คือเริ่มจาก SHA-1(s) แล้วเพิ่มค่าแฮชไปเรื่อย ๆ ตามแบบ ANSI X9.62 Section A.3.3.1
  • มีการให้รายการเป้าหมายโจมตีเป็น nist-and-ansi-prime-order-seeds-increments-99-percent.txt ซึ่งมีแฮชประมาณ 12k ค่า
    • รายการนี้ครอบคลุมพื้นที่ความน่าจะเป็น 99% สำหรับ seed ของ prime order curve แต่ละตัวใน FIPS 186-2 และ ANSI X9.62
    • หากต้นทุนในการตรวจสอบแฮชจำนวนมากต่ำ แนะนำให้ใช้รายการนี้เป็นเป้าหมายโจมตี
    • หากทำได้ การเปรียบเทียบเพียง 16 ไบต์ แรกของแฮชก็ให้ผลเหมือนกัน
  • SHA-1 นั้น brute-force ได้เร็วมาก จึงเหมาะกับผู้ที่มีประสบการณ์ด้านการแคร็กรหัสผ่านและการ brute-force brainwallet

วิธีส่งและเงื่อนไขการจ่ายเงิน

  • ผู้ที่ส่ง pre-seed ของเส้นโค้ง NIST แบบลำดับเฉพาะทั้ง 5 เส้นไปยัง seeds@filippo.io ทางอีเมลเป็นคนแรก จะได้รับค่าหัว
  • โครงสร้างการจ่ายเงินมี 2 ขั้น
    • หากส่ง pre-seed อย่างน้อย 1 รายการ ได้เป็นคนแรก จะได้รับครึ่งหนึ่งคือ $6,144
    • หากส่ง ครบทั้ง 5 pre-seed ได้เป็นคนแรก จะได้รับอีก $6,144
    • คนเดียวกันสามารถรับทั้งสองส่วนได้ จึงไม่จำเป็นต้องรอจนกว่าจะหาครบทั้ง 5 รายการ
  • สามารถเลือกรับเป็นเงินสดหรือให้บริจาคแก่หน่วยงานการกุศลสหรัฐแบบ 501(c)(3)
    • หากเลือกบริจาค จำนวนเงินจะเพิ่มเป็น 3 เท่า
    • อาจปฏิเสธการเลือกองค์กรการกุศลที่ขัดกับค่านิยมอย่างรุนแรง
    • หากเป็นบุคคลสัญชาติสหรัฐหรืออิตาลี และปลายทางไม่สามารถรับโอนเงินได้ตามกฎหมาย จะต้องเลือกตัวเลือกบริจาค
    • ภาษีของเงินรางวัลแบบเงินสดเป็นความรับผิดชอบของผู้รับ
  • หัวข้ออีเมลที่ส่งต้องมีคำว่า ANTISPAM เพื่อให้ผ่านกฎ allowlisting
  • ลำดับการส่งจะยึดตาม Received header ของเมลโฮสต์เป็นเกณฑ์สุดท้าย
  • ค่าหัวจะหมดอายุหาก seed กลายเป็นข้อมูลสาธารณะ และหากยังไม่เป็นเช่นนั้น จะยังมีผลจนกว่าจะมีประกาศอื่นในหน้านี้
    • หากมีการยกเลิกหรือลดค่าหัว จะมีการประกาศล่วงหน้า 6 เดือน
  • ไม่มีข้อจำกัดเรื่องวิธีการค้นหา seed
    • จะใช้ brute-force, การเดาอย่างชาญฉลาด, การสืบค้น, การกู้คืนแบ็กอัป NIST เก่า หรือวิธีใดก็ได้
    • และมีเงื่อนไขว่าจะไม่ถามถึงวิธีการ หากคุณไม่ต้องการบอก

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

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

 
GN⁺ 2023-10-06
ความคิดเห็นบน Hacker News

  • เบื้องหลังเรื่องนี้ค่อนข้างตลก คือช่วงหลังมีเรื่องเล่ากันว่า seed “แบบสุ่ม” ของ NIST P-curve ที่ Jerry Solinas จาก NSA สร้างขึ้นในทศวรรษ 1990 แท้จริงแล้วเป็นค่าที่ได้จากการ SHA1 hash สตริงแปรรูปของ "Give Jerry a raise"
    ในตอนนั้น การส่งสตริงผ่าน SHA1 ถูกมองว่าเป็นกลไกสร้างความเชื่อมั่นว่าโครงสร้างของ seed จะหายไป ทำให้ NSA ไม่สามารถจงใจเลือก seed ที่อ่อนแอได้
    แต่ในทศวรรษ 2000 เมื่อ NIST/NSA ทำลายชื่อเสียงของตัวเอง คำอธิบายนี้อย่างเดียวก็ไม่พอจะสยบทฤษฎีสมคบคิดได้ และภายหลังเมื่อ NIST พยายามแสดงว่า seed นั้น benign โดยให้ Jerry Solinas สร้างซ้ำ เขากลับบอกว่าจำสตริงที่ตัวเองใช้ไม่ได้
    ถ้าเป็นนักทฤษฎีสมคบคิดตัวจริงก็คงมองว่าไม่มีใครจะหาสตริงที่สร้าง seed นี้เจอ แต่ถ้ามีคนหาเจอ ก็อาจเป็นแรงกระแทกค่อนข้างใหญ่ต่อทฤษฎีที่ว่า NIST P-curve ถูกสร้างขึ้นอย่างมีเจตนาร้าย จึงเป็น บาวน์ตีที่น่าสนุก

    • ต่อให้มีคนพบว่าสตริงอย่าง "Give Jerry a raise of $100000 dollars now!!!" มี hash ตรงกับ seed ผมก็ไม่คิดว่านั่นเป็นหลักฐานว่าไม่มีเจตนาร้าย
      เพราะถ้ารู้คุณสมบัติพิเศษที่เส้นโค้งอ่อนแอควรมี ก็สามารถลอง hash สตริงดัดแปลงคล้าย ๆ กันจำนวนมหาศาล แล้วเลือกจนกว่าจะได้ค่าคงที่ที่มีคุณสมบัติตามต้องการได้
    • ช่วงปลายทศวรรษ 1990 วิธีที่ใช้ MD5 กับ SHA1 ร่วมกัน เพื่อ “เพิ่มความแข็งแกร่ง” ในการประกอบแบบสุ่มก็เคยเป็นที่นิยม
      SSLv2 และ SSLv3 เป็นตัวอย่างที่ดี และแม้ขนาดผลลัพธ์จะตรงกับ SHA1 แต่ถ้าเป็น pipeline แบบ echo "$string" | md5sum | sha1sum ก็ไม่ได้ถึงกับน่าประหลาดใจมากนัก
    • ถ้าต้องการประวัติที่ยาวกว่านี้ ดูบทความของ Koblitz และ Menezes ที่กล่าวถึงในบทความชื่อ “A Riddle Wrapped in an Enigma” ได้ บทความนี้ยังพูดถึงด้วยว่าในปี 2015 ทำไม NSA จึงบอกว่าควรมุ่งไปสู่โลกหลังควอนตัม
      https://eprint.iacr.org/2015/1018
      https://eprint.iacr.org/2015/1018.pdf
      ข้อสงสัยเรื่อง backdoor แบบเดียวกันก็เคยมีใน (EC)DSA เช่นกัน และฝ่ายสนับสนุน RSA เคยอ้างว่า NSA ผลักดัน DSA เพราะใส่ backdoor ไว้ แต่ไม่มีหลักฐาน และตลอด 20 ปีก็ยังไม่มีใครค้นพบวิธีใส่ backdoor ใน DSA หรือ ECDSA
      ยังมีเกร็ดอีกว่า ในการประชุมมาตรฐานครั้งหนึ่ง ตัวแทน NSA ออกไปคุยโทรศัพท์แล้วกลับมาบอกว่า NSA เชื่อว่า ECC เพียงพอสำหรับการสื่อสารที่ปลอดภัยของหน่วยงานรัฐบาลสหรัฐฯ ทั้งหมด รวมถึง Federal Reserve ทำให้ทุกคนประหลาดใจ
      การปรับ DES ภายหลังถูกเปิดเผยว่าเป็น การป้องกัน differential cryptanalysis และจุดอ่อนของ SHA ดั้งเดิมคือ SHA-0 ก็ไม่มีอยู่ใน SHA-1 ฉบับสุดท้าย เช่นเดียวกับการกระทำอื่น ๆ ของ NSA ที่ถูกมองอย่างน่าสงสัย
    • ผมเคยเผา CPU ไปหนักมากเพื่อพยายามหาอินพุตที่ใช้สร้างค่า “สุ่ม” ประมาณ 166 บิตสำหรับสร้าง G ใน secp256k1 และ secp224k1 แต่ล้มเหลว
      ในทั้งสองเส้นโค้ง การเลือก G คือจุดที่มีพิกัด x ขนาดเหมาะเจาะจนน่าสงสัยแล้วนำมาคูณสอง และคุณลักษณะนั้นเหมือนกันในทั้งสองเส้นโค้ง
      ในเส้นโค้งเหล่านี้ การเลือก G เป็นอินพุตเดียวที่มี entropy สูง แต่พิสูจน์ได้ว่าในทางปฏิบัติแทบไม่เกี่ยวข้อง และอย่างมากผู้ที่เลือกมันก็จะรู้ discrete log แบบสุ่มเฉพาะตัวค่าเดียว
      ในโปรโตคอลที่ฝืนออกแบบมาก ๆ มันอาจกลายเป็น backdoor ได้ แต่ก็คงประดิษฐ์มาก ถึงอย่างนั้นผมก็มองว่ามันคุ้มที่จะลองหา เพราะเป็นพารามิเตอร์เดียวที่ไม่รู้ที่มา
      ถ้าหา seed ของ P-curve เจอ มันอาจคล้ายกับ seed ที่ใช้กับจุดกำเนิดของเส้นโค้งอื่น ๆ และอาจไขปริศนาเล็ก ๆ นี้ได้ด้วย
    • สำหรับวัตถุประสงค์แบบนี้ โดยทั่วไปมาตรฐานคือใช้ ค่าคงที่เหนือพีชคณิตอย่าง π หรือ e เพราะเลือกเองไม่ได้
      วลีต่าง ๆ ในทางทฤษฎีสามารถถูกเลือกเพื่อให้ได้ hash ตามที่ต้องการได้

  • GCHQ ของสหราชอาณาจักรจ้าง นักคณิตศาสตร์ มากกว่าสถาบันวิจัยหรือมหาวิทยาลัยใด ๆ ในประเทศ หน่วยงานคู่เทียบของสหรัฐฯ ก็น่าจะคล้ายกัน
    GCHQ และ NSA ก็รู้จักการแลกเปลี่ยนกุญแจ Diffie-Hellman ก่อนที่ Diffie กับ Hellman จะค้นพบใหม่เสียอีก
    เป็นเรื่องยากที่จะฟันธงถึงขีดความสามารถพื้นฐานของหน่วยข่าวกรอง และไม่ได้จะบอกว่าพวกเขารู้จักตระกูลเส้นโค้งที่อ่อนแอแบบนี้จริง ๆ แต่ก็ยากจะมองว่าเป็นไปไม่ได้ เรื่องนี้คือสายงานหลักของพวกเขา

    • ผมคิดว่าควรสงสัยไว้ก่อน โดยเฉพาะเพราะเหตุผลที่ยกมาว่าเป็นไปไม่ได้ถูกนำเสนอเหมือนเป็นเหตุผลทางคณิตศาสตร์ แต่จริง ๆ แล้วใกล้เคียงกับ เหตุผลทางสังคม มากกว่า
      โดยทั่วไปมักบอกกันว่าวงวิชาการเก่งมากจนถ้า NSA ทำอะไรไว้ก็คงถูกค้นพบไปแล้ว และถ้าไม่เห็นด้วยก็จะถูกมองว่าเป็น FUD ของคนไม่รู้จริง บทความนี้ก็เดินตามแนวทางนั้นซ้ำอีก แต่ก็ดีที่การตั้ง bounty อย่างเป็นระบบทำให้ประเด็นนี้ถูกพิจารณาอย่างจริงจังขึ้น
      ผมเคยทำงานด้านการเข้ารหัสในอดีต และเป็นเวลาหลายปีที่ต้องตรวจทานงานวิจัยด้านการเข้ารหัสเป็นประจำจากหน้าที่การงาน รวมทั้งเคยเข้าร่วมงานประชุม พูดคุยกับนักวิจัย และเคยทำ implementation การเข้ารหัสด้วยเส้นโค้งวงรีที่ “แปลก ๆ” หลายแบบ จากมุมมองที่ไม่ใช่คนวงในเต็มตัว แต่ก็ไม่ใช่คนนอกเสียทีเดียว ความเชื่อทั่วไปนี้ดูอันตราย
      แกนของเหตุผลมีสองข้อ คือ หากมีการโจมตีแบบ kleptography ต่อการกำหนดมาตรฐานเส้นโค้งของ NIST ได้ วงวิชาการหรืออุตสาหกรรมก็น่าจะหาเจอไปแล้ว และข้ออ้างที่ว่า Dual_EC_DRBG ถูกตั้งข้อสงสัยทันที จึงแปลว่าชุมชนการเข้ารหัสแบบเปิดตรวจจับ backdoor ได้ดี
      ข้อแรกโน้มน้าวใจได้น้อย ในวงวิชาการมีปัญหา file drawer และแรงจูงใจแบบ “ตีพิมพ์หรือหายไป” สำหรับนักวิจัยรุ่นใหม่ เห็นได้ชัดว่าระหว่างการสร้างอัลกอริทึม zero-knowledge proof ใหม่เพื่อออกบทความที่มีคนอ้างอิง กับการโจมตีอัลกอริทึมที่ทุกคนเชื่อว่าแข็งแกร่งแล้วอาจไม่ได้อะไรเลย ทางไหนได้เปรียบกว่า
      หลักฐานคือฉันทามติของผู้เชี่ยวชาญที่ว่า “มีคนฉลาดจำนวนมากศึกษาอย่างลึกซึ้งแล้ว แต่ไม่พบอะไร” แต่ในวงวิชาการ การตีพิมพ์ ผลลัพธ์เชิงลบ ทำได้ยาก จึงไม่มีทางรู้ได้เลยว่ามีความพยายามถูกทุ่มลงไปจริงมากแค่ไหน
      ตัว kleptography เอง หรือวิธีใส่ backdoor ลงในมาตรฐาน ก็แทบไม่มีประโยชน์เว้นแต่จะเป็น NSA จึงไม่ใช่เส้นทางอาชีพที่ดี และยังเสียเปรียบต่อการย้ายไปอุตสาหกรรมหรือการถูกอ้างอิงด้วย
      ในทางกลับกัน NSA สามารถจ่ายค่าจ้างได้มากกว่าวงวิชาการ จ้างนักวิจัยได้มากกว่าวงวิชาการทั้งระบบเพื่อทุ่มให้กับงานวิจัยที่มีโอกาสล้มเหลวสูงหรือมีประโยชน์เฉพาะกับ backdoor ในมาตรฐาน และด้วยงบประมาณฮาร์ดแวร์ ยังสามารถทำวิจัยสหสาขาที่งานวิจัยการเข้ารหัสในวงวิชาการทำไม่ได้มาเป็นเวลาหลายทศวรรษ
      ถ้าต้องเดิมพันว่าฝ่ายไหนเข้าใจ ECC มากกว่ากันระหว่าง NSA กับวงวิชาการ พลังการยิงอยู่ฝั่งรัฐบาล และเทียบกันไม่ติด เราพอประเมินคร่าว ๆ ได้ว่ารัฐบาลจ้างปริญญาเอกคณิตศาสตร์กี่คน แต่ไม่รู้เลยว่าวงวิชาการทุ่มพลังจริง ๆ ลงในพื้นที่ปัญหานี้มากแค่ไหน
      เหตุผลข้อที่สองก็ไม่ได้สมบูรณ์นัก ไม่ใช่แค่ Dual_EC_DRBG เท่านั้น ผู้คนก็ตั้งข้อกังวลต่อเส้นโค้ง NIST ทันทีเช่นกัน ความต่างมีเพียงกรณีแรกมีอัลกอริทึมที่รู้จักอยู่แล้วสำหรับทำการโจมตีที่จำเป็น ส่วนกรณีหลังไม่มี
      วิธีทำให้ไม่ต้องมีข้อถกเถียงแบบนี้ตั้งแต่แรกเป็นสิ่งที่รู้กันมาหลายทศวรรษแล้ว และนั่นก็เป็นเหตุผลที่เส้นโค้ง NIST ถูกสร้างจากผลลัพธ์ SHA1 เวลาที่ดีที่สุดในการเลิกใช้เส้นโค้ง NIST แบบค่อยเป็นค่อยไปคือหลายสิบปีก่อน และเวลาที่ดีรองลงมาคือตอนนี้
    • NSA ยังจ้าง ศาสตราจารย์คณิตศาสตร์ด้านทฤษฎีจำนวนเต็ม ของสหรัฐฯ ด้วย

  • เหตุผลที่ผมร่วมสนับสนุน bounty นี้คือ ถ้ามันเป็นวลีที่ crack รหัสผ่านได้จริง การรู้ให้ได้ว่าวลีนั้นคืออะไรจะมี ความหมายทางประวัติศาสตร์อย่างมาก

  • การที่เส้นโค้งวงรีของ NIST ถูกสร้างขึ้นด้วยการ hash seed ที่ NSA ให้มา นับว่าน่ากังวลพอสมควร
    ฟังดูเหมือน “ไม่ต้องห่วงหรอก เราแค่ hash ประโยคธรรมดา ๆ มาสร้าง ตอนนี้ลืมไปแล้ว แต่ Jerry แค่พูดเล่นเรื่องขึ้นเงินเดือนเท่านั้นเอง”
    ยากจะเชื่อว่าทำไมถึงไม่ผ่านการตรวจสอบอย่างเข้มงวดเร็วกว่านี้ และทำไมจึงไม่ใช้ การเลือก seed ที่สมเหตุสมผลกว่า เช่น ผสม seed สุ่มจากหลายฝ่ายที่มีผลประโยชน์ต่างกัน รวมถึง hardware random number generator เป็นต้น

    • ที่รู้สึกแบบนั้นเพราะเราใช้ชีวิตอยู่ในปี 2023 และมองย้อนหลังโดยรู้สิ่งที่เกิดขึ้นตั้งแต่ทศวรรษ 1990 จนถึงตอนนี้
      วิธีแบบนั้นน่าจะดี แต่ในเวลานั้นคงมีคนไม่มากที่เห็นความจำเป็น
    • ถ้า traffic อินเทอร์เน็ตส่วนใหญ่ในวันนี้ถูกเข้ารหัสแล้ว ก็อดสงสัยไม่ได้ว่าศูนย์ข้อมูลยักษ์อย่าง Bluffdale จำเป็นไปทำไม
      https://en.wikipedia.org/wiki/Utah_Data_Center

  • มีวิดีโอที่ศาสตราจารย์ Dan Boneh อธิบายเบื้องหลังไว้: https://youtu.be/8WDOpzxpnTE?t=892

  • ถ้าผมเข้าใจถูก แปลว่าชุมชนยอมรับสตริงน่าสงสัยที่ไม่รู้ที่มา ทั้งที่การใส่อินพุตอื่นที่รู้จักเข้าไปใน hash เพื่อเปลี่ยนมันเป็น สตริงที่มีที่มาชัดเจน นั้นทำได้ง่ายมากใช่ไหม?

    • เข้าใจถูกแล้ว และนั่นค่อนข้างหายนะเลย นึกถึงวลี “เกือบจะถึงแล้วแท้ ๆ” กับ “คุณมีงานต้องทำแค่อย่างเดียว” ขึ้นมา
      น่าเศร้าที่เท่าที่ผมรู้ นี่เป็นกรณีเดียวที่พูดถึงความไร้ความสามารถเกี่ยวกับ NSA และมาตรฐานการเข้ารหัส ปกติเรื่องเล่ามักไปในทิศทางตรงข้าม
      ที่เป็นปัญหายิ่งกว่าคือ NIST เคยมีประวัติใส่ backdoor ในมาตรฐานเกี่ยวกับเส้นโค้งวงรีมาแล้ว และยังมีคนชี้ทันทีว่ากลไกนี้ไม่สามารถสร้างความเชื่อมั่นได้ แต่ NIST หรือ NSA ก็ไม่ได้ทำอะไรเลย เหมือนกับกรณี Dual_EC_DRBG
      ที่เป็นปัญหายิ่งไปกว่านั้นอีกคือในปี 2015 NSA ระบุอย่างชัดเจนว่าอย่าอัปเกรดไปใช้เส้นโค้งอื่นหลังยุคเส้นโค้ง NIST เหตุผลคือคอมพิวเตอร์ควอนตัมจะดีพอที่จะทำลาย ECC ทั้งหมดได้ในไม่ช้า ดังนั้นทุกคนควรย้ายไปใช้การเข้ารหัสหลังควอนตัม
      ถ้า ECC ทำงานได้ดี คอมพิวเตอร์ควอนตัมยังอยู่อีกไกล และต้องการผูกผู้คนไว้กับเส้นโค้ง NIST ให้นานที่สุดเท่าที่ทำได้ ก็คงพูดแบบนั้นพอดี
      ชุมชนการเข้ารหัสในสถานการณ์นี้คงยากจะเรียกว่ามีเกียรติ ผ่านมาเกือบ 25 ปีแล้ว และมีเส้นโค้งใหม่กว่าที่ไม่มีปัญหานี้ แล้วทำไมเส้นโค้ง NIST ยังถูกใช้อยู่? ความพยายามที่จะค่อย ๆ เลิกใช้เหมือน SHA1 อยู่ที่ไหน? บทความนี้กลับดูเหมือนกำลังโปรโมตเส้นโค้งเหล่านั้นเสียด้วยซ้ำ

  • ถ้ารู้สึกว่าตัวเองโชคดี ก็ลอง เดาแฮช SHA1 ได้ที่นี่: https://wending.dev/hash_guessing/

    • นั่นมันแค่สร้าง SHA1 ของสตริงที่ป้อนไม่ใช่เหรอ? ตามที่บทความบอก มันควรต้องมี ตัวนับ บางรูปแบบรวมอยู่ด้วย
      ถ้าตัวสร้าง seed ของ NSA รู้เรื่องคริปโตกราฟีกับคอมพิวเตอร์แม้แต่นิดเดียว ก็คงไม่มีทางมานั่งพิมพ์วลีต่างกัน 500 วลีด้วยมือจนกว่าจะได้เส้นโค้งที่ดี
      ต่อให้ทำแบบนั้นจริง รูปแบบที่เป็นไปได้ก็ไม่มีที่สิ้นสุด เช่น ใส่จุดต่อท้าย เปลี่ยนตัวพิมพ์เล็ก/ใหญ่ หรือทำเป็นตัวพิมพ์ใหญ่แบบชื่อเรื่อง
      รายการรูปแบบที่น่าจะลองไม่มีทางสมบูรณ์ได้ แต่ถ้าหน้านี้สร้างแค่แฮช SHA1 แบบนี้ ต่อให้เดาสตริงได้ถูกต้องทั้งเครื่องหมายวรรคตอนและตัวพิมพ์เล็ก/ใหญ่ ก็แทบเป็นไปไม่ได้ที่จะหาแฮชจริงเจอ
      อย่างน้อยที่สุด ถ้าจะตรวจว่าค่าแฮชผลลัพธ์เป็นค่าที่ถูกเพิ่มขึ้นหรือไม่ ก็ควรตรวจได้ประมาณว่า 10 ไบต์ด้านหน้าหรือด้านหลังตรงกันไหม ถึงอย่างนั้นส่วนใหญ่ก็มีแต่ทำให้เสียเวลา และผู้เขียนก็คงรู้ว่ามันจะไม่พาไปสู่อะไร
      ในหน้าควรเขียนไว้ว่าเป็นแค่ของเล่นสาธิตเท่านั้น และถึงจะเดาถูกก็ไม่ได้ช่วยให้หา seed จริงเจอ

  • สิ่งที่ได้เรียนรู้จากการดูนักวิทยาการรหัสลับเถียงกันอย่างดุเดือดมานานคือ “อย่าเดิมพันข้าง Bernstein และอย่าเชื่อ NIST”
    ตอนนี้คงต้องแก้เป็น “อย่าเดิมพันข้าง Bernstein หรือ Filippo และอย่าเชื่อ NIST ถ้ากฎสองข้อนี้ขัดกัน ก็ยังคงอย่าเชื่อ NIST”

  • จริงอยู่ที่ SHA-1 ถูกทำลายแล้ว แต่ผมคิดว่าปัญหาหลัก ๆ คือเรื่องอย่างการชนกันผ่านการโจมตีแบบ length extension หรือการโจมตีแบบ known-plaintext
    ผมยังมองว่าการหา วลีลับ เมื่อมีแค่แฮชให้ ยังคงเป็นเรื่องที่จัดการได้ยากในทางปฏิบัติ

    • ถูกต้อง โดยทั่วไปยังถือว่า SHA-1 ยังมี ความต้านทานต่อการหาค่าต้นฉบับ อยู่
      แต่ถ้าสมมติฐานเรื่องโครงสร้างของ seed ถูกต้อง ความต้านทานต่อการหาค่าต้นฉบับก็ไม่ได้สำคัญมากนักในกรณีนี้ SHA-1 เร็วมากและทำขนานได้ง่าย ดังนั้นคนที่ไล่ค้นพื้นที่รูปแบบต่าง ๆ ของ "Jerry needs a raise" อย่างมุ่งมั่น ก็มีโอกาสพอสมควรที่จะเจออินพุตดั้งเดิม
    • นี่เป็นเพียง การโจมตีด้วยพจนานุกรม ธรรมดา ๆ และเป็นวิธีที่แฮชรหัสผ่านส่วนใหญ่ถูกแกะได้
      แทบไม่เกี่ยวกับตัว SHA1 เอง