התקפת קורלציה

בקריפטואנליזה, התקפת קורלציה (correlation attack) היא התקפה קריפטוגרפית נגד צופן זרם שהוצעה לראשונה על ידי תומאס זיגנתאלר (Thomas Siegenthaler) ב-1985. היא המתאימה לכל צופן שהמחולל הפנימי שלו מורכב מאוגרי זיזה ממושבים (LFSR). זוהי התקפת כוח גס סטטיסטית בסגנון הפרד ומשול המתמקדת בשחזור המצב הראשוני (initial state) של האוגרים. ההתקפה בדרך כלל מתבצעת לפי מודל התקפת גלוי-ידוע, אם קיים בידי התוקף מידע מוקדם לגבי חלק מסיביות זרם המפתח. אך אפשרית גם אם לא קיים כל מידע מוקדם, בתנאי שקיימת יתירות כלשהי במסר הגלוי שהוצפן.

ההתקפה המקורית כפי שהוצגה על ידי זיגנתאלר ישימה בעיקר כנגד צופן זרם בסגנון 'מחולל משולב' הפועל באופן כזה שהסיבית הבאה של זרם המפתח היא תוצאה של פונקציית שילוב (combining function) המקבלת כקלט מספר סיביות מתוך פוזיציות מסוימות של $n$ אוגרי LFSR שאורכיהם שונים $L_{1},L_{2},...,L_{n}$ בהתאמה, משלבת אותן באופן לא ליניארי כלשהו ומחזירה סיבית אחת. אם מצליחה, ההתקפה מאפשרת שחזור מלא של שלב האתחול של המחולל בסיבוכיות של $\textstyle \sum _{i=1}^{n}(2^{L_{i}}-1)$ ניסיונות בניגוד לסיבוכיות $\textstyle \prod _{i=1}^{n}(2^{L_{i}}-1)$ הצפויה בחיפוש ממצה.

באופן כללי התקפת קורלציה אפשרית ברגע שמוצאים מתאם כלשהו בין זרם המפתח $s$ והרצף $u$ של אוטומט סופי שהמצב ההתחלתי שלו תלוי בחלק מסיביות זרם המפתח. את סיביות המפתח אפשר לחשוף על ידי שחזור המצב ההתחלתי של $u$, כל עוד אפשר לזהות 'תלות סטטיסטית' אשר יכולה לשמש סימן שהרצף עשוי להיות חלק מפלט המחולל. חיפוש ממצה בר ביצוע על ידי שבוחרים שוב ושוב רצפים אפשריים כלשהם ובודקים אם מידת הקורלציה בין הרצף $u$ לבין $s$ גבוהה מערך סף מסוים שהוא פונקציה של טווח השגיאה האפשרי. אם נמצא רצף מתאים אפשר לשחזר את המצב ההתחלתי של המחולל ומכאן לשחזר כל קטע מזרם המפתח. בהתאמות קלות ההתקפה ישימה כנגד סוגים רבים של צופן זרם כמו צופן זרם שבנוי בסגנון 'מסנן' (filter generator).

רמת מתאם

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

$$p_{i}=\Pr[f(x_{1},...,x_{n})\neq x_{i}]\neq 1/2$$

עבור $1\leq i\leq n$ (כל האוגרים הכלולים במחולל). או לחלופין אם זרם המפתח נקרא $s$ אזי אומרים שקיים מתאם בין רצף חלקי באורך $t$ של זרם המפתח המסומן $(s_{t})_{t\geq 0}$ לבין רצף חלקי $(u_{t})_{t\geq 0}$ הנוצר מאחד האוגרים שבמחולל. רמת המתאם בין שני הרצפים $s,u$ נמדדת על ידי פונקציה המחושבת על $N$ סיביות

$$\sum _{t=0}^{N-1}(-1)^{s_{t}+u_{t}{\text{ mod }}2}$$

והיא משתנה מקרי ממשי בעל התפלגות בינומית עם תוחלת $N(1-2p_{i})$ ושונות $4Np_{i}(1-p_{i})$ (כאשר $N$ גדול). אפשר להשוות את ההתפלגות לרמת המתאם הצפויה בין הרצף $s$ לבין רצף אקראי $(r_{t})_{t\geq 0}$ בלתי תלוי. כאשר הרצף הוא אקראי בלתי תלוי ב-$s$ ההתפלגות בינומית עם תוחלת צפויה אפס ועם שונות $N$. רמת המתאם היא כלי יעיל המאפשר לתוקף להפעיל התקפת כוח גס ישירה בחיפוש אחר המצב הראשוני הנכון של אוגר נתון. ניתן להבחין בין מצב התחלתי נכון למצב התחלתי שגוי, משום שמצפים מערך התחלתי שגוי שיהיה בלתי תלוי סטטיסטית בזרם המפתח, כל תלות סטטיסטית שתמצא תאשש שהמצב ההתחלתי אכן נכון. בפועל ערך כלשהו יתקבל כמצב התחלתי נכון אם רמת המתאם עולה על סף מסוים המחושב בהתבסס על ההסתברות של שתי שגיאות אפשריות, האחת נקראת false alarm והיא מסומנת $P_{f}=2^{L_{i}}$ והשנייה נקראת הסתברות לאי-הבחנה $P_{n}=1.3\times 10^{-3}$. האורך $N$ שהוא כמות הסיביות המינימלית הדרושה להתקפה, נקבע לפי ההסתברות $p_{i}$ לעיל והאורכים של האוגרים $L_{i}$ בהתאמה. ההתקפה דורשת בערך:

$$N\simeq \left({\frac {{\sqrt {{\text{ln}}(2^{L_{i}-1})}}+3{\sqrt {2p_{i}(1-p_{i})}}}{{\sqrt {2}}(p_{i}-0.5)}}\right)^{2}$$

סיביות מפתח. כך שבממוצע מתבצעים $2^{L_{i}-1}$ ניסיונות. בכל מקרה ההתקפה אפשרית רק אם ההסתברות $p_{i}$ שונה מחצי. לסיכום ההתקפה מתוארת בפסאודו קוד הבא:

פסאודו קוד

קלט: קטע מזרם המפתח $s_{0},s_{1},...,s_{N-1}$ באורך $N$ סיביות. כאשר ההסתברות $p_{i}$ לעיל עבור מחרוזת זו לא שווה לחצי.

פלט: המחרוזת $u_{0},u_{1},...,u_{L_{i}-1}$ המייצגת את המצב ההתחלתי של האוגר $i$.

1. עבור כל מצב התחלתי אפשרי $u$, מפעילים את המחולל ומייצרים את $N$ הסיביות הבאות של האוגר $i$ ומחשבים את רמת המתאם בין התוצאה לבין מחרוזת הקלט $s$:

   $$\alpha =\sum _{i=0}^{N-1}(-1)^{s_{t}+u_{t}{\text{ mod }}2}$$

2. אם $\alpha$ קרוב לתוחלת $N(1-2p_{i})$ המחרוזת $u$ מתקבלת כמצב התחלתי אפשרי, אם לא ממשיכים לנסות עם מחרוזת אחרת.

חסינות מתאם

כדי למנוע התקפת קורלציה צריך לבחור פונקציית שילוב עם תכונה שנקראת 'חסינת-מתאם' (correlation immunity) מ'סדר ראשון' (להלן), כלומר שאין מתאם כלשהו בין פלט הפונקציה לאף אחד מהקלטים שלה. כך שהמפתח בלתי תלוי סטטיסטית בפלט של אוגר כלשהו מהאוגרים הכלולים במחולל וכן כל קלט יכול להיות אפשרי במידה שווה. באופן כללי יותר, התקפת קורלציה סימולטנית על $k$ אוגרים מתוך $n$ צריכה לבדוק את רמת המתאם בין זרם המפתח $s$ לבין הרצף $u$ שהוא קומבינציה של $k$ האוגרים באמצעות פונקציה בוליאנית $g$ של $k$ משתנים. היות שמתקיים

$$\Pr[s_{t}\neq u_{t}]=\Pr[f(x_{1},...,x_{n})\neq g(x_{i_{1}},...,x_{i_{k}})]=p_{g}$$

כאשר $f$ מייצגת את כל האוגרים ואילו $g$ את $k$ האוגרים הנבדקים לעומתם. ההתקפה יכולה להצליח רק אם $p_{g}\neq 1/2$. מספר האוגרים המינימלי הדרוש כדי שהתקפה סימולטנית כזו תיתכן היא $m+1$ כאשר $m$ הוא הסדר הגבוה ביותר של חסינות המתאם של הפונקציה הבוליאנית. פונקציה בוליאנית של $m+1$ משתנים המספקת את הקירוב הטוב ביותר של $f$ היא פונקציה אפינית $\textstyle \sum _{j=1}^{m+1}x_{i_{j}}+\epsilon$. התקפת קורלציה היעילה ביותר היא כזו שמוצאת קורלציה בין $s$ לבין המחרוזת $u$ אותה מחשבים על ידי חיבור הפלט של תת-קבוצה $i$ של אוגרים $i_{1},i_{2},...,i_{m+1}$ והיא מתאימה להסתברות:

$$\Pr[s_{t}\neq u_{t}]={\frac {1}{2}}-{\frac {1}{2^{n+1}}}|{\hat {f}}(t)|$$

כאשר $n$ הוא מספר המשתנים של פונקציית השילוב, $t$ הוא וקטור של $n$ סיביות שמרכיב ה-$i$ שלו הוא '1' רק אם $i\in \{i_{1},i_{2},...,i_{m+1}\}$ והפונקציה ${\hat {f}}$ מייצגת טרנספורמציית וואלש של $f$ (נקראת גם התמרת פורייה בדידה) אותה מחשבים על ידי $\textstyle \sum _{x\in f}(-1)^{f(x)\oplus x\cdot u}$. המסקנה שכדי להעלות את סיבוכיות התקפת הקורלציה רצוי שפונקציית השילוב של המחולל תהיה מסדר גבוה של 'חסינות-מתאם' וכן אי-ליניאריות גבוהה. או במילים אחרות שהפונקציה ${\hat {f}}$ תהיה נמוכה מעל כל הווקטורים $t$ עם משקל בינארי נמוך.

סדר חסינות

סדר $m$ של חסינות מתאם פירושו 'מקסימום קורלציה' בין פלט פונקציה בוליאנית $f$ עם $n$ משתנים לבין תת-קבוצה שלה $i$ של $m$ משתנים. מקסימום קורלציה מחושבת על ידי $\textstyle C_{f}(i)=2^{-n}{\text{max}}_{g\in {\mathcal {F}}_{i}}\sum _{x\in F_{2}^{n}}(-1)^{f(x)\oplus g(x)}$ כאשר ${\mathcal {F}}_{i}$ היא פונקציה בוליאנית של $n$ המשתנים $x_{j}$ כאשר $j\in i$. הסימן $F_{2}^{n}$ פירושו קבוצת כל הווקטורים הבינאריים $(x_{1},...,x_{n})$ באורך $n$ מעל השדה $F_{2}$.

לקריאה נוספת

• Bruce Schneier. Applied Cryptography: Protocols, Algorithms and Source Code in C, Second Edition. John Wiley & Sons, Inc. 1996. ISBN 0-471-12845-7. Page 382 of section 16.4: Stream Ciphers Using LFSRs.

• אנציקלופדיה לקריפטוגרפיה ואבטחת מידע