חתימה דיגיטלית מבוססת פונקציית גיבוב

חתימה דיגיטלית מבוססת פונקציית גיבוב היא שם כולל לשיטות חתימה דיגיטלית חד-פעמית אשר ביטחונן מסתמך אך ורק על פונקציית גיבוב קריפטוגרפית ולא על קושיין המשוער של בעיות מתורת המספרים או בעיות אחרות שאין לגביהן הוכחה מתמטית שהן קשות. פונקציות גיבוב קיימות ונחקרות מזה זמן רב ואף שברובן עשויות אד הוק הן עדיין נמצאות בשימוש מעשי נרחב, נחשבות לבטוחות ומעולם לא נפרצו (דוגמאות הן SHA-2, BLAKE, SHA-3 או Skein). בנוסף הדעה הרווחת לגבי מרביתן, אם כי זה לא הוכח, שהן פוסט-קוונטיות. כלומר גם בהינתן מתקיף המצויד במחשב קוונטי לא יוכל לפרוץ את האלגוריתם, כלומר לא ימצא התנגשות בזמן פולינומי. חתימה מבוססת גיבוב בדרך כלל מהירה ובטוחה מאוד והיא נחשבת כיום לתשובה האטרקטיבית ביותר נגד קריפטואנליזה קוונטית כאשר היא תהיה רלוונטית.

חסרונות חתימה דיגיטלית מבוססת גיבוב הן; אורך החתימה גדול מהמקובל בתקנים המעשיים וכן היא חד-פעמית, מסיבה זו היא נקראת "תלוית זיכרון" (stateful), יש צורך לנהל מעקב גם על ידי החותם וגם על ידי המאמת באמצעות מונה כלשהו, כדי לדעת כיצד לחתום או איך לאשר את החתימה על מסמך נתון. זהו מצב בלתי אפשרי במקרה הגרוע או שאינו נוח למימוש מעשי במקרה הטוב. תאורטית ידוע שאפשר לבנות חתימה דיגיטלית מבוססת פונקציית גיבוב נטולת זיכרון (stateless). נושא המחקר העיקרי כיום הוא להפוך פונקציה כזו לאלגוריתם פרקטי, שניתן יהיה לחתום באופן מאסיבי על מסמכים רבים כמעט ללא הגבלה ועם חתימות באורך סביר. כך שניתן יהיה להציעה כחלופה מיידית לאלגוריתמים המקבילים בתקנים הבינלאומיים ללא שינויים מרחיקי לכת במערכת.

רקע

הרעיון להשתמש בפונקציית גיבוב (או בכל פונקציה חד-כיוונית) לצורך חתימה דיגיטלית עלה לראשונה על ידי לזלי למפורט שהמציא ב-1979 את חתימת למפורט. חתימת למפורט היא חד-פעמית במובן שכל זוג מפתחות; מפתח חתימה/מפתח אימות ניתנים לשימוש רק פעם אחת. כדי להדגים זאת, נניח שאליס מעוניינת להעביר לבוב מסר פשוט "כן" או "לא" ('0' או '1'), באופן כזה שהוא ידע בוודאות שההוראה הגיעה ממנה ולא ממתחזה. דרך אחת לפתור את הבעיה, תחילה אליס בוחרת פונקציה חד-כיוונית בלתי הפיכה מוסכמת (כלומר ידועה לכל), בוחרת $x$ אקראי כלשהו ומשתמשת בה כדי לחשב את $y=f(x)$ ושומרת בסוד את $x$. היא שולחת לבוב את $y$ כהתחייבות וכן מסכמת איתו מראש שעבור המסר "כן" אליס תחשוף בפניו את הסוד $x$ כהוכחה, אחרת המסר יהיה "לא". לאחר מכן נניח שאליס שלחה לבוב את $x$. בוב בודק שמתקיים $y=f(x)$ ואם כן הרי שההוראה "כן" הגיעה מאליס ולא מאף אחד אחר, משום שבעצם ידיעת $x$ אליס הוכיחה שהמסר הגיע ממנה. מעצם ההגדרה של הפונקציה יהיה קשה מאוד למי שאינו יודע מהו $x$ לנחש ערך כזה המקיים $y=f(x)$.

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

עץ מרקל

ערך מורחב – עץ מרקל

רלף מרקל הראה שאפשר להקטין את המפתח האימות בדרך מקורית, במקום לשלוח עבור כל מסר $y$ אחר, אפשר להשתמש בעץ גיבוב שהוא עץ בינארי מושלם בגובה $h$ שבו כל צומת היא גיבוב של שני הצמתים הבנים מהעלים ועד לשורש העץ. מפתח האימות יהיה שורש העץ איתו יהיה אפשר לאמת עד $2^{h}$ מסמכים המקבילים ל-$2^{h}$ העלים, כל עלה הוא חתימה חד-פעמית של מסמך אחד. האימות נעשה על ידי בדיקת המסלול מהעלה ועד לשורש העץ. כל עלה מאומת על ידי חתימה חד-פעמית (OTS) שכוללת בתוכה גם מידע הנקרא "מסלול אימות" (authentication path) שהוא בעצם ערכם של עלים אחים לאורך המסלול מהעלה לשורש העץ על מנת לאפשר בניית מסלול אימות. בדרך זו אפשר להפוך חתימה חד-פעמית לחתימה "רב פעמית" חלקית, כי בעוד שנדרשים מפתחות חתימה שונים עבור כל המסמכים, הרי שנדרש מפתח אימות אחד בלבד.

עץ מרקל מהווה שיפור משמעותי אך למרות זאת אינו פרקטי מכמה סיבות:

• היות שמדובר בחתימה חד-פעמית המפתח הפרטי עדיין חייב להיות שונה עבור כל מסמך, לכן החותם צריך לאחסן בזיכרון את כל מפתחות החתימה במקום שמור.
• מספר החתימות מוגבל למספר העלים בעץ, עבור עץ בגובה $h$ אפשר לחתום על לכל היותר $2^{h}$ מסמכים.
• על מנת להבטיח שכל עלה מנוצל רק פעם אחת יש צורך לנהל מעקב אחרי חתימות שבהן כבר השתמשו ואת המונה יש צורך לכלול בחתימה. דרישה זו עלולה להיות בעייתית במיוחד אם ארעה תקלה ונמחקו נתונים ואבד המונה.
• החתימה מתנפחת בסדר גודל לוגריתמי כי יש צורך לשלוח מלבד החתימה $h$ ערכי גיבוב נוספים על מנת לאפשר למאמת לבנות מסלול אימות מהמסמך לשורש המצוי בידו.

כדי לפתור את הבעיות האמורות הוצעו מספר שיפורים. הראשון הוא חלוקת העץ לתת-עצים. למשל אם העץ מכיל יער של $d$ שכבות של עצים המסודרים בערמה זה על גבי זה, כל אחד בגובה $h_{1}$, במהלך החתימה על מסר נתון החותם משתמש רק בעץ אחד מתוכם. במקרה כזה המפתח הציבורי עבור $2^{h_{1}}$ מסרים יקטן ל-$h_{1}$ ערכים לכן החתימה מצטמצמת מ-$O(2^{h})$ ל-$O(d2^{h/d})$. בנוסף אפשר לצמצם את החתימה על ידי ניצול העובדה שהיא סדרתית. כלומר שימוש באלגוריתם חכם לחיפוש בעץ שמאפשר צמצום החתימה מ-$O(2^{h})$ ל-$O(h)$. שילוב שני הרעיונות יחד מאפשר לצמצם עוד את החתימה ל-$O(h/d)$.

עץ מרקל זכה לשיפורים רבים כמו FMTseq שהוא עץ חיפוש פרקטלי של נאור, שנהב ואבישי וול, אלגוריתם Bleichenbacher-Mauer המשתמש בגרפים או אלגוריתם עץ מרקל המורחב XMSS המשתמש בתת-עצים רבים וכן אלגוריתם SPHINCS. בשני האחרונים נוסף אלמנט מיסוך. כלומר כל ערך מחובר ב-XOR עם מסכה אקראית כלשהי לפני הפעלת פונקציית הגיבוב. המחיר הוא עליה קלה בסיבוכיות אבל הרווח הוא גדול, כי אלגוריתם מרקל המקורי דורש שאורך החתימות יהיה $2n$ סיביות כדי להגיע לרמת ביטחון של $n$ סיביות בגלל התקפת יום הולדת. עם המסכה האקראית ניתן להגיע לביטחון של $b$ סיביות עם פרמטר $n=b$ שזהו שיפור בפקטור של חצי ביעילות האלגוריתם והפחתה דומה באורך החתימות.

חתימה דיגיטלית מוכחת כבטוחה נגד התקפת מסר נבחר

תיאור פונקציות המכילות את התכונה "Claw".

רעיון דומה לעץ מרקל הוצע ב-1984 על ידי שפי גולדווסר, סילביו מיקלי ורונלד ריבסט במאמר חשוב המדגים מהיבט תאורטי מוכח כיצד אפשר להשתמש בזוג פונקציות חד-כיוונית עם דלת מלכודת הנקראות "Claw Free" לחתימה דיגיטלית. פונקציות שנקראות Claw-free הן שתי פונקציות $f_{0},f_{1}$ שבלתי אפשרי למצוא $X$ ו-$Y$ כך שמתקיים $f_{0}(X)=f_{1}(Y)$ כמתואר בתרשים. הם הוכיחו שהשיטה שלהם בטוחה נגד "התקפת מסר-נבחר אדפטיבית" בהנחה שבעיית פירוק לגורמים היא בעיה קשה. אף על פי שהסכמה שלהם הודגמה עם פונקציית RSA הרי שאפשר לבנות חתימה כזו מכל פונקציה חד-כיוונית שעונה על התנאי האמור ולאו דווקא כזו המבוססת על פירוק לגורמים או לוגריתם בדיד.

התקפת מסר-נבחר אדפטיבית היא מודל ביטחון תאורטי החזק ביותר של פונקציית חתימה דיגיטלית. לפי מודל זה האויב או המתקיף רשאי לקבל מאורקל חתימות תקפות עבור מסרים כלשהם $m_{1},...,m_{k}$ לפי בחירתו ותפקידו לנסות לשבור את אלגוריתם החתימה על בסיס חתימות אילו וכן הוא רשאי לבקש חתימות נוספות גם לאחר שההתקפה החלה (מכאן הכינוי אדפטיבית). "שבירה" מחולקת לכמה רמות מהקל אל הכבד.

• שבירה מוחלטת (total break). מציאת דרך לגלות את המפתח הפרטי (דלת המלכודת הסודית) של החותם ואז לזייף בקלות חתימה על כל מסמך ולטעון שנחתם על ידי החותם הלגיטימי.
• זיוף כללי (universal forgery). מציאת דרך לעקוף את אלגוריתם החתימה כך שהתוקף מסוגל לדמות אותו ולזייף חתימות על מסמכים כלשהם מבלי לגלות את מפתח החתימה של החותם הלגיטימי.
• זיוף סלקטיבי (selective forgery). מציאת דרך לזייף חתימה על מסמך ספציפי אחד או יותר שנבחרו על ידי המתקיף.
• זיוף קיומי (existential forgery). זיוף חתימה על לפחות מסמך אחד כלשהו אפילו חסר משמעות ואפילו אם לתוקף אין שליטה על תוכנו.

ההגדרה האחרונה היא המחמירה ביותר ומבחינה תאורטית עדיף להגיע לסכמה שתהיה מוכחת כעמידה גם כנגד איום זה. הרעיון של אלגוריתם GMR הוא כדלהלן:

בהינתן שתי תמורות עם דלת מלכודת הנקראות Claw-free ופרמטר ביטחון $k$ יהיה קל לבחור באופן אקראי אלמנט מתחום הפונקציות, אך בהינתן תמורות כלשהן $f_{0},f_{1}$ יהיה קשה מבחינה חישובית למצוא $x,y$ כך שמתקיים $f_{0}(x)=f_{1}(y)$ ללא ידיעת דלת המלכודת. התכונה Claw-free משליכה גם על חד-כיווניות. למשל אם $n=pq$ כך ש-$p\equiv 3{\text{ (mod }}8)$ ו-$q\equiv 7{\text{ (mod }}8)$, אז הפונקציות $f_{0}^{n}(x)=x^{2}{\text{ (mod }}n)$ ו-$f_{1}^{n}(x)=4x^{2}{\text{ (mod }}n)$ הן תמורות חד-כיווניות ומתאימות להגדרה Claw-free, כמו כן מתקיים $f_{i}^{-1}(f_{i}(x))=x$ ודלת המלכודת היא המספרים הראשוניים $p$ ו-$q$. אם נתון $Q$ רק מי שמחזיק במידע הסודי שהוא דלת המלכודת יכול לחשב את הערכים $R,L\in n$ כך שמתקיים $f_{R}^{-1}(Q)=L$. תכונה זו נקראת "הוכחת אימות אטומית" של $L,R$ על ידי $Q$ כי רק מי שיכול להפוך את הפונקציה מסוגל לייצר את הערכים הללו מהערך $Q$ כך שהתנאי האמור יתקיים.

המפתחות הציבוריים לאימות החתימה על מסרים יהיו שני זוגות של תמורות חד-כיווניות $(g_{0},g_{1}),(f_{0},f_{1})$. המפתחות הפרטיים המשמשים לחתימה הם דלתות המלכודת של הפונקציות הללו כך שהחותם יכול באמצעותן לחשב את הפונקציות ההופכיות שלהן בקלות. כעת אם נתון המסמך $M_{j}$ תחילה החותם מייצר ומאמת מספר אקראי $R_{j}$ ואיתו הוא מאמת את $M_{j}$. את $R_{j}$ עצמו מאמתים בעזרת עץ אימות. מתחילים מ-$R_{0}$ שהוא שורש העץ שנקרא מפתח ציבורי ומכל נקודת אימות $R_{j}$ או $L_{j}$ בהתאמה אפשר לאמת שני ערכים חדשים במקרה של צד ימין $(L_{2j+1},R_{2j+1})$ ובמקרה של צד שמאל $(L_{2j},R_{2j})$. בדרך זו נוצר עץ שגדל כלפי מטה ככל שנדרשות יותר חתימות כמתואר בתרשים. כל צומת מאמת את הצמתים הבנים. מכל צומת נתון קיים "מסלול אימות משורשר" לשורש $R_{0}$. החתימה כוללת שני חלקים מלבד המסר עצמו.

• הערכים $R_{j}$ ו-$L_{j}$ המקיימים:

$L_{j}={\begin{cases}f_{R_{j}}^{-1}(L_{j/2}),&{\mbox{if }}j{\mbox{ is even}}\\f_{R_{j}}^{-1}(R_{j-1/2}),&{\mbox{if }}j{\mbox{ is odd}}\end{cases}}$

וכן המאמתים $A_{j}$ שרק החותם יכול היה לחשב, אך כל אחד יכול לבדוק בקלות. את המאמתים הוא בוחר כך:

$A_{j}={\begin{cases}(1,R_{1},L_{1}),&{\mbox{if }}j=1\\(j,R_{j},L_{j},A{\lfloor j/2\rfloor }),&{\mbox{if }}j>1\end{cases}}$

• פונקציית אימות אטומית של המסר $M_{j}$ על ידי $R_{j}$.

החתימה היא הערכים $(M_{j},A_{j},g_{m_{j}}^{-1}(R_{j}))$. ואימות החתימה מתבצע בשני שלבים, תחילה מאמתים את $R_{j}$ על ידי הפונקציות הציבוריות $f_{i}$ ואז מאמתים את המסמך על ידי הפונקציות $g_{i}$. לפיכך הזמן הדרוש לחישוב חתימה הוא $O(k)$ ואורכה הכולל הוא $O(\log(j)\cdot k)$ כאשר $k$ הוא פרמטר ביטחון המייצג את אורך החתימה בסיביות. שים לב שגם אלגוריתם GMR נקרא תלוי זיכרון כיוון שכל חתימה תלויה בחתימות קודמות (כל $R_{j}$ תלוי באימות שלו על ידי ערכים קודמים)

עץ אימות נטול זיכרון

ב-2004 הציע עודד גולדרייך שני שיפורים משמעותיים לאלגוריתם האמור כדי להופכו לאלגוריתם נטול זיכרון. ראשית הוא הציע שכל צומת (שאינו עלה) בעץ יכיל חתימה חד-פעמית על ערך הגיבוב של המפתח הציבורי של הצמתים הבנים שלו. המפתח הסודי יהיה גרעין התחלתי אקראי אשר ישמש לבניית העץ כולו באמצעות מחולל פסאודו-אקראי. מעצם הגדרתו של מחולל כזה אם מתחילים מגרעין התחלתי קבוע, תמיד יתקבל רצף זהה, עובדה זו מסייעת בשיחזור כל עלה רק כאשר הוא נדרש ואין צורך לבנות את כל העץ בזיכרון. שנית הוא הציע במקום לנהל מעקב אחרי החתימות שהשתמשו בהם באמצעות מונה כלשהו, לבחור עלה באופן שערכו נגזר מהמסר, מייצגים את ערך הגיבוב של המסר כמספר כלשהו באורך $n$ סיביות ואז המספר הזה משמש כאינדקס לבחירת העלה המתאים לחתימה. בשיטה זו חתימה אחת תכיל את כל המפתחות הציבוריים של כל החתימות החד-פעמיות של הצמתים במסלול מהעלה לשורש העץ, את כל המפתחות הציבוריים של הצמתים האחים לאורך המסלול וכן את החתימה החד-פעמית של המסר עצמו.

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

לסיכום מפתח החתימה הפרטי באורך $k$ סיביות, חישוב החתימה על המסמך דורש $2k$ מפתחות ו-$k$ חתימות. את מפתחות החתימה של כל הצמתים במסלול אין צורך לצרף לחתימה על המסמך כי אפשר לחשב אותם מהמפתחות הציבוריים. אך בכל זאת החסרון הוא שחתימה חד-פעמית אחת היא באורך $k^{2}$ מפתחות הציבוריים. שילוב של שיטת גולדרייך עם חתימת וינטרניץ מגיע לאורך חתימה של 1 מגה בית במקרה שפרמטר הביטחון הוא $k=256$.

אלגוריתם SPHINCS-256 משלב כמעט את כל הטכניקות המתוארות בנוסף לכמה שיטות חדשות כדי להפוך חתימה חד-פעמית לחתימה דיגיטלית רב-פעמית נטולת זיכרון ויעילה, עם ביטחון ברמה של $2^{128}$ ועם מפתחות באורך 1 קילו בית וחתימה באורך 41 קילו בית.

תקנים

NIST הכינו טיוטה לתקן חדש לחתימה דיגיטלית מבוססת גיבוב הנחשבת בטוחה נגד קריפטואנליזה קוונטית (כאשר הדבר יהיה רלוונטי), היא מהירה ויעילה המשלבת כמה רעיונות ביניהם ${\text{WOTS}}^{+}$ שהוא וריאציה של חתימת וינטרניץ, XMSS ו-${\text{XMSS}}^{MT}$. בהתבסס על הצעה של Mecgrew ו-Curcio.

הערות שוליים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

30248916חתימה דיגיטלית מבוססת פונקציית גיבוב