SipHash

SipHash (קיצור של Short Input Hash) הוא שם כולל למשפחה של פונקציות פסאודו-אקראיות בסגנון ARX, שפותחו ב-2012^[1] על ידי ג'ון פיליפ אמסון ודניאל ברנשטיין. SipHash היא מעין פונקציית גיבוב עם מפתח הממוטבת במיוחד עבור קלט קצר ועוצבה במטרה לתת מענה להתקפות מניעת שירות מסוג Hash Flooding^[2] ששטף את הרשת ב-2011.

בניגוד לפונקציית גיבוב כמו SHA-2 הפונקציה SipHash אינה חסינת התנגשויות במובן החזק. כלומר התכונה החזקה ביותר של פונקציית גיבוב קריפטוגרפית היא שיהיה קשה למצוא ערכים כלשהם לא בהכרח בעלי משמעות כלשהי המקיימים ${\displaystyle H(x)=H(y)}$ כאשר ${\displaystyle y\neq x}$. בעוד שהפונקציה SipHash רק מבטיחה שבהינתן קלט ${\displaystyle x}$ ומפתח סודי ${\displaystyle k}$ יהיה קשה לנחש את ${\displaystyle k}$ מתוך פלט הפונקציה ${\displaystyle {\text{SipHash}(x,k)}$ או לחלופין יהיה קשה לנחש מידע כלשהו בנוגע לפלט ${\displaystyle {\text{SipHash}(y,k)}$ עבור כל ערך ${\displaystyle y\neq x}$, ללא ידיעת מפתח ${\displaystyle k}$.

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

רקע

ערך מורחב – קוד אימות מסרים

קוד אימות מסרים (בקיצור MAC) היא פונקציה המקבלת קלט ${\displaystyle m}$ באורך כלשהו (בדרך כלל ארוך) ומפתח סודי ${\displaystyle k}$ ומפיקה תג אימות קצר ${\displaystyle t}$. תכונתה העיקרית היא שמתקיף המסוגל להשיג עותקים של תגי אימות עבור קלטים שונים (ייתכן אף לפי בחירתו), לא יצליח עם מידע זה לנחש תג אימות עבור כל מסר אחר שטרם ראה את התג שלו. קוד אימות מסרים חשוב מאוד להבטחת אמינות ושלמות תעבורת הרשת ומניעת ניסיונות זדוניים מצד האקרים לשנות ולשבש את המידע למטרות תקיפת מערכת האבטחה. הרעיון הוא שקוד האימות מאפשר לשני הצדדים לוודא שהמידע שעובר ברשת אותנטי, אם חל בו שינוי כלשהו אפילו בסיבית אחת, הדבר יתגלה בהסתברות מאוד גבוהה על ידי פונקציית האימות, במקרה כזה הצדדים מתפטרים מהמידע המשובש ומעבירים הודעת שגיאה מתאימה. לפי מחקרים שנעשו עולה שכשליש מתעבורת האינטרנט כולל חבילות מידע באורך של כחמישים בתים, שליש באורך 256 בתים ושליש כ-1,500 בתים, רבים מהם צריכים אימות. מרבית התקנים הנוכחיים מתמקדים בפונקציות MAC המותאמות לקלט ארוך. יתרה מזו, לרובם אף תקורה גבוהה הנובעת מתהליך הכנה ארוך או ניהול מפתחות מסובך. לדוגמה HMAC מוסיף בין 73 ל-136 בתים למסר מאומת והוא איטי יחסית. זאת משום שהוא אלגוריתם גנרי המסתמך על פונקציית גיבוב, והאחרונה נוקטת בפעולות רבות כדי למנוע התנגשויות, מה שמיותר במקרה זה כי קיים מפתח סודי. אלגוריתמים אחרים כמו VMAC,‏ UMAC או Poly1305 מנצלים צופן בלוקים כמו AES ולמרות היותם יעילים יותר מפני שהם משתמשים בגרסה יותר קלילה של פונקציית גיבוב הנקראת "אוניברסלית", עדיין קיימת תקורה רבה וכן הסתמכות על אלגוריתמים חיצוניים. ב-SipHash נעשה ניסיון להגיע לאותה רמת ביטחון אך בצורה יעילה יותר ללא תקורה מיותרת.

יתרונות SipHah

• ביטחון גבוה. ההצעה SipHash-2-4 היא פונקציה פסאודו-אקראית קריפטוגרפית חזקה והפלט שלה בלתי ניתן להבחנה מערך אקראי שנבחר בהתפלגות אחידה. המפתחים מספקים הוכחות.
• מהירות גבוהה. SipHash-2-4 מהירה יותר מכל פונקציית MAC או PRF ידועה ואף מהווה מתחרה ראויה לפונקציות גיבוב לא קריפטוגרפיות.
• גמישות. SipHash משתמשת במפתח הצפנה באורך 128 סיביות. הפונקציה אינה מכילה תהליך "הרחבת מפתח" ולא קיימת התקורה הנובעת מאחסון וטעינה של מפתחות מהזיכרון.
• פשטות. הפונקציה כוללת בסך הכול ארבע פעולות חיבור, ארבע פעולות XOR וארבע הזזות.
• אוטונומיות. לא נעשה שימוש בפרימיטיביים קריפטוגרפיים חיצוניים.
• זיכרון פנימי קצר. הפונקציה צורכת בסך הכול 4 מילים באורך 64 סיביות כל אחת (בסך הכול 32 בתים בזיכרון).
• אין צורך בניהול מצב פנימי בין הקריאות. האלגוריתם דטרמיניסטי ואין צורך בווקטור אתחול.
• עמידות מפני התקפת ערוץ צדדי. צפנים מודרניים כמו AES בדרך כלל מעודדים שימוש בטבלאות אחזור מטעמי יעילות. מפני שלא קיימות באלגוריתם SipHash טבלאות אחזור סודיות הוא אינו חשוף להתקפות ערוץ צדדי.
• תקורה מינימלית. תג האימות מכיל רק שישה בתים.

שימושים

SipHash נמצא במימושי תוכנה ושפות תכנות רבים, בהם:

• Perl (קיים כאופציה בזמן הידור)
• Python (מגרסה 3.4)
• Ruby
• Rust
• OpenDNS
• Haskell
• OpenBSD

תיאור האלגוריתם

להלן תיאור משפחת הפונקציות במבנה SipHash-c-d כאשר שני הפרמטרים ${\displaystyle c}$ ו-${\displaystyle d}$ הם שלמים חיוביים המייצגים את מספר החזרות של הפונקציה הפנימית. פונקציית הסבב הפנימית של האלגוריתם מורכבת משני סוגים של פונקציות כיווץ, הראשונה נקראת "פונקציית כיווץ" והשנייה "פונקציית סיום". שתי הפונקציות למעשה זהות, ההפרדה ביניהן היא עניין סמלי. כדי למנוע התקפות מסוימות, לאחר ${\displaystyle c}$ חזרות של פונקציית הסבב האלגוריתם מבצע חיבור נוסף עם בלוק הקלט ועם קבוע כלשהו ולאחר מכן מבצע ${\displaystyle d}$ חזרות נוספות של פונקציית הסבב שנקראת בשלב זה פונקציה מסיימת.

בהינתן קלט ${\displaystyle m}$ שהוא מחרוזת כלשהי באורך ${\displaystyle b}$ בתים ומפתח סודי ${\displaystyle k}$ באורך 16 בתים, תפקיד הפונקציה ${\displaystyle {\text{SipHash-c-d}(k,m)}$ הוא להחזיר תג אימות באורך 64 סיביות כדלהלן:

1. אתחול. מאתחלים את המצב הפנימי (Internal state) של האלגוריתם בערכים:

כאשר ${\displaystyle k_{0}$ ו-${\displaystyle k_{1}$ הם שני החצאים של המפתח ${\displaystyle k}$, כל אחד מהם באורך 64 סיביות לפי סדר בתים קטן. לקבועים אילו אין משמעות מתמטית, הם בסך הכול קידוד בבסיס הקסדצימלי של המשפט "some pseudorandomly generated bytes" (ללא רווחים) לפי סדר בתים גדול. כל ערך אחר שונה מאפס טוב ובלבד שיהיה הבדל ניכר בין ערכי ${\displaystyle v_{i}$. לא נבדק האם אפשר לנצל שלב זה כווקטור אתחול מותאם אישית.

2. כיווץ. תחילה מציגים את ${\displaystyle b}$ הבתים של הקלט ${\displaystyle m}$ כמחרוזת המכילה ${\displaystyle w=\lceil (b+1)/8\rceil }$ מילים באורך 64 סיביות כל אחת, לפי סדר בתים קטן: ${\displaystyle m_{0},m_{1},...,m_{w-1}$, כאשר הבית האחרון במילה האחרונה ${\displaystyle m_{w-1}$ מכיל את קידוד אורך הקלט ${\displaystyle b}$ בבתים מודולו 256. הקלט חייב להכיל לפחות מילה אחת, אם הקלט נמוך ממילה אחת או שאורכו אינו כפולה של מילים באורך 64 סיביות, מרפדים באפסים כנדרש (למעט בית האחרון). לדוגמה אם מחרוזת הקלט היא "01234abcde" (בבסיס הקסדצימלי) אז ${\displaystyle b=5}$, ${\displaystyle w=1}$ והמילה ${\displaystyle m_{0}$ מכילה את:

מחברים באופן איטרטיבי את כל מילות הקלט ${\displaystyle m_{i}$ עם המצב הפנימי כאשר ${\displaystyle 0\leq i\leq w-1}$, על ידי:

מבצעים ${\displaystyle c}$ איטרציות של פונקציית הסבב SipRound (המפורטת בהמשך) ולאחר מכן מבצעים על כל מילות הקלט:

3. סיומת. לאחר עיבוד כל מילות הקלט כמתואר, מבצעים XOR של הקבוע ${\displaystyle {\text{0xff}$ עם המילה השלישית של המצב הפנימי:

ואז מבצעים ${\displaystyle d}$ איטרציות של פונקציית הסבב SipRound ומחזירים את 64 הסיביות שהן תוצאה של:

פונקציית הסבב SipRound

הטרנספורמציה SipRound המומחשת בתרשים משמאל מבצעת את הפעולות הבאות על המצב הפנימי של האלגוריתם:

${\displaystyle v_{0}=v_{0}\boxplus v_{1}$	${\displaystyle v_{2}=v_{2}\boxplus v_{3}$
${\displaystyle v_{1}=v_{1}\lll 13}$	${\displaystyle v_{3}=v_{3}\lll 16}$
${\displaystyle v_{1}=v_{1}\oplus v_{0}$	${\displaystyle v_{3}=v_{3}\oplus v_{2}$
${\displaystyle v_{0}=v_{0}\lll 32}$
${\displaystyle v_{2}=v_{2}\boxplus v_{1}$	${\displaystyle v_{0}=v_{0}\boxplus v_{3}$
${\displaystyle v_{1}=v_{1}\lll 17}$	${\displaystyle v_{3}=v_{3}\lll 21}$
${\displaystyle v_{1}=v_{1}\oplus v_{2}$	${\displaystyle v_{3}=v_{3}\oplus v_{0}$
${\displaystyle v_{2}=v_{2}\lll 32}$

כאשר הסימן ${\displaystyle \oplus }$ הוא XOR, הסימן ${\displaystyle \lll }$ מייצג הזזה מעגלית של סיביות שמאלה, בגבולות מילה באורך 64 סיביות, לפי מספר הפוזיציות המצוין לאחריו. הסימן ${\displaystyle \boxplus }$ מייצג חיבור מודולו ${\displaystyle 2^{64}$. היסטי ההזזות נבחרו באופן אמפירי, תוך מתן דגש על ערכים המיושרים לגבולות בתים או מילים להאצת ביצועים ומניעת עיכובים בצינור העיבוד.

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

SipHash-c-d כאשר ${\displaystyle c\geq 2}$ וכן ${\displaystyle d\geq 4}$ אמורה לספק לדעת המפתחים מקסימום ביטחון כפונקציה פסאודו אקראית. הביטחון הגבוה ביותר שניתן להשיג עם כל פונקציית PRF לאימות מסרים. לשימוש רגיל ההמלצה שלהם היא SipHash-2-4 (כלומר שני סבבים של הפונקציה הפנימית ואחריהן ארבעה סבבים של הפונקציה המסיימת) ולשימוש שמרני יותר SipHash-4-8 שהיא איטית פי שניים מהראשונה. מהיבט תאורטי, ביטחון פונקציית PRF סטנדרטית מניח שלמתקיף גישה לפלט הפונקציה על קלטים שנבחרו על ידו באופן אדפטיבי (שזהו המודל המחמיר ביותר), אך הוא אינו רשאי לראות את המפתח, או לצורך הדיון כאן, אין ביכולתו להשיג גישה ל"מפתחות קשורים", "מפתחות ידועים" או "מפתחות נבחרים" (כל אילו מודלים של ביטחון שמניחים שלמתקיף שליטה מסוימת גם אם חלקית ועקיפה על חומר המפתח הסודי). במצב זה ביטחון הפונקציה תלוי באורך המפתח. היות שהמפתח באורך 128 סיביות, אם המתקיף מבצע ${\displaystyle s}$ שאילתות (ניסיונות אימות) סיכוייו לנחש את המפתח שואפים ל-${\displaystyle 2^{s-128}$. בהנחה שלא קיימת דרך טובה מכוח גס. הביטחון המושג מוגבל גם בגלל אורך הפלט. כלומר כאשר משתמשים ב-SipHash כקוד אימות, אם המתקיף מסוגל לבצע ${\displaystyle 2^{s}$ שאילתות הוא יצליח לזייף תג אימות בהסתברות של ${\displaystyle 2^{s-64}$. חשוב להדגיש ש-SipHash אינה ולא הייתה מיועדת להיות פונקציה חסינת התנגשויות.

SipHash אימצה טכניקות מהפונקציות BLAKE,‏ Skein ו-JH שהיו מועמדות תקן הגיבוב SHA-3 ועלו לגמר. פונקציות הגיבוב המנויות עברו ביקורת מדוקדקת של מומחים והוצהרו נכון להיום כבטוחות ולכן הסתמכות על חלקים מהם מקלה על ניתוח ביטחון האלגוריתם. מבנה הפונקציה הפנימית הוא ARX (קיצור של חיבור/הזזה/XOR) שהוכח כבטוח ונמצא בשימוש צפנים מודרניים כמו Salsa20. מ-Blake נלקחו המינימליות והפשטות מ-Skein נלקח תהליך הערבוב MIX ומ-JH אומץ רעיון טעינת הקלט לפני ואחרי כל בלוק. היתרון הוא שבניגוד לסגנון הספוג של SHA-3, אפשר לספוג חלק מהקלט ללא ירידה בביטחון מקור ראשון (Preimage).

המפתחים מציינים כי האלגוריתם נבדק נוכח מספר גדול של התקפות קריפטואנליטיות מודרניות ונמצא בטוח לטענתם. כוח גס בסיבוכיות של ${\displaystyle 2^{127}$ אינו מעשי. ניחוש הזיכרון הפנימי דורש בממוצע ${\displaystyle d2^{191}$ פעולות ולכן אינו מעשי. המחברים ניסו התקפות דיפרנציאליות שונות וכן התקפות קריפטוגרפיות אחרות כמו התקפת נקודות שבת וכן התקפת Cube^[3] והתקפת Rebound^[4].

בפונקציית הסבב של 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;
}

ראו גם

• פונקציית גיבוב קריפטוגרפית
• קוד אימות מסרים
• טבלת גיבוב
• SHA-3

קישורים חיצוניים

• אתר האינטרנט הרשמי של SipHash

הערות שוליים