Hummingbird (צופן)

בקריפטוגרפיה, **Hummingbird** הוא שם כולל למשפחה של צפני בלוקים קלי משקל המיועדים להצפנת תקשורת בחומרה מוגבלת משאבים כתיוג אלקטרוני,מיקרו-בקר, כרטיס חכם וסנסור אלחוטי. Hummingbird הוא פיתוח ייעודי בהשראת מכונת האניגמה במבנה *היברדי* המשלב צופן בלוקים עם צופן זרם, הוא המקבל בלוק טקסט קריא באורך 16 סיביות (שני בתים), מפתח הצפנה באורך 256 סיביות (32 בתים), הוא כולל מצב פנימי (זיכרון) באורך 80 סיביות (עשרה בתים) ומפיק בלוק מוצפן באורך 16 סיביות. השילוב של סיביות המפתח והזיכרון הפנימי מספק לדעת המפתחים ביטחון רב נגד קריפטואנליזה מודרנית (דיפרנציאלית וליניארית). הוא מתאים להטמעה במערכות משובצות מחשב זעירות, יעיל בתוכנה וגם בחומרת 8-ביט/16-ביט. נחשב צופן בלוקים קל משקל 'סטייט אוף דה ארט' ומציג ביצועים טובים מצופן PRESENT.

הצופן הראשון Hummingbird (בעברית "יונק דבש") פותח ב-2009 על ידי דניאל אנגלס מחברת Revere Security ועמיתיו מ-CACR (מרכז מחקר לקריפטוגרפיה יישומית) אוניברסיטת ווטרלו קנדה. הוצג ב-2010 WLC (ועידה שנתית בינלאומית לקריפטוגרפיה קלת משקל עבור חומרה מוגבלת משאבים) וב-RISC ’09. עד כמה שידוע אינו מוגן בפטנט וחופשי לשימוש. הצופן Hummingbird-2 פותח ב-2011 בעקבות קריפטואנליזה של קודמו והוצג ב-RFIDSec'11. הוא מספק הצפנה מאומתת, אורך המפתח הופחת ל-128 סיביות והזיכרון הפנימי הורחב ל-128 סיביות. הוא מכיל שיפורים אחדים לעומת קודמו כדי לחזקו נגד קרפיטואנליזה. המפרט שלו, התפוקה והביטחון שלו מותאמים לתקן איזו ISO/IEC 18000-6:2010.

## מבוא ותיאור כללי
השפעת טכנולוגית מחשוב מפושט (Pervasive Computing) כמו RFID, כרטיסים חכמים וסנסורים אלחוטיים על חיי היום יום הולכת ומתרחבת. השימוש בהם פורץ לכל תחומי החיים, מבקרה ושליטה מרחוק, בית חכם, ניהול שירותי אספקה כמו מדי חשמל ומים ועד ניטור רפואי. כל אילו מערבים עיבוד ושידור מידע רגיש, כמו מידע ביו-רפואי או מידע על צריכה או אספקה של מוצרים ולכן יש צורך להטמיע במערכות אילו מנגנון קריפטוגרפי שיאפשר לשמור על דיסקרטיות ולהבטיח את שלמות המידע. ברוב המקרים מכשירי מחשוב מפושט מכילים מעבד זעיר שפועל על אנרגיה חיצונית כמו כרטיס חכם או על סוללה זעירה שאמורה להחזיק מעמד זמן רב ללא טעינה. מסיבה זו הוא פועל על משאבים כמו זיכרון וכוח מחשוב אולטרה נמוכים בהשוואה למחשב שולחני. צפנים סימטריים רגילים אינם מתאימים במיוחד לעבודה בסביבה כזו. רובם, במיוחד AES פותחו עוד בטרם הטכנולוגיה הזו פרצה לתודעה.

קריפטוגרפיה קלת משקל פותחה כדי לתת מענה לצורך זה. בין היתר פותחו צפני בלוקים בקטגוריה **צפני בלוקים קלי משקל** שהיעד העיקרי בהם הוא לפעול בסביבה בה יש צורך לשקלל או להתפשר על מספר גורמים: ביטחון מול עלות מול ביצועים ולהשיג את המיטב בתנאים מוגבלים. קיימות כיום מספר הצעות טובות המתחלקות לשלוש קטגוריות עיקריות: *מיטוב* צפנים קיימים כמו AES ו-IDEA, *שינוי* צפנים קיימים כמו DES-XL והשלישי פיתוח צפנים ייעודיים כמו HIGHT, SEA, KATAN ו-PRESENT. בנוסף קיימים צפני זרם קלי משקל ביניהם גריין ו-Trivium.

ל-Hummingbird מבנה היברידי ייחודי בהשראת מכונת האניגמה, המשלב צופן בלוקים עם צופן זרם (מכיל זיכרון פנימי מה שמאפשר בלוק קטן) ופותח מתוך כוונה שיהיה יעיל, פשוט וקל ככל האפשר להטמעה והרצה.

## תיאור צופן Hummingbird
מבנה Hummingbird בנוי באופן בלתי שגרתי בניסיון ליהנות מיתרונות שני תחומים שונים בהצפנה סימטרית, צופן זרם וצופן בלוקים. הוא מורכב מצופן בלוקים המקבל קלט באורך 16 סיביות ומתחלק לארבעה עם ארבעה מפתחות שונים: E_{k_1}, E_{k_2}, E_{k_3}, E_{k_4} בהתאמה, ארבעה אוגרים פנימיים באורך 16 סיביות כל אחד: RS1,RS2,RS3,RS4 ואוגר זיזה ממושב LFSR עם 16 מצבים. המפתח הסודי המסופק על ידי המשתמש מחולק לארבעה תת-מפתחות באורך 64 סיביות: k_1,k_2,k_3,k_4 המתאימים לצופן הבלוקים האמור.

להצפנה, בלוק טקסט קריא באורך 16 סיביות PT_i מחובר תחילה מודולו 2^{16} עם תכולת האוגר הראשון RS1 והתוצאה מוצפנת עם צופן הבלוקים הראשון E_{k_1} והפלט הופך קלט לשלב הבא. תהליך זה חוזר על עצמו בדרך דומה שלוש פעמים נוספות עם יתר האוגרים והצפנים, כאשר פלט E_{k_4} הוא הטקסט המוצפן CT_i. המצב הפנימי (ארבעת האוגרים) של הצופן מעודכן באופן בלתי צפוי, בהתאם לערכם הנוכחי, פלט שלושת צפני הבלוקים הראשונים וה-LFSR יחד. פענוח מתנהל בדרך דומה להצפנה אף בסדר הפוך.

לצופן שלושה מצבים אפשריים: מצב אתחול, מצב הצפנה ומצב פענוח. לפני הצפנה/פענוח יש צורך לאתחל את המצב הפנימי של הצופן כדלהלן: תחילה וקטור אתחול המונה ארבעה ערכים אקראיים באורך 16 סיביות: \text{NONCE}_i כאשר i=1,2,3,4 נטען לתוך ארבעת האוגרים בהתאמה ואז מצפינים את RS1\boxplus RS3 (חיבור של האוגר הראשון והשלישי מודולו 2^{16}) במצב אתחול כשהפלט הסופי TV_i משמש כערכים התחלתיים של ה-LFSR. יתרה מזו, הסיבית ה-13 של ה-LFSR נקבעת תמיד ל-1 כדי למנוע מצב שהאוגר יהיה כולו אפסים. ה-LFSR מופעל פעימה אחת לפני שהוא מפיק פלט כדי לעדכן את האוגר השלישי. הטבלה הבאה מסכמת את מהלכי האלגוריתם בשלושת המצבים האמורים:

### צופן בלוקים 16-ביט
צופן הבלוקים הפנימי E_{k_i} בנוי בסגנון רשת החלפה-תמורה עם בלוק באורך 16 סיביות (2 בתים) ולמעשה מחולק לארבעה צפנים כשכל אחד מהם מקבל  תת-מפתח K^{(i)} באורך 64 סיביות (8 בתים) כאשר i\in\{1,2,3,4\} מתייחס למספר הצופן. למעט המפתח השונה הצופן זהה בכל הארבעה והוא פועל עם ארבעה סבבים רגילים בשלוש שכבות החלפה/פיזור/הוספת מפתח וסבב חמישי המכיל רק את שכבת הוספת המפתח וההחלפה לא הפיזור. תת-המפתח מחולק לארבעה מפתחות קטנים באורך 16 סיביות כל אחד: k_1^{(i)},k_2^{(i)},k_3^{(i)},k_4^{(i)} כל מפתח מתאים לסבב אחד ולצורך הסבב האחרון מכינים שני מפתחות נוספים k_5^{(i)},k_6^{(i)} הנגזרים ישירות מהמפתחות הקודמים (המפתח החמישי הוא תוצאת XOR של המפתח הראשון עם השני והמפתח השישי הוא XOR של המפתח השני עם הרביעי).

בארבעת הסבבים הראשונים של הצופן שלוש השכבות מתבצעות כך: 
# המפתח מחובר ב-XOR עם הקלט (16 סיביות).
# ההחלפה מתבצעת עם ארבע תיבות ההחלפה בסגנון סרפנט המקבלות ארבע סיביות ומחזירות ארבע סיביות, עם קריטריון נוסף, המעלה של כל תיבת החלפה בהצגה בוליאנית שלה תהיה לפחות 3. 
# שכבת הפיזור מתבצעת על ידי הטרנספורמציה הליניארית: L(m)=m\oplus (m\ll 6)\oplus (m\ll 10).
כאשר m=(m_0,m_1,...,m_{15}) הוא בלוק הקלט באורך 16 סיביות. כדי לחסוך בצריכת זיכרון ואנרגיה אפשר להשתמש רק בתיבת החלפה אחת במקום ארבעה. הגרסה עם תיבת החלפה אחת החוזרת על עצמה ארבע פעמים היא קומפקטית ומשיגה אותה רמת ביטחון כמו עם ארבע תיבות החלפה שונות.

בסבב האחרון לא מבצעים את שכבת הפיזור אלא מבצעים XOR עם המפתח האחרון.

### תיבות ההחלפה

## Hummingbird-2
Hummingbird-2 הוא צופן בלוקים היברידי המיועד לחומרה מוגבלת משאבים, פותח בהשראת האניגמה ומשלב תכונות של צופן בלוקים עם צופן זרם. הוא מקבל מפתח סודי באורך 128 סיביות ווקטור אתחול באורך 64 סיביות ומצפין בלוק מידע באורך 16 סיביות ואם נדרש מייצר בנוסף תג אימות עבור כל בלוק קלט שהוצפן. כקודמו Hummingbird-1 זהו צופן קל משקל שפותח בעיקר עבור מיקרו-בקרים ומערכות משובצות מחשב בהתקנים קטנים כמו RFID וסנסור אלחוטי. בהשוואה לגרסה הקודמת ובהתחשב בקריפטואנליזה חדשה של הצופן בעיקר בגרסה הקודמת נעשו מספר שינויים. המצב הפנימי הורחב ל-128 סיביות, פונקציית העדכון של המצב הפנימי שופצה בהתאם. כמו כן נעשו שינויים בתיבות ההחלפה ופונקציית הסבב הפנימית.

### הצפנה מאומתת

Hummingbird-2 משמש גם כ**אלגוריתם הצפנה מאומתת** המספק במקביל סודיות והגנה על שלמות המידע בריצה אחת. כתוצאה מכך יעילות האלגוריתם גבוהה במיוחד ביישום בחומרה. כקודמו, הצופן אינו מתאים בדיוק לקטגוריה של צופן בלוקים או צופן זרם, אלא מעין הכלאה של השנים בסגנון דומה לצפנים Helix ו-Phelix. הוא פותח בעקבות הפקת לקחים במיוחד לאור קריפטואנליזה של Saarinen נגד הצופן הקודם Hummingbird-1 ולדעת המפתחים הצופן החדש עמיד נגד כל ההתקפות הקריפטואנליטיות הידועות, אם כי קיים מחקר שמראה אחרת.

### תיאור האלגוריתם
Hummingbird-2 מקבל בלוק טקסט גלוי באורך 16 סיביות (שני בתים), מפתח סודי באורך 128 סיביות (32 בתים) ווקטור אתחול באורך 64 סיביות (16 בתים) ומפיק בלוק מוצפן באורך 16 סיביות וכן במידה שנדרש מפיק **תג אימות** (באורך של עד שמונה מילים) של הבלוק המוצפן בנוסף למידע אחר גלוי שנקרא *מידע נלווה* אם קיים, כמו הערכים החד-פעמיים הגלויים המשמשים לאתחול הצופן או חבילת כותר המכילה מידע תפעולי.

וקטור האתחול IV מחולק לארבע מילים: IV_1,IV_2,IV_3,IV_4, המפתח הסודי K מחולק לשמונה מילים: K_1,K_2,...,K_8 והמצב הפנימי (הזיכרון) R של הצופן מחולק לשמונה אוגרים: R_1,R_2,...,R_8. כל המילים הן באורך 16 סיביות. הפעולות הן חיבור מודולו 65536, XOR ופונקציית ערבוב אי-ליניארית f(x). הפונקציה האי-ליניארית מורכבת מארבע תיבות תמורה לפי טבלה קבועה על כל המילים ולאחריהם מתבצע פיזור ליניארי. תיבות ההחלפה מוצגות בטבלה הבאה:

תיבות ההחלפה של Hummingbird-2 תופסות שטח של 256 סיביות (32 בתים).

להלן הגדרה פורמלית של הפונקציה f(x) המשתמשת בתורה בפונקציית ההחלפה S(x) הכוללת את ארבע תיבות ההחלפה המתוארות ובפונקציה הליניארית L(x):

### פונקציית ההצפנה
מבנה כללי של פונקציית הסבב הפנימית WD16(x,a,b,c,d) המקבלת חמש מילים, את הקלט x וארבעה מפתחות ומשתמשת ב-f הוא:

:\boldsymbol{WD16(x, a, b, c, d) = f(f(f(f(x \oplus a) \oplus b) \oplus c) \oplus d)}

הפונקציה ההופכית f^{-1}(x) וכן הפונקציה ההופכית WD16^{-1} נגזרות ישירות מהפונקציות האמורות.

### אתחול
המצב הפנימי של הצופן מאותחל בארבעה מהלכים. תחילה טוענים את וקטור האתחול:
:R^{(0)}=(IV_1, IV_2, IV_3, IV_4, IV_1, IV_2, IV_3, IV_4)
ומפעילים את פונקציית הסבב ארבע פעמים:

המצב ההתחלתי לפני ההצפנה של הבלוק הראשון הוא R^{(4)}. הסמל \langle \ i \ \rangle מייצג את המשלים ל-2 של i.

### הצפנה
פונקציית ההצפנה של בלוק אחד: C_i=E(P_i) מבצעת ארבע קריאות לפונקציית הסבב הפנימית:

והטקסט המוצפן הוא C_i.

פענוח מתבצע בדרך דומה אך עם הפונקציות ההופכיות ובסדר הפוך של המפתחות.

### עדכון מצב פנימי
לאחר הצפנה או פענוח מבצעים את המהלכים הבאים לעדכון המצב הפנימי:

### תג אימות
לאחר עיבוד כל המידע המוצפן והמידע הגלוי (שאינו מוצפן רק מועבר כמו שהוא) אפשר לייצר תג אימות T באורך של n\le 8 מילים. תחילה מפעילים את הצופן שלוש פעמים ללא פלט כלשהו:

כאשר R_1 ו-R_3 מייצגים את תכולת הזיכרון באוגרים האמורים בכל סבב לפני הפעלת פונקציית ההצפנה E. התג T מורכב מהמילים:

### מצב הפעלה המדמה צופן זרם
לעיתים נדרש להצפין ולאמת יחידות מידע הקטנות ממילה באורך 16 סיביות, במקרה כזה אפשר פשוט להצפין את המידע על ידי תוצאה חתוכה של פונקציית ההצפנה. למשל אם המידע x באורך n סיביות, כאשר n\le 15 מצפינים פעם אחת בלוק של 16 אפסים ומחברים ב-XOR את n הסיביות הראשונות של התוצאה המוצפנת עם בלוק המידע x כך: C=x\oplus E(0). לצורך תג האימות ממשיכים להריץ את הצופן, מעדכנים את המצב הפנימי ומפיקים תג אימות כמתואר לעיל.

היות ש-Hummingbird-2 הוא אלגוריתם הצפנה מאומתת כמו GCM, הוא כולל שימוש בווקטור אתחול חד-פעמי. אף על פי שצופן זה אינו רגיש לשימוש חוזר כמו GCM, מומלץ להימנע משימוש חוזר בווקטור אתחול כל עוד המפתח לא הוחלף (אחד משניהם חייב להיות שונה לפני שמצפינים ומאמתים מסרים נוספים). במילים אחרות ההסתברות ששני מסרים יוצפנו עם אותו מפתח ואותו וקטור אתחול צריכה להיות נמוכה מ-2^{32}. במקרה שהמשתמש לא עמד בקריטריון זה התוצאה תהיה שהמתקיף יוכל לזהות הצפנה של בלוקים זהים. דבר שרצוי להימנע ממנו במקרים מסוימים.

## ביטחון ועילות
בגרסה הראשונה התגלו חולשות בצופן הבלוקים הפנימי. Markku-Juhani O. Saarinen פרסם התקפה דיפרנציאלית שמסוגלת לשחזר את המפתח תוך מספר מיליוני מסרים נבחרים במה שקרוי התקפת גלוי-נבחר בסיבוכיות של 2^{64} פעולות אוף ליין. גרסה 2 יחסית חדשה ועדיין אין הרבה קריפטואנליזה שלה. קיים מחקר שמבוסס על התנגשויות דיפרנציאליות נגד פונקציית הסבב הפנימית, שמראה שקיימת בה בעיה דומה. המחברים מראים אפשר לשבור את הצופן בזמן של 2^{32.6} בסיבוכיות מקום של 2^{32.6} עם מספר זוגות של מפתחות קשורים.

## ראו גם
* צופן בלוקים
* AES
* מכונת האניגמה
* הצפנה מאומתת

## הערות שוליים

קטגוריה:צפני בלוקים