פונקציות תמצות קריפטוגרפיות

מה הקשר בין ימי הולדת, פרדוקסים וקריפטוגרפיה?

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

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

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

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

Published on LinkedIn on May 25, 2024

מציאת מקור כלשהו לערך תמונה נתון (Preimage)

נתונה פונקציית תמצות \( h \) ואלמנט \( y \) כך ש- \( h(x) = y \) עבור כל \( x \), מצאו \( x' \) שמקיים \( h(x') = y \).

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

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

בדוגמת של \( b \): בהינתן התמונה ״יום 26 במאי״ מה הסיכוי למצוא סטודנט שנולד ביום הזה? ב״סיכוי״ הכוונה לכמה ניסיונות או אנשים נצטרך לבחון עד שנגיע למישהו (מקור) שנולד בתאריך הזה. התשובה האינטואיטיבית היא אולי 365 אבל בפועל התוצאה שונה - להלן פלט של הגרלת 365 סטודנטים ותאריכים רנדומליים:

מהאיור עולה שהקורס מלא כימות השנה ועדיין אף סטודנט לא נולד ביום 26 בבמאי. לכל תלמיד שנבחר אכן יש 1/365 (או 366) סיכוי להיוולד ביום הנתון אך גם אחרי 365 ניסיונות לא בטוח שנמצא מקור מתאים לתמונה שלנו. הסיבה לכך היא שהמשתנים לא תלויים אחד בשני: ההסתברות של כל סטודנט להיוולד ביום נתון היא 1/365 - וכך גם של הסטודנט הבא שנבדוק.

מהגרף הבא שמתאר את פונקציית ההסתברות המצטברת אפשר לראות שההסתברות לקבל תשובה נכונה לאחר 365 ניסיונות אכן גבוהה פחות משנדמה: 0.63 בלבד:

ההסתברות לתשובה נכונה ביחס לסיכוי של שתיים בחזקת 32 מלמדת על הקושי הרב של הבעיה:

מבחינה פורמאלית ספר הלימוד משתמש בטרמינולוגיה של \( \epsilon \) ו- \( Q \) בעת בחינת אלגוריתמים שנועדו לפתור בעיות שכוללות רכיב רנדומלי. \( \epsilon \) מייצג את סיכויי ההצלחה של האלגוריתם ו- \( Q \) מייצג את מספר הקריאות לאורקל. מספר הקריאות נובע מאורך הודעה אפשרית \( X \). הסיכוי הממוצע להצליח לנחש נכון את המקור לתמונה \( y \in Y \) כאשר אורך תמונה הוא \( Y = M \) מתקבל בנוסחה הבאה:

\( \epsilon = 1 - (1 - 1/M)^Q \)

להבנתי זאת פשוט הנוסחה של התפלגות גיאומטרית מצטברת כאשר התוחלת \( p = 1/M \). במקרה של יום ההולדת נוכל להציב \( M = 365 \) ונראה שלאחר 365 קריאות ההסתברות להצלחה היא אכן:

\( 1 - (1 - 1/365)^{365} = 0.63 \)

מציאת מקור שני לערך תמונה נתון (Second Preimage)

נתונה פונקציית תמצות \( h \) ואלמנט \( x \) כך ש- \( h(x) = y \), מצאו \( x' \) כך ש- \( h(x') = y \).

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

מה הסיכוי למצוא סטודנט נוסף שנולד באותו יום כמו בוב? במקרה של \( b \) לכאורה אין הבדל – נניח שבוב נולד ב-26 במאי וההסבר מקודם עדיין תקף. בעולם הקריפטוגרפיה לעומת זאת לעיתים מידע על מקור נוסף יכול לסייע לנו בפתרון הבעיה – בפרט מידע נוסף על מקור ראשון.

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

\( \epsilon = 1 - (1 - 1/M)^{(Q-1)} \)

מציאת שני מקורות שונים לערך תמונה כלשהו (Collision)

מצאו \( x \) ו- \( x' \) כך ש- \( h(x) = h(x') \).

בשונה משתי התכונות הראשונות מסתבר שהסיכוי למצוא התנגשות גבוה בהרבה מהסיכוי למצוא ילד נוסף שנולד באותו יום בו נולד ילד נתון או למצוא ילד שנולד בתאריך נתון. כלומר – קל יותר להצליח בתקיפה מהסוג הזה. כפי שניתן לראות בגרף הבא הסיכוי להצליח לאחר 100 ניסיונות כבר מתכנס ל-1:

הגרף האחרון מתאר תופעה שמכונה ״פרדוקס יום ההולדת״: בהינתן מעל 100 תלמידים בקורס הסיכוי שלא יהיו שניים שנולדו באותו יום אפסי. אם תסתכלו שוב על הגרף הראשון (פיזור רנדומלי של 365 סטודנטים על לוח השנה) אתם תזהו שעל חלק לא מבוטל מימות השנה ספרות הגדולות מאחת. במקרה של התנגשות מספיק יום אחד על גבי לוח השנה שבו תופיע ספרה גדולה מאחת.

מבחינה מתמטית כאשר הטווח \( Y \) בגודל \( M \) לכל מקור סיכוי של \( 1/M \) להצליח למצוא מקור נוסף שנותן את לקבל ערך של תמונה מסוימת. בניסוי עם \( Q \) איברים יש \( Q(Q-1)/2 \) זוגות אפשריים של איברים: כל איבר יכול להיצמד לכל אחד מ- \( Q-1 \) האיברים הנותרים כאשר החלוקה בשתיים נועדה למנוע ספירה כפולה של זוגות – כלומר לבטל תמורות (סדר הזוג לא משנה). הסיכוי לא להצליח מתקבל ע״י הכפלה של הניסויים באופן הבא: לסטודנט הראשון הסיכוי לא משנה ל- \( Q-1 \) הסטודנטים שאחריו הסיכוי לא ליפול לתא (יום בשנה) שכבר יש בו מישהו קטן בכל פעם: לסטודנט השני כבר יש רק \( 1 - 1/M \) תאים ריקים לשלישי (בהנחה שעדיין לא הייתה התנגשות) רק \( 1 - 2/M \) ולאחרון \( 1 - (Q-1)/M \). הכפלת המאורעות האלה לאחר פישוט מובילה לכך ש- \( Q = M \) ניסיונות רנדומליים מספיקים למציאת התנגשות בסיכוי של 50%.

במקרה של יום ההולדת כיוון ש- \( M = 365 \) נקבל ש- \( Q = 22.3 \) סטודנטים בלבד מספיקים למציאת התנגשות בסיכויי הצלחה של 50% – כמו שגם ניתן לראות בגרף לעיל. תשומת הלב שלצורך סיכוי של 50% להצליח את הבעיה הראשונה – מציאת המקור - היינו צריכים מעל 200 סטודנטים ושבהינתן 22.3 סטודנטים בלבד הסיכוי להצליח אותה קלוש ביותר: בסביבות 0.05.

דוגמאות לפונקציות תמצות מוכרות:

• MD5
• SHA1
• SHA256
• SHA3

MD5 ו-SHA1 נזנחו לאור חולשות אבטחה שהתגלו בהן ואילו SHA256 ו-SHA3 עדיין נחשבות כיום לבטוחות. כל הפונקציות למעט SHA3 בנויות על בסיס טכניקה שמכונה Merkle-Damgard (ראו להלן). SHA3 לעומת זאת פותחה על בסיס שונה המכונה ספוג (Sponge). למרות שלא נמצאו חולשות ל-SHA3 היא טרם נקלטה באופן שכיח וכיום בעיקר נפוץ השימוש ב-SHA256.

בניית Merkle-Damgard

טכניקת בנייה איטרטיבית המאפשרת לתמצת הודעות מכל גודל לגודל קבוע \( m \) בעזרת פונקציית תמצות מגודל קבוע לגודל קבוע (פונקציות המכונות ״פונקציות דחיסה״ Compression). הטכניקה מבטיחה שבהינתן פונקציית דחיסה \( Compress \) חסינה להתנגשויות נוכל לבנות בעזרתה פונקציית תמצות \( h \) שתפעל גם על גודל לא קבוע - ותהיה חסינה מהתנגשויות בדומה ל- \( Compress \).

יהי פונקציית דחיסה: \( compress: {0..1}^{m+t} \to {0..1}^m \)

בשלב הראשון נניח כי \( t \geq 2 \). אם הפונקציה \( Compress \) חסינת התנגשויות נראה כיצד לבנות פונקציית תמצות \( h \) חסינת התנגשויות כאשר \( h: {0..1}^* \to {0..1}^m \)

הכנה: עבור קלט \( x \) באורך \( n \) נחלק את המידע ל- \( k \) בלוקים בגודל \( t-1 \) תוך עיגול למעלה של \( k = \lceil \frac{n}{t-1} \rceil \). הרעיון הוא שנוכל להפעיל את פונקציית הדחיסה על בלוקים בגודל מתאים – אבל בשלב הראשון שימו לב שהחלוקה היא דווקא לבלוקים ( \( y \) ) בגודל קטן מהנדרש. דוגמה: אם למשל הקלט הוא באורך 123 ביטים ופונקציית הדחיסה פועלת על 32 ביטים ומחזירה 16 ביטים נחלק את הקלט לתשעה בלוקים ( \( 123/15=8.2 \) ואז עיגול למעלה - שימו לב שאתם מבינים את החישוב הוא בעיקר טכני: \( t \) בדוגמה הזאת הוא 16 והמספר 15 הוא פשוט \( t-1 \) ) השמונה הראשונים יהיו באורך של \( t-1 \) (יורחבו בהמשך). אך מה עושים עם הבלוק האחרון \( y_k \) בעיקר כאשר \( n \) לא בהכרח מתחלק ב- \( t-1 \) ללא שארית? מרפדים באפסים עד שיהיה באורך מתאים. בנוסף לכך שומרים בלוק נוסף שבו הייצוג של כמות האפסים שריפדנו ( \( d \) ) בבלוק \( y_{k+1} \). התחלה: נוסיף \( m+1 \) אפסים לפני הבלוק הראשון שכזכור באורך \( t-1 \) ואז נקרא לפונקציית הדחיסה עם בלוק בגודל מתאים לה ( \( m+t \) ). תשומת הלב שלעיתים נבחרים ערכים שונים לשלב הראשון \( IV \) במקום אפסים.

0…0

לשרשור שיוצר את הקלט לפונקציית הדחיסה קוראים בספר \( Zi \). שימו לב שאכן \( |z|=m+t \). איטרציות: נמשיך באופן איטרטיבי לקרוא לפונקציית הדחיסה כאשר בכל פעם הקלט לפונקציית הדחיסה \( Zi \) יהיה שרשור של תוצאת הדחיסה הקודמת \( g_{i-1} \) ביט אחד דלוק והבלוק ה- \( yi \):

סיום: הפלט של \( h \) יתקבל לאחר דחיסת הבלוקים עם התוצאות הקודמות והביטים ויוחזר מהפונקציה. כזכור הבלוק האחרון כולל ריפוד אפסים \( d \).

סקריפט עם מימוש האלגוריתם מצורף תחת ״הרחבות והשלמות״.

ההוכחה לחסינותה של \( h \) להתנגשויות בהינתן חסינותה של פונקציית הדחיסה מתחלקת למקרים ומבוססת על רעיון דומה לסעיף האחרון שפתרנו בשאלה הקודמת. נניח ש- \( h \) אינה חסינה להתנגשויות ונראה כיצד ניתן למצוא התנגשות לפונקציית הדחיסה. כיוון שנתון שפונקציית הדחיסה חסינה נקבל סתירה ונסיק ש- \( h \) אכן חסינה להתנגשויות אף היא.

להלן הפרטים הכלליים של ההוכחה:

נניח שאנו יכולים למצוא \( x \) ו- \( x' \) שונים כך ש- \( h(x) = h(x') \). נסמן את השרשור של \( k+1 \) הבלוקים שיוצרים את \( x \) ואת \( x' \) באופן הבא:

\[ y_x = y_1 || ... || y_{k+1} \\ y_{x'} = y_1 || ... || y'_{l+1} \]

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

כאשר אחד משני המקורות מתחלק ב- \( t-1 \) ללא שארית והשני לא אז בהכרח קיים שוני במספר האפסים המרכיבים את הבלוק האחרון. מצד אחד:

\[ h_x = comp(g_k 1 || y_{k+1}) \\ h_{x'} = comp(g'_{l 1} || y'_{l+1}) \]

לאור השוני בבלוק האחרון \( y_{k+1} \neq y'_{l+1} \) ומכאן שמצאנו שני מקורות שונים שמספקים מקור לפונקציית הדחיסה. מכאן שמצאנו דרך לפתור את בעיית ההתנגשות עבור פונקציית הדחיסה \( compress \) – אך כיוון שנתון שהיא חסינת התנגשויות מדובר בסתירה ומכאן שההנחה ש- \( h \) אינה חסינת התנגשויות שגויה ו- \( h \) דווקא כן חסינה.

כאשר אין הבדל בשארית החלוקה: מפצלים לשני תתי מקרים:

כאשר אורך המקורות זהה הספר מראה שכיוון ששני המקורות שונים כדי שלא תהיה התנגשות בהכרח מתקיימת אחת מהאפשרויות הבאות: או שהקלטים שהוכנסו לאורך הבנייה לפונקציית הדחיסה תמיד היו זהים או שהמקורות היו זהים מראש. אבל כיוון שהנחנו ש- \( h \) אינה חסינה ושהמקורות שונים כלומר \( x \neq x' \) אז בהכרח המקורות היו שונים ובשלב מסוים הוכנסו לבנייה קלטים שונים שסיפקו תוצאה זהה. מכאן שמצאנו דרך לפתור את בעיית ההתנגשות עבור פונקציית הדחיסה \( compress \) – אך כיוון שנתון שהיא חסינת התנגשויות מדובר בסתירה ומכאן שההנחה ש- \( h \) אינה חסינת התנגשויות שגויה ו- \( h \) דווקא כן חסינה.

כאשר אורך המקורות שונה נעזרים בכך שבבלוק הראשון ריפדנו 0 במקום ביט דלוק של 1 כדי להראות שבהכרח הקלט שהוכנס לפונקציית הדחיסה היה שונה ומגיעים למסקנה ש- \( h \) חסינה להתנגשויות בדומה למקודם.

בכל אחד מהמקרים מההנחה ש- \( h \) אינה חסינה להתנגשויות ניתן להראות שגם \( Compress \) אינה חסינה. אבל מכיוון שידוע ש- \( Compress \) אכן חסינה מתקבלת סתירה כלומר ש- \( h \) חסינה להתנגשויות אף היא. מקרה נוסף שהספר מטפל בו הוא המקרה שבו \( t = 1 \) וההוכחה דומה.

בניית ספוג (Keccak)

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

המנגנון כולל רכיב \( r \) שלתוכו מספיגים בכל שלב \( r \) ביטים מהקלט וכן רכיב \( c \) שאינו מושפע באופן ישיר מהקלט. בשלב הראשון המחרוזת נספגת בספוג בשלבים \( P \) באיור שלמעלה. בכל שלב כזה נעשה XOR בין בלוק בהודעה לבין רכיב הספוג. בשלב השני נסחטים בכל פעם \( r \) ביטים הראשונים בפלט של הפרמוטציה. התהליך חוזר על עצמו עד לאורך הפלט הנדרש.

קוד לאותנטיקציה של הודעה (MAC – Message Authentication Codes)

דוגמה

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

ניתן להמחיש את הרעיון באופן הבא: \( Alice to Bob: m with h(k || m) \) כאשר \( k \) מפתח סודי. ליריב אמור להיות קשה לייצר הודעה \( m' \) עם MAC מזויף כלומר \( m' with h(k || m') \) כי הוא לא יודע את המפתח \( k \).

כאשר בוב מקבל \( m' \) וערך של פונקציית התמצות \( h(k || m') \) הוא מחשב בעצמו את ערך הפונקציה לפי המפתח שהוא יודע באופן הבא: \( h(k || m') == \alpha \). כלומר בוב בודק אם התג שקיבל תואם את החישוב לפי המפתח הסודי \( k \) שמצוי ברשותו – נסמן את התוצאה \( \alpha \). אם לא הוא יוכל לזהות שההודעה לא נשלחה מאליס. מכיוון שני אם הערך של פונקציית התמצות כן תואם הוא יוכל להניח שהצד השני אכן יודע את המפתח – כלומר שזו אליס.

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

מסתבר שבבניה שתיארנו יש חולשה לא מבוטלת להלן תיאור פורמאלי של הבעיה.

תהי פונקציית תמצות פשוטה מהצורה: \( compress: {0..1}^m+t \to {0..1}^m \)

נניח שערכו של מפתח סודי \( K \) באורך \( M \) משמש בתחילת הודעה כ- \( IV = K \).

נסמן ב- \( h_k(x) \) את הפונקציה שמשתמשת במפתח \( k \) לצורך שליחת התמצות הסודי.

כיצד יריב יכול לייצר תגית תקפה בלי לדעת את המפתח \( K \) אלא רק בעזרת הודעה כלשהי \( x \) והתגית שלה \( h_k(x) \)?

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

פורמאלית תהי \( x' \) מחרוזת באורך \( t \) ביטים ונתבונן בהודעה שמוסיפה מידע לאחר \( x \):

\( h_k(x || x') = compress(h_k(x) || x') \)

לתוקף יהיה קל לחשב את תוצאת התמצות גם בלי המפתח כיוון שנתון לו ערך התגית \( h_k(x) \) וערך המחרוזת \( x' \) – בנסיבות המקרה התוקף יצטרך למצוא רק את השלב האחרון (או שלבים נוספים אם ייבחר) בחישוב המחרוזת המשורשרת. כך תוקף יוכל לשלוח לאליס הודעה משלו – שאמנם מתחילה בדומה למסר המקורי – אך נחזית להיות מסר מטעמו של בוב. לסוג ההתקפה הזה קוראים length extension attack. אחד הפתרונות הוא ריפוד של ההודעה או המפתח אך גם לכך נמצאו התאמות של התקיפה. דוגמה לריפוד ובנייה מתוחכמת יותר נקראים h(mac) במסגרתו הערך של המפתח הסודי מוזן גם באמצע ההודעה.

בממ״ן יש לנו שאלה שמציעה לעשות Hash באמצעות AES. דוגמה נוספת היא CBC MAC - כל פעם עושים XOR על בלוק ו-AES.

חתימה דיגיטלית – Hash and Sign

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

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

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

הרחבות והשלמות

שאלה מפרק קודם: בהינתן מפתחות בגודל 128 למה אנחנו צריכים גם 256?

128 ביט נחשב לגודל טוב מכיוון שהוא חסין Brute Force. עם זאת חולשות אבטחה עשויות להקטין את מרחב החיפוש: מרחב החיפוש של 128 ביט הוא \( 2^{128} \) אבל אם למשל נצליח למצוא חולשה שמקטינה ב-40 ביט מרחב חיפוש של \( 2^{88} \) כבר מתקרב לפתרון ישים. הגודל הרחב יותר נועד אפוא לאפשר שוליים של בטיחות: במקור גודל של 256 ביט היה נתפס כחשיבה פראנואידית אך כיום מדובר בשימוש הנפוץ.

להרחבה על תחרות ה-SHA3 והרקע שקדם לה ראו ד״ר אור דונקלמן פונקציות תמצות קריפטוגרפיות ותחרות ה-SHA3 Digital Whisper גיליון 21 יוני 2011: קישור למאמר

סקריפט פייתון שמדגים בנייה איטרטיבית של פונקציית תמצות:

מחברת Jupyter עם דוגמאות נוספת כמו מימוש אורקל ומשחקי פרדוקס יום הולדת תפורסם בהמשך ב-GitHub.

תודה רבה לד״ר ארז ויסברד על הנחיית המפגש.

דור פסקל

מבוא לקריפטוגרפיה 20580: סיכום מפגש שני – 21 באפריל 2024

import math

class SimpleCompress:
    """
    A simple compression function that returns the XOR of the first and second halves of the input data.
    """

    def __init__(self):
        self.m = 16
        self.t = 16

    def compress(self, data):
        """
        Compress the input data by XORing the first and second halves.

        :param data: The input data to compress (32 bits)
        :return: The compressed data (16 bits)
        """
        if len(data) != 32:
            raise ValueError("Data must be 32 bits long")
        first = data[:16]
        second = data[16:]
        result = bin(int(first, 2) ^ int(second, 2))[2:]
        result = result.zfill(16)
        return result

def simple_merkle_damgard(data, simple_compress):
    """
    Implement the Merkle-Damgard construction using the SimpleCompress class.
    The data is split into blocks of size t-1 where t is the delta between the preimage and hash size.
    The last block is padded with zeros to make it t-1 bits long.
    The length of the padding is stored in binary in the last block.
    The compression function is applied iteratively to each block using concatenation of the previous hash value 1 and the block.
    The final hash value is returned.

    :param data: The input data to hash
    :param simple_compress: The SimpleCompress class instance
    :return: The hash value of the data
    """
    n = len(data)  # data length
    # number of blocks is ceil(n/t-1)
    k = math.ceil(n / (simple_compress.t - 1))
    # padding length for last block
    d = max(0, k * (simple_compress.t - 1) - n)
    blocks = []  # will hold k+1 blocks size t-1
    for i in range(k - 1):
        blocks.append(
            data[i * (simple_compress.t - 1): (i + 1) * (simple_compress.t - 1)]
        )
    blocks.append(data[(k - 1) * (simple_compress.t - 1):])  # last block
    blocks[-1] += "0" * d  # padding last block - 0s
    # length of padding in binary
    blocks.append(format(d, "b").zfill(simple_compress.t - 1))
    z1 = "0" * (simple_compress.m + 1) + blocks[0]
    g1 = simple_compress.compress(z1)

    for i in range(1, len(blocks)):
        z = g1 + "1" + blocks[i]
        g1 = simple_compress.compress(z)

    return g1

if __name__ == "__main__":
    data = "111111110100" * 10 + "110"
    simple_compress = SimpleCompress()
    print(simple_merkle_damgard(data, simple_compress))