MQV

MQV (קיצור של Menezes-Qu-Vanstone) הוא פרוטוקול שיתוף מפתח קריפטוגרפי עם אימות, שפותח ב-1998 על ידי אלפרד מנזס וסקוט ונסטון מאוניברסיטת ווטרלו, מינגהו קו מחברת Certicom, בשיתוף עם לורי לאו וג'רי סולינס מה-NSA. פרוטוקול MQV מבוסס על פרוטוקול דיפי-הלמן, הוא היעיל ביותר מסוגו וניתן להפעילו בכל חבורה ציקלית סופית, במיוחד בחבורת עקום אליפטי (במקרה זה מסומן בקיצור ECMQV). כמו כן קיימות שתי וריאציות נוספות של הפרוטוקול; העברת מפתח מאומת במהלך יחיד, המתאים לסביבה בה רק צד אחד מקוון וכן העברת מפתח בשלושה מהלכים המספק אימות דו צדדי.

הפרוטוקול מפורט בתקן SEC 1 של איגוד SECG (שנוסד על ידי סרטיקום) ושולב בתקן IEEE P1363, בתקנים ANSI X9.63, X9.42 וכן RFC-5656 של IETF. כמו כן נכלל על ידי NSA בחבילה הקריפטוגרפית Suit B לפי המלצות NIST SP 800-56A. ייתכן שכמה מגרסאות הפרוטוקול מוגנות בפטנט. גרסאות מתקדמות של הפרוטוקול אטרקטיביות במיוחד להצפנת תקשורת אלחוטית ברשתות מקומיות כמו IEEE 802.11 או לטווחים בינוניים כמו WiMAX, כאשר משתמשי הקצה הם בדרך כלל מכשירים המוגבלים במשאבים וברוחב פס.

רקע

פרוטוקול שיתוף מפתח

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

החסרון בפרוטוקול דיפי הלמן במתכונתו המקורית שהוא אינו מספק אימות זהויות ולכן חשוף להתקפת אדם באמצע. אפשר להוסיף מרכיב אימות על ידי חתימה דיגיטלית או תעודת מפתח ציבורי החתומה על ידי רשות מאשרת. משיקולי יעילות נעשו מאמצים לפתח פרוטוקולים המספקים אימות עקיף כחלק אינטרגלי ללא צורך בתהליכים נפרדים ובהתערבות צד שלישי. אפשר לחלק את מרכיב האימות לשני סוגים, שיתוף מפתח מאומת שבו צד אחד משתף ומאמת מפתח עם צד אחר, כך שהוא מקבל אישור לזהותו של המשתתף האחר (כיוון אחד) ונקרא בקיצור AK וכן "שיתוף מפתח מאומת עם אישור", שבנוסף מאשר את זהות השרת כלפי הלקוח (דו כיווני) שנקרא בקיצור AKC (קיצור של Authenticated Key agreement with Confirmation).

בסיום הפרוטוקול יכולים המשתתפים הלגיטימיים להיות סמוכים ובטוחים שמלבדם אין איש יודע מהו המפתח הסודי המשותף. בעיקרון אפשר להשתמש בו כמפתח הצפנה להצפנת ההתקשרות ביניהם. מטעמי ביטחון מומלץ לא להשתמש בו ישירות אלא לגזור ממנו מפתח אחר באמצעות פונקציית גזירת מפתח (Key derivation function) בקיצור KDF. המפתח הסודי המשותף שנגזר בסופו של דבר נקרא מפתח שיחה, כשמו הוא נועד להתקשרות אחת או מספר התקשרויות מוגבל כשלאחריהן מושמד.

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

מאפיינים
פרוטוקול שיתוף מפתח קריפטוגרפי בטוח אמור להתמודד עם התקפות פסיביות, שבהן התוקף מנסה לנחש את המידע הסודי על ידי התבוננות בחילופי המהלכים. ההנחה היא שמסרי הפרוטוקול מועברים בערוץ הפתוח שניתן לציתות על ידי כל גורם עם ציוד מתאים. וכן נגד התקפות אקטיביות בהן התוקף יכול גם ל'הזריק', ליירט, למחוק, לשנות ואו לשכפל מסרים. ביתר פירוט הפרוטוקול אמור לסכל את ההתקפות הבאות:
מפתח ידוע (known-key); הפרוטוקול ייוותר בטוח נוכח מצב שבו נחשפו לעיני התוקף מפתחות שיחה אחרים (שנוצרו בעבר על ידי הפרוטוקול).
שמירת סודיות קדימה (forward secrecy) או סודיות מושלמת קדימה; גם אם מפתח ארוך-טווח של אחד המשתתפים נחשף, הדבר לא ישפיע על סודיות מפתחות שיחה שנוצרו לפני החשיפה.
מניעת התחזות (impersonation); במצב שבו המפתח הפרטי של אחד המשתתפים ידוע לתוקף לא יתאפשר לו לעשות בו שימוש כדי להתחזות לאחרים כלפי משתמש זה (ברור שבמקרה כזה התוקף מסוגל להתחזות למשתמש הלגיטימי הזה כלפי אחרים כיוון שהמפתח הפרטי מייצג בעצם את זהותו, אך ההפך אינו מחויב המציאות ואף רצוי למנוע).
שיתוף לא ידוע (unkown key-share); התוקף לא יצליח לגרום למשתתף אחד לשתף איתו מפתח סודי בעוד שהלה סבור בטעות ששיתף מפתח עם מישהו אחר (כלומר צד אחד מאמין נכון שהוא משתף מפתח עם מישהו שהוא מכיר בעוד שהצד השני למעשה משתף בלא ידיעתו מפתח עם התוקף וסבור שהוא מישהו אחר).
שליטה; אף אחד מהצדדים לא יוכל לאלץ את מפתח השיחה שיהיה ערך כלשהו לפי בחירתו.
יעילות; מספר המהלכים צריך להיות המינימלי האפשרי וכן תעבורת רשת נמוכה (סך כל הסיביות ששודרו).

אפשר לממש את פרוטוקול MQV בתת-חבורה של החבורה הציקלית  מסדר ראשוני, למשל המפתח הפרטי הוא השלם  והציבורי הוא  כאשר  יוצר של השדה. במקרה זה המפתחות צריכים להיות בגודל של מעל 2000 ספרות בינאריות לעומת זאת יש יתרון ביישום הפרוטוקול בעקום אליפטי מכיוון שהוא מציע ביטחון זהה עם מפתח קצר משמעותית (בין 160 ל-512 סיביות נכון לשנת 2015). מסיבה זו תיאור הפרוטוקול מתמקד בעקום אליפטי. מניחים שהפרמטרים הציבוריים של העקום ידועים לכל המשתתפים. וכן כל מפתח ציבורי  (שהוא נקודה בעקום) מאומת ונבדק שהוא עומד בהגדרות המערכת. בבדיקה מוודים ש:
 אינו שווה  (הנקודה באין סוף).
הקואורדינטות  הם אלמנטים של השדה .
 מקיים את משוואת העקום.

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

פרוטוקול דיפי-הלמן הבסיסי בעקום אליפטי (ללא אימות)
פרוטוקול דיפי-הלמן בעקום אליפטי ללא אימות (נקרא בקיצור ECDH) אנלוגי לפרוטוקול דיפי הלמן בחבורה רגילה. נתונים פרמטרי התחום של העקום לפי הגדרות התקן: , העקום האליפטי הוא  כאשר  הסדר של השדה  וכן  מקדמים של משוואת העקום,  היא נקודת הבסיס,  הסדר הראשוני של נקודת הבסיס,  פקטור משלים כך שמתקיים  ו- מייצג את מספר הנקודות בעקום .

המשתתפת  עם מפתח סודי שהוא שלם אקראי  והמפתח הציבורי  (תוצאת כפל סקלארי של נקודת הבסיס  ב-) מסומנת בקיצור  והמשתתף  עם מפתחות  בהתאמה, רוצים לשתף ביניהם סוד , תחילה הם מחליפים ביניהם מפתחות ציבוריים ואז מחלצים את הסוד המשותף כדלהלן:

היות שמתקיים , הסוד המשותף הוא הנקודה .

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

פרוטוקול 1 - שיתוף מפתח עם אימות בשני מהלכים

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

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

לעומת פרוטוקול דיפי הלמן הבסיסי שבו . כמו כן כדי לשפר יעילות הביטוי  מנצל רק מחצית מסיביות הקואורדינטה  של הנקודה, זאת כדי להקל על פעולות הכפל הסקלארי בסעיפים 3 ו-5 והכפל ב- נועד להבטיח שהסוד המשותף  יהיה נקודה בתת-חבורה מסדר  בעקום האליפטי. כמו כן היות שאת  אפשר לחשב מראש יוצא שכל צד מבצע רק 1.5 פעולות כפל סקלארי און ליין.

פרוטוקול 2 - שיתוף מפתח עם אימות במהלך אחד
המטרה היא ש- ו- ישתפו מפתח סודי על ידי מהלך יחיד מ- ל-. מצב זה רצוי במקרה שרק משתמש אחד מקוון כמו ביישומי דואר אלקטרוני. הפרוטוקול הוא כדלהלן:

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

פרוטוקול 3 - שיתוף מפתח מאומת עם אישור דו צדדי
הגרסה הזו של פרוטוקול 1 מנצלת פרימיטיב קריפטוגרפי נוסף שמספק אימות כמו MAC כדי לבצע אימות ואישור דו צדדי. וכן בפרוטוקול הבא הערכים  ו- הם פונקציית לגזירת מפתח. למשל אם הערך הוא  אפשר לממש פונקציית גיבוב בטוחה כמו SHA-2 של  כשהוא משורשר עם ערך נוסף, כך  וכן .

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

כאמור ביטחון הפרוטוקול היוריסטי בלבד, כולל את כל התכונות המצוינות לעיל ויעיל במיוחד.

פרוטוקול HMQV
ב-2005 פרסם הוגו קרווציק מאמר שבו הוא מבקר את ביטחון MQV תחת מודלים של ביטחון ידועים ומציין שהתגלו על ידו כמה חולשות בפרוטוקול. אף על פי שהפרוטוקול זכה לפופולריות רבה וה-NSA הכליל אותו ברשימה הנבחרת של אלגוריתמים שעברו בדיקה של קריפטאנליסטים מקצועיים, הרי שלא ניתנה הוכחה פורמלית לביטחונו במונחים של ביטחון סמנטי לפי מודל סיבוכיות סטנדרטי או במסגרת מודל אורקל אקראי. הוגו הציע לתקן את הליקויים שמצא על ידי אלגוריתם משופר משלו שנקרא HMQV שפועל עם פונקציית גיבוב ומציע יעילות דומה למקורי ועם ביטחון מוכח. אלפרד מנזס ביקר את ממצאיו של הוגו וטען כי HMQV אינו בטוח יותר ומציג התקפה ריאליסטית במודל קנטי-קרווציק שבה אפשר לחשוף את המפתח הפרטי של המשתתפים. וכן מצא לדבריו שגיאות קריטיות בהוכחות המתמטיות שהובאו על ידי קרווציק. התיקון שהציע מנזס נקרא HMQV-1 והוא גרסה מתוקנת שעמידה בפני ההתקפה המצוינת (אולם בשל התיקון אינה מהירה יותר מהמקורית). קרווציק הגיב על טענות מנזס במאמר משלו וסתר חלק מהן.

חלק מהוויכוח מתמקד סביב הבדיקה שנקראת G-test, כלומר במהלך הפרוטוקול המקורי בוצע הכפל ב- כדי להבטיח שהתוצאה שייכת לתת-חבורה  מסדר  וכי לא נבחר בכוונה תחילה ערך מתת חבורה קטנה יותר שעלולה להפוך את הפרוטוקול ללא בטוח כי התוקף יכול להפעיל כוח גס אם ידוע לו שהמפתח נמצא בטווח אחר קטן משמעותית מהמצופה. ב-HMQV הבדיקה הזו הוסרה לטובת יעילות בטענה שאינה מוסיפה לביטחון האלגוריתם לפי מודל אורקל אקראי. על כל פנים, הוספת פונקציית גיבוב לפרוטוקול MQV כפי שהציע קרווציק מקובלת כיום כיוון שהיא יעילה למדי ואינה מסכנת את ביטחון הפרוטוקול.

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

כעת שני המשתתפים מחלצים את הסוד המשותף

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

ב-2001 ביקרו רוגווי, בלייר ובונה את הפרוטוקול כפי שהתקבל לתקן SEC-1 והעלו כמה נקודות שראוי להיזהר בהן, תיארו כמה התקפות אפשריות כנגד הפרוטוקול וציינו שהאיומים אינם פטאליים והפרוטוקול טוב לדעתם אם כי יש צורך להגדיר במדויק את יעדי הפרוטוקול באופן שיאפשר להעריך את ביטחונו, מה שלא נעשה בתקן למעט כמה הערות כלליות. כמו כן מציינים שהפרוטוקול יכול להיות בטוח רק במסגרת שבה כל משתמש מחזיק במפתחות הצפנה ארוכי טווח ובמפתחות ארעיים חד פעמיים, מסיבה זו פרוטוקול 2 לא בטוח.

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

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

הערות שוליים

קריפטוגרפיה