פונקציית גיבוב קריפטוגרפית

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

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

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

פונקציית גיבוב קריפטוגרפית בטוחה מקיימת את התנאים הבאים:

1. בהינתן פלט מסוים, מציאת ערך קלט מתאים קשה מבחינה חישובית (Preimage).
2. בהינתן קלט כלשהו קשה חישובית למצוא קלט אחר המוביל לאותו פלט (Second preimage).
3. מציאת שני קלטים שונים המובילים לאותו פלט קשה מבחינה חישובית (התנגשות, Collision).

עמידות

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

פונקציית גיבוב קריפטוגרפית היא פונקציה חד-כיוונית $\ h : X \rightarrow Z$ המקיימת:

1. קושי היפוך (Preimage resistance) - לכל אלגוריתם הסתברותי: בהינתן פלט $\ z \in Z$, זמן הריצה הממוצע הנדרש למציאת מקור $\ x \in X$ המקיים $\ h(x)=z$ הוא $\ 2^{|Z|}$.
2. קושי במציאת מקור נוסף (Second-preimage resistance) - לכל אלגוריתם הסתברותי: בהינתן קלט $\ x \in X$, זמן הריצה הממוצע הנדרש למציאת קלט נוסף $\ x \neq x' \in X$ המקיים $\ h(x)=h(x')$ הוא $\ 2^{|Z|}$.
3. קושי במציאת התנגשויות (Collision resistance) - לכל אלגוריתם הסתברותי: מציאת שני משתנים מקריים $\ x_1, x_2 \in X$, כך ששניהם מובילים לאותו פלט ($\ h(x_1)=h(x_2)$) דורשת זמן ריצה ממוצע של $2^{\frac{|Z|}{2}}$. (זמן ריצה זה נובע מפרדוקס יום ההולדת) שני קלטים כאלה נקראים התנגשות (Collision) של הפונקציה.

כיוון שהפונקציה ממפה קלטים ארוכים לפלטים קצרים יותר, קיומן של התנגשויות הינו בלתי נמנע. במידה והפונקציה מקיימת את התכונה השלישית, ימופו בממוצע $2^{x-z}$ קלטים לכל פלט.

שיטות לגיבוב

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

מבנים נפוצים לפונקציות תמצות

באופן כללי התהליך מתבצע באופן הבא:

1. בשלב ההכנה הקלט $\ x$ מחולק ל-$\ t$ מקטעים בגודל $\ r$ סיביות, $\ x=x_1x_2...x_t$. במידת הצורך מרופד הערך האחרון באופן כלשהו (בדרך כלל באפסים) ולעתים מוסיפים (מסיבות של בטיחות) מקטע נוסף המייצג את אורך הקלט המקורי ללא הריפוד בסיביות. תוספת זו מכונה MD strengthening. תוספת זו הוכנסה לראשונה באלגוריתם MD4 של רונלד ריבסט.
2. כל מקטע $\ x_i$ מהווה קלט לפונקציה הפנימית $\ h$ (הנקראת גם פונקציית תמצות) המפיקה ערך ביניים $\ H_i$ בגודל קבוע שהוא תוצאת חישוב כלשהו על פלט הפונקציה הקודם $\ H_{i-1}$ בשילוב ערך המקטע הנוכחי (ערך האתחול $\ H_0$ נקרא Initializing Value או בקיצור IV). מבנה הפונקציה הפנימית ואופן שילוב הערכים משתנה גם הוא בהתאם לשיטה עליה בנוי האלגוריתם, (ראה תרשים). ערך הביניים $\ H_i$ נקרא משתנה סבב (Chaining Value). דהיינו $\ H_i=h(H_{i-1},x_i)$. פעולה זו מתבצעת שוב ושוב עד לעיבוד כל המקטעים וקבלת פלט סופי $\ H_t$.
3. לבסוף פונקציית פלט אופציונלית $\ g$ ממירה את הפלט האחרון לתוצאה הסופית $\ h(x)$.

לסיכום האלגוריתם נראה כך:

$\ H_0=IV, H_i=h(H_{i-1},x_i), 1 \le i \le t; h(x)=g(H_t)$

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

יישומים

אימות אמינות או נכונות של מסר

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

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

סיסמאות

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

מחולל מספרים פסאודו-אקראי

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

משפחת הפונקציות ‎(Secure Hash Algorithm) SHA

במטרה ליצור תקן של פונקציות גיבוב קריפטוגרפיות פרסם ארגון ה-NIST האמריקאי את תקן ה-SHA המאושר לשימוש על ידי גופי ממשל בארצות הברית. בשנת 1993 פורסמה הראשונה מבין הפונקציות במשפחה שנקראה SHA-0 (שנקראה בתחילה SHA אך לאחר מכן הוסף לה מספר סידורי כדי להבדילה מגרסאות מאוחרות יותר). הפונקציה הוחלפה בשנת 1995 בפונקציה SHA-1 עקב חולשות שנתגלו בה. SHA-1 דמתה ל-SHA-0 בשינויים קלים. שתי הפונקציות מבוססות על אלגוריתם תמצית מסרים של רונלד ריבסט MD5, פועלות בשיטת מרקל-דמגרד ומפיקות פלט באורך 160 סיביות.

בשנת 2002 פרסם NIST את משפחת הפונקציות הבאה, SHA-2, המורכבת מארבע פונקציות המפיקות פלטים באורכים 224, 256, 384 ו-512 סיביות. בניגוד ל-SHA-1 טרם נתגלו חולשות משמעותיות ב-SHA-2 והיא נחשבת עדיין בטוחה. אך עקב העובדה שהמבנה שלה דומה ל-SHA-1 מעריכים מומחים שהפונקציה תפסיק להיות בטוחה בקרוב.

משפחת פונקציות הגיבוב SHA הינה סדרת פונקציות גיבוב ייעודיות המבוססות על הידע שנצבר בעקבות המצאת סדרת האלגוריתמים MD (תמצית מסרים). פונקציות אלו נבנו תוך שימת דגש על פיזור אחיד של כל סיביות המסר באופן כזה שלכל חלקי המסר תהיה השפעה על הפלט. הפונקציות משתמשות בפעולות פשוטות כמו XOR, Shift ו-Rotate הבנויות כסדרה של פונקציות לוגיות המקבלות שלושה ערכים ומפיקות ערך אחד בגודל קבוע. כאשר ב-SHA1 וכן SHA256 הערכים בגודל מילה (32 סיביות) ואילו ב-SHA384 ו-SHA512 הערכים בגודל מילה כפולה (64 סיביות). ההבדל העיקרי בין הפונקציות השונות במשפחה הוא בכמות סיביות הפלט וערכי האתחול (IV).

בנובמבר 2007 השיק NIST תחרות לפונקציות גיבוב קריפטוגרפיות בטוחות, בדומה לתחרות שהתקיימה לצופני גושים שבה זכה AES. בחירת האלגוריתם המנצח, שייקרא SHA-3, מתוכננת לשנת 2012. האלגוריתם שייבחר יחליף את משפחת האלגוריתמים SHA בתקן ההצפנה האמריקאי.‏‏

לקריאה נוספת

• Douglas R. Stinson, Cryptography, Theory and Practice, CRC press, 1995. ISBN 0-8493-8521-0