Skein

Skein היא משפחה של פונקציות גיבוב קריפטוגרפיות שפותחה ב-2010 על ידי ניילס פרגוסון ועמיתיו במטרה להציעה לתחרות תקן הגיבוב הפדרלי של NIST שבה הפסידה בסופו של דבר ל-Keccak. פונקציית גיבוב נחשבת לסוס עבודה של הקריפטוגרפיה המודרנית והיא שכיחה בכל מערכת אבטחה מודרנית כחלק מחתימה דיגיטלית, מנגנון סיסמאות, קישור אינטרנטי מאובטח, ניהול מפתחות הצפנה, אנטי-וירוס וכמעט כל פרוטוקול קריפטוגרפי.

מוטיבציה

בשל חולשות, חלקן תאורטיות שהתגלו בפונקציות הגיבוב ממשפחת SHA, נערכה על ידי NIST תחרות פתוחה לבחירת תקן גיבוב מדור חדש SHA-3. למרות שעדיין אין צורך מיידי במעבר לתקן החדש, הדעה הרווחת היא שבעתיד הקרוב מרבית היישומים יעברו. מארגני התחרות הצהירו כי למרות בדיקות מעמיקות שנעשו על ידי מומחים רבים לא נמצאו כשלים או פגמים חמורים באף אחד מחמשת המועמדים המובילים שהוצעו לתקן, ביניהם Skein והם הוצהרו כבטוחים לשימוש.

Skein מעוצבת במיוחד להשגת גמישות, ביצועים, בטחון ופשטות אופטימליים והיא מהירה מאד הן בחומרה והן בתוכנה עם זיכרון פנימי באורך 200 בתים. ניתן ליישמה גם בחומרת 8 ביט כמו כרטיס חכם בשטח של 100 בתים. Skain-512 פועלת במהירות של 6.1 CPB על מעבד 64 ביט, במילים אחרות על מחשב ממוצע Skein יכולה לגבב מעל 500MB לשנייה לליבה, שזה מהיר פי שניים ויותר מ-SHA-2. בתצורת עץ גיבוב (Tree Hash) להלן, אפשר להגיע לביצועים טובים אף יותר על ידי יישום מקבילי.

Skein נחשבת לפונקציית גיבוב בטוחה בעיצוב שמרני המבוססת על צופן בלוקים Threefish במצב הפעלה שנקרא UBI שהוא גרסה של מטיאס-מאייר-אוסאס. היא מגיעה בשלוש מידות שונות בהתאם לגודל הזיכרון הפנימי: Skain-256, Skein-512, Skein-1024 כאשר הפלט יכול להיות בכל אורך רצוי. כוונת המפתחים היא ליצור חלופה טובה לאלגוריתמים הקיימים באופן שלא יהיה צורך בשינויים מהותיים במערכות קיימות. מסיבה זו Skein נבנתה תוך ראייה רחבה שתהיה כלי שימושי במגוון תחומים כמו מחולל פסאודו-אקראי, צופן זרם, פונקציית גזירת מפתח או פונקציית אימות.

Skein

מבנה כללי של פונקציית הגיבוב Skein

Skein (פְּקַעַת בעברית) בנויה משלושה רכיבים עיקריים:

• צופן הבלוקים Threefish.
• מצב הפעלה Unique Block Iteration.
• מערכת ארגומנטים אופציונליים.

Threefish

ערך מורחב – Threefish

צופן הבלוקים Threefish הוא צופן בלוקים בר-התאמה פשוט ומהיר המקבל בלוק קלט, מפתח הצפנה ו-tweak המשרת כמו וקטור אתחול ומחזיר בלוק מוצפן. הרעיון הבסיסי בצופן הוא שלוש פעולות פשוטות: XOR, חיבור והזזה מעגלית בהיסטים קבועים, שמופעלות במספר חזרות גבוה בניגוד לצופן המכיל פעולות מרכבות יותר אך עם פחות חזרות. Threefish פותח בשביל Skein אם כי יכול לשמש באופן עצמאי.

Unique Block Iteration

דוגמה למבנה UBI של פונקציית הגיבוב Skein-512 עם קלט באורך 166 בתים (שלושה בלוקים). בסך הכול התבצעו שלוש קריאות לצופן Threefish. בדוגמה זו הושמטו מספר שדות למען הפשטות

מבנה UBI הוא מצב הפעלה בסגנון מטיאס-מאייר-אוסאס (כמתואר בתרשים), הפועל מעל צופן בלוקים בר-התאמה (tweakable) עם בלוק ומפתח הצפנה בגודל זהה ועם tweak. הפונקציה ${\text{UBI}}(G,M,T_{s})$ מקבלת שלושה פרמטרים:

• $G$ ערך התחלתי בגודל $N_{b}$ בתים. כאשר $N_{b}\in \{32,64,128\}$.
• $M$ מסר באורך מקסימלי של $2^{96}-1$ בתים.
• $T_{s}$ tweak באורך 16 בתים.

מבנה UBI מעבד בלוק אחר בלוק עם tweak שונה עבור כל בלוק. כאשר בנוסף קיים בלוק מיוחד שנקרא "בלוק קונפיגורציה" המכיל פרטים שונים אודות התצורה הנבחרת והוא מעובד ראשון.

מערכת ארגומנטים אופציונליים

כדי להתאים את Skein למגוון השימושים האפשריים הוא כולל מספר אופציות:

• מפתח אופציונלי. שדה הכולל מפתח הצפנה סודי, באופן זה הפונקציה תשמש כקוד אימות מסרים או פונקציה לגזירת מפתח הצפנה.
• בלוק קונפיגורציה. הבלוק הראשון המכיל את המידע על אופן השימוש בפונקציה.
• פרסונליזציה. מחרוזת כלשהי המכילה מידע ספיציפי למשתמש, כך שאפשר להתאים את Skein לשימוש אישי. שדה זה משפיע על הפלט.
• מפתח ציבורי. אופציה המאפשרת שילוב מפתח ציבורי של המשתמש על מנת ליצור ערך גיבוב מהמסר עם המפתח, כך שמסר המיועד לחתימה דיגיטלית עם מפתחות שונים יפיק ערך גיבוב שונה עבור כל מפתח.
• מזהה פונקציית גזירת מפתח. משולב יחד עם השדה הראשון על מנת להפיק מפתחות הצפנה רבים ממפתח מאסטר יחיד.
• Nonce. אם משתמשים בפונקציה כצופן זרם או כפונקציית גיבוב ראנדומלית, ערך זה משמש כוקטור אתחול. זאת על מנת להבטיח ששני מסרים זהים תמיד יפיקו תוצאה אחרת.
• קלט. הקלט הרגיל שאינו חובה. במידה ואין קלט הפונקציה תשרת כמחולל פסאודו-אקראי.
• פלט. פונקציית הפלט שמחזירה את ערך הגיבוב.

ריפוד

אם אורך הקלט בסיביות אינו מתחלק ב-8 (אינו בבתים שלמים), מוסיפים סיבית "1" בסוף הקלט ומאפסים את יתרת הסיביות עד שמגיעים למחרוזת בתים שלמים. במקרה זה קובעים את הדגל ${\text{BitPad}}=1$ (חלק מה-tweak להלן). בדרך זו קל להסיר את הריפוד מבלי לדעת מה היה אורך המסר בדיוק. אם אורך הקלט הוא $N_{m}$ בתים, מוסיפים $p$ בתי אפס בסופו כדי להשלימו לבלוק אחד לפחות באורך $N_{b}$ בתים. אם אין קלט יתקבל בלוק אחד ריק. כלומר התוצאה צריכה להיות $k$ בלוקים $M_{0},M_{1},...,M_{k-1}$ באורך $N_{b}$ בתים כל אחד כאשר $k\geq 1$.

Tweak

ה-tweak הוא משתנה עזר באורך 128 סיביות (16 בתים) המחולק לשדות ערכים ברמה של סיביות כמתואר בתרשים.

תרשים מבנה ה-Tweak

להלן פירוט שדות ה-tweak:

שם שדה	סיביות	תיאור
Position	0-95	מספר שלם המייצג את מספר בתי הקלט שעובדו עד עכשיו כולל הבלוק הנוכחי
Reserved	96-111	לא בשימוש, חייב להיות אפס
TreeLevel	112-118	מספר המייצג את הרמה בעץ הגיבוב, אפס אם לא בתצורת עץ
BitPad	119	שווה 1 אם מספר סיביות המסר בבלוק האחרון אינו מתחלק ב-8
Type	120-125	שדה סוג המקודד לפי טבלת הסוגים להלן
First	126	שווה 1 עבור הבלוק הראשון אחרת אפס
Last	127	שווה 1 עבור הבלוק האחרון אחרת אפס

פונקציית הגיבוב

גיבוב מסר נעשה על ידי הפעלה של UBI במספר חזרות רצוי לפי הנוסחה הבאה:

$H_{0}=G$

$\mathbf {UBI} {\boldsymbol {(H_{i},M_{i},T_{s})}}$ $T_{s}=T_{s}+{\text{min}}(N_{M},(i+1)N_{b})+a_{i}2^{126}+b_{i}(B2^{119}+2^{127})$ $H_{i+1}=E(H_{i},T_{s},M_{i})\oplus M_{i}$ ${\text{Return }}H_{i+1}$

הערך $T_{s}$ מייצג את ה-tweak שכולל את שלושת השדות ${\text{TreeLevel}}$, ${\text{Type}}$ וכן ${\text{Position}}$ כשהם מקודדים כמספר שלם באורך 128 סיביות (באמצעות פונקציה להמרת מערך בתים למילה) בנוסף לסיביות הדגלים הבאים; דגל בלוק ראשון $a_{i}$, דגל בלוק אחרון $b_{i}$ ודגל ריפוד $B$. הביטוי $a_{i}2^{126}$ פירושו הצבת הסיבית $a_{i}$ בפוזיציה 126 ב-tweak וכן לגבי הערכים הבאים. את שדה הפוזיציה שהיא אופסט לבלוק הנוכחי מעדכנים כך $(i+1)N_{b}$ דהיינו מספר הבלוק כפול מספר המילים לבלוק (למעט בבלוק האחרון שהוא $N_{m}$ אם המסר אינו מתחלק לבלוקים שלמים). $a_{i}=1$ רק בבלוק הראשון ו-$b_{i}=1$ רק באחרון, בכל היתר הם אפס. $B$ הוא הסיבית הריפוד. בכל סבב מעבדים את ערך הביניים מסבב קודם ובלוק הקלט הבא באמצעות צופן הבלוקים הפנימי $E$ בשילוב עם ה-tweak וערך הביניים המשמש כמפתח הצפנה ואת התוצאה מחברים ב-XOR עם הבלוק הנוכחי. כל קריאה ל-UBI מתבצעת עם ערכים שונים מסיבה זו התוצאה תהיה תמיד שונה ללא קשר לקלט. הקריאה הראשונה ל-UBI נעשית עם בלוק קונפיגורציה, הכולל פרטים אודות אופן השימוש שנבחר. יתר הקריאות למעט האחרונה הן של בלוקים של המסר בזה אחר זה. לסיכום תצורת גיבוב רגילה נראית כך:

$\mathbf {Skein} {\boldsymbol {(M)}}$

$K'=0^{N_{b}}$

$G_{0}={\text{UBI}}(K',C,T_{\text{cfg}}2^{120})$

$G_{1}={\text{UBI}}(G_{0},M,T_{\text{msg}}2^{120})$

$H={\text{Output}}(G_{1},N_{o})$

${\text{Return }}H$

$K'$ הוא מחרוזת אפסים באורך $N_{b}$ בתים ו-$C$ הוא בלוק הקונפיגורציה המפורט בטבלה. הביטוי $T_{\text{cfg}}$ המקודד לפי הטבלת הסוגים להלן, פירושו שזהו בלוק הקונפיגורציה, ההכפלה ב-$2^{120}$ היא דרך לתאר הכנסת הערך לפוזיציה המתאימה ב-Tweak (ראה תרשים).

טרנספורמציית הפלט

הקריאה האחרונה לפונקציה ${\text{Output}}(G,N_{o})$ היא לצורך הפקת פלט הגיבוב הסופי. הפונקציה מקבלת את ערך הביניים $G_{1}$ (האחרון שהתקבל) ומספר סיביות הפלט הרצויות $N_{o}$ ומחזירה את ערך הגיבוב באורך הרצוי על ידי חזרה על פונקציית הפלט במספר הפעמים הדרוש ושרשור התוצאות למחרוזת אחת ארוכה. אורך הפלט המקסימלי הוא $2^{61}$ בתים. פונקציית הפלט קוראת ל-UBI עם מונה פנימי בגודל 8 בתים המתחיל באפס, כדלהלן:

$O={\text{UBI}}(G,0,T_{\text{out}}2^{120})\ \|\$

${\text{UBI}}(G,1,T_{\text{out}}2^{120})\ \|\$

${\text{UBI}}(G,2,T_{\text{out}}2^{120})\ \|\$

$\cdots$

${\text{Output the first}}\left\lceil N_{o}/8\right\rceil {\text{ bytes of }}O$

סוגים

Skein כולל מערכת הארגומנטים שפותחה כדי לאפשר תאימות לאחור והוספת אופציות בעתיד. האופציות מעובדות בעזרת UBI לפי הסדר. כל קלט מתאפיין בסוג שונה עבור קידוד ה-tweak. בכל מקרה התוספת אינה משפיעה על ביצועי האלגוריתם. הפרמטרים האפשריים של Skein כוללים:

סמל	ערך	תיאור
key	0	מפתח MAC או KDF
cfg	4	קונפיגורציה
prs	8	פרסונליזציה
PK	12	מפתח ציבורי (עבור חתימה דיגיטלית)
kdf	16	מזהה מפתח עבור KDF
non	20	ערך חד פעמי Nonce עבור צפן זרם
msg	48	קלט
out	63	פלט

קונפיגורציה

בלוק הקונפיגורציה באורך 32 בתים מכיל את השדות הבאים:

• מזהה סכמה. מחרוזת כלשהי באורך 4 בתים לפי בחירת המשתמש. עבור התקן נקבעה ל-"SHA3" או בייצוג הקסדצימלי ${\text{0x33414853}}$
• גרסת אלגוריתם כמספר שלם באורך שני בתים (גרסה נוכחית היא 1).
• שני בתים ריקים.
• אורך הפלט הרצוי בסיביות המקודד כמספר שלם באורך שמונה בתים. הכללת אורך המסר בבלוק הקונפיגורציה מבטיחה שתוצאת פונקציית הגיבוב על שני מסרים השונים רק באורכם (כגון אם מסר אחד הוא התחלה של מסר אחר), תהיה תוצאה שונה לגמרי.
• בית אחד המייצג גודל עלה (בבלוקים) בעץ הגיבוב (רלוונטי רק בתצורת עץ).
• בית אחד המייצג את מספר העלים האפשרי לרוחב (רלוונטי רק בתצורת עץ).
• בית אחד המייצג את גובה העץ המקסימלי, אם אין מגבלה ערך זה נקבע ל-255 (רלוונטי רק בתצורת עץ).
• 13 בתים ריקים

MAC

הדרך המקובלת לשימוש בפונקציית גיבוב כקוד אימות מסרים היא בתצורת HMAC. אולם Skein מציעה דרך יותר יעילה כיוון שיש לה תקורה כמעט אפסית. הפיכת Skein לקוד אימות מסרים פשוטה. במקום להתחיל באפס מעבדים תחילה את בלוק המפתח ועם התוצאה מעבדים את בלוק הקונפיגורציה. וכן כיוון שבדרך כלל מאמתים מספר מרובה של מסרים עם מפתח יחיד, אפשר לשפר ביצועים על ידי חישוב בלוק המפתח מראש.

עץ גיבוב

סכמת עץ גיבוב עם Skein

הקונספט של עץ גיבוב מאפשר חישוב מקבילי של קוד גיבוב של מסרים ארוכים מאד כמו קובץ וידאו. במעבד מרובה ליבות אפשר לחלק את העבודה כך שכל מעבד יחשב במקביל חלק אחר של המסר. הרעיון הוא פשוט במקום לחשב את קוד הגיבוב של כל המסר בבת אחת, מחלקים אותו למקטעים בגודל סביר שנקבע לפי הגדרות מקומיות, מחשבים את קוד הגיבוב על כל המקטעים באופן מקבילי ואז משרשרים את תוצאות הגיבוב של כל המקטעים למחרוזת קלט חדשה וחוזרים על התהליך עם הקלט החדש שוב ושוב עד שנשארים עם בלוק אחד שהוא תוצאת הגיבוב הסופית. ב-Skein ישנם שלושה פרמטרים בבלוק הקונפיגורציה שתומכים בעץ גיבוב: השדה $Y_{l}$ - המייצג את גודל העלה לפי הנוסחה $N_{b}2^{Y_{l}}$ כאשר $Y_{l}\geq 1$. השדה $Y_{f}$ המייצג את מקסימום העלים או הפריסה לרוחב של העץ לפי הנוסחה $2^{Y_{f}}$ כאשר $Y_{f}\geq 1$. והשדה $Y_{m}$ המייצג את גובה העץ המקסימלי, כאשר $Y_{m}\geq 2$ אם הגובה אינו מוגבל שדה זה נקבע ל-255.

ראו גם

• פונקציית גיבוב קריפטוגרפית