במילים ההגדרה אומרת שהסיכויים של היריב להצליח בניסוי formula_35 נמוכים משיעור זניח כלשהו שנקבע על ידי פונקציית הזניחות. כלומר במקרה כזה הסיכויים כל כך נמוכים שאפשר להתעלם מהם. העובדה שמוענקת ליריב עוצמה כזו - לא רק שהוא רשאי לבקש תגי אימות עבור כל מסר שיחפוץ, אלא שכל מסר שהוא ימצא תג מתאים עבורו אפילו אם אינו בעל משמעות כלשהי ייחשב הדבר כשבירה של האלגוריתם, הכרחית במטרה להכליל את ההגדרה עבור כל יישום אפשרי של האלגוריתם בעולם האמיתי. למשל ההגדרה של "מסר משמעותי" היא לחלוטין תלוית יישום. בעוד שיישום אחד מייצר תגי אימות רק עבור מסרים הכתובים בשפה האנגלית, יישום אחר עשוי לייצר תגי אימות עבור מחרוזות בינאריות שיכולות לייצג כל דבר כמו קוד מכונה, קבצים דחוסים תמונות וכדומה.
אורך התג בסיביות חייב להיות גדול מספיק כדי למנוע ניחוש. אם התג קטן מאוד, תוקף פוטנציאלי יכול לנסות לנחש את התג בכוח גס, ניסוי כל האפשרויות עד שנמצא תג מתאים למסר שהוא מעוניין לזייף, מבלי לדעת את המפתח. בהערכה גסה, אורך התג צריך להיות לפחות 64 סיביות. כך שניחוש באמצעות כוח גס יהיה בסיבוכיות formula_49 ומעלה. פרוטוקול TLS, חלק מאבטחת שכבת התעבורה של האינטרנט, מיישם סכמות אימות מסרים באמצעות מספר פרימיטיבים קריפטוגרפיים (כמו MD5, SHA-1 ו-SHA-2) כדי לייצר תגי אימות באורכים של 32, 64, 96 או 128 סיביות.
קוד תיקון שגיאות CRC אינו יכול לשמש לאימות מסרים, כיוון שלמרות שמבטיח כי לא בוצע שינוי כתוצאה משגיאות אקראיות בזמן המעבר, אינו מספק הגנה כנגד שגיאה זדונית (Malicious). כלומר תוקף פוטנציאלי יכול לשנות את המסר ולהחליף את התג בתג אחר המתאים לו ולמקבל לא תהיה דרך לעלות על זה. קוד אימות מסרים מערב שימוש במפתח סודי לכן ההתקפה האמורה לא תועיל לתוקף, כיוון שחסר בידיו מידע כדי לייצר תג מתאים למסר ששינה והוא המפתח הסודי.
אלגוריתם MAC שונה מחתימה דיגיטלית בכך שערכי MAC נוצרים ומאומתים באמצעות מפתח סודי משותף לשולח והמקבל, לכן אינו יכול לספק תכונת "אי הכחשה" כבחתימה דיגיטלית. כל משתמש המסוגל לאמת קוד MAC של מסר כלשהו מסוגל גם לייצר קוד MAC עבור כל מסר אחר באמצעות אותו מפתח. בניגוד לחתימה דיגיטלית, שבה החתימה מתבצעת אך ורק באמצעות המפתח הפרטי שבידי השולח והמאמת אינו מסוגל לעשות שימוש כלשהו במפתח האימות מלבד כמובן אימות החתימה.
שימושים אפשריים.
MAC מתאים להגנה על מחשב מפני וירוסים. לדוגמה, באמצעות סיסמת המשתמש אפשר לייצר מפתח הצפנה סודי, איתו מייצרים תגי אימות מתאימים עבור כל הקבצים (החשובים) במחשב לצורך אימות עתידי. במקרה שתוכנה זדונית תנסה לשנות אחד מהם הדבר יתגלה מיד בבדיקת האימות. רצוי כמובן להכניס בתג גם את שם הקובץ כדי למנוע החלפה של שמות הקבצים. מאותה סיבה אנטי-וירוס ירצה להגן על קובץ החתימות מפני שינויים זדוניים. כמו כן קיימים מקרים נוספים בהם חשוב להגן על שלמות המידע ולא בהכרח על סודיותו. למשל מידע מסחרי כמו מחירון או מידע פרסומי כלשהו, שייתכן שהמפרסם או בעל העסק ירצה להבטיח שבעוד שהמידע נגיש לכול, עדיין תהיה אפשרות בידי עמיתים המחזיקים במפתח המתאים לאתר שינויים זדוניים אם נעשו.
הצפנה מאומתת.
כיוון שצופן בלוקים סימטרי בדרך כלל אינו מספק אימות והבטחת שלמות, פרוטוקולי אבטחה רבים משלבים פונקציית MAC יחד עם אלגוריתם סימטרי כדי ליהנות מיתרונות שניהם. שילוב בין אימות מסרים להצפנה נקרא הצפנה מאומתת (Authenticated encryption) בקיצור AE והיא מקובלת במערכות הצפנה מודרניות. אופן השילוב אפשרי בכמה וריאציות. פרוטוקול SSL משלב אימות עם הצפנה בשיטה שנקראת "אימות והצפנה", תחילה מייצרים תג אימות מהמסר, לאחר מכן משרשרים את התג לטקסט הקריא ומצפינים הכול ביחד ומשדרים במצב מוצפן. פרוטוקול IPSec משלב בשיטה הפוכה כלומר "הצפנה ואימות", תחילה מצפינים את המסר, לאחר מכן מייצרים תג אימות מהטקסט המוצפן, אותו משדרים בגלוי יחד עם הטקסט המוצפן. SSH משתמש בטכניקה אחרת, מייצרים תג אימות מהטקסט הקריא, מצפינים את הטקסט הקריא בלבד ושולחים את הטקסט המוצפן עם התג באופן גלוי.
השיטה האחרונה אינה מומלצת.
היסטוריה.
רעיון אימות מסרים עלה לראשונה ב-1977 כאשר הציע קמפבל (Campbell) להשתמש ב-DES כבסיס לאלגוריתם אימות מסרים. השם הכולל MAC ניתן בסביבות 1979 במהלך פיתוח תקן ANSI X9.9. אלגוריתמי MAC מיושמים בדרך כלל עם שיטות סימטריות או מפרימיטיבים קריפטוגרפיים אחרים כמו פונקציית גיבוב. קיימים גם אלגוריתמים ייעודיים, ביניהם Message Authenticator Algorithm בקיצור MAA שפותח בשנת 1983 על ידי דוויס וקליידן (Davis &amp; Clayden) לבקשת שירותי הבנק האוטומטיים בבריטניה כחלק מתקן ISO. לאחר שהתגלו בו ליקויים אינו מומלץ כיום. וכן CRC-MAC שהוא אלגוריתם MAC המשתמש בצופן זרם ומבוסס גם על CRC. רעיון השימוש ב-CRC נולד בעקבות רעיון של ווגמן וקרטר (Wegman &amp; Carter) לשלב פנקס חד פעמי ופונקציית גיבוב אקראית 'אוניברסלית' ליצירת אלגוריתם אימות מסרים. שיטה זו מספקת ביטחון מוכח בהנחה שקיימת פונקציית PRF בטוחה.
אלגוריתמים.
כל פונקציה פסבדו-אקראית קריפטוגרפית (PRF) מתאימה למימוש אלגוריתם MAC. בניסוח פורמלי אם נתונה פונקציית PRF מסוג formula_50, אפשר לבנות סכמת אימות מסרים עם פונקציית החתימה הפועלת כך; formula_51 ופונקציית האימות תהיה זהה כלומר תחזיר אמת רק אם formula_52. אם הפונקציה הפסאודו-אקראית בטוחה, אזי סכמת האימות הזו תהיה בטוחה. למעשה אפשר לבנות קוד אימות מסרים באמצעות כל צופן בלוקים בטוח כמו AES, או פונקציית גיבוב קריפטוגרפית. קיימות שתי שיטות עיקריות:
CBC-MAC.
CBC-MAC בגרסה הבסיסית דומה למצב הפעלה CBC של צופן בלוקים (קיצור של Cipher Block Chaining). הרעיון הכללי הוא כדלהלן: נתונה פונקציית הצפנה סימטרית formula_53 עם מפתח סודי formula_54 והמסר formula_55 כשהוא מחולק ל-formula_3 בלוקים בגודל קבוע formula_57, חישוב התג (כאן formula_58) נעשה כדלהלן, תחילה: formula_59 ואז עבור formula_60 מחשבים formula_61 (אורך בלוק נקבע לפי הצופן שבשימוש, במקרה של AES הוא 128 סיביות). הסימן formula_62 מייצג XOR. ותג האימות הוא formula_63. אם אורך המסר לא מתחלק בגודל הבלוק מרפדים באפסים לפי הצורך.
השיטה המתוארת נקראת "raw CBC" והיא אינה בטוחה אם המסרים לחתימה אינם באורך קבוע וידוע מראש. בגלל התקפה שנקראת Extension Attack הרעיון הבסיסי הוא כדלהלן: התוקף משיג מסר formula_2 ותג formula_3 מתאים כך שמתקיים formula_66 ואז טוען שהתג formula_3 מתאים למסר formula_68 והטענה נכונה בשל הזהות הבאה:
אפשר לשים לב שכיוון ש-XOR הופכי של עצמו, הופעת formula_3 פעמיים מבטלת אחת את השנייה ונותר רק formula_2, שעבורו התג תקף. כלומר התוקף הצליח לייצר מסר אחר שהתג formula_3 תקף גם עבורו וזה בניגוד להגדרת MAC. (הסימן formula_73 מייצג שרשור, כלומר צרוף שתי מחרוזות למחרוזת אחת גדולה). אפשר לפתור את הבעיה על ידי הוספת בלוק המכיל את אורך המסר, את בלוק האורך יש להוסיף בתחילת המסר ולא בסופו ולכן עובדה זו יכולה להוות בעיה מסיבות של יעילות (כאשר אורך המסר אינו ידוע מראש). גרסה אחרת יותר בטוחה נקראת ECBC והיא (כמתואר בתרשים) תוספת הצפנה של התוצאה בסוף התהליך עם מפתח סודי אחר. תוצאת ה-MAC תהיה תוצאת ההצפנה האחרונה, או רק קטע ממנה. הוכח שאם פונקציית ההצפנה היא PRF כך גם חלק ממנה, כל עוד אינו ניתן לניחוש בכוח גס.
הגדרת הביטחון של קוד אימות ECBC המבוסס על פונקציה פסאודו-אקראית היא:
Adv הוא כינוי ל"יתרון", ל-A נתונה פונקציית PRF, ול-formula_75 הפונקציה formula_76 אקראית אמיתית. formula_77 מייצג את אורך בלוק בסיביות, formula_78 מייצג את מספר השאילתות (או מספר הבלוקים החתומים). הביטוי אומר שה"יתרון" של A לא יהיה גדול משמעותית מהיתרון של B (פלוס טווח שגיאה formula_79). בגלל פרדוקס יום הולדת הפונקציה תהיה בטוחה רק אם formula_80 במקרה של AES זה אומר שהיא תהיה בטוחה אם formula_81, כלומר שלא בוצעה חתימה על formula_49 מסרים עם אותו מפתח.
הבסיס לקוד אימות HMAC (להלן) נקרא קסקדה (Cascade) או NMAC (קיצור של Nested MAC), פותח ב-1996 על ידי בלייר רן קנטי וקרוציק והוכח כבטוח. הרעיון של NMAC הוא לעשות שימוש בפונקציה חד-כיוונית כמו פונקציית גיבוב עם מפתח או צופן בלוקים כקופסה שחורה באופן שמוליד קוד אימות בטוח. יתרון אחד של שיטה זו שאין תלות בפונקציה ספציפית וניתן להחליפה בכל פונקציה מתאימה אחרת. פונקציית גיבוב בדרך כלל מהירה יותר לכן עדיפה, אולם אינה פועלת עם מפתח, דרך אחת להפוך אותה לפונקציית הצפנה עם מפתח היא להחליף את וקטור האתחול הקבוע בדרך כלל במפתח ההצפנה סודי המשותף לשולח והמקבל. המבנה של NMAC הוא כדלהלן. בהינתן הפונקציה formula_83 ושני מפתחות הצפנה formula_84 תג האימות מחושב על ידי: