ביטחון סמנטי

בקריפטוגרפיה, ביטחון סֵמַנְטִי (Semantic security) היא הגדרה של ביטחון אלגוריתם הצפנה דטרמיניסטי או הסתברותי, סימטרי ואסימטרי כאחד. נניח שליריב או התוקף גישה לזוג טקסטים קריאים כלשהם $m_{0},m_{1}$ ובאפשרותו לראות את תוצאת ההצפנה שלהם עם האלגוריתם אותו הוא מעוניין לפצח. האלגוריתם ייקרא בטוח סמנטית אם היריב לא יוכל ללמוד בזמן ריצה פולינומי בהסתברות גבוהה מחצי בשיעור שאינו זניח האם תוצאת האלגוריתם היא הצפנה של $m_{0}$ או $m_{1}$ מבלי לראות את המפתח. המילה סמנטי מקורה מהגדרה היסטורית של ההצפנה בה הוצפנו מילים ואותיות.

אי-יכולת הבחנה

הוכח, שביטחון סמנטי שקול להגדרת ביטחון מערכת הצפנה שנקראת 'אי-יכולת הבחנה' (indistinguishability) המסומנת בקיצור IND, שפירושה שהיריב לא יכול להבחין בין טקסטים מוצפנים של המערכת לבין טקסט אקראי אמיתי בהסתברות גבוהה מחצי בשיעור שאינו זניח (non-negligable). אפשר לחלק את ההגדרה של ביטחון סמנטי לכמה דרגות בהתאם ליכולות היריב מהקל לכבד. מהיבט תאורטי ההנחה היא שליריב בעל עוצמת חישוב גבוהה גישה ל"אורקל הצפנה" או "אורקל פענוח". ההבדל ביניהם הוא שבראשונה היריב מקבל תוצאות הצפנה של טקסטים קריאים אותם הוא מגיש לאורקל לפי בחירתו, מה שקרוי התקפת גלוי-נבחר, או בקיצור IND-CPA. יש לציין שבהצפנה אסמטרית מעצם ההגדרה, היריב יכול תמיד לקבל הצפנה של טקסטים קריאים כרצונו, בגלל שיש לו גישה למפתח הציבורי. בשנייה הוא מגיש טקסטים מוצפנים לאורקל לפי בחירתו ומקבל בחזרה את הפענוח שלהם. זוהי התקפת מוצפן-נבחר בקיצור IND-CCA שהיא ההגדרה היותר מחמירה וגם היא מתחלקת לשני סוגים CCA1 ו-CCA2 (ראו גם חשילות).

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

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

הקשר לסודיות מושלמת

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

ההגדרה הפורמלית של סודיות מושלמת היא; עבור כל שני מסרים אקראיים כלשהם המסומנים בקיצור $(m_{0},m_{1})$ אם ההתפלגות של ההצפנה ${\text{ENC}}_{K}(m_{0})$ וההצפנה ${\text{ENC}}_{K}(m_{1})$ זהה לחלוטין ולא ניתן להבחין ביניהם בשום אופן, אזי ההצפנה מספקת סודיות מושלמת. למשל הוכח שאם $K$ הוא מחרוזת אקראית כלשהי (לפחות כמו המסר עצמו) הרי ש-XOR של המסר עם $K$ מספק ביטחון מושלם, כלומר הצופן אינו טומן בחובו שום מידע לגבי המקור. ההוכחה נכונה רק אם $K$ נבחר באקראי בהסתברות שווה, מתוך מרחב המפתחות שגודלו לפחות כמרחב המסר, כלומר $|K|\geq |M|$.

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

למעשה, כעת בידי היריב שתי אופציות, שאותן תמיד יוכל לנצל כדי לתקוף את הצופן, ללא תלות בביטחונו. הראשונה: ניחוש אקראי. אם מפתח ההצפנה שאיתו נעשה שימוש בגודל $k$ סיביות והוא נבחר באקראי מתוך הטווח המקסימלי של המפתחות האפשריים, ההסתברות שהניחוש יצליח היא $2^{-k}$. אך אם המפתח קל לניחוש, כגון: אם נבחר מתוך רשימה קצרה של מפתחות, או שמכיל יתירות מסוימת - דהיינו שאינו אקראי לחלוטין, הניחוש הרבה יותר קל. האופציה השנייה היא כוח גס, דהיינו הניסיון לנחש מהו המפתח על ידי $2^{k-1}$ ניסיונות הצפנה במקרה הממוצע, עם כל המפתחות האפשריים. אם התקפת איזון זמן/זיכרון אפשרית או תקיפת היפגשות באמצע (MITM), התוקף יכול להשתמש בטבלאות חיפוש. למשל אפשר לאחסן טבלה של כל אפשרויות ההצפנה (עם כל המפתחות האפשריים) ולחפש התאמה. חיפוש בטבלה אמנם מתבצע בזמן של ${\text{log }}k$ אך דרישות הזיכרון מאידך אינן מעשיות. אף על פי שקיימות טכניקות לאיזון בין צריכת זיכרון לזמן חישוב, אם המפתח גדול התקפה כזו לא תהיה מעשית.

פונקציית זניחות

ערך מורחב – פונקציה זניחה

בניסוח פורמלי, indistinguishability (אי-יכולת הבחנה) פירושה שאם נתונה סכמת הצפנה ופענוח (בקיצור: Enc/Dec), הפרמטר $\epsilon$ ומפתח אקראי $K$, אז לכל שני מסרים $M_{0},M_{1}$ כלשהם ופונקציה בוליאנית $T$ בסיבוכיות לפי פרמטר $t$ (הפרמטרים יובהרו בהמשך), מתקיים:

$|\Pr[T(ENC_{K}(M_{0})=1]-\Pr[T(ENC_{K}(M_{1})=1]|\leq \epsilon$

כלומר: בהינתן תוצאות ההצפנה של שני המסרים, היריב לא יכול לזהות בהבדל משמעותי (שאינו זניח) ביניהם, ולומר מי מהן היא תוצאה של המסר הראשון ומי מהן של השני. רצוי שהפרמטר $t$ יהיה גדול, מסדר גודל של $2^{90}$. הפרמטר $\epsilon$ הוא טווח השגיאה, כלומר המידה שבה הפונקציה היא זניחה (להלן).

כלי שימושי להגדרת בטיחות ההצפנה היא המושג פונקציה זניחה (Negligible function). הפונקציה $\nu :\mathbb {N} \rightarrow \mathbb {R} ^{+}$ נקראת זניחה, אם לכל פולינום $p$ ו-$k$ גדול מתקיים:

$\nu (k)\leq {\frac {1}{p(k)}}$.

כלומר: תכונת אי-ההבחנה מתקיימת, אם ההסתברות שהיריב יצליח לזהות הבדל בין שני המסרים המוצפנים גדול מחצי בשיעור כה קטן, עד שהוא זניח (לא מורגש). לדוגמה: $k^{-{\text{log }}k}$ היא פונקציה זניחה, היות שהיא מתכנסת ל-0 בקצב "מהיר"; לעומת זאת, $1/k^{1000}$ אינה פונקציה זניחה. שני פרמטרים שימושיים נוספים להגדרה קונקרטית של ביטחון סמנטי, הם הפונקציה $I(m)$ שהיא כמות המידע שיש בידי התוקף לגבי ההתפלגות $X$ של טווח המסר $M$ לפני ההצפנה והפונקציה $f(m)$ מייצגת את המידע שהתוקף מעוניין להשיג לגבי $m$ על ידי ציתות. ייתכן שהתוקף מעוניין בחשיפת המסר כולו או מסתפק בסיבית אחת בלבד.

ההגדרה הקונקרטית של ביטחון סמנטי, בהינתן סכמת הצפנה (Enc,Dec), הפרמטרים $(t,o,\epsilon )$, אם עבור כל התפלגות $X$ וכל פונקציה $I:\{0,1\}^{m}\rightarrow \{0,1\}^{*}$ ופונקציה $f:\{0,1\}^{m}\rightarrow \{0,1\}^{*}$. עבור כל אלגוריתם $A$ בסיבוכיות $t_{A}+t$ קיים אלגוריתם $A'$ בסיבוכיות $t_{A}+o$, כך שמתקיים:

$|\Pr[A(ENC_{K}(m),I(m))=f(m)]-\Pr[A'(I(m))=f(m)]|\ \leq \epsilon$

במילים, ההסתברות שאלגוריתם $A$ עם פונקציית ההצפנה $Enc$ יפיק פלט $f(m)$ כלומר ישיג את היעד שנקבע, לא גדולה בשיעור שעולה על $\epsilon$, מההסתברות ש-$A'$ יצליח לעשות זאת (ללא ההצפנה). כלומר המידע הנוסף לתוקף על ידי ההצפנה זניח. פרמטרים מעניינים מבחינה מעשית יכולים להיות למשל: $t=2^{90}$ ו-$\epsilon =2^{-70}$ וסיבוכיות $o$ צריכה להיות קטנה מאוד. אפשר לראות שאם $\epsilon =0$ ו-$t$ לא מוגבל, ההגדרה המתוארת תהיה מקבילה לסודיות מושלמת.

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

ערך מורחב – התקפת גלוי-נבחר

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

בניסוח פורמלי עבור סכמת הצפנה (Enc,Dec), פונקציה בוליאנית $T$ בסיבוכיות $\leq t$, פרמטר $\epsilon$ המייצג פונקציית זניחות כלשהי ושני מסרים אקראיים כלשהם $m_{0},m_{1}$, מתקיים:

$|\Pr[T^{ENC_{K}}(ENC_{K}(m_{0}))=1]-\Pr[T^{ENC_{K}}(ENC_{K}(m_{1}))=1]|\leq \epsilon$

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

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

היסטוריה

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

דוגמאות

שיטת הצפנה דטרמיניסטית כמו RSA מכילה מטבעה מספר חולשות מהותיות:

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

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