בקריפטוגרפיה, פונקציית ספוג (sponge function) היא דרך להרחיב פונקציית גיבוב לפונקציה קריפטוגרפית כללית שהקלט והפלט שלה באורך משתנה. פונקציית ספוג מיישמת מבנה ספוג (sponge structure) שהוא מבנה איטרטיבי פשוט המבוסס על תמורה או טרנספורמציה פנימית הפועלת על קלט באורך קבוע, שמקבל קלט באורך משתנה ומפיק פלט באורך משתנה. פונקציית ספוג מאוד גמישה ויכולה לשמש כצופן זרם שבו נדרש קלט קצר ופלט ארוך או כפונקציית גיבוב וקוד אימות מסרים שבהם הקלט ארוך והפלט קצר. מהיבט תאורטי פונקציית ספוג משמשת כמודל למבנה קונקרטי של פונקציית גיבוב עם גישה לזיכרון פנימי. פונקציית ספוג אקראית מקבילה לאורקל אקראי, למעט אפקט הזיכרון הסופי (התנגשויות הן בלתי נמנעות). לכן יכולה לשמש כחלופה למודל אורקל אקראי כדי לבטא טענת ביטחון.
רקע.
הרעיון נולד במהלך פיתוח RadioGatun שהיא פונקציית גיבוב המקבלת קלט באורך שרירותי ומפיקה פלט בכל אורך רצוי. המפתחים נתקלו בבעיה בניסיון לבטא את ביטחון האלגוריתם במונחים של סיבוכיות זמן. כאשר הפלט קבוע אפשר לטעון שפונקציית הגיבוב טובה לפחות כאורקל אקראי שהפלט שלו נחתך ל-formula_1 סיביות. לכן בגלל התקפת יום הולדת סיבוכיות התקפה בסיסית למציאת התנגשות היא מסדר גודל של formula_2. אולם כאשר הפלט באורך משתנה אין לטענה זו משמעות, כביכול אפשר להגיע לביטחון אינסופי אם מאריכים את הפלט מאוד. לכן המפתחים הגיעו למודל שונה שבו מצהירים ביטחון במונחים של אורקל אקראי שנקרא כאן "פונקציית ספוג אקראית", שהוא מבנה תאורטי כמו אורקל אקראי למעט העובדה שהוא מוגבל בזיכרון לכן התנגשויות בלתי נמנעות. הממצאים פורסמו לראשונה ב-2007 בסמינר Dugstuhl בגרמניה ולאחר מכן בסדנת Ecrypt בברצלונה.
פונקציית ספוג התגלתה ככלי יעיל לבניית פרימיטיבים קריפטוגרפיים רבים. אפשר לנצל מבנה ספוג ותאומו הנקרא "מבנה דופלקס" (duplex construction), כדי ליישם מגוון רחב של פרימיטיבים קריפטוגרפיים, כולל פונקציית גיבוב, מחולל פסאודו-אקראי, הצפנה סימטרית, אימות מסרים והצפנה מאומתת, עם ובלי וקטור אתחול ובאורכים משתנים לפי לצורך. בדרך זו נהנים מפונקציונליות רבה בפונקציית תמורה יחידה ומפשטים את תהליך הפיתוח והיישום מבלי לדאוג למרכיבים אחרים כמו תהליך הכנת מפתח. האטרקטיביות של מבנה זה נובעת מהעובדה שאפשר להתבסס על פרמוטציה מתאימה שזה יותר קל מלפתח צופן בלוקים או פונקציית דחיסה. קיימים כמה אלגוריתמים חדשים שמסתמכים על מבנה ספוג מהם Keccak, Quark, Photon, Spongent וכן Spritz. מראה כללי של מבנה ספוג הוא:
הסימן formula_3 מייצג שרשור. תחילה הקלט formula_4 מרופד לפי כלל ריפוד מתאים (בהמשך), לאחר מכן התוצאה formula_5 נספגת לתוך המצב הפנימי formula_6 באמצעות הפונקציה הפנימית formula_7 באורך formula_8 סיביות. היא יכולה להיות כל PRP או PRF בטוח לפי בחירה. ואז הפלט formula_9 נסחט בהתאם לאורך הרצוי formula_10, הפלט יכול לשמש כמפתח הצפנה או ערך גיבוב. באופן כללי אמור להיות קשה למצוא מסלול מ-formula_6 ל-formula_5. התנגשות פירושה ש-formula_13 כאשר formula_14 וכן אם מתקבל formula_15 פירושו שהמבנה מכיל מעגליות ולכן הפלט יחזור על עצמו.
כלל ריפוד.
היות שהקלט באורך משתנה יש להפעיל כלל ריפוד מתאים כדי לחלק את הקלט ל-formula_16 בלוקים בגודל formula_17 סיביות כל אחד, באופן שיהיה קל להסיר את הריפוד עם קבלת המסר בצד השני מבלי לדעת מה היה אורך המסר. סכמת הריפוד הפשוטה והנפוצה ביותר היא formula_18 כלומר מוסיפים את הסיבית "1" בסוף הקלט ומרפדים באפסים, כאשר הכוכבית מציינת שמספר האפסים הנדרש תלוי באורך הקלט ובגודל הבלוק, כך שהאורך הכולל צריך להתחלק ב-formula_17. כלל הריפוד חייב לקיים שלושה תנאים:
הסימון של כלל הריפוד עבור בלוק באורך formula_16 סיביות מסומן בקיצור: formula_21
מבנה ספוג.
מבנה ספוג הוא מבנה איטרטיבי פשוט ליצירת פונקציה formula_22 המקבלת קלט מהתחום formula_23 ומפיקה פלט בטווח formula_24. היא מבוססת על תמורה או טרנספורמציה formula_7 הפועלת על formula_17 סיביות. formula_17 קבוע ונקרא כאן רוחב. הוא כולל מצב פנימי (זיכרון) באורך formula_28 סיביות, כאשר formula_8 נקרא "קצב" (bitrate) ו-formula_30 נקרא "קיבולת" (capacity). המצב הפנימי מאותחל באפסים, הקלט מרופד כאמור ומחולק לבלוקים של formula_8 סיביות ומשם ממשיכים בשני שלבים:
הסימון formula_36 פירושו שאת פלט הפונקציה חותכים ל-formula_10 הסיביות הראשונות. כאשר formula_30 הסיביות הנותרות של המצב לעולם לא מושפעות מבלוקים של הקלט ולעולם אינן נכללות בפלט במהלך הסחיטה.
להלן פסאודו-קוד המתאר מבנה הספוג:
מודל ביטחון.
בפונקציית גיבוב עם פלט קבוע מקובל היה בדרך כלל להשוותה מול אורקל אקראי, אולם זה השתנה בעקבות גילויים חדשים בעשור האחרון. יש לזכור שהיות שהמצב הפנימי סופי והפונקציה איטרטיבית - היא מעבדת את הקלט בלוק אחר בלוק, בהכרח שיהיו התנגשויות, זאת לעומת אורקל אקראי תאורטי שאצלו לא קיים מושג "מצב" ואין לו התנגשויות. מסיבה זו אי אפשר להשוות ישירות למודל אורקל אקראי. אלטרנטיבה טובה למודל אורקל אקראי בהקשר זה היא מבנה ספוג אקראי שהוא מבנה תאורטי שהפונקציה הפנימית שלו formula_7 היא פרמוטציה אקראית שנבחרה באופן אחיד מטווח הפרמוטציות האפשריות מעל formula_17 סיביות. למעט האפקט שנובע עקב מגבלת הזיכרון הסופי. מהיבט תאורטי כשמנתחים ביטחון פונקציית ספוג לפי מודל זה מביאים בחשבון גם את הפרמטרים קצב וקיבולת. במצב אידיאלי אומרים שביטחון הפונקציה הוא במונחים של הקיבולת formula_30, כלומר התקפה גנרית שאינה מנצלת חולשות ספציפיות בפונקציה הפנימית תהיה בסיבוכיות formula_53 לפחות. במילים אחרות מוכיחים שכל התקפה מוצלחת נגד המבנה עצמו משליכה בהכרח שניתן להבחין בין תוצאת הפרמוטציה שהמבנה משתמש בה לבין מחרוזת אקראית ומכאן שהיא אינה טובה לשימוש.
מבנה דופלקס.
באופן דומה מבנה formula_54 משתמש בטרנספורמציה או תמורה פנימית formula_7, כלל ריפוד מתאים ופרמטר formula_8. אך בשונה מפונקציית ספוג שהיא חסרת מצב בין הקריאות לפונקציה, מבנה דופלקס הוא אובייקט שיכול לקבל קלט נוסף ולהפיק מחרוזת פלט שהיא תוצאה של הקלט שהתקבל עד כה. במילים אחרות מבנה דופלקס דומה לרצף קריאות חוזרות של פונקציית ספוג עם קלט שונה. אובייקט דופלקס מכיל מצב בגודל formula_17 סיביות, בשלב האתחול המצב הפנימי מאופס, ומכאן ואילך אפשר להפעיל את הפונקציה formula_58 שוב ושוב עם קלט formula_59 שאורכו צריך להיות קצר מספיק כדי שיתקבל בלוק אחד לאחר ריפוד. הפלט הוא באורך formula_10 שהוא לכל היותר formula_8 סיביות. בכל קריאה המבנה תחילה מרפד את הקלט לפי כלל הריפוד שנבחר, מחבר את הקלט ב-XOR עם חלק החיצוני של המצב הפנימי ואז מיישם את הפונקציה formula_7 על המצב ומחזיר את formula_10 הסיביות הראשונות של המצב. הוכח שמבנה דופלקס בטוח כמבנה ספוג, היות שמבנה דופלקס בעצם מקביל למבנה ספוג שהקלט שלו חולק למקטעים בגודל formula_59 שכל אחד מהם מרופד בנפרד ואז הם משורשרים לרצף אחד ארוך. להלן תיאור מבנה דופלקס:
הצפנה מאומתת.
הצפנה מאומתת היא דרך להצפין ולאמת מידע יחד עם מידע נלווה המשויך אליו אם ישנו. הרעיון שימושי במיוחד בפרוטוקול תקשורת שבו חלק מחבילת מידע אמור להיות סודי בעוד שחלק אחר שנקרא בהקשר זה כותר (header) אמור להישאר קריא (משמש את השרת המקבל). המצפין רוצה להבטיח מלבד סודיות שהמסר והמידע הנלווה אליו אותנטיים וכי לא שונו על ידי גורם זר או בשל תקלה בשידור, באופן שמסכן את החלק הסודי של החבילה. אפשר ליישם הצפנה מאומתת באמצעות מבנה דופלקס. האובייקט SpongeWrap להלן, משתמש באובייקט דופלקס D עם הפרמטרים formula_73 אותו הוא מאתחל ומעביר אליו את המפתח formula_74. כדי להצפין ולאמת קוראים לפונקציה W.wrap עם הפרמטרים formula_75 כאשר formula_76 הוא המידע הנלווה, formula_77 הוא המסר המיועד להצפנה והפרמטר formula_10 מייצג את אורך תג האימות בסיביות. הפונקציה מחזירה את הטקסט המוצפן formula_79 שהוא formula_80 כאשר formula_81 הוא הערך החוזר מהפונקציה duplexing ואת תג האימות formula_82. לפענוח קוראים לפונקציה W.unwrap עם הפרמטרים formula_83 והיא אמורה להחזיר את formula_77 או "Error" אם אחד הערכים אינו תקין. לפני הקריאה לאובייקט D לביצוע duplexing תחילה מרפדים את כל האלמטים בסיבית אחת נוספת שנקראת frame-bit (1 חוץ מהבלוק האחרון). הערך formula_85 נקרא קצב והוא קובע את גודל הבלוק, כלומר כמות הסיביות שאפשר להצפין ולאמת בקריאה אחת. לכן הערך המקסימלי שלו הוא formula_86 כי יש להביא בחשבון את הסיבית הנוספת. להלן תיאור האלגוריתם:
אושייצק
אושייצק (בפולנית: Osieck) היא עיירה במחוז אוטובוצק שבפרובינציית מזוביה בפולין, בה שכנה עד השואה קהילה יהודית.
תולדות היישוב.
אושייצק נזכרת לראשונה בתעודות מן המאה ה-18 ככפר בבעלות אצילים פולנים. על פי אופייה הייתה יישוב חקלאי, אך מאחר שהתקיימו בה שווקים וירידים, היא שימשה גם מרכז מסחרי לסביבתה, וב-1826 קיבלה מעמד עירוני.
בשנת 1827 היו בה 159 בתים, וב-1860 185 בתים, רק ארבעה מהם בתי לבנים.
באמצע ספטמבר 1939 נכבשה העיירה בידי הגרמנים, אך הם לא ישבו בה דרך קבע, והשאירו את ניהולה בידי הרשות המקומית הפולנית.
יהודי אושייצק.