Advanced Encryption Standard

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

הטרנספורמציה ByteSub היא פונקציית החלפת בתים אי-ליניארית הפועלת באופן סדרתי על כל בתי המצב ללא תלות אחד בשני על פי טבלת החלפה קבועה והפיכה. בניגוד ל-DES ערכי תיבות (S-box) של AES אינם ערכים אקראיים כלשהם שעונים על המאפיינים הדרושים, אלא הם בעלי מבנה אלגברי מובהק. למעשה אפשר לחשב אותם על ידי שילוב של שתי טרנספורמציות. הראשונה היא חישוב הופכי כפלי של הקלט בשדה  מודולו  כאשר אפס ממופה לעצמו כך שאם הקלט לפונקציה הראשונה של  הוא  הפלט הוא . הפעולה השנייה היא טרנספורמציה אפינית של הפלט מעל השדה  שתפקידה "לטשטש" את המבנה האלגברי הייחודי שלו. הטרנספורמציה האפינית היא הכפלה במטריצה בינארית הפיכה קבועה מסדר  סיביות וחיבור עם וקטור קבוע באורך 8 סיביות. לצורך המחשה אם הקלט לתיבת ההחלפה הוא  ההופכי הכפלי הוא  כך שמתקיים , אחרי הטרנספורמציה האפינית מתקבל . הטרנספורמציה האפינית מומחשת בתרשים הבא:
לפענוח מבצעים בסדר הפוך, דהיינו תחילה טרנספורמציה אפינית הפוכה ואז חישוב הופכי כפלי. ביישום האלגוריתם בפועל, במערכת בה קיים זיכרון זמין רב, מעדיפים שימוש בטבלת איחזור (lookup table) כדי להימנע מפעולות כפל במטריצות בזמן ריצה. בטבלת האיחזור של ריינדל מקודדים את כל 256 הערכים האפשריים מראש ובזמן ריצה פשוט מחליפים את הקלט בערך המתאים לפי אינדקס למשל אם הבית הראשון של המצב הוא , התוצאה תהיה הערך שנמצא בשורה 12 בעמודה השלישית (). אם טבלאות ההחלפה של ההצפנה והפענוח מוכנות מראש הקוד לביצוע ההחלפה מאוד פשוט, כל 16 בתי המצב מוחלפים בזה אחר זה בערכי תיבות ההחלפה המתאימות:
void subBytes(byte *state){
   for(int i = 0; i < 16; i++)
      state[i] = sbox[state[i]];}
לפענוח משתמשים בתיבות ההחלפה ההופכיות:
void iSubBytes(byte *state){
   for(int i = 0; i < 16; i++)
      state[i] = rsbox[state[i]];}

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

הזזת שורות המצב בהזזה מעגלית לפי ערכים שונים. השורה הראשונה נותרת במקומה והשורות הבאות מוזזות לפי היסטים קבועים  בהתאמה. ההיסטים תלויים בגודל הבלוק  (בתקן הערכים הם 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
   }}
הפעולה ההפוכה של טרנספורמציה זו מושגת על ידי הזזה לפי  בהתאמה. כך שהבית בפוזיציה  בשורה  מוסט לפוזיציה . כדלהלן:
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

עמודות המצב מיוצגות כפולינומים מעל  ומוכפלים (מודולו ) בפולינום קבוע  שהוא זר ל- ולכן יש לו הופכי. המקדמים מוצגים בבסיס הקסדצימלי. אפשר לתאר את הפעולה הזו ככפל במטריצה  כך:
להלן הקוד שמשתמש בפונקציית העזר 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];
   }}
ולפענוח מבצעים פעולה דומה. כל עמודה מוכפלת בפולינום  שהוא הופכי כפלי של . הקוד נראה כך:
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];
   }}

פונקציית הוספת מפתח

מעדכנים את ערכי כל בתי המצב באמצעות חישוב XOR עם מפתח הסבב (round key). את מפתח הסבב מפיקים ממפתח הצופן באמצעות התהליך המתואר להלן וגודלו נקבע לפי גודל הבלוק . לדוגמה המערך הדו ממדי של המצב הוא  כאשר מספר העמודה  ומספר הסבב , מחשבים את  (הסוגריים המרובעות מייצגות את המילה הנוצרת מעמודה  של המצב). הפעולה ההפוכה בתהליך הפענוח זהה כיוון שהפעולה XOR הופכית של עצמה. להלן הקוד של שכבת הוספת המפתח:
void addRoundKey(byte *state, byte *roundKey){
   for(int i = 0; i < 16; i++)
      state[i] ^= roundKey[i];}

היבטי יישום

צופן ריינדל מתאים להטמעה ביעילות במגוון מערכות ובחומרה ייעודית כמו כרטיס חכם המצויד במעבד 8-ביט. במעבד 32 סיביות אפשר למטב את הצופן על ידי המרת ארבע טרנספורמציות הסבב בטבלת חיפוש אחת גדולה. בנוסף כפל מטריצות ניתן לפישוט על ידי קומבינציה ליניארית של וקטורים. מכינים ארבע טבלאות  עד  המכילות 256 מילים בגודל 4 בתים (סך הכול 4 קילובתים). את ערכי הכניסות מחשבים ומקודדים מראש (החישובים מופיעים בתיאור האלגוריתם על ידי המחברים, ערכי הטבלאות מופיעים באתר NIST בתקן 197) ואז אפשר להמיר את טרנספורמציות הסבב לפעולה הבאה:
אפשר לראות שהפעולה מורכבת מארבע פעולות חיפוש בטבלה וארבע פעולות XOR לכל עמודה בכל סבב. במחיר של שלוש הזזות נוספות בכל עמודה (בכל סבב) אפשר להחליף את הפעולה הקודמת בפעולת חיפוש בטבלה אחת בגודל אחד קילובית:
כמו כן כדי לשמור על קוד מצומצם אם נחוץ אפשר להוסיף קוד לייצור הטבלאות בזמן ריצה במקום לקודד אותן מראש. בסבב האחרון בשל העובדה שלא מבוצעת הטרנספורמציה MixColumn לא ניתן להשתמש בטבלאות  כיוון שהן חושבו כדי לכלול את הטרנספורמציה הזו. במקום ליצור טבלה מיוחדת עבור הסבב האחרון אפשר לבצע מיסוך (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);}// encryptionint 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);}// decryptionint 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 הטמיעה חברת אינטל פונקציות קריפטוגרפיות ממוטבות (IPP) בארכיטקטורת AI שתומכות ב-OpenSSL גרסה 1.0.1 ומעלה. התוצאות שנבדקו בעיקר על מעבד Xeon הגיעו לביצועים של כ-900 מגה בשנייה. (פענוח מהיר יותר ויכול להגיע ל-2.3 ג'יגה לשנייה).

ביטחון הצופן

הדרך הטובה ביותר לתקוף צופן בלוקים היא הפעלת סוגי התקפות שונות על גרסאות מצומצמות של הצופן, קרי עם מספר קטן יותר של סבבים. משמעות שבירת האלגוריתם היא בעצם מציאת כל דרך אפשרית לחשיפת המפתח, הקצרה ולו במעט מכוח גס. אם כי במרבית המקרים גם אם תמצא דרך כזו, לרוב לא תהיה מעשית ולא תטריד איש בטווח הקרוב. אך מעצם ההגדרה, מהווה נקודת תורפה שיש להתייחס אליה.
ב-2002 פותחה על ידי הקריפטוגרפים קורטויז ופייפרציק שהיה ממפתחי LOKI התקפה על AES הנקראת XSL שמסוגלת לטענתם לפרוץ את האלגוריתם מהר יותר מכוח גס באופן משמעותי. ההתקפה פועלת על ידי גזירת מערכת משוואות ריבועיות מהצופן, שהן פונקציה של הטקסט המקורי, הטקסט המוצפן והמפתח. המערכת מאוד גדולה (כ-8,000 משוואות עם כ-1,600 נעלמים במקרה של AES-128). אלימינציית גאוס מחייבת המצאות כמות מספקת של משוואות בלתי תלויות. הם הציעו פתרון באמצעות טכניקה שהמציאו לצמצום מספר הנעלמים שנקראת eXtended Sparse Linearization המסתמכת על עבודתם של שמיר וקיפניס. יתרון ההתקפה שנדרשת רק כמות מועטה של טקסטים ידועים. אולם הסתבר שהשיטה דורשת משאבים עצומים ואינה יעילה מכוח גס כפי שנטען בתחילה על ידי המפתחים, לכן נקראת תאורטית במובן זה.
במהלך התחרות לתקן המתקדם הביעו מומחים אחדים דאגה מהמבנה האלגברי הייחודי הסגור של ריינדל וכן העובדה שהוא מסתמך על הנחה שטרם הוכחה, שקשה חישובית לפתור מערכת משוואות בעלת מבנה ייחודי כזה. ברוס שנייר שפיתח את Twofish הצהיר שאינו סבור שמישהו יוכל לנצל את המבנה הייחודי הזה לצורך התקפה מעשית כנגד ריינדל.
ב-2009 פותחה על ידי בריוקוב וחובראטוביץ והלוי התקפה על כל גרסאות AES הנקראת התקפת מפתחות קשורים. התקפה מסוג זה מניחה שהתוקף מסוגל לבחור מפתחות שיש ביניהם קשר או יחס כלשהו, כגון אם מפתח אחד הוא XOR של מפתח אחר עם קבוע כלשהו. ההתקפה מתמקדת בתהליך הרחבת המפתח הפשוט יחסית של ריינדל בגרסאות AES-192 ו-AES-256 והגיעה לסיבוכיות של  וסיבוכיות מקום של . יש לזכור שמעשית היות שהמפתחות נבחרים באקראי, התקפה כזו אינה סבירה. התקפה דומה שהמציאו המפתחים האמורים יחד עם שמיר, דונקלמן וקלר, כנגד AES-256 מצליחה לחשוף את המפתח רק עם שני מפתחות קשורים, בזמן של  בתשעה סבבים,  בעשרה סבבים ו- ב-11 סבבים. אף אחת מההתקפות לא יעילה כנגד AES במלוא הסבבים.
נכון ל-2011 ההתקפה הטובה ביותר כנגד AES מלא (14 סבבים במקרה של 256 סיביות) היא של בוגדנוב, חובראטוביץ' ורכנברג. זוהי סוג של התקפת 'נפגש באמצע' הנקראת biclique והיא טובה מכוח גס בפקטור של 4 בקירוב כלומר  על כן חשיבותה תאורטית והיא אינה מסכנת את השימוש בצופן ריינדל מבחינה מעשית.

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

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