SipHash

SipHash (קיצור של Short Input Hash) הוא שם כולל למשפחה של פונקציות פסאודו-אקראיות בסגנון ARX, שפותחו ב-2012 על ידי ג'ון פיליפ אמסון ודניאל ברנשטיין. SipHash היא מעין פונקציית גיבוב עם מפתח הממוטבת במיוחד עבור קלט קצר ועוצבה במטרה לתת מענה להתקפות מניעת שירות מסוג Hash Flooding ששטף את הרשת ב-2011.
בניגוד לפונקציית גיבוב כמו SHA-2 הפונקציה SipHash אינה חסינת התנגשויות במובן החזק. כלומר התכונה החזקה ביותר של פונקציית גיבוב קריפטוגרפית היא שיהיה קשה למצוא ערכים כלשהם לא בהכרח בעלי משמעות כלשהי המקיימים  כאשר . בעוד שהפונקציה SipHash רק מבטיחה שבהינתן קלט  ומפתח סודי  יהיה קשה לנחש את  מתוך פלט הפונקציה  או לחלופין יהיה קשה לנחש מידע כלשהו בנוגע לפלט  עבור כל ערך , ללא ידיעת מפתח .
אפשר להשיג אפקט דומה על ידי כל פונקציית MAC המבוססת על פונקציית גיבוב או פונקציית גיבוב אוניברסלית. הפירוש "אוניברסלית" הוא ששני קלטים שונים כמעט אף פעם לא יפיקו פלט זהה אם המפתח אקראי. יתרונה של SipHash הוא ביעילותה ובפשטותה. לצורך השוואה על מעבד AMD FX-8150 הפונקציה מסוגלת לעבד קלט באורך 16 בתים תוך 140 מחזורי שעון והיא כמעט משתווה בתפוקתה לפונקציית גיבוב לא קריפטוגרפית. מסיבה זו היא מתאימה במיוחד להחליף את הפונקציונליות של טבלאות גיבוב. בדרך כלל מסדי נתונים משתמשים בטבלאות גיבוב לא קריפטוגרפיות כדי לייעל את תהליך אחזור המידע. לדוגמה שרת אינטרנט אמור לתת מענה למיליוני בקשות התחברות במקביל. כדי לעקוב אחרי הבקשות, השרת מנהל רשימה מגובבת של המידע הנכנס. מתקיף שמכיר את פונקציית הגיבוב שהשרת משתמש בה (בדרך כלל המידע הזה ציבורי) צריך רק לשלוח לשרת מאות בקשות התחברות שערך הגיבוב שלהן זהה (התנגשויות מרובות), כאשר מספר רב של בקשות מסוג כזה מתקבלות, הדבר מאט את השרת מאוד ואף משבית אותו כי הוא נאלץ לבצע חיפוש במסד הנתונים בסיבוכיות הגרועה ביותר. פונקציית גיבוב עם מפתח סודי אמורה לסכל התקפה כזו לגמרי, אף על פי שהיא אינה פונקציית גיבוב במובן הרגיל, אולם נוכחותו של המפתח הסודי מקשה על מציאת קלטים אחרים שיניבו פלט זהה (עם אותו מפתח), אלא אם כן יעלה בידי המתקיף לנחש את המפתח.

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

SipHash-c-d כאשר  וכן  אמורה לספק לדעת המפתחים מקסימום ביטחון כפונקציה פסאודו אקראית. הביטחון הגבוה ביותר שניתן להשיג עם כל פונקציית PRF לאימות מסרים. לשימוש רגיל ההמלצה שלהם היא SipHash-2-4 (כלומר שני סבבים של הפונקציה הפנימית ואחריהן ארבעה סבבים של הפונקציה המסיימת) ולשימוש שמרני יותר SipHash-4-8 שהיא איטית פי שניים מהראשונה. מהיבט תאורטי, ביטחון פונקציית PRF סטנדרטית מניח שלמתקיף גישה לפלט הפונקציה על קלטים שנבחרו על ידו באופן אדפטיבי (שזהו המודל המחמיר ביותר), אך הוא אינו רשאי לראות את המפתח, או לצורך הדיון כאן, אין ביכולתו להשיג גישה ל"מפתחות קשורים", "מפתחות ידועים" או "מפתחות נבחרים" (כל אילו מודלים של ביטחון שמניחים שלמתקיף שליטה מסוימת גם אם חלקית ועקיפה על חומר המפתח הסודי). במצב זה ביטחון הפונקציה תלוי באורך המפתח. היות שהמפתח באורך 128 סיביות, אם המתקיף מבצע  שאילתות (ניסיונות אימות) סיכוייו לנחש את המפתח שואפים ל-. בהנחה שלא קיימת דרך טובה מכוח גס. הביטחון המושג מוגבל גם בגלל אורך הפלט. כלומר כאשר משתמשים ב-SipHash כקוד אימות, אם המתקיף מסוגל לבצע  שאילתות הוא יצליח לזייף תג אימות בהסתברות של . חשוב להדגיש ש-SipHash אינה ולא הייתה מיועדת להיות פונקציה חסינת התנגשויות.
SipHash אימצה טכניקות מהפונקציות BLAKE,‏ Skein ו-JH שהיו מועמדות תקן הגיבוב SHA-3 ועלו לגמר. פונקציות הגיבוב המנויות עברו ביקורת מדוקדקת של מומחים והוצהרו נכון להיום כבטוחות ולכן הסתמכות על חלקים מהם מקלה על ניתוח ביטחון האלגוריתם. מבנה הפונקציה הפנימית הוא ARX (קיצור של חיבור/הזזה/XOR) שהוכח כבטוח ונמצא בשימוש צפנים מודרניים כמו Salsa20. מ-Blake נלקחו המינימליות והפשטות מ-Skein נלקח תהליך הערבוב MIX ומ-JH אומץ רעיון טעינת הקלט לפני ואחרי כל בלוק. היתרון הוא שבניגוד לסגנון הספוג של SHA-3, אפשר לספוג חלק מהקלט ללא ירידה בביטחון מקור ראשון (Preimage).
המפתחים מציינים כי האלגוריתם נבדק נוכח מספר גדול של התקפות קריפטואנליטיות מודרניות ונמצא בטוח לטענתם. כוח גס בסיבוכיות של  אינו מעשי. ניחוש הזיכרון הפנימי דורש בממוצע  פעולות ולכן אינו מעשי. המחברים ניסו התקפות דיפרנציאליות שונות וכן התקפות קריפטוגרפיות אחרות כמו התקפת נקודות שבת וכן התקפת Cube והתקפת Rebound.
בפונקציית הסבב של SipHash יש בסך הכול 14 פעולות על משתנים באורך 64 סיביות. לכן ב-SipHash-2-4 יש בסך הכול 30 פעולות עבור כל שמונה בתים של קלט, 3.75 פעולות פר בית בממוצע. מעבד ארבע ליבות מבזבז כמחזור שעון אחד עבור כל בית של קלט. האלגוריתם נבדק על מספר מעבדים ומערכות הפעלה, הן בתוכנה והן בחומרה והביצועים השוו לפונקציות גיבוב לא קריפטוגרפיות כמו CityHash של גוגל וכן SpookyHash ו-MD5. לפי התוצאות SipHash קרובה בביצועיה לפונקציות הגיבוב המהירות ביותר הקיימות כיום. לצורך השוואה על מעבד Xeon E5620 של אינטל, ליבת Core i7, קלט באורך 8 בתים עובד תוך 92 מחזורי שעון בערך.

קוד לדוגמה של SipHash-2-4

#define U8TO32_LE(p) \   (((uint32_t)((p)[0]) ) | ((uint32_t)((p)[1]) << 8) | \   ((uint32_t)((p)[2]) << 16) | ((uint32_t)((p)[3]) << 24)) \#define U8TO64_LE(p) \   ((uint64_t)U8TO32_LE(p) | ((uint64_t)U8TO32_LE((p) + 4)) << 32 )#define ROTL64(v, s) \   ((v) << (s)) | ((v) >> (64 - (s)))#define ROTL64_TO(v, s) ((v) = ROTL64((v), (s)))#define ADD64_TO(v, s) ((v) += (s))#define XOR64_TO(v, s) ((v) ^= (s))#define XOR64_INT(v, x) ((v) ^= (x))static const char sip_init_state_bin[] = "uespemos""modnarod""arenegyl""setybdet";#define sip_init_state (*(uint64_t (*)[4])sip_init_state_bin)#define SIP_COMPRESS(v0, v1, v2, v3) \do { \   ADD64_TO((v0), (v1)); \   ADD64_TO((v2), (v3)); \   ROTL64_TO((v1), 13); \   ROTL64_TO((v3), 16); \   XOR64_TO((v1), (v0)); \   XOR64_TO((v3), (v2)); \   ROTL64_TO((v0), 32); \   ADD64_TO((v2), (v1)); \   ADD64_TO((v0), (v3)); \   ROTL64_TO((v1), 17); \   ROTL64_TO((v3), 21); \   XOR64_TO((v1), (v2)); \   XOR64_TO((v3), (v0)); \   ROTL64_TO((v2), 32); \} while(0)#define SIP_2_ROUND(m, v0, v1, v2, v3) \do { \   XOR64_TO((v3), (m)); \   SIP_COMPRESS(v0, v1, v2, v3); \   SIP_COMPRESS(v0, v1, v2, v3); \   XOR64_TO((v0), (m)); \} while (0)uint64_t sip_hash24(uint8_t key[16], uint8_t *data, size_t len){
   uint64_t k0, k1;
   uint64_t v0, v1, v2, v3;
   uint64_t m, last;
   uint8_t *end = data + len - (len % sizeof(uint64_t));

   k0 = U8TO64_LE(key);
   k1 = U8TO64_LE(key + sizeof(uint64_t));

   v0 = k0; XOR64_TO(v0, sip_init_state[0]);
   v1 = k1; XOR64_TO(v1, sip_init_state[1]);
   v2 = k0; XOR64_TO(v2, sip_init_state[2]);
   v3 = k1; XOR64_TO(v3, sip_init_state[3]);

   for (; data != end; data += sizeof(uint64_t)) {
      m = U8TO64_LE(data);
      SIP_2_ROUND(m, v0, v1, v2, v3);
   }

   last = len << 56;
   #define OR_BYTE(n) (last |= ((uint64_t) end[n]) << ((n) * 8))

   switch (len % sizeof(uint64_t)) {
      case 7: OR_BYTE(6);
      case 6: OR_BYTE(5);
      case 5: OR_BYTE(4);
      case 4: OR_BYTE(3);
      case 3: OR_BYTE(2);
      case 2: OR_BYTE(1);
      case 1: OR_BYTE(0); 
      break;
      case 0: break;
   }

   SIP_2_ROUND(last, v0, v1, v2, v3);

   XOR64_INT(v2, 0xff);

   SIP_COMPRESS(v0, v1, v2, v3);
   SIP_COMPRESS(v0, v1, v2, v3);
   SIP_COMPRESS(v0, v1, v2, v3);
   SIP_COMPRESS(v0, v1, v2, v3);

   XOR64_TO(v0, v1);
   XOR64_TO(v0, v2);
   XOR64_TO(v0, v3);
   return v0;}