אור דונקלמן

פרס קריל 2014
אוניברסיטת חיפה

ד"ר אור דונקלמן (Dr. Or Dunkelman) 
תחומי מחקר: קריפטאנליזה של פרימטיביים סימטריים

תמצית מחקר:

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

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

המחקרים שאני עורך ניתנים לחלוקה לכמה קטגוריות – בחינת חוזק של פרימטיב מסוים (לדוגמא, הצופן KASUMI אשר משמש באבטחת התקשורת בטלפונים סלולריים של הדור השלישי, או צופן ה-AES שהוא תקן ההצפנה החדש שבנמצא בשימוש נרחב מאז 2001), בחינת משפחות של פרימטיביים (לדוגמא, פונקציות תמצות המבוססות על מבנה Merkle-Damgard), או פיתוח טכניקות קריפטאנליטיות חדשות (כמו התקפות ה-Rectagnle או התקפת ה-Dissection שפיתחנו לאחרונה).
אחד המחקרים האחרונים בהם הייתי מעורב היה פיתוחה של התקפת ה-Dissection. אחת מהדרכים להוספת בטיחות היא השימוש בהצפנה כפולה, כלומר, לוקחים את המידע, מצפינים אותו פעם אחת, ואז מצפינים פעם נוספת. עם זאת, כבר משנות ה-70, אנחנו יודעים שלהצפנה כפולה אין את החוזק שהיינו מצפים ממנו (החוזק של הצפנה כפולה הוא כהצפנה בודדת). לכן, במשך שנים השתמשו בהצפנה משולשת (כלומר הצפנה של התוצאה של הצפנה כפולה), אשר מעניקה את הבטיחות שהיינו מצפים לקבל מהצפנה כפולה. במשך שנים חשבו כי תוספת שכבות הצפנה מוסיפה אבטחה. עם זאת, ע"י פיתוח שיטת התקפה חדשה לחלוטין, הצלחנו להראות שתוספת השכבה הרביעית, לא מוסיפה בטיחות (כך שתקיפה של ארבע שכבות הצפנה שקולה לתקיפה של שלוש שכבות). מלבד ההשלכות בתחום ההצפנה של השיטות שפיתחנו (שמאשפרות גם להשפיע על הצפנה מחומשת, משושה, וכו'), האלגוריתם שפיתחנו מאפשר לנו גם לפתור קוביה הונגרית!

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

זוכי פרס קריל

// order posts by year $posts_by_year;