MD5

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

היסטוריה

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

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

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

5. פלט

הפלט הוא שרשור ערכי הביניים מהסבב האחרון:

קוד לדוגמה

להלן קוד שלם בשפת 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 לא בטוח כיום לשימוש קריפטוגרפי והוא הוצא ממרבית התקנים וכן מ-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 ידוע בפשטותו ומהירותו, לכן ישנן חברות אבטחה שעדיין עושות בו שימוש.