SHA-3

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

SHA-3 השלישי במשפחת האלגוריתמים Secure Hash Algorithm, בשמו המקורי Keccak[1] הוא פונקציית גיבוב קריפטוגרפית שפותחה ב-2008 על ידי גוידו ברטוני, יוהאן דאמן ממפתחי AES, מיכאל פיטרס וג'יל ואן אשה ונבחרה על ידי NIST כתקן גיבוב פדראלי של ממשלת ארצות הברית. פונקציית גיבוב היא מרכיב חיוני בכל מערכת קריפטוגרפית מודרנית. הפונקציה מפיקה ממסר בכל אורך רצוי, ערך ייחודי בגודל קבוע שנקרא "ערך גיבוב" או "תמצית המסר" ומטרתו להוות ייצוג קומפקטי או טביעת אצבע דיגיטלית של המסר.


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

המניע מאחורי פיתוח תקן SHA-3 הוא התפתחותן של טכניקות קרפיטואנליטיות חדשות וחשיפת חולשות תאורטיות ומעשיות באלגוריתמים הקודמים במשפחה MD5 וכן SHA-0 והתקפה תאורטית על SHA-1. ב-NIST ראו צורך לפתח פונקציית גיבוב חדשה שונה במבנה ובקונספט מקודמותיה, על מנת להרחיב את היצע הפונקציות במשפחה וסימנה יהיה SHA-3. לאור זאת הוחלט בנובמבר 2007 על תחרות פתוחה לציבור לפיתוח פונקציית גיבוב קריפטוגרפית שתשמש כתקן גיבוב ממשלתי (בדומה לתחרות לבחירת תקן AES שבסופה נבחר צופן הבלוקים Rijndael). באוקטובר 2008 הצטברו 64 הצעות של מומחי הצפנה מכל העולם, מתוכם נבחרו 51 מועמדים לסבב הראשון לאחר שכמה מהם נפסלו כי לא עמדו בתנאי הסף‏[2]. ביולי 2009 הצטמקה הרשימה הנבחרת לסבב השני ל-14 מועמדים, ההכרזה בוצעה באמצעות אימייל שנשלח לרשימת התפוצה של התחרות.

הקריטריונים בהם נעזר חבר השופטים היו: בטיחות האלגוריתם, עלות החישוב ומדידת ביצועים ומאפיינים הקשורים במימוש. חבר השופטים ציין במפורש שאף אחד מהאלגוריתמים שנבחרו לשלב השני לא נשבר במלואו. NIST אפשרה למועמדים שעברו לשלב זה לבצע שינוים קלים (Tweaks) באלגוריתמים שהגישו אך לא כאלה שיהפכו התקפות קיימות לבטלות‏[3].

בדצמבר 2010 הגיעו לגמר חמשה מועמדים מובילים:

הקהילה הקריפטוגרפית הייתה מעורה בשיקולים וההתלבטות במהלך התחרות. הערות והצעות רבות נשלחו ל-NIST או לפורום הגיבוב שהוקם למטרה זו וכן פורסמו מאמרים אקדמיים של קריפטואנליזה של המועמדים על ידי מומחים בעלי שם מסביב לעולם. באוקטובר 2012 נסגרה התחרות עם ההכרזה על האלגוריתם הזוכה‏[4].

משפחת האלגוריתמים SHA-3 הוכנסה לתקן FIPS PUB 202‏[5] של NIST והיא כוללת שישה אלגוריתמים בגדלים שונים בהתאם, SHA3-224, SHA3-256, SHA3-384 ו-SHA3-512 וכן שתי פונקציות הרחבה הנקראות XOF והן SHAKE128, SHAKE256. תקן FIPS 202 אושר על ידי מנהל מחלקת המסחר של ארצות הברית באוגוסט 2015.

כל החישובים בפונקציית הגיבוב, מוגבלים לפעולות XOR, NOT, AND ורוטציה (Rotate) או הזזה מעגלית, ללא פעולות אריתמטיות או פונקציות המבוססות על מידע חיצוני. וכן אין צורך ליישם טבלאות חיפוש לצורך האצת החישובים. לפי הצהרת המפתחים נדרשים 12.5 מחזורי שעון לבית במעבד אינטל ליבה כפולה. בגרסת החומרה שלו האלגוריתם הפגין ביצועים טובים יותר מכל המועמדים האחרים.

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

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

תיאור המצב הפנימי של Keccak. נתיב (lane) הוא שורה אחת לאורך ציר ה-z

אלגוריתם Keccak (מבוטא קֵצַ'אק) פותח ב-2008 על ידי Guido Bertoni, Joan Daemen, Michaël Peeters ו-Glls Van Assche‏[6]. זוהי משפחה של פונקציות גיבוב המבוססת על פונקציית ספוג שהתגלתה במהלך פיתוח אלגוריתם RadioGatun. ב-Keccak הפונקציה הפנימית f היא פרמוטרציה אחת מתוך אוסף של שבע פרמוטציות אפשריות המסומנות \text{KECCAK-f}[b], כאשר b\in\{25,50,100,200,400,800,1600\} נקרא רוחב המצב הפנימי. המצב הפנימי בנוי כמערך תלת-ממדי בעל אורך ורוחב קבועים 5\times 5 נתיבים (lanes) בעומק משתנה w\in\{1,2,4,8,16,32,64\} כאשר b=25w כמתואר בתרשים. על מעבד 64 ביט נתיב (lane) ב-\text{KECCAK-f}[1600] ניתן לייצוג במילה אחת בגודל 64 סיביות. פונקציית הספוג \text{KECCAK-f}[r+c] מקבלת את הפרמטרים קצב (bitrate) המסומן r וכן קיבולת (capacity) המסומנת c. מפונקציה זו מתקבל מבנה ספוג יחד עם כלל ריפוד מתאים. כלל הריפוד הוא \text{pad}10^*1. כלומר תחילה מוסיפים סיבית "1" בסוף המסר, מרפדים באפסים ולבסוף מסיימים עם סיבית "1" נוספת, מספר האפסים הוא פונקציה של גודל הבלוק, כך שלבסוף יתקבל לפחות בלוק שלם או יותר באורך b סיביות.

הפונקציה \text{Round}[b](A, \text{RC})[עריכת קוד מקור | עריכה]

להלן פסאודו-קוד המתאר את פונקציית הסבב המקבלת מערך A המכיל את המצב הפנימי. מספר הסבבים הוא n_r בהתאם לאורך הבלוק והוא נתון על ידי n_r=12+2l כאשר 2^l=w. למשל עבור \text{KECCAK-f}[1600] מתקבלים 24 סבבים. כל הפעולות על האינדקסים בקוד הבא הם מודולו 5. הביטוי A[x,y] מתייחס לנתיב אחד במצב (ראה תרשים). B[x,y], X[x], D[x] הם משתנים זמניים. הקבועים r[x,y] הם היסטים של ההזזה המעגלית לפי הטבלה להלן. \text{RC}[i] הם קבועי סבב הנתונים בטבלה להלן. \text{ROT}(W,r) הוא פעולת הזזה מעגלית רגילה (cyclic shift) בסיביות כשההיסט הוא מודולו אורך הנתיב.


\mathbf{Round[b](A, \text{RC})}

\color{Blue}\boldsymbol{\theta}\text{ Step}

\text{For }x = 0\text{ to }4\text{ do}
C[x]=A[x,0]\oplus A[x,2]\oplus A[x,3]\oplus A[x,4]
\text{For }x = 0\text{ to }4\text{ do}
D[x]=C[x-1]\oplus ROT(C[x+1],1)
\text{For }x = 0\text{ to }4\text{ do}
\text{For }y = 0\text{ to }4\text{ do}
A[x,y]=A[x,y]\oplus D[x]

\color{Blue}\boldsymbol{\rho}\text{ and }\boldsymbol{\pi}\text{ Steps}

\text{For }x = 0\text{ to }4\text{ do}
\text{For }y = 0\text{ to }4\text{ do}
B[y,2\cdot x+3\cdot y]=\text{ROT}(A[x,y],r[x,y])

\color{Blue}\boldsymbol{\chi}\text{ Step}

\text{For }x = 0\text{ to }4\text{ do}
\text{For }y = 0\text{ to }4\text{ do}
A[x,y]=B[x,y]\oplus((\text{NOT }B[x+1,y])\text{ AND }B[x+2,y]

\color{Blue}\boldsymbol{\iota}\text{ Step}

A[0,0]=A[0,0]\oplus \text{RC} \text{Return }A

הפונקציה \text{KECCAK-f}[b](A)[עריכת קוד מקור | עריכה]

\mathbf{KECCAK-f[b](A)}

\text{For }i = 0\text{ to }n_r-1\text{ do}
A=\text{Round}[b](A,\text{RC}[i])
\text{Return }A

הפונקציה \mathbf{KECCAK[r,c](M)}[עריכת קוד מקור | עריכה]

להלן פסאודו-קוד המתאר את פונקציית הספוג \text{KECCAK}[r,c], עם הפרמטרים c ו-r (קצב וקיבולת) והמסר M, כאשר ההנחה לפי התקן היא ש-r הוא כפולה של אורך נתיב. הקוד מתייחס אל המידע ברמה של בתים, ברמה של סיבויות יש צורך בהתאמות נוספות. S מייצג את המצב כמערך של נתיבים. המסר המרופד P מאורגן כמערך דו ממדי של נתיבים. הסימן \| מייצג שרשור מחרוזות.

\mathbf{KECCAK[r,c](M)}

\color{Blue}\text{Initialization and padding}

\text{For }x = 0\text{ to }4\text{ do}
\text{For }y = 0\text{ to }4\text{ do}
S[x,y]=0
P=M \ \| \ \text{0x01} \ \| \ \text{0x00} \ \| \ ... \ \| \ \text{0x00}
P = P\oplus (\text{0x00} \ \| \ ... \ \| \ \text{0x00} \ \| \ \text{0x80})

\color{Blue}\text{Absorbing phase}

\text{Ror all blocks }P_i\text{ in }P\text{ do}
\text{For all }(x,y)\text{ such that }x+5\cdot y<r/w\text{ do}
S[x,y]=S[x,y]\oplus P_i[x+5*y]
S=\text{KECCAK-f}[r+c](S)

\color{Blue}\text{Squeezing phase}

\text{Loop:}
\text{For all }(x,y)\text{ such that }x+5\cdot y<r/w\text{ do}
Z=Z\ \| \ S[x,y]
S=\text{KECCAK-f}[r+c](S)
\text{Return }Z

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

קבועי הסבב \text{RC}[i] נתונים בטבלה הבאה עבור אורך מקסימלי של נתיב. עבור אורכים קצרים יותר פשוט חותכים את הערכים בהתאם.

RC[ 0] 0x0000000000000001 RC[12] 0x000000008000808B
RC[ 1] 0x0000000000008082 RC[13] 0x800000000000008B
RC[ 2] 0x800000000000808A RC[14] 0x8000000000008089
RC[ 3] 0x8000000080008000 RC[15] 0x8000000000008003
RC[ 4] 0x000000000000808B RC[16] 0x8000000000008002
RC[ 5] 0x0000000080000001 RC[17] 0x8000000000000080
RC[ 6] 0x8000000080008081 RC[18] 0x000000000000800A
RC[ 7] 0x8000000000008009 RC[19] 0x800000008000000A
RC[ 8] 0x000000000000008A RC[20] 0x8000000080008081
RC[ 9] 0x0000000000000088 RC[21] 0x8000000000008080
RC[10] 0x0000000080008009 RC[22] 0x0000000080000001
RC[11] 0x000000008000000A RC[23] 0x8000000080008008

ההיסטים עבור ההזזה המעגלית נתונים בטבלה הבאה.

x = 3 x = 4 x = 0 x = 1 x = 2
y = 2 25 39 3 10 43
y = 1 55 20 36 44 6
y = 0 28 27 0 1 62
y = 4 56 14 18 2 61
y = 3 21 8 41 45 15

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

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