הצגת המקור של הדף "מודל אורקל אקראי"

ב[[קריפטואנליזה]], '''מודל אורקל אקראי''' (Random oracle model) הוא [[פרדיגמה]] לבניית [[פרוטוקול קריפטוגרפי]] עם ביטחון מוכח שהוצעה לראשונה ב-1995 על ידי [[מיהיר בלייר]] מ[[אוניברסיטת קליפורניה בסן דייגו]] ו[[פיליפ רוגווי]] מ[[אוניברסיטת קליפורניה בדייוויס]]{{הערה|[http://cseweb.ucsd.edu/~mihir/papers/ro.pdf Bellare, Mihir and Philip Rogaway (1993). “Random oracles are practical: A paradigm for designing efficient protocols.”]}}. מודל אורקל אקראי מהווה מעין ממוצע בין מצב שבו קיימת הוכחת ביטחון מוצקה לפי [[המודל הסטנדרטי]] לבין מצב שלא קיימת הוכחה כלל. בעוד שהמודל אינו משקף את המציאות לגמרי, לפחות הוא מספק אמון רב יותר בביטחון הפרוטוקול על פי המודל, לעומת מצב שבו לא קיימת הוכחה כלשהי מעבר לעובדה שמפתחי האלגוריתם הצהירו כי לא מצאו שיטה טובה לשבירתו. או כפי שניסחו המחברים "מודל אורקל אקראי מהווה גשר בין [[קריפטוגרפיה]] תאורטית לבין קריפטוגרפיה מעשית".

==אורקל אקראי==
בקריפטוגרפיה מודרנית נוח להשתמש באובייקט תאורטי הנקרא [[אורקל (מדעי המחשב)|אורקל]]. אפשר לחשוב עליו כעל [[קופסה שחורה (הנדסה)|קופסה שחורה]] שמקבלת כקלט [[מחרוזת (מדעי המחשב)|מחרוזת]] בינארית ומחזירה מחרוזת בינארית. המבנה הפנימי של הקופסה "מסתורי" ואינו ידוע לאיש. כל אחד, כולל היריב רשאי להפעיל את הקופסה והיא פועלת כפונקציה המקבלת את <math>x</math> ומחזירה את <math>y</math>. בהקשר זה <math>x</math> נקרא [[שאילתה (תוכנה)|שאילתה]]. למען הפשטות מבלי לוותר על הכלליות מניחים כמה הנחות יסוד לגבי האורקל:
*המבנה הפנימי של האורקל אינו ידוע לאיש. כל מה שידוע הוא שאילתות שהוגשו עד עתה והתשובות שהתקבלו.
*'''פרטיות'''. כל שאילתה שמוגשת לאורקל פרטית במובן שרק האורקל ומגיש השאילתה יודעים מהי. זו הנחה טבעית כי במציאות הגשת שאילתה לאורקל מתאימה להפעלת פונקציית גיבוב באופן מקומי.
*'''עקביות'''. האורקל תמיד יחזיר את אותה תשובה <math>y</math> בהינתן אותה שאילתה <math>x</math>. כי למעשה רואים באורקל כביכול הוא מיישם פונקציה <math>H</math>. מסיבה זו אפשר להתייחס לאורקל כאל הפונקציה <math>H</math> עצמה.
*'''אקראיות'''. האורקל יקרא '''אורקל אקראי''' אם הפונקציה <math>H</math> נבחרה באקראי בהתפלגות אחידה מתוך כל הפונקציות הממפות <math>n</math> סיביות ל-<math>\ell(n)</math> סיביות. כאשר <math>x\in\{0,1\}^n</math> והפלט <math>H(x)\in\{0,1\}^{\ell(n)}</math>.

אפשר להתייחס לכל <math>H</math> כאל טבלה ענקית שמכילה עבור כל קלט אפשרי את הפלט המתאים. בכל טבלה <math>2^n\cdot \ell(n)</math> סיביות בסך הכול ובתחום כולו קיימות בסך הכול <math>2^{\ell(n)\cdot 2^n}</math> פונקציות שונות עם קלט ופלט באורך המצוין. דרך אחרת היא להתייחס ל-<math>H</math> כאל פונקציה אקראית בתנאי אחד, עבור כל <math>x</math> הפונקציה בודקת תחילה אם הופיע בעבר, אם לא היא מחזירה <math>y</math> אקראי ושומרת את הזוג <math>x</math> ו-<math>y</math> במסד נתונים כלשהו. אם <math>x</math> כבר מופיע במסד הנתונים של הפונקציה משמע שכבר הוגשה שאילתה עם <math>x</math> זה ולכן היא תחזיר את <math>y</math> המתאים השמור במסד הנתונים.

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

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

רעיון מודל אורקל אקראי מנסה לגשר על הפער הזה על ידי תוספת אורקל אקראי. באופן תאורטי נוספת לפרוטוקול פונקציה אקראית <math>H</math> שניתנת להערכה רק באמצעות שאילתה לאורקל שמקבל <math>x</math> כלשהו ומחזיר את <math>H(x)</math> באופן אקראי. אמנם הפונקציה לא מציאותית אך היא מספקת שיטה לפיתוח ובדיקה של פרוטוקול קריפטוגרפי בשני מהלכים, לפי הגישה הבאה:
*תחילה שיטת ההצפנה מפותחת ומוכחת כבטוחה במסגרת מודל אורקל אקראי. כלומר מניחים שקיים אורקל אקראי מדומה ומנסים לבנות אלגוריתם בהתבסס על הנחה זו ומוכיחים שהוא בטוח מבחינה תאורטית. מבלי להוציא מהכלל הוכחות סטנדרטיות בדרך מקובלת כפי שנהוג.
*בשלב השני כאשר מנסים ליישם את הפרוטוקול בפועל כיוון שאורקל אקראי לא קיים במציאות מנסים להחליפו בפונקציית גיבוב מתאימה (למשל וריאציה של [[SHA-2]]). כך שבכל נקודה בפרוטוקול שבה מופיעה שאילתה לאורקל אקראי עם <math>x</math>, היא תוחלף בפונקציית הגיבוב <math>\hat H(x)</math>.

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

===ביקורת===
לטענת מבקרים סקפטיים של הרעיון היות שהפונקציה המחליפה בפועל אינה רנדומלית אמיתית, ההוכחה אינה משיגה מאומה. נותרת השאלה האם ההוכחה תהיה תקפה כאשר מחליפים את <math>h</math> בפונקציה מעשית. אפשר להביט בזה בדרך אחרת, לעיתים נוח לקריפטאנליסט לצורך ניתוח פרוטוקול המשלב פונקציה מ[[תורת המספרים]] ופונקציית גיבוב כלשהי <math>h</math> (כמו [[RSA]] עם [[SHA-2]]), להתייחס אל האחרונה כאל פונקציה אקראית. התקפה בסגנון כזה כנגד הפרוטוקול נקראת 'גנרית' במובן שאינה מניחה הנחות מוקדמות כלשהן לגבי <math>h</math> וזה בדיוק המצב בו רעיון האורקל האקראי יכול להיות שימושי. כלומר המודל מאפשר לפחות להוכיח שהתקפה גנרית כזו תכשל אלא אם כן הפונקציה מתורת המספרים אינה כפי שהיא מתיימרת. יש המכנים זאת הוכחה ברדוקציית קופסה שחורה. אך יש להיזהר בפועל בבחירת הפונקציה <math>h</math> שחשוב שתהיה 'עצמאית' ביחס לפרוטוקול, או במילים אחרות שהפרוטוקול עצמו אינה מתייחס אליה בדרך כלשהי.

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

[[רן קנטי]], [[עודד גולדרייך]] ו[[שי הלוי]] (1998){{הערה|[http://eprint.iacr.org/1998/011.pdf Canetti, Ran, Oded Goldreich, and Shai Halevi (1998). “The random oracle methodology, revisited.”]}} ביקרו את רעיון מודל האורקל האקראי והשימוש בפונקציות גיבוב קריפטוגרפיות ליישומו והוכיחו שקיים פרוטוקול שנקרא בטוח תחת מודל אורקל אקראי אך כל ניסיון ליישמו על ידי החלפה מפונקציה תאורטית בפונקציה מעשית, מניב סכמה לא בטוחה. הם מסכמים בהצעות משלהם ליישום בטוח של המודל ומציינים מספר מגבלות. יש הסבורים שהסיטואציה שהעלו קצת מלאכותית ולא סביר שתקרה במנגנונים קריפטוגרפיים אמיתיים.

==תיאור המודל==
באופן כללי קיים פער בין תאורטיקנים בתחום ההצפנה לבין המיישמים בפועל. מהיבט תאורטי [[פונקציה חד כיוונית]] היא הבסיס למבנים קריפטוגרפיים מורכבים יותר כמו [[פונקציה פסבדו-אקראית קריפטוגרפית|פונקציה פסאודו-אקראית]] (PRF). מנקודת ראות תאורטית אין משקל ליעילות, לכן ניסיון להגיע לביטחון מוכח עשוי לבוא על חשבון יעילות. אולם מהיבט מעשי קיימים אלגוריתמים יעילים מאוד כמו [[AES]] או SHA-2 שנחשבים לפונקציה פסאודו-אקראית אם כי לא קיימת הוכחה פורמלית כלל. הפתרון שמוצע לפי המודל הזה הוא לראות ב-SHA-2 כפונקציה אקראית רק לצורך הדיון. כלומר נניח שקיימת פונקציה אקראית <math>h</math> ונניח שקיימת בעיה (משימה) <math>\Pi</math> שאותה מנסים לפתור באמצעות פיתוח פרוטוקול מתאים, ושהיא נפרדת ובלתי תלויה בפונקציה <math>h</math>. נתון אורקל אקראי המסומן בקיצור <math>R : \{0,1\}^*\rightarrow \{0,1\}^\infty</math>. כלומר הוא מקבל כקלט מחרוזת כלשהי באורך לא מוגדר ומחזיר מחרוזת אקראית אמיתית כלשהי. כדי להמציא פרוטוקול <math>P</math> שפותר את הבעיה האמורה אפשר לפעול כדלהלן:

א. מנסחים הגדרה פורמלית לבעיה <math>\Pi</math> בסביבה שבה כל המשתתפים כולל יריב אפשרי נגישים לאורקל <math>R</math>.

ב. מתכננים פרוטוקול יעיל <math>P</math> לבעיה האמורה בסביבה זו.

ג. מוכיחים ש-<math>P</math> אכן פותר את הבעיה.

ד. מחליפים את האורקל <math>R</math> בפונקציה <math>h</math>.

ההוכחה שניתנת בשלב (ג) נכונה רק במסגרת מודל האורקל האקראי והיא אינה בהכרח נכונה בסיום התהליך, הביטחון כאן מבוסס על ההנחה ההיוריסטית ש-<math>h</math> בטוחה. זו לא הוכחה מוחלטת אך שימושית מבחינה מעשית. כאשר מחליפים את <math>R</math> בפונקציה קונקרטית כלשהי יש להיזהר משתי מלכודות אפשריות. הראשונה, הפונקציה צריכה להיות 'טובה', כלומר שלא ידוע על התקפות מוצלחות נגדה וכן שהיא מתאימה ליישום במסגרת המודל. השנייה היא שאין להסתמך על מאפיינים ספציפיים במבנה הפנימי של הפונקציה כך שהיא צריכה להיות עצמאית ונפרדת מהפרוטוקול. [[פונקציית גיבוב קריפטוגרפית]] כשלעצמה לא מתאימה ליישום בטוח במסגרת מודל אורקל אקראי מסיבות אילו. אך ישנן כמה גרסאות מתאימות, למשל שימוש בפלט חלקי של פונקציית גיבוב או שימוש בה בדרך לא סטנדרטית.

ככלל [[הצפנה אסימטרית]] יעילה ומוכחת עלולה להיות משימה קשה לפי מודל [[סיבוכיות]] סטנדרטי, אך מעשית יותר במסגרת מודל האורקל האקראי. המקור לרעיון החל בעבודה של גולדרייך [[שפרירה גולדווסר|גולדווסר]] ו[[סילביו מיקאלי|מיקאלי]]{{הערה|1=[http://dl.acm.org/citation.cfm?id=6503 O. Goldreich, S. Goldwasser and S. Micali, "How to construct random functions," Journal of the ACM, Vol. 33, No. 4, 210-217, (1986).]}} (1986) שהגדירו את המושג פונקציה פסאודו-אקראית והראו איך ליישמה באופן בטוח. וכן [[עמוס פיאט|פיאט]] ו[[עדי שמיר|שמיר]] שהראו איך להפוך את [[פרוטוקול פייגה-פיאט-שמיר|פרוטוקול אימות פיאט-שמיר]] ל[[חתימה דיגיטלית]] וכן [[מנואל בלום]] שהעלה רעיון דומה להפוך כל [[מערכת הוכחה אינטראקטיבית]] כמו [[הוכחה באפס ידיעה]] להוכחה לא אינטראקטיבית. כולם משתמשים ברעיון האורקל האקראי בשילוב עם פונקציות גיבוב או מחולל פסאודו-אקראי כבסיס תאורטי.

==יישום מעשי==
{{ערך מורחב|סכמת ריפוד אסימטרית אופטימלית}}
לדוגמה נתון מחולל פסאודו-אקראי <math>G : \{0,1\}^*\rightarrow \{0,1\}^\infty</math> ונתונה פונקציית גיבוב <math>H : \{0,1\}^*\rightarrow \{0,1\}^k</math> כאשר <math>k</math> הוא פרמטר ביטחון. <math>f</math> היא [[תמורה פסאודו-אקראית]] עם 'דלת צונחת' יחד עם הפונקציה ההופכית שלה <math>f^{-1}</math> המשמשות להצפנה ופענוח עם מפתחות מתאימים (למשל [[RSA]]). הביטוי <math>G(r)\oplus x</math> פירושו פעולת [[XOR]] של <math>x</math> עם <math>|x|</math> הסיביות הראשונות של תוצאת הפונקציה <math>G</math> עם הקלט <math>r</math> והסימן "<math>\|</math>" מייצג שרשור. להלן שתי סכימות להצפנה בטוחה תחת מודל אורקל אקראי:

#<math>E^G(x)=f(r) \ \| \ G(r)\oplus x</math>
#<math>E^{G,H}(x)=f(r) \ \| \ G(r)\oplus x \ \| \ H(rx)</math>

כאן <math>x</math> הוא המסר המיועד להצפנה ו-<math>r</math> הוא מספר אקראי חד פעמי שנבחר מתוך התחום של <math>f</math> לצורך הצפנת המסר <math>x</math>. הפונקציה <math>f</math> היא הצפנת [[מפתח ציבורי]] והיא משתמשת במפתח הפומבי של המקבל. הטענה היא שהשיטה הראשונה מספקת [[ביטחון סמנטי]] פולינומי לפי הרעיון של מיקלי וגודלווסר שנקרא [[הצפנה הסתברותית]]. והשנייה טובה כנגד [[התקפת מוצפן-נבחר]] ונקראת [[חשילות (קריפטוגרפיה)|אי-חשילה]] ושתיהן יעילות יותר מסכימות הצפנה שהן בעלות ביטחון מוכח לפי מודל סטנדרטי כמו [[הצפנת בלום-גולדווסר]]. לעומת זאת החיסרון בשיטות המתוארות כאן שהצופן המתקבל גדול יותר בערך פי שניים מהטקסט המקורי.

הצעה טובה יותר של בלייר ורוגווי נקראת OAE{{הערה|[https://cseweb.ucsd.edu/~mihir/papers/oae.pdf Optimal Asymmetric Encryption - How to Encrypt with RSA]}} קיצור של Optimal Asymmetric Encryption היא כדלהלן:
:<math>E^{G,H}(x)=f(x\oplus G(r) \ \| \ r\oplus H(x\oplus G(r)))</math>
שיטה זו 'אופטימלית' במובן שהיא יעילה כמו הקודמות והתוצאה נשמרת בגודל כמעט זהה וניתנה הוכחה לביטחונה במסגרת מודל אורקל אקראי כמו כן נוספה הגדרה שנקראת plaintext-aware שאומרת שהסכמה בטוחה באופן כזה שלא ניתן לייצר טקסט מוצפן תקף שפונקציית הפענוח תקבל מבלי לדעת את הטקסט המקורי. על בסיס הרעיון הזה עודכן תקן PKCS שבו נוספה סכימת ריפוד שנקראת RSA-OAES. ההוכחה שניתנה על ידי המחברים לא הייתה נכונה כפי שהתברר על ידי [[ויקטור שופ|שופ]]{{הערה|[http://www.shoup.net/papers/oaep.pdf 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]}}. למרות זאת מסתבר שהגרסה שמשתמשת ב-RSA למרות זאת בטוחה וזאת בעיקר בגלל תכונת [[הומומורפיזם|ההומומורפיות]] של RSA.

==ראו גם==
* [[ריפוד אופטימלי להצפנה אסימטרית]]

==הערות שוליים==
{{הערות שוליים|יישור=שמאל}}

{{קריפטוגרפיה}}

[[קטגוריה:קריפטוגרפיה]]