Ed448 ו-Brainpool ECDSA בפסקל טהור ל-PDF

PDFlibPas חותם ומאמת באמצעות Ed448 ובאמצעות שלוש עקומות ה-ECDSA של Brainpool ב-Object Pascal טהור. בלי ספריית הצפנה חיצונית, בלי ספק פלטפורמה, בלי DLL: PDFlibEd448 מממש את PureEdDSA של RFC 8032 על edwards448, ו-PDFlibBrainpool מממש את brainpoolP256r1, brainpoolP384r1 ו-brainpoolP512r1 של RFC 5639. שתיהן נבנו באותה דרך, מול וקטורי בדיקה ידועי-תשובה שהופקו באופן עצמאי לפני שנכתב שורת פסקל אחת, ושתיהן ראויות לכתיבה בעיקר בזכות הבאגים

אריתמטיקת שדות היא קוד כנה במיוחד. היא או תואמת וקטורים מפורסמים בייט-בייט או שאינה תואמת, ולכן אין מקום ל"עובד ברובו". מה שמקשה הוא שמימוש שגוי עדיין מפיק חתימות, עדיין מאמת את החתימות שלו עצמו ועדיין נראה הגיוני לחלוטין

למה דווקא העקומות האלה, ולמה דווקא בפסקל

עקומות Brainpool מופיעות בפרופילי חתימה מוסמכת אירופיים, ולכן ספרייה שחותמת מסמכים לשוק הזה לא יכולה להתייחס אליהן כאל תחום נישה. Ed448 נכלל בקבוצת האלגוריתמים ש-ISO/TS 32002 מביאה ל-PDF, ושם התקציר הפנימי שלה הוא SHAKE256 ולא SHA-2. אף אחת משתי המשפחות אינה זמינה בספריות ההצפנה לפסקל הנפוצות, ולכן ספריית PDF שרוצה אותן חייבת להחזיק בהן בעצמה

הטיעון של הפריסה זהה לזה שחל על כל ההצפנה של הספרייה הזאת: אפליקציה שמספקת קובץ הרצה אחד ללא תלות בהצפנה אינה צריכה לאתר ספק, אינה צריכה להתאים גרסה ואין לה התנהגות שמשתנה כשהמארח מתוקן. חתימה היא בדיוק התחום שבו תלות ניידת היא הדבר האחרון שרוצים

קבועים מגיעים מטקסט המפרט, לעולם לא מהזיכרון

הניסיון הראשון לנקודת הבסיס של edwards448 נכתב מהזיכרון והיה שגוי. זו לא טעות יוצאת דופן והיא כן טעות יקרה מאוד, כי נקודת בסיס שגויה מפיקה מערכת עקבית-עצמית: יצירת המפתחות, החתימה והאימות שלכם מסכימים זה עם זה וחולקים על כל שאר העולם

נוהל העבודה הוא לקחת כל פרמטר דומיין מטקסט המפרט ואז לאמת בצליבה. עבור edwards448 הכוונה למספר הראשוני, לקבוע העקומה, לסדר החבורה ולשתי קואורדינטות העשרון של נקודת הבסיס מתוך RFC 8032, בהמרה לייצוג ה-limb הפנימי, ואז בדיקה מול וקטורי בדיקה מפורסמים מאותו מסמך. עבור עקומות Brainpool הכוונה לפרמטרים מ-RFC 5639, למימוש עצמאי שנכתב כדי להפיק וקטורים, ולצליבת בדיקה מול ספריית מערכת בשני הכיוונים לפני שרץ שורת פסקל אחת

קיצור דרך אחד בגזירה ראוי לאזהרה כי הוא נראה אוניברסלי ואיננו: שחזור נקודת הבסיס מערך y קבוע עובד עבור העקומה של 25519 ואינו עובד עבור edwards448, שבה לערך הזה אין שורש ריבועי. סקריפט הפריך זאת תוך שניות, וזה הרבה זול יותר מגילוי דרך דיבאגר

השיטה: מימוש מראה ברמת limb לפני שורת פסקל אחת

הטכניקה שהפכה את שתי היחידות לניתנות לניהול היא מימוש מראה בשפה עם מספרים שלמים ללא הגבלה, שנבנה מלמטה למעלה. קודם שכבת האריתמטיקה בלבד: כפל שדה, חיסור והפצת carry, בבדיקות עומס מול האינווריאנטות האלגבריות שלהן על כמה מאות מקרים אקראיים. אחר כך יצירת המפתחות המלאה בתוך המראה, ושם חיים הבאגים הסמנטיים ושם הם זולים לגילוי. רק אז התעתוק לפסקל

התשואה היא אבחונית יותר מאשר התפתחותית. ברגע שהמראה ידועה כנכונה, כל חוסר התאמה בין המראה לפסקל הוא מעידת העתקה, ובדיקה של אותו ערך ביניים בשני המימושים מאתרת אותה מיד. זה הופך סוג של באג שאחרת כמעט בלתי ניתן לניפוי, limb שגוי אחד עמוק בתוך כפל סקלרי, להשוואה של חמש דקות

ארבע סיבות שורש ב-Ed448

כל ארבעתן התגלו בחקירת ערכי ביניים, וכל ארבעתן מהסוג שמפיק פלט שנראה תקין

הראשונה היא מלכודת סימון. רוב הנוסחאות המפורסמות לחיבור Edwards האחיד מניחות קבוע עקומה של מינוס אחד, ול-edwards448 יש פלוס אחד. כשמעבירים זאת ללא שינוי, המונה של קואורדינטת y נכתב כסכום כאשר הוא אמור להיות הפרש. התיקון אינו לסתום את הסימן אלא לגזור מחדש את הצורה המכפלתית חסרת ההיפוך מחוק החיבור האפיני של העקומה הנכונה, מה שמפיק את ארבעת הביטויים הקואורדינטיים ולא משאיר מקום לסימן שיורש ממקור שגוי

השנייה היא בפריקת נקודות. שחזור ה-x האפיני מקואורדינטות פרויקטיביות דורש כפל אחד בהופכי של Z. כפל בהופכי בריבוע מניב ערך שעדיין ייצוג פרויקטיבי תקין והוא קואורדינטה אפינית שגויה, ולכן התסמין הוא y נכון עם x שגוי. בכל פעם שקואורדינטה אחת נכונה והאחרת לא, הבאג הוא בנרמול ולא באריתמטיקה

השלישית היא הרגל שיובאה מהעקומה הקצרה. גם הסקלר הפר-חתימה וגם הסקלר האתגר חייבים להיות מופחתים מהתקציר המלא, שהוא ל-Ed448 בן 114 הבייט, ולא מ-57 הראשונים שלו. עקומת 32 הבייט משתמשת גם היא בכל התקציר שלה בן 64 הבייט, ולכן הכלל עקבי; רק ההנחה ש"חצי מהתקציר הוא רוחב הסקלר" שגויה

הרביעית היא סדר. קידומת הפרדת הדומיין באה ראשונה, לפני קידומת ההקשר וההודעה, וזה אינו הסדר שהקריאה האינטואיטיבית של R ו-A במפרט מרמזת עליו. טעות בזה מפיקה חתימות שמאומתות מול המימוש שלכם ומול שום דבר אחר, וזה הכישלון המטעה ביותר האפשרי

// תכנון carry של שדה: הפצה בסמנטיקת 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, לא חיתוך
      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;

גרסה מוקדמת יותר של השגרה הזאת החילה bias לפני ההפצה, ובקלטים גדולים היא קיפלה carry מזויף בגודל שגוי אל ה-limb הנמוכים. סכמות carry מבוססות bias הן מקור מתמשך למחלקת פגמים כזאת; סמנטיקת floor עם לולאת חזרה חסומה קלה יותר להבנה ומהירה מספיק במדידה

שתי סיבות שורש ב-Brainpool

הראשונה אינה קריפטוגרפיה כלל. הייצוג העובד הוא 33 limb, ולכן המכפלה של שני ערכים דורשת 66, והמערך של המכפלה הוכרז עם 64. כתיבה מעבר לסוף שחתה זיכרון סמוך, מה שהתגלה קודם כתוצאות שגויות והפך לקריסה רק אחרי הוספת סריקה רחבה יותר. הכלל שיצא מזה ראוי ליישום על כל חוצץ מספרי בגודל קבוע: קבעו את הגודל לפי רוחב המכפלה במקרה הגרוע והוסיפו שוליים, ואז אל תחשבו על זה שוב. המערך בקוד המשולח הוא 68 limb

השנייה היא צורת העלאה לחזקה מבולבלת. יש שתי צורות square-and-multiply נכונות והן צורכות את המעריך בכיוונים מנוגדים: הצורה מימין לשמאל כופלת ואז מעלה את הבסיס בריבוע וחייבת לקרוא ביטים מהקצה הפחות משמעותי, ואילו הצורה משמאל לימין מעלה בריבוע ואז כופלת וקוראת מהקצה המשמעותי ביותר. לולאת ההיפוך המודולרי החזיקה גוף מימין לשמאל עם מהלך ביטים מהמשמעותי ביותר קודם. שני החלקים ספרות לימוד, השילוב איננו, והתוצאה היא הופכי שגוי שעדיין נראה כאיבר שדה סביר

// כפילה וחיבור של Jacobian כאשר רשומת היעד עשויה להיות
// אותו משתנה כמו המקור. העתקת רשומה שלמה בכניסה היא
// ההגנה האמינה היחידה: כתיבת ה-limb של R מזהמת קריאות מאוחרות של P
procedure BPPointDouble(var R: TBPPoint; const P: TBPPoint;
  const Curve: TBPCurve);
var
  Pin: TBPPoint;
begin
  Pin := P;        // קודם העתקה, ואז חישוב מ-Pin בלבד
  // ... M = 3X^2 + A*Z^4, S = 4*X*Y^2, X3 = M^2 - 2S, ...
end;

שני לקחי תהליך שעלו יותר מהבאגים

תיקוני חם מצטברים אינם מתכנסים עבור יחידה קריפטוגרפית. טיוטה אחת תוקנה שוב ושוב עד שנשאה 32 שגרות משוכפלות ומבנה פגום, והיא תוקנה רק בכתיבה מחדש. התבנית לאמץ היא או לכתוב פעם אחת ממראה מאומתת או לכתוב מחדש; רצף של תיקונים מקומיים לאריתמטיקה שעדיין אינכם מבינים מצטבר מהר יותר משהוא מתקן

ובדקו את חותמת הזמן על קובץ ההרצה לפני שאתם מאמינים לתוצאת בדיקה. בנייה מצטברת שמהדרת אבל לא מקשרת מחדש מריצה את קובץ ההרצה הקודם, מה שייצר סבב שלם של מסלולי שווא על חיישנים חסרים ופלט משוכפל. בניפוי באגים של קריפטוגרפיה, תוצאה שאינה מוסברת צריכה לעורר את השאלה "האם זה קובץ ההרצה שבניתי זה עתה" לפני "האם האלגוריתם שגוי"

ביצועים, היקף ואופן הקריאה

הפחתה מודולרית ביחידת Brainpool היא חיסור-הזזה סדרתי-ביט מהביט הדלוק הגבוה של המכפלה, ולכן כפל עולה בסדר גודל של רוחב הביט. אימות P-256 נופל במאות הנמוכות של המילישניות, מה שמובן מאליו לחתימה או אימות של מסמכים ויהיה בלתי מספק עבור מסיים TLS. הפחתת Barrett היא השדרוג המובן והיא דורשת ערך עבודה רחב יותר ממה שהייצוג הנוכחי נושא, ולכן זה שינוי לביצוע כשעומס עבודה דורש אותו ולא מראש

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: הקורא מספק את ה-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;

שימו לב שנקודת הכניסה לחתימה של Brainpool מקבלת את ה-nonce במקום לייצר אותו. זה מכוון: יצירת nonce היא הדבר הקטסטרופלי ביותר לטעות בו ב-ECDSA, כי ערך חוזר או ניתן לחיזוי חושף את המפתח הפרטי, וההחלטה מאיפה מגיעה האקראיות שייכת לאפליקציה ולמשטר התאימות שלה, ולא לספריית PDF

העקומות האלה מתלוות לעבודת הפוסט-קוונטום המתוארת במאמר FIPS 204 ML-DSA, והן מתחברות לאותה צינורית חתימה ואימות המכוסה בחתימה ואימות PAdES. עבור תעודות בדיקה על העקומות האלה, נתיב היצירה המקומי מתואר בתעודות חתומות-עצמי עם CryptoAPI. מטריצת האלגוריתמים המלאה מופיעה בדף המוצר של losLab PDF Developer Library