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

מתוך ויקיפדיה, האנציקלופדיה החופשית

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

[עריכה] שימושים

[עריכה] טבלת גיבוב

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

[עריכה] בדיקת שגיאות

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

פונקציה נפוצה לבדיקה ותיקון שגיאות היא CRC.

אלגוריתם חישוב ספרת ביקורת הוא דוגמה לפונקציית גיבוב.

[עריכה] השוואה בין קבצים

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

[עריכה] פונקציית גיבוב קריפטוגרפית

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

פונקציות גיבוב קריפטוגרפיות הנן תת-משפחה חשובה של פונקציות הגיבוב שלה מספר מאפיינים ייחודיים. הן מכונות פונקציות גיבוב חד-כיווניות (באנגלית: One way hash function בקיצור OWHF). כלומר קל יחסית לחשב את הפלט מתוך קלט נתון, אולם קשה מאוד (מבחינה חישובית) לשחזר את קלט הפונקציה בהינתן הפלט בלבד.

פונקציות גיבוב קריפטוגרפיות ממלאות תפקיד חשוב בהצפנה מודרנית. הן משמשות בעיקר להבטחת שלמות מסרים גם בשילוב עם חתימה דיגיטלית. הן מתחלקות לשני סוגים עיקריים: פונקציות גיבוב ללא מפתח הנקראות MDC (קיצור של Modification Detection Code), ופונקציות בשילוב עם מפתח הצפנה הנקראות קוד אימות מסרים - שהן פונקציות גיבוב סימטריות לאימות מסרים. כמו כן פונקציות גיבוב שימושיות ליצירת מספרים אקראיים.

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

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

התכונות הבסיסיות של כל פונקציית גיבוב הן:

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

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

עמידות מקור ראשון (preimage resistance), פירושו: עבור כל פלט נתון, יהיה קשה עד בלתי אפשרי מבחינה חישובית למצוא את הקלט המקורי לפונקציה שהפיקה פלט זה. כלומר בהינתן $\ y$ , למצוא $\ x$ המקיים $\ h(x)=y$ .
עמידות מקור שני (2nd-preimage resistance), פירושו: עבור כל קלט נתון, יהיה קשה עד בלתי אפשרי מבחינה חישובית למצוא קלט אחר שעבורו הפונקציה מפיקה פלט זהה. כלומר בהינתן $\ x$ כלשהו למצוא $\ x'$ (אחר) המקיים $\ h(x)=h(x')$ . פונקציה שעונה על דרישות אילו נקראת One Way Hash Function - פונקציית גיבוב חד-כיוונית, בקיצור OWHF.
עמידות בפני התנגשות (collision resistance), פירושו שיהיה קשה עד בלתי אפשרי מבחינה חישובית למצוא כל זוג קלטים אפשרי שעבורם יופק פלט זהה. כלומר למצוא $\ x$ ו- $\ x'$ שרירותיים המקיימים $\ h(x)=h(x')$ . פונקציה שעונה על דרישה זו נקראת Collision Resistant Hash Function - פונקציית גיבוב עמידת התנגשות, בקיצור CRHF.

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

שלד פונקציית גיבוב בסיסי

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

[עריכה] סוגי פונקציות גיבוב

השלד הבסיסי של מרבית פונקציות הגיבוב הקריפטוגרפיות (ראה תרשים), בנוי מפונקציה פנימית הנקראת פונקציית כיווץ, שמופעלת על גושי הקלט באופן איטרטיבי ובדרך כלל לחיזוק האלגוריתם נוספת בהתחלה פרוצדורת ריפוד. השיטה המקובלת היא MD-Strengthening, שיטה זו מוסיפה 1 בסוף המסר, מרפדת את המסר באפסים כדי להשלימו לגודל הרצוי (גודל הגושים שמקבל האלגוריתם) ומוסיפה גוש אחד נוסף המכיל את גודל המסר בייצוג בינארי. אפשר לתאר את התהליך באופן הבא: בהינתן פונקציית כיווץ $\ f$ ומסר $\ x$ המחולק לגושים בגודל קבוע $\ x_1,x_2,...,x_t$ :

תחילה מוזן הערך ההתחלתי $\ H_0=IV$ . המשתנה $\ H_i$ נקרא chaining variable, משתנה זמני המכיל את פלט הפונקציה בכל סבב.
בכל סבב $\ H_i=f(H_{i-1},x_i)$ , עבור כל $\ 1\le i\le t$ . פונקציית הכיווץ מקבלת ככקלט את ערכו של $\ H$ מהסבב הקודם ואת גוש המסר הבא ומפיקה פלט חדש. תהליך זה חוזר על עצמו עד לקריאת כל גושי הקלט כאשר $\ H_t$ מהווה פלט סופי של הפונקציה.
לעתים נוספת פרוצדורה משלימה $\ h(x)=g(H_t)$ הממפה את תוצאת פונקציית הכיווץ לפלט סופי כלשהו.

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

1. פונקציות גיבוב מבוססות הצפנה סימטרית

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

מודל Matyas-Meyer-Oseas בו פונקציית הכיווץ מופעלת באופן הזה: $\ H_i=E_{g(H_{i-1})}(x_i)\oplus x_i$ .
מודל Davis-Meyer בו פונקציית הכיווץ פועלת באופן הזה: $\ H_i=E_{x_i}(H_{i-1})\oplus H_{i-1}$ .
מודל Miyaguchi-preneel בו פונקציית הכיווץ פועלת באופן הזה: $\ H_i=E_{g(H{i-1})}(x_i)\oplus x_i\oplus H_{i-1}$ .

הפונקציה $\ E$ מייצגת צופן גושים ידוע, כאשר מפתח ההצפנה מסופק על ידי הפונקציה $\ g$ המייצגת פונקציית מיפוי כלשהי שמקבלת כקלט את ערכו של $\ H$ מהסבב הקודם או את גוש המסר הנוכחי (בהתאם למודל) ומפיקה ערך המשמש כמפתח הצפנה לסבב הנוכחי.

2. פונקיות גיבוב מבוססות אריתמטיקה מודולרית: בקבוצה זו נמנה 1-MASH (קיצור של Modular arithmetic secure hash) בשיטה זו פונקציית הכיווץ הפנימית מתבססת על המשוואה המודולרית: $\ H_i\leftarrow((((H_{i-1}\oplus y_i)\vee A)^2\mbox{ mod }M)\dashv n)\oplus H_{i-1}$ . הערך $\ y_i$ הוא המסר כשהוא מורחב אחרי הוספת יתירות, הערך $\ A$ קבוע השווה ל- $\ 0xF0...0$ , הסימן " $\ \dashv$ " מייצג הזזה של סיביות התוצאה שמאלה (כלפי מעלה) והסימן " $\ \vee$ " מייצג או לוגי.

3. פונקציות גיבוב ייעודיות

מרבית האלגוריתמים הפופולריים הנם אלגוריתמים ייעודיים שפותחו במיוחד למטרה זו. המודל הראשון לאלגוריתמים אילו היה MD4, הרביעי בסדרה של אלגוריתמי גיבוב שפותחו על ידי רונלד ריבסט ב-1990, שנקראים Message Digest (תמצית מסרים). בשל ליקויים בטיחותיים שהתגלו ב-MD4, יצא MD5 שהוא תוצר ישיר של קודמו, בשיפורים קלים להגברת בטיחותו. על בסיס הידע שנצבר בעקבות MD4 הומצאו אלגוריתמים נוספים כמו אלגוריתם גיבוב בטוח (SHA) וגרסאותיו פרי פיתוח של ה-NSA וכן RIPEMD שהומצא על ידי דן בויר בחסות הפרויקט האירופאי RIPE.

מחקרים חדשים שנעשו חושפים ליקויים נוספים במרבית האלגוריתמים המנויים המבוססים על MD4, מסתבר שאינם בטוחים לגמרי, חלקם אף לא בטוחים כלל. למעט SHA-2 ו-RIPEMD-160 (לגביהם קיים ספק לגבי בטיחותם לטווח רחוק).

קיימים אלגוריתמים חדשים שטרם זכו לביקורת מספקת כמו אלגוריתם Tiger של אלי ביהם המבוסס על פונקציה פנימית 'מעין' צופן גושים ומיושם לפי מודל מטיאס-מאייר האמור וכן Whirlpool של ונסנט ריימן המבוסס על גרסה מיוחדת של AES ומיושם לפי מודל מיאגוצ'י פרניל האמור לעיל. אלגוריתם זה אומץ על ידי ארגון התקינה הבינלאומי כחלק מתקן ISO/IEC 10118-3:2004. אלגוריתמים מבטיחים נוספים הם: Cellhash, FSB, GOST R, HAS-160, LASH, MAELSTROM, RADIOGATUN, Subhash.

ארגון NIST השיק באוגוסט 2006 תחרות כלל עולמית לפונקציות גיבוב קריפטוגרפיות בטוחות, בדומה לתחרות שתהקיימה לצופני גושים שבה זכה AES. התחרות נמצאת לקראת השלב השני בו ייבחרו האלגוריתמים המובילים מתוך כלל המשתתפים. בחירת האלגוריתם המנצח (לאחר שלבים ארוכים של המתנה להערות וניפוי מועמדים אחרים) מתוכננת לשנת 2012. האלגוריתם שייבחר יחליף את משפחת האלגוריתמים SHA בתקן ההצפנה האמריקאי.‏‏^[1]

[עריכה] MD5

ערך מורחב – MD5

אלגוריתם MD5 (ראשי תיבות של Message-Digest 5), פותח בשנת 1991 על ידי רונלד ריבסט. האלגוריתם מחזיר פלט של 128 סיביות. בגרסאות שקדמו לו (MD2 ו־MD4) התגלו חולשות רבות ולכן פותח אלגוריתם זה על מנת להחליפם. אולם לאחרונה התגלו שיטות ניתוח חדשות שמעמידות בספק את בטיחות האלגוריתם, על כן לא מקובל להשתמש בו כיום.

[עריכה] SHA-1

אלגוריתם SHA-1 (ראשי תיבות של: Secure Hash Algorithm) תוכנן על ידי ה־NSA והופץ על ידי ממשלת ארצות הברית בשנת 1995 באמצעות ארגון NIST. במקור נקרא SHA אבל התגלתה בו פרצה חמורה וכדי שיהיה ניתן להבדיל בין הגרסאות נקראה הגרסה המתוקנת SHA-1. SHA-1 מחזיר פלט של 160 סיביות.

דוגמה מעשית לפלט (חתימה) של SHA-1:

SHA1("The quick brown fox jumps over the lazy dog") = 2fd4e1c67a2d28fced849ee1bb76e7391b93eb12

SHA1("The quick brown fox jumps over the lazy cog") = de9f2c7fd25e1b3afad3e85a0bd17d9b100db4b3

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

[עריכה] SHA-2

ל־SHA קיימות גרסאות שמחזירות פלט בגדלים שונים, המסומנות SHA-xxx כאשר xxx הוא מספר סיביות הפלט. גרסאות אילו מכונות לעתים SHA-2, ובהן SHA-224, SHA-256, SHA-384, SHA-512. דוגמה לפלט אלגוריתם ערבול SHA-512:

SHA512("The quick brown fox jumps over the lazy dog") = 
   
   07e547d9 586f6a73 f73fbac0 435ed769
   51218fb7 d0c8d788 a309d785 436bbb64
   2e93a252 a954f239 12547d1e 8a3b5ed6
   e1bfd709 7821233f a0538f3d b854fee6

[עריכה] בטיחות

ישנן שתי סוגי התקפות עיקריות על פונקציות גיבוב: האחת היא יכולת היריב למצוא ערך ספציפי לפי בחירתו, אשר יניב פלט זהה לקלט המקורי והשנייה היא היכולת למצוא ערך כלשהו לאו דווקא לפי בחירה אשר יניב ערך דומה, ללא יכולת שליטה על הערך עצמו. ההתקפה המפורסמת ביותר על פונקציות גיבוב הינה התקפת יום הולדת של גדעון יובל, יעילותה היא $\ O(2^{n/2})$ עבור ערך גיבוב באורך n סיביות והיא מבוססת על פרדוקס יום ההולדת. הרעיון הוא ליצור טבלה של $\ 2^{n/2}$ גרסאות שונות של המסר המקורי והמסר המזויף (בשינויים קלים) יחד עם ערך הגיבוב שלהם, למיינם לפי ערך הגיבוב באופן שיאפשר חיפוש מהיר ואז לחפש התאמות בין זוגות שונים. כאמור התאמה כזו חייבת להופיע בשלב כלשהו. אפשר לשפר את ההתקפה ולהימנע משימוש בזיכרון בהסתמך על תכונות ידועות של פונקציה אקראית. כמו באמצעות אלגוריתם מציאת מחזוריות של פלויד. התקפה נוספת כנגד פונקציות גיבוב נקראת התקפת שרשור (Chaining attack). בהתקפה זו מנצלים את האופי המחזורי של פונקציות הגיבוב הידועות, במיוחד כאלו העושות שימוש במשתני שרשור (Chaining variable), תוך התמקדות בחלק הכיווץ של הפונקצייה במקום בפונקצייה כולה. על כל פנים התקפות אילו אינן מעשיות במיוחד כאשר פונקציית הגיבוב מתוכננת היטב ומפיקה ערך גיבוב הגדול מ-64 סיביות. למשל אלגוריתם SHA קיים במספר גרסאות בהתאם לרמת בטיחות רצויה בסיביות כגון SHA-256/224 או SHA-512/384.

[עריכה] ראו גם

[עריכה] קישורים חיצוניים

פונקציות גיבוב חד כיווניות (בוויקיפדיה האנגלית)

[עריכה] הערות שוליים

^ ‏לוח הזמנים לתחרות באתר NIST‏

[0] ‏לוח הזמנים לתחרות באתר NIST‏

[1]