קוד אימות מסרים

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

בקריפטוגרפיה, קוד אימות מסרים - Message Authentication Code בקיצור MAC, הוא שם כולל לקבוצה של פונקציות עם מפתח סודי המשמשות לאימות (Authentication) והבטחת שלמות מסרים (Message Integrity). פונקציית MAC מקבלת מפתח סודי ומסר באורך שרירותי ומפיקה פיסת מידע קצרה הנקראת תג המשמשת לאימות וזיהוי מסר. אלגוריתם קוד אימות מסרים הוא סימטרי במובן שהשולח והמקבל חייבים לשתף ביניהם מראש מפתח סודי, באמצעותו המקבל יכול לוודא שהמסמך שקיבל אותנטי ושלא נעשה שינוי בתוכנו. ללא ידיעת המפתח לא ניתן לייצר את התג הנכון, ולכן אם נעשה שינוי כלשהו בהודעה, היריב לא יצליח לשנות גם את התג בצורה שמתאימה להודעה ששונתה, והמקבל יבחין בשינוי. במערכות הצפנה מודרניות מנצלים את העובדה שהמשתמשים כבר משתפים מפתח סודי באמצעות פרוטוקול שיתוף מפתח אם באמצעים סימטריים כמו קרברוס או א-סימטריים כמו דיפי-הלמן.

הגדרה כללית[עריכת קוד מקור | עריכה]

דיאגרמת קוד אימות מסרים

אלגוריתם אימות מסרים מורכב משתי פונקציות;

  1. פונקציית חתימה S שמקבלת מסר כלשהו M המיועד לחתימה ומפתח סודי K (המשותף לשולח והמקבל) ומייצרת את תג האימות: T=S_K(M). התג T נשלח למקבל, יחד עם המסר M או בנפרד, בכל מקרה אפשר באופן גלוי כך שניתן לקריאה על ידי כל אחד.
  2. פונקציית אימות V_K(M,T) המקבלת שלושה פרמטרים, את המסר M, התג T והמפתח K ומחזירה תשובה 'אמת' אם המסר אותנטי או 'שקר' אם חל בו שינוי אפילו קל מאוד. באופן כללי, עבור כל פונקציית MAC בהינתן מסר כלשהו M ומפתח K תמיד יתקיים V_K(M,S_K(M))=\mbox{''True''}.

אורך התג בסיביות חייב להיות גדול מספיק כדי למנוע ניחוש. אם התג קטן מאוד, תוקף פוטנציאלי יכול לנסות לנחש את התג בכוח גס, ניסוי כל האפשרויות עד שנמצא תג מתאים למסר שהוא מעוניין לזייף, מבלי לדעת את המפתח. בהערכה גסה, אורך התג צריך להיות לפחות 64 סיביות. כך שניחוש באמצעות כוח גס יהיה בסיבוכיות 2^{64} ומעלה. פרוטוקול TLS, חלק מאבטחת שכבת התעבורה של האינטרנט, מיישם סכמות אימות מסרים באמצעות מספר פרימיטיבים קריפטוגרפיים (כמו MD5 ,SHA-1 ו-SHA-2) כדי לייצר תגי אימות באורכים של 32, 64, 96 או 128 סיביות.

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

למרות הדמיון בין פונקציית אימות מסרים לפונקציית גיבוב קריפטוגרפית, ישנו הבדל מהותי ביניהם. פונקציית MAC צריכה להיות עמידה בפני התקפת גלוי-נבחר הנקראת זיוף קיומי (Existential forgery). כלומר, נניח שהתוקף יכול להגיש שאילתות לאורקל היפותטי, שהמפתח הסודי K ידוע לו ומסוגל לייצר עם מפתח זה ערכי MAC לכל מסר. ונניח שהתוקף קיבל ממנו עבור n מסרים כלשהם שהוא בחר m_1,m_2,...,m_n, את התגים המתאימים להם t_i=S_K(m_i). לא יוכל עם מידע זה לייצר תג תקף עבור מסר אחר m גם אם הוא חסר משמעות. או בהינתן הזוג (m,t) מסר ותג מתאים, לייצר בלא ידיעת המפתח, תג אחר t' \ne t כך שהמחזיק במפתח הסודי יקבל V_K(m,t')=\mbox{''True''}. למרות שההתקפה נשמעת לא מעשית, בעולם האמיתי זהו מצב בהחלט אפשרי, למשל אם התוקף הצליח לשים ידו על מדיית אחסון כלשהי המכילה קבצים גלויים ותגי אימות מתאימים.

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

שימושים אפשריים[עריכת קוד מקור | עריכה]

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

הצפנה מאומתת[עריכת קוד מקור | עריכה]

Postscript-viewer-shaded.png ערך מורחב – הצפנה מאומתת

כיוון שצופן בלוקים סימטרי בדרך כלל אינו מספק אימות והבטחת שלמות, פרוטוקולי אבטחה רבים משלבים פונקציית MAC יחד עם אלגוריתם סימטרי כדי להנות מיתרונות שניהם. שילוב בין אימות מסרים להצפנה נקרא הצפנה מאומתת (Authenticated encryption) בקיצור AE והיא מקובלת במערכות הצפנה מודרניות. אופן השילוב אפשרי בכמה וריאציות. פרוטוקול SSL משלב אימות עם הצפנה בשיטה שנקראת "אימות והצפנה", תחילה מייצרים תג אימות מהמסר, לאחר מכן משרשרים את התג לטקסט הקריא ומצפינים הכול ביחד ומשדרים במצב מוצפן. פרוטוקול IPSec משלב בשיטה הפוכה כלומר "הצפנה ואימות", תחילה מצפינים את המסר, לאחר מכן מייצרים תג אימות מהטקסט המוצפן, אותו משדרים בגלוי יחד עם הטקסט המוצפן. SSH משתמש בטכניקה אחרת, מייצרים תג אימות מהטקסט הקריא, מצפינים את הטקסט הקריא בלבד ושולחים את הטקסט המוצפן עם התג באופן גלוי. השיטה האחרונה אינה מומלצת.

היסטוריה[עריכת קוד מקור | עריכה]

רעיון אימות מסרים עלה לראשונה ב-1977 כאשר הציע קמפבל (Campbell) להשתמש ב-DES כבסיס לאלגוריתם אימות מסרים. השם הכולל MAC ניתן בסביבות 1979 במהלך פיתוח תקן ANSI X9.9. אלגוריתמי MAC מיושמים בדרך כלל עם שיטות סימטריות או מפרימיטיבים קריפטוגרפיים אחרים כמו פונקציית גיבוב. קיימים גם אלגוריתמים ייעודיים, ביניהם Message Authenticator Algorithm בקיצור MAA שפותח בשנת 1983 על ידי דוויס וקליידן (Davis & Clayden) לבקשת שירותי הבנק האוטומטיים בבריטניה כחלק מתקן ISO. לאחר שהתגלו בו ליקויים אינו מומלץ כיום. וכן CRC-MAC שהוא אלגוריתם MAC המשתמש בצופן זרם ומבוסס גם על CRC. רעיון השימוש ב-CRC נולד בעקבות רעיון של ווגמן וקרטר (Wegman & Carter) לשלב פנקס חד פעמי ופונקציית גיבוב אקראית 'אוניברסלית' ליצירת אלגוריתם אימות מסרים. שיטה זו מספקת ביטחון מוכח בהנחה שקיימת פונקציית PRF בטוחה.

אלגוריתמים[עריכת קוד מקור | עריכה]

כל פונקציה פסבדו-אקראית קריפטוגרפית (PRF) מתאימה למימוש אלגוריתם MAC. בניסוח פורמלי אם נתונה פונקציית PRF מסוג F:K\times X \to Y, אפשר לבנות סכמת אימות מסרים עם פונקציית החתימה הפועלת כך; t=F(K,M) ופונקציית האימות תהיה זהה כלומר תחזיר אמת רק אם t = F(K,M). אם הפונקציה הפסאודו-אקראית בטוחה, אזי סכמת האימות הזו תהיה בטוחה. למעשה אפשר לבנות קוד אימות מסרים באמצעות כל צופן בלוקים בטוח כמו AES, או פונקציית גיבוב קריפטוגרפית. קיימות שתי שיטות עקריות:

  • קוד אימות מבוסס צופן בלוקים סימטרי (כמו וריאציות של CBC-MAC). נפוץ בעיקר בשימוש בנקאי. נתמך בתקנים X9.9 ו-X9.19 וכן FIPS 186-3.
  • קוד אימות מבוסס פונקציית גיבוב קריפטוגרפית (כמו וריאציות של HMAC). נפוץ ביישומי אבטחת אינטרנט כמו SSL, IPSec, SSH וכדומה.

CBC-MAC[עריכת קוד מקור | עריכה]

תיאור סכמת CBC הסימן \oplus מייצג XOR ו-E היא פונקציית הצפנה מוסכמת כמו AES.

CBC-MAC בגרסה הבסיסית דומה למצב הפעלה CBC של צופן בלוקים (קיצור של Cipher Block Chaining). הרעיון הכללי הוא כדלהלן: נתונה פונקציית הצפנה סימטרית \ E עם מפתח סודי \ K והמסר \ M כשהוא מחולק ל-t בלוקים בגודל קבוע \ m_1,m_2,...,m_t, חישוב התג (כאן \ H) נעשה כדלהלן, תחילה: H_1=E_K(m_1) ואז עבור \ 2 \le i \le t מחשבים \ H_i=E_K(m_i\oplus  H_{i-1}) (אורך בלוק נקבע לפי הצופן שבשימוש, במקרה של AES הוא 128 סיביות). הסימן \oplus מייצג XOR. ותג האימות הוא H_t.

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

השיטה המתוארת נקראת "raw CBC" והיא אינה בטוחה אם המסרים לחתימה אינם באורך קבוע וידוע מראש. בגלל התקפה שנקראת Extension Attack הרעיון הבסיסי הוא כדלהן: התוקף משיג מסר m ותג t מתאים כך שמתקיים E_k(m)=t ואז טוען שהתג t מתאים למסר (m \ \| \ t \oplus m) והטענה נכונה בשל הזהות הבאה:

E_K(m \ \rVert \  t\oplus m)=E_K(E_K(m)\oplus(t\oplus m))=E_K(t\oplus t\oplus m)=t,

אפשר לשים לב שבגלל ש-XOR הופכי של עצמו, הופעת t פעמיים מבטלת אחת את השנייה ונותר רק m, שעבורו התג תקף. כלומר התוקף הצליח לייצר מסר אחר שהתג t תקף גם עבורו וזה בניגוד להגדרת MAC. (הסימן \rVert מייצג שרשור, כלומר צרוף שתי מחרוזות למחרוזת אחת גדולה). גרסה יותר בטוחה נקראת ECBC והיא (כמתואר בתרשים) תוספת הצפנה של התוצאה בסוף התהליך עם מפתח סודי אחר. תוצאת ה-MAC תהיה תוצאת ההצפנה האחרונה, או רק קטע ממנה. הוכח שאם פונקציית ההצפנה היא PRF כך גם חלק ממנה, כל עוד אינו ניתן לניחוש בכוח גס.


NMAC[עריכת קוד מקור | עריכה]

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

הבסיס לקוד אימות HMAC (להלן) נקרא קסקדה (Cascade) או NMAC (קיצור של Nested MAC), פותח ב-1996 על ידי בלייר רן קנטי וקרוציק[1] והוכח כבטוח. הרעיון של NMAC הוא לעשות שימוש בפונקצייה חד-כיוונית כמו פונקציית גיבוב עם מפתח או צופן בלוקים כקופסה שחורה באופן שמוליד קוד אימות בטוח. יתרון אחד של שיטה זו שאין תלות בפונקציה ספציפית וניתן להחליפה בכל פונקציה מתאימה אחרת. פונקציית גיבוב בדרך כלל מהירה יותר לכן עדיפה, אולם אינה פועלת עם מפתח, דרך אחת להפוך אותה לפונקציית הצפנה עם מפתח היא להחליף את וקטור האתחול הקבוע בדרך כלל במפתח ההצפנה סודי המשותף לשולח והמקבל. המבנה של NMAC הוא כדלהלן. בהינתן הפונקציה F_K(m) ושני מפתחות הצפנה K_1,K_2 תג האימות מחושב על ידי:

tag=F_{K_2}(F_{K_1}(m))

הפונקציה הפנימית מיושמת על כל הבלוקים m_i בזה אחר זה. כל בלוק מוצפן עם מפתח k_i שהוא תוצאה של הצפנת הבלוק הקודם, כאשר k_0 הוא המפתח הסודי המסופק על ידי המשתמש ו-k_i=F_{k_{i-1}}(m_i). אפשר להחליף את פונקציית הגיבוב בצופן בלוקים E כמתואר בתרשים. תוצאת הפונקציה האחרונה או חלק ממנה היא תג האימות. גם במקרה זה אופן הריפוד זהה וכן כדי שהשיטה תהיה בטוחה ההצפנה האחרונה צריכה להיות עם מפתח אחר, אחרת הסכמה תהיה פגיעה להתקפה המתוארת לעיל. לביטחון נוסף יש המשרשרים ערך ריפוד קבוע כלשהו לפני ההצפנה האחרונה כך: tag=F_{K_2}(F_{K_1}(m)\ \| \ pad). ביטחון המבנה המתואר נשען על בטחון הפונקציה הפנימית. ככל שהיא בטוחה, מבנה NMAC בטוח גם הוא, תחת מודלים קריפטוגרפיים סטנדרטיים. כלומר בהתקפת כוח גס ניסיון לזייף את התג שקולה לניסיון לפרוץ צופן הבלוקים או פונקציית הגיבוב שבשימוש. התקפת יום הולדת כנגד פונקציית גיבוב, פחות מעשית במקרה זה כי התג תלוי במפתח סודי.

OMAC[עריכת קוד מקור | עריכה]

תיאור סכמת CMAC הסימן \oplus מייצג XOR ו-E היא פונקציית הצפנה מוסכמת כמו AES.

דרך אחרת שפותרת מהצורך להוסיף 'בלוק-דמה', נקראת OMAC קיצור של One key MAC או CMAC (קיצור של Cipher based MAC). היא מבוססת על CBC-MAC, פועלת עם שלושה מפתחות ומתחלקת לשני סוגים OMAC1 ו-OMAC2. תחילה מצפינים את כל הבלוקים עם המפתח הראשון בשיטת CBC, בסוף התהליך אם אורך המסר הוא כפולה של גודל הבלוק מצפינים את התוצאה האחרונה עם המפתח השני, אם לא, מצפינים עם המפתח השלישי והתוצאה של ההצפנה האחרונה תהיה התג (ראה תרשים). כאן שני המפתחות הנוספים הם פונקציה של המפתח הראשון (שהיא פונקציה אקראית 'אוניברסלית' באמצעות חישוב כפל מודולרי בפולינומים). בגרסת OMAC1 תחילה מחשבים את L=E_k(0^n), דהיינו הצפנה של מחרוזת אפסים באורך n באמצעות המפתח הראשון ואז המפתח השני הוא L\cdot u=L\ \ll \ 1 (הסימן \ll הוא הזזה לשמאל של כל הסיביות פוזיציה אחת, כשהסיבית השמאלית ביותר נפלטת) ואם הסיבית הגבוהה (MSB) של המפתח היא '1' מחסרים מהתוצאה באמצעות XOR את הקבוע \mbox{0x0...87} (התחילית \mbox{0x} מייצגת בסיס הקסדצימלי כנהוג בשפת C). באופן דומה מחשבים את המפתח השלישי: L\cdot u^2=(L\cdot u)\ \ll \ 1, ושוב אם הסיבית הגבוהה היא '1' מבצעים XOR עם אותו קבוע. גרסת OMAC2 שונה במעט, המפתח השלישי הוא L\cdot u^{-1} והוא מחושב על ידי הזזה לימין במקום לשמאל וחיבור XOR מותנה עם הפולינום הקבוע \mbox{0x80...43}.

אלגוריתם CMAC שנקרא בתחילה XCBC, פותח על ידי בלאק ורוגווי (Black & Rogaway) במיוחד כדי להתגבר על החסרון העיקרי באלגוריתם אימות מסרים מבוסס CBC-MAC (הבטוח לשימוש רק עבור מסרים באורך קבוע). אלגוריתם זה הומלץ על ידי NIST כתקן אימות מסרים במאי 2005.

שים לב שמדובר בכפל פולינומים מעל שדה בינארי מורחב F_{2^n} לכן x הוא פולינום (\mbox{0x02} בייצוג הקסדצימלי), הפעולה L\cdot x מקבילה בעצם לכפל ב-2 או אופרטור הזזה בסיביות שמאלה צעד אחד (Shift left) וצמצום מודולרי על ידי חיסור מותנה ב-XOR (במידה שהסיבית הגבוהה היא '1' שאז דרוש צמצום) עם פולינום אי פריק קבוע באורך 128 סיביות (x^{128}+x^7+x^2+x+1 או \mbox{0x00..87} בייצוג הקדסצימלי). כמו כן הערך L\cdot x^{-1} שקול להזזה בסיביות לימין צעד אחד וחיסור מותנה ב-XOR עם הקבוע x^{127}+x^5+x^3+x+1.

PMAC[עריכת קוד מקור | עריכה]

תיאור סכמת PMAC, הסימן \oplus מייצג XOR ו-E היא פונקציית הצפנה מוסכמת.

גרסת MAC מקבילית שנקראת PMAC (קיצור של Parallelizable MAC) פותחה על ידי בלאק ורוגווי ב-2002 כדי להתגבר על בעיה בקוד אימות CBC שהוא סידרתי באופיו לכן במקרה של צורך בשינוי בלוק אחד, צריך לבצע את כל תהליך החתימה מהתחלה. בנוסף לא ניתן לחלק את הביצוע בין מספר מעבדים באופן מקבילי. PMAC מבצע (ראה תרשים) הצפנה בנפרד של כל בלוק עם המפתח הסודי K בנוסף ל-XOR עם ערך נוסף שהוא פונקציה בשדה סופי המחושבת באופן רקורסיבי כדלהלן: תחילה L_0=E_K(0^n) (כלומר הצפנת מחרוזת אפסים עם צופן הבלוקים והמפתח הסודי K) ואז בכל שלב L_i=L_{i-1}\cdot x והמפתח להצפנת כל הבלוקים של המסר למעט הבלוק האחרון m_t הוא \gamma_i\cdot L המחושב רקורסיבית: \gamma_i\cdot L=(\gamma_{i-1}\cdot L)\oplus L(\mbox{ntz}(i)) כאשר \gamma_1=1. הפונקציה \mbox{ntz}(i) מייצגת את מספר האפסים המסיימים בערך i, לדוגמה \mbox{ntz}(7)=0 וכן \mbox{ntz}(8)=3. כל הבלוקים המוצפנים מחוברים ב-XOR ומתקבל \Sigma. את הבלוק האחרון m_t מצפינים בדרך שונה התלויה במצב הריפוד, כלומר אם אורך המסר אינו כפולה של גודל הבלוק בדיוק שאז נדרש ריפוד (בשיטה המתוארת לעיל), מתבצע XOR של הבלוק האחרון עם \Sigma. אם הבלוק האחרון שלם ולא נדרש ריפוד, מבצעים XOR נוסף עם הערך L\cdot x^{-1}. התג יהיה חלק מתוצאת ההצפנה של \Sigma.

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

HMAC[עריכת קוד מקור | עריכה]

HMAC הוא קוד אימות מסרים גנרי הדומה ל-NMAC ופועל עם פונקציית גיבוב קריפטוגרפית בשילוב עם מפתח סודי. HMAC פותח על ידי בלייר, קנטי וקרווציק ב-1996 והוכח כבטוח, תחת הנחה שפונקציית הגיבוב בטוחה לפי מודלים רגילים. כלומר הפונקציה אמורה להיות חד-כיוונית וחסינת התנגשויות (אם כי הדרישה האחרונה אינה הכרחית תמיד). בפועל כוללים בשם הפונקציה את פונקציית הגיבוב, לדוגמה בשילוב עם SHA-1 הקוד ייקרא HMAC-SHA1. ביטחון השיטה מבוסס על חוזקה של פונקציית הגיבוב. הגדרה הכללית ללא תלות בפונקציית הגיבוב היא כדלהלן:

t=H(K \oplus \ \mbox{opad}\ \rVert \ H(K \oplus \mbox{ipad} \ \rVert \ M))

K הוא המפתח הסודי ו-M הוא המסר לחתימה, הערכים ipad ו-opad הם קבועים מוסכמים שאינם סודיים, הנקראים כך בשל אופן שימוש בהם, 'פד פנימי' ו'פד חיצוני'. תיאור השיטה כדלהלן:

  1. מרפדים את המפתח באפסים עד שמקבלים B בתים (64 בתים בדרך כלל).
  2. מבצעים חיבור בינארי XOR עם \mbox{ipad}=\mbox{0x363636...} (בגודל B בתים).
  3. משרשרים לתוצאה את M.
  4. מחשבים את ערך הגיבוב H של התוצאה משלב 3.
  5. מבצעים חיבור בינארי של הבתים משלב 1 עם \mbox{opad}=\mbox{0x5C5C5C...} (באורך B בתים).
  6. משרשרים את התוצאה האחרונה עם הערך שהתקבל משלב 4.
  7. מחשבים את ערך הגיבוב של התוצאה האחרונה.
  8. התג יהיה חלק מהסיביות של תוצאת הגיבוב האחרונה בהתאם לצורך.

UMAC[עריכת קוד מקור | עריכה]

אלגוריתם אימות מסרים UMAC[2] (קיצור של Universal MAC) פותח על ידי בלאק, הלוי, קרייציק, קרובץ ורוגאווי ב-1999 והורחב בשנת 2000. הוא בנוי על פרימיטיבים קריפטוגרפיים ידועים ונחשב לבטוח ומהיר מקודמיו כמו כן האלגוריתם אינו מוגן בזכויות יוצרים כלשהם. UMAC הוא קוד אימות מסרים בסגנון וואגמן וקרטר, המשלב פונקציית גיבוב אוניברסלית, מחולל אקראי קריפטוגרפי ושני מפתחות הצפנה סודיים. תחילה מפיקים ערך גיבוב קטן מהמסר באמצעות פונקציית הגיבוב אותו ממסכים ב-XOR עם ערך אקראי הנקרא "פד פסאודו אקראי" (שמהווה חלק מהמפתח הסודי) והתוצאה נקראת תג-UMAC שיכול להיות בכמה גדלים (32, 64, 96 או 128 סיביות). השילוב מתבצע כך: \ H_{K_1}(M) \oplus F_{K_2}(\mbox{Nonce}). הפונקציה \ H היא פונקציית גיבוב שכאן משולבת עם מפתח הצפנה. הפונקציה \ F היא פונקציה פסאודו אקראית (במקרה זה מבוססת על צופן בלוקים AES) והערך Nonce הוא ערך חד-פעמי כלשהו כלומר לכל תג-UMAC יש לייצר ערך אחר שצריך להיות ידוע גם למקבל אך אינו חייב להיות סודי, למשל מספר רץ יספיק (אם שני הצדדים מסונכרנים). האלגוריתם מהיר כיוון שהמסר M עובר גיבוב באמצעות פונקציית גיבוב מהירה, התוצאה שהיא קטנה יותר מוצפנת באמצעות פונקציית ההצפנה שהיא יותר איטית. ביטחון האלגוריתם תלוי בסודיות המפתחות ובהנחה שהפרימיטיבים הקריפטוגרפיים שבשימוש בטוחים. תיאור האלגוריתם על ידי המחברים מכיל מפרט מדויק למימוש בטוח של הפונקציות השונות המרכיבות את האלגוריתם.

קישורים חיצוניים[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ Keying Hash Functions for Message Authentication
  2. ^ "UMAC: Fast and Secure Message Authentication". John Black, Shai Halevi, Hugo Krawczyk, Ted Krovetz, and Phillip Rogaway. Advances in Cryptology - CRYPTO '99. Lecture Notes in Computer Science, vol. 1666, Springer-Verlag, 1999, pp. 216-233.