LEA (צופן)

LEA

תרשים הפונקציה הפנימית של צופן LEA
מידע כללי
תכנון	Deukjo Hong, Jung-Keun Lee, Dong-Chan Kim, Daesung Kwon, Kwon Ho Ryu, ו-Dong-Geon Lee
פרסום	2013
מבנה הצופן
אורך מפתח	128/192/256 סיביות
אורך בלוק	128 סיביות
מבנה	ARX
מספר סבבים	24/28/32 סבבים בהתאמה

LEA (ראשי תיבות של: Lightweight Encryption Algorithm) הוא צופן בלוקים קל משקל במבנה ARX הממוטב למעבדי 32 ו-64 ביט ונועד לפטלפורמות מחשוב זעירות^[1]. הצופן פועל על בלוק באורך 128 סיביות, מקבל מפתח הצפנה באורך 128, 192 או 256 סיביות ומחזיר בלוק מוצפן באורך 128 סיביות. קוד האלגוריתם זעיר, הוא מהיר מ-AES ומציג ביצועים טובים בתוכנה על מעבדים נפוצים כמו אינטל ו-AMD. בחומרה הוא מגיע לתפוקה טובה ביחס לאלגוריתמים מתחרים^[2]. לדעת המפתחים הצופן בטוח נגד כל ההתקפות הידועות נגד צופן בלוקים. ב-2013 הוכנס LEA לתקן הצפנה עבור IoT על ידי TTA (דרום קוראה) החבר ב-3GPP.

LEA פותח ב-2013 על ידי Deukjo Hong, Jung-Keun Lee, Dong-Chan Kim, Daesung Kwon, Kwon Ho Ryu, ו-Dong-Geon Lee, הוא חופשי לשימוש ואינו מוגן בפטנט. מטרת הפיתוח שלו היא להגן על פרטיות המידע במחשבים וטלפונים ניידים, שהשימוש בהם נעשה תכוף יותר ויותר ומשמשים בין היתר לתקשורת ברשתות החברתיות ומחשוב ענן. שימוש נוסף הוא בהגנה על תקשורת של סנסורים אלחוטיים, התקני תיוג זעירים ומדים חכמים כמו מונה חשמל הפועל מרחוק. מכשירים אלו מצוידים בדרך כלל במעבד קטן, רכיב תקשורת ולרוב פועלים על סוללה. הם מסוגלים לבצע חישובים בתוכנה ברמה מוגבלת ועם מעט זיכרון. לדעת המפתחים המעבר למעבדים חזקים יותר, 32 או 64 ביט בלתי נמנע כך שהצורך באלגוריתמים קלי משקל המותאמים למעבדים אלו רק ילך ויגדל.

צופן בלוקים הוא פרימיטיב קריפטוגרפי מהחשובים ביותר. הוא משמש כמרכיב עיקרי בהצפנה סימטרית, אימות מסרים, מחולל אקראי ופונקציית גיבוב. צופן הבלוקים התקני והנפוץ בעולם כיום AES, משיג ביצועים טובים הן בתוכנה והן בחומרה ונחשב בטוח אחרי ששרד חמש עשרה שנות קריפטואנליזה מעמיקה. אך מאז המצאתו ההתקדמות הטכנולוגית הולידה צורך חדש ותקנים בינלאומיים הוסיפו קטגוריה הנקראת צופן קל משקל כמו תקן איזו ISO/IEC 29192-2 כשהמטרה שלהם היא יישום יעיל בחומרה עם צריכת אנרגיה נמוכה ביותר.

הצופן LEA עונה על ההגדרה בכמה היבטים:

• הוא מכיל רק שלוש פעולות אריתמטיות בסיסיות: חיבור מודולרי, הזזה מעגלית ו-XOR שהן פעולות הנתמכות בכל המעבדים והן בדרך כלל מהירות, במיוחד על מעבדי 32 ו-64 סיביות.
• מבנה ARX הוא מבנה קריפטוגרפי בטוח שנחקר רבות ונמצא בשימוש צפנים רבים כמו Salsa20. אין בו תיבות החלפה והוא המאפשר הפעלה מקבילית.
• בניגוד ל-AES כל סבבי צופן LEA זהים.
• הכנת המפתח פשוטה ויעילה.

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

הצופן אמור להיות מהיר ויעיל במימוש בתוכנה על פלטפורמות רבות עם תקורה נמוכה במיוחד המועילה בחסכון באנרגיה. במדידות שעשו המפתחים LEA מהיר יותר מ-AES וניתן ליישום באופן מקבילי תוך שימוש בפקודות SIMD ועם קוד מקור מינימלי שהוא אטרקטיבי במיוחד בסביבה מוגבלת זיכרון. LEA ייושם בתוכנה עם פחות מ-750 בתים (בעוד ש-AES לפי הפרסומים צורך 2400 בתים לפחות). צופן LEA נמצא יעיל בהשוואה לצפנים קלי משקל אחרים כמו TEA ,HEIGHT ,RC5, הצפנים SPECK ו-SIMON שפותחו על ידי NSA וכן PRESENT ו-CLEFIA שתוקננו על ידי ISO.

LEA הוא צופן בלוקים סימטרי איטרטיבי עם בלוק באורך 128 סיביות. המפתח הסודי יכול להגיע בשלושה אורכים אפשריים: 128, 192 או 256 סיביות. הפונקציה הפנימית של הצופן מבוצעת במספר הסבבים משתנה בהתאם לאורך המפתח: עבור מפתח 128 סיביות 24 סבבים, עבור מפתח 192 סיביות 28 סבבים ועבור מפתח 256 סיביות 32 סבבים. בתיאור האלגוריתם לא הובאה פונקציית פענוח, בגלל שהיא פשוט הפעולה ההופכית של ההצפנה.

כל הפעולות בצופן הן ברמת מילים באורך 32 סיביות. קלט האלגוריתם הוא המסר ${\displaystyle P}$ המחולק לארבע מילים: ${\displaystyle P[0],P[1],P[2],P[3]}$ באופן דומה מוצג פלט האלגוריתם ${\displaystyle C}$. הזיכרון הפנימי של האלגוריתם מכיל גם הוא ארבע מילים: ${\displaystyle X_{i}=X_{i}[0],X_{i}[1],X_{i}[2],X_{i}[3]}$ כאשר ${\displaystyle i}$ מתייחס למספר הסבב. באותה הדרך, המפתח ${\displaystyle K}$ מחולק ל-4, 6 או 8 מילים בהתאם לאורכו: ${\displaystyle K=K[0],K[1],...,K[\ell -1]}$ כאשר ${\displaystyle \ell }$ הוא אורך המפתח במילים (במפתח 256 מסיביות ${\displaystyle \ell =256/32=8}$).

התרשים משמאל מתאר את פונקציית ההצפנה של LEA.

ההמרה ממחרוזת בתים למילים וההפך היא לפי סדר בתים קטן (הערך הימני ביותר הוא ההערך הכי פחות משמעותי, במילים אחרות אם מתייחסים לבתים כאל ספרות בטווח 0-255 אז הבית בכתובת אפס מכיל את הספרה הכי פחות משמעותית). למשל נתון הקלט ${\displaystyle a}$ שמתקבל כמערך של 16 בתים: ${\displaystyle a[0],a[1],...,a[16]}$, הבית ${\displaystyle a[i]}$ מכיל את הסיביות ${\displaystyle \{b_{8i},b_{8i+1},...,b_{8i+7}\}}$. כל מילה ${\displaystyle P[i]}$ מקודדת לפי:

${\displaystyle P[i]=a[4\cdot i+3]\ \|\ a[4\cdot i+2]\ \|\ a[4\cdot i+1]\ \|\ a[4\cdot i]}$ עבור ${\displaystyle 0\leq i\leq 3}$.

הטבלה הבאה מסכמת את קידוד הקלט, הפלט והמפתח בצופן LEA:

24	${\displaystyle \cdots }$	31	16	${\displaystyle \cdots }$	23	8	${\displaystyle \cdots }$	15	0	${\displaystyle \cdots }$	7	קלט בסיביות
0												מספר מילה
3			2			1			0			מספר בית
31	${\displaystyle \cdots }$										0	מספר הסיבית במילה

הפרוצדורה להכנת המפתח מייצרת ממפתח המאסטר המסופק על ידי המשתמש רצף של תת-מפתחות ${\displaystyle RK_{i}}$ כדלהלן:

תחילה מגדירים את הקבועים הבאים בבסיס הקסדצימלי:

${\displaystyle \delta [0]={\text{0xc3efe9db}}}$	${\displaystyle \delta [1]={\text{0x44626b02}}}$
${\displaystyle \delta [2]={\text{0x79e27c8a}}}$	${\displaystyle \delta [3]={\text{0x78df30ec}}}$
${\displaystyle \delta [4]={\text{0x715ea49e}}}$	${\displaystyle \delta [5]={\text{0xc785da0a}}}$
${\displaystyle \delta [6]={\text{0xe04ef22a}}}$	${\displaystyle \delta [7]={\text{0xe5c40957}}}$

ערכים אלו הם תוצאה של חישוב השורש הריבועי של המספר 766965 כאשר הספרות 76, 69 ו-65 הן קידוד אסקי של השם LEA. (זהו מנהג מקובל בצופן בלוקים כדי להראות שבחירתם אינה נובעת מהרצון להחדיר דלת סתרים).

אם המשתמש בחר במפתח 128 סיביות, תחילה מכינים שני מערכים זמניים: המערך ${\displaystyle T}$ המכיל 4 מילים לתוכו טוענים את מילות המפתח של המשתמש לפי הסדר (${\displaystyle T[0]=K[0],T[1]=K[1],...}$) והמערך ${\displaystyle RK_{i}}$ המכיל 6 מילים בו מאחסנים את תת-המפתחות עבור כל הסבבים כאשר ${\displaystyle i}$ מתייחס למספר הסבב. להכנת תת-המפתחות מחשבים את:

${\displaystyle T[0]\leftarrow {\text{ROL}}_{1}(T[0]\boxplus {\text{ROL}}_{i}(\delta [i{\text{ mod }}4]))}$, ${\displaystyle T[1]\leftarrow {\text{ROL}}_{3}(T[1]\boxplus {\text{ROL}}_{i+1}(\delta [i{\text{ mod }}4]))}$, ${\displaystyle T[2]\leftarrow {\text{ROL}}_{6}(T[2]\boxplus {\text{ROL}}_{i+2}(\delta [i{\text{ mod }}4]))}$, ${\displaystyle T[3]\leftarrow {\text{ROL}}_{11}(T[3]\boxplus {\text{ROL}}_{i+3}(\delta [i{\text{ mod }}4]))}$, ${\displaystyle RK_{i}\leftarrow (T[0],T[1],T[2],T[1],T[3],T[1])}$ עבור ${\displaystyle 0\leq i<24}$.

הסימן ${\displaystyle \boxplus }$ מייצג כאן חיבור מודולו ${\displaystyle 2^{32}}$. הסימן ${\displaystyle {\text{ROL}}_{i}}$ מייצג הזזה מעגלית ברמת סיביות בגבולות מילה באורך 32 סיביות ${\displaystyle i}$ פוזיציות.

עבור מפתח באורך 192 סיביות טוענים ב-${\displaystyle T}$ את ששת המילים של המפתח שסופק על ידי המשתמש ו-${\displaystyle RK}$ מכיל בסך הכול 28 סטים אפשריים כך:

${\displaystyle T[0]\leftarrow {\text{ROL}}_{1}(T[0]\boxplus {\text{ROL}}_{i}(\delta [i{\text{ mod }}6]))}$, ${\displaystyle T[1]\leftarrow {\text{ROL}}_{3}(T[1]\boxplus {\text{ROL}}_{i+1}(\delta [i{\text{ mod }}6]))}$, ${\displaystyle T[2]\leftarrow {\text{ROL}}_{6}(T[2]\boxplus {\text{ROL}}_{i+2}(\delta [i{\text{ mod }}6]))}$, ${\displaystyle T[3]\leftarrow {\text{ROL}}_{11}(T[3]\boxplus {\text{ROL}}_{i+3}(\delta [i{\text{ mod }}6]))}$, ${\displaystyle T[4]\leftarrow {\text{ROL}}_{13}(T[4]\boxplus {\text{ROL}}_{i+4}(\delta [i{\text{ mod }}6]))}$, ${\displaystyle T[5]\leftarrow {\text{ROL}}_{17}(T[5]\boxplus {\text{ROL}}_{i+5}(\delta [i{\text{ mod }}6]))}$, ${\displaystyle RK_{i}\leftarrow (T[0],T[1],T[2],T[3],T[4],T[5])}$ עבור ${\displaystyle 0\leq i<28}$.

הכנת המפתח במקרה של 256 סיביות מתבצעת בסגנון דומה. שמונה מילות המפתח נטענות ב-${\displaystyle T}$ ו-${\displaystyle RK}$ מכיל 8 מילים כפול 32 סבבים כדלקמן:

${\displaystyle T[6i{\text{ mod }}8]\leftarrow {\text{ROL}}_{1}(T[6i{\text{ mod }}8]\boxplus {\text{ROL}}_{i}(\delta [i{\text{ mod }}8]))}$, ${\displaystyle T[6i+1{\text{ mod }}8]\leftarrow {\text{ROL}}_{3}(T[6i+1{\text{ mod }}8]\boxplus {\text{ROL}}_{i+1}(\delta [i{\text{ mod }}8]))}$, ${\displaystyle T[6i+2{\text{ mod }}8]\leftarrow {\text{ROL}}_{6}(T[6i+2{\text{ mod }}8]\boxplus {\text{ROL}}_{i+2}(\delta [i{\text{ mod }}8]))}$, ${\displaystyle T[6i+3{\text{ mod }}8]\leftarrow {\text{ROL}}_{11}(T[6i+3{\text{ mod }}8]\boxplus {\text{ROL}}_{i+3}(\delta [i{\text{ mod }}8]))}$, ${\displaystyle T[6i+4{\text{ mod }}8]\leftarrow {\text{ROL}}_{13}(T[6i+4{\text{ mod }}8]\boxplus {\text{ROL}}_{i+4}(\delta [i{\text{ mod }}8]))}$, ${\displaystyle T[6i+5{\text{ mod }}8]\leftarrow {\text{ROL}}_{17}(T[6i+5{\text{ mod }}8]\boxplus {\text{ROL}}_{i+5}(\delta [i{\text{ mod }}8]))}$, ${\displaystyle RK_{i}\leftarrow (T[6i{\text{ mod }}8],T[6i+1{\text{ mod }}8],T[6i+2{\text{ mod }}8],T[6i+3{\text{ mod }}8],T[6i+4{\text{ mod }}8],T[6i+5{\text{ mod }}8])}$. עבור ${\displaystyle 0\leq i<32}$.

פונקציית ההצפנה מקבלת את בלוק ${\displaystyle P=(P[0],P[1],P[2],P[3])}$ ואת תת-המפתחות עבור כל הסבבים בהתאם לגודל המפתח ומחזירה את הבלוק המוצפן ${\displaystyle C=(C[0],C[1],C[2],C[3])}$.

תחילה מעתיקים את בלוק הקלט למערך מקומי ${\displaystyle X_{0}[0],X_{0}[1],X_{0}[2],X_{0}[3]}$ כאשר אפס מייצג את מצב הזיכרון הפנימי של האלגוריתם לפי תחילת ההצפנה. מכינים ${\displaystyle r}$ תת-המפתחות לפי התיאור לעיל. ומבצעים ${\displaystyle r}$ פעמים כדלקמן:

${\displaystyle X_{i+1}[0]\leftarrow {\text{ROL}}_{9}((X_{i}[0]\oplus RK_{i}[0])\boxplus (X_{i}[1]\oplus RK_{i}[1]))}$, ${\displaystyle X_{i+1}[1]\leftarrow {\text{ROR}}_{5}((X_{i}[1]\oplus RK_{i}[2])\boxplus (X_{i}[2]\oplus RK_{i}[3]))}$, ${\displaystyle X_{i+1}[2]\leftarrow {\text{ROR}}_{3}((X_{i}[2]\oplus RK_{i}[4])\boxplus (X_{i}[3]\oplus RK_{i}[5]))}$, ${\displaystyle X_{i+1}[3]\leftarrow X_{i}[0]}$.

${\displaystyle \oplus }$ הוא XOR, הסמל ${\displaystyle \boxplus }$ מייצג כאן חיבור מודולו ${\displaystyle 2^{32}}$, הסמל ${\displaystyle {\text{ROR}}}$ הוא הזזה מעגלית לימין בגבולות מילה באורך 32 סיביות במספר פוזיציות המצוין אחריו. תוצאת ההצפנה היא המצב הפנימי ${\displaystyle X_{r}[0],X_{r}[1],X_{r}[2],X_{r}[3]}$ לאחר ${\displaystyle r}$ הסבבים:

${\displaystyle C=(C[0]=X_{r}[0],C[1]=X_{r}[1],C[2]=X_{r}[2],C[3]=X_{r}[3])}$

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

ערך מורחב – התקפת ערוץ צדדי

צפני בלוקים בדרך כלל רגישים לסוגים שונים של התקפת ערוץ צדדי ולכן במקרים שהצופן עלול להיות חשוף להתקפת ערוץ צדדי מיישמים אותו בשינויים אחדים לעיתים אף מרחיקי לכת מההצעה המקורית. למשל טבלאות האחזור של AES עלולות להדליף מידע בהתקפת ערוץ צדדי המודדת את גרף צריכת האנרגיה של הצופן בעת פעולתו, לכן ממליצים לא להשתמש בטבלאות החלפה אלא לחשב אותן בזמן ריצה. באופן כללי ביישום בפועל מנצלים טכניקות כמו bitslice ומיסוך (masking) על מנת למנוע דליפת מידע כתוצאה מאופן פעולת האלגוריתם. החסרון הוא שהאלגוריתם במקרה זה אינו מציג ביצועים זהים לזה שהוצהרו על ידי המפתחים, ברוב המקרים ההרעה בביצועים משמעותית. במקרה של LEA הרעה גדולה בקצב ההצפנה אינה מקובלת כי עיקר יתרונו הוא במהירות, לכן קיימת הצעה^[3] ליישום LEA בשיטת מיסוך שאינה פוגעת בתפוקתו באופן משמעותי. הרעיון הוא לפרמט את הקלט במקום למסך את הפעולות האריתמטיות. השינוי פועל כך שבמקום לעבד 16 בתי מידע בכל פעם, מעבדים רק 12 בתים, ובארבעה הנותרים מכניסים מידע דמי שתפקידו למסך את דפוס גל צריכת האנרגיה של הצופן.

כאמור צופן LEA הוא צופן חדש יחסית וקיימת מעט קריפטואנליזה שלו (לא כולל המחקר שעשו המפתחים). להלן שני מחקרים שמעידים שהצופן בטוח. קריפטואנליזה ליניארית חדשה הנקראת התקפת מתאם אפס^[4] וקריפטואנליזה דיפרנציאלית חדשה הנקראת "Automatic Differential Analysis"^[5].

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