ריפוד אופטימלי להצפנה אסימטרית

בקריפטוגרפיה, ריפוד אופטימלי להצפנה אסימטרית (Optimal Asymmetric Encryption Padding) הוצע לראשונה על ידי מיהיר בלייר מאוניברסיטת קליפורניה בסן דייגו ופיליפ רוגווי מאוניברסיטת קליפורניה בדייוויס בשנת 1995. סכימת OAEP היא אלגוריתם שמכין את הקלט להצפנה באופן כזה שאפשר יהיה לנצל פונקציית הצפנה אסימטרית דטרמיניסטית כמו RSA ולקבל ביטחון סמנטי נגד התקפת מוצפן-נבחר תחת מודל אורקל אקראי.

היסטוריה ורקע

בכל הצפנה דטרמיניסטית, בהצפנה חוזרת של מסר נתון עם מפתח הצפנה זהה תמיד יתקבל טקסט מוצפן זהה. בשל עובדה זו היא אינה יכולה להחשב "בטוחה סמנטית", כי בעצם העובדה שכאשר מופיעים בלוקים מוצפנים זהים אפשר להסיק שהטקסטים המקוריים המתאימים להם היו זהים, מועבר ליריב פוטנציאלי מידע על סכימת ההצפנה שלא היה מושג בדרך אחרת, מה שמאפשר התקפת מוצפן-נבחר בתנאים מסוימים. מסיבה זו פונקציית הצפנה דטרמיניסטית כזו אינה ראויה לשימוש באופן ישיר אלא רק לאחר הכנת המסר על ידי סכימת ריפוד מתאימה הכוללת ערך אקראי כלשהו. הריפוד מבטיח שללא תלות במסר תמיד יתקבל בלוק שונה ועל כן תמיד יופק טקסט מוצפן שונה. תקן PKCS #1 גרסה v1.5 (הקודם) פירט שיטת ריפוד פשוטה כדלקמן: עבור מודולוס בגודל  סיביות, להצפנת המסר , בונים בלוק באורך  בתים ( נקרא כאן פרמטר ביטחון ונקבע על ידי פונקציית ההצפנה, למשל ב-RSA-1024 הוא ). הבלוק המורכב על ידי שרשור הערכים לפי הסדר הבא: , כאשר  הוא המסר המקורי המיועד להצפנה. מתחילים בבית אפס לאחריו בית שמכיל את הערך '02', לאחריו מחרוזת אקראית של שמונה בתים לפחות שאינם '00' שצריכה להיות שונה עבור כל מסר אך לא חייבת להיות סודית, אחריה בית אפס נוסף ולבסוף מצמידים את המסר . את הבלוק שנוצר מצפינים לאחר מכן עם RSA כרגיל: . לאחר פענוח, המפענח מוודא תחילה שהבלוק בנוי בפורמט הנכון, כלומר הערכים מופיעים לפי הסדר האמור, אם לא הוא דוחה את המסר המוצפן ומחזיר הודעת שגיאה, אם כן, מפרק את הבלוק למחרוזות המקוריות ומחלץ את המסר המקורי .
בשיטה זו בידי המפענח יכולת בסיסית לאתר תקלות או שינויים זדוניים בטקסט המוצפן. היות שהתוצאה חייבת לעמוד בדרישות התקן, לא סביר שטקסט מוצפן שעבר "שיפוץ" בדרכו אל המקבל על ידי צד שלישי כלשהו (שהטקסט המקורי לא ידוע לו) יתקבל במבנה הנכון לאחר פענוח. על פניו נראה כאילו סכימת הריפוד הזו מספקת אימות עקיף והיא בטוחה סמנטית בשל תוספת האקראיות של , דהיינו בכל הצפנה יתקבל טקסט מוצפן אחר וכן לפי זה היא אמורה להיות חסינה מפני התקפת מוצפן-נבחר. אולם ב-1998 הראה דניאל בלייכנבכר ממעבדות בל ששיטת ריפוד זו אינה בטוחה כלל ואפשר לפרוץ אותה על ידי שליחה של כ־ טקסטים מוצפנים לכאורה בהתקפת מוצפן-נבחר אדפטיבית, בהסתמך על יכולת המתקיף לקבל משוב מהמערכת. כלומר כדי שההתקפה תצליח צריך שלמתקיף תהיה גישה לשרת הפענוח והוא יכול לבקש פענוח של כל טקסט כרצונו. אם הטקסט אינו תואם PKCS מהסיבה שאינו בנוי בפורמט המתואר הוא אמור לקבל הודעת שגיאה. הודעת השגיאה במקרה זה משרתת את המתקיף כ"אורקל פענוח" איתו הוא יכול לנחש את הטקסט המוצפן בשיטה האדפטיבית, כלומר כל בקשת פענוח מסתמכת על תוצאות קודמות כדי לצמצם את טווח החיפוש עדי כדי אפשרות יחידה. ההתקפה הייתה הרסנית במיוחד כיוון ש-SSL הסתמך על סכמת הריפוד הזו וכתוצאה מכך הפך ללא בטוח כלל.
בלום ומיקאלי הציעו שיטת "רדוקציה" להוכחת ביטחון, כלומר הצגת אלגוריתם אפקטיבי שיכול לקרוא תיגר על ההשערה הבסיסית כמו קושי בהיפוך RSA או קושי בפירוק לגורמים, שמכיל את הפרוטוקול עצמו כתת-שגרה. כלומר מראים שאם קיים אלגוריתם שיכול לפרוץ את הפרוטוקול, אזי בהכרח אפשר להמיר אותו לאלגוריתם שיכול לפתור את הבעיה המתמטית עליה הוא מבוסס. היות שההנחה היא שקשה לפתור את הבעיה המתמטית עליה הפרוטוקול מסתמך, זוהי הוכחת ביטחון טובה לחוזקו של הפרוטוקול מהיבט תאורטי. אך אינה פרקטית, מסתבר שקשה להגיע לביטחון פרקטי מוכח שהוא גם יעיל.