Secure Hash Algorithm

מתוך ויקיפדיה, האנציקלופדיה החופשית
(הופנה מהדף SHA)
קפיצה אל: ניווט, חיפוש

בקריפטוגרפיה, Secure Hash Algorithm (בקיצור SHA) היא משפחה של פונקציות גיבוב קריפטוגרפיות, הכוללת את הפונקציות SHA-0 (במקור SHA)‏, SHA-2, SHA-1 והחל מ-2012 גם את SHA-3. הפונקציות ממשפחה זו משמשות ביישומים ופרוטוקולים מאובטחים רבים. פונקציות ה-SHA פורסמו על ידי הNIST כתקן FIPS.

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

אלגוריתם SHA פורסם בשנת מאי 1993 על ידי ה-NIST לצורך ייצוג תמציתי של הודעות בשימוש באלגוריתמי חתימות וכאשר נדרש ערך גיבוב קריפטוגרפי ביישומים פדרליים‏[1]. אלגוריתם SHA בנוי בשיטת מרקל-דמגרד. הקלט שלו הוא מחרוזת שאורכה עד 2^{64} סיביות והפלט שלה הוא תמצית באורך 160 סיביות. האלגוריתם מבוסס ברובו על הפונקציה MD4 תוך הגדלת המצב הפנימי ושינוי חלק מהפונקציות הפנימיות וערכי הקבועים שבשימוש.

בשנת 1995 פרסם ה-NIST אלגוריתם חדש שנקרא SHA-1 שמטרתו להחליף את אלגוריתם SHA הקודם (החל מהפרסום נהוג להתייחס לאלגוריתם הראשון כ-SHA-0). השוני היחיד בין האלגוריתמים כלל שינוי במנגנון הרחבת ההודעה של SHA-1 על פני SHA-0. לטענת ה-NIST מטרת התיקון הייתה לפתור חולשה שנמצאה באלגוריתם הקודם; ה-NIST לא פרסם את החולשה שהתיקון אמור לפתור‏[2].

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

בשנת 2007 יזמה ה-NIST תחרות לבחירת פונקציות שיצטרפו למשפחת ה-SHA. לתחרות הוגשו 64 הצעות שמתוכן עמדו 51 בתנאי הסף. ההצעות פורסמו והקהילה הקריפטוגרפית הבינלאומית הוזמנה לנתח ולנסות לשבור את כל המועמדים. 14 מועמדים עברו לשלב השני של התחרות כאשר חמשת המועמדים הסופיים הם BLAKE, Grøstl, JH, Keccak ו-Skein. בשנת 2012 פורסם הזוכה בתחרות לגיבוב SHA-3 והוא הצופן Keccak[5].

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

התרשים מתאר איטרציה אחת בתוך פונקציית ה"כיווץ" של האלגוריתם. A,B,C,D,E הינם מילים בנות 32 ביט אשר שומרות מצב; F הינה פונקציה לא לינארית משתנה; sleft shift מסמלת הזזת סיביות ימנית ב- s מקומות. Addition מסמל חיבור מודולו 232. Kt הינו קבוע.

SHA-0[עריכת קוד מקור | עריכה]

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

אתחול[עריכת קוד מקור | עריכה]

ראשית, המשתנים הפנימיים מקבלים את ערכי וקטור האתחול (IV)

A=\text{0x67452301}
B=\text{0xEFCDAB89}
C=\text{0x98BADCFE}
D=\text{0x10325476}
E=\text{0xC3D2E1F0}
h_0=(A,B,C,D,E)

לאחר מכן, קלט הפונקציה מחולק לבלוקים באורך 512 סיביות המכונים M_1,M_2...M_\ell; לבלוק האחרון מוסיפים את אורך ההודעה. במידה ואורך ההודעה אינו כפולה של 512 מוסיפים לבלוק האחרון, אחרי ההודעה ולפני האורך שלה את הסיבית 1 ולאחריה 0 בכמות הנדרשת כדי להביא אותה לאורך של 512 סיביות.

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

בכל שלב של הפונקציה מועברים לפונקציית התמצות המשתנים הפנימיים מהסיבוב הקודם והבלוק הנוכחי לעיבוד. הפונקציה מחזירה את הערך החדש של המשתנים הפנימיים (h_i=H(H_{i-1},M_i)). פונקציית הגיבוב אינה כוללת שלב סיום ולכן בסיום התהליך פלט פונקציית הגיבוב הוא הפלט של פונקציית התמצות מהשלב האחרון.

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

מנגנון הרחבת הודעות: הפונקציה מחלקת את הבלוק ל-16 חלקים באורך 32 סיביות המכונים w_0,w_1...w_{15}. לאחר מכן, הפונקציה מרחיבה את 16 החלקים ל-80 באמצעות הפעלת ה-LFSR הבא 64 פעמים:

w_t=w_{t-3}\oplus w_{t-8}\oplus w_{t-14} \oplus w_{t-16}

תמצות המסר: עבור כל אחד מ-80 החלקים של המסר, הפונקציה מפעילה את האלגוריתם הבא:


T=(A\lll 5)+f_t(B_t,C_t,D_t)+E_t+W_t+K_t

E_{t+1}=D_t;D_{t+1}=C_t;C_{t+1}=B_t\lll 30;B_{t+1}=A_t;A_{t+1}=T

פלט: פונקציית התמצות מחזירה את הפלט:

A=A_0+A_{80};B=B_0+B_{80};C=C_0+C_{80};D=D_0+D_{80};E=E_0+E_{80}


הפונקציה f והקבוע K מוגדרים כך:

0\leq t\leq 19 \ K=0x5A827999 \ f_t(X,Y,Z)=XY\vee(\neg X)Z

20\leq t\leq 39 \ K=0x6ED9EBA1 \ f_t(X,Y,Z)=X\oplus Y \oplus Z

40\leq t\leq 59 \ K=0x8F1BBCDC \ f_t(X,Y,Z)=XY\vee XZ \vee YZ

60\leq t\leq 79 \ K=0xCA62C1D6 \ f_t(X,Y,Z)=X\oplus Y\oplus Z

SHA-1[עריכת קוד מקור | עריכה]

הפונקציות SHA-0 ו-SHA-1 זהות באלגוריתמים שלהם פרט למנגנון הרחבת ההודעה ב-SHA-1 שמפעיל את ה-LFSR הבא 64 פעמים:

w_t=(w_{t-3}\oplus w_{t-8}\oplus w_{t-14} \oplus w_{t-16})\lll 1

בטיחות[עריכת קוד מקור | עריכה]

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

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

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

האלגוריתם גודל מסר מקסימלי בסיביות גודל גוש בסיביות גודל מילה (Word) גודל תמצית המסר (בסיביות) בטיחות* (בסיביות)
SHA-1 \ 2^{64} \ 512 \ 32 \ 160 \ 80
SHA-256 \ 2^{64} \ 512 \ 32 \ 256 \ 128
SHA-384 \ 2^{128} \ 1024 \ 64 \ 384 \ 192
SHA-512 \ 2^{128} \ 1024 \ 64 \ 512 \ 256
  • בהקשר זה הבטיחות מתייחסת לכמות העבודה הנדרשת למציאת התנגשות (מסרים שונים המפיקים פלט זהה) תוך שימוש בהתקפת יום ההולדת. הערך מתפרש כ-\ 2^{n/2}.


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

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