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

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

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

אטימולוגיה

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

היסטוריה

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

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

השיטה

קריפטואנליזה דיפרנציאלית בגרסה הבסיסית מנצלת את ההסתברות הגבוהה של מופעים מסוימים של דיפרנציאלים בין זוגות בלוקים בפלט הצופן (ליתר דיוק בקלט לסבב האחרון של הצופן) בהינתן דיפרנציאלים של בלוקים גלויים מסוימים בקלט הצופן. המושג דיפרנציאל פירושו שאם למשל נתונה פונקציה $F$ המקבלת קלט $X$ באורך $n$ סיביות; $X=[X_{1}X_{2}...X_{n}]$ ומפיקה פלט $Y=[Y_{1}Y_{2}...Y_{n}]$. אם נסמן שני קלטים אפשריים לפונקציה ב-$X'$ ו-$X''$ בהתאמה וכן הפלטים המתאימים להם ב-$Y'$ ו-$Y''$ בהתאמה, כלומר $Y'=F(X')$ וכן $Y''=F(X'')$. אז הדיפרנציאל של הקלט (או ההפרש) הוא $\Delta X=X'\oplus X''$ כאשר הסימן $\oplus$ מייצג חיבור XOR של וקטורים באורך $n$ סיביות. לכן,

$\Delta X=[\Delta X_{1},\Delta X_{2},...,\Delta X_{n}]$, כאשר $\Delta X_{i}=X_{i}'\oplus X_{i}''$.

האיברים $X_{i}'$ ו-$X_{i}''$ מייצגים את הסיביות במיקום ה-$i$ של $X'$ ו-$X''$ בהתאמה. באופן דומה $\Delta Y=Y'\oplus Y''$ הוא הדיפרנציאל של הפלט ולכן

$\Delta Y=[\Delta Y_{1},\Delta Y_{2},...,\Delta Y_{n}]$, כאשר $\Delta Y_{i}=Y_{i}'\oplus Y_{i}''$.

בצופן אידיאלי המתנהג באופן אקראי לגמרי, ההסתברות שדיפרנציאל פלט מסוים $\Delta Y$ יופיע בהינתן דיפרנציאל קלט מסוים $\Delta X$ אמורה להיות $1/2^{n}$ כאשר $n$ מייצג את מספר הסיביות של $X$. אולם במציאות אין זה כך ולכן הקרפיטואנליזה הדיפרנציאלית מחפשת את המקרים בהם דיפרנציאל פלט מסוים מופיע בשכיחות גבוהה יותר בהינתן דיפרנציאל קלט מסוים. אם ההסתברות הדיפרנציאלית של הצופן שמקובל לסמנה ב-$p_{D}$ גבוהה באופן משמעותי מ-$1/2^{n}$ אפשר יהיה באמצעותה לפצח את הצופן.

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

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

$x\oplus k\oplus y\oplus k=x\oplus y\oplus k\oplus k=x\oplus y\oplus 0=x\oplus y$.

תיבות ההחלפה

בכל צופן בלוקים במבנה רשת החלפה תמורה כמו 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 סיביות: $X=[X_{1}X_{2}X_{3}X_{4}]$ ומחזירה פלט באורך 4 סיביות: $Y=[Y_{1}Y_{2}Y_{3}Y_{4}]$ מתוך $2^{n}=16$ ערכים אפשריים, לפי הטבלה. לדוגמה אם הקלט הוא $1100$ או בבסיס הקסדצימלי ${\text{0xC}}$ הפלט צריך להיות $0101$ או ${\text{0x5}}$. אפשר לרשום זאת כסדרה של פונקציות: $F({\text{0xC}})={\text{0x5}}$ או $F({\text{0x2}})={\text{0xD}}$ וכן הלאה. אם רושמים את כל הדיפרנציאלים של זוגות אפשריים של קלט/פלט לתיבת ההחלפה הזו ההסתברות של $\Delta Y$ בהינתן $\Delta X$ עבור זוג מסוים $X',X''$ וכן $Y',Y''$ מתקבלת על ידי ספירת כל המופעים שלהם חלקי $2^{n}$. היות שהסדר אינו חשוב ויש רק 4 סיביות, במילים אחרות 16 אפשרויות לכן אפשר לרשום את כל 16 הערכים האפשריים של $X'$ ולהגביל את $X''$ שיהיה $X''=X'\oplus \Delta X$. ואז לחשב את ערכי $\Delta Y$ עבור כל זוג קלט ($X',X''=X'\oplus \Delta X$) אפשרי. את כל זה אפשר לסכם בטבלה, את הערכים הבינאריים של הקלט $X$, הפלט $Y$ וכן ערכי $\Delta X$ ו-$\Delta Y$ עבור ערכי $X',X''$. לדוגמה, הטבלה הבאה מכילה חלק מהנתונים הללו עבור תיבת ההחלפה המתוארת. אפשר לראות שאם $\Delta X=1011$ אז $\Delta Y=0010$ מופיע בשמונה מתוך 16 המקרים האפשריים, דהיינו בהסתברות של 8/16. כמו כן אם $\Delta X=1000$ אז $\Delta Y=1011$ בהסתברות של 4/16. כמו כן רואים שבמקרה ש- $\Delta X=0100$ אז $\Delta Y=1010$ לא מופיע אף פעם (הסתברות אפס). אילו תיבת ההחלפה הייתה אידיאלית אז כל הערכים בטבלה היו אמורים להופיע בהסתברות של $1/2^{n}=1/16$ אולם מסתבר שמצב כזה בלתי אפשרי מבחינה מתמטית, כלומר לא קיימת תיבת החלפה באורך 4 סיביות שהדיפרנציאלים שלה הם $1/16$ עבור כל המופעים.

X	Y	$\Delta Y$
		$\Delta X$=1011	$\Delta X$=1000	$\Delta X$=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

את כל המידע האמור מסכמים בטבלת התפלגות דיפרנציאלית שבה השורות מייצגות את $\Delta X$ והעמודות את $\Delta Y$. להמחשה מובאת טבלת ההתפלגות הדיפרנציאלית של תיבת ההחלפה של DES מהדוגמה לעיל. אפשר לראות שלמעט המקרה יוצא הדופן של $\Delta X=0,\Delta Y=0$ הערך הגבוה ביותר הוא 8 המתאים ל-$\Delta X=B$ ו-$\Delta Y=2$. לכן ההסתברות של הדיפרנציאל $\Delta Y=2$ בהינתן כל זוג אפשרי של קלט המקיים $\Delta X=B$ היא 8/16. הערך הנמוך ביותר הוא 0 שמתאים לכל המקרים בהם $\Delta Y$ אינו מופיע אף פעם בהינתן $\Delta X$. סכום כל האיברים בכל שורה בטבלה הוא $2^{n}=16$ וכן בכל העמודות. כמו כן רואים שכל הערכים זוגיים, הסיבה היא היות שהסדר אינו חשוב לכן הדיפרנציאל של $(X',X'')$ שווה לדפירנציאל של $(X'',X')$. כמו כן הערך בפינה הימנית העליונה הוא תמיד $2^{n}=16$ וכל הערכים האחרים בשורה זו ובעמודה זו הם 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 לכן התיבה $S_{31}$ פירושה תיבת ההחלפה הראשונה בסבב השלישי של הצופן. נבחן לצורך ההמחשה (כמתואר בתרשים משמאל) את מסלול הדיפרנציאלים של הסיביות במיקומים 5, 7 ו-8 של הקלט במעבר בתיבות המסומנות ב-$S_{12},S_{23},S_{32},S_{33}$ (התיבה השנייה בסבב הראשון, השלישית בסבב השני והתיבות השנייה והשלישית בסבב השלישי) וכן במעבר דרך התמורות הבאות אחריהן. יש לשים לב שהמאפיין הדיפרנציאלי המתקבל כאן הוא של שלושה סבבים בלבד ולא של מלוא ארבעת הסבבים של הצופן. כיוון שאילו תיבות ההחלפה הפעילות היחידות עבור פוזיציות אילו של הקלט, הדיפרנציאל בכל התיבות האחרות יהיה 0. נניח שהדיפרנציאלים של תיבות ההחלפה התקבלו לפי הפירוט הבא:

$S_{12}:\Delta X=B\rightarrow \Delta Y=2$ בהסתברות של $8/16$,

$S_{23}:\Delta X=4\rightarrow \Delta Y=6$ בהסתברות של $6/16$,

$S_{32}:\Delta X=2\rightarrow \Delta Y=5$ בהסתברות של $6/16$,

$S_{33}:\Delta X=2\rightarrow \Delta Y=5$ בהסתברות של $6/16$.

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

$\Delta P=\Delta U_{1}=[0000\ 1011\ 0000\ 0000]$

שהוא הדיפרנציאל הכי שכיח. $U_{i}$ מייצג את הקלט של תיבות ההחלפה בסבב ה-$i$. כמו כן $V_{i}$ מייצג את הפלט של תיבות ההחלפה בסבב ה-$i$ בהתאמה. לכן $\Delta U_{i}$ ו-$\Delta V_{i}$ מייצגים את הדיפרנציאלים שלהם בהתאמה. כתוצאה מכך $\Delta V_{1}=[0000\ 0010\ 0000\ 0000]$. אם ממשיכים בסגנון זה בונים את הדיפרנציאלים של כל סבב וסבב כך ש-$\Delta V_{i}=\Delta U_{i-1}$. כמובן שיש להביא בחשבון גם את התמורה המבוצעת בכל סבב של רשת ההחלפה תמורה (היות שהתמורה ליניארית היא משפיעה רק על מיקום הסיביות המושפעות). אם בודקים את הדיפרנציאל עבור התיבה $S_{12}$ והתמורה שאחריה מגיעים ל:

$\Delta U_{2}=[0000\ 0000\ 0100\ 0000]$

בהסתברות של $8/16$ או $1/2$ בהינתן $\Delta P$. בסבב השני הדיפרנציאל עבור התיבה $S_{23}$ הוא

$\Delta V_{2}=[0000\ 0000\ 0110\ 0000]$

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

$\Delta U_{3}=[0000\ 0010\ 0010\ 0000]$

בהסתברות של $6/16$ בהינתן $\Delta U_{2}$ או בהסתברות של $1/2\times 6/16=3/16$ בהינתן $\Delta P$. שוב, בהנחה שהדיפרנציאלים בלתי תלוים. באותה דרך אפשר לחשב את הדיפרנציאל עבור הסבב השלישי בתיבות ההחלפה $S_{32}$ ו-$S_{33}$ ולאחר התמורה השלישית ומתקבל:

$\Delta V_{3}=[0000\ 0101\ 0101\ 0000]$

וכן

$\Delta U_{4}=[0000\ 0110\ 0000\ 0110]$

בהסתברות של $(6/16)^{2}$ בהינתן $\Delta U_{3}$. אם מכפילים את כל ההסתברויות מתקבל המאפיין הדיפרנציאלי של הצופן עד נקודה זו, במקרה זה $8/16\times 6/16\times (6/16)^{2}=27/1024$ (בהינתן $\Delta P$). וזהו המאפיין הדיפרנציאלי של הצופן לאחר $R-1$ מתוך $R$ סבבים (בדוגמה זו $R=4$). כשההנחה בכל הדרך היא שהדיפרנציאלים של כל תיבות ההחלפה בכל הסבבים הם בלתי תלויים זה בזה. בשלב זה של ההתקפה על הצופן מצפינים בלוקים רבים שלהם הדיפרנציאל $\Delta P=[0000\ 1011\ 0000\ 0000]$ ואז בהסתברות גבוהה, במקרה זה $27/1024$ המאפיין הדיפרנציאלי יופיע. כל זוג שאיתו מתקבל $\Delta P$ נקרא זוג נכון וכל זוג אחר שבו המאפיין האמור אינו מתקבל נקרא זוג לא נכון.

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

בנוסף אפשר לייעל את ההתקפה אם לא כל תיבות ההחלפה משפיעות על הקלט. למשל בדוגמה המובאת רק שתי תיבות משפיעות על הנתונים של הצופן בסבב השלישי, לכן, היות שהדיפרנציאל של הקלט לסבב האחרון עבור זוג נכון הוא אפס בשתי התיבות האחרות (הלא פעילות), אפשר לפשוט להתעלם מכל הזוגות שבהן לא מופיעים אפסים בדיפרנציאל המתאים לפוזיציות בתיבות אילו. בדוגמה המובאת אפשר לפצח את הצופן בעזרת התהליך המתואר על ידי 5000 זוגות של קלט/פלט נבחרים, דהיינו 10000 הצפנות עם זוגות קלט שהדיפרנציאל שלהם הוא $\Delta P=[0000\ 1011\ 0000\ 0000]$. וסיביות היעד הנכונות הן במקרה זה $[K_{5,5}...K_{5,8},K_{5,13}...K_{5,16}]=[0010,0100]=[{\text{0x2}},{\text{0x4}}]$. בדוגמה זו המאפיין הדיפרנציאלי של הצופן הוא $27/1024=0.0264$ ובניסוי ותהיה התגלה שסיביות היעד הנכונות הניבו תוצאה של $0.0244$ שזה די קרוב.

יעילות

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

$N_{D}\approx c/p_{D}$.

כאשר $p_{D}$ הוא המאפיין הדיפרנציאלי של הצופן אחרי $R-1$ סבבים ו-$c$ הוא קבוע קטן. בהנחה שהדיפרנציאלים של תיבות ההחלפה בלתי תלויים זה בזה, הסתברות המאפיין הדיפרנציאלי של הצופן נתונה על ידי:

$p_{D}=\prod _{i=1}^{\gamma }\beta _{i}$

$\gamma$ מייצג את מספר התיבות הפעילות והסתברות הדיפרנציאל של זוג מסוים בתיבה הפעילה ה-$i$ מיוצגת על ידי $\beta _{i}$. הביטוי האחרון מעיד על כך שמספר מועט של מופעים של זוגות נכונים מספיק כדי לתת מונה גבוה של סיביות יעד וכן מונה זה גבוה הרבה יותר מהמונה עבור זוגות לא נכונים. זוג נכון אמור להופיע בהסתברות של $1/p_{D}$ זוגות. לכן בפועל מספיקה כפולה קטנה של $1/p_{D}$ כדי להצליח בהתקפה הדיפרנציאלית על הצופן.

וריאציות

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

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

עמידות של צפנים

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

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

ראו גם

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

לקריאה נוספת

• Eli Biham, Adi Shamir, Differential Cryptanalysis of the Data Encryption Standard, Springer Verlag, 1993. ISBN 0-387-97930-1, ISBN 3-540-97930-1.
• Eli Biham, Adi Shamir,"Differential Cryptanalysis of the Full 16-Round DES", Proceedings of CRYPTO '92, Volume 740 of Lecture Notes in Computer Science, December 1991.