PDFlibPas ลงนามและตรวจสอบด้วย Ed448 และเส้นโค้ง ECDSA ของ Brainpool ทั้งสามเส้นใน Object Pascal ล้วน ๆ ไม่มีไลบรารีเข้ารหัสภายนอก ไม่มี platform provider ไม่มี DLL: PDFlibEd448 ใช้งาน PureEdDSA ตาม RFC 8032 บน edwards448 ส่วน PDFlibBrainpool ใช้งาน brainpoolP256r1, brainpoolP384r1 และ brainpoolP512r1 ตาม RFC 5639 ทั้งสองสร้างขึ้นด้วยวิธีเดียวกันคือตรวจกับ known-answer vectors ที่สร้างขึ้นอย่างเป็นอิสระก่อนที่โค้ด Pascal จะถูกเขียนสักบรรทัด และทั้งสองสมควรได้รับการเล่าถึงเป็นหลักเพราะบั๊กที่พบระหว่างทาง
เลขคณิตระดับ field เป็นโค้ดที่ซื่อสัตย์ผิดปกติ มันจะตรงกับเวกเตอร์ที่เผยแพร่ไว้แบบไบต์ต่อไบต์หรือไม่ตรงเลย จึงไม่มีที่ว่างให้กับคำว่า "ใช้ได้เกือบดี" สิ่งที่ทำให้มันยากคือการใช้งานที่ผิดยังคงสร้างลายเซ็นได้ ยังตรวจสอบลายเซ็นของตัวเองผ่าน และยังดูน่าเชื่อถืออย่างสมบูรณ์
ทำไมต้องเส้นโค้งเหล่านี้ และทำไมต้องเป็น Pascal
เส้นโค้ง Brainpool ปรากฏใน qualified-signature profiles ของยุโรป ไลบรารีที่ลงนามเอกสารเพื่อตลาดนี้จึงเลือกไม่ได้ว่าจะมองมันเป็นของแปลกหรือไม่ Ed448 อยู่ในชุดอัลกอริทึมที่ ISO/TS 32002 นำเข้ามาใน PDF ซึ่ง digest ภายในของมันคือ SHAKE256 แทนที่จะเป็น SHA-2 ทั้งสองตระกูลไม่มีอยู่ในไลบรารีเข้ารหัสภาษา Pascal ที่ใช้กันทั่วไป ไลบรารี PDF ที่ต้องการมันจึงต้องสร้างขึ้นเอง
ข้อโต้แย้งด้านการ deploy ก็คือข้อเดียวกับที่ใช้กับงานเข้ารหัสทั้งหมดของไลบรารีนี้: แอปพลิเคชันที่แจกจ่ายไบนารีเดียวโดยไม่มี dependency ด้านการเข้ารหัสจะไม่มี provider ให้ต้องตรวจจับ ไม่มีเวอร์ชันให้ต้องจับคู่ และไม่มีพฤติกรรมที่เปลี่ยนไปเมื่อเครื่องโฮสต์ถูกแพตช์ การลงนามเป็นพื้นที่ที่คุณอยากให้ dependency ขยับตัวน้อยที่สุดเสียแล้ว
ค่าคงที่มาจากข้อความในสเปกเท่านั้น ไม่ใช่จากความจำ
ครั้งแรกที่เขียน base point ของ edwards448 จากความจำ ผลออกมาผิด นั่นไม่ใช่ความผิดพลาดที่น่าแปลกใจอะไร แต่มันแพงมาก เพราะ base point ที่ผิดจะสร้างระบบที่สอดคล้องในตัวเอง: การสร้างคีย์ การลงนาม และการตรวจสอบของคุณเห็นพ้องกันเองทั้งหมด แล้วขัดแย้งกับที่เหลือของโลก
ขั้นตอนที่ใช้ได้ผลคือหยิบ domain parameter ทุกตัวจากข้อความในสเปก แล้วไล่ตรวจซ้ำข้ามกัน สำหรับ edwards448 หมายถึงจำนวนเฉพาะ ค่าคงที่ของเส้นโค้ง อันดับของกรุป และพิกัดฐานสิบของ base point ทั้งสองค่าจาก RFC 8032 แปลงเข้าสู่รูปแบบ limb ภายใน แล้วตรวจกับเวกเตอร์ทดสอบที่เผยแพร่ไว้ในเอกสารฉบับเดียวกัน สำหรับเส้นโค้ง Brainpool หมายถึงพารามิเตอร์จาก RFC 5639 การใช้งานอิสระที่เขียนขึ้นเพื่อสร้างเวกเตอร์ และการตรวจข้ามกับ system library ทั้งสองทิศทางก่อนที่โค้ด Pascal บรรทัดแรกจะรัน
ทางลัดในการ derive หนึ่งตัวสมควรได้รับคำเตือน เพราะมันดูเป็นสากลแต่ไม่ใช่: การกู้ base point คืนจากค่า y คงที่ใช้ได้กับเส้นโค้งตระกูล 25519 แต่ใช้ไม่ได้กับ edwards448 ที่ค่าดังกล่าวไม่มีรากที่สอง สคริปต์หนึ่งตัวหักล้างข้อสมมตินี้ได้ในไม่กี่วินาที ซึ่งถูกกว่าการมาค้นพบมันผ่านดีบักเกอร์อยู่หลายเท่า
วิธีการ: สร้าง mirror ระดับ limb ก่อนแตะ Pascal
เทคนิคที่ทำให้ทั้งสองยูนิตควบคุมได้คือการสร้าง mirror implementation ในภาษาที่มีจำนวนเต็มไม่จำกัดขนาด สร้างจากล่างขึ้นบน เริ่มจากชั้นเลขคณิตเพียงอย่างเดียว: field multiply, subtraction และการ propagate carry ทดสอบเครื่องหนักกับ invariant ทางพีชคณิตของมันสักสองร้อยเคสสุ่ม จากนั้นจึงเป็นการสร้างคีย์แบบเต็มภายใน mirror ซึ่งเป็นที่อยู่ของบั๊กเชิงความหมายและเป็นจุดที่จับมันได้ราคาถูก แล้วเท่านั้นจึงลงมือเขียนเป็น Pascal
ผลตอบแทนของมันอยู่ที่การวินิจฉัยมากกว่าการพัฒนา เมื่อ mirror ได้รับการพิสูจน์แล้วว่าถูกต้อง ความไม่ลงรอยใด ๆ ระหว่าง mirror กับ Pascal คือความผิดพลาดตอนเขียนถ่ายทอด และการเจาะดูค่า intermediate ตัวเดียวกันในทั้งสอง implementation จะชี้ตำแหน่งมันได้ทันที สิ่งนี้เปลี่ยนบั๊กประเภทที่แทบดีบักไม่ได้เลย คือ limb ผิดเพียงตัวเดียวลึกอยู่ใน scalar multiplication ให้กลายเป็นการเทียบค่าห้านาทีเท่านั้น
สาเหตุรากสี่ประการใน Ed448
ทั้งสี่พบได้จากการเจาะดูค่า intermediate และทั้งสี่ล้วนเป็นประเภทที่ผลิตผลลัพธ์ซึ่งดูถูกต้องได้
ประการแรกคือกับดักสัญกรณ์ สูตรการบวกแบบ Edwards ที่เผยแพร่กันส่วนใหญ่สมมติว่าค่าคงที่ของเส้นโค้งเป็นลบหนึ่ง ขณะที่ edwards448 มีค่าเป็นบวกหนึ่ง เมื่อก๊อปมาใช้โดยไม่แก้ ตัวเศษของพิกัด y จะถูกเขียนเป็นการบวกทั้งที่ควรเป็นการลบ ทางแก้ไม่ใช่การไปแพตช์เครื่องหมาย แต่เป็นการ derive รูปผลคูณแบบไม่ต้องหา inverse ใหม่จาก addition law แบบ affine ของเส้นโค้งที่ถูกต้อง ซึ่งให้นิพจน์พิกัดทั้งสี่ออกมา และไม่เหลือช่องให้เครื่องหมายถูกสืบทอดมาจากแหล่งที่ผิด
ประการที่สองอยู่ที่การ decompress จุด การกู้ค่า affine x จากพิกัด projective ต้องใช้การคูณหนึ่งครั้งด้วย inverse ของ Z การคูณด้วย inverse ยกกำลังสองให้ค่าที่ยังเป็นรูป projective ที่ถูกต้อง แต่เป็นพิกัด affine ที่ผิด อาการจึงเป็น y ถูกแต่ x ผิด ไม่ว่าเมื่อไรที่พิกัดหนึ่งถูกและอีกตัวผิด บั๊กอยู่ที่การ normalize ไม่ใช่ที่เลขคณิต
ประการที่สามคือนิสัยที่ติดมาจากเส้นโค้งที่สั้นกว่า ทั้ง scalar ประจำลายเซ็นและ challenge scalar ต้องถูก reduce จาก digest เต็มซึ่งของ Ed448 คือ 114 ไบต์ ไม่ใช่จาก 57 ไบต์แรก เส้นโค้ง 32 ไบต์ก็ใช้ digest เต็ม 64 ไบต์เช่นกัน กฎจึงเป็นไปในทิศเดียวกัน สิ่งที่ผิดมีเพียงสมมติฐานที่ว่า "ครึ่งหนึ่งของ digest คือความกว้างของ scalar" เท่านั้นเอง
ประการที่สี่คือลำดับ domain separation prefix ต้องมาก่อน ทั้งก่อน context prefix และก่อนข้อความ ซึ่งไม่ใช่ลำดับที่การอ่าน R และ A ในสเปกด้วยสัญชาตญาณจะบอก ทำผิดจุดนี้จะได้ลายเซ็นที่ตรวจผ่านกับ implementation ของตัวเองเท่านั้น และกับอย่างอื่นไม่ผ่านเลย ซึ่งเป็นความล้มเหลวที่หลอกลวงที่สุดเท่าที่จะเป็นได้
// การออกแบบ carry ระดับ field: propagate ด้วย semantics แบบ floor ล้วน
// เพื่อให้ limb ทั้งบวกและลบใช้ได้ และการลบไม่ต้องเติม bias
// carry ตัวบนพับกลับผ่าน 2^448 = 2^224 + 1 (mod p) ซึ่งแตะ limb 0
// และ limb 8 จำกัดที่สี่รอบ ในทางปฏิบัติพบแค่สองรอบ
procedure FeCarry(var A: TFe448);
var
I, Round: Integer;
Carry: Int64;
begin
for Round := 1 to 4 do
begin
Carry := 0;
for I := 0 to 15 do
begin
A[I] := A[I] + Carry;
Carry := Floor28(A[I]); // floor ไม่ใช่ truncation
A[I] := A[I] - (Carry shl 28);
end;
if Carry = 0 then
Break;
A[0] := A[0] + Carry; // 2^448 == 1
A[8] := A[8] + Carry; // 2^448 == 2^224
end;
end;เวอร์ชันก่อนหน้าของ routine นี้เติม bias ก่อน propagate แล้วในกรณีอินพุตขนาดใหญ่ มันพับ carry ปลอมที่มีขนาดผิดเข้าไปอยู่ใน limb ต่ำ ๆ scheme แบบใช้ bias เป็นแหล่งเกิดข้อบกพร่องชั้นนี้อย่างต่อเนื่อง ส่วน floor semantics ที่วนซ้ำแบบมีขอบเขตให้เหตุผลที่ตามง่ายกว่า และเร็วพอโดยวัดได้จริง
สาเหตุรากสองประการใน Brainpool
ประการแรกไม่ใช่เรื่อง cryptography เลย รูปแบบที่ใช้ทำงานคือ 33 limb ผลคูณของค่าสองตัวจึงต้องการ 66 แต่อาร์เรย์ผลคูณถูกประกาศไว้ที่ 64 การเขียนเกินปลายแถวทำให้หน่วยความจำข้างเคียงเสียหาย ซึ่งปรากฏอาการแรกเป็นผลลัพธ์ผิด และกลายเป็น crash เมื่อเพิ่มการสแกนที่กว้างขึ้นเท่านั้น กฎที่ได้มาจากเรื่องนี้สมควรใช้กับบัฟเฟอร์ตัวเลขขนาดตายตัวทุกตัว: กำหนดขนาดจากความกว้างผลคูณในกรณีแย่ที่สุดแล้วบวก margin เพิ่ม จากนั้นไม่ต้องกลับมาคิดถึงมันอีก อาร์เรย์ในโค้ดที่ส่งมอบมีขนาด 68 limb
ประการที่สองคือรูปทรงการยกกำลังที่เข้ากันผิด มี square-and-multiply ที่ถูกต้องอยู่สองแบบ และทั้งสองกินเลขชี้กำลังจากคนละทิศ: แบบ right-to-left คูณแล้วยกกำลังสองฐาน และต้องอ่านบิตจากปลาย least significant ขณะที่แบบ left-to-right ยกกำลังสองแล้วคูณ และอ่านจากปลาย most significant ลูป modular inversion กลับมีเนื้อคู่แบบ right-to-left แต่เดินบิตแบบ most-significant-first ทั้งสองส่วนเป็นของที่มีในตำรา แต่การประกอบเข้าด้วยกันไม่ใช่ ผลลัพธ์คือ inverse ที่ผิดแต่ยังดูเหมือน field element ที่หาได้จริง
// การเทียบเท่าและการบวกแบบ Jacobian ในกรณีที่ record ปลายทางอาจเป็น
// ตัวแปรเดียวกับต้นทาง การ copy ทั้ง record ไว้ตอนเริ่มคือการป้องกัน
// ที่เชื่อถือได้เพียงหนทางเดียว: การเขียน limb ของ R ทำให้การอ่าน
// P ในภายหลังเสียหาย
procedure BPPointDouble(var R: TBPPoint; const P: TBPPoint;
const Curve: TBPCurve);
var
Pin: TBPPoint;
begin
Pin := P; // copy ก่อน แล้วคำนวณจาก Pin เท่านั้น
// ... M = 3X^2 + A*Z^4, S = 4*X*Y^2, X3 = M^2 - 2S, ...
end;บทเรียนเชิงกระบวนการสองข้อที่แพงกว่าบั๊กทั้งหมด
การแก้ด่วนทีละนิดไม่มีวันลู่เข้าสู่จุดสมบูรณ์ของยูนิตเข้ารหัสหรอก ดราฟต์หนึ่งถูกแพตช์ซ้ำไปมาจนสะสม routine ซ้ำซ้อนถึง 32 ตัวและโครงสร้างที่เสียหาย และถูกแก้ได้ก็ด้วยการเขียนใหม่ทั้งหมดเท่านั้น รูปแบบที่ควรยึดคือเขียนครั้งเดียวจาก mirror ที่ผ่านการตรวจสอบแล้ว หรือไม่ก็เขียนใหม่เลย การซ่อมท้องถิ่นต่อเนื่องกับเลขคณิตที่คุณยังไม่เข้าใจจะสะสมความผิดเร็วกว่าที่มันจะแก้คืนได้
และให้เช็ก timestamp ของ executable ก่อนเชื่อผลทดสอบ การ build แบบ incremental ที่คอมไพล์ผ่านแต่ไม่ relink จะรันไบนารีตัวเดิม ซึ่งเคยปั่นเกมไล่ทางผิดทั้งรอบเรื่อง probe ที่หายไปและผลลัพธ์ซ้ำซ้อนขึ้นมาทั้งดวง ตอนดีบักงานเข้ารหัส ผลลัพธ์ที่อธิบายไม่ได้ควรกระตุ้นคำถามว่า "นี่คือไบนารีที่เพิ่ง build หรือเปล่า" ก่อนคำถามว่า "อัลกอริทึมผิดหรือเปล่า"
ประสิทธิภาพ ขอบเขต และวิธีเรียกใช้
การ reduce แบบ modular ในยูนิต Brainpool เป็น shift-subtract ทีละบิตเริ่มจากบิตที่ตั้งไว้ตัวสูงสุดของผลคูณ การคูณหนึ่งครั้งจึงมีต้นทุนอยู่ในระดับเดียวกับความกว้างบิตโดยประมาณ การ verify ที่ P-256 ใช้เวลาอยู่ในระดับร้อยมิลลิวินาทีต่ำ ๆ ซึ่งธรรมดาดีสำหรับการลงนามหรือตรวจสอบเอกสาร และไม่พอสำหรับ TLS terminator Barrett reduction เป็นการอัปเกรดที่เห็นชัดและต้องการค่าทำงานที่กว้างกว่าที่รูปแบบปัจจุบันพาได้ จึงเป็นการเปลี่ยนที่ควรทำเมื่อ workload เรียกร้อง ไม่ใช่ทำล่วงหน้า
uses
PDFlibEd448, PDFlibBrainpool;
var
PublicKey, Signature: AnsiString;
Curve: TBPCurve;
R, S, PubX, PubY: TBPValue;
begin
// Ed448: PureEdDSA, SHAKE256 ภายใน, คีย์ 57 ไบต์
if Ed448PublicKeyFromSeed(Seed, PublicKey) and
Ed448Sign(DocumentDigest, Seed, Signature) then
Assert(Ed448Verify(DocumentDigest, PublicKey, Signature));
// Brainpool: caller เป็นผู้ส่ง nonce ประจำลายเซ็น นโยบาย nonce
// จึงยังอยู่กับแอปพลิเคชัน
Curve := BPLoadCurve(bpP256r1);
if BPKeyGen(PubX, PubY, PrivateD, Curve) and
BPSignFixedK(R, S, Hash, PrivateD, Nonce, Curve) then
Assert(BPVerify(R, S, Hash, PubX, PubY, Curve));
end;ให้สังเกตว่า entry point การลงนามของ Brainpool รับ nonce เข้ามาเป็นพารามิเตอร์แทนที่จะสร้างเอง นั่นคือการตัดสินใจอย่างมีสติ: การสร้าง nonce เป็นสิ่งที่ทำให้พังพินาศที่สุดเมื่อทำผิดใน ECDSA เพราะค่าที่ซ้ำหรือคาดเดาได้จะเปิดเผย private key การตัดสินใจว่าความสุ่มมาจากไหนจึงเป็นของแอปพลิเคชันและระบบ compliance ของมัน ไม่ใช่ของไลบรารี PDF
เส้นโค้งเหล่านี้อยู่เคียงข้างงาน post-quantum ที่เล่าไว้ในบทความ FIPS 204 ML-DSA และต่อเข้ากับท่อการลงนามและการตรวจสอบชุดเดียวกับที่ครอบคลุมไว้ในการลงนามและตรวจสอบ PAdES สำหรับใบรับรองทดสอบบนเส้นโค้งเหล่านี้ เส้นทางการสร้างในเครื่องอธิบายไว้ในใบรับรอง self-signed ด้วย CryptoAPI ตารางอัลกอริทึมฉบับเต็มระบุไว้บนหน้าผลิตภัณฑ์losLab PDF Developer Library