TEA (צופן)

אלגוריתם הצפנה זעיר (באנגלית: Tiny encryption algorithm) בקיצור TEA הוא שם כולל למשפחה של צפני בלוקים סימטריים איטרטיביים בסגנון רשת פייסטל שייחודם הוא בפשטותם הרבה וקלות מימושם הן בתוכנה והן בחומרה (מכילים מספר שורות קוד בלבד).

הצופן הראשון TEA פותח על ידי דויד ווילר ורוג'ר נידהם מהמכון הטכנולוגי של מסצ'וסטס, הוצג לראשונה ב-1994 בסדנה הקריפטוגרפית FSE בלוון והוא אינו מוגן בפטנט. הצופן מתאפיין במיוחד בפונקציית סבב פנימית פשוטה בתכלית ומספר גבוה של סבבים. מספר הסבבים הגבוה (64 בהצעה המקורית) נועד לחפות על פשטותה של הפונקציה הפנימית. לאחר חולשות וליקויים רבים שהתגלו בו פותח ב-1997 הצופן XTEA (קיצור של TEA מורחב) שנועד לתקן כמה מהם. בנוסף הוצע צופן חדש המותאם לבלוק באורך משתנה הנקרא Block TEA. בגלל קריפטואנליזה של תהליך הכנת המפתח שלו ואפקט הפיזור האיטי יחסית, הוצע על ידי המפתחים ב-1998 טלאי נוסף לאלגוריתם המכונה XXTEA, כל זאת תוך שמירה על ייחודו ופשטותו. כיום ידוע שהצופן, לאחר כל השיפורים, חלש יחסית והוא מכיל מספר חסרונות מהותיים. אפקט הפיזור האיטי של הצופן מעמיד בסימן שאלה את אקראיותו ומאפשר "התקפות הבחנה" (קריפטואנליזה שמבחינה עם יתרון משמעותי בין פלט הצופן למחרוזת אקראית באותו אורך). תהליך הכנת המפתח הפשוט מאפשר מספר התקפות מוצלחות נגד האלגוריתם ביניהן התקפת גלוי-נבחר בסיבוכיות של $2^{59}$. אף על פי שמעשיות התקפה זו נתונה בספק, עדיין נחשב הדבר לשבירה של האלגוריתם כי אינו מציע בטחון ברמה המינימלית הנדרשת ממפתח באורך 128 סיביות. למרות האמור, בשל פשטותו הרבה ייתכן שיהיה ראוי לשימוש בתנאים מסוימים.

רקע

אבסטרקציה של סבב בודד של צופן TEA. הסימנים $<<$ ו-$>>$ מייצגים הזזה לשמאל או לימין בהתאמה (בהזזה הסיביות שמוזזות החוצה נמחקות ובמקומן נוספים אפסים בצד השני), הסימן $\boxplus$ הוא חיבור מודולו 32 והסימן $\oplus$ הוא XOR.

בדרך כלל תקני הצפנה מעדיפים אלגוריתמים היעילים במיוחד בהצפנת כמויות גדולות של מידע ולא תמיד מביאים בחשבון כמות מועטה של מידע. מערכות הפעלה נדרשות לפעמים להצפין או לגבב קבצים קטנים המכילים מספר בתים בודדים ובגלל התקורה הנוספת הנובעת מעבודת ההכנה של אלגוריתם ההצפנה, במיוחד תהליך הכנת מפתח ההצפנה, נוצר מצב שהתקנים הנוכחיים פחות מתאימים וזו אחת הסיבות מדוע MD5 עדיין בשימוש. TEA פותח במטרה למלא את החלל הזה. ייעודו הראשוני היה לפי הצהרת המפתחים להחליף את DES. לטענתם, למרות היותו של TEA פשוט יותר הוא אינו נופל ברמת הבטחון שלו מזו של DES. חברת מיקרוסופט עשתה שימוש בצופן TEA במקום RC4 כחלק מפונקציית גיבוב באבטחת קונסולת המשחקים שלה Xbox, אך בשל העובדה שקיימות בו חולשות מסוימות הוא אינו מתאים למטרה שלשמה נעשה בו שימוש, דבר שגרם לפרצת אבטחה שאפשרה להאקרים לפרוץ את קונסולת המשחקים.

TEA הוא צופן בלוקים פשוט בסגנון רשת פייסטל, הכולל פונקציה פשוטה במספר גבוה של סבבים במקום מבנה פנימי מסובך. הפונקציה הפנימית מבצעת פעולות אריתמטיות בסיסיות ברמת מילים באורך 32 סיביות: XOR, חיבור והזזה (Shift), פעולות שנתמכות על ידי שפות התכנות הנפוצות. כמו ב-DES בלוק הצופן הוא 64 סיביות והוא מקבל מפתח הצפנה באורך 128 סיביות ומחזיר בלוק מוצפן באורך 64 סיביות. הכנת המפתח כמעט שואפת לאפס, הצופן אינו עושה שימוש בטבלאות החלפה או טבלאות פיזור קבועות או דינאמיות. "הערבוב/פיזור" לפי התאוריה של שאנון מושג על ידי תערובת פעולות אלגבריות בחבורות אורתוגונליות שונות (כמו בצופן IDEA). הערבוב האי-ליניארי של הפונקציה הפנימית חלש יחסית כשהתקווה היא שלאחר מספר רב של סבבים יהיה בטוח. הצעת המפתחים היא להריץ את הפונקציה הפנימית לפחות 64 פעמים המבוצעים בזוגות, בסך הכול 32 חזרות.

לא כל מומחי ההצפנה תמימי דעים שהאסטרטגיה של קוד מינימלי עדיפה על יעילות. אפשר להבין שבתנאים מסוימים כמו עם חומרה מוגבלת משאבים לקוד קטן יש יתרון על פני אלגוריתם עם קוד מסובך יותר כמו AES (הכולל טבלאות מקודדות מראש). אך ברוב המקרים אפשר למטב הרבה צפנים ולהתאימם לחומרה או תוכנה ספציפיים, להחליף טבלאות אחזור בקוד זמן ריצה וכדומה. אם זעירות הקוד מהווה יתרון אז TEA נחשב לצופן אטרקטיבי. ברוס שנייר התבטא פעם: "אף פעם לא הייתי אוהד גדול של TEA, אף על פי ש-64 סבבים יכולים לכסות על הרבה חטאים".

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

TEA הוא צופן במבנה רשת פייסטל עם מפתח מאסטר $K$ באורך 128 סיביות המחולק לארבע מילים: $K[0],K[1],K[2],K[3]$ כל אחת באורך 32 סיביות ופועל על בלוק קלט באורך 64 סיביות המחולק לשתי מילים $Y[i]$ ו-$Z[i]$ כאשר $i$ מתייחס למספר הסבב. הכנת המפתח פשוטה, סבב אי זוגי משתמש בשני המפתחות הראשונים, וסבב זוגי בשני המפתחות האחרונים. בכל לולאה של הצופן מבוצעים שני סבבים של הפונקציה הפנימית הכוללים את הפעולות הבאות:

$c=c+\delta ,\ \ Y[i+1]=Y[i]+F(Z[i],K[0,1],c),\ \ Z[i+1]=Z[i]+F(Y[i+1],K[2,3],c)$

הפונקציה $F$ מוגדרת כך:

$F(z,K[i,j],c)=({\text{SL}}_{4}(z)+K[i])\oplus (z+c)\oplus ({\text{SR}}_{5}(z)+K[j])$

כאשר ${\text{SL}}$ ו-${\text{SR}}$ הן פונקציות הזזה לימין או לשמאל בהתאמה, ברמת סיביות, כאשר מספר ההזזות מצוין לאחר השם. $\delta$ הוא קבוע והסימן $\oplus$ מייצג XOR.

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

void TEA(ulong* v, ulong *k)
{
   ulong y = v[0], z = v[1], sum = 0, delta = 0x9e3779b9, n=32;
   while(n-- > 0)
   {
      sum += delta;
      y   += (z << 4) + k[0] ^ z + sum ^ (z >> 5) + k[1];
      z   += (y << 4) + k[2] ^ y + sum ^ (y >> 5) + k[3];
   }
   v[0] = y, v[1] = z;
}

הערך של הקבוע ${\text{delta}}$ הוא ${\text{delta}}=\lfloor 2^{32}/\phi \rfloor ={\text{0x9e3779b9}}$ בבסיס הקסדצימלי כאשר $\phi$ הוא יחס הזהב או בניסוח אחר: ${\text{delta}}=({\sqrt {5}}-1)2^{31}$.

בכל סבב האלגוריתם משתמש בכפולה שונה של ${\text{delta}}$. המטרה היא לטשטש את מבנה הפונקציה $F$ ולגרום לה להשתנות בתדירות גבוהה, כדי למנוע התקפה מאד קלה לשבירת האלגוריתם. לדעת המפתחים ערכו של ${\text{delta}}$ אינו עקרוני, רצוי שיהיה אי זוגי ובלבד שלא יהיה ערך גרוע. כלומר כל ערך שמניב אפקט שינוי איטי.

בטחון

בצופן TEA המקורי התגלו מספר חולשות. דויד וגנר, ג'ון קלסי וברוס שנייר גילו ב-1996 שבגלל העדר תהליך הכנת מפתח הצפנה אפשר לבצע התקפת גלוי-נבחר בסיבוכיות של $2^{32}$ פעולות הצפנה עם "מפתחות קשורים" (מפתחות שקיים יחס כלשהו ביניהם, כמו מפתחות שההבדל ביניהם הוא בסיבית אחת). הפונקציה הפנימית חלשה מדי ואפקט הפיזור איטי מאד וקיימת קריפטואנליזה מוצלחת של הצופן במספר סבבים מופחת וכן התגלה שהצופן סובל מתופעה הנקראת "מפתחות שקולים". לכל מפתח קיימים שלושה מפתחות נוספים (שאם מצפינים עם מפתחות אילו מתקבלת תוצאה זהה). עובדה זו מצמצמת אפקטיבית את טווח המפתח ל-$2^{126}$ סיביות. עובדה זו משליכה גם שהצופן יהיה גרוע מאד לשימוש כחלק מפונקציית גיבוב בגלל שקל למצוא התנגשויות (עובדה שנוצלה לפיצוח קונסולת המשחקים Xbox של מיקרוסופט).

XTEA

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

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

XTEA(long* v, long* k, long N)
{
   ulong y = v[0], z = v[1], DELTA = 0x9e3779b9;
   if (N > 0) { /* coding */
      ulong limit = DELTA * N, sum = 0;
      while (sum != limit) {
         y   += (z << 4 ^ z >> 5) + z ^ sum + k[sum & 3];
         sum += DELTA;
         z   += (y << 4 ^ y >> 5) + y ^ sum + k[sum >> 11 & 3];
      }
   } else { /* decoding */
      ulong sum = DELTA * (-N);
      while (sum) {
         z   -= (y << 4 ^ y >> 5) + y ^ sum + k[sum >> 11 & 3];
         sum -= DELTA;
         y   -= (z << 4 ^ z >> 5) + z ^ sum + k[sum & 3];
      }
   }
   v[0]=y, v[1]=z ;
}

כאשר ${\text{v}}$ מכיל את הקלט כשהוא מחולק לשתי מילים, ${\text{k}}$ מכיל את המפתח המחולק ל-4 מילים ו-${\text{N}}$ מייצג את מספר הסבבים (32 לפי ההמלצה). כאן אם ${\text{N}}$ חיובי האלגוריתם מבצע הצפנה ואילו אם ${\text{N}}$ שלילי האלגוריתם מבצע פענוח.

Block TEA

במקביל הציעו המפתחים שינוי נוסף כדי לתמוך בבלוקים גדולים. במילים אחרות, היכולת להתאים את האלגוריתם לבלוק בכל אורך רצוי מיתרת את הצורך במצב הפעלה. הגרסה החדשה נקראה על ידם Block TEA. בדומה לקודמיו זהו צופן בלוקים איטרטיבי בסגנון רשת פייסטל, המורכב מפונקציה פנימית פשוטה בתכלית ומספר סבבים גבוה. פעולות הצופן נותרו זהות לצופן הקודם במשפחה XTEA אך מבוצעות באופן מחזורי על כל בלוק הקלט. תהליך הכנת המפתח השתנה בהתאם. פונקציית הערבוב הפנימית שהיא בתמצית: $v_{n}=v_{n}+{\text{mix}}(v_{n-1},{\text{key}})$, מקיפה את הקלט במעגליות מספר פעמים. אם מבוצעים 64 סבבים, כשבכל סבב מבוצעות שש פעולות אריתמטיות על כל מילת קלט, יוצא שכל מילה מעובדת $6+52/n$ פעמים ובסך הכול מופעלות בממוצע לפחות 6 פעולות ערבוב על כל מילה. אם $n\geq 4$ גרסה זו מהירה יותר מ-XTEA למרות התקורה הנוספת, אולם אם $n=2$ היא איטית יותר. המפתחים מציינים שהם אינם יכולים להוכיח בוודאות שגרסה זו בטוחה מהקודמת, אך הם ממליצים להשתמש בה מכמה סיבות ביניהן: אפקט הפיזור גבוה יותר ונשמר לאורך כל הקלט וכן האלגוריתם מדמה צופן זרם בכך שהוא מקבל קלט בכל אורך רצוי ולכן אין צורך במצב הפעלה של צופן בלוקים.

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

long TEAB(long* v, long n, long* k)
{
   ulong z, sum = 0, e, DELTA = 0x9e3779b9;
   long m, p, q;
   if(n > 1){ /* Coding Part */
      z = v[n-1];
      q = 6 + 52 / n;
      while (q-- > 0){
         sum += DELTA;
         e = sum >> 2 & 3;
         for (p = 0; p < n; p++)
            z = v[p] += (z << 4 ^ z >> 5) + z ^ k[p & 3 ^ e] + sum;
      } 
      return 0;
   } else if (n<-1) { /* Decoding Part */
      n = -n;
      q = 6 + 52 / n;
      sum = q * DELTA;
      while (sum != 0) {
         e = sum >> 2 & 3;
         for (p = n-1; p > 0; p--) {
            z = v[p-1];
            v[p] -= (z << 4 ^ z >> 5) + z ^ k[p & 3 ^ e] + sum;
         }
         z = v[n-1];
         v[0] -= (z << 4 ^ z >> 5) + z ^ k[p & 3 ^ e] + sum 
         sum -= DELTA;
      }
      return 0;
   }
   return 1;
} /* Signal n=0 */

בטחון

בטחון הצפנים Block TEA ו-XTEA חלש אפילו מ-TEA. זמן קצר לאחר הצגתם גילה Markku-Juhani Saarinen קריפטואנליזה לפי מודל התקפת מוצפן-נבחר נגד Block TEA שיכולה לנחש את מפתח ההצפנה בסיבוכיות של $2^{34}$ שאילתות. זוהי סוג של קריפטואנליזה דיפרנציאלית שמתמקדת בפונקציית הערבוב הפנימית בגלל שהיא אינה פונקציה על וקיימת אסימטריה בהתפתחות הדיפרנציאלית בין ההצפנה לפענוח. בנוסף כמו באלגוריתמים הקודמים, קיימת קריפטואנליזה של קלסי ושנייר שמעידה על בעיות בהכנת המפתח וחולשות נוספות. מסיבה זו הצופן אינו ראוי לשימוש כתחליף לאלגוריתם ברמה של AES אך ייתכן שיהיה שימושי בתנאים מסוימים. הוא אטרקטיבי בשל היותו פשוט מאד.

XXTEA

צופן XXTEA הוא גרסה מתוקנת של Block TEA לאחר שהמפתחים הודו כי הקריפטואנליזה שלו אכן ריאלית ומצריכה שינוי. בצופן XXTEA בוצעו מספר שינויים, תחילה ראוי לציין שההצפנה בגרסת Block TEA שונה מהפענוח מהיבט של "התפתחות דיפרנציאלית", בתהליך הפענוח ההתפתחות היא בשיעור של מילה אחת לסבב מה שמאפשר התקפת הבחנה מסוג "מוצפן-נבחר" דבר שתוקן בגרסה החדשה. כמו כן המפתחים שינו את הערכי ההזזות כדי שיעילות האלגוריתם לא תפגע אם $n=2$ וכן סדר הפעולות בפונקציה הפנימית השתנה מעט להגברת אי-הליניאריות. באופן כללי פונקציית הערבוב השתנתה ל-$v_{m}=v_{m}+F(v_{m-1},v_{m+1},{\text{key}})$ כאשר $m$ גדל או פוחת מודולו $n$. לדעת המפתחים נראה שהשינויים פתרו את הבעיות שהועלו אך לא בטוח שהם לא יצרו בעיות חדשות.

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

להלן תיאור קוד האלגוריתם לצורך ייחוס במימוש לא ממוטב בשפת C:

#define MX (z >> 5 ^ y << 2) + (y >> 3 ^ z << 4) ^ (sum ^ y) + (k[p & 3 ^ e] ^ z);

long XXTEA(long* v, long n, long* k)
{
   ulong z, y, sum = 0, e, DELTA = 0x9e3779b9;
   long m, p, q;
   if(n > 1){ /* Coding Part */
      z = v[n-1];
      q = 6 + 52 / n;
      while(q-- > 0){
         sum += DELTA;
         e = sum >> 2 & 3;
         for (p = 0; p < n-1; p++)
            y = v[p+1], z = v[p] += MX
         y = v[0];
         z = v[n-1] += MX
      }
      return 0;
   } else if (n <-1) {  /* Decoding Part */
      n = -n;
      q = 6 + 52 / n;
      sum = q * DELTA;
      while(sum != 0) {
         e = sum >> 2 & 3;
         for (p = n-1; p > 0; p--)
            z = v[p-1], y = v[p] -= MX
         z = v[n-1] ;
         y = v[0] -= MX
         sum -= DELTA ; 
      }
      return 0;
   }
   return 1;
} /* Signal n=0,1,-1 */

בטחון

בטחון אלגוריתם XXTEA אינו שפיר בהרבה מקודמיו. למרות השיפורים ההתקפות המתוארות לעיל חלקן עדיין ישימות אם כי בסיבוכיות גבוהה יותר. בכל מקרה סיבוכיות ההתקפות הללו במסגרת מודל התקפת גלוי-נבחר או התקפת מוצפן-נבחר נמוכה מ-$2^{128}$ כפי שצפוי במקרה של כוח גס בניחוש מפתח באורך 128 סיביות ולכן האלגוריתם אינו מוגדר בטוח במסגרת מודלים אילו ברמה גבוהה. ב-2010 גילה Elias Yarrkov התקפת גלוי-נבחר נגד הצופן שמסוגלת לנחש את מפתח ההצפנה בסיבוכיות זמן של $2^{59}$. כאשר בלוק הקלט מכיל לפחות 53 מילים מספר פעולות הערבוב לבלוק מצטמצם ל-6 בקירוב. עובדה זו פותחת פתח לקריפטואנליזה דיפרנציאלית. נראה שהבעיות בצופן הן אינהרנטיות ולכן שינויים מינוריים כפי שהוצע עד כה לא יספיקו כדי לפתור אותן. הסיבות הן הפשטות הרבה מדי של הצופן והעדר תהליך הכנה ראוי של מפתח ההצפנה.

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

וקטור בדיקה

להלן וקטור הבדיקה של הגרסאות השונות של TEA עם בלוק קלט באורך 64 סיביות וערכים אקראיים:

TEA(70666f71756a6e62636a67627366626d, 756972636c677270) = 436358c7d1e15fcb
XTEA(2F2F2F2F2F2F2F2F2F2F2F2F2F2F2F2F, 2F2F2F2F2F2F2F2F) = 0e28c8467f07bbff
XXTEA(0102040810204080fffefcf8f0e0c080, 0000000000000000) = d1e78be2c746728a

ראו גם

• צופן בלוקים
• AES
• IDEA

הערות שוליים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

22523721TEA (צופן)