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

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

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

בכל הצפנה דטרמיניסטית, בהצפנה חוזרת של מסר נתון עם מפתח הצפנה זהה תמיד יתקבל טקסט מוצפן זהה. בשל עובדה זו היא אינה יכולה להחשב "בטוחה סמנטית", כי בעצם העובדה שכאשר מופיעים בלוקים מוצפנים זהים אפשר להסיק שהטקסטים המקוריים המתאימים להם היו זהים, מועבר ליריב פוטנציאלי מידע על סכימת ההצפנה שלא היה מושג בדרך אחרת, מה שמאפשר התקפת מוצפן-נבחר בתנאים מסוימים. מסיבה זו פונקציית הצפנה דטרמיניסטית כזו אינה ראויה לשימוש באופן ישיר אלא רק לאחר הכנת המסר על ידי סכימת ריפוד מתאימה הכוללת ערך אקראי כלשהו. הריפוד מבטיח שללא תלות במסר תמיד יתקבל בלוק שונה ועל כן תמיד יופק טקסט מוצפן שונה. תקן PKCS #1 גרסה v1.5 (הקודם) פירט שיטת ריפוד פשוטה כדלקמן: עבור מודולוס בגודל $2^{8k}$ סיביות, להצפנת המסר $m$ , בונים בלוק באורך $k$ בתים ( $k$ נקרא כאן פרמטר ביטחון ונקבע על ידי פונקציית ההצפנה, למשל ב-RSA-1024 הוא $128$ ). הבלוק המורכב על ידי שרשור הערכים לפי הסדר הבא: $M=00\ \|\ 02\ \|\ r\ \|\ 00\ \|\ m$ , כאשר $m$ הוא המסר המקורי המיועד להצפנה. מתחילים בבית אפס לאחריו בית שמכיל את הערך '02', לאחריו מחרוזת אקראית של שמונה בתים לפחות שאינם '00' שצריכה להיות שונה עבור כל מסר אך לא חייבת להיות סודית, אחריה בית אפס נוסף ולבסוף מצמידים את המסר $m$ . את הבלוק שנוצר מצפינים לאחר מכן עם RSA כרגיל: $C=M^{e}{\text{ mod }}n$ . לאחר פענוח, המפענח מוודא תחילה שהבלוק בנוי בפורמט הנכון, כלומר הערכים מופיעים לפי הסדר האמור, אם לא הוא דוחה את המסר המוצפן ומחזיר הודעת שגיאה, אם כן, מפרק את הבלוק למחרוזות המקוריות ומחלץ את המסר המקורי $m$ .

בשיטה זו בידי המפענח יכולת בסיסית לאתר תקלות או שינויים זדוניים בטקסט המוצפן. היות שהתוצאה חייבת לעמוד בדרישות התקן, לא סביר שטקסט מוצפן שעבר "שיפוץ" בדרכו אל המקבל על ידי צד שלישי כלשהו (שהטקסט המקורי לא ידוע לו) יתקבל במבנה הנכון לאחר פענוח. על פניו נראה כאילו סכימת הריפוד הזו מספקת אימות עקיף והיא בטוחה סמנטית בשל תוספת האקראיות של $r$ , דהיינו בכל הצפנה יתקבל טקסט מוצפן אחר וכן לפי זה היא אמורה להיות חסינה מפני התקפת מוצפן-נבחר. אולם ב-1998 הראה דניאל בלייכנבכר ממעבדות בל^[2] ששיטת ריפוד זו אינה בטוחה כלל ואפשר לפרוץ אותה על ידי שליחה של כ־ $2^{20}$ טקסטים מוצפנים לכאורה בהתקפת מוצפן-נבחר אדפטיבית, בהסתמך על יכולת המתקיף לקבל משוב מהמערכת. כלומר כדי שההתקפה תצליח צריך שלמתקיף תהיה גישה לשרת הפענוח והוא יכול לבקש פענוח של כל טקסט כרצונו. אם הטקסט אינו תואם PKCS מהסיבה שאינו בנוי בפורמט המתואר הוא אמור לקבל הודעת שגיאה. הודעת השגיאה במקרה זה משרתת את המתקיף כ"אורקל פענוח" איתו הוא יכול לנחש את הטקסט המוצפן בשיטה האדפטיבית, כלומר כל בקשת פענוח מסתמכת על תוצאות קודמות כדי לצמצם את טווח החיפוש עדי כדי אפשרות יחידה. ההתקפה הייתה הרסנית במיוחד כיוון ש-SSL הסתמך על סכמת הריפוד הזו וכתוצאה מכך הפך ללא בטוח כלל.

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

מודל אורקל אקראי

ערך מורחב – מודל אורקל אקראי

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

סכימת OAEP

סכימת OAEP היא הסכימה הראשונה שמיישמת את מודל האורקל האקראי. היא יכולה לעבוד עם כל פונקציה חד-כיוונית עם דלת מלכודת (פונקציית הצפנה) $f$ שמקבלת קלט ומחזירה פלט באורך $k$ סיביות ופונקציית גיבוב בטוחה כלשהי שמקודדת כל $m$ הקצר במעט מ- $k$ ומשלבת אותו יחד עם ערך אקראי $r$ . השיטה מסתמכת בנוסף גם על חוזקה של פונקציית הגיבוב. לצורך יישומה בפועל יש להגדיר פרמטר שלם $k_{0}<k$ ופרמטר $n=k-k_{0}$ וכן שתי פונקציות כלליות: הראשונה מחולל אקראי $G:\{0,1\}^{k_{0}}\rightarrow \{0,1\}^{n}$ שמקבל מחרוזת באורך $k_{0}$ ומחזיר מחרוזת אקראית באורך $n$ ופונקציה נוספת $H:\{0,1\}^{n}\rightarrow \{0,1\}^{k_{0}}$ שמקבלת מחרוזת באורך $n$ סיביות ומחזירה מחרוזת קצרה יותר באורך $k_{0}$ (למשל אפשר להשתמש ב- $n$ או $k_{0}$ הסיביות הפחות משמעותיות של SHA-2 לפי הצורך). כדי לרפד את המסר $m\in \{0,1\}^{n}$ בוחרים שלם אקראי $r$ באורך $k_{0}$ סיביות ומחשבים את:

{\text{OAEP}}(m)=m\oplus G(r)\ \|\ r\oplus H(m\oplus G(r))

כאשר הסימן $\|$ מסמל שרשור מחרוזות והסמל $\oplus$ מייצג XOR. ההצפנה היא $c=f({\text{OAEP}}(m))$ והפענוח מבוצע בדרך דומה. הסכימה הבסיסית המתוארת הוכחה בטוחה על ידי בלייר ורוגווי בהנחה שפונקציית הגיבוב "אידיאלית". פירושו של דבר הוא שההנחה היא ש- $G$ ו- $H$ הן פונקציות רנדומליות המתנהגות כמו אורקל אקראי. כמובן שמעשית אי אפשר להניח כזו הנחה, אך הפונקציות הקיימות ידועות כמספיק חזקות כדי לבסס עליהן מערכת הצפנה מהיבט פרקטי. החסרון העיקרי בסכימה המתוארת שאינה "מודעת טקסט-מקור" (plaintext-aware). בהקשר של מודל אורקל אקראי "מודעות טקסט מקור" פירושה שכדי שתוקף יצליח לבנות טקסט מוצפן "תקף", דהיינו שהמקבל יצליח לפענחו במבנה הנכון לפי התקן עליו לדעת בהכרח טקסט מקור שמתאים לו. ניסיון לנחש מחרוזת סיביות כלשהי שלאחר פענוחה בפונקציית הפענוח עם מפתח הצפנה כלשהו, יתקבל טקסט מקור במבנה הנכון קשה לביצוע. ההשלכה היא שהסכימה הבסיסית אינה מוכחת כעמידה נגד התקפת מוצפן נבחר אדפטיבית (CCA2) אלא רק כנגד CCA1. בלייר ורוגווי הציעו גרסה נוספת (כמתואר בתרשים) שלטענתם "מודעת טקסט מקור" והיא פועלת כדלהלן:

{\text{OAEP}}(m)=m0^{k_{1}}\oplus G(r)\ \|\ r\oplus H(m0^{k_{1}}\oplus G(r))

.

כאשר $n=k-k_{0}-k_{1}$ וכן $k_{1}$ הוא פרמטר נוסף המקיים $k_{0}+k_{1}<k$ . כאן בנוסף משרשרים מחרוזת של $k_{1}$ אפסים למסר. ההצפנה והפענוח באותו האופן. וריאציה של הסכימה האחרונה שולבה למעשה בתקן PKCS#2 כסכימת ריפוד מחייבת עבור הצפנה עם RSA.

OAEP נחשבה עמידה כנגד התקפת מוצפן נבחר מסוג 2 אם כי המחברים לא סיפקו הוכחה פורמלית. ויקטור שופ הוכיח^[5] על ידי דוגמה נגדית שתחת מודל אורקל אקראי זה לא תמיד נכון. הוא הראה שקיימת פונקציה חד-כיוונית $g$ שבה קל חשב את $g(x\oplus a)$ מתוך $g(x)$ ו- $a$ מזה נובע שמבנה ריפוד OAEP אינו יכול להיות עמיד תמיד כנגד CCA2 עבור סתם פונקציה חד-כיוונית. מאידך הוא גם הוכיח כי עבור פונקציית RSA הסכימה שהוצעה טובה, וזאת רק בשל תכונה ספציפית ל-RSA (בהמשך).

סכימת OAEP+‎

מהדוגמה שהובאה על ידי שופ נראה שכדי שהתקפה מסוג CCA2 תצליח, התוקף צריך להיות מסוגל לפחות חלקית להפוך את התמורה החד-כיוונית $f$ . העובדה שפונקציה חד-כיוונית אינה מעידה בהכרח שהיא חד-כיוונית חלקית (partial domain one-way). פוג'יסאקי ואחרים הוכיחו^[6] שאם הפונקציה $f$ היא חד-כיוונית חלקית הרי שסכימת OAEP תהיה בטוחה כנגד CCA2. הגדרה זו של פונקציה חד-כיוונית חלקית חזקה יותר מהגדרה של פונקציה חד-כיוונית רגילה. מסתבר שבשל תכונת ההומומורפיות של RSA היא נחשבת חד-כיוונית חלקית בהנחה שהיא חד-כיוונית. כמו כן שופ הוכיח פורמלית שאם המעריך (מפתח ההצפנה) של RSA שווה 3 סכימת RSA-OAEP בטוחה כנגד התקפת מוצפן נבחר מכל סוג, אולם יש הסבורים שמעריך קטן מהווה חולשה בפני עצמה לכן שופ הציע אלטרנטיבה משלו לסכימת OAEP והוכיח פורמלית שהיא בטוחה סמנטית כנגד התקפת מוצפן נבחר בהנחה שהפונקציה חד-כיוונית. הסכימה משתמשת בפונקציית יתירות משתנה $R(m,r)$ במקום בקבוע המכיל אפסים ואחד בסוף. סכימת OAEP+‎ מורכבת מרשת פייסטל בשני סבבים עם שלוש פונקציות $G,H,R$ כמתואר בתרשים:

s=(G(r)\oplus m)\ \|\ R(r\ \|\ m)

t=H(s)\oplus r

וההצפנה היא $c=f(s\ \|\ t)$ . הפונקציות המוטמעות בסכימה הן: $G:\{0,1\}^{k_{0}}\rightarrow \{0,1\}^{n}$ וכן $R:\{0,1\}^{n+k_{0}}\rightarrow \{0,1\}^{k_{1}}$ וכן $H:\{0,1\}^{n+k_{1}}\rightarrow \{0,1\}^{k_{0}}$ . הפונקציה $f$ היא פונקציה חד-כיוונית שהיא תמורה הפועלת על $k$ סיביות. הפרמטרים הנוספים מקיימים $k_{0}+k_{1}<k$ וכן הערכים $2^{-k_{0}}$ ו- $2^{-k_{1}}$ צריכים להיות זניחים. המסר הוא לכל היותר באורך $n$ סיביות כאשר $n=k-k_{0}-k_{1}$ .

סכימת SAEP

דן בונה הציע^[7] סכימת ריפוד דומה אך פשוטה יותר מזו של שופ והיא נקראת Simplified Asymmetric Encryption Padding. היא מתאימה להצפנת RSA או רבין. בסכימה זו אין מגבלה על המעריך, היא מורכבת מסבב בודד. אם המסר המיועד להצפנה הוא $m\in \{0,1\}^{n}$ ו- $r\in \{0,1\}^{k_{1}}$ הוא מחרוזת אקראית. הפונקציה $H:\{0,1\}^{k_{1}}\rightarrow \{0,1\}^{n+k_{0}}$ והפונקציה $G:\{0,1\}^{n+k_{1}}\rightarrow \{0,1\}^{k_{0}}$ הסכימה פועלת כדלהלן:

{\text{SAEP}}(m,r)=((m\ \|\ G(m\ \|\ r)\oplus H(r))\ \|\ r

פונקציית הריפוד המתוארת מבוצעת לפני ההצפנה, כדי להצפין מסר $m$ כלשהו באורך $n$ סיביות, תחילה בוחרים מחרוזת אקראית $r$ באורך $k_{1}$ סיביות ומחשבים את $y={\text{SAEP}}(m,r)$ ואז $C=y^{e}{\text{ mod }}N$ . אם הפרמטרים $n,k_{0},k_{1}$ נבחרו כראוי הסכימה מוכחת כבטוחה נגד התקפת מוצפן נבחר אדפטיבית במסגרת מודל אורקל אקראי.

ראו גם

לקריאה נוספת

אנציקלופדיה לקריפטוגרפיה ואבטחה

הערות שוליים

^ Bellare, M. and P. Rogaway (1995). "Optimal asymmetric encryption—how to encrypt with RSA." Advances in Cryptology—EUROCRYPT'94, Lecture Notes in Computer Science, vol. 950, ed. A. De Santi. Springer-Verlag, Berlin, 92-111
^ Bleichenbacher, D. (1998). "A chosen ciphertext attack against protocols based on the RSA encryption standard PKCS #1." Advances in Cryptology-CRYPTO'98, Lecture Notes in Computer Science, vol. 1462, ed. H. Krawazy. Springer-Verlag, Berlin, 1–12
^ Blum, M. and S. Micali (1984). How to generate cryptographically strong sequences of pseudorandom bits. SIAM Journal on Computing, 13, 850-864
^ Fiat, A. and A. Shamir (1987). "How to prove yourself: Practical solutions of identification and signature problems." Advances in Cryptology-CRYPTO’86, Lecture Notes in Computer Science, vol. 263, ed. A. Odlyzko. Springer-Verlag, Berlin, 186-194
^ Shoup, V. (2001). "OAEP reconsidered." Advances in Cryptology—CRYPTO 2001, Lecture Notes in Computer Science, vol. 2139, ed. J. Kilian. Springer-Verlag, Berlin, 239–259
^ Fujisaki, E., T. Okamoto, D. Pointcheval, and J. Stern (2001). "RSA–OAEP is secure under the RSA assumption." Advances in Cryptology-CRYPTO 2001, Lecture Notes in Computer Science, vol. 2139, ed. J. Kilian. Springer-Verlag, Berlin, 260–274
^ Boneh, D. (2001). "Simplified OAEP for the RSA and rabin functions." Advances in Cryptology-CRYPTO 2001, Lecture Notes in Computer Science, vol. 2139, ed. J. Kilian. Springer-Verlag, Berlin, 275–291.

[1] Bellare, M. and P. Rogaway (1995). "Optimal asymmetric encryption—how to encrypt with RSA." Advances in Cryptology—EUROCRYPT'94, Lecture Notes in Computer Science, vol. 950, ed. A. De Santi. Springer-Verlag, Berlin, 92-111

[2] Bleichenbacher, D. (1998). "A chosen ciphertext attack against protocols based on the RSA encryption standard PKCS #1." Advances in Cryptology-CRYPTO'98, Lecture Notes in Computer Science, vol. 1462, ed. H. Krawazy. Springer-Verlag, Berlin, 1–12

[3] Blum, M. and S. Micali (1984). How to generate cryptographically strong sequences of pseudorandom bits. SIAM Journal on Computing, 13, 850-864

[4] Fiat, A. and A. Shamir (1987). "How to prove yourself: Practical solutions of identification and signature problems." Advances in Cryptology-CRYPTO’86, Lecture Notes in Computer Science, vol. 263, ed. A. Odlyzko. Springer-Verlag, Berlin, 186-194

[5] Shoup, V. (2001). "OAEP reconsidered." Advances in Cryptology—CRYPTO 2001, Lecture Notes in Computer Science, vol. 2139, ed. J. Kilian. Springer-Verlag, Berlin, 239–259

[6] Fujisaki, E., T. Okamoto, D. Pointcheval, and J. Stern (2001). "RSA–OAEP is secure under the RSA assumption." Advances in Cryptology-CRYPTO 2001, Lecture Notes in Computer Science, vol. 2139, ed. J. Kilian. Springer-Verlag, Berlin, 260–274

[7] Boneh, D. (2001). "Simplified OAEP for the RSA and rabin functions." Advances in Cryptology-CRYPTO 2001, Lecture Notes in Computer Science, vol. 2139, ed. J. Kilian. Springer-Verlag, Berlin, 275–291.

[1]

[2]

[3]

[4]

[5]

[6]

[7]