הצגת המקור של הדף "Grøstl"

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

==מוטיבציה ושיקולי פיתוח==
פונקציית הגיבוב Grøstl{{הערה|Praveen Gauravaram, Lars R. Knudsen, Krystian Matusiewicz, Florian Mendel, Christian Rechberger, Martin Schläffer, and Søren S. Thomsen (2011-03-02), [http://www.groestl.info/Groestl.pdf Grøstl - a SHA-3 candidate]}} פותחה ב-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 נבחר [[SHA-3#Keccak|קצ'אק]] מבין חמשת המועמדים המובילים לאלגוריתם הזוכה בתחרות. המארגנים הצהירו כי חמשת האלגוריתמים המובילים נבדקו היטב ונמצאו ראויים לשימוש ולא התגלו בהם פגמים רציניים.

השיקולים העיקריים שהנחו את המפתחים הם: פשטות המקלה על קריפטואנליזה, ביטחון מוכח (בתנאים מסוימים), עקרונות פיתוח ידועים ובדוקים, אי תלות בחומרה או בתוכנה, עמידות נגד התקפות קריפטואנליטיות ידועות ו[[התקפת ערוץ צדדי|התקפות ערוץ צדדי]], ביצועים טובים ותמיכה ב[[חישוב מקבילי|מקביליות]].

בגלל העובדה שהמצב הפנימי של הצופן רחב הרבה יותר מהפלט בסיביות, התקפות גנריות כמו [[פונקציית גיבוב קריפטוגרפית#התקפת יום הולדת|התקפת יום הולדת]] אינן ישימות. כמו כן התקפות שמנצלות תכונות מיוחדות בתמורות הפנימיות אינן אפקטיביות אלא רק במספר מועט של סבבים. חולשות בפונקציית הכיווץ לא בהכרח ניתנות לתירגום להתקפות יעילות נגד פונקציית הגיבוב עצמה ולא ידוע על התקפות יעילות כאלה למיטב ידיעת המפתחים.

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

==תיאור האלגוריתם==
[[קובץ:Grostl scheme.png|560px|ממוזער|שמאל|מבנה כללי של פונקציית הגיבוב Grøstl]]
אלגוריתם '''גרוסטל''' הוא פונקציית גיבוב איטרטיבית ב[[שיטת מרקל-דמגרד|מבנה מרקל-דמגרד]] הפועלת ברמה של בתים, מקבלת מסר באורך כלשהו ומחזירה '''תמצית גיבוב''' באורך משתנה בין בית אחד ל-64 בתים לפי בחירת המשתמש. אורכים שונים של הפלט מבוטאים במספר המופיע לאחר השם, לדוגמה Grøstl-256 מחזירה מחרוזת באורך 256 סיביות או 32 בתים. הקלט <math>M</math> תחילה מרופד, לפי שיטת ריפוד שתובא בהמשך, באופן שיתחלק ל-<math>t</math> בלוקים שלמים באורך <math>\ell</math> סיביות כל אחד המסומנים <math>m_1,...,m_t</math>. האורך <math>\ell</math> מייצג את גודל הזיכרון הפנימי של האלגוריתם הנקרא '''מצב''' (state) וצריך להיות 512 סיביות עבור תמציות באורך של עד 256 סיביות או 1024 סיביות במידה שאורך התמצית המבוקשת גדול יותר. המבנה הכללי של האלגוריתם פשוט בתכלית כמתואר בתרשים משמאל. האלגוריתם מקבל וקטור אתחול <math>h_0=\text{iv}</math> באורך <math>\ell</math> סיביות ואת הבלוקים של הקלט ומעבד אותם בזה אחר זה:
:<math>h_i\longleftarrow f(h_{i-1},m_i)</math> כאשר <math>i=1</math> עד <math>t</math>.
בכל סבב של האלגוריתם פונקציית הכיווץ הפנימית <math>f</math> מקבלת שני קלטים באורך <math>\ell</math> סיביות כל אחד, הראשון הוא תוצאת הפונקציה מהסבב הקודם הנקראת '''ערך ביניים''' והשני נקרא '''בלוק מסר''' ומחזירה בלוק אחד <math>h_i</math> מסיבה זו היא נקראת פונקציית '''כיווץ'''. לאחר עיבוד כל הבלוקים התוצאה היא <math>h_t</math>. [[פלט]] האלגוריתם הסופי הוא <math>H(M)=\Omega(h_t)</math> כאשר <math>\Omega</math> היא פונקציה מסיימת שמקצצת (truncate) את הפלט לאורך הרצוי והיא מוגדרת להלן. הפלט שלה באורך <math>n</math> סיביות הוא תמצית המסר הסופית.

===פונקציית הכיווץ===
[[קובץ:Grostl f function.png|180px|ממוזער|שמאל|פונקציית הכיווץ הפנימית של Grøstl]]
פונקציית הכיווץ <math>f</math> השוכנת בלב האלגוריתם היא פונקציה מהצורה: <math>f:\{0,1\}^{\ell}\times\{0,1\}^{\ell}\longrightarrow\{0,1\}^{\ell}</math>
המבוססת על שתי תמורות פנימיות גדולות וקבועות הנקראות <math>P</math> ו-<math>Q</math> בהתאמה, באורך <math>\ell</math> סיביות כל אחת. שים לב שעבור תמצית באורך <math>n</math>, רוחב המצב הפנימי חייב להיות <math>\ell\ge 2n</math>. באופן פורמלי פונקציית הכיווץ מבצעת, כמתואר בתרשים משמאל:
:<math>f(h_{i-1},m_i)=P(h_{i-1}\oplus m_i)\oplus Q(m_i)\oplus h_{i-1}</math>.

===פונקציה מסיימת===
הפונקציה <math>\text{trunc}_n(x)</math> שהיא מעין פעולת "קיצוץ" שמחזירה רק את <math>n</math> הסיביות המסיימות של הקלט <math>x</math> ומתעלמת מכל היתר. הפונקציה המסיימת של האלגוריתם <math>\Omega</math> המתוארת בתרשים משמאל היא:
:<math>\Omega(x)=\text{trunc}_n(P(x)\oplus x)</math>.

===התמורות===
[[קובץ:Grostl omega function.png|220px|ממוזער|שמאל|תרשים הפונקציה <math>\Omega</math> של Grøstl]]
כאמור פונקציית הכיווץ הפנימית פועלת בשתי גרסאות, גרסת 512 סיביות עם התמורות: <math>P_{512}</math>, <math>Q_{512}</math>, עבור תמצית מסרים קצרה והשנייה גרסת 1024 סיביות עם התמורות <math>P_{1024}</math>, <math>Q_{1024}</math>, עבור תמצית ארוכה. כל גרסה משתמשת בזוג תמורות <math>P</math> ו-<math>Q</math> אחרות. כך שבסך הכול קיימות ארבע תמורות שונות. התמורות הן בהשראת [[צופן בלוקים|צופן הבלוקים]] AES, כלומר כל אחת מהן מורכבת למעשה מ-<math>R</math> סבבים שבכל אחד מהם מתבצעות ארבע פעולות ערבוב ופיזור שונות בהתאם לטבלאות קבועות. היות שהמצב הפנימי גדול בהרבה מזה של AES היה צורך לחשב מחדש את ערכיהן. הפעולות של התמורות הן:
*'''הוספת קבועים'''
*'''החלפת בתים'''
*'''הזזת בתים'''
*'''ערבוב בתים'''

הפעולה הראשונה והשלישית משתנות בהתאם לאורך התמצית המבוקשת ואילו האחרות זהות. מספר הסבבים נקבע גם הוא לפי אורך התמצית המבוקשת. עבור תמצית בטווח [8-256] סיביות נדרשים עשרה סבבים ועבור תמצית בטווח [264-512] נדרשים 14 סבבים. סדר הפעולות מוגדר באופן פורמלי על ידי:
:<math>R=\text{MixBytes}\circ\text{ShiftBytes}\circ\text{SubBytes}\circ\text{AddRoundConstants}</math>.
כל הפעולות מבוצעות על המצב הפנימי המיוצג כמערך דו־ממדי של בתים או [[מטריצה]] מסדר <math>8\times v</math> בתים. <math>v</math> מייצג את מספר העמודות והוא שווה 8 או 16 בהתאם לגודל המצב הפנימי. עבור תמצית מסרים עד 256 סיביות <math>v=8</math> בתים ואילו עבור תמצית ארוכה יותר <math>v=16</math> בתים. ההמרה ממערך בתים למטריצה ובחזרה נייטרלית מהיבט של [[סדר בתים|סדר הבתים]], אולם יש צורך לציין במפורש כיצד מערך של 64 בתים ממופה למטריצה <math>A</math> וההפך. אם נמספר את כניסות 64 הבתים של המערך מ-00 עד <math>\text{3f}</math> ב[[בסיס הקסדצימלי]] הרי שהמיפוי מתבצע כמתואר בתרשים הבא:
<center>
<math>
\begin{bmatrix}
\text{00} & \text{08} & \text{10} & \text{18} & \text{20} & \text{28} & \text{30} & \text{38} \\
\text{01} & \text{09} & \text{11} & \text{19} & \text{21} & \text{29} & \text{31} & \text{39} \\
\text{02} & \text{0a} & \text{12} & \text{1a} & \text{22} & \text{2a} & \text{32} & \text{3a} \\
\text{03} & \text{0b} & \text{13} & \text{1b} & \text{23} & \text{2b} & \text{33} & \text{3b} \\
\text{04} & \text{0c} & \text{14} & \text{1c} & \text{24} & \text{2c} & \text{34} & \text{3c} \\
\text{05} & \text{0d} & \text{15} & \text{1d} & \text{25} & \text{2d} & \text{35} & \text{3d} \\
\text{06} & \text{0e} & \text{16} & \text{1e} & \text{26} & \text{2e} & \text{36} & \text{3e} \\
\text{07} & \text{0f} & \text{17} & \text{1f} & \text{27} & \text{2f} & \text{37} & \text{3f}
\end{bmatrix}</math>
</center>
עבור המטריצה הגדולה <math>8\times 16</math> בתים, הרעיון דומה. בתי המערך מסודרים מלמעלה למטה החל מהעמודה השמאלית ימינה.

===הוספת קבועי סבב===
בשלב זה מחברים ב-[[XOR]] את קבועים המובאים להלן בהתאם למספר הסבב עם המטריצה <math>A</math>. בניסוח רשמי עבור סבב <math>i</math> החל מאפס, מעדכנים את המטריצה כך:
:<math>A\leftarrow A\oplus C[i]</math>.
כאשר <math>C[i]</math> הוא קבוע תלוי סבב המתאים לסבב <math>i</math>. לתמורות <math>P</math> ו-<math>Q</math> יש קבועים שונים. הקבועים עבור מצב פנימי של 512 סיבית בבסיס הקסדצימלי, הם:

<center>
<math>P_{512}:C[i]=\begin{bmatrix}
00 \oplus i & 10 \oplus i & 20 \oplus i & 30 \oplus i & 40 \oplus i & 50 \oplus i & 60 \oplus i & 70 \oplus i \\
00 & 00 & 00 & 00 & 00 & 00 & 00 & 00 \\
00 & 00 & 00 & 00 & 00 & 00 & 00 & 00 \\
00 & 00 & 00 & 00 & 00 & 00 & 00 & 00 \\
00 & 00 & 00 & 00 & 00 & 00 & 00 & 00 \\
00 & 00 & 00 & 00 & 00 & 00 & 00 & 00 \\
00 & 00 & 00 & 00 & 00 & 00 & 00 & 00 \\
00 & 00 & 00 & 00 & 00 & 00 & 00 & 00
\end{bmatrix}</math>

<math>Q_{512}:C[i]=\begin{bmatrix}
\text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} \\
\text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} \\
\text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} \\
\text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} \\
\text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} \\
\text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} \\
\text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} \\
\text{ff} \oplus i & \text{ef} \oplus i & \text{df} \oplus i & \text{cf} \oplus i & \text{bf} \oplus i & \text{af} \oplus i & \text{9f} \oplus i & \text{8f} \oplus i
\end{bmatrix}</math>

</center>
באופן דומה הקבועים עבור מצב פנימי גדול הם:

<center>
<math>P_{1024}:C[i]=\begin{bmatrix}
00 \oplus i & 10 \oplus i & 20 \oplus i & 30 \oplus i & 40 \oplus i & 50 \oplus i & 60 \oplus i & 70 \oplus i & \cdots & \text{f0} \oplus i \\
00 & 00 & 00 & 00 & 00 & 00 & 00 & 00 & \cdots & 00 \\
00 & 00 & 00 & 00 & 00 & 00 & 00 & 00 & \cdots & 00 \\
00 & 00 & 00 & 00 & 00 & 00 & 00 & 00 & \cdots & 00 \\
00 & 00 & 00 & 00 & 00 & 00 & 00 & 00 & \cdots & 00 \\
00 & 00 & 00 & 00 & 00 & 00 & 00 & 00 & \cdots & 00 \\
00 & 00 & 00 & 00 & 00 & 00 & 00 & 00 & \cdots & 00 \\
00 & 00 & 00 & 00 & 00 & 00 & 00 & 00 & \cdots & 00
\end{bmatrix}</math>

<math>Q_{1024}:C[i]=\begin{bmatrix}
\text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \cdots & \text{ff} \\
\text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \cdots & \text{ff} \\
\text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \cdots & \text{ff} \\
\text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \cdots & \text{ff} \\
\text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \cdots & \text{ff} \\
\text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \cdots & \text{ff} \\
\text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \text{ff} & \cdots & \text{ff} \\
\text{ff} \oplus i & \text{ef} \oplus i & \text{df} \oplus i & \text{cf} \oplus i & \text{bf} \oplus i & \text{af} \oplus i & \text{9f} \oplus i & \text{8f} \oplus i & \cdots & \text{0f} \oplus i
\end{bmatrix}</math>

</center>

===החלפת בתים===
ההחלפה מתבצעת על המצב הפנימי בית אחר בית לפי תיבות החלפה קבועות הנקראות S-box. תיבות אילו זהות ל[[AES#תיבות ההחלפה של ריינדל|תיבות ההחלפה של ריינדל]]. כך שאם <math>a_{i,j}</math> הוא אלמנט בשורה <math>i</math> ובעמודה <math>j</math> של המטריצה <math>A</math> טרנספורמציית ההחלפה SubBytes מתבצעת כדלהלן:
:<math>a_{i,j}=S(a_{i,j}), 0\le i<8, 0\le j<v</math>.

===הזזת בתים===
הזזת בתים, ליתר דיוק '''הזזת בתים מעגלית''' מתבצעת באופן שונה בהתאם לסוג המצב הפנימי. כמו בריינדל, שורות המצב מוסטות באופן מעגלי, כל אלמנט מועתק לאמנט שמשמאלו והאלמנט האחרון מועתק לאלמנט הראשון בתנועה מעגלית כמו בשעון. אם הווקטור <math>\sigma=[\sigma_0,\sigma_1\,...,\sigma_7]</math> הוא רשימה של שלמים בטווח שבין 0 ל-<math>v-1</math> אז ההזזה ShiftBytes מזיזה את כל הבתים שבשורה ה-<math>i</math> של מטריצת המצב <math>\sigma_i</math> צעדים או פוזיציות לשמאל ומחזירה את הבתים ששנפלטו מצד אחד לצד השני. עבור התמורה <math>P</math> הווקטור הוא <math>\sigma=[0,1,2,3,4,5,6,7]</math>, כלומר השורה הראשונה אינה מוסטת כלל, השנייה מוסטת בפוזיציה אחת, השלישית בשתי פוזיציות וכן הלאה. ואילו עבור <math>Q</math> הווקטור הוא <math>\sigma=[1,3,5,7,0,2,4,6]</math>. במצב הפנימי הרחב משתמשים בוקטור אחר כי קיימות יותר עמודות. במקרה זה וקטורי ההזזות עבור <math>P</math> ו-<math>Q</math> הם <math>\sigma=[0,1,2,3,4,5,6,11]</math> וכן <math>\sigma=[1,3,5,11,0,2,4,6]</math> בהתאמה.

===ערבוב בתים===
בפעולת הערבוב כל עמודה של המטריצה <math>A</math> מעובדת בנפרד. פעולה זו היא פעולה ב[[שדה סופי|שדה הסופי]] <math>\mathbb{F}_{256}</math> וכמו בצופן ריינדל השדה מוגדר על ידי [[פולינום אי פריק|הפולינום האי-פריק]] <math>x^8+x^4+x^3+x+1</math> מעל <math>\mathbb{F}_2</math>. הבתים של העמודה ה-<math>i</math> נחשבים לאלמנטים בשדה ופעולות הכפל והחיבור בין אלמנטים אילו מתבצעת לפי כללי האריתמטיקה בשדה הבינארי המורחב <math>{F}_{2^8}</math>. כלומר האלמנטים נחשבים לפולינומים מדרגה 7 עם מקדמים אפס או אחד, הסיבית המשמעותית ביותר מייצגת את המקדם המוביל ואילו הסיבית הכי פחות משמעותית מייצגת את המקדם החופשי והכפל והחיבור הם על המקדמים כנהוג בפולינומים. ביתר פירוט ראה [[AES#צופן ריינדל|צופן ריינדל]].

הטרנספורמציה MixBytes מכפילה כל עמודה של המטריצה <math>A</math> במטריצה קבועה <math>B</math> מסדר <math>8\times 8</math>. כל התהליך יכול להתפרש ככפל מטריצות הבא:
:<math>A\leftarrow B\times A</math>.
והמטריצה <math>B</math> היא '''מטריצה מעגלית''', שפירושה הוא שכל שורה שווה לשורה שמעליה כשהי מוסטת באופן מעגלי צעד אחד לימין:

<center>
<math>B=\begin{bmatrix}
02 & 02 & 03 & 04 & 05 & 03 & 05 & 07 \\
07 & 02 & 02 & 03 & 04 & 05 & 03 & 05 \\
05 & 07 & 02 & 02 & 03 & 04 & 05 & 03 \\
03 & 05 & 07 & 02 & 02 & 03 & 04 & 05 \\
05 & 03 & 05 & 07 & 02 & 02 & 03 & 04 \\
04 & 05 & 03 & 05 & 07 & 02 & 02 & 03 \\
03 & 04 & 05 & 03 & 05 & 07 & 02 & 02 \\
02 & 03 & 04 & 05 & 03 & 05 & 07 & 02
\end{bmatrix}</math>
</center>

אפשר לתאר את המטריצה בכתיב מקוצר: <math>B=\text{circ}(2,2,3,4,5,3,5,7)</math> כאשר הפונקציה <math>\text{circ}</math> היא פונקציית [[הזזה מעגלית]].

===קבועים התחלתיים===
[[וקטור אתחול|וקטור האתחול]] <math>\text{iv}_n</math> עבור Grøstl-n כאשר <math>n</math> מייצג את אורך התמצית המבוקשת, הוא הייצוג הבינארי של <math>n</math> במשתנה באורך <math>\ell</math> סיביות. בטבלה הבאה מופיעים הערכים ההתחלתיים עבור תמציות באורכים 224,256,384,512 בבסיס הקסדצימלי:
<center>
{| class="wikitable" dir="ltr"
|-
! <math>n</math> !! <math>\text{iv}_n</math>
|-
| <math>224</math> || <math>00 \cdots 00 00 \text{e0}</math>
|-
| <math>256</math> || <math>00 \cdots 00 01 00</math>
|-
| <math>384</math> || <math>00 \cdots 00 01 80</math>
|-
| <math>512</math> || <math>00 \cdots 00 02 00</math>
|}
</center>

===ריפוד===
פונקציית הריפוד של Grøstl הנקראת כאן <math>x^*=\text{pad}(x)</math> דומה לזו שיושמה ב-[[MD5]]. בהינתן [[קלט]] באורך <math>N</math> סיביות, תחילה מוסיפים את הסיבית '1' בסופו ואז מוסיפים אפסים כנדרש כדי להשלימו לאורך המתחלק ב-<math>\ell</math> פחות 64 סיביות. בניסוח רשמי מספר האפסים שיש להוסיף הוא <math>w=-N-65\text{ mod }\ell</math>. ב-64 הסיביות הנותרות מקודדים את הערך <math>(N+w+65)/\ell</math> המספר הזה יוצא תמיד שלם בגלל <math>w</math> והוא מייצג את מספר הבלוקים הסופי לאחר הריפוד. לאור זאת האורך המקסימלי של קלט הניתן לעיבוד על ידי Grøstl יכול להיות לכל היותר <math>2^{64}-1</math> בלוקים אחרת 64 סיביות לא יספיקו כדי לקודד את הערך האמור. עבור תמצית מסרים קצרה אורך הקלט המקסימלי הוא <math>512\cdot (2^{64}-1)-65=2^{73}-577</math> ועבור תמצית מסרים ארוכה האורך המקסימלי הוא <math>1024\cdot(2^{64}-1)-65=2^{74}-1089</math>.

==ביטחון ויעילות==
Grøstl יכולה להגיע לתפוקה של 21.4 מחזורי שעון לבית על מעבד [[Intel Core 2]]. האלגוריתם הוא שילוב של מצב פנימי רחב (wide pipe) עם גרסה של [[שיטת מרקל-דמגרד|מבנה מרקל-דמגרד]] משופרת (שבה מקצצים חלק מהפלט). בעקבות הניסיון המצטבר הוכח ששתי התכונות הללו מחזקות את האלגוריתם מפני התקפות קריפטואנליטיות שונות. זיכרון פנימי רחב עוזר נגד התקפות גנריות שמתמקדות באיטרציה של הפונקציה הפנימית. האלגוריתם מסתמך על שתי תמורות שונות, תחת ההנחה התאורטית שהתמורות הללו אקראיות המפתחים הוכיחו שהיתרון של מבחין לזיהוי בין פלט Grøstl לבין פלט אקראי אמיתי אינו גדול מ-<math>O((Kq)^4/2^{\ell})</math>, כאשר המבחין רשאי להגיש לכל היותר <math>q</math> שאילתות באורך לכל היותר <math>K</math> בלוקים. כמו כן אפשר לראות שיש חשיבות לפונקציה המסיימת בלעדיה קיימות התקפות מעשיות נגד האלגוריתם. כמו כן קיימות התקפות היעילות מ[[כוח גס]] נגד גרסה מצומצמת של גרוסטל בחמישה סבבים{{הערה|[https://eprint.iacr.org/2014/305.pdf Collision Attack on 5 Rounds of Grøstl]}}.

המפתחים מונים ניתוח סדרה של התקפות קריפטואנליטיות ידועות והטענות שלהם לגבי הביטחון של Grøstl נגד התקפות אילו. בין ההתקפות הם מונים את: [[קריפטאנליזה דיפרנציאלית|ההתקפה הדיפרנציאלית]], התקפת ריבאונד, אנליזה [[קריפטאנליזה ליניארית|ליניארית]] ואינטגרלית, התקפה אלגברית, התקפות התנגשויות ורב-התנגשויות, התקפת הארכה והתקפת [[נקודת שבת|נקודות שבת]], [[פונקציית גיבוב קריפטוגרפית#התקפת יום הולדת|התקפת יום הולדת]] וההתקפה של [[שיטת מרקל-דמגרד#התקפת נקודת שבת|קלסי ושנייר]] על מבנה מרקל-דמגרד. הם מסכמים שביטחון האלגוריתם עם מספר סבבים מלא, נגד כל ההתקפות המתוארות הוא לכל הפחות בסדר גודל של <math>2^{n/2}</math>. לכן אם הפלט הוא באורך 256 סיביות המשמעות היא ביטחון של <math>2^{128}</math> שזה המינימום הנדרש כיום.

==ראו גם==
* [[SHA-3]]
* [[AES]]
* [[שיטת מרקל-דמגרד]]

==הערות שוליים==
{{הערות שוליים|יישור=שמאל}}

{{קריפטוגרפיה}}

[[קטגוריה:פונקציות גיבוב קריפטוגרפיות]]
[[קטגוריה:קריפטוגרפיה]]