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

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

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

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

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

  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 Vector או בקיצור 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[עריכת קוד מקור | עריכה]

Postscript-viewer-shaded.png ערך מורחב – 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 תחרות פתוחה לתקן פונקציות גיבוב קריפטוגרפיות בטוחות (הקרוי בקיצור SHA), בדומה לתחרות שהתקיימה לצופני גושים שבה זכה AES. באוקטובר 2012 נסגרה התחרות והוכרז Keccak האלגוריתם הזוכה בתחרות, שיחליף בהדרגה את קודמו לתפקיד ונקרא כעת SHA-3‏‏‏[1]. בארגון התקינה רואים בתקן SHA-2 עדיין בטוח לשימוש נכון לשנת 2013 ולא מתוכנן להחליפו בזמן הקרוב.

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

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

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

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

  1. ^ הזוכה בתחרות באתר NIST