Data Encryption Standard

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

Data Encryption Standard (בראשי תיבות: DES), הוא תקן הצפנת נתונים שפותח ב־1975 על ידי IBM בשיתוף פעולה עם הסוכנות לביטחון לאומי. האלגוריתם התקבל בשנת 1976 כחלק מדרישת תקן עבור הממשל האמריקאי להצפנת נתונים בעולם האזרחי ושימש בתפקיד זה עד נובמבר 2001, אז הוחלף בתקן החדש Advanced Encryption Standard, שהינו בטוח ומהיר מקודמו. למרות זאת, צופן DES עדיין נמצא בשימוש נרחב בעיקר בתחום הבנקאות.

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

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

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

הרעיון של צופן פייסטל הוא מיפוי של \ 2t סיביות של גוש טקסט קריא \ (L_i, R_i), ל-\ 2t סיביות גוש צופן באופן זה: מחלקים כל גוש לשני חלקים, צד ימין \ R וצד שמאל \ L. בכל סבב מצפינים את חלקי הגוש בנפרד ושוזרים, כלומר \ R ו-\ L מחליפים מקומות. פעולת פונקציית ההצפנה מבוצעת על שני חלקי הגוש לסירוגין, בכל סבב פלט צד ימין הופך לקלט צד שמאל וחוזר חלילה. סחרור הצופן באופן זה מחזק אותו ומקשה על פריצתו. הפענוח מתבצע באותו סדר שזירה אך עם פונקציית מפתח הפוכה.

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

תיבת תמורה סטטית ראשונית והתיבה ההופכית לה. טבלה זו נקראת Initial permutation בקיצור IP
"תיבת הרחבה" \ E ו"תיבת תמורה" \ P
DES untwisted ladder.jpg

קלט האלגוריתם הוא גוש טקסט קריא בגודל 64 סיביות ומפתח הצפנה סודי \ K בגודל 64 (בפועל 56) סיביות. תחילה באמצעות פרוצדורת הרחבת מפתח מרחיבים ומחלקים את המפתח ל-16 מקטעים בני 48 סיביות, כל אחד מהם משמש עבור סבב אחד. מכינים 8 תיבות החלפה (S-box) סטטיות \ S_1,S_2,...,S_8 המייצגות פונקציות שמחזירות פלט של 4 סיביות עבור קלט של 6 סיביות. תיבות ההחלפה מיוצגות באמצעות טבלה (ראו תרשים להלן).

מכינים "תיבת הרחבה" (\ E בתרשים) ו"תיבת תמורה" (\ P בתרשים), המייצגות פונקציות מיפוי לפי ערכים קבועים. התיבה E (קיצור של Expansion) היא תיבת תמורה/הרחבה, שתפקידה בנוסף להרחיב את הקלט מ-32 סיביות ל-48 סיביות. התיבה P (קיצור של Permutation) הנה תיבת תמורה סטטית נוספת שממירה את הקלט בסוף כל סבב תוך שמירה על גודלו - 32 סיביות. בשלב הראשון מבצעים תמורה חד פעמית על כל סיביות הקלט באמצעות תיבת תמורה סטטית הנקראת \ IP (ראו תרשים) ובסיום כל 16 הסבבים מעבירים את הפלט בתיבת התמורה ההופכית לה \ IP^{-1}. לפעולה זו אין השפעה משמעותית על בטיחות הצופן כיון שאינה תלויה במפתח ההצפנה ומקובל להתעלם ממנה כשמנתחים את הצופן. לא ברורה לגמרי הסיבה לתוספת זו, יש הסבורים כי היא נועדה להאט את האלגוריתם במכוון. כמו כן שינוי של אות אחת בטקסט המקורי מערבל לגמרי את הטקסט המוצפן. סדר הפעולות בכל הסבבים זהה. תחילה מחלקים את קלט האלגוריתם לשני חצאים \ L_0, R_0 בהתאמה ובכל סבב מבצעים כדלהלן:

\ L_i=R_{i-1},
\ R_i = L_{i-1} \oplus f(R_{i-1}, K_i)
כאשר \ f(R_{i-1},K_i)=P(S(E(R_{i-1}) \oplus K_i)).

פעולת הפונקציה \ f מתבצעת רק על מחצית הקלט (היינו 32 סיביות). המחצית השנייה מועברת לסבב הבא ללא שינוי. הפונקציה \ f מורכבת משילוב הפונקציות המתוארות: הפונקציה \ E ממפה "ומגדילה" את הקלט לפלט של 48 סיביות (כל סיבית קלט אחת משפיעה על פלט הפונקציה לפחות פעם אחת). תיבת ההחלפה S (ראו להלן) מבצעת פעולה לא-לינארית על הקלט והפונקציה \ P ממפה "ומכווצת" את הקלט לערכים בגודל 32 סיביות.

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

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

להרחבת המפתח, צופן DES משתמש בשתי טבלאות סטטיות \ PC1 ו-\ PC2 (ראו תרשימים). המפתח מורחב ל-16 גושים בני 48 סיביות כל אחד. מתעלמים מהסיביות \ (k_8,k_{16},...,k_{64}) ובאמצעות טבלה \ PC1 מחלקים את 56 הסיביות האפקטיביות לשני משתנים \ C ו-\ D בני 28 סיביות כל אחד. עבור כל סבב מבצעים הזזה מחזורית לשמאל (Rotate left) של סיביות המשתנים \ C ו-\ D בסיבית אחת או שתים (בהתאם לערך התלוי במיקום הסיביות, עבור סבבים 1,2,9,16 מזיזים ב-1 עבור היתר מזיזים ב-2) משתמשים בטבלה \ PC2 כדי לשרשר את סיביות המשתנים לגוש מפתח בגודל 48 סיביות.

אמצע

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

                        S1
14  4  13  1   2 15  11  8   3 10   6 12   5  9   0  7
 0 15   7  4  14  2  13  1  10  6  12 11   9  5   3  8
 4  1  14  8  13  6   2 11  15 12   9  7   3 10   5  0
15 12   8  2   4  9   1  7   5 11   3 14  10  0   6 13

                        S2
15  1   8 14   6 11   3  4   9  7   2 13  12  0   5 10
 3 13   4  7  15  2   8 14  12  0   1 10   6  9  11  5
 0 14   7 11  10  4  13  1   5  8  12  6   9  3   2 15
13  8  10  1   3 15   4  2  11  6   7 12   0  5  14  9

                        S3
10  0   9 14   6  3  15  5   1 13  12  7  11  4   2  8
13  7   0  9   3  4   6 10   2  8   5 14  12 11  15  1
13  6   4  9   8 15   3  0  11  1   2 12   5 10  14  7
 1 10  13  0   6  9   8  7   4 15  14  3  11  5   2 12

                        S4
 7 13  14  3   0  6   9 10   1  2   8  5  11 12   4 15
13  8  11  5   6 15   0  3   4  7   2 12   1 10  14  9
10  6   9  0  12 11   7 13  15  1   3 14   5  2   8  4
 3 15   0  6  10  1  13  8   9  4   5 11  12  7   2 14

                        S5
 2 12   4  1   7 10  11  6   8  5   3 15  13  0  14  9
14 11   2 12   4  7  13  1   5  0  15 10   3  9   8  6
 4  2   1 11  10 13   7  8  15  9  12  5   6  3   0 14
11  8  12  7   1 14   2 13   6 15   0  9  10  4   5  3

                        S6
12  1  10 15   9  2   6  8   0 13   3  4  14  7   5 11
10 15   4  2   7 12   9  5   6  1  13 14   0 11   3  8
 9 14  15  5   2  8  12  3   7  0   4 10   1 13  11  6
 4  3   2 12   9  5  15 10  11 14   1  7   6  0   8 13

                        S7
 4 11   2 14  15  0   8 13   3 12   9  7   5 10   6  1
13  0  11  7   4  9   1 10  14  3   5 12   2 15   8  6
 1  4  11 13  12  3   7 14  10 15   6  8   0  5   9  2
 6 11  13  8   1  4  10  7   9  5   0 15  14  2   3 12

                        S8
13  2   8  4   6 15  11  1  10  9   3 14   5  0  12  7
 1 15  13  8  10  3   7  4  12  5   6 11   0 14   9  2
 7 11   4  1   9 12  14  2   0  6  10 13  15  3   5  8
 2  1  14  7   4 10   8 13  15 12   9  0   3  5   6 11

תיבת ההחלפה הנקראת S-box (קיצור של Substitution box) מייצגת פונקציות החלפה אי-לינאריות. תיבות ההחלפה של DES הנן מקור בטיחותו, הפונקציות שהן מייצגות הנן הפעולות האי-לינאריות היחידות המופעלות על הקלט ואלמלא הן הצופן היה ניתן לפריצה בקלות. בדיעבד מסתבר כי התיבות עוצבו באופן כזה שהצופן יהיה עמיד יחסית כנגד התקפות דוגמת קריפטואנליזה דיפרנציאלית. עוד ידוע כי, ה-NSA היה מעורב בתכנון תיבת ההחלפה של DES ואף שינה אחדים מן הערכים המופיעים בה, בנימוק לא ידוע. יש הסבורים כי השינויים בתיבת ההחלפה נועדו להחליש את הצופן. אולם מן הדברים עולה כי הקריפטואנליזה הדיפרנציאלית כבר הייתה ידועה למתכנני הצופן.

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

DES הינו צופן סימטרי ועל כן פעולת הפענוח דומה לפעולת ההצפנה. על מנת לפענח בלוק של 64 ביטים מוצפנים, נעביר אותם במערכת ה-DES אך נבצע את תהליך ה-Round Functions בצורה הפוכה. בסוף התהליך יתקבל כפלט המידע המקורי שהוצפן.

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

הצפנה סימטרית כמו DES מכילה מטבעה בעיה מהותית והיא: הצפנה חוזרת של גושים זהים עם מפתח זהה תניב גוש מוצפן זהה. ניתן להיעזר במספר מועט של גושי צופן (שחלקם זהים) על מנת לבצע ניתוח סטטיסטי של הצופן ולחלץ בדרך זו מידע מסוים אודות טקסט המקור. הפתרון לכך הוא יישום האלגוריתם באחד ממצבי ההפעלה המבטלים את יתירות הצופן. במצב הפעלה זה המכונה "שרשור בלוקי צופן" כל בלוק של טקסט המקור, באורך 64 ביטים, עובד תהליך Xor עם תוצאת ההצפנה של הבלוק הקודם. כך שני בלוקים מקוריים זהים יובילו לפלט צופן שונה. נשים לב כי אין אפשרות לבצע Xor בין הבלוק הראשון לבלוק קודם לו. לצור כך, במצב הפעלה זה משתמשים במפתח נוסף המכונה וקטור אתחול (Initialization Vector) או IV אשר גם הוא באורך 64 ביט, ואת ה-Xor של בלוק המידע המקורי הראשון נבצע מולו.

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

התקפת כוח גס ישירה כנגד DES אינה יעילה. בהתקפה זו מנסים את כל המפתחות האפשריים על ידי הרצת אלגוריתם ההצפנה שוב ושוב עם מפתחות שונים עד שנמצא המפתח המתאים. במילים אחרות ניסוי של לפחות \ 2^{55} מפתחות אפשריים במקרה הממוצע, דהיינו מחצית מטווח המפתח. אם מעגל VLSI מסוגל לבצע הצפנת DES במהירות של 2 ג'יגה בית בשנייה (2Gbytes/sec), הרי שנדרשים לפחות כעשרים שנה כדי להשלים משימה כזו. אמנם התקפה ישירה מסוג זה בהכרח תביא בסופו של דבר להצלחה, אך לרוב אינה מעשית.

ההתקפה הבולטת הראשונה כנגד צופן DES שסיבוכיותה טובה מעט יותר מכח גס, התגלתה על ידי אלי ביהם, כיום פרופסור בטכניון, והמנחה שלו לדוקטורט עדי שמיר, כיום פרופסור במכון ויצמן למדע. הם פרסמו ב-1990 את עבודת הדוקטורט שלו שעסקה בקריפטואנליזה דיפרנציאלית כנגד DES - טכניקה רבת עוצמה היעילה כנגד אלגוריתמים סימטריים נוספים. קריפטואנליזה דיפרנציאלית מסוגלת לגלות מפתח הצפנה של DES עם \ 2^{47} דגימות קלט-פלט נבחרות של האלגוריתם בהתקפה הנקראת התקפת גלוי נבחר. אולם ההתקפה הטובה ביותר המוכרת כיום כנגד DES היא דווקא הקריפטואנליזה הלינארית. שמציעה שיפור ניכר על פני קודמתה, מלבד יכולתה לגלות מפתח DES עם \ 2^{44} קלטים, אין צורך עבורה בטקסט-מקור נבחר אלא כל טקסט אפשרי. התקפה זו נקראת התקפת גלוי-ידוע.

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

מסתבר שמתקפת כוח גס מקבילית באמצעות חומרה ייעודית, משיגה תוצאות משמעותיות הרבה יותר כנגד DES. ב-1993 טען מיכאל ויינר שאפשר לבנות בהשקעה של כמיליון דולר מכונה שתפצח את DES בתוך 3.5 שעות במקרה הממוצע. לפי התכנון המקורי שלו המכונה צריכה להכיל כ-57,000 שבבים המסוגלים להריץ את DES במקביל. מאוחר יותר נבנתה מכונה כזו הלכה למעשה ובעלות נמוכה בהרבה. הארגון Electronic Frontier Foundation בנה מכונה לשבירת צופן DES בעלות של 250,000 דולר שבאמצעותה גילוי המפתח מתבצע בתוך יומיים וחצי בקירוב. כיום ניתן בהחלט לבנות מכונות מסוג דומה במחירים נמוכים בהרבה ובזמנים טובים יותר במידה ניכרת.

התקפה אחרת כנגד DES הנקראת מתקפת יום הולדת היא התקפה אקראית מקבילית היעילה אף יותר מההתקפות המתוארות. התקפה זו מנצלת את תופעת פרדוקס יום ההולדת הידועה ומתבססת על ההנחה שהסיכויים ששני מפתחות שונים שנבחרו באקראי יניבו תוצאה זהה (עם טקסט מקור קבוע), גבוהים. Quisquater ו-Delescaille הראו שאפשר בהתקפה כזו לגלות מפתח DES ב-\ 2^{32} נסיונות במקרה הממוצע.

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

חולשתו העיקרית של DES היא גודל מפתח ההצפנה (וכן גודל הגושים). גודל המפתח האפקטיבי של DES הוא רק 56 סיביות, שמונה מתוך 64 סיביות המפתח נחשבות כסיביות זוגיות (Parity) ואינן משפיעות על ההצפנה. בעיקר בשל עובדה זו נחשב DES בימינו כ"הצפנה חלשה" ואינו בטוח לשימוש בגרסה הבסיסית. דרך בטוחה יותר וזולה ליישום DES היא איטרציה. כלומר הצפנה חוזרת של הטקסט עם מפתחות הצפנה נוספים. שיטה אחת כזו נקראת "2DES" או DES כפול. אם \ K_1,K_2 הם שני מפתחות DES שונים בגודל 56 סיביות כל אחד, ו-\ M הוא המסר המיועד להצפנה, השיטה היא:

\ \mbox{DES}2=\mbox{DES}_{K_2}(\ \mbox{DES}_{K_1}(\ M\ ))

במקרה זה מתקבל צופן DES עם מפתח הצפנה בגודל 112 סיביות. אף לא אחת מההתקפות המתוארות לעיל ישימה כנגד צופן עם מפתח בסדר גודל כזה. גם לא מתקפת כוח גס מקבילית על חומרה ייעודית. אולם מסתבר ששיטה זו פגיעה להתקפה הנקראת Meet in the Middle הדומה להתקפת יום הולדת לעיל. בהתקפה זו מנצלים זיכרון על חשבון זמן ביצוע. אם מאחסנים טבלת גיבוב של \ 2^{56} הצפנות DES עם מפתחות שונים הממוינות לפי סדר וחיפוש התנגשויות, אפשר לקצר את זמן ההתקפה ל-\ 2^{57}. כמות הזיכרון האדירה הדרושה להתקפה כזו עושה אותה כמעט בלתי ישימה באופן מעשי, אך ישנן שיטות לצמצום עלויות הזיכרון כך שאפקטיבית נאמר שגודל מפתח DES כפול אינו עולה על \ 2^{57}.

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

\ \mbox{DES}3=\mbox{DES}_{K_2}(\ \mbox{DES}^{-1}_{K_1}(\ \mbox{DES}_{K_2}(\ M\ )))

כאשר \ \mbox{DES}^{-1}_{K_1} נקרא פענוח עם המפתח \ K_1. ההתקפות המתוארות לעיל אינן ישימות כנגד שיטה זו ולמרות היותה איטית יותר היא נימצאת בשימוש נרחב כיום. כאמור בשל טכניקת Meet in the Middle, אפקטיבית גודל מפתח DES משולש הוא רק \ 2^{112} סיביות.

גרסה אחרת נקראת DESX בשיטה זו מצפינים את המידע לאחר הוספת שתי מחרוזות אקראיות בגודל 64 סיביות, כך שהמידע מוגדל ל-184 סיביות לפני ההצפנה. אם \ K הוא מפתח ההצפנה ו-\ K_1, K_2 הם מחרוזות אקראיות של 64 סיביות השיטה היא:

\ \mbox{DESX} = K_2\oplus \mbox{DES}_K(K_1\oplus M)

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

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