פונקציית hash קריפטוגרפית ודעות קדומות

ב־4.1.2009, מאת ארתיום; פורסם תחת: פיתוח, תכנה ומחשבים; ‏4 תגובות

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

  • פונקציית md5 פרוצה, אז אני שומר את הססמאות בבסיס הנתונים בעזרת sha1 (או רשום פונקציית hash החביבה עליך) ואמנע גילוי ססמאות עם בסיס הנתונים ייפרץ!
  • פונקציית md5 אינה בטוחה, אז אני אוסיף קצת "מלח"‏: md5(salt+pass)‎ והיא תהיה בטוחה!
  • אני השתמשתי ב־hmac של פייתון בקונפיגורציית ברירת מחדל וגיליתי שהוא משתמש ב־md5 הפרוצה... עכשיו כל החתימות של שוות כלום.

מוכר לכם? ידוע לכם?

אז תגלו, שכל אלו הן טענות לא־בדיוק־נכונות.

וכבן נתחיל. קודם כל, md5, כפי שידוע לנו היום, היא פונקציה העמידה נגד התנגשויות באופן חלש: כלומר: קשה למצוא x' כך ש־hash(x')=hash(x) עבור x נתון. אבל כן ניתן למצוא x_1 \neq x_2 כך ש־hash(x_1)=hash(x_2).

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

אז נתחיל להפריך את הטענות שמוצגות לעיל:

  1. האם בטוח לשמור y=hash(x) כדי להבטיח סודיות של X? במקרה כזה, לפי ההגדרה, גם פונקציית Hash העמידה בפני התנגשויות במובן חלש מספיקה. כי היא בדיוק מונעת חושב x=hash^{-1}(y) -- הססמה.

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

  2. האם פתרון salting כפי שהוצג הוא בטוח? לא משנה עם md5 או עם sha1? מסתבר שלא. אני לא אביא כאן ציטוטים, אבל למעשה, אותו אדם שרוצה "לחזק" את החתימה שלו, עדיין משאיר מספר חורים. מה שבפועל הוא מחפש זה MAC_k(x) חתימה דיגיטלית עם מפתח k. זאת לא דרך נכונה לעשות את זה.

    קיים פתרון סטנדרטי וידוע HMAC‏ שנועד בדיוק מקרים כאלה --- הוא למעשה, מהווה הרכבה של שני פונקציות hash רגילות. הוכח ב־1996 שהחוזק שלו הוא כחוזק פונקציית hash העמידה בפני התנגשויות במובן החלש. קרי, חתימה דיגיטלית המבוססת על פונקצית Hash חלשה --- md5 עדיין מספיק "חזקה" אפילו שהיא "חלשה".

  3. כנ"ל למימוש של Python. למרות שבתיעוד נאמר כי "לא־מומלץ" או אף מסוכן להשתמש בברירת מחדל של md5, מסתבר שזה לא עד כדי כך נורא --- או ליתר דיוק בטוח.

בנוסף, כל שיטות ה־salting ו־MAC מניחות דבר חשוב: המפתח נשאר סודי. כך בין כה לכה צריך לקוות שאם מישהו יפרוץ לבסיס הנתונים שלכם, הוא לא ימצא את המקום על השרת איפה ששמור מפתח פרטי; או לחלופין, אתם לא תאבדו אותו בעצמכם ואף משתמש לא יצליח להיכנס יותר.

במילים אחרות: הכר את אויבייך ואת יכולותיך.

הערות:

  • הבעיה האמתית של שמירת ססמאות כ־md5 --- יש יותר מידי כלים מוכנים שיודעים לעשות את הפריצה.
  • אני לא מנסה להמליץ לכם להשתמש ב־md5, אלא להכיר את החולשות שלו ושל שאר "פתרון מועדפים" כגון sha1.

תגובות

ik_5, ב־4.1.2009, 16:40

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

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

להגיד שבגלל שכרגע אין משהו טוב, וגם אי אפשר להשיג בצורה יעילה אפשרות ש x = x' רק מתעלמת מהבעיה, במקום לנסות ולהימנע ממנה. זה מזכיר לי את הבעיה של באג 2000. כאשר כולם ידעו שהבאג הזה יגיע בשנות ה60-70, אבל תמיד אמרו שיש עוד זמן ועוד זמן ועוד זמן, וכשהבעיה באמת התחילה להיות קריטית, רק אז התחיל הכאב ראש האמיתי.

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

ארתיום, ב־4.1.2009, 16:55

אם יש לי גישה לקובץ shadow

אם יש לך גישה לקובץ shadow אז יש לך גישה ל־root. אם יש לך גישה ל־root יש לך שליטה על הכל: קרנל, זיכרון ועוד --- תטען מודול משלך שיכתוב ללוג את כל הססמאות.

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

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

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

מי יודע, אולי hash זה לא הרעיון הכי טוב ומתאים לשמירת סיסמאות… אולי זה מה שאפשר ללמוד מהבעיות האלו

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

ו אם אתה רוצה לצטט את סאן טצ'ו

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

במקרה שלנו --- צריך לא לפחד מ־md5 אלא משימוש הלא נכון ב־hash באופן כללי, שזה מה שקורה ב־90% מהמקרים.

עפר, ב־17.11.2010, 15:24

זו דוגמה לדבריפ שנראים רחוקים אבל נתנים לביצוע:

known MD5 (with weakness) + 200 PlayStation 3’s cluster + a lot of creativity = man in the middle attack on ca.

http://www.gnucitizen.org/blog/thoughts-on-the-certificate-authority-attack-presented-at-ccc/)

ארתיום, ב־17.11.2010, 16:06

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

עדיין היום להריץ מערך של 300 PS כזה כדי לפרוץ את ה־MD5 הוא מאוווד יקר, וסביר להניח שהתוקף יבחר להשתמש בשיטות אחרות לפני השיטה הזו.

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

תמיד תזכור את זה כשאתה חושב על אבטחה: http://xkcd.com/538/

הוסף תגובה:

 
 כתובת דוא"ל לא תוצג
 

ניתן לכתוב תגובות עם שימוש בתחביר Markdown.

חובה לאפשר JavaScript כדי להגיב.

דפים

נושאים