בניגוד לפונקציית גיבוב כמו SHA-2 הפונקציה SipHash אינה חסינת התנגשויות במובן החזק. כלומר התכונה החזקה ביותר של פונקציית גיבוב קריפטוגרפית היא שיהיה קשה למצוא ערכים כלשהם לא בהכרח בעלי משמעות כלשהי המקיימים formula_1 כאשר formula_2. בעוד שהפונקציה SipHash רק מבטיחה שבהינתן קלט formula_3 ומפתח סודי formula_4 יהיה קשה לנחש את formula_4 מתוך פלט הפונקציה formula_6 או לחלופין יהיה קשה לנחש מידע כלשהו בנוגע לפלט formula_7 עבור כל ערך formula_2, ללא ידיעת מפתח formula_4.
אפשר להשיג אפקט דומה על ידי כל פונקציית MAC המבוססת על פונקציית גיבוב או פונקציית גיבוב אוניברסלית. הפירוש "אוניברסלית" הוא ששני קלטים שונים כמעט אף פעם לא יפיקו פלט זהה אם המפתח אקראי. יתרונה של SipHash הוא ביעילותה ובפשטותה. לצורך השוואה על מעבד AMD FX-8150 הפונקציה מסוגלת לעבד קלט באורך 16 בתים תוך 140 מחזורי שעון והיא כמעט משתווה בתפוקתה לפונקציית גיבוב לא קריפטוגרפית. מסיבה זו היא מתאימה במיוחד להחליף את הפונקציונליות של טבלאות גיבוב. בדרך כלל מסדי נתונים משתמשים בטבלאות גיבוב לא קריפטוגרפיות כדי לייעל את תהליך אחזור המידע. לדוגמה שרת אינטרנט אמור לתת מענה למיליוני בקשות התחברות במקביל. כדי לעקוב אחרי הבקשות, השרת מנהל רשימה מגובבת של המידע הנכנס. מתקיף שמכיר את פונקציית הגיבוב שהשרת משתמש בה (בדרך כלל המידע הזה ציבורי) צריך רק לשלוח לשרת מאות בקשות התחברות שערך הגיבוב שלהן זהה (התנגשויות מרובות), כאשר מספר רב של בקשות מסוג כזה מתקבלות, הדבר מאט את השרת מאוד ואף משבית אותו כי הוא נאלץ לבצע חיפוש במסד הנתונים בסיבוכיות הגרועה ביותר. פונקציית גיבוב עם מפתח סודי אמורה לסכל התקפה כזו לגמרי, אף על פי שהיא אינה פונקציית גיבוב במובן הרגיל, אולם נוכחותו של המפתח הסודי מקשה על מציאת קלטים אחרים שיניבו פלט זהה (עם אותו מפתח), אלא אם כן יעלה בידי המתקיף לנחש את המפתח.
רקע.
קוד אימות מסרים (בקיצור MAC) היא פונקציה המקבלת קלט formula_10 באורך כלשהו (בדרך כלל ארוך) ומפתח סודי formula_4 ומפיקה תג אימות קצר formula_12. תכונתה העיקרית היא שמתקיף המסוגל להשיג עותקים של תגי אימות עבור קלטים שונים (ייתכן אף לפי בחירתו), לא יצליח עם מידע זה לנחש תג אימות עבור כל מסר אחר שטרם ראה את התג שלו. קוד אימות מסרים חשוב מאוד להבטחת אמינות ושלמות תעבורת הרשת ומניעת ניסיונות זדוניים מצד האקרים לשנות ולשבש את המידע למטרות תקיפת מערכת האבטחה. הרעיון הוא שקוד האימות מאפשר לשני הצדדים לוודא שהמידע שעובר ברשת אותנטי, אם חל בו שינוי כלשהו אפילו בסיבית אחת, הדבר יתגלה בהסתברות מאוד גבוהה על ידי פונקציית האימות, במקרה כזה הצדדים מתפטרים מהמידע המשובש ומעבירים הודעת שגיאה מתאימה. לפי מחקרים שנעשו עולה שכשליש מתעבורת האינטרנט כולל חבילות מידע באורך של כחמישים בתים, שליש באורך 256 בתים ושליש כ-1,500 בתים, רבים מהם צריכים אימות. מרבית התקנים הנוכחיים מתמקדים בפונקציות MAC המותאמות לקלט ארוך. יתרה מזו, לרובם אף תקורה גבוהה הנובעת מתהליך הכנה ארוך או ניהול מפתחות מסובך. לדוגמה HMAC מוסיף בין 73 ל-136 בתים למסר מאומת והוא איטי יחסית. זאת משום שהוא אלגוריתם גנרי המסתמך על פונקציית גיבוב, והאחרונה נוקטת בפעולות רבות כדי למנוע התנגשויות, מה שמיותר במקרה זה כי קיים מפתח סודי. אלגוריתמים אחרים כמו VMAC, UMAC או Poly1305 מנצלים צופן בלוקים כמו AES ולמרות היותם יעילים יותר מפני שהם משתמשים בגרסה יותר קלילה של פונקציית גיבוב הנקראת "אוניברסלית", עדיין קיימת תקורה רבה וכן הסתמכות על אלגוריתמים חיצוניים. ב-SipHash נעשה ניסיון להגיע לאותה רמת ביטחון אך בצורה יעילה יותר ללא תקורה מיותרת.
שימושים.
SipHash נמצא במימושי תוכנה ושפות תכנות רבים, בהם:
תיאור האלגוריתם.
להלן תיאור משפחת הפונקציות במבנה SipHash-c-d כאשר שני הפרמטרים formula_13 ו-formula_14 הם שלמים חיוביים המייצגים את מספר החזרות של הפונקציה הפנימית. פונקציית הסבב הפנימית של האלגוריתם מורכבת משני סוגים של פונקציות כיווץ, הראשונה נקראת "פונקציית כיווץ" והשנייה "פונקציית סיום". שתי הפונקציות למעשה זהות, ההפרדה ביניהן היא עניין סמלי. כדי למנוע התקפות מסוימות, לאחר formula_13 חזרות של פונקציית הסבב האלגוריתם מבצע חיבור נוסף עם בלוק הקלט ועם קבוע כלשהו ולאחר מכן מבצע formula_14 חזרות נוספות של פונקציית הסבב שנקראת בשלב זה פונקציה מסיימת.
בהינתן קלט formula_10 שהוא מחרוזת כלשהי באורך formula_18 בתים ומפתח סודי formula_4 באורך 16 בתים, תפקיד הפונקציה formula_20 הוא להחזיר תג אימות באורך 64 סיביות כדלהלן:
1. אתחול. מאתחלים את המצב הפנימי (Internal state) של האלגוריתם בערכים:
כאשר formula_25 ו-formula_26 הם שני החצאים של המפתח formula_4, כל אחד מהם באורך 64 סיביות לפי סדר בתים קטן. לקבועים אילו אין משמעות מתמטית, הם בסך הכול קידוד בבסיס הקסדצימלי של המשפט "some pseudorandomly generated bytes" (ללא רווחים) לפי סדר בתים גדול. כל ערך אחר שונה מאפס טוב ובלבד שיהיה הבדל ניכר בין ערכי formula_28. לא נבדק האם אפשר לנצל שלב זה כווקטור אתחול מותאם אישית.
2. כיווץ. תחילה מציגים את formula_18 הבתים של הקלט formula_10 כמחרוזת המכילה formula_31 מילים באורך 64 סיביות כל אחת, לפי סדר בתים קטן: formula_32, כאשר הבית האחרון במילה האחרונה formula_33 מכיל את קידוד אורך הקלט formula_18 בבתים מודולו 256. הקלט חייב להכיל לפחות מילה אחת, אם הקלט נמוך ממילה אחת או שאורכו אינו כפולה של מילים באורך 64 סיביות, מרפדים באפסים כנדרש (למעט בית האחרון). לדוגמה אם מחרוזת הקלט היא "01234abcde" (בבסיס הקסדצימלי) אז formula_35, formula_36 והמילה formula_37 מכילה את:
מחברים באופן איטרטיבי את כל מילות הקלט formula_39 עם המצב הפנימי כאשר formula_40, על ידי:
מבצעים formula_13 איטרציות של פונקציית הסבב SipRound (המפורטת בהמשך) ולאחר מכן מבצעים על כל מילות הקלט:
3. סיומת. לאחר עיבוד כל מילות הקלט כמתואר, מבצעים XOR של הקבוע formula_44 עם המילה השלישית של המצב הפנימי:
ואז מבצעים formula_14 איטרציות של פונקציית הסבב SipRound ומחזירים את 64 הסיביות שהן תוצאה של:
פונקציית הסבב SipRound.
הטרנספורמציה SipRound המומחשת בתרשים משמאל מבצעת את הפעולות הבאות על המצב הפנימי של האלגוריתם:
כאשר הסימן formula_48 הוא XOR, הסימן formula_49 מייצג הזזה מעגלית של סיביות שמאלה, בגבולות מילה באורך 64 סיביות, לפי מספר הפוזיציות המצוין לאחריו. הסימן formula_50 מייצג חיבור מודולו formula_51. היסטי ההזזות נבחרו באופן אמפירי, תוך מתן דגש על ערכים המיושרים לגבולות בתים או מילים להאצת ביצועים ומניעת עיכובים בצינור העיבוד.
ביטחון ויעילות.
SipHash-c-d כאשר formula_52 וכן formula_53 אמורה לספק לדעת המפתחים מקסימום ביטחון כפונקציה פסאודו אקראית. הביטחון הגבוה ביותר שניתן להשיג עם כל פונקציית PRF לאימות מסרים. לשימוש רגיל ההמלצה שלהם היא SipHash-2-4 (כלומר שני סבבים של הפונקציה הפנימית ואחריהן ארבעה סבבים של הפונקציה המסיימת) ולשימוש שמרני יותר SipHash-4-8 שהיא איטית פי שניים מהראשונה. מהיבט תאורטי, ביטחון פונקציית PRF סטנדרטית מניח שלמתקיף גישה לפלט הפונקציה על קלטים שנבחרו על ידו באופן אדפטיבי (שזהו המודל המחמיר ביותר), אך הוא אינו רשאי לראות את המפתח, או לצורך הדיון כאן, אין ביכולתו להשיג גישה ל"מפתחות קשורים", "מפתחות ידועים" או "מפתחות נבחרים" (כל אילו מודלים של ביטחון שמניחים שלמתקיף שליטה מסוימת גם אם חלקית ועקיפה על חומר המפתח הסודי). במצב זה ביטחון הפונקציה תלוי באורך המפתח. היות שהמפתח באורך 128 סיביות, אם המתקיף מבצע formula_54 שאילתות (ניסיונות אימות) סיכוייו לנחש את המפתח שואפים ל-formula_55. בהנחה שלא קיימת דרך טובה מכוח גס. הביטחון המושג מוגבל גם בגלל אורך הפלט. כלומר כאשר משתמשים ב-SipHash כקוד אימות, אם המתקיף מסוגל לבצע formula_56 שאילתות הוא יצליח לזייף תג אימות בהסתברות של formula_57. חשוב להדגיש ש-SipHash אינה ולא הייתה מיועדת להיות פונקציה חסינת התנגשויות.
SipHash אימצה טכניקות מהפונקציות BLAKE, Skein ו-JH שהיו מועמדות תקן הגיבוב SHA-3 ועלו לגמר. פונקציות הגיבוב המנויות עברו ביקורת מדוקדקת של מומחים והוצהרו נכון להיום כבטוחות ולכן הסתמכות על חלקים מהם מקלה על ניתוח ביטחון האלגוריתם. מבנה הפונקציה הפנימית הוא ARX (קיצור של חיבור/הזזה/XOR) שהוכח כבטוח ונמצא בשימוש צפנים מודרניים כמו Salsa20. מ-Blake נלקחו המינימליות והפשטות מ-Skein נלקח תהליך הערבוב MIX ומ-JH אומץ רעיון טעינת הקלט לפני ואחרי כל בלוק. היתרון הוא שבניגוד לסגנון הספוג של SHA-3, אפשר לספוג חלק מהקלט ללא ירידה בביטחון מקור ראשון (Preimage).
המפתחים מציינים כי האלגוריתם נבדק נוכח מספר גדול של התקפות קריפטואנליטיות מודרניות ונמצא בטוח לטענתם. כוח גס בסיבוכיות של formula_58 אינו מעשי. ניחוש הזיכרון הפנימי דורש בממוצע formula_59 פעולות ולכן אינו מעשי. המחברים ניסו התקפות דיפרנציאליות שונות וכן התקפות קריפטוגרפיות אחרות כמו התקפת נקודות שבת וכן התקפת Cube והתקפת Rebound.