CWC mode

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

בקריפטוגרפיה, Carter-Wegman Counter mode הוא מצב הפעלה של צופן בלוקים שפותח ב-2004 על ידי טאדיושי קונו מאוניברסיטת קליפורניה, ג'ון ויאגה מ-Virginia Tech ו-דאג ווייטינג מ-Hifn כיום חלק מ-exar, המספק הצפנה מאומתת, פועל לפי פרדיגמה "הצפנה ולאחריה אימות" ושייך לקטגוריה AEAD (הצפנה מאומתת עם מידע נלווה). בניגוד לצופן בלוקים כשלעצמו המספק רק סודיות של בלוק בגודל קבוע, CWC מספק סודיות והגנה על שלמות ואימות מסר בכל אורך רצוי על ידי הצפנה עם צופן בלוקים סימטרי בעדיפות לאלגוריתם חופשי כמו AES במצב מונה ולאחר מכן ייצור תג אימות באמצעות בפונקציית גיבוב 'אוניברסלית' מקבילית בסגנון קרטר-ווגמן, לאימות המידע המוצפן וטקסט נוסף המשויך אליו שצריך להבטיח את שלמותו אך עליו להשאר גלוי, כמו קובץ כותר המכיל הגדרות או כתובות. ל-CWC חמש תכונות חשובות שמציבות אותו כמועמד מועדף לתקן הצפנה מאומתת; ביטחון מוכח, מקביליות, ביצועים גבוהים בחומרה ובתוכנה והעדר זכויות יוצרים. במימוש אופטימלי בחומרה אמור להגיע לתפוקה של 10Gbps. הוא מהיר יותר ממצבי ההפעלה CCM ו-EAX אך פחות מהיר בהשוואה לOCB שמוגן בפטנט. מועמדותו של OCB לתקן IEEE 802.11 נדחתה בגלל נושא זכויות יוצרים. האלגוריתם נכלל ברשימה שמנהל NIST של הערכת אלגוריתמים לצורך תקן הצפנה מאומתת‏[1].

אם המסר המיועד להצפנה הוא M המכיל מחרוזת סיביות באורך שרירותי כלשהו והמידע הנלווה אליו הוא A. האלגוריתם מצפין את M באמצעות מפתח הצפנה אקראי K ומפיק טקסט מוצפן \sigma ולאחר מכן מאמת את \sigma ואת A באמצעות מפתח האימות שנגזר ממפתח ההצפנה, על ידי ייצור תג אימות \tau באורך הרצוי שנשלח יחד עם הצופן לצד המקבל ושמאפשר לו להבטיח שהמסר המוצפן לא שונה או הוחלף במהלך ההעברה. תג האימות מבטיח מעצם ההגדרה שתוקף פוטנציאלי לא יכול לזייפו. כלומר ליצור תג אימות תקף עבור מסר מוצפן אחר שלא הגיע מהשולח האותנטי, מבלי ידיעת מפתח ההצפנה הסודי שהשולח והמקבל משתפים ביניהם. ההעדפה היא שגודל בלוק של צופן הבלוקים יהיה 128 סיביות ומספר הקריאות לצופן הבלוקים הוא \left \lceil |M|/128\right \rceil+2. פונקציית הגיבוב המשמשת לאימות מבוססת על חישוב פולינומים מודולו הראשוני 2^{127}-1. המעלה של פולינום האימות היא d=\left \lceil |A|/96\right \rceil +\left \lceil|M|/96\right \rceil. החישובים ניתנים להאצה באמצעות טבלאות. למשל אם מספר פעולות הכפל בחישוב פולינום אחד הוא d כשכל אחד מהם צורך 127\times 127 פעולות בסיביות, הרי בשימוש בטבלת חזקות בגודל n אפשר לקצר את מספר הפעולות ל-d-m פעולות כפל בגודל 96\times 127 ועוד m פעולות של כפל מלא, כאשר m=\left \lceil(d+1)/n\right \rceil -1.

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

בתיאור האלגוריתם יופיעו הסימנים הבאים: אם N ו-l שלמים חיוביים כך שמתקיים N < 2^l אזי הפונקציה \text{tostr}(N,l) פירושה הקידוד של N כמחרוזת של l סיביות לפי סדר בתים גדול (big-endian). בסדר בתים גדול הסיבית המשמעותית ביותר לא נחשבת כסיבית הסימן. לדוגמה המספר 30 בבסיס בינארי הוא המחרוזת "11110". אם x ו-y הן מחרוזות סיביות אזי |x| הוא אורך המחרוזת והביטוי x\oplus y הוא XOR של x עם y. הפונקציה \text{toint}(x) מייצגת את השלם המקביל למחרוזת x לפי סדר בתים גדול. לדוגמה \text{toint}(\text{''10000010''})=2^7+2=130. אם נתונה הסיבית b הביטוי b^n מתייחס לסיבית b כשהיא משוכפלת n פעמים למשל 0^7=0000000. הביטוי x \stackrel{$}{\longleftarrow} f(y) פירושו הפלט x של הפונקציה f עם הקלט y ומחרוזת פסאודו-אקראית כלשהי שנבחרה באופן אחיד מתוך מרחב המחרוזות האפשריות.

אלגוריתם ההצפנה הסימטרי המסומן בקיצור \mathcal{SE} שבשימוש CWC, מיוצג על ידי אוסף של שלושה אלגוריתמים \mathcal{SE}=(\mathcal{K}_e,\mathcal{E},\mathcal{D}) מעל מרחב מפתח כלשהו \text{KeySp}_{se}, מרחב Nonce (וקטור אתחול) המסומן \text{NonceSp}_{se}\subseteq \{0,1\}^n, מרחב המידע \text{MsgSp}_{se}\subseteq \{0,1\}^* ומרחב המידע הנלווה \text{AdSp}_{se}\subseteq \{0,1\}^* באורך שרירותי כלשהו. הסימון CWC-BC-tl מתייחס למצב ההפעלה CWC עם צופן בלוקים ספציפי המכונה כאן בקיצור BC ועם אורך תג רצוי tl למשל במקרה של AES עם תג באורך 96 סיביות אפשר להחליפו בסימון CWC-AES-96. המפתח K מופק על ידי K \stackrel{$}{\longleftarrow} \mathcal{K}_e יהיה באורך שנקבע לפי האלגוריתם ולפי העדפה (לפחות 128 סיביות). ה-Nonce צריך להיות באורך n=88 סיביות. המסר M והמידע הנלווה A, מחרוזות בינאריות באורך שאינו עולה על 2^{32}-1 בלוקים של 128 סיביות. הביטוי \sigma=BC_K(M) מתייחס להפעלה של צופן הבלוקים עם המפתח K על המסר M והפלט הוא \sigma.

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

CWC מורכב משישה מודולים המתוארים בפסאודו קוד הבא:

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

\mathcal{K}
K \stackrel{$}{\longleftarrow}  \{0,1\}^{kl}
\text{Return }K

האלגוריתם בוחר מפתח אקראי כלשהו מתוך מרחב המפתחות, המשמש להצפנה ולהכנת מפתח האימות.

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

\mathbf{CWC}\text{-}\mathbf{ENC}_K(N,A,M)
  1. \sigma=\text{CWC-CTR}_K(N,M)
  2. \tau=\text{CWC-MAC}_K(N,A,\sigma)
  3. \text{Return }\sigma \ \| \ \tau

הפונקציה מנצלת את הפונקציות CWC-CTR ו-CWC-MAC המתוארות להלן, כדי להצפין ולאמת את המידע. הפלט הוא \sigma,\tau המשורשרים יחד. \sigma הוא הטקסט המוצפן והוא באורך טקסט המקור ו-\tau הוא תג האימות והוא באורך המוגדר על ידי הפרמטר tl. כך שהתנפחות הטקסט המוצפן אינה משמעותית.

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

\mathbf{CWC}\text{-}\mathbf{DEC}_K(N,A,C)
  1. \text{If }|C|<\text{ tl then return INVALID}
  2. \text{Parse }C\text{ as }\sigma \ \| \ \tau\text{ where }| \tau |=tl
  3. \text{If }A\notin \text{AdSp}_{\text{CWC-BC-tl}} \text{ or }\sigma\notin \text{MsgSp}_{\text{CWC-BC-tl}}\text{ then Return INVALID}
  4. \text{If }\tau \ne \text{CWC-MAC}_K(N,A,\sigma)\text{ then return INVALID}
  5. M=\text{CWC-CTR}_K(N,\sigma)
  6. \text{Return }M

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

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

\mathbf{CWC}\text{-}\mathbf{CTR}_K(N,M)
  1. \alpha=  \left \lceil |M|/128 \right \rceil
  2. \text{For } i=1\text{ to }\alpha\text{ do: }s_i=\text{BC}_K(10^7\ \| \ N \ \| \ \text{tostr}(i,32))
  3. x=\text{first }|M| \text{ bits of }s_1\| s_2 \| \cdots \| s_\alpha
  4. \sigma=x\oplus M
  5. \text{Return }\sigma

הפונקציה מיישמת הצפנה במצב 'מונה', המונה מורכב מוקטור אתחול ואינדקס i, שמוצפנים יחד באמצעות צופן הבלוקים BC, ממנו מייצרים באופן איטרטיבי זרם-מפתח באורך הרצוי המשמש להצפנת המסר M ב-XOR כמו בצופן זרם.

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

\textbf{CWC-HASH}_K(A,\sigma)
  1. Z=\text{ last }127\text{ bits of BC}_K(110^{126})
  2. K_h=\text{toint}(Z)
  3. l=\text{ min integer such that }96\text{ divides } |A||0^l|
  4. l'=\text{ min integer such that }96\text{ divides }|\sigma||0^l|
  5. X=A \ \| \ 0^l \ \| \ \sigma \ \| \ 0^{l'}
  6. \beta=|X|/96
  7. X=X_1,X_2,...,X_\beta
  8. \text{For }i=1\text{ to }\beta\text{ do: } Y_i=\text{toint}(X_i)
  9. l_\sigma=|\sigma|/8
  10. l_A=|A|/8
  11. Y_{\beta+1}=2^{64}\cdot l_A+l_\sigma
  12. R=Y_1K_h^\beta+\cdots+Y_\beta K_h+Y_{\beta+1}\text{ mod }(2^{127}-1)
  13. \text{Return tostr}(R,128)

הפונקציה מייצרת ערך גיבוב (hash) מהטקסט המוצפן \sigma ומהמידע הנלווה A כשהם מרופדים באפסים כנדרש כדי שיהיו כפולות של 96 סיביות ומשורשרים למחרוזת אחת ארוכה שאליה מתייחסים כאל פולינום כשהמקדמים שלו הם שלמים בגודל 96 סיביות כל אחד. תוצאת הפונקציה R היא חישוב הפולינום המתואר, מודולו המספר הראשוני 2^{127}-1.

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

\mathbf{CWC}\text{-}\mathbf{MAC}_K(N,A,\sigma)
  1. R=\text{BC}_K(\text{CWC-HASH}_K(A,\sigma))
  2. \tau=\text{BC}_K(10^7 \ \| \ N \ \| \ 0^{32})\oplus R
  3. \text{Return first }tl\text{ bits of }\tau

קוד האימות מוכן באמצעות חיבור ב-XOR של תוצאת פונקציית הגיבוב המתוארת לעיל והצפנה של וקטור האתחול באמצעות צופן הבלוקים \text{BC} עם מפתח ההצפנה K. התוצאה היא tl הסיביות הראשונות של \tau.

ביטחון[עריכת קוד מקור | עריכה]

הגדרת הביטחון של CWC מבוססת על הרעיון של לובי וראקוף לגבי פרמוטציה אקראית (PRP). אם E:\{0,1\}^k\times \{0,1\}^L \rightarrow \{0,1\}^L הוא צופן בלוקים כלשהו והביטוי \text{Perm}(L) מייצג את קבוצת כל התמורות האפשריות מעל \{0,1\}^L. אם נתון יריב המנסה לתקוף את המערכת, המסומן בקיצור A ויש לו גישה לאורקל המחזיר סיבית אחת (אמת או שקר). אזי אומרים ש:

\text{Adv}_F^{prp}(A)=\Pr[f \stackrel{$}{\longleftarrow} E : A^{f(\cdot)}=1]-\Pr[g \stackrel{$}{\longleftarrow} \text{Perm}(L):A^{g(\cdot)}=1]

ופירושו שכדי שהצופן E יהיה בטוח, ה"יתרון" שבידי יריב בעל יכולת סבירה, המריץ את PRP, המאפשר לו להבחין (distinguish) בין תוצאות של מימוש אקראי כלשהו של E לבין תמורה אקראית Perm "זניח". צופן מודרני כמו AES נחשב כ-PRP בטוח לפי הגדרה זו (אם כי זה לא הוכח).

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

בהצפנה במצב מונה אפשר לחלק את העבודה בין כמה יחידות עיבוד. כל יחידה יכולה לחשב בנפרד את הקטע המתאים מזרם המפתח לפי אינדקס הבלוק i, המפתח K וה-Nonce. הליבה של מנגנון האימות בסגנון קרטר-ווגמן ניתנת גם היא לביצוע מקבילי בשל העובדה שמנגנון האימות ממיר את זוג הערכים (A,\sigma) לפולינום

Y_1x^n+Y_2x^{n-1}+Y_3x^{n-2}+\cdots +Y_nx+Y_{n+1}\text{ mod }(2^{127}-1)

שים לב שהמקדמים Y_i הם שלמים בגודל 96 סיביות ו-x הוא שלם מודולו 2^{127}-1. אפשר לראות שחישוב פולינום זה יכול להתבצע באופן מקבילי כיוון שאפשר לכתוב את הפולינום המתואר כך

(Y_1y^m+Y_3y^{m-1}+\cdots+Y_n)+(Y_2y^m+Y_4y^{m-1}+\cdots+Y_{n+1})\text{ mod }(2^{127}-1)

כאשר y=x^2\text{ mod }(2^{127}-1) ו-m=(n-1)/2. לצורך ההדגמה נניח ש-n אי-זוגי. כעת אפשר לחשב את שני צידי המשוואה במקביל ולחברם לאחר מכן. בדרך זו אפשר להשיג מקביליות נוספת על ידי חלוקה ל-j פולינומים ב-y'=x^j\text{ mod }(2^{127}-1).

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

  • ביטחון מוכח; CWC נחשב לאלגוריתם AEAD בטוח בהנחה שצופן הבלוקים שביסודו בטוח. הנחה זו סבירה כי לדעת הרוב אלגוריתם כמו AES נחשב PRP (פרמוטציה פסאודו-אקראית). CWC מבטיח סודיות, אימות והבטחת שלמות המידע M ומידע נלווה A בהינתן וקטור אתחול כלשהו N ומפתח אקראי כלשהו K.
  • כשל מצטבר; לאור האמור בהנחה שצופן הבלוקים שבשימוש בטוח, אפשר להוכיח שכל ניסיון זיוף מצד יריב בעל עוצמת חישוב סבירה יתגלה בסבירות גבוהה מאוד.
  • מקביליות; CWC ניתן ליישום באופן מקבילי במיוחד בחומרה להשגת תפוקה גבוהה יותר. מידת המקביליות ניתנת לשליטה בידי המיישם. ביישום ממוטב בחומרה אפשר להגיע לתפוקה של 10 גיגה לשנייה.
  • מפתח הצפנה; CWC מוגדר כאלגוריתם עם מפתח הצפנה יחיד אם כי פנימית האלגוריתם משתמש בשני מפתחות שונים להצפנה ואימות. מפתח הגיבוב המשמש לאימות נגזר ממפתח ההצפנה הראשי.
  • וקטור אתחול; ב-CWC נקבע וקטור האתחול בקיצור IV לגודל 11 בתים. האלגוריתם בטוח בתנאי שלא נעשה שימוש חוזר ב-IV להצפנת שני מסרים שונים, עם אותו מפתח. וקטור האתחול יכול להיות כל מספר ייחודי כמו מונה ואינו חייב להיות סודי.
  • דרישות זיכרון; CWC ניתן ליישום בכמה אופנים, בעיקרון דרישות הזיכרון המינימליות הן בעצם דרישות הזיכרון של צופן הבלוקים שביסוד האלגוריתם. למשל אפשר ליישם את AES ללא צריכת זיכרון, אך קיימים יישומים ממוטבים שצורכים 4K בתים. במידה ומיישמים את אלגוריתם האימות של CWC באמצעות טבלאות דרישת הזיכרון עולה בהתאם.
  • הכנה מוקדמת; במצב מונה אפשר להכין מראש את זרם מפתח ההצפנה ללא תלות בטקסט הקריא. אך לא ניתן לחשב מראש את פלט CWC-HASH המשמש לאימות. הכנה מוקדמת, במידה שערכים מסוימים קבועים או משתנים לעתים רחוקות, מאפשרת שיפור בביצועים על חשבון צריכת זיכרון.
  • אורך מקסימלי; המסר הארוך ביותר שניתן להצפנה באמצעות CWC הוא 128\cdot (2^{32}-1) סיביות. CWC לא הוגדר לטפל בכל אורך רצוי אלא רק בכפולות של 128 סיביות.
  • התנפחות; תוצאת האלגוריתם היא המינימלית האפשרית במונחים של צופן בלוקים, שהוא אורך הטקסט המוצפן \sigma פלוס אורך התג tl.
  • יעילות; מספר הקריאות לצופן הבלוקים הפנימי הוא לכל היותר \left \lceil |M|/128\right \rceil+3 בשל הצורך בקריאה אחת נוספת להכנת מפתח האימות.
  • און ליין; אפשר להצפין או לפענח מיידית חלק מהמידע שנעשה זמין ללא תלות בחלקים אחרים. לעובדה זו יתרון בהזרמת מדיה, אולם יש לזכור שהמקבל אינו יכול לוודא את שלמות המידע שהתקבל עד שיגיעו כל החלקים. הוא יכול לאחסן את המידע בחוצץ זמני ולהמתין להגעת יתר החלקים.
  • זכויות יוצרים; לפי הצהרת המפתחים CWC חופשי לשימוש ואינו מוגן בפטנט או זכויות יוצרים.
  • פשטות; לטענת המפתחים CWC פשוט וקל ליישום ולהטמעה בתוכנה או בחומרה.

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

  1. ^ [1]