Advanced Encryption Standard

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

תהליך בחירת התקן[עריכת קוד מקור | עריכה]

בתקן הישן שהתקבל ב-1977, שימש DES במשך שנים רבות את המגזר הפרטי והעסקי כצופן סימטרי להצפנת מידע לא מסווג, בעיקר כמויות גדולות של מידע פיננסי. אולם עקב ההתקדמות הטכנולוגית והופעתם של התקפות קריפטוגרפיות משופרות ובמיוחד בשל מפתח ההצפנה הקצר שלו (רק 56 סיביות) שגרם להיותו פגיע להתקפת כוח גס (גרסת DES משולש סיפקה אמנם ביטחון רב יותר אולם הרבה פחות יעילה), הוחלט להחליפו באלגוריתם חדש, בטוח ומהיר יותר. תהליך קבלת ההחלטות ושיקולי הפיתוח של התקן הקודם היו רחוקים מעין הציבור מה שהוביל לחרושת שמועות ש-NSA התערב בפיתוח DES כדי להחלישו במכוון. רבים אף הביעו חשש שהוחדרה בו דלת אחורית. בשל כך, לבחירת התקן החדש נקטה הוועדה בגישה יותר שקופה והוחלט על תחרות פתוחה לציבור. התחרות זכתה לשבחים רבים במיוחד מצד אילו שחששו מדלת האחורית. תנאי הסף לפתיחת התחרות פורסמו בתחילת 1997 - בין היתר הדרישה שגודל הבלוק יהיה לפחות 128 סיביות וכן שמפתחות ההצפנה יהיו בטווח 128-256 סיביות. התחרות נמשכה כחמש שנים, בתחילה הוצעו כחמשה עשר מועמדים על ידי מפתחים מרחבי העולם, מתוכם כחמשה התגלו חלשים להתקפות מסוימות ונפסלו. ההצעות נבחנו על ידי מומחי הצפנה רבים לא רק מהיבט של בטיחות, גם יעילות וקלות יישום הן בחומרה והן בתוכנה. באוגוסט 1998 התקיימה הועידה הראשונה AES1 ולאחר סינון שנמשך כשנה הוכרזו בוועידה AES2 שהתקיימה באוגוסט 1999, חמשת המועמדים המובילים שעלו לשלב הגמר. מועמדים אלה הוצעו על ידי גופים מוערכים בעלי ידע וניסיון קריפטוגרפי רב ונבחנו היטב על ידי מומחים רבים. האלגוריתמים דורגו לפי ניקוד שניתן להם בקטגוריות השונות, ביטחון, יעילות, קלות יישום והטמעה בחומרה. בסבב השלישי והאחרון, בוועידת AES3 שהתקיימה בנובמבר 2000 הוכרז אלגוריתם ריינדל כמנצח של התחרות והוכרז כתקן ההצפנה המתקדם. ארבעת המועמדים האחרים שעלו לגמר בסדר יורד לפי דירוג הוועדה, הם:

במהלך התחרות הוכרז על ידי המארגנים שלא נמצאו באף אחד מהפיינליסטים חולשות כלשהן. הסברה הייתה לפני עשור שהתקפה מעשית כנגד האלגוריתמים המנויים עם מפתח 128 סיביות, לא סבירה בטווח של כחמש/עשר שנים. ההגדרה של התקפה מעשית נתונה לשינויים בהתאם ליכולת טכנולוגית, הערכות שניתנו על ידי מומחים‏[2] לפני כעשור, הגדירו התקפה מעשית ככזו שמבוצעת עם 2^{32} טקסטים ידועים (known plaintext) בסיבוכיות של 2^{70} נסיונות, כיום הועלה הרף מעט יותר, להערכת מומחים 2^{128} עדיין נחשב מחוץ להישג יד, אם כי איש לא יודע להעריך לכמה זמן. לדעת מומחים‏[3] גם אם מחשב קוונטי יהיה מעשי בטווח הקרוב, סיבוכיות התקפה כנגד האלגוריתמים המנויים באמצעות חישוב קוונטי רק תפחית את המאמץ לחצי (בכללות 2^{k/2} פעולות כאשר k אורך המפתח), כלומר מפתח 256 עדיין מותיר שולי ביטחון טובים נכון לשנת 2014 ולשנים הקרובות. יתרה מזו, קיימות טכניקות לשילוב מספר אלגוריתמים בשיטת הצפנה מרובה עם מפתחות שונים ולהגביר את הביטחון ולאילו שחוששים במיוחד לחוסנו של האלגוריתם מסוים כנגד התקפות עתידיות, אפשר להגיע לתצורה שבה הצפנה עם מספר אלגוריתמים שונים, תהיה חזקה לפחות כחוזקו של האלגוריתם החזק מביניהם. זאת בהנחה שלא סביר שתמצא דרך לשבירת כל האלגוריתמים באותה הקלות.

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

צופן ריינדל[עריכת קוד מקור | עריכה]

צופן ריינדל (השם הוא משחק שילוב שמות הממציאים) הוא שכלול צפנים ישנים שפיתחו SHARK ו-SQUARE. רוב הפעולות בצופן הן פעולות אלגבריות על בתים המייצגים אלמנטים בשדה סופי GF(2^8) (הרחבה של השדה F_2 עם מקדמים בינאריים). פעולות אחרות מוגדרות ברמת מילים בגודל 4 בתים. הסיבה לבחירת שדה זה היא תכונת האיזומורפיות. מסיבות של יעילות נבחר ייצוג פולינומי רגיל. דהיינו הבית b מתאר פולינום ממעלה 7 עם מקדמים b_i \in \{0,1\} מהייצוג הבינארי שלו b_7,...,b_0. פעולת החיבור (וכן חיסור) בין אלמנטים בשדה היא חיבור מודולו 2 של המקדמים (פעולה המקבילה ל-XOR המסומן \oplus). עם פעולה זו מתקבלת חבורה אבליאנית אסוציאטיבית וחילופית עם איבר יחידה (0) והופכי חיבורי (כל אלמנט הוא הופכי של עצמו). פעולת הכפל היא כפל ארוך בפולינומים כשהתוצאה היא שארית מחילוק בפולינום אי-פריק קבוע x^8+x^4+x^3+x+1 כך שתשאר תמיד ממעלה נמוכה מ-8. לשם הנוחות המקדמים מוצגים בבסיס הקסדצימלי לדוגמה '1B' הוא הפולינום x^4+x^3+x+1.

משיקולי יעילות רצוי לחשב כפל פולינומים בעזרת סדרה של הכפלות בפולינום x ('02' בייצוג הקסדצימלי). כיוון שמעשית פעולה זו שקולה לאופרטור ההזזה בסיביות (shift left) ופעולת חיסור מותנית (כאשר b_7=1) עם הפולינום x^4+x^3+x+1 ששקולה לאופרטור XOR. פעולות הנחשבות זולות במונחי מחשוב. לדוגמה (x^3+x+1) \cdot (x^2+1)=x^5+x^2+x+1 בייצוג הקסדצימלי \mbox{'0B'}\cdot \mbox{'05'}=\mbox{'27'} שקול לפעמיים כפל ב-x (שזה בעצם שתי הזזות שמאלה) ומתקבל x^5+x^3+x^2 או \mbox{'2C'} ואחר כך XOR אחד ומתקבל \mbox{'2C'} \oplus \mbox{'0B'}=\mbox{'27'}.

אם המקדמים הם מהשדה F_{2^8} אפשר לראות בקלט של 4 בתים כוקטור של ארבעה אלמנטים המייצג את הפולינום a_3x^3+a_2x^2+a_1x+a_0. פעולות החיבור והכפל זהות לשדה הבינארי כאשר את הכפל הארוך ממירים לסדרה של הזזות ואופרטור XOR. התוצאה במקרה של כפל היא השארית מחילוק ב-x^4+1. גם כאן הכפל בפולינום x או בחזקות שלו מקביל למעשה להזזה מעגלית (rotate) של הבתים בוקטור ולכן אפשר לתרגם את כל הפעולות לכפל במטריצות. כיוון שהפולינום איתו מכפילים קבוע אפשר להכין מראש טבלה שמייצגת את ההזזות.

שיקולי פיתוח[עריכת קוד מקור | עריכה]

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

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

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

תיאור האלגוריתם[עריכת קוד מקור | עריכה]

Eas table.jpg

ריינדל הוא צופן בלוקים איטרטיבי עם בלוק ומפתח משתנים בגודלם. ניתן להגדירם ללא תלות אחד בשני; 128, 192 או 256 סיביות (בתקן ההצפנה המתקדם גודל הבלוק נקבע ל-128). מצב ביניים של הצופן מתאר את ערכי הביניים לאחר כל סבב ונקרא בקיצור 'מצב'. המצב ניתן להצגה כמערך בתים דו ממדי בעל ארבע שורות ומספר עמודות המסומן Nb שהוא פונקציה של גודל הבלוק בסיביות חלקי 32 (ראה טבלה). באופן דומה מיוצגים בתי המפתח מארבע שורות ומספר עמודות המסומן Nk - פונקציה של אורך המפתח בסיביות חלקי 32. בחלק מהפעולות בצופן מתייחסים לבלוקים של צופן ומפתח כאל מערך של וקטורים בני ארבע בתים כאשר כל ווקטור מייצג עמודה אחת. קלט ופלט הצופן מיוצגים כמערך חד-ממדי של בתים בגודל 4\cdot Nb (דהיינו 16, 24 או 32 בתים בהתאם לגודל הבלוק - בתקן נקבע ל-16 בתים) שממופים למערך הדו ממדי לפי הסדר s_{0,0},s_{1,0},s_{2,0},s_{3,0},s_{0,1},s_{1,1},s_{2,1},s_{3,1},... וכן הלאה (ראה תרשים). באופן דומה מיוצג המפתח. מספר הסבבים מיוצג על ידי Nr ותלוי בערכים Nb,Nk (ראה טבלה).

s_{0,3} s_{0,2} s_{0,1} s_{0,0}
s_{1,3} s_{1,2} s_{1,1} s_{1,0}
s_{2,3} s_{2,2} s_{2,1} s_{2,0}
s_{3,3} s_{3,2} s_{3,1} s_{3,0}

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

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

\mbox{Round(State, RoundKey)}

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

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

הטרנספורמציה ByteSub[עריכת קוד מקור | עריכה]

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

פונקציית החלפת בתים לא לינארית הפועלת על כל בתי המצב ללא תלות אחד בשני, על פי טבלת החלפה הפיכה הנקראת S-box. טבלת ההחלפה בנויה משילוב של שתי טרנספורמציות, חישוב הופכי כפלי בשדה GF(2^8) כאשר אפס ממופה לעצמו וכן טרנספורמציה אפינית מעל השדה F_{2^8}, הנתונה בתרשים:

טבלת החלפה של AES. הערכים בייצוג הקסדצימלי

\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}

לפענוח משתמשים בטבלת ההחלפה ההופכית בסדר הפוך, דהיינו טרנספורמציה אפינית הפוכה וחישוב הופכי כפלי. ביישום האלגוריתם בפועל, במערכת בה קיים זיכרון זמין רב, מעדיפים שימוש בטבלאות חיפוש (table lookup) כדי להימנע מפעולות כפל במטריצות בזמן ריצה. בטבלת חיפוש (ראה תמונה) מקודדים את הערכים מראש ובזמן ריצה פשוט מחליפים בערך המתאים לפי אינדקס למשל אם S_{1,1}=\mbox{'53'} התוצאה תהיה הערך שנמצא בשורה 5 עמודה 3 (\mbox{'ED'}).

הטרנספורמציה ShiftRow[עריכת קוד מקור | עריכה]

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

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

הטרנספורמציה MixColumn[עריכת קוד מקור | עריכה]

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

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

\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}

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

טרנספורמצית הוספת מפתח[עריכת קוד מקור | עריכה]

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

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

פרוצדורת הרחבת מפתח[עריכת קוד מקור | עריכה]

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

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

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

  1. \mbox{temp}=W[i-1]
  2. \mbox{If } i\mbox{ mod }Nk = 0 \mbox{ then}
    \mbox{temp = SubByte(RotByte(temp))} \oplus \mbox{ Rcon}[i / Nk]
  3. W[i]=W[i-Nk] \oplus \mbox{temp}

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

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

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

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

\mbox{Else If }i\mbox{ mod }Nk = 4\mbox{ then}
\mbox{temp = SubByte(temp)}

היבטי יישום[עריכת קוד מקור | עריכה]

צופן ריינדל מתאים להטמעה ביעילות במגוון מערכות ובחומרה ייעודית כמו כרטיס חכם המצויד במעבד 8-ביט. במעבד 32 סיביות אפשר למטב את הצופן על ידי המרת ארבעת טרנספורמציות הסבב בטבלת חיפוש אחת גדולה. בנוסף כפל מטריצות ניתן לפישוט על ידי קומבינציה לינארית של וקטורים. מכינים ארבע טבלאות T_0 עד T_3 המכילות 256 מילים בגודל 4 בתים (סך הכול 4 קילובתים). את ערכי הכניסות מחשבים ומקודדים מראש (החישובים מופיעים בתיאור האלגוריתם על ידי המחברים, ערכי הטבלאות מופיעים באתר NIST בתקן 197) ואז אפשר להמיר את טרנספורמציות הסבב לפעולה הבאה:

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

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

ביצועים[עריכת קוד מקור | עריכה]

לפי בדיקות שערכו המפתחים, על גרסאות שונות של פטניום הצפנת AES על מעבד 200 MHz, צרכה כ-18 מחזורי שעון לבית שזה מקביל בערך ל-11 מגה-בית בשניה ועל מעבד פנטיום M 1.7 GHz עד 60 מגה לשניה. ב-2011 הטמיעה חברת אינטל פונקציות קריפטוגרפיות ממוטבות בארכיטקטורת AI שתומכות ב-OpenSSL גרסה 1.0.1 ומעלה. התוצאות שנבדקו בעיקר על מעבד Xeon הגיעו לביצועים של כ-900 מגה בשניה. (פענוח מהיר יותר ויכול להגיע ל-2.3 ג'יגה לשניה).

פסאודו קוד[עריכת קוד מקור | עריכה]

הרחבת מפתח
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(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

ביטחון הצופן[עריכת קוד מקור | עריכה]

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

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

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

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

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

התקפת ערוץ צדדי[עריכת קוד מקור | עריכה]

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

הערות שוליים[עריכת קוד מקור | עריכה]


מקורות[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]