Advanced Encryption Standard

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

תקן הצפנה מתקדם (AES) הידוע גם בשמו ריינדל (Rijndael), הנו צופן בלוקים שאומץ כתקן הצפנה סימטרית הרשמי של ממשלת ארצות הברית המחליף את DES. אלגוריתם AES אומץ בנובמבר 2001 על ידי NIST המכון הלאומי לתקנים ולטכנולוגיה של ממשלת ארצות הברית תחת תקן FIPS PUB 197 לאחר תהליך בחינה שנמשך כחמש שנים, במהלכן נבחנו מספר מועמדים טובים. AES נמצא כיום בעיצומו של תהליך הפצה בקנה מידה גדול וההערכה היא שהצופן יופץ מסביב לעולם וייבחן בעיון רב על ידי מומחים רבים כפי שקרה עם קודמו.

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

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

• שכבת ערבוב לינארי (Linear mixing layer) - שתפקידה להבטיח הפצה רוחבית מקסימלית של כל סיביות המצב.
• שכבה לא לינארית (Non-linear layer) - שמערבלת את כל סיביות המצב באופן מקבילי, באמצעות תיבות החלפה/תמורה בעלות תכונת אי-לינאריות גבוהה.
• שכבת הוספת מפתח (Key addition layer) - כשמה, מוסיפה חלק ממפתח ההצפנה לתוצאת הביניים באמצעות XOR.

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

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

רוב החישובים של AES הם בשדות סופיים ומתבצעים במספר סבבים (לכל היותר 14 בהתאם לגודל המפתח) כאשר כל סבב מורכב מארבעה שלבים הקרויים טרנספורמציות המצב. מצב (State) מתאר את גוש המידע הנוכחי כמערך בתים דו-ממדי המורכב מארבעה שורות ומספר עמודות שהוא גודל הגוש חלקי 32 (עבור גושי מידע של 256 סיביות יהיו 8 עמודות). באופן דומה מיוצג גם המפתח המופק בתהליך הרחבת מפתח בכל שלב ונקרא מפתח-סבב. התהליכים הבאים מבוצעים על טבלת המצב כדלהלן:

טבלת החלפה של AES

1. SubBytes

תהליך החלפה לא לינארי של בתי המצב המתבצע על כל בית בנפרד, תוך שימוש בטבלת החלפה סטטית המכונה S-box (ראו תרשים) ובפענוח משתמשים בטבלה ההופכית.

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

2. ShiftRows

תהליך הזזה מחזורית Cyclic Shift או Rotate, שבה שורות טבלת המצב מוזזות בהיסטים שונים לפי ערכים קבועים כלשהם, בתנועה מחזורית. השורה הראשונה (שורה 0) נותרת ללא שינוי, שורה 1 מוזזת לפי הקבוע C1, שורה 2 לפי הקבוע C2 ושורה 3 לפי הקבוע C3. ערכי הקבועים C1, C2, C3 תלויים בגודל הגוש.

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

3. MixColumns

תהליך טרנספורמציה לינארית, שבו מתייחסים לכל עמודות המצב כפולינומים מעל השדה המורחב $\ \mathbb{F}_ {2^8}$. כל העמודות מוכפלות בפולינום הקבוע $\ c(x)= 3x^3 + x^2 + x + 2$ ומצומצמות מודולו הפולינום $\ x^{4}+1$ (בפענוח ההכפלה מתבצעת בפולינום $\ d(x)= 11x^3 + 13x^2 + 9x + 14$ ההופכי של $\ c(x)$).

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

4. AddRoundKey

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

תהליך הרחבת מפתח

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

1. for i = 0 to keys -1
  1.1 W[i]=(Key[4*i],Key[4*i]+1,Key[4*i]+2,Key[4*i]+3)
 
2. for i=keys to columns * (rounds + 1) -1
  2.1 temp=W[i-1]
  2.2 if i mod Nk = 0 then
    2.2.1 temp=SubBytes(ShiftRows(temp)) XOR Rcon[i/keys]
  2.3 W[i]=W[i-keys] XOR temp

להלן פסבדו קוד המתאר את מהלכי אלגוריתם AES, מהלכים 1 עד 4 המתוארים לעיל, מבוצעים בלולאה הראשית שורות 4.1 עד 4.4, היות שהסבב האחרון שונה מיתר הסבבים, הוא מבוצע בנפרד לאחר הלולאה הראשית. שים לב שטרנסופרמציה 3 לא מבוצעת בסבב זה:

AES(byte in[4*columns],
    byte out[4*columns],
    word w[columns*(rounds+1)])
 
1. byte state[4, columns]
2. state=in
3. AddRoundKey(state, w[0,columns-1])
4. for round=1 to rounds-1
  4.1 SubBytes(state)
  4.2 ShiftRows(state)
  4.3 MixColumns(state)
  4.4 AddRoundKey(state, w[round*columns, (round+1)*columns-1])
5. SubBytes(state)
6. ShiftRows(state)
7. AddRoundKey(state, w[rounds*columns, (rounds+1)*columns-1])
8. out=state

מיטוב הצופן

במעבדי 32 סיביות או יותר שבהם יש זיכרון רב, ניתן להאיץ את ביצוע הצופן בהמרת התהליכים האמורים לעיל לטבלאות חיפוש table lookup שיחד עם חיבור בינארי (XOR) וכן פעולות הזזה shift המובנות בשפות התכנות הנפוצות כמו C, מאפשרות האצת ביצועים תוך שמירה על פורטביליות רבה. כמו כן ניתן ליישם את הצופן גם במערכות מוגבלות כמו מעבדי 8 סיביות ובחומרה גם בתנאים בהם הזיכרון מוגבל. ניתן ליישם את AES בשבבים ולבצע פעולות אלגבריות בשדות סופיים בעזרת XOR, הזזה Shift והזזה מחזורית Rotate.

בטיחות הצופן

ה-NSA סקר את כל המועמדים שעלו לגמר בתהליך בחירת סטנדרט ההצפנה החדש: MARS, RC6, Rijndael, Serpent, Twofish. והצהיר כי כולם בטוחים לשימוש עבור ממשלת ארצות הברית להצפנת מידע לא מסווג. ב-2003 הכריזה ממשלת ארצות הברית כי ניתן לעשות שימוש ב-AES להצפנת מידע מסווג עבור הממשל עם מפתח 128 סיביות, מלבד מידע מסווג בדרגה העליונה ביותר (Top Secret) שעבורו נדרש מפתח בגודל של 256 סיביות לכל הפחות. על כל פנים, כל מוצר המיועד להצפנת מידע עבור הממשל נבדק ומאושר על ידי ה-NSA. בכך למעשה לראשונה נחשף הציבור לאלגוריתם הצפנה בטוח שנבחן ואושר על ידי מומחי ממשל בכירים.

הדרך הטובה לתקוף צופן בלוקים היא הפעלת סוגי התקפות שונות על גרסאות מצומצמות של הצופן, קרי עם מספר קטן יותר של סבבים. למעשה ההתקפה הטובה ביותר, הצליחה על AES עם 7 עד 9 סבבים בהתאם לגודל המפתח, בקירוב. מספר הסבבים של AES הוא, 10 סבבים עבור מפתח 128 סיביות, 12 סבבים עבור מפתח 192 סיביות ו-14 סבבים עבור מפתח 256 סיביות. כך שמספר הסבבים מהווה מרווח ביטחון מספק לדעת רבים. משמעות שבירת אלגוריתם AES היא בעצם מציאת כל דרך אפשרית לחשיפת המפתח, הקצרה ולו במעט מחיפוש ממצה. אם כי במרבית המקרים גם אם תמצא דרך כזו, לרוב לא תהיה מעשית ולא תטריד איש בטווח הקרוב. אולם מעצם ההגדרה, מהווה בהחלט נקודת תורפה שיש להתייחס אליה. נכון להיום לא נמצאה דרך כזו באשר ל-AES.

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

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

Side channel attack

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

מקורות

• אתר NIST, אלגוריתם AES (ריינדל)
• אתר המחברים
• מתקפת תזמון על AES

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

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