Grøstl

Grøstl (גרוסטל) היא פונקציית גיבוב קריפטוגרפית שהייתה מועמדת ל-SHA-3 והייתה בין חמשת האלגוריתמים שעלו לגמר. Grøstl היא פונקציית גיבוב איטרטיבית ברמת בתים, עם זיכרון פנימי רחב (wide pipe), בסגנון רשת החלפה-תמורה בדומה ל-AES והיא למעשה משתמשת במספר מרכיבים דומים. פונקציית הכיווץ הפנימית בנויה משתי תמורות גדולות וקבועות שנבנו כך שתהיה להן עקבה רחבה באופן שאפשר להראות את עמידותן נגד התקפות קריפטואנליטיות שונות. יתרה מזו אם מניחים שהתמורות הפנימיות "אידיאליות" קיימת הוכחה לביטחון פונקציית הגיבוב. Grøstl באופן כללי מבוססת על עקרונות שונים למדי ממשפחת האלגוריתמים SHA והיא בעלת ביצועים טובים על מגוון פלטפורמות.

מוטיבציה ושיקולי פיתוח

פונקציית הגיבוב Grøstl פותחה ב-2011 על ידי Praveen Gauravaram, Lars Knudsen, Krystian Matusiewicz, Florian Mendel, Christian Rechberger, Martin Schläffer, ו-Søren S. Thomsen. המפתחים ממדינות שונות, דנמרק, פולין אוסטריה ובלגיה.
מקור השם Grøstl נובע משילוב של שתי שפות. Gröstl מתאר מאכל אוסטרי מסורתי, כאשר האות "ö" הוחלפה ב-"ø" שהיא מהאלפבית הדני, אותה מבטאים באופן דומה. ביטוי השם בשפות רבות קשה, במיוחד בגלל האות ø אותה אפשר להחליף בהלחם האותיות "oe". 
הפונקציה פותחה עקב הקריאה של NIST לפיתוח תקן חדש של פונקציות גיבוב קריפטוגרפיות שכונה SHA-3, בסוף 2008 הוכרזה התחרות שבה השתתפו מועמדים רבים ומתוכם רק חמשה הגיעו לקו הסיום ביניהם גרוסטל. באוקטובר 2012 נבחר קצ'אק מבין חמשת המועמדים המובילים לאלגוריתם הזוכה בתחרות. המארגנים הצהירו כי חמשת האלגוריתמים המובילים נבדקו היטב ונמצאו ראויים לשימוש ולא התגלו בהם פגמים רציניים.
השיקולים העיקריים שהנחו את המפתחים הם: פשטות המקלה על קריפטואנליזה, ביטחון מוכח (בתנאים מסוימים), עקרונות פיתוח ידועים ובדוקים, אי תלות בחומרה או בתוכנה, עמידות נגד התקפות קריפטואנליטיות ידועות והתקפות ערוץ צדדי, ביצועים טובים ותמיכה במקביליות.
בגלל העובדה שהמצב הפנימי של הצופן רחב הרבה יותר מהפלט בסיביות, התקפות גנריות כמו התקפת יום הולדת אינן ישימות. כמו כן התקפות שמנצלות תכונות מיוחדות בתמורות הפנימיות אינן אפקטיביות אלא רק במספר מועט של סבבים. חולשות בפונקציית הכיווץ לא בהכרח ניתנות לתירגום להתקפות יעילות נגד פונקציית הגיבוב עצמה ולא ידוע על התקפות יעילות כאלה למיטב ידיעת המפתחים.  
בניגוד לצופן בלוקים, התמורות הפנימיות אינן תלויות במפתח. גישה זו נועדה גם כדי להגן על הפונקציה מפני התקפות שמתמקדות בתהליך הכנת המפתח וגם לשיפור ביצועים כי תהליך הכנת המפתח עלול להוות צוואר בקבוק.

הזזת בתים

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

ריפוד

פונקציית הריפוד של Grøstl הנקראת כאן  דומה לזו שיושמה ב-MD5. בהינתן קלט באורך  סיביות, תחילה מוסיפים את הסיבית '1' בסופו ואז מוסיפים אפסים כנדרש כדי להשלימו לאורך המתחלק ב- פחות 64 סיביות. בניסוח רשמי מספר האפסים שיש להוסיף הוא . ב-64 הסיביות הנותרות מקודדים את הערך  המספר הזה יוצא תמיד שלם בגלל  והוא מייצג את מספר הבלוקים הסופי לאחר הריפוד. לאור זאת האורך המקסימלי של קלט הניתן לעיבוד על ידי Grøstl יכול להיות לכל היותר  בלוקים אחרת 64 סיביות לא יספיקו כדי לקודד את הערך האמור. עבור תמצית מסרים קצרה אורך הקלט המקסימלי הוא  ועבור תמצית מסרים ארוכה האורך המקסימלי הוא .

ביטחון ויעילות

Grøstl יכולה להגיע לתפוקה של 21.4 מחזורי שעון לבית על מעבד Intel Core 2. האלגוריתם הוא שילוב של מצב פנימי רחב (wide pipe) עם גרסה של מבנה מרקל-דמגרד משופרת (שבה מקצצים חלק מהפלט). בעקבות הניסיון המצטבר הוכח ששתי התכונות הללו מחזקות את האלגוריתם מפני התקפות קריפטואנליטיות שונות. זיכרון פנימי רחב עוזר נגד התקפות גנריות שמתמקדות באיטרציה של הפונקציה הפנימית. האלגוריתם מסתמך על שתי תמורות שונות, תחת ההנחה התאורטית שהתמורות הללו אקראיות המפתחים הוכיחו שהיתרון של מבחין לזיהוי בין פלט Grøstl לבין פלט אקראי אמיתי אינו גדול מ-, כאשר המבחין רשאי להגיש לכל היותר  שאילתות באורך לכל היותר  בלוקים. כמו כן אפשר לראות שיש חשיבות לפונקציה המסיימת בלעדיה קיימות התקפות מעשיות נגד האלגוריתם. כמו כן קיימות התקפות היעילות מכוח גס נגד גרסה מצומצמת של גורסטל בחמשה סבבים. 
המפתחים מונים ניתוח סדרה של התקפות קריפטואנליטיות ידועות והטענות שלהם לגבי הביטחון של Grøstl נגד התקפות אילו. בין ההתקפות הם מונים את: ההתקפה הדיפרנציאלית, התקפת ריבאונד, אנליזה ליניארית ואינטגרלית, התקפה אלגברית, התקפות התנגשויות ורב-התנגשויות, התקפת הארכה והתקפת נקודות שבת, התקפת יום הולדת וההתקפה של קלסי ושנייר על מבנה מרקל-דמגרד. הם מסכמים שביטחון האלגוריתם עם מספר סבבים מלא, נגד כל ההתקפות המתוארות הוא לכל הפחות בסדר גודל של . לכן אם הפלט הוא באורך 256 סיביות המשמעות היא ביטחון של  שזה המינימום הנדרש כיום.