CWC mode

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

אם המסר המיועד להצפנה הוא $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 \neq {\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_{1}K_{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_{1}x^{n}+Y_{2}x^{n-1}+Y_{3}x^{n-2}+\cdots +Y_{n}x+Y_{n+1}{\text{ mod }}(2^{127}-1)$

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

$(Y_{1}y^{m}+Y_{3}y^{m-1}+\cdots +Y_{n})+(Y_{2}y^{m}+Y_{4}y^{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 ניתן ליישום באופן מקבילי במיוחד בחומרה להשגת תפוקה גבוהה יותר. מידת המקביליות ניתנת לשליטה בידי המיישם. ביישום ממוטב בחומרה אפשר להגיע לתפוקה של 50 גיגה לשנייה.
• מפתח הצפנה; 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 פשוט וקל ליישום ולהטמעה בתוכנה או בחומרה.