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, כאשר משתמשי הקצה הם בדרך כלל מכשירים המוגבלים במשאבים וברוחב פס.

פרוטוקול MQV

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

פרוטוקול HMQV

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

ביטחון

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

התקפת שיתוף לא ידוע

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