התקפת מוצפן-נבחר

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

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

מבוא והגדרות

נתונה מערכת הצפנה סימטרית $\Pi =({\text{Gen}},{\text{Enc}},{\text{Dec}})$ הכוללת שלושה אלגוריתמים, אלגוריתם הכנת מפתח, אלגוריתם הצפנה ואלגוריתם פענוח בהתאמה. נתון יריב ${\mathcal {A}}$ המעוניין לשבור את $\Pi$ וכן נתון פרמטר ביטחון $n$.

מהיבט תאורטי היכולת המוקנת ל-${\mathcal {A}}$ מבוטאת באמצעות אורקל היפותטי שהוא מעין קופסה שחורה, באמצעות פרוטוקול הפעלה חיצוני הוא יכול להצפין או לפענח איתה כל קלט שיחפוץ ולראות את התוצאה, איך אין לו אפשרות לראות את תכולתה ביחוד לא את מפתח ההצפנה או מפתח הפענוח. להלן מתואר "ניסוי הבחנה" הנקרא ${\text{PrivK}}_{{\mathcal {A}},\Pi }^{\text{cca}}(n)$ המתנהל כך:

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

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

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

מערכת ההצפנה $\Pi$ תקרא בלתי ניתנת להבחנה תחת התקפת מוצפן-נבחר (בקיצור CCA-IND) אם עבור כל יריב פולינומי היסתברותי ${\mathcal {A}}$ קיימת פונקצית זניחות ${\text{negl}}$ כך שמתקיים:

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

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

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

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

דוגמאות מעשיות

אם נתונה מערכת הצפנה סימטרית כדלהלן: ${\text{Enc}}_{k}(m)=\langle r,F_{k}(r)\oplus m\rangle$ כאשר $F_{k}$ היא פונקציית הצפנה כמו DES. המערכת מקבלת את $m$ ומחזירה ערך אקראי כלשהו $r$ ואת $s=F_{k}(r)\oplus m$ כאשר $\oplus$ מסמל XOR. הוכח שמערכת זו נקראת בטוחה לפי מודל התקפת גלוי-נבחר. אפשר להמחיש בקלות מדוע מערכת זו לא תהיה בטוחה במסגרת מודל התקפת מוצפן-נבחר, כדלהלן. המתקיף יכול לשלוח לאורקל את $m_{0}=0^{n}$ (מחרוזת של $n$ אפסים) וכן $m_{1}=1^{n}$ (מחרוזת של $n$ אחדים). כעת, כאשר הוא מקבל את האתגר $c=\langle r,s\rangle$, הוא יכול להפוך את הסיבית הראשונה של $s$ ואז לבקש מהאורקל לפענח את הטקסט המוצפן $c'$ לאחר השינוי. כמובן ש-$c\neq c'$ לכן השאילתה הזו מותרת. תשובת האורקל לאחר הפענוח של $c'$ יכולה להיות אחד מהשנים, או $10^{n-1}$ במקרה של $b=0$ או $01^{n-1}$ במקרה של $b=1$. בגלל ה-XOR השינוי בסיבית הראשונה משפיע על תוצאת הפענוח רק בסיבית הראשונה, לכן התוצאה תהיה יכולה להיות רק '0' שלאחריו מחרוזת של $n-1$ אחדים או להיפך '1' שלאחריו מחרוזת של $n-1$ אפסים. ברור שהמתקיף יכול כעת להבחין בברור מה פוענח או במילים אחרות $b=b'$ בהסתברות של '1'. דוגמה זו ממחישה היטב מדוע מודל התקפת מוצפן-נבחר נחשבת למודל המחמיר ביותר. כל מערכת הצפנה שבה המתקיף רשאי לבצע מניפולציה לוגית של סיביות מבלי שהדבר יתקל בחשיפה ודחייה על ידי המערכת, אינה נחשבת לבטוחה תחת מודל התקפת מוצפן-נבחר. למעשה הגדרה זו מקבילה להגדרת החשילות. באופן כללי רעיון החשילות הוא שצופן אינו חשיל אם יריב המנסה לשנות טקסט מוצפן כלשהו נתקל בתוצאה שהיא אחת מהשתיים, טקסט "בלתי חוקי" או טקסט מוצפן כזה שלטקסט הגלוי המתקבל לאחר פענוחו אין קשר סטטיסטי כלשהו לטקסט הגלוי המקורי.

ידוע שהצפנת RSA וכן כל שיטת הצפנה דטרמיניסטית חשופה מעצם טבעה להתקפת מוצפן-נבחר. למרות שצופן אל-גמאל והצפנת בלום-גולדווסר מוגדרות כבטוחות סמנטית, זוהי הגדרה חלשה כיוון שניתן לפרוץ אותן בהתקפת CCA. למשל ב-RSA כדי לחלץ את $m=c^{d}{\mbox{ (mod }}n)$ אפשר להערים על המערכת המצפינה והמפענחת על ידי ניסיון לפענח את $c'\equiv cs^{e}{\mbox{ mod }}n$ אם התוצאה היא $m'$ כלשהו קל מאוד לחלץ את $m$ ממנה פשוט על ידי הכפלה בהופכי הכפלי של $s$ כי $m\equiv m's^{-1}{\mbox{ (mod }}n)$.

יתרה מזו כיוון שהוכח שבהצפנת RSA חשיפת הסיבית הנמוכה ביותר שקולה לפענוח המסר כולו. לכן אפשר לבסס את ההתקפה על תשובה פשוטה; אמת או שקר. כלומר האם הפענוח הצליח או נכשל עקב אי תאימות לתקן כגון אם התוצאה אינה בפורמט הנכון או בטווח הערכים המותר על פי התקן. דוגמה טובה להתקפה כזו היא התקפת מוצפן-נבחר של דניאל בלייכבכר ממעבדות בל כנגד PKCS הגרסה הראשונה, שיישם את RSA עם שיטת ריפוד הכוללת שני בתים קבועים ומחרוזת ריפוד רנדומאלית המשורשרת למסר לפני ההצפנה. פרוטקול PKCS#1 שהיווה חלק חשוב מ-SSL היה פגיע להתקפה זו שאיפשרה שחזור מפתח השיחה על ידי בחירה מושכלת של $s^{e}$ ו-$2^{20}$ ניסיונות פענוח בקירוב.

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

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

גרסאות של מתקפת מוצפן-נבחר

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

התקפת "ארוחת צהרים"

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

התקפת מוצפן-נבחר מותאמת

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