เลขคณิตเส้นโค้ง NIST ใน Pure Pascal สำหรับลงนาม PDF

HotPDF ทำการตกลงคีย์แบบ elliptic-curve และการตรวจสอบลายเซ็นสำหรับ PDF ใน Object Pascal ล้วน ๆ โดยไม่มี binding ของ OpenSSL และไม่มี provider เข้ารหัสระดับ platform แทรกอยู่ในเส้นทาง มันครอบคลุมห้าเส้นโค้ง: P-256, P-384 และ P-521 สำหรับตระกูล NIST prime บวกกับ X25519 และ X448 สำหรับการตกลงคีย์บนเส้นโค้ง Montgomery เหตุผลที่เขียนโค้ดนี้เองแทนการ link เข้ามาคือ deployment ไม่ใช่ความบริสุทธิ์ แอปพลิเคชัน Delphi หรือ Free Pascal ที่แจกจ่าย executable เดียวโดยไม่มี DLL เข้ารหัสจะไม่มีความเหลื่อมของเวอร์ชันให้ต้องจัดการ ไม่มี provider ราย platform ให้ต้องตรวจจับ และไม่มีอะไรเปลี่ยนพฤติกรรมเมื่อลูกค้าแพตช์ system library ของเขา

ต้นทุนก็คือตอนนี้เลขคณิตเป็นของคุณ การคูณแบบ modular ของจำนวนเต็มขนาดใหญ่เป็นโค้ดที่ไม่ให้อภัย มันจะให้ผลเหมือนเวกเตอร์ทดสอบที่เผยแพร่ไว้แบบไบต์ต่อไบต์ หรือไม่ก็ให้ขยะที่ดูน่าเชื่อถือ และระยะระหว่างสองสถานะนั้นอาจเป็นการเทียบเพียงครั้งเดียว เรื่องนี้คือเรื่องของการเทียบจุดนั้น เพราะรูปร่างของบั๊กขยายไปถึงการพอร์ตเลขคณิต field ภาษา Pascal ทุกรูปแบบ

ทำไมไลบรารี PDF จึงต้องมีเลขคณิตเส้นโค้ง

มีสองฟีเจอร์ที่ดึงมันเข้ามา อย่างแรกคือการเข้ารหัสเอกสารด้วย public key: handler recipient-list ของ ISO 32000 ห่อคีย์ประจำเอกสารไว้ให้ใบรับรองที่ระบุชื่อ และเมื่อผู้รับถือ EC key การห่อจะวิ่งผ่านการตกลงคีย์ ไม่ใช่การส่งคีย์แบบ RSA โดยไม่มี ECDH ก็ไม่มีทางเปิดเอกสารแบบนี้ได้ อย่างที่สองคือการตรวจสอบลายเซ็น การ verify ลายเซ็น ECDSA ทับไบต์ /ByteRange ต้องใช้การคูณจุดบนเส้นโค้งของผู้ลงนาม และ P-384 เป็นของที่พบบ่อยใน profile ภาครัฐและ qualified-signature ที่ P-256 ถูกมองเป็นเพดานต่ำสุด ไม่ใช่เป้าหมาย HotPDF เปิดเผยผลของงานชุดนี้ผ่านเส้นทางการตรวจสอบ ECDSA และ CMS และผ่านโมเดล signature-provider แบบต่อเสริมได้

แผนภาพจุดที่เลขคณิตเส้นโค้งภาษา Pascal ล้วนของ HotPDF ถูกใช้: การเข้ารหัส recipient-list ด้วย ECDH และการตรวจสอบลายเซ็น ECDSA ทับ ByteRange — การตกลงคีย์เปิดเอกสารที่เข้ารหัสด้วย EC ให้ผู้รับที่ระบุชื่อ ขณะที่การตรวจสอบลายเซ็นต้องการการคูณจุดบนเส้นโค้งของผู้ลงนาม

CIOS และการลบหนึ่งครั้งที่ท้ายทาง

การคูณแบบ Montgomery เลี่ยงการหารโดยทำงานในโดเมนที่ถูกแปลง ที่ที่การ reduce เป็นเพียงการ shift ตัวแปรที่ HotPDF ใช้คือ Coarsely Integrated Operand Scanning ซึ่งสานการคูณกับการ reduce ทีละ limb ค่า intermediate จึงไม่เคยโตเกินความกว้างของ modulus บวกอีกหนึ่ง limb เนื้อคู่ของลูปตรงไปตรงมาและทดสอบง่าย ส่วนท้ายไม่ตรงไปตรงมา: หลังรอบการสานผ่านไปแล้ว accumulator อาจอยู่ที่ใดก็ได้ในช่วงถึงสองเท่าของ modulus อัลกอริทึมจึงจบด้วยการลบแบบมีเงื่อนไข ที่ตัดสำเนาของจำนวนเฉพาะออกหนึ่งสำเนาก็ต่อเมื่อ accumulator มากกว่าหรือเท่ากับมัน

การเทียบตัวเลขหลาย limb หมายถึงการเดินจาก limb สูงสุดลงมาโดยพก borrow ไปด้วย วิธีเขียนที่ชัดที่สุดคือเทียบ limb ของ accumulator กับ limb ของ modulus บวก borrow ที่ไหลเข้ามา นิพจน์นั้นผิด และผิดในแบบที่เส้นโค้งส่วนใหญ่ปิดบังไว้

// ผิด: P[I] + Borrow อาจ wrap เมื่อ P[I] เป็น $FFFFFFFFFFFFFFFF
if T[I] < P[I] + Borrow then
begin
  Borrow := 1;
  Break;
end;

// ถูกต้อง: เทียบโดยไม่ต้องบวกเข้า limb เลย
if (T[I] < P[I]) or ((T[I] = P[I]) and (Borrow = 1)) then
begin
  Borrow := 1;
  Break;
end;

การ wrap ของ borrow หน้าตาเป็นอย่างไรจริง ๆ

หน้าตาของมันคือเส้นโค้งที่ใช้ได้ทุกที่ ยกเว้นใน production จำนวนเฉพาะของ P-384 และ P-521 มี limb ที่เป็นเลขหนึ่งล้วนทั้ง limb จึงมีค่า P[I] เท่ากับ $FFFFFFFFFFFFFFFF บวก borrow ที่ไหลเข้ามาค่าหนึ่งเข้าไปแล้วเลข 64 บิตแบบไม่มีเครื่องหมาย wrap เป็นศูนย์ การเทียบจะถามว่า limb ของ accumulator น้อยกว่าศูนย์หรือไม่ ตัดสินว่าไม่ แล้วสรุปว่าไม่ต้องมี borrow ผลลัพธ์จึงเพี้ยนไปหนึ่งที่ limb เดียว

แผนภาพการ wrap ของ borrow ใน Montgomery reduction เทียบการเทียบ limb ที่ผิดกับการ propagate borrow ที่ถูกต้องในเลขคณิต P-384 ของ HotPDF — การบวก borrow ลง limb ที่เป็นเลขหนึ่งล้วน wrap เป็นศูนย์ P-384 และ P-521 จึงพลาดการลบ ขณะที่ P-256 ปิดบังข้อบกพร่องไว้

P-256 รอดพ้นเพราะไม่มี limb ตัวใดเป็นเลขหนึ่งล้วน การบวกจึงไม่เคย overflow และนิพจน์ที่บกพร่องบังเอิญเห็นพ้องกับตัวที่ถูกต้อง นั่นคือผลลัพธ์ที่เลวที่สุดเท่าที่ชุดทดสอบจะเจอ: เส้นโค้งที่ถูกทดสอบมากที่สุดผ่าน เส้นโค้งที่ถูกทดสอบน้อยกว่าพลาดเป็นช่วง ๆ ตามค่า operand และความล้มเหลวปรากฏเป็นผลตรวจว่า "ลายเซ็นไม่ถูกต้อง" กับเอกสารที่ถูกต้องสมบูรณ์ HotPDF แบก gate เจาะจงกับ P-384 ไว้เพื่อเหตุผลนี้โดยตรง โดยคืนสถานะว่าไม่พร้อมใช้แทนคำตอบที่ผิด จนกว่าเลขคณิตจะถูกพิสูจน์กับเวกเตอร์อ้างอิง

บั๊กถูกค้นพบตำแหน่งได้อย่างไรจริง ๆ

ไม่ได้ค้นด้วยการอ่านโค้ด ลำดับที่ให้ผลเป็นกลไกและนำไปใช้ซ้ำได้ หนึ่ง กำจัดค่าคงที่ออกก่อน: limb ทุกตัวของ p, R และ R^2 ถูกสร้างใหม่อย่างเป็นอิสระและเทียบทีละ limb ซึ่งกำจัดแหล่งบั๊กเส้นโค้งที่พบบ่อยที่สุดทิ้งไป สอง ใส่เครื่องมือวัดที่เลขคณิต ไม่ใช่ที่ API: โพรซีเดอร์ dump ชั่วคราวพิมพ์ค่า intermediate ของการคูณ Montgomery ของ R^2 ของ x^3 และของ y^2 กับจุดที่รู้จัก เพื่อให้เทียบกับค่าความจริงที่คำนวณอย่างเป็นอิสระได้

การเทียบนั้นชี้ตรงไปที่ตัวการ x ถูกตลอดสาย ขณะที่ y^2 ต่างกันเพียง limb เดียวด้วยค่าหนึ่งพอดี ความต่าง limb เดียวด้วยค่าหนึ่งไม่ใช่บั๊กการคูณ บั๊กการ propagate carry หรือบั๊กค่าคงที่ แต่คือบั๊กสาย borrow และสาย borrow เพียงสายเดียวใน routine ก็คือการลบแบบมีเงื่อนไขตอนท้าย มีรายละเอียดหนึ่งที่เกือบทำให้การไล่ล่าหลงทาง: ค่าคงที่อ้างอิงที่ใช้กับ dump ถูกเขียนผิดลำดับไบต์ในครั้งแรกเอง ทำให้เกิดความไม่ตรงกันที่ค่า y และชี้นำชั่วขณะว่ามีข้อบกพร่องที่สองที่ไม่มีอยู่จริง ให้ตรวจ endianness ของค่าความจริงของคุณก่อนเชื่อมันให้กล่าวหาโค้ดของคุณ

ผังงานวิธีค้นตำแหน่งบั๊กเส้นโค้งของ HotPDF ด้วยการสร้างค่าคงที่ใหม่ ดัมพ์ค่า intermediate แบบ Montgomery และ diff กับค่าความจริงจาก mirror — ความต่าง limb เดียวด้วยค่าหนึ่งพอดีชี้ตรงไปที่สาย borrow เพียงสายเดียวใน routine และค่าอ้างอิงที่สลับไบต์เกือบทำให้การไล่ล่าหลงทาง

กับดักข้างเคียงใน routine เดียวกัน

มี failure mode อีกสามแบบอาศัยอยู่ห่างจากการเทียบนั้นไม่กี่บรรทัด และทั้งสามเคยมีชีวิตระหว่างการพัฒนา

// 1. accumulator มี limb เหนือความกว้างของ modulus หนึ่งตัว การเทียบ
//    เฉพาะ L limb ต่ำ ๆ พลาดกรณีที่ T เท่ากับ p บวก 2^(64*L) พอดี
//    ซึ่งเกิดกับอินพุตสุ่มอยู่ไม่น้อย เพราะ 2p เกิน 2^256 สำหรับ P-256
//    และเกิน 2^384 สำหรับ P-384
if (T[L] <> 0) or NotLessThanModulus(T, P, L) then
  SubtractModulus(T, P, L);

// 2. การลบแบบ multi-limb ทั่วไปมีอันตราย wrap เช่นเดียวกัน เมื่อ
//    Y[I] เป็น $FFFFFFFFFFFFFFFF ค่า Y[I] + Borrow จะ wrap เป็นศูนย์
//    และ borrow ต้องรอดไป limb ถัดไป ไม่ใช่ถูกเคลียร์ทิ้ง
Diff := X[I] - Y[I] - Borrow;
NextBorrow := Ord((X[I] < Y[I]) or ((X[I] = Y[I]) and (Borrow = 1)));

ข้อที่สามไม่ใช่โค้ด แต่คือแหล่งที่มา จำนวนเฉพาะของ P-521 ถูกจดออกมาครั้งแรกด้วยเลขฐานสิบหก 130 หลัก ขาด F ไปหนึ่งตัว แล้วค่าคงที่ Montgomery ก็ถูกคำนวณจากจำนวนเฉพาะที่ผิดนั้น ค่าคงที่จึงสอดคล้องกันในตัวเองแต่ผิดพร้อมกันทั้งชุด พารามิเตอร์เส้นโค้งต้องถูก derive ไม่ใช่พิมพ์ใส่: คำนวณ R เป็น (1 shl (64 * L)) mod p จากจำนวนเฉพาะที่คุณใช้จริง แล้วเทียบข้าม R * R mod p กับค่าที่ค่าคงที่ R^2 ของคุณอ้างว่ามี ค่าคงที่คู่หนึ่งที่เห็นพ้องกันเองไม่พิสูจน์อะไรกับตัวใดตัวหนึ่งเลย

กลยุทธ์การตรวจสอบที่ขยายได้เกินเส้นโค้งเดียว

เทคนิคที่ทำให้ X25519 และ X448 ควบคุมได้คือการเขียน mirror implementation ในภาษาที่มีจำนวนเต็มไม่จำกัด แล้วถ่ายทอด control flow ของ Pascal ลงไปทีละบรรทัด เมื่อ mirror ให้คำตอบที่ถูกแต่ Pascal ให้ไม่ถูก ข้อบกพร่องคือความพลาดตอนถ่ายทอด และการเจาะดูค่า intermediate ตัวเดียวกันในทั้งสอง implementation จะจับมันได้ในไม่กี่วินาที ความผิดพลาดคลาสสิกของ ladder ตาม RFC 7748 ทั้งสามอย่างถูกจับได้ด้วยวิธีนี้: swap แบบ constant-time ที่บรรทัดที่สองกลับไปใช้ค่าที่สลับไปแล้ว, การกลับด้านตอนจบที่คืน z ยกกำลังลบหนึ่งแทนที่จะคูณมันเข้าไปใน X และการคูณด้วยค่าคงที่เล็กที่ประกอบผลคูณครึ่งเวิร์ดด้วย bitwise or แล้วทำ carry หล่นหาย

สำหรับเนื้อหาทดสอบ ให้หยิบเวกเตอร์ในรูปไบต์ ไม่ใช่รูปข้อความ การดึง private key ด้วยรูปแบบข้อความคือหนทางที่ implementation ที่ถูกต้องถูกกล่าวหาว่าผิดแบบเลื่อนไบต์หนึ่งตำแหน่ง ทั้งที่ความผิดอยู่เต็ม ๆ ในขั้นตอนการดึงเอง ให้ตัดเลขฐานสิบหกออกจาก DER encoding ที่ offset ที่รู้จักแล้วเทียบกันเป็นอาร์เรย์ไบต์

เมื่อสาย borrow ถูกแก้แล้ว ทั้งห้าเส้นโค้งตรงกับเวกเตอร์อ้างอิงที่เผยแพร่ไว้แบบไบต์ต่อไบต์ และ HotPDF ไม่ต้อง gate เส้นโค้งตัวใดอีก ถ้าคุณกำลังต่อระบบลงนามด้วยใบรับรองหรือการเข้ารหัสแบบ recipient-list ข้อสรุปเชิงปฏิบัติคือการเลือกเส้นโค้งตอนนี้เป็นการตัดสินใจเชิงนโยบาย ไม่ใช่คำถามเรื่องความสามารถ profile และกับดักลำดับไบต์ฝั่งลงนามอยู่ในคู่มือเดินลงนาม PAdES รายละเอียด component และตารางอัลกอริทึมที่รองรับอยู่บนหน้าผลิตภัณฑ์HotPDF Delphi PDF component