אל תסמכו על החתימות הדיגיטליות

בקצרה: פרצו את MD5.

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

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

קצת רקע:
אלגוריתמים של חתימה דיגיטלית מאפשרים לוודא שרק מישהו שיודע סוד מסויים יכול היה לייצר חתימה מסויימת. אלגורתמים נפוצים היום הם RSA, DSA ו-ElGamal. אנחנו מניחים שיש רק בן אדם אחד שמחזיק את המפתח. נקרא לו, ללא הגבלת הכלליות, “אור”. אנחנו יכולים להניח שאם יש הודעת דואר אלקטרוני שחתומה ע”י המפתח של אור, אזי אור הוא זה שכתב את ההודעה.

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

אבל יש קוץ קל בכל השימחה. לחתום על הודעה, חוזה, או קובץ בגודל דיי גדול באמצעות אחד מהאלגוריתמים המוזכרים למעלה הינה פעולה יקרה וארוכה. כתוצאה מכך, בד”כ בוחרים בשיטה אחרת לביצוע חתימות. השיטה מכונה פונקצית האש קריפטוגרפית “cryptographic hash function”.

הרעיון הוא כזה. פונקציה y=f(x)‎ תחשב פונקצית האש טובה אם אפשר להגיד עליה כך:
בהנתן x, קל לחשב את y (אחרת למה אנחנו משתמשים בה).
בהנתן y, קשה למצוא x שמקיים את הפונקציה (הפונקציה לא הפיכה).
קשה למצוא שני xים, כך שיש להם את אותו ה-y.

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

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

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

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

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

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

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

:
שברו את MD5. בגדול, יש שלושה דברים שהמשפט הקודם עלול/עשוי להגיד, בסדר עולה של חומרה:
1. תוקף מסוגל לייצר שתי הודעות שעונות על תנאי מתמטי מסויים, כך שלשתי ההודעות אותו האש.
2. תוקף מסוגל לייצר שתי הודעות, פחות או יותר כרצונו, כך שלשתי ההודעות אותו האש.
3. תוקף מסוגל לייצר הודעה חדשה כך שיש לה את אותו ההאש כמו הודעה קיימת.

אני חייב להודות שעוד לא התעמקתי בחומר בעצמי. על פי מה שאחרים לעסו בשבילי, בשלב זה פרצו אותו ברמה 1, אבל רמות 2 ושלוש הינן סבירות בעתיד הנראה לעין.

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

מצד שני, אם זה כל מה שיש לי, יהיה לי מאוד קשה לייצר שתי הודעות טקסט שמכילות טקסטים (כמעט) כרצוני, ושיהיה להם את אותו ההאש.

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

אחרי ששלחתם אלי את החוזה חתום, אני מוציא לכם חשבונית על 10,000 דולר. “מה זה?”, אתם שואלים. “הנה, החוזה שחתמתם עליו”, אני עונה. כדי להוכיח, אני שולח לכם חוזה, ואכן כתוב בו שאתם מתחייבים לשכור את שירותי למשך שנה, בעלות דו-חודשית של 10,000$. החוזה חתום בחתימה דיגיטלית המוצפנת באמצעות המפתח שלכם, הכל נראה כשר ותקף.

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

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

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

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

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

שחר