אריתמטיקת עקומות NIST בפסקל טהור לחתימת PDF

HotPDF מבצע הסכמת מפתחות על עקומה אליפטית ואימות חתימות עבור PDF ב-Object Pascal טהור, בלי קישור ל-OpenSSL ובלי ספק הצפנה של פלטפורמה בנתיב. זה מכסה חמש עקומות: P-256, P-384 ו-P-521 עבור משפחות הראשוניים של NIST, ועוד X25519 ו-X448 עבור הסכמת מפתחות על עקומות Montgomery. הסיבה לכתוב את הקוד הזה במקום לקשר אותו היא פריסה, לא טוהר. לאפליקציית Delphi או Free Pascal שמשלחת קובץ הרצה אחד ואף DLL של הצפנה אין סטיית גרסאות לנהל, אין ספק לפלטפורמה לזהות, ושום דבר לא משתנה בהתנהגות כשלקוח מתקן את ספריות המערכת שלו

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

למה ספריית PDF צריכה בכלל אריתמטיקת עקומות?

שתי תכונות גוררות זאת פנימה. הראשונה היא הצפנת מפתח ציבורי של מסמכים: מטפל רשימת הנמענים של ISO 32000 עוטף מפתח פר-מסמך עבור תעודות ממונות, וכשנמען מחזיק מפתח EC העטיפה רצה דרך הסכמת מפתחות ולא הובלת מפתח RSA. בלי ECDH אין דרך לפתוח מסמך כזה. השנייה היא אימות חתימות. אימות חתימת ECDSA על בייטי ה-/ByteRange דורש כפל נקודות על העקומה של החותם, ו-P-384 נפוץ בפרופילים ממשלתיים ושל חתימה מוסמכת שבהם P-256 נחשב לרצפה ולא ליעד. HotPDF חושף את תוצאות העבודה הזאת דרך נתיב אימות ה-ECDSA וה-CMS ודרך מודל ספקי החתימה הניתנים להחלפה

תרשים היכן נעשה שימוש באריתמטיקת העקומות הפסקלית הטהורה של HotPDF: הצפנת ECDH של רשימת נמענים ואימות חתימות ECDSA על ByteRange — הסכמת מפתחות פותחת מסמכים מוצפני EC עבור נמענים ממונים, בזמן שאימות חתימות צריך כפל נקודות על עקומת החותם

CIOS, והחיסור האחד בסוף

כפל Montgomery נמנע מחלוקה בעבודה במרחב מומר שבו ההפחתה היא הזזה. הגרסה ש-HotPDF משתמש בה היא Coarsely Integrated Operand Scanning, ששזרה את הכפל ואת ההפחתה limb אחר limb כך שהערך הביניימי לעולם לא גדל מעבר לרוחב המודולוס ועוד limb אחד. גוף הלולאה פשוט וקל לבדיקה. הזנב איננו: אחרי המעברים השזורים הצבר יכול להיות בכל מקום בטווח עד פי שניים מהמודולוס, ולכן האלגוריתם מסתיים בחיסור מותנה שמסיר עותק אחד של הראשוני אם ורק אם הצבר גדול או שווה לו

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

// שגוי: P[I] + Borrow עשוי להתקפל כש-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;

איך נראה בפועל התקפלות borrow?

הוא נראה כעקומה שעובדת בכל מקום חוץ מבייצור. הראשוניים של P-384 ושל P-521 מכילים limbs שכולם אחדים, כך ש-P[I] שווה $FFFFFFFFFFFFFFFF. מוסיפים אליו borrow נכנס של אחד ושלם ללא סימן בן 64 ביט מתקפל לאפס. ההשוואה אז שואלת האם limb הצבר קטן מאפס, מחליטה שאיננו, ומסיקה שאין צורך ב-borrow. limb אחד של התוצאה חורג באחד

תרשים התקפלות borrow בהפחתת Montgomery שמנגיד את השוואת ה-limb השגויה מול הפצת borrow נכונה באריתמטיקת P-384 של HotPDF — הוספת ה-borrow ל-limb שכולו אחדים מתקפלת לאפס, ולכן P-384 ו-P-521 מוותרות על החיסור בזמן ש-P-256 מסתירה את הפגם

P-256 נמלטת כי אף אחד מה-limbs שלה אינו כולם אחדים, ולכן החיבור לעולם לא גולש והביטוי הפגום מקרה תואם את הנכון. זו התוצאה הגרועה ביותר האפשרית עבור סביבת בדיקות: העקומה הנבדקת ביותר עוברת, הפחות נבדקות נכשלות לסירוגין בהתאם לערכי האופרנדים, והכשל עולה כתוצאת אימות של "חתימה בלתי תקפה" על מסמכים תקינים לחלוטין. HotPDF נשא שער מפורש על P-384 בדיוק מהסיבה הזאת, מחזיר סטטוס לא זמין במקום תשובה שגויה, עד שהאריתמטיקה הוכחה מול וקטורי ייחוס

איך הבאג אותר בפועל

לא על ידי קריאת הקוד. הרצף הפרודוקטיבי היה מכני, והוא ניתן לשימוש חוזר. ראשית, ביטול הקבועים: כל limb של p, R ו-R^2 הופק מחדש באופן עצמאי והושווה limb-ב-limb, מה ששולל את מקור באגי העקומות הנפוץ ביותר. שנית, הוספת מדידות לאריתמטיקה ולא ל-API: פרוצדורת dump זמנית הדפיסה את הערכים הביניימיים של כפל Montgomery של R^2, של x^3 ושל y^2 עבור נקודה ידועה, כך שאפשר היה לבדוק אותם מול אמת מחושבת באופן עצמאי

ההשוואה הזאת הצביעה ישירות על האשם. שרשרת ה-x הייתה נכונה מקצה לקצה, בזמן ש-y^2 שונה בבדיוק limb אחד בבדיוק באחד. הפרש של אחד ב-limb יחיד אינו באג כפל, באג הפצת carry או באג קבוע; זהו באג שרשרת borrow, ושרשרת ה-borrow היחידה בשגרה היא החיסור המותנה הסופי. פרט אחד כמעט סטה מהמסלול: הקבוע הייחוס ששימש ל-dump נכתב בעצמו בסדר בייטים שגוי בניסיון הראשון, מה שהפיק אי התאמה בערך ה-y ורמז לרגע קצר לפגם שני שאינו קיים. אמתו את סדר הבייטים של האמת שלכם לפני שאתם סומכים עליה להאשים את הקוד

תרשים זרימה של אופן איתור באג העקומות של HotPDF על ידי הפקת קבועים מחדש, הצפת ערכי ביניים של Montgomery והשוואה מול אמת המראה — הפרש של limb יחיד בדיוק באחד הצביע ישירות על שרשרת ה-borrow היחידה בשגרה, וייחוס עם בייטים הפוכים כמעט הסיט את הציד

המלכודות השכנות באותה שגרה

שלושה מצבי כשל נוספים חיים בתוך כמה שורות מאותה השוואה, וכל שלושתם היו חיים בשלב כלשהו במהלך הפיתוח

// 1. לצבר יש limb אחד מעל רוחב המודולוס. השוואת ה-L limbs
//    הנמוכים בלבד מפספסת את המקרה שבו 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. חיסור גנרי מרובה limb חשוף לאותה התקפלות: כש
//    Y[I] הוא $FFFFFFFFFFFFFFFF, Y[I] + Borrow מתקפל לאפס וה
//    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 ספרות הקסדצימליות במקום 131, F אחד חסר, והקבועים של Montgomery חושבו אז מאותו ראשוני שגוי, כך שהקבועים היו עקביים-עצמית ושגויים יחד. פרמטרי עקומה חייבים להיגזר, לעולם לא להקלד: חשבו את R כ-(1 shl (64 * L)) mod p מהראשוני שאתם באמת משתמשים בו, ואז צלבו את R * R mod p מול הערך שקבוע ה-R^2 שלכם טוען. זוג קבועים שמסכימים זה עם זה לא מוכיח דבר על אף אחד מהם

אסטרטגיית אימות שמתרחבת מעבר לעקומה אחת

הטכניקה שהפכה את X25519 ו-X448 לניתנים לניהול הייתה כתיבת מימוש מראה בשפה עם מספרים שלמים ללא הגבלה ותעתוק זרימת הבקרה של הפסקל אליה שורה-שורה. כשהמראה מפיקה את התשובה הנכונה והפסקל לא, הפגם הוא מעידת העתקה וחקירת אותו ערך ביניים בשני המימושים מוצאת אותו בשניות. כל שלושת הטעויות הקלאסיות של הסולם של RFC 7748 נתפסו כך: swap של זמן קבוע שהשורה השנייה שלו שימשה שוב את הערך המוחלף כבר, היפוך סופי שהחזיר את z בחזקת מינוס אחת במקום לכפול אותו אל X, וכפל בקבוע קטן שהרכיב מכפלות חצי-מילה עם bitwise or ואיבד את ה-carry

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

עם שרשרת ה-borrow מתוקנת, כל חמש העקומות תואמות וקטורי ייחוס מפורסמים בייט-בייט, ו-HotPDF כבר לא שוער אף אחת מהן. אם אתם משלבים חתימה מבוססת תעודות או הצפנה של רשימת נמענים, המסקנה המעשית היא שבחירת עקומה היא עכשיו החלטת מדיניות ולא שאלת יכולת; הפרופילים ומלכודות סדר הבייטים של צד החתימה מכוסים בההליכה על חתימת PAdES. פרטי הרכיב ומטריצת האלגוריתמים הנתמכים נמצאים בדף המוצר של HotPDF Delphi PDF component