Advanced Encryption Standard

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

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

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

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

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

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

Eas table.jpg

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

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


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

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

אלגוריתם הרחבת המפתח של AES משתמש במפתח ההצפנה הראשוני כדי להפיק מפתחות סבב עבור כל סבבי ההצפנה. כל מפתח סבב בגודל ארבע מילים בהתאם למספר עמודות טבלת המצב (מיוצג על ידי  Nb), סך כל המילים הדרושות הוא כמספר הסבבים כפול מספר העמודות (ליתר דיוק Nb(Nr + 1)). לדוגמה עבור מפתח 128 סיביות בעשרה סבבים סך כל מילות המפתח המורחב הן 44 מילות שהן 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.

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

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

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

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

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

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

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


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

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