התקפת גלוי-נבחר

בקריפטואנליזה, התקפת גלוי-נבחר או תְּקִיפַת תַּמְלִיל פָּשׁוּט נִבְחָר (באנגלית: Chosen-plaintext attack) היא מודל התקפה נגד מערכת הצפנה שמניח כי ליריב היכולת להשיג תוצאות הצפנה של טקסטים גלויים כלשהם, לפי בחירתו, שהוצפנו באמצעות אלגוריתם ההצפנה המותקף. מטרת ההתקפה היא להשיג באמצעותם מידע כלשהו על האלגוריתם כמו חשיפת חלק ממפתח הצפנה או כולו ובכך לרופף את ביטחונו או להביא לשבירתו המוחלטת.

אורקל הצפנה

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

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

מודל כללי

התקפת גלוי-נבחר מתחלקת לשני סוגים:

• התקפת גלוי-נבחר המסומנת IND-CPA 1 - קיצור של Indistinguishability Chosen Plaintext Attack. היא סוג של התקפה שבה מניחים שהמתקיף יכול לבחור כל טקסט מקור שהוא מעוניין לקבל עבורו את הטקסט המוצפן המתאים. אך הוא יכול לראות את הטקסט המוצפן רק לאחר שסיים להגיש את כל השאילתות. מרגע שהוא רואה את הטקסט המוצפן, הוא אינו יכול להגיש בקשות נוספות.
• התקפת גלוי נבחר אדפטיבית המסומנת IND-CPA 2. היא התקפה חזקה יותר שבה המתקיף מסוגל להתאים את בקשותיו בהתאם לתוצאות קודמות, כלומר ביכולתו לבקש טקסט מוצפן גם לאחר שראה טקסט מוצפן שביקש קודם.

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

התקפת גלוי-נבחר נגד מערכת הצפנה סימטרית

התקפת גלוי-נבחר הכללית מתוארת באמצעות ניסוי המתנהל בין המתקיף לאורקל הצפנה היפותטי.

1. תחילה אורקל ההצפנה בוחר מפתח הצפנה אקראי סודי $k$.
2. המתקיף ${\mathcal {A}}$ בוחר ושולח לאורקל זוג טקסטים גלויים $(m_{0},m_{1})$.
3. אורקל ההצפנה בתורו מטיל מטבע, ולפי התוצאה $b\in \{0,1\}$ הוא מבצע הצפנה של אחד משני המסרים שקיבל: $c={\text{Enc}}_{k}(m_{b})$ ומחזיר את $c$ (האתגר) למתקיף.
4. המתקיף ${\mathcal {A}}$ שיש לו גישה לאורקל ההצפנה רשאי לבקש ממנו הצפנות נוספות כלשהן, הוא בודק את המידע שקיבל ומחזיר את הסיבית $b'$.
5. תוצאת הניסוי היא 1 כלומר מוכרזת כמוצלחת אם $b=b'$ או אפס המייצג כישלון במקרה ש-$b\neq b'$.

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

אם תוצאת הניסוי או הניסויים היא 1 המשמעות היא שאלגוריתם ההצפנה נפרץ, כי כעת עלה בידי המתקיף להבחין בין הצפנה של טקסטים שונים. חשוב להדגיש שאין מדובר כאן בהגדרה תאורטית בלבד, אלא לעובדה זו השלכות מעשיות ולא מומלץ כלל להשתמש באלגוריתם הצפנה דטרמיניסטי מפני כמה סיבות. לא רק שבמקרה כזה למתקיף קל לזהות הצפנה חוזרת של מסרים זהים עם אותו מפתח, אלא שהוא יכול אפילו לפענח את הטקסט המוצפן בהסתברות גבוהה, אם במקרה טווח המסרים האפשריים קטן. לצורך המחשה, אם נניח שפרופסור באוניברסיטה מצפין את הציונים של הסטודנטים שלו עם RSA, עם מפתח הצפנה גדול. היות שטווח הציונים הוא $\{A,B,C,D,E,F\}$ המתקיף יכול פשוט להצפין עם המפתח הציבורי של הפרופסור את כל הציונים האפשריים, להכין טבלה של ציונים מוצפנים ואז להשוות את הציונים בפועל של הסטודנטים עם ציונים המוצפנים בטבלה.

ביטחון מערכת סימטרית נגד התקפת גלוי-נבחר

באופן פורמלי מערכת הצפנה סימטרית אקראית $\Pi =({\text{Gen}},{\text{Enc}},{\text{Dec}})$ תוגדר בלתי ניתנת להבחנה (indistinguishable) או בטוחה סמנטית תחת מודל התקפת גלוי-נבחר אם עבור כל מתקיף פולינומי ${\mathcal {A}}$ קיימת פונקציית זניחות ${\text{negl}}(n)$ עבור פרמטר הביטחון $n$ המייצג את אורך הקלט כך שמתקיים:

$\Pr[{\text{Priv}}_{{\mathcal {A}},\Pi }^{\text{cpa}}(n)=1]\leq {\frac {1}{2}}+{\text{negl}}(n)$,

פירוש הביטוי הוא שסיכוייו של המתקיף ${\mathcal {A}}$ לשבור את $\Pi$ תחת מודל התקפת גלוי נבחר אינם עולים על חצי יותר משיעור שנקבע על ידי פונקציית הזניחות שמשמעה שהיתרון של המתקיף שולי ביחס ל-$n$. יש לציין שאם $\Pi$ הייתה דטרמיניסטית התכונה האמורה לא הייתה מתקיימת, כיוון שבמקרה כזה קל מאוד למתקיף לדעת האם ההצפנה היא של $m_{0}$ או $m_{1}$, הוא יכול פשוט לשלוח את שניהם ולרשום את התוצאות, כי הרי בכל הצפנה של קלט זהה התוצאה תהיה תמיד זהה. לעומת זאת תכונת אי-יכולת הבחנה תקפה כאשר אלגוריתם ההצפנה הסתברותי. כלומר בכל הצפנה גם אם הקלט זהה תתקבל תוצאה שונה בגלל אקראיות ההצפנה. המסקנה היא שאלגוריתם הצפנה דטרמיניסטי אינו יכול להיות בטוח תחת מודל התקפת גלוי-נבחר.

ביטחון מערכת א-סימטרית נגד התקפת-גלוי-נבחר

מערכת הצפנת מפתח ציבורי $\Pi =({\text{Gen}},{\text{Enc}},{\text{Dec}})$ נקראת בטוחה סמנטית או בעלת אי-יכולת הבחנה תחת מודל התקפת גלוי-נבחר (בקיצור CPA) אם עבור כל אלגוריתם פולינומי הסתברותי ${\mathcal {A}}$ ופונקציית זניחות ${\text{negl}}(n)$ מתקיים:

$\Pr[{\text{PubK}}_{{\mathcal {A}},\Pi }^{\text{cpa}}(n)=1]\leq {\frac {1}{2}}+{\text{negl}}(n)$

ההגדרה דומה לזו של צופן סימטרי למעט העובדה שהמתקיף מקבל בנוסף את מפתח ההצפנה הציבורי. גם כאן ההצפנה חייבת להיות הסתברותית כי לא קיימת מערכת הצפנה דטרמיניסטית בטוחה סמנטית וכן במקרה זה אורקל ההצפנה אינו נחוץ למתקיף ${\mathcal {A}}$ היות שהוא יכול להצפין כל מסר בעצמו באמצעות המפתח הציבורי. לכן, עצם העובדה שמערכת הצפנה א-סימטרית בטוחה נגד יריב פאסיבי מלמדת בהכרח שהיא בטוחה גם נגד התקפת גלוי-נבחר. הבדל נוסף הוא שבניגוד למערכת הצפנה סימטרית לא ניתן להגיע בשום אופן למערכת הצפנה א-סימטרית בעלת ביטחון מושלם ואין זה משנה כמה ארוכים המפתחות או כמה המסר קצר.

התקפות מעשיות

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

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

התקפת גלוי-נבחר נגד צפנים מודרניים

צופן DES היה במשך שנים מטרה להתקפות קריפוטואנליטיות תאורטיות ומעשיות, בראשן הקריפטואנליזה הדיפרנציאלית שמסתמכת על כמות נכבדה של זוגות טקסטים גלויים וטקסטים מוצפנים המתאימים להם (בערך $2^{47}$). אפשר לבצע את ההתקפה עם פחות טקסטים נבחרים אולם סיבוכיותה עולה בהתאם. הקריפטואנליזה הדיפרנציאלית היא התקפת גלוי-נבחר במהותה כיוון שמתקיף צריך להכין תחילה מאגר של טקסטים קריאים בעלי דיפרנציאל מסוים, אותם הוא צריך להצפין ומתוכם הוא אמור לבחור טקסטים מסוימים. אף על פי ש-DES גילה עמידות גבוהה נגד התקפה זו, צפנים אחרים כמו FEAL ,Khafre ,REDOC-II ,LOKI ולוציפר פוצחו לגמרי בשיטה זו.

ראו גם

• ביטחון סמנטי
• התקפת מוצפן-נבחר
• חשילות