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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
סכמה כללית של פונקציית גיבוב

פונקציית גיבוב קריפטוגרפית היא פונקציית גיבוב חד-כיוונית הממירה קלט באורך שרירותי לפלט באורך קבוע, הנקרא קוד גיבוב (hash code) או ערך גיבוב (hash value). ערך הגיבוב משרת כייצוג קומפקטי של הקלט, או כאמצעי זיהוי ייחודי שלו, מעין טביעת אצבע דיגיטלית. יש נוהגים לכנותו תמצית-מסר (message digest) ועיקר השימוש בו הוא להוכחת שלמות ואימות. בניגוד לפונקציית גיבוב רגילה, פונקציית גיבוב קריפטוגרפית חייבת להיות חד-כיוונית במובן שבהינתן הפלט יהיה קשה מבחינה חישובית למצוא את קלט המקור שלו וכן כל שינוי אפילו קל ביותר בקלט יגרום בהסתברות גבוהה לשינוי משמעותי בפלט.

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

כמו פונקציית גיבוב קונבנציונלית הנפוצה ביישומי מחשב לא קריפטוגרפיים, תפקידה העיקרי הוא למפות תחום גדול לטווח קטן, אך הן נבדלות במספר היבטים חשובים. פונקציית גיבוב כללית מקבלת קלט באורך שרירותי ומפיקה פלט באורך קבוע. בניסוח פורמלי עבור התחום D והטווח R תמיד מתקיים h : D\rightarrow R, |D| > |R|. לפי עקרון שובך היונים העובדה שהפונקציה ממפה מקורות רבים לתמונות מעטות משמעה שבהכרח קיימות התנגשויות - זוג קלטים שמפיקים פלט זהה. בהנחה שפונקציית הגיבוב ראנדומלית, אם t הוא אורך הקלט בסיביות ו-n אורך הגיבוב בסיביות הרי שבמקרה הממוצע 2^{t-n} קלטים ימופו באופן זהה. במילים אחרות ההסתברות ששני מקורות ימופו לתמונה זהה היא  2^{-n} ללא תלות ב-t.


תכונות בסיסיות[עריכת קוד מקור | עריכה]

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

  1. קושי בהיפוך (preimage resistance); בהינתן פלט מסוים, מציאת הקלט המקורי שלו, קשה מבחינה חישובית. או בניסוח פורמלי, אם נתונה פונקציה היסתברותית כלשהי h והמקור x, מציאת x' כאשר x'\ne x כך שמתקיים y=h(x') היא משימה קשה.
  2. קושי במציאת מקור נוסף (2nd-preimage resistance); בהינתן קלט כלשהו יהיה קשה חישובית למצוא קלט אחר המוביל לאותו פלט, בניסוח פורמלי: בהינתן x, מציאת x' כאשר x'\ne x כך שיתקיים h(x)=h(x').
  3. קושי במציאת התנגשויות (collision resistance); מציאת שני קלטים שונים כלשהם המפיקים פלט זהה קשה מבחינה חישובית. בניסוח פורמלי מציאת מקורות x,x' כך שמתקיים h(x)=h(x'). שים לב שבניגוד להגדרה הקודמת שני הקלטים חופשיים ויכולים להיות כל ערך לפי בחירה.

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

סוגי פונקציות[עריכת קוד מקור | עריכה]

פונקציות גיבוב קריפטוגרפיות מתחלקות לשתי משפחות עיקריות:

  • פונקציית גיבוב ללא מפתח; נקראת גם modification detection code בקיצור MDC. תפקידה להוות ייצוג תמציתי של המסר כך שיהיה אפשר לחשוף כל שינוי אפילו קל ביותר בסבירות גבוהה. דוגמאות שימוש; הגנה על סיסמאות וחתימה דיגיטלית. בסיסמאות למשל הן אינן נשמרות במצב גלוי אלא רק ערך הגיבוב שלהן נשמר ובחתימה דיגיטלית מסיבות של יעילות, החתימה מתבצעת על תמצית מהמסר במקום על המסר עצמו.
פונקציית גיבוב ללא מפתח מוגדרת באופן כללי כך:
H : \{0,1\}^*\rightarrow \{0,1\}^n
הכוכבית מציינת שאורך המידע אינו קבוע ו-n הוא אורך התג בסיביות (למשל 160 סיביות ב-SHA-1 או 256 סיביות ב-SHA-2).
  • פונקציית גיבוב עם מפתח; נקראת גם message authentication code בקיצור MAC ומשמשת בעיקר לאימות מסרים. היא מוגדרת באופן כללי כך:
H : \{0,1\}^k \times \{0,1\}^*\rightarrow \{0,1\}^n
k הוא אורך המפתח בסיביות ויכול להיות בכל אורך שרירותי שמתאים לגודל הבלוק שפונקציית הגיבוב מקבלת. אפשר להפוך כל פונקציית גיבוב לפונקציית MAC עם מפתח. דרך אחת פשוטה היא על ידי XOR של מפתח סודי עם המסר לפני העברתו בפונקציית הגיבוב, כמו ב-HMAC.

התקפת יום הולדת[עריכת קוד מקור | עריכה]

פונקציה חד-כיוונית העמידה בפני התנגשויות (הגדרה 3) היא החזקה ביותר. המודל המקובל להגדרת קושי מבחינה חישובית הוא במונחים של סיבוכיות זמן. כלומר אם נתונה הפונקציה h : X \rightarrow Z, זמן הריצה האידאלי למציאת מקור (הפיכת הפונקציה) צריך להיות מסדר גודל של 2^{|Z|}. לעומת זאת זמן הריצה במקרה הגרוע למציאת התנגשות מתקצר משמעותית, רק \textstyle 2^{\frac{|Z|}{2}}. זאת בגלל התקפת יום הולדת שמבוססת על פרדוקס יום ההולדת. כדלהלן; בהינתן n שלמים אקראיים r_1,...,r_n מתוך הטווח H כאשר n=1.25\sqrt{H}, אזי ההסתברות ששני ערכים יהיו זהים גבוהה מחצי (בערך 1-e^{-n^2/(2H)}). במילים אחרות מספר הערכים שצריך לבדוק לפני שתמצא התנגשות הוא בערך \textstyle \sqrt{\frac{\pi H}{2}}. לדוגמה הסיכויים שיימצאו בחדר אחד שניים מתוך 23 אנשים שלהם יום הולדת זהה, הוא בערך 0.507 שזה באופן מפתיע גבוה מהאינטואיציה הראשונית ומסיבה זו נקרא 'פרדוקס'.

בהתקפת יום הולדת התוקף מנסה לנצל עובדה זו כדי למצוא התנגשויות על ידי חיפוש אקראי ובדיקה של זוגות ערכים בתקווה למצוא התנגשות וכאמור הסיכויים עולים ככל שנבדקים יותר ערכים. באופן כללי, עבור כל פונקציית גיבוב טובה (בהנחה שלא קיימת נגדה התקפה טובה מכוח גס), אם היא מפיקה פלט של n סיביות, אזי אומרים שביטחונה המרבי הוא בפקטור של כמחצית n. למשל ב-SHA-1 פלט הפונקציה המינימלי הוא 160 סיביות ועל כן מציאת התנגשות בכוח גס היא בסיבוכיות של 2^{80}.

תיאור סכמת פונקציית גיבוב קריפטוגרפית

מבנה מרקל-דמגרד[עריכת קוד מקור | עריכה]

Postscript-viewer-shaded.png ערך מורחב – שיטת מרקל-דמגרד

מבנה טיפוסי של פונקציית גיבוב קריפטוגרפית מורכב משלושה שלבים עיקריים; שלב הכנה, הליבה שנקראת 'פונקציית תמצות' ושלב סיום אופציונלי. היות שבדרך כלל המסר גדול במידה נכרת מהקלט אותו מקבלת פונקציית התמצות הפנימית יש צורך ליישם שיטה כלשהי לחלוקה לבלוקים בגודל קבוע וריפוד הבלוק האחרון כאשר אורך המסר אינו מתחלק היטב. השיטה הנפוצה שנקראת MD strengthening הומצאה על ידי רונלד ריבסט והיא מיישמת את מבנה מרקל ודמגרד. בשיטה זו מחלקים את הקלט לבלוקים בגודל קבוע מוסיפים '1' בסוף המסר ומרפדים באפסים ואז מוסיפים בלוק אחד המייצג את גודל המסר בסיביות ומבצעים את פעולת הפונקציה על כל הבלוקים בזה אחר זה. מרקל ודמגרד הוכיחו שאם נתונה פונקציית כיווץ (compression function) חסינת התנגשויות (בקיצור CRHF) למשל פונקציה מהצורה F : \{0,1\}^{n}\times \{0,1\}^{k} \rightarrow \{0,1\}^{k} כאשר k<n, אפשר להכין ממנה פונקציית גיבוב בטוחה לגיבוב מסר בכל אורך רצוי, שגם היא חסינת התנגשויות. כלומר ביטחון המבנה האמור אינו חלש מביטחונה של הפונקציה הפנימית עצמה.

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

כמתואר בתרשים השיטה באופן כללי פועלת כדלהלן:

  1. הקלט x מחולק ל-t בלוקים בגודל r סיביות, x=x_1,x_2,...,x_t.
  2. אם |x| (אורך x בסיביות) אינו מתחלק ב-r בשלמותו מוסיפים '1' בבלוק x_t לאחר המידע ומשלימים באפסים. תוספת זו מכונה MD strengthening והיא הוכנסה לראשונה באלגוריתם MD4 של רונלד ריבסט.
  3. מוסיפים בלוק x_{t+1} שמכיל ייצוג של אורך המסר בסיביות.
  4. מכינים וקטור אתחול בגודל r סיביות, נקרא בקיצור IV ומציבים בבלוק H_0.
  5. מבצעים איטרציה של הפונקציה הפנימית; עבור כל הבלוקים x_i כאשר i=1,...,t+1 מבצעים H_i=h(H_{i-1},x_i). בכל סבב h מפיקה ערך ביניים H_i שנקרא chaining value שהוא תוצאת החישוב על הבלוק הנוכחי בשילוב עם פלט הבלוק הקודם H_{i-1}. מבנה הפונקציה הפנימית ואופן שילוב הערכים משתנה בהתאם לשיטה עליה בנוי האלגוריתם (כמתואר תרשים). בגמר כל הסבבים הפלט הוא H_t.
  6. לסיום טרנספומציה אופציונלית g ממירה את הפלט האחרון לתוצאה הסופית h(x).

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

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

פונקציית תמצות[עריכת קוד מקור | עריכה]

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

פונקציית התמצות שנקראת גם פונקציית כיווץ (compression function) היא הליבה של פונקציית הגיבוב. אפשר להכין פונקציית תמצות חד-כיוונית וחסינת התנגשויות בשלושה אופנים עיקריים;

  • פונקציית תמצות מבוססת צופן בלוקים; קיימים שלושה מודלים בטוחים לבניית פונקציית תמצות על בסיס צופן בלוקים (כמתואר בתרשים).
  1. לפי מודל מטיאס-מאייר-אוסאס (האיור השמאלי בתרשים) הפונקציה היא H_i=E_{g(H_{i-1})}(x_i)\oplus x_i.
  2. לפי מודל דויס-מאייר הפונקציה היא H_i=E_{x_i}(H_{i-1})\oplus H_{i-1}.
  3. לפי מודל מיאגוצ'י-פרניל הפונקציה היא E_{g(H_{i-1})}(x_i)\oplus x_i\oplus H_{i-1}.
באופן כללי הסתמכות על צופן בלוקים לבניית פונקציית גיבוב איטית יחסית ואינה נפוצה בשימוש.
  • פונקציית תמצות ייעודית; זוהי פונקציה חד כיוונית חסינת התנגשויות (CRHF) שמבצעת סדרה של פעולות אריתמטיות בסיסיות תוך מתן דגש על ביצוע יעיל וקל ליישום במחשב הן בתוכנה והן בחומרה. קיימים מספר אלגוריתמים פופולריים שמסתמכים על פונקציית תמצות ייעודית. ביניהם אפשר למנות את משפחת תמצית המסרים של רונלד ריבסט, MD4 ו-MD5 וכן משפחת SHA בה כלולים שלושה אלגוריתמים SHA-2, SHA-1 ו-SHA-3 וכן RIPE-MD. שני האחרונים במשפחת SHA מומלצים כתקן גיבוב רשמי של ממשלת ארצות הברית המנוהל על ידי NIST.
דוגמה מפונקציית התמצות של SHA-2 הפועלת עם שמונה משתנים a עד h ונעזרת בטבלת ערכים קבועים K שהם שורשים מעוקבים של 64 הראשוניים הראשונים והמסר W לאחר הרחבה:
T_1=h+((e\ggg_6)\oplus (e\ggg_{11})\oplus (e\ggg_{25}))+((e\land f)\oplus (\lnot e\land g))+K_j+W_j
T_2=((a\ggg_2)\oplus (a\ggg_{13})\oplus (a\ggg_{22}))+((a\land b)\oplus (a\land c)\oplus (b\land c))
h=g, g=f, f=e, e= d+T_1, d=c, c=b, b=a, a=T_1+T_2
  • פונקציית גיבוב מבוססת אריתמטיקה מודולרית. פונקציה חד כיוונית שמסתמכת על בעיה מתורת המספרים שמאמינים שהיא קשה. סכמות מסוג זה בדרך כלל איטיות מאוד ומגיעות לתפוקה של בערך \text{log}_2\text{log}_2N סיביות פר העלאה בחזקה מודולרית אחת. N נקרא המודולוס והוא בדרך כלל בסגנון RSA - כפולה של שני מספרים ראשוניים סודיים N=pq. יש לציין שפונקציית גיבוב בעל מבנה אלגברי כמו זו מכילה חולשה מובנית, קל להחדיר דלת אחורית לפרמטרים של הסכמה כדי לגרום להתנגשויות. מלבד זאת חלק מהפרמטרים אמור להיות נסתר מהעין למשל הגורמים הראשוניים של N, ואסור לאף צד לראותם. לכן יש צורך לנקוט משנה זהירות בבחירת הפרמטרים. דרך אחת היא להיעזר בצד שלישי מהימן, דרך אחרת היא שימוש בסכמת שיתוף בטוחה.

פונקציית גיבוב מבוססת אריתמטיקה מודולרית[עריכת קוד מקור | עריכה]

איוון דמגרד הציע סכמה כזו המבוססת על צופן אל-גמאל וגיבסון ובלייר הציעו מבנים דומים המבוססים על בעיית לוגריתם דיסקרטי שפועלים מעל חבורה G מסדר ראשוני p. הרעיון הוא להכפיל את t הבלוקים של המסר עם t אלמנטים אקראיים \alpha_i מתוך G. ערך הגיבוב יהיה תוצאה של:

H_{t+1}=\prod_{i=1}^t \alpha_i^{\hat X_i} (מודולו p).

כאשר \hat X_i הוא הבלוק X_i של המסר לאחר שרופד ב-'1' כדי למנוע מצב שהבלוק יהיה כולו מאופס. בכל אופן מרבית הסכמות המבוססות על אריתמטיקה מודולרית כמו זו הן סכמות שפותחו בשיטות אד הוק, לא הוכחו כבטוחות וחלקן הגדול אף נפרצו בקלות. במיוחד ראוי לציון תקן איזו 10118-4 (MASH) שנפרץ פעם אחר פעם באופן מביך, לאחר שתוקן ובכל פעם התגלו בו שוב חולשות. המבנה הכללי הטוב ביותר היודע הוא מהצורה: H_i=((X_i\oplus H_{i-1})^2\text{ mod }N)\oplus H_{i-1}. כאשר H_{i-1} הוא ערך הביניים ו-X_i הם הבלוקים של המסר עם יתירות מוספת. חשוב מאוד להוסיף יתירות מכוונת למסר לפני הגיבוב כדי למנוע את 'התקפת בלוק מתקן' (להלן). הגרסה העדכנית של תקן איזו 10118-4 נכון לשנת 1998 (ISO/IEC 10118-4) נקראת MASH קיצור של modular arithmetic secure hash והיא מופיעה בשתי גרסאות MASH-1 ו-MASH-2. פונקציית התמצות הפנימית של MASH היא מהצורה:

H_i=(((\hat X_i\oplus H_{i-1})\lor A)^2(\text{ mod }N))\dashv n\oplus H_{i-1}

כאן A=\text{0xF00..00} הוא קבוע (בבסיס הקסדצימלי) וכן את הבלוקים \hat X_i בגודל n סיביות מכינים על ידי שמחלקים תחילה את המסר לבלוקים בגודל n/2 סיביות ומרחיבים כל בלוק על ידי הוספת יתירות, מציבים '1111' בארבעת הסיביות המשמעותיות של כל בית בבלוק. הסימן \lor מייצג OR, הסימן \oplus מייצג XOR והסימן \dashv אומר שתוצאת ההעלאה בריבוע נחתכת בכל סבב ל-n סיביות האחרונות. בנוסף התקן מגדיר פונקציה מסיימת מסובכת שנועדה למחוק כל זכר של המבנה האלגברי של הפונקציה. התוצאה האחרונה של פונקציית התמצות H_{t+1} מחולקת ל-4 תת-בלוקים, איתם מחשבים ברקורסיה עוד שנים-עשר בלוקים בגודל n/4 סיביות Y_i=Y_{i-1}\oplus Y_{i-4}, מאחדים את כל 16 הבלוקים שנוצרו לשמונה בלוקים בני n/2 סיביות X_{t+1+i}=Y_{2i-2}\ \| \ Y_{2i-1}, מרחיבים אותם לפי השיטה האמורה לעיל ומבצעים עוד שמונה סבבים של פונקציית התמצות על הבלוקים האחרונים. ולסיום התוצאה הסופית היא מחרוזת סיביות בגודל n/2 המחושבת על ידי H_{t+1+8}\text{ mod }p. ההתקפה הטובה ביותר הידועה כנגד מבנה זה היא בסיבוכיות של 2^{n/2} שהיא לא יותר טובה מכוח גס. MASH-2 היא גרסה שונה במעט שבה ההעלאה בריבוע מוחלפת ב-e=2^8+1.

התקפת בלוק מתקן[עריכת קוד מקור | עריכה]

התקפת בלוק מתקן (correcting block) היא התקפה המנצלת את המבנה האלגברי של פונקציית התמצות הפנימית. ההתקפה מתמקדת בחיפוש התנגשויות או מקור נוסף על ידי החלפת חלק מהבלוקים בבלוקים אחרים למעט בלוק אחד או יותר בסוף, באמצע או בהתחלה. ההתקפה מתבצעת על ידי חישוב h(X\ \| \ Y) כאשר Y הוא הבלוק המתקן. מבנה אלגברי פגיע במיוחד להתקפה זו משום שאפשר להפוך לפעמים את פונקציית התמצות הפנימית בעזרת מניפולציה אלגברית. דרך נפוצה להתמודד עם התקפה זו היא להוסיף יתירות מכוונת למסר לפני הגיבוב כך שיהיה קשה למצוא בלוק מתקן עם היתירות הדרושה. המחיר כמובן הוא ירידה בביצועים. לדוגמה ב-1984 הציעו דייויס ופרייס פונקציית גיבוב עם פונקציית תמצות f כדלהלן: f=(H_{i-1}\oplus X_i)^2\text{ mod }N. היתירות שהם הוסיפו הייתה 64 אפסים שנוספו לכל בלוק לפנים או בסוף. גיראולט ואחרים הראו כיצד אפשר לתקוף פונקציה כזו ולמצוא מקור נוסף. CCITT X.509 הייתה פונקציית גיבוב שפותחה ב-1988 וניסתה למנוע את ההתקפה המתוארת על ידי הוספת היתירות באופן כזה שכל ניבל (חצי בית) בכל הבתים של המסר יכיל ארבעה אפסים. למרות זאת הראה קופרשמידט שאפשר למצוא התנגשויות במבנה זה באמצעות ההתקפה האמורה.

יישומים מעשיים[עריכת קוד מקור | עריכה]

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

תקן פונקציית גיבוב בטוחה (SHA)[עריכת קוד מקור | עריכה]

במטרה ליצור תקן בינלאומי אחיד של פונקציות גיבוב קריפטוגרפיות פרסם המכון הלאומי לתקנים וטכנולוגיה האמריקאי את תקן SHA קיצור של secure hash algorithm. בשנת 1993 פורסמה הראשונה מבין הפונקציות במשפחה שנקראה SHA-0 (האפס נוסף מאוחר יותר כדי להבדילה מהגרסאות המתקדמות). הפונקציה הוחלפה ב-1995 בגרסה המחוזקת SHA-1, עקב חולשות שנתגלו בה. SHA-1 דמתה ל-SHA-0 בשינויים קלים. שתי הפונקציות מבוססות על אלגוריתם תמצית מסרים של רונלד ריבסט MD5, פועלות בשיטת מרקל-דמגרד ומפיקות פלט באורך 160 סיביות. ב-2002 פרסם NIST את משפחת הפונקציות הבאה SHA-2, המפיקות ארבעה פלטים אפשריים 224, 256, 384 ו-512 סיביות.

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

בנובמבר 2007 הושקה תחרות פתוחה לתקן SHA החדש, בדומה לתחרות שהתקיימה לצפני בלוקים שבה זכה AES. באוקטובר 2012 נסגרה התחרות והוכרז Keccak האלגוריתם הזוכה בתחרות, זה שיחליף בהדרגה את קודמו לתפקיד ונקרא SHA-3‏‏‏. בארגון התקינה ממליצים שלא להשתמש יותר ב-SHA-1 וממליצים לעבור ל-SHA-2 או SHA-3. בארגון התקינה רואים בתקן SHA-2 עדיין בטוח לשימוש נכון לשנת 2013 ולא מתוכנן להחליפו בזמן הקרוב. העובדה ש-SHA-3 שונה מאוד בעיצובו ואופן פעולתו מתקן SHA-2 רק מרחיב את האפשרויות כיוון שלא סביר שתמצא התקפה אחת שתהיה יעילה כנגד שניהם. Keccak הזוכה בתחרות SHA-3 הינו אלגוריתם גיבוב יעיל ובטוח, שפותח על ידי קריפטוגרפים בלגיים ואיטלקיים. הוא מצטיין בגמישות רבה, שולי ביטחון גבוהים, ביצועים כלליים טובים ומימוש יעיל בחומרה. באלגוריתם זה הוכנס לראשונה מבנה ייחודי למנגנון השרשור (chaining) אותו הם מכנים "מבנה ספוגי" המנצל טבלת תמורה סטטית הניתנת להתאמה על מנת לבחור בין ביצועים וביטחון.

פונקציות גיבוב[עריכת קוד מקור | עריכה]

להלן רשימה נבחרת של פונקציות גיבוב פופולריות שהיו בשימוש נרחב בעשור האחרון, חלקן לא בטוחות לאחר שהתגלו בהן חולשות והן מובאות כאן רק למען התיעוד. SHA-0 לא נכלל ברשימה גם משום שאינו בטוח כלל וגם משום שהוחלף בגרסאות מחוזקות שלו SHA-1 ו-SHA-2. ב-2005 דווחה התקפה תאורטית כנגד SHA-1 שמוצאת התנגשויות בזמן של 2^{69} פעולות גיבוב (לעומת 2^{80} כפי שמצפים מפונקציית גיבוב של 160 סיביות) ולמרות שב-2010 דווחה התקפה מעשית בסדר גודל של 2^{61}, הוא נכלל ברשימה כי עדיין נפוץ בשימוש נרחב. MD5 נפרץ לגמרי. ב-2004 בתוך ארבעה חודשים נמצאו התנגשויות בגרסה מלאה של MD5 בפרויקט שנקרא MD5CRK. ב-2005 ארג'ן לנסטרה הראה שאפשר לזייף סרטיפיקט X.509 בגרסה שעושה שימוש ב-MD5 באמצעות חיפוש התנגשויות בפונקציית הגיבוב, בתוך מספר שעות. ב-2010 דווחה התקפה נוספת, היעילה ביותר עד כה כנגד MD5 שפרטיה לא פורסמו אלא הוצעה כאתגר בסך 10,000 דולר למי שיצליח למצוא התנגשות עם 64 בתים עד ינואר 2013. ייתכן שהאלגוריתם נמצא עדיין בשימוש מוגבל והוא למעשה מוחלף כעת בהדרגה על ידי ארגוני התקינה הבינלאומיים באלגוריתם בטוח יותר.

להלן הרשימה:

שם הפונקציה אורך התג בסיביות
GOST 256
HAVAL 128/160/192/224/256
MD5 160
RIPEMD 128/160/256
SHA-1 160
SHA-2 224/256/512
SHA-3 224/256/384/512
Tiger 2 192/128/160
Whirlpool 512

שלושת האלגוריתמים הראשונים HAVAL, GOST, MD5 וכן RIPEMD-128 לא מומלצים לשימוש כיום, והם מופיעים לצורך התיעוד בלבד. כמו כן ארגוני התקינה המליצו לעבור ל-SHA-2 ולא להשתמש יותר ב-SHA-1.

ראו גם[עריכת קוד מקור | עריכה]

לקריאה נוספת[עריכת קוד מקור | עריכה]

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

הערות שוליים[עריכת קוד מקור | עריכה]