בעיית הפצת מפתחות

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

שמירת מפתחות הצפנה בסוד מחייבת הפעלת אמצעים קריפטורפיים או פיזיים כמו כספת כדי להגן עליהם מפני חשיפה. בעיה זו מחריפה אף יותר כאשר מספר המשתתפים גדול. לצורך המחשה, כאשר 15 משתמשים מעוניינים לנהל התקשרות בטוחה ביניהם, הם צריכים בסך הכול 105 מפתחות, כשכל משתמש צריך להחזיק ב-14 מפתחות. מספר זה גדל באופן מעריכי ככל שמספר המשתתפים עולה. בניסוח כללי, עבור רשת של $n$ משתמשים נדרשים בסך הכול $\textstyle {n \choose 2}={\frac {n(n-1)}{2}}$ מפתחות. ברשת מרובת משתמשים אין שום דרך מעשית לאחסן מספר כה גדול של מפתחות בסודיות.

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

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

הגדרה כללית

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

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

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

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

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

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

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

פתרונות

קיימות שתי דרכים עיקריות לשיתוף מפתח.

הצפנה סימטרית עם מפתח משותף

• צד שלישי נאמן (trusted third party). צד שלישי הנקרא בהקשר זה KDC - קיצור של key distribution center. הוא שרת ייעודי שתפקידו לייצר ולהפיץ מפתחות הצפנה סודיים עבור כל המשתמשים ברשת. תחילה המשתמשים משתפים מפתח הצפנה סודי עם שרת ה-KDC כל אחד מהם בנפרד והוא מצידו מנהל רשימה ארוכת טווח של מפתחות סודיים של כל המשתמשים הרשומים. לאחר מכן לפי דרישה, מפיק ושולח מפתח שיחה זמני וחד פעמי, כשהוא מוצפן תוך שימוש במפתחות ההצפנה המתאימים למשתמשים שמעוניינים להתקשר ביניהם ובגמר השימוש בו המפתח מושמד.
  • היתרונות בשיטה; כל משתמש נדרש לזכור רק מפתח סודי אחד ארוך טווח, אותו הוא משתף עם שרת המפתחות. הוספה או הסרה של משתמש מתבצעת מול שרת המפתחות בלבד. אין צורך ליצור קשר עם משתמשים אחרים.
  • חסרונות השיטה; במקרה ששרת המפתחות מותקף, כל המפתחות בסכנה. אם ההתקפה מצליחה כל המשתמשים חשופים לחלוטין. כאשר שרת המפתחות קורס מסיבה טכנית כלשהי התקשורת נעצרת לחלוטין.
  • דוגמה מעשית. פרוטוקול קרברוס הוא פרוטוקול העברת מפתח מעשי וחינמי שהומצא ב-MIT ונועד לשיתוף מפתחות הצפנה על ידי צד שלישי נאמן המשמש כשרת מפתחות. הפרטוקול פופולרי מאד והוא בשימוש נרחב במערכות ההפעלה חלונות ומקינטוש.

הצפנה א-סימטרית

• הצפנת מפתח ציבורי. ב-1976 פרסמו ויטפילד דיפי ומרטין הלמן מאמר מפורסם בשם "new directions in cryptography" בו הם הסבירו לראשונה אסטרטגיה שונה להפצת מפתחות שנקראה לאחר מכן בשם פרוטוקול דיפי-הלמן. השיטה מבוססת על פרדיגמה שנקראת "מפתח ציבורי" או "הצפנה א-סימטרית". כל משתמש מייצר שני מפתחות, האחד פרטי וסודי והשני ציבורי. ההצפנה מתבצעת עם המפתח הציבורי והפענוח עם המפתח הפרטי. לכל מפתח פרטי קיים מפתח ציבורי אחד ויחיד שמתאים לו. כך שאם מתבצעת ההצפנה במפתח הראשון, ניתן לפענח את התוצאה עם המפתח השני ולהיפך. בדרך זו המשתמשים יכולים לפרסם ברבים את מפתחות ההצפנה הציבוריים שלהם, כך שיהיו נגישים לכל. כאשר אליס מעוניינת להתקשר עם בוב אף שמעולם לא פגשה בו, כל שעליה לעשות הוא להשיג את המפתח הציבורי של בוב מהרשימה הציבורית, להפיק מפתח שיחה חד פעמי ולהצפינו באמצעותו ולשולחו לבוב בערוץ הפתוח. רק בוב יכול לפענח את המסר, לחלץ ממנו את מפתח השיחה הסודי ואיתו להתקשר עם אליס בצורה בטוחה. קיימת הבחנה בין המפתחות הציבוריים הארעיים (ephemeral key) שנוצרים לצורך הפרוטוקול ומשמשים להכנת מפתח השיחה לבין המפתחות ארוכי-טווח שברשות המשתתפים שנועדו לאימות זהותם. בדרך כלל רצוי שההמשתתפים בפרוטוקול יאמתו את המפתחות הציבוריים ארוכי הטווח שלהם. ישנן שתי דרכים לכך, האחת אימות מוקדם באמצעות צד שלישי כמו רשות אישורים, זאת בטרם יחלו במהלכי הפרוטוקול. והשני שילוב חתימה דיגיטלית בכל מסרי הפרוטוקול.
  • יתרונות השיטה; המשתמשים אינם צריכים להפגש כלל ואין צורך בניהול והחזקה של מספר גדול של מפתחות. הצטרפות או הסרה של משתמש אינן דורשות מאמץ מיוחד, כל שיש לעשות הוא להוסיף או להסיר את המשתמש המתאים ברשימה הציבורית. כל שיחה מתבצעת עם מפתח טרי וחד פעמי אותו משמידים בגמר השיחה.
  • חסרונות השיטה; עדיין נדרש תהליך אימות כדי לוודא שמפתח ציבורי שייך למי שמתיימר להיות בעליו. כל ניסיון מוצלח להונות משתמשים אחרים באמצעות מפתחות מזויפים יכול להביא לפריצת הרשת לחלוטין.
  • דוגמה מעשית. RSA היא שיטת הצפנה א-סימטרית מעשית שנמצאת בשימוש נרחב בכל מערכת הצפנה מודרנית והיא מנוצלת בעיקר להעברת מפתחות הצפנה.

חתימה דיגיטלית

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

• קוד אימות מסרים העושה שימוש בצופן בלוקים או פונקציית גיבוב כדי לייצר הצפנה מאומתת.

דוגמאות מעשיות אפשר למצוא למכביר; כמו CBC-MAC או HMAC. או בשיטות מתקדמות יותר כמו OCB או GCM.

• חתימה דיגיטלית.

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

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

הגדרה פורמלית של ביטחון פרוטוקול שיתוף מפתח

אליס ובוב מעוניינים לשתף ביניהם מפתח הצפנה סודי באמצעות פרוטוקול שיתוף מפתח $\Pi$. פרמטר ראשון שעליהם להסכים הוא $1^{n}$ (אורך המפתח בסיביות). כל אחד מהם מטיל מטבע במספר הפעמים הדרוש כדי לייצר מחרוזת אקראית באורך $n$ ומריץ את הפרוטוקול בערוץ פתוח שנתון לציתות. בגמר הפרוטוקול אליס ובוב מפיקים מפתחות הצפנה סודיים $k_{A},k_{B}\in \{0,1\}^{n}$ בהתאמה. ולצורך הנכונות, הפרוטוקול הסתיים בהצלחה אם $k_{A}=k_{B}$ בכל הטלת מטבעות והרצה של הפרוטוקול. במילים אחרות אליס ובוב כעת משתפים ביניהם מפתח סודי, כאשר בהגדרה המצותתת איב לא תוכל לנחש בזמן פולינומי מהו מתוך התבוננות במהלכי הפרוטוקול.

ביטחון הפרוטוקול מוגדר במונחים של ניסוי אותו אפשר לתאר בקיצור: ${\text{KE}}_{{\mathcal {A}},\Pi }^{\text{eav}}(n)$.

הסבר: אליס ובוב מריצים את הפרוטוקול $\Pi$ בנוכחות איב (eavesdropper) המוצתתת להם ומסומנת בקיצור ${\text{eav}}$ כשבידי כל אחד מהם מחרוזת סיביות אקראית בגודל $1^{n}$. תוצאת הרצת הפרוטוקול היא עותק המכיל את מהלכי הפרוטוקול והמסרים שעברו מצד לצד וכן מפתח $k$ המשותף לשני הצדדים. לצורך הניסוי מטילים מטבע, דהיינו בוחרים סיבית אקראית $b\in \{0,1\}$ ובודקים:

אם $b=0$, בוחרים מחרוזת $k'\leftarrow \{0,1\}$ באופן אקראי ואחיד.

אם $b=1$ אזי מציבים $k'=k$.

נניח שקיים אלגוריתם ${\mathcal {A}}$ שמקבל כקלט עותק של מהלכי הפרוטוקול $\Pi$ ואת הסיבית $k'$ ומפיק את $b'$. תוצאת הניסוי מוגדרת '1', דהיינו האלגוריתם הסתיים בהצלחה אם $b'=b$ אחרת התוצאה היא אפס.

פרוטוקול שיתוף מפתח $\Pi$ ייקרא בטוח בנוכחות המצותתת איב, אם עבור כל ${\mathcal {A}}$ - אלגוריתם הסתברותי פולינומי, קיימת 'פונקציית זניחות' של $n$ המסומנת בקיצור ${\text{negl}}(n)$ כך שמתקיים:

$\Pr[{\text{KE}}_{{\mathcal {A}},\Pi }^{\text{eav}}(n)=1]\leq {\frac {1}{2}}+{\text{negl}}(n)$

כלומר ההסתברות ש-${\mathcal {A}}$ יחזיר את $b$ ובכך יאפשר ליריב לגלות האם $k'=k$, גדולה מחצי בשיעור שאינו עולה על פונקציה זניחה כלשהי של $n$. פונקציית זניחות יכולה להיות למשל מהצורה $2^{-{\text{log }}n}$.

ראו גם

• MQV
• שידור מוצפן