פונקציית ספוג

בקריפטוגרפיה, פונקציית ספוג (sponge function) היא דרך להרחיב פונקציית גיבוב לפונקציה קריפטוגרפית כללית שהקלט והפלט שלה באורך משתנה. פונקציית ספוג מיישמת מבנה ספוג (sponge structure) שהוא מבנה איטרטיבי פשוט המבוסס על תמורה או טרנספורמציה פנימית הפועלת על קלט באורך קבוע, שמקבל קלט באורך משתנה ומפיק פלט באורך משתנה. פונקציית ספוג מאד גמישה ויכולה לשמש כצופן זרם שבו נדרש קלט קצר ופלט ארוך או כפונקציית גיבוב וקוד אימות מסרים שבהם הקלט ארוך והפלט קצר. מהיבט תיאורתי פונקציית ספוג משמשת כמודל למבנה קונקרטי של פונקציית גיבוב עם גישה לזיכרון פנימי. פונקציית ספוג אקראית מקבילה לאורקל אקראי, למעט אפקט הזיכרון הסופי (התנגשויות הן בלתי נמנעות). לכן יכולה לשמש כחלופה למודל אורקל אקראי כדי לבטא טענת ביטחון.

רקע

הרעיון נולד במהלך פיתוח RadioGatun שהיא פונקציית גיבוב המקבלת קלט באורך שרירותי ומפיקה פלט בכל אורך רצוי. המפתחים נתקלו בבעיה בניסיון לבטא את ביטחון האלגוריתם במונחים של סיבוכיות זמן. כאשר הפלט קבוע אפשר לטעון שפונקציית הגיבוב טובה לפחות כאורקל אקראי שהפלט שלו נחתך ל-$n$ סיביות. לכן בגלל התקפת יום הולדת סיבוכיות התקפה בסיסית למציאת התנגשות היא מסדר גודל של $2^{n/2}$. אולם כאשר הפלט באורך משתנה אין לטענה זו משמעות, כביכול אפשר להגיע לביטחון אינסופי אם מאריכים את הפלט מאוד. לכן המפתחים הגיעו למודל שונה שבו מצהירים ביטחון במונחים של אורקל אקראי שנקרא כאן "פונקציית ספוג אקראית", שהוא מבנה תאורטי כמו אורקל אקראי למעט העובדה שהוא מוגבל בזיכרון לכן התנגשויות בלתי נמנעות. הממצאים פורסמו לראשונה ב-2007 בסמינר Dugstuhl בגרמניה ולאחר מכן בסדנת Ecrypt בברצלונה.

פונקציית ספוג התגלתה ככלי יעיל לבניית פרימיטיבים קריפטוגרפיים רבים. אפשר לנצל מבנה ספוג ותאומו הנקרא "מבנה דופלקס" (duplex construction), כדי ליישם מגוון רחב של פרימיטיבים קריפטוגרפיים, כולל פונקציית גיבוב, מחולל פסאודו-אקראי, הצפנה סימטרית, אימות מסרים והצפנה מאומתת, עם ובלי וקטור אתחול ובאורכים משתנים לפי לצורך. בדרך זו נהנים מפונקציונליות רבה בפונקציית תמורה יחידה ומפשטים את תהליך הפיתוח והיישום מבלי לדאוג למרכיבים אחרים כמו תהליך הכנת מפתח. האטרקטיביות של מבנה זה נובעת מהעובדה שאפשר להתבסס על פרמוטציה מתאימה שזה יותר קל מלפתח צופן בלוקים או פונקציית דחיסה. קיימים כמה אלגוריתמים חדשים שמסתמכים על מבנה ספוג מהם Keccak, Quark, Photon, Spongent וכן Spritz. מראה כללי של מבנה ספוג הוא:

${\boldsymbol {P\ =\ M\ \|\ \mathbf {pad} [r](|M|)}}$ ${\boldsymbol {s\ =\ \mathbf {ABSORB} [f,r](P)}}$ ${\boldsymbol {Z\ =\ \mathbf {SQUEEZE} [f,r](s,\ell )}}$

הסימן $\|$ מייצג שרשור. תחילה הקלט $M$ מרופד לפי כלל ריפוד מתאים (בהמשך), לאחר מכן התוצאה $P$ נספגת לתוך המצב הפנימי $s$ באמצעות הפונקציה הפנימית $f$ באורך $r$ סיביות. היא יכולה להיות כל PRP או PRF בטוח לפי בחירה. ואז הפלט $Z$ נסחט בהתאם לאורך הרצוי $\ell$, הפלט יכול לשמש כמפתח הצפנה או ערך גיבוב. באופן כללי אמור להיות קשה למצוא מסלול מ-$s$ ל-$P$. התנגשות פירושה ש-${\text{ABSORB}}(P)={\text{ABSORB}}(Q)$ כאשר $P\neq Q$ וכן אם מתקבל ${\text{ABSORB}}(P)={\text{ABSORB}}(P\ \|\ 0^{dr})$ פירושו שהמבנה מכיל מעגליות ולכן הפלט יחזור על עצמו.

כלל ריפוד

היות שהקלט באורך משתנה יש להפעיל כלל ריפוד מתאים כדי לחלק את הקלט ל-$x$ בלוקים בגודל $b$ סיביות כל אחד, באופן שיהיה קל להסיר את הריפוד עם קבלת המסר בצד השני מבלי לדעת מה היה אורך המסר. סכמת הריפוד הפשוטה והנפוצה ביותר היא ${\text{pad}}10^{*}$ כלומר מוסיפים את הסיבית "1" בסוף הקלט ומרפדים באפסים, כאשר הכוכבית מציינת שמספר האפסים הנדרש תלוי באורך הקלט ובגודל הבלוק, כך שהאורך הכולל צריך להתחלק ב-$b$. כלל הריפוד חייב לקיים שלושה תנאים:

• הריפוד צריך להיות קל להסרה.
• מחרוזת הריפוד לא יכולה להיות ריקה.
• הבלוק האחרון חייב להיות שונה מאפס.

הסימון של כלל הריפוד עבור בלוק באורך $x$ סיביות מסומן בקיצור: $M\ \|\ {\text{pad}}[x](|M|)$

מבנה ספוג

פונקציית ספוג

מבנה ספוג הוא מבנה איטרטיבי פשוט ליצירת פונקציה ${\text{SPONGE}}[f,{\text{pad}},r](M,\ell )$ המקבלת קלט מהתחום $\mathbb {Z} _{2}^{*}$ ומפיקה פלט בטווח $\mathbb {Z} _{2}^{\infty }$. היא מבוססת על תמורה או טרנספורמציה $f$ הפועלת על $b$ סיביות. $b$ קבוע ונקרא כאן רוחב. הוא כולל מצב פנימי (זיכרון) באורך $b=r+c$ סיביות, כאשר $r$ נקרא "קצב" (bitrate) ו-$c$ נקרא "קיבולת" (capacity). המצב הפנימי מאותחל באפסים, הקלט מרופד כאמור ומחולק לבלוקים של $r$ סיביות ומשם ממשיכים בשני שלבים:

• שלב הספיגה, בשלב זה הבלוקים של הקלט מועברים בפונקציה $f$ ומשולבים ב-XOR עם $r$ הסיביות הראשונות של המצב הפנימי. כאשר מסיימים לקלוט את כל הבלוקים עוברים לשלב הבא.
• שלב הסחיטה. בשלב זה $r$ הסיביות הראשונות של המצב מועברות שוב בפונקציה $f$ והתוצאה מוחזרת למשתמש. מספר הבלוקים שהפונקציה מחזירה תלוי במשתמש.

הסימון $\left\lfloor \cdot \right\rfloor _{\ell }$ פירושו שאת פלט הפונקציה חותכים ל-$\ell$ הסיביות הראשונות. כאשר $c$ הסיביות הנותרות של המצב לעולם לא מושפעות מבלוקים של הקלט ולעולם אינן נכללות בפלט במהלך הסחיטה.

להלן פסאודו-קוד המתאר מבנה הספוג:

$\mathbf {SPONGE} [f,{\text{pad}},r]$

$P=M\ \|\ {\text{pad}}[r](|M|)$

$s=0^{b}$

${\text{For }}i=0{\text{ to }}{|P|}_{r}-1{\text{ do}}$

$s=s\oplus P_{i}\ \|\ 0^{b-r}$

$s=f(s)$

$Z=\left\lfloor s\right\rfloor _{r}$

${\text{While }}|Z|_{r}r<\ell {\text{ do}}$

$s=f(s)$

$Z=Z\ \|\ \left\lfloor s\right\rfloor _{r}$

${\text{Return }}\left\lfloor Z\right\rfloor _{\ell }$

מודל ביטחון

בפונקציית גיבוב עם פלט קבוע מקובל היה בדרך כלל להשוותה מול אורקל אקראי, אולם זה השתנה בעקבות גילויים חדשים בעשור האחרון. יש לזכור שהיות שהמצב הפנימי סופי והפונקציה איטרטיבית - היא מעבדת את הקלט בלוק אחר בלוק, בהכרח שיהיו התנגשויות, זאת לעומת אורקל אקראי תאורטי שאצלו לא קיים מושג "מצב" ואין לו התנגשויות. מסיבה זו אי אפשר להשוות ישירות למודל אורקל אקראי. אלטרנטיבה טובה למודל אורקל אקראי בהקשר זה היא מבנה ספוג אקראי שהוא מבנה תאורטי שהפונקציה הפנימית שלו $f$ היא פרמוטציה אקראית שנבחרה באופן אחיד מטווח הפרמוטציות האפשריות מעל $b$ סיביות. למעט כמובן האפקט שנובע עקב מגבלת הזיכרון הסופי. מהיבט תאורטי כשמנתחים ביטחון פונקציית ספוג לפי מודל זה מביאים בחשבון גם את הפרמטרים קצב וקיבולת. במצב אידאלי אומרים שביטחון הפונקציה הוא במונחים של הקיבולת $c$, כלומר התקפה גנרית שאינה מנצלת חולשות ספציפיות בפונקציה הפנימית תהיה בסיבוכיות $2^{c/2}$ לפחות. במילים אחרות מוכיחים שכל התקפה מוצלחת נגד המבנה עצמו משליכה בהכרח שניתן להבחין בין תוצאת הפרמוטציה שהמבנה משתמש בה לבין מחרוזת אקראית ומכאן שהיא אינה טובה לשימוש.

מבנה דופלקס

פונקציית ספוג

באופן דומה מבנה ${\text{DUPLEX}}[f,{\text{pad}},r]$ משתמש בטרנספורמציה או תמורה פנימית $f$, כלל ריפוד מתאים ופרמטר $r$. אך בשונה מפונקציית ספוג שהיא חסרת מצב בין הקריאות לפונקציה, מבנה דופלקס הוא אובייקט שיכול לקבל קלט נוסף ולהפיק מחרוזת פלט שהיא תוצאה של הקלט שהתקבל עד כה. במילים אחרות מבנה דופלקס דומה לרצף קריאות חוזרות של פונקציית ספוג עם קלט שונה. אובייקט דופלקס מכיל מצב בגודל $b$ סיביות, בשלב האתחול המצב הפנימי מאופס, ומכאן ואילך אפשר להפעיל את הפונקציה ${\text{D.duplexing}}(\sigma ,\ell )$ שוב ושוב עם קלט $\sigma$ שאורכו צריך להיות קצר מספיק כדי שיתקבל בלוק אחד לאחר ריפוד. הפלט הוא באורך $\ell$ שהוא לכל היותר $r$ סיביות. בכל קריאה המבנה תחילה מרפד את הקלט לפי כלל הריפוד שנבחר, מחבר את הקלט ב-XOR עם חלק החיצוני של המצב הפנימי ואז מיישם את הפונקציה $f$ על המצב ומחזיר את $\ell$ הסיביות הראשונות של המצב. הוכח שמבנה דופלקס בטוח כמבנה ספוג, היות שמבנה דופלקס בעצם מקביל למבנה ספוג שהקלט שלו חולק למקטעים בגודל $\sigma$ שכל אחד מהם מרופד בנפרד ואז הם משורשרים לרצף אחד ארוך. להלן תיאור מבנה דופלקס:

$\mathbf {DUPLEX} [f,{\text{pad}},r]$

$\mathbf {D.initialize}$

$s=0^{b}$

$\mathbf {D.duplexing} (\sigma ,\ell ){\text{ with }}\ell \leq r$

$P=\sigma \ \|\ {\text{pad}}[r](|\sigma |)$

$s=s\oplus (P\ \|\ 0^{b-1})$

$s=f(s)$

${\text{Return }}\left\lfloor s\right\rfloor _{\ell }$

הצפנה מאומתת

ערך מורחב – הצפנה מאומתת

הצפנה מאומתת היא דרך להצפין ולאמת מידע יחד עם מידע נלווה המשויך אליו אם ישנו. הרעיון שימושי במיוחד בפרוטוקול תקשורת שבו חלק מחבילת מידע אמור להיות סודי בעוד שחלק אחר שנקרא בהקשר זה כותר (header) אמור להישאר קריא (משמש את השרת המקבל). המצפין רוצה להבטיח מלבד סודיות שהמסר והמידע הנלווה אליו אותנטיים וכי לא שונו על ידי גורם זר או בשל תקלה בשידור, באופן שמסכן את החלק הסודי של החבילה. אפשר ליישם הצפנה מאומתת באמצעות מבנה דופלקס. האובייקט SpongeWrap להלן, משתמש באובייקט דופלקס D עם הפרמטרים $f,{\text{pad}},r$ אותו הוא מאתחל ומעביר אליו את המפתח $K$. כדי להצפין ולאמת קוראים לפונקציה W.wrap עם הפרמטרים $A,B,\ell$ כאשר $A$ הוא המידע הנלווה, $B$ הוא המסר המיועד להצפנה והפרמטר $\ell$ מייצג את אורך תג האימות בסיביות. הפונקציה מחזירה את הטקסט המוצפן $C$ שהוא $C_{i}=B_{i}\oplus Z_{i}$ כאשר $Z_{i}$ הוא הערך החוזר מהפונקציה duplexing ואת תג האימות $T$. לפענוח קוראים לפונקציה W.unwrap עם הפרמטרים $A,C,T$ והיא אמורה להחזיר את $B$ או "Error" אם אחד הערכים אינו תקין. לפני הקריאה לאובייקט D לביצוע duplexing תחילה מרפדים את כל האלמטים בסיבית אחת נוספת שנקראת frame-bit (1 חוץ מהבלוק האחרון). הערך $\rho$ נקרא קצב והוא קובע את גודל הבלוק, כלומר כמות הסיביות שאפשר להצפין ולאמת בקריאה אחת. לכן הערך המקסימלי שלו הוא $\rho _{\text{max}}({\text{pad}},r)-1$ כי יש להביא בחשבון את הסיבית הנוספת. להלן תיאור האלגוריתם:

$\mathbf {SpongeWrap} [f,{\text{pad}},\rho ]$

‎

${\text{W.initialize}}(K),{\text{ with }}K\in \mathbb {Z} _{2}^{*}$

${\text{Let }}K=K_{0}\ \|\ K_{1}\ \|\ ...\ \|\ K_{u}{\text{ with }}|K_{i}|=\rho {\text{ for }}i<u,|K_{u}|\leq \rho ,|K_{u}|>0{\text{ if }}u>0$

${\text{D.initialize}}()$

${\text{for }}i=0{\text{ to }}u-1{\text{ do}}$

${\text{D.duplexing}}(K_{i}\ \|\ 1,0)$

${\text{D.duplexing}}(K_{u}\ \|\ 0,0)$

‎

$\mathbf {W.wrap} (A,B,\ell ){\text{ with }}A,B\in \mathbb {Z} _{2}^{*},\ell \geq 0$

${\text{Let }}A=A_{0}\ \|\ A_{1}\ \|\ A_{v}{\text{ with }}|A_{i}|=\rho {\text{ for }}i<v{\text{ and }}|A_{v}|\leq \rho ,|A_{v}|>0{\text{ if }}v>0$

${\text{Let }}B=B_{0}\ \|\ B_{1}\ \|\ B_{w}{\text{ with }}|B_{i}|=\rho {\text{ for }}i<w{\text{ and }}|B_{w}|\leq \rho ,|B_{w}|>0{\text{ if }}w>0$

${\text{for }}i=0{\text{ to }}v-1{\text{ do}}$

${\text{D.duplexing}}(A_{i}\ \|\ 0,0)$

$Z={\text{D.duplexing}}(A_{v}\ \|\ 1,|B_{0}|)$

$C=B_{0}\oplus Z$

${\text{for }}i=0{\text{ to }}w-1{\text{ do}}$

$Z={\text{D.duplexing}}(B_{i}\ \|\ 1,|B_{i+1}|)$

$C=C\ \|\ (B_{i+1}\oplus Z)$

$Z={\text{D.duplexing}}(B_{w}\ \|\ 0,\rho )$

${\text{while }}|Z|<\ell {\text{ do}}$

$Z=Z\ \|\ {\text{D.duplexing}}(0,\rho )$

$T=\left\lfloor Z\right\rfloor _{\ell }$

${\text{Return }}(C,T)$

‎

$\mathbf {W.unwrap} (A,C,T){\text{ with }}A,C,T\in \mathbb {Z} _{2}^{*}$

${\text{Let }}A=A_{0}\ \|\ A_{1}\ \|\ A_{v}{\text{ with }}|A_{i}|=\rho {\text{ for }}i<v{\text{ and }}|A_{v}|\leq \rho ,|A_{v}|>0{\text{ if }}v>0$

${\text{Let }}C=C_{0}\ \|\ C_{1}\ \|\ C_{w}{\text{ with }}|C_{i}|=\rho {\text{ for }}i<w{\text{ and }}|C_{w}|\leq \rho ,|C_{w}|>0{\text{ if }}w>0$

${\text{Let }}T=T_{0}\ \|\ T_{1}\ \|\ T_{x}{\text{ with }}|T_{i}|=\rho {\text{ for }}i<x{\text{ and }}|T_{x}|\leq \rho ,|T_{x}|>0{\text{ if }}x>0$

${\text{for }}i=0{\text{ to }}v-1{\text{ do}}$

${\text{D.duplexing}}(A_{i}\ \|\ 0,0)$

$Z={\text{D.duplexing}}(A_{v}\ \|\ 1,|C_{0}|)$

$B_{0}=C_{0}\oplus Z$

${\text{for }}i=0{\text{ to }}w-1{\text{ do}}$

$Z={\text{D.duplexing}}(B_{i}\ \|\ 1,|C_{i+1}|)$

$B_{i+1}=C_{i+1}\oplus Z$

$Z={\text{D.duplexing}}(B_{w}\ \|\ 0,\rho )$

${\text{if }}T=\left\lfloor Z\right\rfloor _{\ell }{\text{ then}}$

${\text{Return }}B_{0}\ \|B_{1}\ \|\ ...\ \|\ B_{w}$

${\text{else return }}\mathbf {Error}$

ראו גם

• SHA-3