קריפטואנליזה דיפרנציאלית

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

בקריפטואנליזה, קריפטואנליזה דִּיפֵרֶנְצִיָּלִית (באנגלית: Differential cryptanalysis) היא סוג של קריפטואנליזה גנרית המתאימה בעיקר לניתוח צופן בלוקים אך גם צופן זרם ופונקציות גיבוב. באופן תמציתי היא פועלת על ידי ניתוח השפעת דיפרנציאלים של קלט פונקציית הצפנה סימטרית על דיפרנציאלים של הפלט שלה. במקרה של צופן בלוקים קריפטואנליזה דיפרנציאלית מתייחסת לאוסף של טכניקות לגילוי דיפרנציאלים בעלי הסתברות גבוהה המלמדים על התנהגות לא ראנדומלית של הצופן שבהם אפשר להיעזר כדי לנחש את המפתח הסודי. דיפרנציאל בהקשר של קריפטוגרפיה פירושו הפרש או הבדל בין זוג קלטים אפשריים של הצופן בדרך כלל מעל פעולת XOR.

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


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

המילה "קריפטואנליזה" היא הלחם של המילים קריפטוגרפיה ואנליזה, שפירושה "נִתּוּחַ". המילה דיפרנציאל משמעותה "הֶפְרֵשׁ" או "הֶבְדֵּל".

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

הראשונים לפרסם את הקריפטואנליזה הדיפרנציאלית היו עדי שמיר ואלי ביהם בסוף שנות ה-80[1] והיא נחשבת להתקפה הקריפ]טוגרפית הותיקה ביותר הידועה. שמיר וביהם פרסמו מספר התקפות קריפטוגרפיות שהשתמשו בשיטה זו ובהן חולשה בפרוטוקול DES ששימש באותה תקופה כתקן ההצפנה של ממשלת ארצות הברית. בשנת 1994, פרסם דון קופרסמית', ממפתחי DES, מאמר בו טען שקריפטואנליזה דיפרנציאלית הייתה ידועה למפתחי DES ב-IBM כבר משנת 1974‏[2]. לאחר שמדעני IBM גילו את הקריפטואנליזה דיפרנציאלית שנקראה בפיהם בשם הקוד "התקפת דיגדוג" (Tickle Attack)[3], הם עידכנו את אנשי ה-NSA ובעצה אחת החליטו שני הגופים לשמור את דבר קיום השיטה בסוד כדי לשמור על היתרון הטכנולוגי של ארצות-הברית בתחום הקריפטאנליזה.

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

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

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

, כאשר .

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

, כאשר .

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

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

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

.

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

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

קלט 0 1 2 3 4 5 6 7 8 9 A B C D E F
פלט E 4 D 1 2 F B 8 3 A 6 C 5 9 0 7

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

X Y
=1011 =1000 =0100
0000 1110 0010 1101 1100
0001 0100 0010 1110 1011
0010 1101 0111 0101 0110
0011 0001 0010 1011 1001
0100 0010 0101 0111 1100
0101 1111 1111 0110 1011
0110 1011 0010 1011 0110
0111 1000 1101 1111 1001
1000 0011 0010 1101 0110
1001 1010 0111 1110 0011
1010 0110 0010 0101 0110
1011 1100 0010 1011 1011
1100 0101 1101 0111 0110
1101 1001 0010 0110 0011
1110 0000 1111 1011 0110
1111 0111 0101 1111 1011
Diff crypt example-01.png

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

0 1 2 3 4 5 6 7 8 9 A B C D E F
0 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 2 0 0 0 2 0 2 4 0 4 2 0 0
2 0 0 0 2 0 6 2 2 0 2 0 0 0 0 2 0
3 0 0 2 0 2 0 0 0 0 4 2 0 2 0 0 4
4 0 0 0 2 0 0 6 0 0 2 0 4 2 0 0 0
5 0 4 0 0 0 2 2 0 0 0 4 0 2 0 0 2
6 0 0 0 4 0 4 0 0 0 0 0 0 2 2 2 2
7 0 0 2 2 2 0 2 0 0 2 2 0 0 0 0 4
8 0 0 0 0 0 0 2 2 0 0 0 4 0 4 2 2
9 0 2 0 0 2 0 0 4 2 0 2 2 2 0 0 0
A 0 2 2 0 0 0 0 0 6 0 0 2 0 0 4 0
B 0 0 8 0 0 2 0 2 0 0 0 0 0 2 0 2
C 0 2 0 0 2 2 2 0 0 0 0 2 0 6 0 0
D 0 4 0 0 0 0 0 4 2 0 2 0 2 0 2 0
E 0 0 2 4 2 0 0 0 6 0 0 0 0 0 2 0
F 0 2 0 0 6 0 0 0 0 4 0 2 0 0 2 0


היות שהצופן מכיל בדרך כלל מספר תיבות החלפה שונות וכן מספר סבבים כאשר בכל סבב מופעלות תיבות החלפה אחרות, יש צורך לסכם את הדיפרנציאלים של כל תיבות ההחלפה הפעילות באותה דרך ואז לשלב את הדיפרנצאלים של הזוגות בכולן כדי לקבל את "המאפיין הדיפרנציאלי" של הצופן. כשאומרים תיבת החלפה פעילה מתכוונים לתיבת החלפה שדיפרנציאל הפלט שלה אינו בהסתברות אפס. למרות שמפתח ההצפנה שונה מתיבה לתיבה ומסבב לסבב אפשר להוכיח באופן ישיר שכאשר הדיפרנציאל הוא מעל XOR אין למפתח כל השפעה על דיפרנציאלים של הזוגות, בגלל התכונה המהותית של פעולה זו שהיא הופכית של עצמה ולכן אם ערך מסוים מופיע פעמיים הוא מתבטל. כדי להדגים את חישוב המאפיין הדיפרנציאלי של הצופן נניח למען הפשטות שקיימות 4 תיבות החלפה וישנם ארבעה סבבים בסך הכול וקלט הצופן הוא בלוק באורך 16 סיביות (כל תיבה מקבלת 4 סיביות ממנו). למען הנוחות כל תיבה מסומנת במספר מ-1 עד 4 וכל סבב מסומן בהתאם מ-1 עד 4 לכן התיבה פירושה תיבת ההחלפה הראשונה בסבב השלישי של הצופן. נבחן לצורך ההמחשה (כמתואר בתרשים משמאל) את מסלול הדיפרנציאלים של הסיביות במיקומים 5, 7 ו-8 של הקלט במעבר בתיבות המסומנות ב- (התיבה השנייה בסבב הראשון, השלישית בסבב השני והתיבות השנייה והשלישית בסבב השלישי) וכן במעבר דרך התמורות הבאות אחריהן. יש לשים לב שהמאפיין הדיפרנציאלי המתקבל כאן הוא של שלושה סבבים בלבד ולא של מלוא ארבעת הסבבים של הצופן. כיוון שאילו תיבות ההחלפה הפעילות היחידות עבור פוזיציות אילו של הקלט, הדיפרנציאל בכל התיבות האחרות יהיה 0. נניח שהדיפרנציאלים של תיבות ההחלפה התקבלו לפי הפירוט הבא:

בהיסתברות של ,
בהיסתברות של ,
בהיסתברות של ,
ביהסתברות של .

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

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

בהסתברות של או בהינתן . בסבב השני הדיפרנציאל עבור התיבה הוא

ואחרי התמורה של הסבב השני מתקבל:

בהסתברות של בהינתן או בהסתברות של בהינתן . שוב, בהנחה שהדיפרנציאלים בלתי תלוים. באותה דרך אפשר לחשב את הדיפרנציאל עבור הסבב השלישי בתיבות ההחלפה ו- ולאחר התמורה השלישית ומתקבל:

וכן

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

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

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

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

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

.

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

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

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

מאז המצאת הקריפטואנליזה הדפירנציאלית הראשונה על ידי ביהם ושמיר, פותחו מספר וריאציות והרחבות שלה. ב-1993 הציע אלי ביהם קריפטואנליזה דיפרנציאלית חדשה המבוססת על מפתחות קשורים. כלומר התקפה שמניחה כי קיים בין מספר מפתחות הצפנה קשר או יחס כלשהו. ב-1994 המציא לארס קנודסן את הדיפרנציאלים החתוכים וכן דיפרנציאלים מסדר גבוה. קנודסן ודויד וגנר המציאו את הקריפטואנליזה האינטגרלית וב-1998 פיתחו ביהם, אלקס בריוקוב ושמיר את קריפטואנליזה של דיפרנציאלים בלתי אפשריים. ב-1999 פיתחו וגנר וקנודסן את התקפת בומרנג ששונתה ב-2001 על ידי ביהם, נתן קלר ואור דונקלמן להתקפת מלבן. התקפות מפתחות קשורים המנצלות חולשות בתהליך הכנת המפתח ניתנות לשילוב עם סוגים אחרים של התקפות דיפרנציאליות. להלן רשימה של התקפות דיפרנציאליות ידועות:

  • קריפטואנליזה של דיפרנציאלים חתוכים[5]. בהתקפה זו בדומה לקריפטואנליזה דיפרנציאלית רגילה משווים את ההסתברות של דיפרנציאלים של קלט/פלט אך בניגוד אליה רק של חלק מהדיפרנציאל נבדק.
  • קריפטואנליזת דיפרנציאלים בלתי אפשריים[6]. בשיטה זו מתמקדים בדיפרנציאלים שלא מופיעים בכלל. כלומר בתהליך ניפוי שוללים את כל המפתחות האפשריים אם הם מניבים בהצפנת טקסט מסוים דפירנציאלים שלא אמורים להופיע לפי התחזיות.
  • קריפטואנליזה אינטגרלית (או התקפת ריבוע)[7]. זוהי סוג של התקפה דפירנציאלית שמתאימה במיוחד לצופן בלוקים שהוא פונקציה חד-חד-ערכית ועל כמו AES והיא פועלת על זוגות קלט פלט שחלק מהם קבוע וחלק משתנה.
  • קריפטואנליזה דיפרנציאלית מסדר גבוה[8]. זוהי קריפטואנליזה הישימה נגד צפנים שניתנים לביטוי על ידי פונקציות בוליאניות עם משתנים מרובים.
  • התקפת בומברנג (התקפת מלבן)[9][10]. התקפה זו קוראת תיגר על ההנחה שאם הצופן אינו מכיל דיפרנציאלים גבוהים מאוד או נמוכים מאוד הוא נחשב בטוח. ההתקפה מתייחסת אל הצופן כאל שני צפנים המחוברים בקסקדה (כמו הצפנה מרובה) ומחפשת דיפרנציאלים בהסתברות גבוהה של שני תתי-הצפנים ואז מנסה לאחד בין שני הדיפרנציאלים במבנה כלשהו. בגרסה המשופרת של ההתקפה הנקראת התקפת מלבן מנסים לאחד בין מספר דיפרנציאלים בכל תת-צופן.
  • התקפת מפתחות קשורים[11]. קריפטואנליזה שבה באפשרות המתקיף לבדוק את התנהגות הצופן בהינתן מספר מפתחות שונים שאינם ידועים לו, אך יש ביניהם קשר מתמטי כלשהו.

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

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

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

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

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

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

  1. ^ Biham, E. and A. Shamir, "Differential Cryptanalysis of DES-like Cryptosystems", Advances in Cryptology – CRYPTO '90, Springer-Verlag, 1990.
  2. ^ Coppersmith, Don (מאי 1994). "The Data Encryption Standard (DES) and its strength against attacks" (PDF). IBM Journal of Research and Development 38 (3): 243.  (subscription required)
  3. ^ Cryptanalysis of GOST
  4. ^ A Tutorial on Linear and Differential Cryptanalysis
  5. ^ L. Knudsen, "Truncated and higher order differentials", in In B.Preneel,editor, FSE, LNCS 1008, pp.196-211, Springer-verlag (1995).
  6. ^ E. Biham, A. Biryukov, A. Shamir, "Cryptanalysis of Skipjack Reduced to 31 Rounds using Impossible Differentials", in Advances in Cryptology: EUROCRYPT'99 LNCS 1592, pp. 12-23, Springer Verlag (1999).
  7. ^ L. Knudsen, D. Wagner, "Integral Cryptanalysis (Extended Abstract)", in FSE 2002, LNCS 2365, pp.112-127, Springer-Verlag (2002).
  8. ^ Lai, Xuejia (1994). "Higher Order Derivatives and Differential Cryptanalysis". Communications and Cryptography. Springer US. 276: 227–233
  9. ^ D. Wagner, "The Boomerang Attack", in Fast Software Encryption, FSE'99 (L. R.Knudsen, ed.) Springer-Verlag, vol. 1636 of Lecture Notes in Computer Science,p. 156-170 (1999).
  10. ^ E. Biham, O. Dunkelman, N. Keller, "The Rectangle Attack - Rectangling the Serpent", EUROCRYPT 2001 LNCS,, vol. 2045, pp. 340-357, Springer, Heidelberg (2001).
  11. ^ E. Biham, "New Types of Cryptanalytic Attacks Using Related Keys", Journal of Cryptology, vol. 7, no. No. 4, p. 229{246, Springer-Verlag (1994).