Secure Hash Algorithm

בקריפטוגרפיה, אלגוריתם גיבוב בטוח (SHA) הוא שם כולל למשפחה של פונקציות גיבוב קריפטוגרפיות. "גיבוב" כאן פירושו המרת קלט באורך כלשהו ל"תמצית" קצרה באורך קבוע. SHA הוא חלק מתקן הפדרלי האמריקאי FIPS ונועד לאימות והבטחת שלמות מידע, כולל בשיטות חתימה דיגיטלית. משפחת SHA כוללת בין היתר את SHA-0, SHA-1, SHA-2 ואת SHA-3 (נבחרה ב-2012).

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

המשפחה פותחה והתקבלה בתקן SHS של NIST בשיתוף NSA. הגרסאות המרכזיות הן SHA-0 (המקורית), SHA-1, ומשפחת SHA-2 שמכילה גרסאות כגון SHA-256, SHA-384 ו-SHA-512. SHA-3 (Keccak) נבחרה בתחרות שסיימה ב-2012.

פונקציות SHA נבדקות ומאושרות במסגרת CMVP, שיתוף פעולה של NIST ו-CSE הקנדית. גוף זה בודק ומסמיך מוצרים קריפטוגרפיים לשימוש מסחרי, ומעריך את בטיחות המודולים בעזרת מומחים.

האלגוריתם המקורי פורסם ב-1993. ב-1995 שוחררה SHA-1 עם שינוי קטן במנגנון הרחבת ההודעה. ב-2002 הוכנסו לתקן פונקציות חדשות (SHA-256/384/512) כדי לאפשר ערכי תמצית ארוכים ובטיחות גבוהה יותר; ב-2008 נוספה SHA-224. ב-2007 ערך NIST תחרות לבחור אלגוריתם חדש, וב-2012 הוכרז Keccak כ-SHA-3.

ברוב גרסאות ה-SHA קיימים: זיכרון פנימי (סט של מילים), חלוקת הקלט לבלוקים של גודל קבוע, ריפוד שמוסיף סיבית 1 ואז אפסים ולהוסיף את אורך ההודעה, הרחבת הבלוק למערך מילים גדול יותר, ואז 80 סבבי עיבוד על ידי פונקציית התמצות. פעולות פנימיות כוללות XOR (פעולת יוצא מן הכלל), הזזות מעגליות וחיבור מודולרי. מבנה האלגוריתם לרוב בסגנון מרקל-דמגרד; SHA-3 שונה במבנה.

בגרסה המקורית יש חמישה משתנים פנימיים (כל אחד 32 ביט) שיוצרים מצב של 160 ביט. הקלט נחלק לבלוקים של 512 ביט, בריפוד מוסיפים סיבית 1 ואז אפסים ואז את אורך ההודעה. הבלוק מחולק ל-16 מילים של 32 ביט, ואז מרחיבים את המערך ל-80 מילים באמצעות פעולות XOR לפי כלל איטרטיבי. לאחר מכן מפעילים 80 סבבים של חישוב שמשלבים הזזות, פונקציות לא־ליניאריות וערכי קבועים, ועדכון המשתנים הפנימיים.

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

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

הרחבת ההודעה מייצרת 80 מילים מתוך 16 הראשוניות. בכל אחד מ-80 סבבי העיבוד מחשבים ערך זמני T שמשלב סיבוב של A, פונקציה לא־ליניארית של B,C,D, הערך E, המילה הנוכחית ועוד קבוע לפי טווח הסיבובים. בתום 80 הסבבים מעדכנים את המצב ההתחלתי עם הערכים החדשים כדי לקבל את הפלט של הבלוק.

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

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

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

מטרת SHA היא לבדוק שמידע לא שונה. גם שינוי קטן בהודעה ייצור תמצית שונה. זה עוזר לוודא שהמידע לא שונה בדרך.

יש כמה גרסאות חשובות: SHA-0 ו-SHA-1 (ישנות), SHA-2 (כוללת SHA-256 ועוד), ו-SHA-3 שנבחרה ב-2012.

ארגונים כמו NIST ו-CSE בודקים את הפונקציות האלה ומאשרים מוצרים שעמדו בבדיקה.

הגרסה הראשונה פורסמה ב-1993. ב-1995 יצאה SHA-1 עם תיקון קטן. ב-2002 הוסיפו גרסאות חזקות יותר. ב-2007 ערכו תחרות למציאת אלגוריתם חדש, וב-2012 נבחר Keccak להיות SHA-3.

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

ב-SHA-0 יש חמש מילים פנימיות. עובדים על בלוקים של מידע ומרחיבים אותם ליותר מילים. עושים 80 סבבים כדי לקבל את התמצית.

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

בכל סבב מעדכנים את המידע הפנימי לפי כללים של הזזה וחיבור.

הפעולות כוללות חיבור, XOR (פעולה מתמטית שמערב ביטים) והזזות. בסוף מוסיפים את התוצאות לקבלת הפלט.

SHA-1 דומה ל-SHA-0, אך בהרחבת ההודעה מוסיפים סיבוב אחד לכל מילה. ב-2005 נמצאה חולשה ב-SHA-1, אז כבר לא ממליצים להשתמש בו.

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