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 הגיעו לגמר חמישה מועמדים מובילים:

Keccak
Skein
JH
Grøstl
BLAKE

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

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

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

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

Keccak

אלגוריתם Keccak (מבוטא קֵצַ'אק, על שם ריקוד באלינזי עתיק) פותח ב-2008 על ידי Guido Bertoni, Joan Daemen, Michaël Peeters ו-Gils Van Assche^[5]. זוהי משפחה של פונקציות גיבוב המבוססת על פונקציית ספוג שהיא מבנה גנרי שהומצא במהלך פיתוח אלגוריתם 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) בסיביות כשההיסט הוא מודולו אורך הנתיב. הביטוי ${\text{NOT}}$ פירושו אופרטור השלילה, הסימן $\oplus$ הוא XOR והסימן $\land$ מייצג AND.

$\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,1]\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 {\text{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])\land 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)$

פונקציית הסבב המתוארת מבוצעת $n_{r}$ פעמים על הקלט:

$\mathbf {KECCAK} {\text{-}}\mathbf {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{For 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\cdot 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

קישורים חיצוניים

cryptographic hash Algorithm Competition, באתר NIST
SHA-3 Zoo – אתר המרכז את המידע שנצבר לגבי כל אחד מהמועמדים בתחרות
אור דונקלמן, The Hitchhiker’s Guide to the SHA-3 Competition, מצגת מיום עיון בקריפטולוגיה שנערך בטכניון ב-4 ביולי 2012

הערות שוליים

^ ¹ ² NIST בחרה את הזוכה בתחרות אלגוריתם הגיבוב (SHA-3) - הודעה לעיתונות באתר NIST
^ תחרות פונקציית הגיבוב הקריפטוגרפית - תיאור כללי באתר NIST
^ תחרות SHA-3 - שלב 2, באתר NIST
^ SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions
^ The Keccak sponge function family

[תחרות-1] ¹ ² NIST בחרה את הזוכה בתחרות אלגוריתם הגיבוב (SHA-3) - הודעה לעיתונות באתר NIST

[2] תחרות פונקציית הגיבוב הקריפטוגרפית - תיאור כללי באתר NIST

[3] תחרות SHA-3 - שלב 2, באתר NIST

[4] SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions

[5] The Keccak sponge function family

[1]

[2]

[3]

[4]

[5]