ביטחון סמנטי

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

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

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

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

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

היסטוריה

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