AES

תקן הצפנה מתקדם (באנגלית: Advanced Encryption Standard), או בקיצור AES, הוא צופן בלוקים סימטרי שאומץ על ידי המכון הלאומי לתקנים וטכנולוגיה (NIST) של ארצות הברית כתקן הצפנה רשמי שהתקבל בעולם כולו, להצפנת נתונים מאסיבית.

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

AES

מידע כללי
תכנון	וינסנט ריימן, יוהאן דאמן
פרסום	2000
מבוסס על	SHARK ו-SQUARE
גרסאות מתקדמות	Anubis
מבנה הצופן
אורך מפתח	128/192/256 סיביות
אורך בלוק	128 סיביות
מבנה	רשת החלפה-תמורה
מספר סבבים	10/12/14 בהתאמה
קריפטואנליזה
אף על פי שקיימות התקפות תאורטיות שהן טובות במקצת מכוח גס, נכון ל-2018 לא ידוע על אף התקפה יעילה נגד הצופן, למעט התקפה בסגנון מפתחות קשורים נגד AES-192 ו-AES-256 בסיבוכיות זמן של ${\displaystyle 2^{176}}$ וסיבוכיות מקום ${\displaystyle 2^{99.5}}$.

AES או בשמו המקורי ריינדל (Rijndael) פותח על ידי הקריפטוגרפים הבלגיים יוהאן דאמן ווינסנט ריימן כשכלול של שני צפנים ישנים יותר (SHARK ו-SQUARE), והוצע במהלך פרויקט בחירת התקן שאורגן על ידי NIST בשנת 2000. לאחר שזכה בתחרות אומץ על ידי ממשלת ארצות הברית באופן רשמי להצפנת נתונים מסווגים עבור הממשל והחליף בכך את קודמו DES שיצא לאור ב-1977. כיום אלגוריתם AES נמצא בשימוש מעשי נרחב בכל העולם הן בתוכנה והן בחומרה וידוע כאלגוריתם בטוח.

AES הוכרז^[1] כתקן הצפנה FIPS PUB 197 בנובמבר 2001 ואושר רשמית במאי 2002 על ידי מזכיר המסחר של ארצות הברית וכן נכלל בתקן איזו (ISO/IEC 18033-3). זהו הצופן הסימטרי הפומבי הראשון שקיבל את אישור הסוכנות לביטחון לאומי האמריקאי כראוי להצפנת נתונים המוגדרים ברמת סיווג SECRET וכן TOP SECRET עבור ממשלת ארצות הברית, אם נעשה בו שימוש כחלק ממודול הצפנה מאושר.

תהליך בחירת התקן

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

התחרות של NIST

תהליך קבלת ההחלטות ושיקולי הפיתוח של התקן הקודם (DES) היו רחוקים מעין הציבור, מה שהוביל לחרושת שמועות שהסוכנות לביטחון לאומי (NSA) התערבה בפיתוח DES כדי להחלישו במכוון. רבים אף הביעו חשש שהוחדרה בו דלת אחורית. בשל כך, לבחירת התקן החדש נקטה הוועדה בגישה יותר שקופה והוחלט על תחרות פתוחה לציבור. התחרות זכתה לשבחים רבים. תנאי ההשתתפות פורסמו בתחילת 1997 – בין היתר הדרישה שגודל הבלוק יהיה לפחות 128 סיביות וכן שמפתחות ההצפנה יהיו בטווח 128–256 סיביות. התחרות נמשכה כחמש שנים. בתחילה הוצעו כחמישה עשר מועמדים על ידי מפתחים מרחבי העולם, מתוכם כחמישה התגלו חלשים להתקפות מסוימות ונפסלו מיד. ההצעות נבחנו על ידי מומחים רבים לא רק מהיבט של בטיחות אלא גם יעילות וקלות יישום הן בחומרה והן בתוכנה.

באוגוסט 1998 התקיימה הוועידה הראשונה (AES1) שבה הוצגו כל המועמדים, ולאחר סינון שנמשך כשנה הוכרזו בוועידה AES2 שהתקיימה באוגוסט 1999 חמשת המועמדים המובילים שעלו לשלב הגמר. מועמדים אלה הוצעו על ידי גופים מוערכים בעלי ידע וניסיון קריפטוגרפי רב ונבדקו היטב. האלגוריתמים דורגו לפי ניקוד שניתן להם בקטגוריות השונות – ביטחון, יעילות, קלות יישום והטמעה בחומרה. בסבב השלישי והאחרון, בוועידת AES3 שהתקיימה בנובמבר 2000, הוכרז אלגוריתם ריינדל כמנצח של התחרות. ארבעת המועמדים האחרים שעלו לגמר בסדר יורד לפי דירוג הוועדה, הם:

• סרפנט
• Twofish
• RC6
• MARS

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

שיקולי פיתוח

הקריטריונים העיקריים שעמדו בפיתוח הצופן היו עמידות, פשטות, קומפקטיות ומהירות. בניגוד לצפני בלוקים אחרים, ריינדל אינו מיישם רשת פייסטל שבה מחצית מסיביות המצב הפנימי של הצופן מועברים מסבב אחד למשנהו ללא שינוי. במקום זאת, פונקציית הסבב היא רשת החלפה-תמורה (SP-network) המורכבת משלוש טרנספורמציות שונות, אחידות והפיכות הנקראות "שכבות". כאשר אחידות פירושה שכל סיביות מצבי הביניים מקבלות טיפול זהה. בחירת השכבות נעשתה לפי אסטרטגיית wide trail (עִקְבָה רחבה)^[2] שפותחה על ידי ריימן ודאמון בתהליך פיתוח הצופן כדי להתמודד עם קריפטואנליזה דיפרנציאלית וליניארית. הרעיון הוא בחירה מושכלת של תיבות ההחלפה (s-box) באופן שלא תהיה להם עקבה דיפרנציאלית או ליניארית בעלת משקל נמוך, משקל נמוך יכול לנבוע ממספר נמוך של פוזיציות פעילות בתיבות ההחלפה (פעילות נמדדת באמצעות קורלציה). שלוש השכבות הן:

• שכבה לא ליניארית: תיבות החלפה בעלות תכונת אי-ליניאריות גבוהה, להבטחת ערבוב (confusion) גבוה.
• שכבת ערבוב ליניארי: להבטחת פיזור (diffusion) גבוה.
• שכבת חיבור מפתח: חיבור XOR של מפתח הסבב עם תוצאת הביניים.

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

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

צרופי מפתח/בלוק/סבב אפשריים באלגוריתם AES

AES הוא גרסה של צופן ריינדל (השם הוא משחק שילוב שמות המשפחה של הממציאים), שהוא צופן מסוג רשת החלפה-תמורה. זהו צופן בלוקים איטרטיבי עם בלוק ומפתח משתנים בגודלם. ניתן להגדירם ללא תלות אחד בשני; 128, 192 או 256 סיביות. ב-AES, גודל הבלוק הוא תמיד 128 סיביות. כעת נתאר את אופן ההצפנה של בלוק יחיד.

ליבת הצופן מורכבת ממספר סבבים (rounds) שפועלים על מטריצה בגודל 4x4 (או 16 בתים) המהווה את מצב הביניים של הצופן ונקראת בקיצור המצב (state). מספר הסבבים תלוי באורך המפתח:

• 10 סבבים עבור מפתח בגודל 128 סיביות
• 12 סבבים עבור מפתח בגודל 192 סיביות
• 14 סבבים עבור מפתח בגודל 256 סיביות

המצב מאותחל להיות הקלט (כלומר הבלוק), והוא ניתן להצגה כמערך בתים דו־ממדי בעל ארבע שורות ומספר עמודות המסומן ${\displaystyle Nb}$ שהוא פונקציה של גודל הבלוק בסיביות חלקי 32 (ראה טבלה). באופן דומה מיוצגים בתי המפתח מארבע שורות ומספר עמודות המסומן ${\displaystyle Nk}$ – פונקציה של אורך המפתח בסיביות חלקי 32.

בחלק מהפעולות בצופן מתייחסים לבלוקים של צופן ומפתח כאל מערך של וקטורים בני ארבעה בתים כאשר כל ווקטור מייצג עמודה אחת. קלט ופלט הצופן מיוצגים כמערך חד-ממדי של בתים בגודל ${\displaystyle 4\cdot Nb}$ (דהיינו 16, 24 או 32 בתים בהתאם לגודל הבלוק – בתקן נקבע ל-16 בתים) שממופים למערך הדו־ממדי לפי סדר עמודות ראשי כמתואר בתרשים משמאל. 16 הבתים של הקלט ${\displaystyle a_{0},...,a_{15}}$ מסודרים במטריצה ${\displaystyle s}$ מלמעלה למטה החל מהעמודה השמאלית והאינדקס לכל כניסה הוא ${\displaystyle s_{{\text{row}},{\text{column}}}}$ למשל ${\displaystyle s_{1,2}}$ מתייחס לערך המצוי בשורה הראשונה בעמודה השנייה. באופן דומה מיוצג המפתח. הערך ${\displaystyle Nr}$ מציין את מספר הסבבים הדרוש והוא תלוי בערכים ${\displaystyle Nb,Nk}$ (ראה טבלה).

${\displaystyle s_{0}}$	${\displaystyle s_{4}}$	${\displaystyle s_{8}}$	${\displaystyle s_{12}}$
${\displaystyle s_{1}}$	${\displaystyle s_{5}}$	${\displaystyle s_{9}}$	${\displaystyle s_{13}}$
${\displaystyle s_{2}}$	${\displaystyle s_{6}}$	${\displaystyle s_{10}}$	${\displaystyle s_{14}}$
${\displaystyle s_{3}}$	${\displaystyle s_{7}}$	${\displaystyle s_{11}}$	${\displaystyle s_{15}}$

תיאור בלוק מצב הביניים State כמערך דו־ממדי בגודל 4x4 בתים

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

${\displaystyle {\mbox{Round(State, RoundKey)}}}$

1. ${\displaystyle {\mbox{SubBytes(State)}}}$
2. ${\displaystyle {\mbox{ShiftRow(State)}}}$
3. ${\displaystyle {\mbox{MixColumn(State)}}}$
4. ${\displaystyle {\mbox{AddRoundKey(State, RoundKey)}}}$

כאשר בסבב האחרון משמיטים את הפעולה MixColumn.

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

הטרנספורמציה SubBytes

פונקציית החלפה של AES

הטרנספורמציה SubBytes היא פונקציית החלפת בתים פשוטה ואי-ליניארית הפועלת באופן סדרתי על כל בתי המצב (ללא תלות אחד בשני) על פי טבלת החלפה קבועה והפיכה הנקראת S-Box.

בקוד:

void subBytes(byte *state)
{
 for (int i = 0; i < 16; i++)
 state[i] = sbox[state[i]];
}

במקרה של פענוח (decrypt), משתמשים בתיבות ההחלפה ההפוכית – rSBox:

void iSubBytes(byte *state)
{
 for (int i = 0; i < 16; i++)
 state[i] = rsbox[state[i]];
}

תיבות ההחלפה של ריינדל

sbox

rsbox

0 1 2 3 4 5 6 7 8 9 A B C D E F 0 63 7C 77 7B F2 6B 6F C5 30 01 67 2B FE D7 AB 76 1 CA 82 C9 7D FA 59 47 F0 AD D4 A2 AF 9C A4 72 C0 2 B7 FD 93 26 36 3F F7 CC 34 A5 E5 F1 71 D8 31 15 3 04 C7 23 C3 18 96 05 9A 07 12 80 E2 EB 27 B2 75 4 09 83 2C 1A 1B 6E 5A A0 52 3B D6 B3 29 E3 2F 84 5 53 D1 00 ED 20 FC B1 5B 6A CB BE 39 4A 4C 58 CF 6 D0 EF AA FB 43 4D 33 85 45 F9 02 7F 50 3C 9F A8 7 51 A3 40 8F 92 9D 38 F5 BC B6 DA 21 10 FF F3 D2 8 CD 0C 13 EC 5F 97 44 17 C4 A7 7E 3D 64 5D 19 73 9 60 81 4F DC 22 2A 90 88 46 EE B8 14 DE 5E 0B DB A E0 32 3A 0A 49 06 24 5C C2 D3 AC 62 91 95 E4 79 B E7 C8 37 6D 8D D5 4E A9 6C 56 F4 EA 65 7A AE 08 C BA 78 25 2E 1C A6 B4 C6 E8 DD 74 1F 4B BD 8B 8A D 70 3E B5 66 48 03 F6 0E 61 35 57 B9 86 C1 1D 9E E E1 F8 98 11 69 D9 8E 94 9B 1E 87 E9 CE 55 28 DF F 8C A1 89 0D BF E6 42 68 41 99 2D 0F B0 54 BB 16

0 1 2 3 4 5 6 7 8 9 A B C D E F 0 52 09 6A D5 30 36 A5 38 BF 40 A3 9E 81 F3 D7 FB 1 7C E3 39 82 9B 2F FF 87 34 8E 43 44 C4 DE E9 CB 2 54 7B 94 32 A6 C2 23 3D EE 4C 95 0B 42 FA C3 4E 3 08 2E A1 66 28 D9 24 B2 76 5B A2 49 6D 8B D1 25 4 72 F8 F6 64 86 68 98 16 D4 A4 5C CC 5D 65 B6 92 5 6C 70 48 50 FD ED B9 DA 5E 15 46 57 A7 8D 9D 84 6 90 D8 AB 00 8C BC D3 0A F7 E4 58 05 B8 B3 45 06 7 D0 2C 1E 8F CA 3F 0F 02 C1 AF BD 03 01 13 8A 6B 8 3A 91 11 41 4F 67 DC EA 97 F2 CF CE F0 B4 E6 73 9 96 AC 74 22 E7 AD 35 85 E2 F9 37 E8 1C 75 DF 6E A 47 F1 1A 71 1D 29 C5 89 6F B7 62 0E AA 18 BE 1B B FC 56 3E 4B C6 D2 79 20 9A DB C0 FE 78 CD 5A F4 C 1F DD A8 33 88 07 C7 31 B1 12 10 59 27 80 EC 5F D 60 51 7F A9 19 B5 4A 0D 2D E5 7A 9F 93 C9 9C EF E A0 E0 3B 4D AE 2A F5 B0 C8 EB BB 3C 83 53 99 61 F 17 2B 04 7E BA 77 D6 26 E1 69 14 63 55 21 0C 7D

בניגוד ל-DES, ערכי התיבות (S-box) של AES אינם ערכים אקראיים כלשהם שעונים על המאפיינים הדרושים, אלא הם בעלי מבנה אלגברי מובהק. למעשה אפשר לחשב אותם על ידי שילוב של שתי טרנספורמציות. הראשונה היא חישוב הופכי כפלי של הקלט בשדה ${\displaystyle GF(2^{8})}$ מודולו ${\displaystyle P(x)}$ כאשר אפס ממופה לעצמו כך שאם הקלט לפונקציה הראשונה של ${\displaystyle S}$ הוא ${\displaystyle A_{i}=(a_{7},...,a_{0})}$ הפלט הוא ${\displaystyle B_{i}'(x)=A_{i}^{-1}(x){\text{ (mod }}P(x))}$. הפעולה השנייה היא טרנספורמציה אפינית של הפלט מעל השדה ${\displaystyle F_{2^{8}}}$ שתפקידה "לטשטש" את המבנה האלגברי הייחודי שלו. הטרנספורמציה האפינית היא הכפלה במטריצה בינארית הפיכה קבועה מסדר ${\displaystyle 8\times 8}$ סיביות וחיבור עם וקטור קבוע באורך 8 סיביות. לצורך המחשה אם הקלט לתיבת ההחלפה הוא ${\displaystyle {\text{'C2'}}}$ ההופכי הכפלי הוא ${\displaystyle {\text{'2F'}}}$ כך שמתקיים ${\displaystyle {\text{'2F'}}\times {\text{'C2'}}\equiv 1{\text{ (mod }}{\text{'11B'}})}$, אחרי הטרנספורמציה האפינית מתקבל ${\displaystyle S(A_{i})={\text{'25'}}}$. הטרנספורמציה האפינית מומחשת בתרשים הבא:

${\displaystyle {\begin{bmatrix}y_{0}\\y_{1}\\y_{2}\\y_{3}\\y_{4}\\y_{5}\\y_{6}\\y_{7}\end{bmatrix}}={\begin{bmatrix}{\mbox{1 0 0 0 1 1 1 1}}\\{\mbox{1 1 0 0 0 1 1 1}}\\{\mbox{1 1 1 0 0 0 1 1}}\\{\mbox{1 1 1 1 0 0 0 1}}\\{\mbox{1 1 1 1 1 0 0 0}}\\{\mbox{0 1 1 1 1 1 0 0}}\\{\mbox{0 0 1 1 1 1 1 0}}\\{\mbox{0 0 0 1 1 1 1 1}}\end{bmatrix}}{\begin{bmatrix}x_{0}\\x_{1}\\x_{2}\\x_{3}\\x_{4}\\x_{5}\\x_{6}\\x_{7}\end{bmatrix}}+{\begin{bmatrix}1\\1\\0\\0\\0\\1\\1\\0\end{bmatrix}}}$

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

ביישום האלגוריתם בפועל, במערכת בה קיים זיכרון זמין רב, מעדיפים שימוש בטבלת איחזור (lookup table) כדי להימנע מפעולות כפל במטריצות בזמן ריצה. בטבלת האיחזור של ריינדל מקודדים את כל 256 הערכים האפשריים מראש ובזמן ריצה פשוט מחליפים את הקלט בערך המתאים לפי אינדקס. למשל, אם הבית הראשון של המצב הוא ${\displaystyle S_{0,0}={\mbox{'C2'}}}$, התוצאה תהיה הערך שנמצא בשורה 12 בעמודה השלישית (${\displaystyle {\mbox{'25'}}}$). אם טבלאות ההחלפה של ההצפנה והפענוח מוכנות מראש הקוד לביצוע ההחלפה מאוד פשוט, כל 16 בתי המצב מוחלפים בזה אחר זה בערכי תיבות ההחלפה המתאימות:

הטרנספורמציה ShiftRow

תהליך הזזה מחזורית

הזזת שורות המצב בהזזה מעגלית לפי ערכים שונים. השורה הראשונה נותרת במקומה והשורות הבאות מוזזות לפי היסטים קבועים ${\displaystyle C1,C2,C3}$ בהתאמה. ההיסטים תלויים בגודל הבלוק ${\displaystyle Nb}$ (בתקן הערכים הם 1,2,3 בהתאמה). הקוד הבא מתאר את הטרנספורמציה לפי התקן:

void shiftRows(byte *state)
{
 for (int i = 0; i < 4; i++)
 {
 for (int j = 0; j < i; j++)
 {
 byte tmp = state[0];
 for (int k = 0; k < 3; k++)
 state[k] = state[k+1];
 state[3] = tmp;
 }
 state += 4; // read the next state
 }
}

הפעולה ההפוכה של טרנספורמציה זו מושגת על ידי הזזה לפי ${\displaystyle Nb-C1,Nb-C2,Nb-C3}$ בהתאמה. כך שהבית בפוזיציה ${\displaystyle j}$ בשורה ${\displaystyle i}$ מוסט לפוזיציה ${\displaystyle (j+Nb-Ci){\mbox{ mod }}Nb}$. כדלהלן:

void iShiftRows(byte *state)
{
 for (int i = 0; i < 4; i++)
 {
 for(int j = 0; j < i; j++)
 {
 byte tmp = state[3];
 for (int k = 3; k > 0; k--)
 state[k] = state[k-1];
 state[0] = tmp;
 }
 state += 4; // get next state
 }
}

הטרנספורמציה MixColumn

תהליך ערבוב עמודות

עמודות המצב מיוצגות כפולינומים מעל ${\displaystyle GF(2^{8})}$ ומוכפלים (מודולו ${\displaystyle x^{4}+1}$) בפולינום קבוע ${\displaystyle c(x)={\mbox{'03'}}\cdot x^{3}+{\mbox{'01'}}\cdot x^{2}+{\mbox{'01'}}\cdot x+{\mbox{'02'}}}$ שהוא זר ל-${\displaystyle x^{4}+1}$ ולכן יש לו הופכי. המקדמים מוצגים בבסיס הקסדצימלי. אפשר לתאר את הפעולה הזו ככפל במטריצה ${\displaystyle b(x)=c(x)\otimes a(x)}$ כך:

${\displaystyle {\begin{bmatrix}b_{0}\\b_{1}\\b_{2}\\b_{3}\end{bmatrix}}={\begin{bmatrix}{\mbox{02 03 01 01}}\\{\mbox{01 02 03 01}}\\{\mbox{01 01 02 03}}\\{\mbox{03 01 01 02}}\end{bmatrix}}{\begin{bmatrix}a_{0}\\a_{1}\\a_{2}\\a_{3}\end{bmatrix}}}$

להלן הקוד שמשתמש בפונקציית העזר Gmul (מוגדרת למטה):

void mixColumns(byte *state)
{
 byte column[4];
 for (int i = 0; i < 4; i++)
 {
 for (int j = 0; j < 4; j++)
 column[j] = state[(j*4)+i];

 byte t[4]; // copy the column bytes to a temporary array
 t[0] = column[0], t[1] = column[1], t[2] = column[2], t[3] = column[3];
 column[0] = Gmul(t[0],2) ^ Gmul(t[3],1) ^ Gmul(t[2],1) ^ Gmul(t[1],3);
 column[1] = Gmul(t[1],2) ^ Gmul(t[0],1) ^ Gmul(t[3],1) ^ Gmul(t[2],3);
 column[2] = Gmul(t[2],2) ^ Gmul(t[1],1) ^ Gmul(t[0],1) ^ Gmul(t[3],3);
 column[3] = Gmul(t[3],2) ^ Gmul(t[2],1) ^ Gmul(t[1],1) ^ Gmul(t[0],3);

 for (int j = 0; j < 4; j++)
 state[(j*4)+i] = column[j];
 }
}

ולפענוח מבצעים פעולה דומה. כל עמודה מוכפלת בפולינום ${\displaystyle d(x)={\mbox{'0B'}}\cdot x^{3}+{\mbox{'0D'}}\cdot x^{2}+{\mbox{'09'}}\cdot x+{\mbox{'0E'}}}$ שהוא הופכי כפלי של ${\displaystyle c(x)}$. הקוד נראה כך:

void iMixColumns(byte *state)
{
 byte column[4];
 for (int i = 0; i < 4; i++)
 {
 for (int j = 0; j < 4; j++)
 column[j] = state[(j*4)+i];

 byte t[4]; // copy the column bytes to temporary array
 t[0] = column[0], t[1] = column[1], t[2] = column[2], t[3] = column[3];
 column[0] = Gmul(t[0],0x0E) ^ Gmul(t[3],0x09) ^ Gmul(t[2],0x0D) ^ Gmul(t[1],0x0B);
 column[1] = Gmul(t[1],0x0E) ^ Gmul(t[0],0x09) ^ Gmul(t[3],0x0D) ^ Gmul(t[2],0x0B);
 column[2] = Gmul(t[2],0x0E) ^ Gmul(t[1],0x09) ^ Gmul(t[0],0x0D) ^ Gmul(t[3],0x0B);
 column[3] = Gmul(t[3],0x0E) ^ Gmul(t[2],0x09) ^ Gmul(t[1],0x0D) ^ Gmul(t[0],0x0B);

 for (int j = 0; j < 4; j++)
 state[(j*4)+i] = column[j];
 }
}

פונקציית הוספת מפתח (AddRoundKey)

הוספת המפתח באמצעות XOR

מעדכנים את ערכי כל בתי המצב באמצעות חישוב XOR עם מפתח הסבב (round key).

את מפתח הסבב מפיקים ממפתח הצופן באמצעות התהליך המתואר להלן (Key Expansion) וגודלו נקבע לפי גודל הבלוק ${\displaystyle Nb}$. לדוגמה המערך הדו־ממדי של המצב הוא ${\displaystyle s_{0,c},s_{1,c},s_{2,c},s_{3,c}}$ כאשר מספר העמודה ${\displaystyle c=0,...,Nb}$ ומספר הסבב ${\displaystyle r=0,...,Nr}$, מחשבים את ${\displaystyle [s_{0,c},s_{1,c},s_{2,c},s_{3,c}]\oplus [w_{r*Nb+c}]}$ (הסוגריים המרובעים מייצגים את המילה הנוצרת מעמודה ${\displaystyle c}$ של המצב). הפעולה ההפוכה בתהליך הפענוח זהה כיוון שהפעולה XOR הופכית של עצמה. להלן הקוד של שכבת הוספת המפתח:

void addRoundKey(byte *state, byte *roundKey)
{
 for (int i = 0; i < 16; i++)
 state[i] ^= roundKey[i];
}

תהליך הרחבת מפתח (Key Expansion)

מפתחות הסבבים הם פונקציה של מפתח הצופן המסופק על ידי המשתמש. סך כל סיביות המפתח המורחב שווה לגודל הבלוק הנבחר כפול מספר הסבבים ועוד אחד. למשל עבור בלוק של 128 סיביות יהיו 1408 סיביות מפתח מורחב, אותם מחלקים ל-${\displaystyle Nb}$ מילים לפי הסדר. למעשה מתקבל מערך חד־ממדי של 44 מילים בגודל 4 בתים המסומן ${\displaystyle W[Nb\cdot (Nr+1)]}$ כאשר בכל סבב משתמשים ב-${\displaystyle Nb}$ המילים הבאות.

תחילה מחלקים את מפתח הצופן למילים בגודל 32 סיביות אותם מציבים ב-${\displaystyle Nk}$ הכניסות הראשונות במערך. יתר הכניסות מחושבות באופן רקורסיבי על בסיס ערכים קודמים. כל מילה ${\displaystyle W[i]}$ היא חישוב XOR עם מילה ${\displaystyle W[i-Nk]}$ ועבור מילים שמיקומם הוא כפולה של ${\displaystyle Nk}$ מופעלת טרנספורמציה נוספת שכוללת הזזה מעגלית של בתי המילה בנוסף להחלפה בתיבות ההחלפה וחיבור XOR עם הקבועים ${\displaystyle {\mbox{Rcon}}}$ (ראו להלן). פרוצדורת הרחבת המפתח תלויה ב-${\displaystyle Nk}$ כאשר ${\displaystyle Nk\leq 6}$ הרחבת המפתח מתוארת בפסאודו קוד הבא:

${\displaystyle {\mbox{For }}i=Nk{\mbox{ to }}Nb\cdot (Nr+1)-1{\mbox{ Do:}}}$

1. ${\displaystyle {\mbox{temp}}=W[i-1]}$
2. ${\displaystyle {\mbox{If }}i{\mbox{ mod }}Nk=0{\mbox{ then}}}$

   ${\displaystyle {\mbox{temp = SubByte(RotByte(temp))}}\oplus {\mbox{ Rcon}}[i/Nk]}$

3. ${\displaystyle W[i]=W[i-Nk]\oplus {\mbox{temp}}}$

כאן הפונקציה ${\displaystyle {\mbox{SubByte(W)}}}$ מחזירה ארבעה בתים שהם תוצאה של הפעלת תיבות ההחלפה של ריינדל על בתי הקלט. הפונקציה ${\displaystyle {\mbox{RotByte(W)}}}$ מחזירה ארבעה בתים שהם תמורה מחזורית של עצמם. דהיינו שינוי סדר הבתים, אם בתי הקלט הם ${\displaystyle a,b,c,d}$ התוצאה תהיה ${\displaystyle b,c,d,a}$.

הקבועים ${\displaystyle {\mbox{Rcon}}}$ המשמשים להרחבת המפתח הם סדרה של עשרה ערכים בגודל 32 סיביות מהצורה ${\displaystyle {\mbox{Rcon}}_{i}=({\mbox{RC}}_{i},{\mbox{'00'}},{\mbox{'00'}},{\mbox{'00'}})}$. ערכי ${\displaystyle {\mbox{RC}}_{i}}$ מייצגים חזקות הפולינום ${\displaystyle x^{i-1}}$ דהיינו מתחילים ב-${\displaystyle {\mbox{RC}}_{1}=1}$ ואז מחשבים ${\displaystyle {\mbox{RC}}_{i}=x\cdot ({\mbox{RC}}_{i-1})=x^{(i-1)}}$. עבור מפתח 128 סיביות הקבועים הם:

${\displaystyle \{{\mbox{'01','02','04','08','10','20','40','80','1B','36'}}\}}$.

במפתח 256 סיביות משתמשים רק בשבעת הערכים הראשונים. וכן אם המפתח הנבחר בגודל 256 שאז ${\displaystyle Nk>6}$, נוספת פעולה לאחר שורה 2 כדלהלן:

${\displaystyle {\mbox{Else If }}i{\mbox{ mod }}Nk=4{\mbox{ then}}}$

${\displaystyle {\mbox{temp = SubByte(temp)}}}$

סיכום הפרוצדורה להרחבת המפתח בקוד C++‎ הוא:

void createRoundKey(byte *expKey, byte *roundKey)
{
 for(int i = 0; i < 4; i++)
 {
 for(int j = 0; j < 4; j++)
 roundKey[(i+(j*4))] = expKey[(i*4)+j];
 }
}
void expandKey(byte *expKey, byte *key, int size, size_t expKeySize)
{
 int currSize = 0, rconIter = 1;
 byte t[4] = {0};
 for (int i = 0; i < size; i++)
 expKey[i] = key[i];
 currSize += size;

 while ((unsigned)currSize < expKeySize)
 {
 for(int i = 0; i < 4; i++)
 t[i] = expKey[(currSize - 4) + i];

 if(currSize % size == 0)
 {
 byte tmp = t[0];
 for(int i = 0; i < 3; i++)
 t[i] = t[i+1];
 t[3] = tmp;
 for(int i = 0; i < 4; i++)
 t[i] = sbox[t[i]];

 t[0] = t[0] ^ rcon[rconIter++];
 }
 if (size == 32 && ((currSize % size) == 16))
 {
 for(int i = 0; i < 4; i++)
 t[i] = sbox[t[i]];
 }
 for(int i = 0; i < 4; i++)
 {
 expKey[currSize] = expKey[currSize - size] ^ t[i];
 currSize++;
 }
 }
}

היבטים מתמטיים

רוב הפעולות בצופן הן פעולות אלגבריות על בתים המייצגים איברים של השדה ${\displaystyle GF(2^{8})}$. הסיבות לבחירה זו הן שכל איבר בשדה ניתן לייצוג על ידי בית אחד במחשב וכן בגלל תכונת האיזומורפיות. מסיבות של יעילות נבחר ייצוג פולינומי רגיל, דהיינו הבית ${\displaystyle a}$ מתאר פולינום ממעלה 7 עם מקדמים ${\displaystyle a_{i}\in \{0,1\}}$ מהייצוג הבינארי שלו, כאשר ${\displaystyle a_{0}}$ מייצג את המקדם הראשון או החופשי ו-${\displaystyle a_{7}}$ המקדם המוביל. בניסוח רשמי:

${\displaystyle A(x)=a_{7}x^{7}+a_{6}x^{6}+\cdots +a_{1}x+a_{0},\ \ a_{i}\in GF(2)=\{0,1\}}$

אף על פי שבזיכרון האלמנטים מאוחסנים כמספרים שלמים, יש הבדל מהותי בין אריתמטיקה במספרים שלמים לבין חשבון פולינומים מעל הרחבה של השדה הבינארי. לשם הנוחות המקדמים מוצגים כאן בבסיס הקסדצימלי כנהוג בשפת C לדוגמה 0X2D שהוא ${\displaystyle (101101)_{2}}$ (בייצוג בינארי) מקביל לפולינום ${\displaystyle x^{5}+x^{3}+x^{2}+1}$. בכתיב זה משמיטים את המקדמים כי הם מובנים מההקשר. בצורה מפורשת יותר אפשר להציג זאת: ${\displaystyle 1\cdot x^{5}+0\cdot x^{4}+1\cdot x^{3}+1\cdot x^{2}+0\cdot x^{1}+1\cdot x^{0}}$.

בכתיב מקוצר אפשר להציג אלמנט כוקטור ${\displaystyle A=(a_{7},a_{6},...,a_{1},a_{0})}$ שמכיל את המקדמים (בזיכרון מאחסנים רק את המקדמים). פעולת החיבור בין אלמנטים בשדה היא חיבור מודולו 2 של המקדמים (פעולה המקבילה ל-XOR המסומן ${\displaystyle \oplus }$) לדוגמה ${\displaystyle (x^{5}+x^{3}+x)+(x^{4}+x^{3}+1)=x^{5}+x^{4}+x+1}$ ובייצוג הקסדצימלי ${\displaystyle {\text{'2A'}}\oplus {\text{'19'}}={\text{'33'}}}$. באופן פורמלי:

${\displaystyle C(x)=A(x)+B(x)=\sum _{i=0}^{m-1}(a_{i}+b_{i})x^{i}}$

כאשר כל ${\displaystyle (a_{i}+b_{i})}$ הוא מודולו 2. עם פעולה זו מתקבלת חבורה אבלית אסוציאטיבית וקומוטטיבית עם איבר יחידה אפס ואיבר נגדי (כל אלמנט נגדי של עצמו לכן חיסור זהה לחיבור) ואיבר הופכי.

פעולת כפל בין אלמנטים בשדה היא כפל ארוך בפולינומים כשהתוצאה היא:

${\displaystyle A(x)\cdot B(x)=(a_{m-1}x^{m-1}+\cdots +a_{0})\cdot (b_{m-1}x^{m-1}+\cdots +b_{0})=C(x)=c_{2m-2}x^{2m-2}+\cdots +c_{0}}$

כאשר כל ${\displaystyle c_{i}}$ הוא מודולו 2. כעת לפי חוקי החשבון המודולרי היות שהתוצאה אינה בשדה ${\displaystyle GF(2^{8})}$ (כי המעלה שלה גבוהה משבע) יש צורך לצמצם אותה מודולו פולינום אי-פריק המייצג את השדה (דהיינו שחזקות שלו הם האלמנטים של השדה). ב-AES נבחר הפולינום ${\displaystyle P(x)=x^{8}+x^{4}+x^{3}+x+1}$ (או ${\displaystyle {\text{'11B'}}}$ בבסיס הקסדצימלי) שהוא פולינום אי-פריק ממעלה 8. היות שהפעולות הן רק בגבולות בית אחד, אפשר להתעלם מהסיבית העליונה לכן הצמצום נעשה במחשב עם ${\displaystyle {\text{0x1b}}}$. פעולת הכפל המודולרי בניסוח פורמלי היא:

${\displaystyle C(x)\equiv A(x)\cdot B(x){\text{ mod }}P(x)}$

כפל פולינומים מודולרי

byte px = 0x1b;
byte Gmul(byte a, byte b)
{
	byte p = 0, high;
	for (int i = 0; i < 8; i++)
	{
 if ((b & 1) == 1) p ^= a;
 high = (a & 0x80);
 a <<= 1;
 if(high == 0x80) a ^= px;
 b >>= 1;
	}
	return p;
}

משיקולי יעילות רצוי לחשב כפל פולינומים בשדה ${\displaystyle GF(2^{8})}$ בעזרת רקורסיה של הכפלות בפולינום ${\displaystyle x}$ ('02' בייצוג הקסדצימלי), כיוון שמעשית פעולה זו שקולה לאופרטור ההזזה בסיביות (shift left). למשל ${\displaystyle (x+1)\cdot x=x^{2}+x}$ הוא למעשה הזזת המקדמים צעד אחד שמאלה והוספת אפס בהתחלה. בנוסף, אם התוצאה היא ממעלה גבוהה מ-7 כאשר ${\displaystyle b_{7}=1}$ שזה אומר שהתרחשה גלישה, יהיה צורך בפעולת חיסור נוספת לצימצום התוצאה לפי כללי החשבון המודולרי בפולינומים. היות שהגלישה קטנה, אפשר להסתפק בחיסור במקום חילוק מודולרי, ולכן מבצעים רק XOR עם הפולינום האי-פריק ${\displaystyle x^{4}+x^{3}+x+1}$. הפעולות הללו נחשבות לפעולות זולות במונחי מחשוב.

לדוגמה הכפל ${\displaystyle (x^{6}+x+1)\times (x^{2}+1)}$ בייצוג הקסדצימלי ${\displaystyle {\mbox{'43'}}\times {\mbox{'05'}}}$ שקול בעצם לפעמיים כפל ב-${\displaystyle x}$ (שתי הזזות) וחיבור אחד. לכן תחילה לאחר שתי הזזות מתקבל ${\displaystyle x^{8}+x^{3}+x^{2}}$ או ${\displaystyle {\mbox{'10C'}}}$ והיות שהתרחשה גלישה יש לצמצם על ידי חיסור ${\displaystyle (x^{8}+x^{3}+x^{2})-(x^{8}+x^{4}+x^{3}+x+1)=(x^{4}+x^{2}+x+1)}$ ואחר כך החיבור ${\displaystyle (x^{4}+x^{2}+x+1)+(x^{6}+x+1)=x^{6}+x^{4}+x^{2}}$. לסיכום ${\displaystyle {\text{'43'}}\times {\text{'05'}}={\text{'54'}}}$ (מודולו ${\displaystyle P(x)}$).

התרשים משמאל ממחיש בקוד C++‎ את הפונקציה Gmul המקבלת שני אלמנטים ומחזירה את תוצאת הכפל שלהם בשדה ${\displaystyle GF(2^{8})}$ מודולו ${\displaystyle P(x)}$. כאן צריך להיזהר מהתקפת ערוץ צדדי המודדת את הפרשי הזמן בעת ביצוע הכפל (התנאי הבודק אם הסיבית הנוכחית ב-${\displaystyle b}$ היא 0 או 1 משפיע על זמן החישוב). לכן במימושים בטוחים מופיע קוד ארוך במקצת שעוקף את הבעיה ומבטיח זמן ביצוע אחיד (constant time) ללא תלות בערכן של סיביות ${\displaystyle b}$.

כפל במטריצת המצב

בחלק אחר של הצופן מתייחסים לעמודות מטריצת המצב כאל מקדמים מעל השדה ${\displaystyle F_{2^{8}}}$. הפעולות האריתמטיות מוגדרות ברמת מילים כאשר כל עמודה מייצגת מילה אחת בגודל 32 סיביות המורכבת מארבעה בתים. כל בית נחשב למקדם אחד וארבעתם מייצגים את האלמנטים של הפולינום ${\displaystyle a_{3}x^{3}+a_{2}x^{2}+a_{1}x+a_{0}}$. פעולת הכפל דומה לשדה הבינארי, כאשר את הכפל הארוך ממירים לסדרה של הזזות (shift) ברמה של בתים והתוצאה היא השארית מחילוק ב-${\displaystyle x^{4}+1}$, כלומר כל אלמנט הוא תוצאה של ${\displaystyle x^{i}{\text{ mod }}x^{4}+1=x^{i{\text{ mod }}4}}$. יוצא שהכפל בפולינום ${\displaystyle x}$ או בחזקות שלו מקביל למעשה להזזה מעגלית ברמה של בתים, כלומר לא יותר מאשר הזזה מעגלית של בתים שמאלה כאשר הבית שנפלט מצד שמאל מוחזר מצד ימין. למשל כדי לחשב את הכפל המודולרי ${\displaystyle d(x)=a(x)\otimes b(x)}$ מחשבים את ${\displaystyle d(x)=d_{3}x^{3}+d_{2}x^{2}+d_{1}x+d_{0}}$ על ידי:

כפל במטריצה ב-AES

כיוון שהפולינום איתו מכפילים קבוע, אפשר להכין מראש טבלה שמייצגת את ההזזות (צד ימין בתרשים). לדוגמה אם ערכי העמודה הם: ${\displaystyle (S_{0,0}={\text{'07'}},S_{1,0}={\text{'3C'}},S_{2,0}={\text{'10'}},S_{3,0}={\text{'65'}})}$ התוצאה תהיה: ${\displaystyle (S_{0,0}={\text{'3F'}},S_{1,0}={\text{'2A'}},S_{2,0}={\text{'B4'}},S_{3,0}={\text{'EF'}})}$. בהמשך מובא קוד C++‎ הממחיש את הפעולה.

היבטי יישום

צופן ריינדל מתאים להטמעה ביעילות במגוון מערכות ובחומרה ייעודית כמו כרטיס חכם המצויד במעבד 8-ביט. במעבד 32 סיביות אפשר למטב את הצופן על ידי המרת ארבע טרנספורמציות הסבב בטבלת חיפוש אחת גדולה. בנוסף, כפל מטריצות ניתן לפישוט על ידי צירוף ליניארי של וקטורים. מכינים ארבע טבלאות ${\displaystyle T_{0}}$ עד ${\displaystyle T_{3}}$ המכילות 256 מילים בגודל 4 בתים (סך הכול 4 קילובתים). את ערכי הכניסות מחשבים ומקודדים מראש (החישובים מופיעים בתיאור האלגוריתם על ידי המחברים, ערכי הטבלאות מופיעים באתר NIST בתקן 197) ואז אפשר להמיר את טרנספורמציות הסבב לפעולה הבאה:

${\displaystyle e[j]=T_{0}[a_{0,j}]\oplus T_{1}[a_{1,j-C1}]\oplus T_{2}[a_{2,j-C2}]\oplus T_{3}[a_{3,j-C3}]\oplus k_{j}}$

אפשר לראות שהפעולה מורכבת מארבע פעולות חיפוש בטבלה וארבע פעולות XOR לכל עמודה בכל סבב. במחיר של שלוש הזזות נוספות בכל עמודה (בכל סבב) אפשר להחליף את הפעולה הקודמת בפעולת חיפוש בטבלה אחת בגודל אחד קילוביט:

${\displaystyle e_{j}=k_{j}\;\oplus \;T[b_{0,j}]\;\oplus \;{\mbox{ RotByte}}(T[b_{1,j-C1}]\;\oplus \;{\mbox{ RotByte}}(T[b_{2,j-C2}]\;\oplus \;{\mbox{ RotByte}}(T[b_{3,j-C3}])))}$

כמו כן כדי לשמור על קוד מצומצם אם נחוץ אפשר להוסיף קוד לייצור הטבלאות בזמן ריצה במקום לקודד אותן מראש. בסבב האחרון בשל העובדה שלא מבוצעת הטרנספורמציה MixColumn לא ניתן להשתמש בטבלאות ${\displaystyle T_{i}}$ כיוון שהן חושבו כדי לכלול את הטרנספורמציה הזו. במקום ליצור טבלה מיוחדת עבור הסבב האחרון אפשר לבצע מיסוך (masking) כדי לחלץ את הערך הנכון בזמן ביצוע הסבב האחרון.

הצפנה

void Rijndael(byte *state, byte *expKey, int nRounds)
{
 byte roundKey[16];
 createRoundKey(expKey, roundKey);
 addRoundKey(state, roundKey);

 for (int i = 1; i < nRounds; i++)
 {
 createRoundKey(expKey + 16*i, roundKey);
 subBytes(state);
 shiftRows(state);
 mixColumns(state);
 addRoundKey(state, roundKey);
 }

 createRoundKey(expKey + 16 * nRounds, roundKey);
 subBytes(state);
 shiftRows(state);
 addRoundKey(state, roundKey);
}

// encryption
int AES_Encrypt(byte *input, byte *output, byte *key, int size)
{
 int nbrRounds;
 byte expKey[240]; // the expanded key takes 240 bytes at most
 byte block[AES_BLOCK];
 switch (size)
 {
 case 16: nbrRounds = 10; break;
 case 24: nbrRounds = 12; break;
 case 32: nbrRounds = 14; break;
 default: return -1; // error code for wrong key size
 }
 for (int i = 0; i < 4; i++)
 {
 for (int j = 0; j < 4; j++)
 block[(i + (j * 4))] = input[(i * 4) + j];
 }
 expandKey(expKey, key, size, 16 * (nbrRounds + 1));
 rijndael(block, expKey, nbrRounds);

 for (int i = 0; i < 4; i++)
 {
 for(int j = 0; j < 4; j++)
 output[(i * 4) + j] = block[(i + (j * 4))];
 }
 return 0;
}

פענוח

void iRijndael(byte *state, byte *expKey, int nRounds)
{
 byte roundKey[16];
 createRoundKey(expKey + 16 * nRounds, roundKey);
 addRoundKey(state, roundKey);

 for(int i = nRounds - 1; i > 0; i--)
 {
 createRoundKey(expKey + 16*i, roundKey);
 iShiftRows(state);
 iSubBytes(state);
 addRoundKey(state, roundKey);
 iMixColumns(state);
 }

 createRoundKey(expKey, roundKey);
 iShiftRows(state);
 iSubBytes(state);
 addRoundKey(state, roundKey);
}

// decryption
int AES_Decrypt(byte *input, byte *output, byte *key, int size)
{
 int nbrRounds;
 byte expKey[240];
 byte block[16];
 switch (size)
 {
 case 16: nbrRounds = 10; break;
 case 24: nbrRounds = 12; break;
 case 32: nbrRounds = 14; break;
 default: return -1;
 }
 for (int i = 0; i < 4; i++)
 {
 for(int j = 0; j < 4; j++)
 block[(i+(j*4))] = input[(i * 4) + j];
 }
 expandKey(expKey, key, size, 16 * (nbrRounds + 1));
 inv_rijndael(block, expKey, nbrRounds);

 for (int i = 0; i < 4; i++)
 {
 for (int j = 0; j < 4; j++)
 output[(i*4)+j] = block[(i+(j*4))];
 }
 return 0;
}

ביצועים

לפי בדיקות שערכו המפתחים, על גרסאות שונות של מעבד פנטיום הצפנת AES על מעבד 200 MHz, צרכה כ-18 מחזורי שעון לבית שזה מקביל בערך ל-11 מגה-בית בשנייה ועל מעבד פנטיום M 1.7 GHz עד 60 מגה לשנייה. ב-2008 הטמיעה אינטל הרחבת סט פקודות לסדרה x86 בשם Advanced Encryption Standard New Instructions בקיצור AES-NI הכוללת פונקציות הצפנה ופענוח AESENC ו-AESDEC המגיעות למהירות של 3.5 cpb. ב-2011^[3][4] הטמיעה חברת אינטל פונקציות קריפטוגרפיות ממוטבות (IPP) בארכיטקטורת AI שתומכות ב-OpenSSL גרסה 1.0.1 ומעלה. התוצאות שנבדקו בעיקר על מעבד Xeon הגיעו לביצועים של כ-900 מגה בשנייה. (פענוח מהיר יותר ויכול להגיע ל-2.3 ג'יגה לשנייה).

ביטחון הצופן

במהלך התחרות המקורית של NIST הוכרז על ידי המארגנים שלא נמצאו באף אחד מהפיינליסטים חולשות כלשהן. הסברה הייתה אז שהתקפה מעשית כנגד האלגוריתמים המנויים עם מפתח 128 סיביות היא לא סבירה בטווח של כעשר שנים, אך ההגדרה של התקפה מעשית נתונה לשינויים בהתאם ליכולת טכנולוגית. הערכות שניתנו על ידי מומחים^[5] לפני כעשור, הגדירו התקפה מעשית ככזו שמבוצעת עם ${\displaystyle 2^{32}}$ טקסטים ידועים (known plaintext) בסיבוכיות של ${\displaystyle 2^{70}}$ ניסיונות. כיום הועלה הרף מעט יותר. להערכת מומחים ${\displaystyle 2^{128}}$ עדיין נחשב מחוץ להישג יד, אם כי איש לא יודע להעריך לכמה זמן.

לדעת מומחים^[6] גם אם מחשב קוונטי יהיה מעשי בטווח הקרוב, סיבוכיות התקפה כנגד האלגוריתמים המנויים באמצעות חישוב קוונטי רק תפחית את המאמץ לחצי (בכללות ${\displaystyle 2^{k/2}}$ פעולות כאשר ${\displaystyle k}$ אורך המפתח), כלומר מפתח 256 עדיין מותיר שולי ביטחון טובים נכון לשנת 2014 ולשנים הקרובות. יתרה מזו, קיימות טכניקות הצפנה מרובה עם מפתחות שונים להגברת הביטחון ולאילו שחוששים במיוחד לחוסנו של האלגוריתם מסוים כנגד התקפות עתידיות, אפשר להגיע לתצורה שבה הצפנה עם מספר אלגוריתמים שונים, תהיה חזקה לפחות כחוזקו של האלגוריתם החזק מביניהם. זאת בהנחה שלא סביר שתמצא דרך לפצח את כולם באותה הקלות.

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

ניסיונות התקפה

ב-2002 פותחה על ידי הקריפטוגרפים קורטויז ופייפרציק שהיה ממפתחי LOKI התקפה על AES הנקראת XSL שמסוגלת לטענתם לפרוץ את האלגוריתם מהר יותר מכוח גס באופן משמעותי. ההתקפה פועלת על ידי גזירת מערכת משוואות ריבועיות מהצופן, שהן פונקציה של הטקסט המקורי, הטקסט המוצפן והמפתח. המערכת מאוד גדולה (כ-8,000 משוואות עם כ-1,600 נעלמים במקרה של AES-128). אלימינציית גאוס מחייבת המצאות כמות מספקת של משוואות בלתי תלויות. הם הציעו פתרון באמצעות טכניקה שהמציאו לצמצום מספר הנעלמים שנקראת eXtended Sparse Linearization המסתמכת על עבודתם של שמיר וקיפניס. יתרון ההתקפה שנדרשת רק כמות מועטה של טקסטים ידועים. אולם הסתבר שהשיטה דורשת משאבים עצומים ואינה יעילה מכוח גס כפי שנטען בתחילה על ידי המפתחים, לכן נקראת תאורטית במובן זה.

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

ב-2009 פותחה על ידי בריוקוב וחובראטוביץ והלוי התקפה על כל גרסאות AES הנקראת התקפת מפתחות קשורים^[7][8]. התקפה מסוג זה מניחה שהתוקף מסוגל לבחור מפתחות שיש ביניהם קשר או יחס כלשהו, כגון אם מפתח אחד הוא XOR של מפתח אחר עם קבוע כלשהו. ההתקפה מתמקדת בתהליך הרחבת המפתח הפשוט יחסית של ריינדל בגרסאות AES-192 ו-AES-256 והגיעה לסיבוכיות של ${\displaystyle 2^{99.5}}$ וסיבוכיות מקום של ${\displaystyle 2^{96}}$. היות שהמפתחות נבחרים באקראי, באופן מעשי התקפה כזו אינה סבירה. התקפה דומה שהמציאו המפתחים האמורים יחד עם שמיר, דונקלמן וקלר, כנגד AES-256 מצליחה לחשוף את המפתח רק עם שני מפתחות קשורים, בזמן של ${\displaystyle 2^{39}}$ בתשעה סבבים, ${\displaystyle 2^{45}}$ בעשרה סבבים ו-${\displaystyle 2^{70}}$ ב-11 סבבים. אף אחת מההתקפות לא יעילה כנגד AES במלוא הסבבים.

נכון ל-2011 ההתקפה הטובה ביותר כנגד AES מלא (14 סבבים במקרה של 256 סיביות) היא של בוגדנוב, חובראטוביץ' ורכנברג. זוהי סוג של "התקפת נפגש באמצע" הנקראת biclique והיא טובה מכוח גס בפקטור של 4 בקירוב כלומר ${\displaystyle 2^{252}}$ על כן חשיבותה תאורטית והיא אינה מסכנת את השימוש בצופן ריינדל מבחינה מעשית.

התקפת ערוץ צדדי

נכון ל-2011 התפרסמו מספר התקפות ערוץ צדדי מוצלחות כנגד AES אם כי בעקיפין. סוג זה של התקפה אינו מתמקד בצופן עצמו אלא באופן יישומו במערכת, העשוי שלא במודע להדליף מידע קריטי אודות הצופן או המפתח. באפריל 2005, הכריזו מומחים על התקפת cache timing שהצליחה לפרוץ לשרת ייעודי שיישם הצפנת AES כחלק ממערכת SSL. השרת נבנה כך שיאפשר חשיפה של מידע תזמון רב ככל האפשר. ההתקפה נזקקה ללפחות 200 מיליון צופנים נבחרים. יש הסבורים כי התקפה זו אינה מעשית דרך אינטרנט, ברוס שנייר כינה אותה "התקפת תזמון נאה". באותה שנה, עדי שמיר ושני חוקרים נוספים ממכון ויצמן, פרסמו מסמך המתאר מספר התקפות תזמון דומות כנגד AES ופתרונותיהן. אחת מהן, הצליחה לחשוף את המפתח כולו אחרי 800 כתיבות לזיכרון בלבד תוך מספר מילישניות, בתנאי שלתוקף הייתה גישה לשרת בו מתבצעת ההצפנה. הדרך הטובה ביותר להתמודדות עם התקפות מסוג זה היא יישום האלגוריתם באופן שאינו מדליף מידע, בעיקר הימנעות משימוש בטבלאות המרה (table lookup) שאמנם משפרות ביצועים אך פותחות פתח להתקפות תיזמון, לשם כך פותחו שיטות כגון Bit Slicing, שיטה ישנה שפותחה על ידי אלי ביהם לשיפור ביצועי אלגוריתם DES והתגלתה כטובה במיוחד כנגד התקפת תיזמון.

ראו גם

• צופן בלוקים
• מצב הפעלה של צופן בלוקים

קישורים חיצוניים

מדיה וקבצים בנושא AES בוויקישיתוף

מקורות

• NIST, Federal Information Processing Standards Publication 197
• Daemen, Joan, Rijmen, Vincent, The Design of Rijndael ספרינגר 2002, XVII, 238 p.
• מתקפת תזמון על AES

קישורים נוספים

• אתר להצפנה ופיענוח AES אונליין
• יאן ואינטר, עד כמה צופן AES בטוח מפני התקפות כוח גס?(הקישור אינו פעיל), באתר טכנולוגיות
• אתר הרשמי של NSA, ערכת הצפנה Suite B
• AES, באתר אנציקלופדיה בריטניקה (באנגלית)

הערות שוליים

1. Gayle Swenson, Commerce Department Announces Winner of Global Information Security Competition, NIST, ‏2000-10-02 (באנגלית)
2. Joan Daemen, Vincent Rijmen, The wide trail design strategy, in Proceedings of the 8th IMA International Conference on Cryptography and Coding (IMA ’01, 2001, עמ' 222–238
3. Improving OpenSSL* Performance
4. Intel® Integrated Performance
5. Comments by the NESSIE Project on the AES Finalists
6. Quantum Cryptography
7. Distinguisher and Related-Key Attack on the Full AES-256 Alex Biryukov, Dmitry Khovratovich, Ivica Nikolić, Lecture Notes in Computer Science
8. Biryukov, A., Khovratovich, D., Nikolic, I.: Distinguisher and Related-Key Attack on the Full AES-256. In Halevi, S., ed.: CRYPTO 2009. Volume 5677 of LNCS., Springer (August 2009) 231–249