Advanced Encryption Standard

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

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

האלגוריתם פותח על ידי שני מומחי הצפנה בלגיים, ג'ון דאמן ווינסנט ריימן והוצג בתהליך בחירת סטנדרט ההצפנה בשם ריינדל שהוא שילוב שמות ממציאיו. ריינדל הוא שכלול פיתוחים קודמים של דאמן וריימן הקרויים Square ו-Shark. צופן ריינדל הינו צופן איטרטיבי (פונקציית ההצפנה מיושמת במספר סבבים). בתכנון האלגוריתם הושם דגש על שלושה מוטיבים עקריים: פשטות, עמידות ויעילות. בניגוד ל-DES, אינו רשת פייסטל אלא רשת החלפה-תמורה. פירושו שבניגוד לקודמו פונקציית ההצפנה אינה מיושמת רק על מחצית מגוש הקלט בכל סבב, אלא מיושמת על גוש הקלט בשלמותו. ריינדל מבוצע בשלוש שכבות כאשר בכל שכבה כל סיביות המצב מטופלות באופן זהה. תכנון השכבות נועד בעיקר להתמודד עם איום אנליזה דיפרנציאלית ואנליזה לינארית. השכבה הראשונה נקראת "שכבת ערבוב לינארי" (Linear mixing layer) תפקידה להבטיח הפצה רוחבית מכסימלית של כל סיביות המצב. השכבה השנייה קרויה "שכבה לא לינארית" (Non-linear layer), עיבוד מקבילי של כל סיביות המצב באמצעות תיבות החלפה בעלות תכונת אי-לינאריות גבוהה ככל האפשר. והשכבה השלישית נקראת "שכבת הוספת מפתח" (Key addition layer), כשמה, הוספת חלק מהמפתח לתוצאת הביניים באמצעות XOR. אלגוריתם ריינדל הינו מהיר ונוח ליישום גם בחומרה וגם בתוכנה וצורך מעט מאוד זיכרון.

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

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

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)$ ).

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

[עריכה] תהליך הרחבת מפתח

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

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

[עריכה] מיטוב הצופן

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