EAX

בקריפטוגרפיה, EAX הוא מצב הפעלה של צופן בלוקים עם הצפנה מאומתת, שפותח ב-2004 על ידי מיהיר בלייר, פיליפ רוגווי ודייוויד וגנר אוניברסיטת קליפורניה בברקלי והוצע כאלטרנטיבה ל-CCM לצורך תקן הצפנה מאומתת. האלגוריתם שייך לקטגוריה AEAD - הצפנה מאומתת עם מידע נלווה ופועל בשתי ריצות. בהינתן מסר $M$, וקטור אתחול $N$ שנקרא גם Nonce וכותר $H$ באורך שרירותי כלשהו, האלגוריתם מצפין תחילה את $M$ תוך שימוש בצופן בלוקים בטוח לפי העדפת המשתמש ומייצר טקסט מוצפן $C$ ולאחר מכן מייצר תג אימות $T$ להבטחת שלמות $C$ והמידע הנלווה $H$, תוך ביצוע $2\left\lceil |M|/n\right\rceil +\left\lceil |H|/n\right\rceil +\left\lceil |N|/n\right\rceil$ ריצות של צופן הבלוקים כאשר $n$ הוא אורך הבלוק בסיביות (128 סיביות במקרה של AES).‏ EAX הוא און ליין, אפשר להתחיל הצפנה או פענוח לפני שמתקבל כל המסר ואורכו לא חייב להיות ידוע מראש וכן ניתן לחשב חלקים קבועים מראש כדי להפחית את כמות העבודה פר מסר. EAX מוכח כבטוח תחת הנחות סטנדרטיות ויעיל ופשוט יותר מ-CCM וכן כמו המתחרה, למיטב ידיעת המפתחים נקי מזכויות יוצרים וחופשי לשימוש לכל מטרה.

הצפנה מאומתת

ערך מורחב – הצפנה מאומתת

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

קיימות מספר סכמות תיקניות להצפנה מאומתת ביניהן כאלו שנקראות 'גנריות' המשלבות הצפנה עם אימות בשני שלבים נפרדים ובלתי חופפים, כך שאפשר להחליף אלגוריתם הצפנה או אימות לפי הצורך, וכאלו שמשלבים הצפנה עם אימות יחד. וכן כאלו שפועלים בריצה אחת או בשתי ריצות. בשל פטנטים וזכויות יוצרים שמקשים על תיקנון אלגוריתמים יעילים כמו OCB, פותחו CCM ו-EAX שאמנם פחות יעילים אך חופשיים לשימוש. לעיתים עולה הצורך באימות ללא סודיות של חלק מהמידע. לדוגמה קובץ כותר המכיל הוראות והגדרות כמו כתובות שאמור להיות גלוי לעיני השרת המקבל, לכן התפתחה קטגוריה של מצבי הפעלה שנקראת AEAD שמנסה לענות על צורך זה.

סימנים מוסכמים

תרשים לדוגמה של הצפנה מאומתת בשיטת EAX

בבסיס האלגוריתם קיים צופן בלוקים שההנחה היא שהוא תמורה פסאודו-אקראית (PRP), למשל ההנחה היא ש-AES מתאים להגדרה זו. סימונו הכללי הוא $E:K\times \{0,1\}^{n}\rightarrow \{0,1\}^{n}$ כאשר $n$ הוא גודל הבלוק בסיביות. בסימון מקוצר $C=E_{K}(M)$ - פירושו $C$ הוא התוצאה של הפעלת האלגוריתם $E$ עם המפתח $K$ על המסר $M$. הביטוי $0^{n}$ פירושו הסיבית אפס כשהיא משוכפלת $n$ פעמים (לדוגמה $0^{5}=00000$). הביטוי $L\ll 1$ פירושו הזזה לשמאל של כל סיביות האופרנד $L$ פוזיציה אחת, כאשר הסיבית הפחות משמעותית תהיה אפס והסיבית המשמעותית ביותר נפלטת. הסימון $|M|$ פירושו אורכה של המחרוזת $M$ בסיביות. האופרטור XOR מסומן בקיצור $\oplus$ והסימון "${\stackrel {}{\oplus }}{\rightarrow }$" פירושו כאשר המחרוזות אינן באותו אורך, המחרוזת הקצרה יותר מיושרת לסוף המחרוזת הארוכה ואז מבוצע XOR. בנוסף האלגוריתם עושה שימוש בכמה פרימיטיבים ידועים; CBC, CTR, OMAC*‎ ו-pad. לפירוט האלגוריתמים תחילה CBC (קיצור של CBC MAC) הוא קוד אימות מסרים בסיסי ופשוט המשתמש במצב ההעפלה Cipher block chaining. האלגוריתם CTR הוא סגנון הפעלה במצב מונה של צופן בלוקים. pad משמש כשיטת עזר לריפוד המסר עבור OMAC*‎. האחרון הוא קיצור של One key MAC שהוא פונקציה פסאודו-אקראית (PRF), פרי פיתוח של בלאק ורוגווי בשנת 2000 כחלק מקוד אימות מסרים XCBC. הכוכבית מסמנת שגרסה זו שונה מהמקורית בכך שהיא מקבלת פרמטר נוסף $t$ הנקרא "tweak" שהוא סוג של וקטור אתחול או Nonce. זהו בעצם אלגוריתם OMAC הרגיל שבו מחרוזת הקלט משורשרת עם מחרוזת נוספת המייצגת את וקטור האתחול ואז מחשבים את תג האימות על המחרוזת החדשה.

הכוונה בביטוי $2L$ באלגוריתם OMAC להלן היא שמתייחסים למחרוזת הסיביות $L$ כאל פולינום מעל השדה $GF(2^{n})$ תוך שימוש בפולינום 'קנוני' המייצג את השדה. זהו פולינום פרימיטיבי אי-פריק בעל משקל בינארי נמוך, למשל במקרה של בלוקים בגודל 128 סיביות ההמלצה היא $x^{128}+x^{7}+x^{2}+x+1$. אפשר לראות באלמנטים של שדה בינארי מורחב $GF(2^{n})$ כפולינומים עם מקדמים בינאריים ממעלה הנמוכה מ-$n$ ואז פעולת החיבור בשדה היא חיבור המקדמים מודולו 2 שמקבילה בעצם לאופרטור XOR וכפל ב-2 הוא בעצם הזזה (Shift) של כל המקדמים (סיביות) של הפולינום שמאלה פוזיציה אחת. במקרה של כפל ב-2 אם הסיבית המשמעותית היא 1 התוצאה תהיה פולינום ממעלה הגבוהה או שווה ל-128 תוצאה שחורגת מהשדה לכן יש צורך לצמצם את המספר, כלומר לחלק אותו בפולינום האי-פריק ולקחת את השארית (ראו חשבון מודולרי). כל מה שנדרש הוא פעולת חיסור אחת שבשדה זה זהה לחיבור כי XOR הופכי של עצמו לכן הפעולה מסתכמת ב-$2L=(L\ll 1)\oplus 0^{120}10000111$ במקרה שהסיבית המשמעותית היא 1, או פשוט $L\ll 1$ במקרה שהסיבית המשמעותית היא אפס. בדרך זו, אפשר לחשב את $4L=2(2L)$. כדי למנוע התקפת תזמון צריך לשים לב שפעולת הכפל תתבצע בזמן קבוע (בין אם הסיבית המשמעותית היא 1 או 0).

להלן פירוט האלגוריתמים הבסיסיים ש-EAX משתמש בהם:

${\textbf {CBC}}_{\textit {\textbf {K}}}({\textit {\textbf {M}}})$

$M=M_{1},M_{2},...,M_{m},{\text{ where }}|M_{i}|=n$

$C=0^{n}$

${\text{For }}i=1{\text{ to }}m{\text{ do: }}C=E_{K}(M_{i}\oplus C)$

${\text{Return }}C$

${\textbf {CTR}}_{{\textit {\textbf {K}}},{\textit {\textbf {N}}}}({\textit {\textbf {M}}})$

$m=\left\lceil |M|/n\right\rceil$

$S=E_{K}(N)\ \|\ E_{K}(N+1)\ \|\ \cdots \ \|\ E_{K}(N+m-1)$

${\text{Return }}M\oplus S[{\text{first }}|M|{\text{ bits}}]$

${\textbf {pad}}({\textit {\textbf {M}}},{\textit {\textbf {B}}},{\textit {\textbf {P}}})$

${\text{If }}|M|\in \{n,2n,3n,...\}{\text{ then return }}M\ {\stackrel {}{\oplus }}{\rightarrow }\ B$

${\text{else return }}\left(M\ \|\ 10^{n-1-(|M|{\text{ mod }}n)}\right)\ {\stackrel {}{\oplus }}{\rightarrow }\ P$

הסבר: אם אורך המסר מתחלק ללא שארית בגודל הבלוק, אזי מבצעים XOR עם הפרמטר $B$ כשהוא מיושר לסוף $M$ ומחזירים את התוצאה. אחרת מרפדים את הבלוק האחרון בסיבית '1' ובאפסים כמידת הצורך כדי להשלימו לגודל בלוק שלם ומחזירים את התוצאה לאחר XOR עם הפרמטר $P$ כשהוא מיושר לסוף $M$.

${\textbf {OMAC}}_{\textit {\textbf {K}}}^{t}({\textit {\textbf {M}}})$

$L=E_{K}(0^{n})$

${\text{Return }}{\text{CBC}}_{K}({\text{pad}}([t]_{n}\ \|\ M,2L,4L))$

הסבר: תחילה משרשרים את $n$ הסיביות הראשונות של $t$ למסר $M$, מחשבים את שני הפרמטרים $(P,B)$ לצורך הריפוד ומחזירים את תג האימות שהוא תוצאה של CBC של המסר לאחר הריפוד.

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

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

קלט: אורך התג הרצוי $\tau$, מפתח $K$, מסר $M$, כותר $H$, וקטור אתחול $N$.

פלט: טקסט מוצפן $C$ ותג אימות $T$.

${\textbf {EAX-ENCRYPT}}_{{\textit {\textbf {K}}},{\textit {\textbf {N}}},{\textit {\textbf {H}}}}({\textit {\textbf {M}}},\tau )$

${\mathcal {N}}={\text{OMAC}}_{K}^{0}(N)$

${\mathcal {H}}={\text{OMAC}}_{K}^{1}(H)$

$C={\text{CTR}}_{K,N}(M)$

${\mathcal {C}}={\text{OMAC}}_{K}^{2}(C)$

${\text{Tag}}={\mathcal {N}}\oplus {\mathcal {C}}\oplus {\mathcal {H}}$

$T={\text{Tag}}[{\text{first }}\tau {\text{ bits}}]$

${\text{Return }}C\ \|\ T$

הסבר: תחילה מייצרים תג אימות עבור קובץ הכותר $H$ וכן עבור וקטור האתחול $N$ באמצעות OMAC. לאחר מכן מצפינים את המסר במצב מונה ומייצרים תג אימות מהטקסט המוצפן $C$. מחברים ב-XOR את שלושת התגים שנוצרו ולוקחים חלק מהתוצאה האחרונה כתג אימות $T$ שנשלח יחד עם $C$.

אלגוריתם פענוח עם אימות

קלט: אורך התג הרצוי $\tau$, מפתח $K$, טקסט מוצפן $C$, כותר $H$, וקטור אתחול $N$, תג אימות $T$.

פלט: מסר מקורי $M$ או סמל מיוחד INVALID שפירושו שהאלגוריתם נכשל בפענוח, עקב שינוי באחד הערכים.

${\textbf {EAX-DECRYPT}}_{{\textit {\textbf {K}}},{\textit {\textbf {N}}},{\textit {\textbf {H}}}}({\textit {\textbf {C}}}\ \|\ {\textit {\textbf {T}}},\tau )$

${\text{If }}|(C\ \|\ T)|<\tau {\text{ then return INVALID}}$

${\mathcal {N}}={\text{OMAC}}_{K}^{0}(N)$

${\mathcal {H}}={\text{OMAC}}_{K}^{1}(H)$

${\mathcal {C}}={\text{OMAC}}_{K}^{2}(C)$

${\text{Tag}}'={\mathcal {N}}\oplus {\mathcal {C}}\oplus {\mathcal {H}}$

${\text{If }}T\neq {\text{Tag}}'[{\text{first }}\tau {\text{ bits}}]{\text{ then return INVALID}}$

$M={\text{CTR}}_{K,N}(C)$

${\text{Return }}M$

תכונות

EAX הוא סכמת הצפנה מאומתת בשתי ריצות, בתור שכזה יעילותו נמוכה מאלגוריתמים הפועלים בריצה אחת. ל-EAX מספר יתרונות:

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

ראו גם

• CCM
• CWC