צופן קוד בינארי
צילום: Istock

ישראלי פרסם שני רצפים של מספרים; לקח שבועיים עד שמומחי ההצפנה הבינו מה הוא עשה

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

מנדי הניג |
נושאים בכתבה סייבר

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

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

בסוף השבוע, יותר משבועיים לאחר פרסום הציוץ, נתקל בו זוקו וילקוקס, ממייסדי מטבע הקריפטו Zcash ודמות מוכרת בתחום ההצפנה. התגובה שלו הייתה הרבה פחות מאופקת: "WTF WTF WTF. This is amazing", או בתרגום חופשי - "מה לעזאזל? זה מדהים". בהמשך הוא גילה שהציוץ פורסם כבר ב-2 בנובמבר, ותהה איך כמעט אף אחד לא הבחין בו עד אז, למעט האנשים שעוסקים בפרויקט HashSmash, שמקדם מחקר בתחום פונקציות הגיבוב.


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

מה זה בכלל SHA-256, ומה הוא הצליח לשבור?

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

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

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

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

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

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

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

אז למה רק 38 שלבים מתוך 64?

כאן מגיע החלק שמסביר גם את גודל ההישג וגם את המגבלות שלו.

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

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

קיראו עוד ב"מדע"

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

במקרה של SHA-256, חוקרים הצליחו לאורך השנים לייצר התנגשויות בגרסאות שהפעילו מספר קטן יותר של שלבים. בשנתיים האחרונות נרשמה התקדמות נוספת, והחוקרים הצליחו להגיע גם לגרסאות של 35 ו-36 שלבים. לגבי 38 שלבים כבר היו מחקרים שהצביעו על אפשרות תאורטית לייצר התנגשות, אבל המחיר החישובי היה עצום.

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

למה חוקרי ההצפנה כל כך הופתעו?

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

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

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

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

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

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

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

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

גם גולדצווייג עצמו מציין במאמר שהשיטה המסוימת שבה השתמש אינה מתרחבת ישירות ל-39 שלבים.

ומה הקשר לבינה מלאכותית?

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

בעמוד הראשון של המאמר המדעי שלו מופיעה הצהרה מפורשת שלפיה מדובר בעבודה שנוצרה בעיקר באמצעות AI. הוא מסביר שהמחקר והכתיבה פותחו בתהליך עבודה חוזר עם סוכני Claude של חברת Anthropic, בעיקר באמצעות המודל Claude Opus 5.5, ותחת הנחייתו.

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

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

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

אז האם SHA-256 נפרץ?

התשובה היא לא. וזה הבדל שחשוב להבין.

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

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

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

גולדצווייג כבר פרסם את המאמר המדעי המלא שלו, "A Collision for 38-Step SHA-256", במאגר המחקר הקריפטוגרפי Cryptology ePrint, ובו הוא מפרט את השיטה המתמטית שפיתח ואת התוצאות שהשיג. המאמר מאפשר לחוקרים נוספים לבחון את העבודה ולשחזר את התוצאות.

הוספת תגובה

תגובות לכתבה:

הגב לכתבה

השדות המסומנים ב-* הם שדות חובה