MD5

בקריפטוגרפיה, MD5 (ראשי תיבות באנגלית: Message Digest algorithm 5, בתרגום חופשי: "אלגוריתם תמצות מסרים גרסה 5") היא פונקציית גיבוב קריפטוגרפית שהייתה פונקציה קריפטוגרפית פופולרית בכל העולם ועדיין נמצאת בשימוש^[1] למרות שהתגלתה כפונקציה פגיעה ולא נחשבת בטוחה יותר^[2]. MD5 מקבלת קלט באורך כלשהו ומפיקה ממנו "תמצית" באורך 128 סיביות שהיא מחרוזת סיביות חסרת משמעות המשמשת מעין טביעת אצבע דיגיטלית. עיקר מטרתה היה לספק אמצעי קריפטוגרפי להגנה על שלמות ואימות מסרים ברשת האינטרנט וכחלק ממנגנון חתימה דיגיטלית. ההתאמה בין התמצית לבין הקלט היא חד כיוונית באופן שקשה מאוד למצוא קלט אחר שממנו אפשר להפיק תמצית זהה לכן התמצית מהווה הוכחה לאותנטיות הקלט. נהוג לייצג את תמצית MD5 כמחרוזת טקסט הקסדצימלית.

היסטוריה

פונקציית הגיבוב MD5 פותחה על ידי רונלד ריבסט ב-1991 והחליפה את קודמתה MD4. מקור שמה הוא ראשי התיבות של "Message Digest" (בתרגום חופשי: "תמצית מסרים"). האלגוריתם היה בעבר תקן^[3], כלומר, הוא הוגדר וסווג על ידי ה-IETF, ולכן הוא כלול בתוכנות אבטחה רבות. תיאורו וקוד המקור שלו נמצאים בטיוטה RFC 1321. ב-1996 נמצא פגם באלגוריתם MD5 ואף על פי שלא פגע בביטחונו באופן מהותי, מספר מומחי אבטחה ייעצו לעבור לאלגוריתם בטוח יותר. כיום מרבית התקנים ומומחי ההצפנה ממליצים שלא להשתמש בו כלל לצורך קריפטוגרפי אלא לעבור לאלגוריתם תיקני מסדרת SHA. במרוצת השנים מאז המצאתו התגלו ב-MD5 בעיות וחולשות רבות שנוצלו לצורך התקפות נגד מערכות שעשו בו שימוש, כשהמפורסמת שבהן הייתה הנוזקה להבה שניצלה את חולשתו כדי לזייף חתימה דיגיטלית של מיקרוסופט. הוכח שהוא אינו מספק את המטרה לשמה נועד ואינו מקיים את התכונות החיוניות הנדרשות מפונקציית גיבוב קריפטוגרפית, בעיקר התכונה החזקה יותר שלה - עמידות מפני התנגשויות. הוא עדיין נמצא בשימוש מוגבל בעיקר בגלל תאימות לאחור ושיקולי יעילות. הוא הוצא כליל מפרוטוקולי חתימה דיגיטלית כמו DSA ופרוטוקולי תקשורת כמו SSL, אך נמצא עדיין בשימוש כאלגוריתם תיקון שגיאות או סכום ביקורת, להבטחת שלמות מידע כל עוד השגיאות נגרמות עקב תקלות תקשורת שאינן זדוניות.

תיאור האלגוריתם

אלגוריתם MD5 הוא פונקציית גיבוב איטרטיבית הבנויה בסגנון מרקל-דמגרד. בהינתן הקלט $m$ באורך $\ell$ סיביות שעבורו מעוניינים לייצר תמצית. תחילה מחלקים אותו למקטעים באורך 512 סיביות אותם מעבדים בזה אחר זה, כל מקטע נקרא בלוק. הקלט לא תמיד מתחלק באורך הבלוק. אם למשל מחרוזת הקלט מכילה 75 אותיות, לפי קידוד ASCII שבו כל אות תופסת שמונה סיביות, אורכה הכולל הוא 600 סיביות ולכן היא מתחלקת לשני בלוקים, בלוק אחד מלא באורך 512 סיביות ובלוק שני חלקי המכיל רק 88 סיביות משמעותיות והיתר מאופסות. הבלוקים מסומנים כאן על ידי:

m_{0},m_{1},m_{2},...,m_{b-1}

.

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

1. ריפוד

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

לדוגמה אם מחרוזת הקלט היא המשפט:

"Hello World!"

בבסיס הקסדצימלי המחרוזת נראית כך:

48

65

6c

6f

20

57

6f

72

6c

64

21

כל ספרה הקסדצימלית היא באורך 4 סיביות. כולל הרווח (קוד אסקי 20) וסימן הקריאה (קוד אסקי 21) המחרוזת מכילה 12 תווים שתופסים לפי קידוד ASCII בדיוק 12 בתים בזיכרון (96 סיביות). היות שהמחרוזת נכנסת בבלוק אחד, מוסיפים $448-96=352$ סיביות כשהראשונה היא הסיבית '1' ולאחריה 351 אפסים (בסך הכול 44 בתים) ומתקבלת המחרוזת הבאה:

48	65	6c	6c	6f	20	57	6f	72	6c	64	21	80	00	00	00
00	00	00	00	00	00	00	00	00	00	00	00	00	00	00	00
00	00	00	00	00	00	00	00	00	00	00	00	00	00	00	00
00	00	00	00	00	00	00	00

ב-64 הסיביות הנותרות של הבלוק מקודדים את אורך המחרוזת המקורית שהוא 96 סיביות או בבסיס הקסדצימלי ${\text{0x60}}$ ומתקבל:

48	65	6c	6c	6f	20	57	6f	72	6c	64	21	80
00	00	00	00	00	00	00	00	00	00	00	00	00
00	00	00	00	00	00	00	00	00	00	00	00	00
00	00	00	00	00	00	00	00	60	00	00	00	00

כעת מתקבל בלוק שלם (אחד או יותר) באורך 512 סיביות כך שהקלט מוכן לעיבוד.

2. קידוד האורך

אורך הקלט בסיביות $\ell$ (לפני הריפוד) מקודד במשתנה באורך 64 סיביות לפי סדר בתים קטן. משתנה זה מוצב ב-64 הסיביות האחרונות של הבלוק האחרון. בשל כך אורכו הכולל של הקלט לא יעלה על $2^{64}$ סיביות כי אז לא ניתן לייצג את אורכו במשתנה באורך 64 סיביות. אם במקרה אורך הקלט עולה על מספר זה יש לקחת רק את 64 הסיביות האחרונות (הפחות משמעותיות) של $\ell$ . הקידוד לפי סדר בתים קטן פירושו שהבית בכתובת הנמוכה ביותר מייצג את הספרות הפחות משמעותיות של המספר. דהיינו המילה $W$ באורך 32 סיביות מורכבת מארבעה בתים $B_{1},B_{2},B_{3},B_{4}$ כאשר $B_{1}$ הוא הבית הראשון (בכתובת הראשונה בזיכרון). אזי לפי סדר בתים קטן $W=2^{24}B_{4}+2^{16}B_{3}+2^{8}B_{2}+B_{1}$ . במקרה שהמספר מתפרס על פני שתי מילים אזי המילה הראשונה מכילה את החלק הפחות משמעותי של המספר.

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

3. אתחול זיכרון

מכינים חוצץ באורך 4 מילים המסומנות $A,B,C,D$ כל מילה מאוחסנת באוגר באורך 32 סיביות. בסך הכול נפח הזיכרון הפנימי הוא 128 סיביות. אתחול האוגרים מתבצע על ידי וקטור האתחול המכיל 4 מילים קבועות $(H_{1},H_{2},H_{3},H_{4})$ . המכילות את מחרוזת הספרות של הבסיס ההקסדצימלי: "0123456789abcdef" ישר והפוך. לאחר חלוקה למילים לפי סדר בתים קטן מתקבל:

H_{1}={\text{67452301}},H_{2}={\text{efcdab89}},H_{3}={\text{98badcfe}},H_{4}={\text{10325476}}

4. עיבוד הקלט

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

{\boldsymbol {F}}(x,y,z)=(x\land y)\lor (\lnot x\land z)

.

{\boldsymbol {G}}(x,y,z)=(x\land z)\lor (y\land \lnot z)

.

{\boldsymbol {H}}(x,y,z)=x\oplus y\oplus z

.

{\boldsymbol {I}}(x,y,z)=y\oplus (x\lor (\lnot z))

.

הסימן $\land$ מייצג וגם, הסימן $\lnot$ מייצג את אופרטור השלילה, הסימן $\lor$ מייצג או לוגי והסימן $\oplus$ מייצג XOR. בכל פוזיציה של הקלט הפונקציה $F$ מתנהגת כפסוק לוגי: "אם $x$ אז $y$ אחרת $z$ ". אפשר היה להחליף את האופרטור $\lor$ בחיבור (+) בגלל שסיביות $(x\land y)\lor (\lnot x\land z)$ לעולם לא יהיו '1' באותן פוזיציות ולכן לא תהיה בעיה עם הנשא. אפשר לראות שאם סיביות הקלט $x$ , $y$ ו- $z$ בלתי מוטות ובלתי תלויות זו בזו, תוצאת הפונקציה תהיה בלתי תלויה גם היא. יתר הפונקציות דומות לפונקציה $F$ בכך שהן מייצרות במקביל פלט בלתי תלוי הדדית. הפונקציה $H$ היא פונקציית הזוגיות (XOR) של הקלט.

בנוסף לפונקציות יש להכין טבלת קבועים $T$ המכילה 64 אלמנטים. עבור כל אינדקס $i$ כאשר $0\leq i\leq 63$ האלמנט $T[i]$ מכיל את החלק השלם של השבר $4294967296\cdot |\sin(i+1)|$ (הפונקציה sin היא הסינוס של $i+1$ ברדיאנים). אין צורך לחשב את הטבלה בכל פעם שצריכים לחשב תמצית, נהוג לחשבה מראש. להלן ערכי הקבועים בבסיס הקסדצימלי:

{\begin{matrix}{\text{d76aa478}}&{\text{e8c7b756}}&{\text{242070db}}&{\text{c1bdceee}}&{\text{f57c0faf}}&{\text{4787c62a}}&{\text{a8304613}}&{\text{fd469501}}\\{\text{698098d8}}&{\text{8b44f7af}}&{\text{ffff5bb1}}&{\text{895cd7be}}&{\text{6b901122}}&{\text{fd987193}}&{\text{a679438e}}&{\text{49b40821}}\\{\text{f61e2562}}&{\text{c040b340}}&{\text{265e5a51}}&{\text{e9b6c7aa}}&{\text{d62f105d}}&{\text{02441453}}&{\text{d8a1e681}}&{\text{e7d3fbc8}}\\{\text{21e1cde6}}&{\text{c33707d6}}&{\text{f4d50d87}}&{\text{455a14ed}}&{\text{a9e3e905}}&{\text{fcefa3f8}}&{\text{676f02d9}}&{\text{8d2a4c8a}}\\{\text{fffa3942}}&{\text{8771f681}}&{\text{6d9d6122}}&{\text{fde5380c}}&{\text{a4beea44}}&{\text{4bdecfa9}}&{\text{f6bb4b60}}&{\text{bebfbc70}}\\{\text{289b7ec6}}&{\text{eaa127fa}}&{\text{d4ef3085}}&{\text{04881d05}}&{\text{d9d4d039}}&{\text{e6db99e5}}&{\text{1fa27cf8}}&{\text{c4ac5665}}\\{\text{f4292244}}&{\text{432aff97}}&{\text{ab9423a7}}&{\text{fc93a039}}&{\text{655b59c3}}&{\text{8f0ccc92}}&{\text{ffeff47d}}&{\text{85845dd1}}\\{\text{6fa87e4f}}&{\text{fe2ce6e0}}&{\text{a3014314}}&{\text{4e0811a1}}&{\text{f7537e82}}&{\text{bd3af235}}&{\text{2ad7d2bb}}&{\text{eb86d391}}\end{matrix}}

במהלך חישוב התמצית, כל בלוק קלט $m_{i}$ מועתק למשתנה מקומי $X$ לצורך עיבוד. $X$ מכיל 16 מילים באורך 32 סיביות שהם 512 סיביות. כל חישובי הפונקציות מבוצעים עם מילים מתוך $X$ לפי סדר מסוים. סדר עיבוד המילים נקבע לפי הטבלה הבאה בהתאם למספר הסבב:

z[0..15]=\{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15\},

z[16..31]=\{1,6,11,0,5,10,15,4,9,14,3,8,13,2,7,12\},

z[32..47]=\{5,8,11,14,1,4,7,10,13,0,3,6,9,12,15,2\},

z[48..63]=\{0,7,14,5,12,3,10,1,8,15,6,13,4,11,2,9\}.

ב-16 הסבבים הראשונים מעבדים את מילות הבלוק לפי הסדר מהמילה הראשונה עד המילה ה-16. בסבב ה-17 לפי הטבלה מתחילים מהמילה השנייה $X[z[16]]=X[1]$ במקום הראשונה לאחר מכן מדלגים למילה השביעית וכן הלאה (יש לזכור שהספירה מתחילה תמיד מאפס).

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

s[0..15]=\{7,12,17,22,7,12,17,22,7,12,17,22,7,12,17,22\},

s[16..31]=\{5,9,14,20,5,9,14,20,5,9,14,20,5,9,14,20\},

s[32..47]=\{4,11,16,23,4,11,16,23,4,11,16,23,4,11,16,23\},

s[48..63]=\{6,10,15,21,6,10,15,21,6,10,15,21,6,10,15,21\}.

הטבלה $s$ מכילה 64 ערכים כשכל ערך מייצג את מספר הפוזיציות שיש להזיז את המשתנה המקומי $t$ המכיל את פלט הפונקציות האמורות ומהווה חלק מערך הביניים של האלגוריתם. למשל בסבב הראשון $t\lll s[0]=t\lll 7$ הזזה של שבע סיביות, לדוגמה ${\text{10F24B1F}}\lll 7={\text{19258FC3}}$ .

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

{\text{For each }}i{\text{ from }}0{\text{ to }}b-1{\text{ do }}

\{

{\text{For }}j=0{\text{ to }}15{\text{ do:}}

X[j]\leftarrow m[16\cdot i+j].

‎

(A,B,C,D)\leftarrow (H_{1},H_{2},H_{3},H_{4}).

‎

{\text{For }}j=0{\text{ to }}15{\text{ do:}}

t\leftarrow (A+F(B,C,D)+X[z[j]]+y[j]),

(A,B,C,D)\leftarrow (D,B+(t\lll s[j]),B,C).

‎

{\text{For }}j=16{\text{ to }}31{\text{ do:}}

t\leftarrow (A+G(B,C,D)+X[z[j]]+y[j]),

(A,B,C,D)\leftarrow (D,B+(t\lll s[j]),B,C).

‎

{\text{For }}j=32{\text{ to }}47{\text{ do:}}

t\leftarrow (A+H(B,C,D)+X[z[j]]+y[j]),

(A,B,C,D)\leftarrow (D,B+(t\lll s[j]),B,C).

‎

{\text{For }}j=48{\text{ to }}63{\text{ do:}}

t\leftarrow (A+I(B,C,D)+X[z[j]]+y[j]),

(A,B,C,D)\leftarrow (D,B+(t\lll s[j]),B,C).

‎

(H_{1},H_{2},H_{3},H_{4})\leftarrow (H_{1}+A,H_{2}+B,H_{3}+C,H_{4}+D).

\}

הביטוי $(A,B,C,D)\leftarrow (H_{1},H_{2},H_{3},H_{4})$ פירושו העתקת הערכים מהאגף הימני לאגף השמאלי לפי סדר זה $A=H_{1}$ , $B=H_{2}$ וכן הלאה. הסימן $\lll$ מייצג הזזה מעגלית לשמאל לפי מספר הפוזיציות המופיע לימין הסימן בגבולות מילה באורך 32 סיביות. הזזה מעגלית ניתנת למימוש בתוכנה או בחומרה. למשל בשפת C ממשים הזזה מעגלית כך: (value << count) | (value >> (32 - count)) כאשר האופרטורים "<<" ו-">>" הם אופרטורי ההזזה המובנים בכל שפות התכנות. הפעולה העיקרית באלגוריתם היא המשפט $t\leftarrow (A+F(B,C,D)+X[z[j]]+y[j])$ , המשתנה המקומי $t$ מכיל את תוצאת הפונקציה על המצב הפנימי יחד עם חלק מבלוק הקלט והקבועים, כאשר $F$ מוחלפת בפונקציות האחרות לפי הסדר. הפעולה מומחשת בתרשים למעלה.

5. פלט

הפלט הוא שרשור ערכי הביניים מהסבב האחרון: $H_{1}\ \|\ H_{2}\ \|\ H_{3}\ \|\ H_{4}$

וקטור בדיקה

פלט	קלט
${\text{d41d8cd9 8f00b204 e9800998 ecf8427e}}$ ${\text{0cc175b9 c0f1b6a8 31c399e2 69772661}}$ ${\text{90015098 3cd24fb0 d6963f7d 28e17f72}}$ ${\text{c3fcd3d7 6192e400 7dfb496c ca67e13b}}$	${\text{MD5(“”)}}$ ${\text{MD5(“a”)}}$ ${\text{MD5(“abc”)}}$ ${\text{MD5(“abcdefghijklmnopqrstuvwxyz”)}}$

קוד לדוגמה

להלן קוד שלם בשפת C++‎ הממחיש את האלגוריתם. הקוד ממוטב חלקית ומיישם מספר אופטימיזציות כדי להשיג ביצועים טובים, ביניהם אפשר למנות; שימוש באופרטורים כמו XOR ו-AND במקום כפל וחיבור, פקודות מאקרו, פתיחת לולאות (loop unrolling) ומיעוט קריאות לפונקציות.

typedef unsigned int uint;
typedef unsigned char byte;

typedef struct {
	uint state[4];
	uint count[2];
	byte buffer[64];
} MD5_CTX;

class MD5
{
	#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))
	#define F(x, y, z) (((x) & (y)) | ((~x) & (z)))
	#define G(x, y, z) (((x) & (z)) | ((y) & (~z)))
	#define H(x, y, z) ((x) ^ (y) ^ (z))
	#define I(x, y, z) ((y) ^ ((x) | (~z)))

	byte PADDING[64] = {
		0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
	};

	#define FF(a, b, c, d, x, s, ac) { \
		 (a) += F ((b), (c), (d)) + (x) + (uint)(ac); \
		 (a) = ROTATE_LEFT ((a), (s)); \
		 (a) += (b); \
		}
	#define GG(a, b, c, d, x, s, ac) { \
		 (a) += G ((b), (c), (d)) + (x) + (uint)(ac); \
		 (a) = ROTATE_LEFT ((a), (s)); \
		 (a) += (b); \
		 }
	#define HH(a, b, c, d, x, s, ac) { \
		 (a) += H ((b), (c), (d)) + (x) + (uint)(ac); \
		 (a) = ROTATE_LEFT ((a), (s)); \
		 (a) += (b); \
		 }
	#define II(a, b, c, d, x, s, ac) { \
		 (a) += I ((b), (c), (d)) + (x) + (uint)(ac); \
		 (a) = ROTATE_LEFT ((a), (s)); \
		 (a) += (b); \
		 }
	static void MD5Transform(uint state[4], byte block[64])
	{
		uint a = state[0], b = state[1], c = state[2], d = state[3], x[16];
		Decode(x, block, 64);
		/* Round 1 */
		FF(a, b, c, d, x[0], 7, 0xd76aa478); 
		FF(d, a, b, c, x[1], 12, 0xe8c7b756); 
		FF(c, d, a, b, x[2], 17, 0x242070db); 
		FF(b, c, d, a, x[3], 22, 0xc1bdceee); 
		FF(a, b, c, d, x[4], 7, 0xf57c0faf); 
		FF(d, a, b, c, x[5], 12, 0x4787c62a);
		FF(c, d, a, b, x[6], 17, 0xa8304613);
		FF(b, c, d, a, x[7], 22, 0xfd469501); 
		FF(a, b, c, d, x[8], 7, 0x698098d8); 
		FF(d, a, b, c, x[9], 12, 0x8b44f7af);
		FF(c, d, a, b, x[10], 17, 0xffff5bb1); 
		FF(b, c, d, a, x[11], 22, 0x895cd7be);
		FF(a, b, c, d, x[12], 7, 0x6b901122);
		FF(d, a, b, c, x[13], 12, 0xfd987193);
		FF(c, d, a, b, x[14], 17, 0xa679438e);
		FF(b, c, d, a, x[15], 22, 0x49b40821);

	/* Round 2 */
		GG(a, b, c, d, x[1], 5, 0xf61e2562); 
		GG(d, a, b, c, x[6], 9, 0xc040b340); 
		GG(c, d, a, b, x[11], 14, 0x265e5a51);
		GG(b, c, d, a, x[0], 20, 0xe9b6c7aa);
		GG(a, b, c, d, x[5], 5, 0xd62f105d); 
		GG(d, a, b, c, x[10], 9, 0x2441453); 
		GG(c, d, a, b, x[15], 14, 0xd8a1e681); 
		GG(b, c, d, a, x[4], 20, 0xe7d3fbc8);
		GG(a, b, c, d, x[9], 5, 0x21e1cde6); 
		GG(d, a, b, c, x[14], 9, 0xc33707d6); 
		GG(c, d, a, b, x[3], 14, 0xf4d50d87); 
		GG(b, c, d, a, x[8], 20, 0x455a14ed); 
		GG(a, b, c, d, x[13], 5, 0xa9e3e905); 
		GG(d, a, b, c, x[2], 9, 0xfcefa3f8); 
		GG(c, d, a, b, x[7], 14, 0x676f02d9); 
		GG(b, c, d, a, x[12], 20, 0x8d2a4c8a);

	/* Round 3 */
		HH(a, b, c, d, x[5], 4, 0xfffa3942);
		HH(d, a, b, c, x[8], 11, 0x8771f681); 
		HH(c, d, a, b, x[11], 16, 0x6d9d6122); 
		HH(b, c, d, a, x[14], 23, 0xfde5380c);
		HH(a, b, c, d, x[1], 4, 0xa4beea44); 
		HH(d, a, b, c, x[4], 11, 0x4bdecfa9); 
		HH(c, d, a, b, x[7], 16, 0xf6bb4b60); 
		HH(b, c, d, a, x[10], 23, 0xbebfbc70); 
		HH(a, b, c, d, x[13], 4, 0x289b7ec6); 
		HH(d, a, b, c, x[0], 11, 0xeaa127fa); 
		HH(c, d, a, b, x[3], 16, 0xd4ef3085);
		HH(b, c, d, a, x[6], 23, 0x4881d05); 
		HH(a, b, c, d, x[9], 4, 0xd9d4d039); 
		HH(d, a, b, c, x[12], 11, 0xe6db99e5); 
		HH(c, d, a, b, x[15], 16, 0x1fa27cf8); 
		HH(b, c, d, a, x[2], 23, 0xc4ac5665);

	/* Round 4 */
		II(a, b, c, d, x[0], 6, 0xf4292244); 
		II(d, a, b, c, x[7], 10, 0x432aff97); 
		II(c, d, a, b, x[14], 15, 0xab9423a7); 
		II(b, c, d, a, x[5], 21, 0xfc93a039); 
		II(a, b, c, d, x[12], 6, 0x655b59c3); 
		II(d, a, b, c, x[3], 10, 0x8f0ccc92); 
		II(c, d, a, b, x[10], 15, 0xffeff47d);
		II(b, c, d, a, x[1], 21, 0x85845dd1); 
		II(a, b, c, d, x[8], 6, 0x6fa87e4f); 
		II(d, a, b, c, x[15], 10, 0xfe2ce6e0); 
		II(c, d, a, b, x[6], 15, 0xa3014314);
		II(b, c, d, a, x[13], 21, 0x4e0811a1); 
		II(a, b, c, d, x[4], 6, 0xf7537e82);
		II(d, a, b, c, x[11], 10, 0xbd3af235);
		II(c, d, a, b, x[2], 15, 0x2ad7d2bb); 
		II(b, c, d, a, x[9], 21, 0xeb86d391);
		state[0] += a;
		state[1] += b;
		state[2] += c;
		state[3] += d;
		memset((byte *)x, 0, sizeof(x));
	}

	static void Decode(uint *output, byte *input, uint len)
	{
		uint i, j;
		for (i = 0, j = 0; j < len; i++, j += 4)
			output[i] = ((uint)input[j]) | (((uint)input[j + 1]) << 8) |
			(((uint)input[j + 2]) << 16) | (((uint)input[j + 3]) << 24);
	}

	static void Encode(byte *output, uint *input, uint len)
	{
		for (uint i = 0, j = 0; j < len; i++, j += 4) {
			output[j] = (byte)(input[i] & 0xff);
			output[j + 1] = (byte)((input[i] >> 8) & 0xff);
			output[j + 2] = (byte)((input[i] >> 16) & 0xff);
			output[j + 3] = (byte)((input[i] >> 24) & 0xff);
		}
	}

public:
	void Init(MD5_CTX *context)
	{
		context->count[0] = context->count[1] = 0;
		context->state[0] = 0x67452301;
		context->state[1] = 0xefcdab89;
		context->state[2] = 0x98badcfe;
		context->state[3] = 0x10325476;
	}

	void Update(MD5_CTX *context, byte *input, uint inputLen)
	{
		uint i, index = (uint)((context->count[0] >> 3) & 0x3F);
		if ((context->count[0] += ((uint)inputLen << 3)) < ((uint)inputLen << 3))
			context->count[1]++;
		context->count[1] += ((uint)inputLen >> 29);
		uint partLen = 64 - index;
		if (inputLen >= partLen) {
			memcpy((byte *)&context->buffer[index], (byte *)input, partLen);
			MD5Transform(context->state, context->buffer);
			for (i = partLen; i + 63 < inputLen; i += 64)
				MD5Transform(context->state, &input[i]);
			index = 0;
		}
		else i = 0;
		memcpy((byte *)&context->buffer[index], (byte *)&input[i], inputLen - i);
	}

	void Final(byte digest[16], MD5_CTX *context)
	{
		byte bits[8];
		uint index, padLen;
		Encode(bits, context->count, 8);
		index = (uint)((context->count[0] >> 3) & 0x3f);
		padLen = (index < 56) ? (56 - index) : (120 - index);
		Update(context, PADDING, padLen);
		Update(context, bits, 8);
		Encode(digest, context->state, 16);
		memset((byte *)context, 0, sizeof(*context));
	}
};

שימושים נפוצים

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

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

ביטחון

MD5 לא בטוח כיום לשימוש קריפטוגרפי והוא הוצא ממרבית התקנים וכן מ-SSL לאחר שהתגלו בו בעיות ופגמים רבים. למרות זאת הוא עדיין קיים בשימוש מוגבל. ב-1996 התגלה פגם בתכנון MD5 שבזמנו לא נחשב לבעיה חמורה, אולם לאור הממצאים מומחי הצפנה המליצו כבר אז לעבור לאלגוריתמים טובים יותר כמו פונקציות הגיבוב ממשפחת SHA שבחלקם התגלו גם הם כבעייתיים. ב-2004 הוכח ש-MD5 אינו מספק את המטרה העיקרית לשמה הוא פותח; עמידות מפני התנגשויות, כלומר אמור להיות קשה מאוד מבחינה חישובית למצוא שני קלטים שונים שאם מזינים אותם לפונקציית הגיבוב מקבלים פלט זהה. מסיבה זו MD5 אינו מתאים לתעודת מפתח ציבורי או חתימה דיגיטלית שהם מסתמכים על ההנחה שהתנגשויות בלתי אפשריות (חישובית). באותה שנה קבוצת חוקרים גילו פגמים חמורים נוספים. הם הראו איך אפשר להכין שני מסמכים שונים כך שיפיקו תמצית MD5 זהה. בשנים שלאחר מכן חלה התקדמות נוספת בשבירת האלגוריתם. בדצמבר 2008 קבוצת חוקרים השתמשה בטכניקות שהתגלו כדי לזייף תעודת מפתח ציבורי בתוך מספר שעות. נכון לשנת 2010 הוכרז על ידי ארגון SEI כי אלגוריתם MD5 נפרץ לחלוטין ואינו מתאים יותר לכל שימוש קריפטוגרפי. יישומים ממשלתיים נדרשים כיום להשתמש ב-SHA-2. ב-2012 נוזקת להבה ניצלה את חולשות MD5 כדי לזייף חתימה דיגיטלית של מיקרוסופט. כיום קיימות התקפות התנגשויות נגד MD5 שמסוגלות למצוא התנגשות בתוך שניות על מחשב ביתי. יתרה מזו, קיימת התקפה שנקראת chosen-prefix (תחילית-נבחרת) שמאפשרת ליצור התנגשות עבור שני קלטים עם תחילית קבועה בתוך מספר שעות עם חומרה סטנדרטית.

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

ראו גם

לקריאה נוספת

סיימון סינג, סודות ההצפנה, "ידיעות אחרונות".
Internet Security: Cryptographic Principles, Algorithms and Protocols.

הערות שוליים

^ Catalin Cimpanu, A quarter of major CMSs use outdated MD5 as the default password hashing scheme, ZDNet (באנגלית)
^ MD5 vulnerable to collision attacks, Carnegie Mellon University, ‏31/12/2008
^ Internet Standard: "The MD5 Message-Digest Algorithm"

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

32162259MD5

[1] Catalin Cimpanu, A quarter of major CMSs use outdated MD5 as the default password hashing scheme, ZDNet (באנגלית)

[2] MD5 vulnerable to collision attacks, Carnegie Mellon University, ‏31/12/2008

[3] Internet Standard: "The MD5 Message-Digest Algorithm"

[1]

[2]

[3]

MD5

תוכן עניינים

היסטוריה