ZUC

ZUC הוא צופן זרם שפותח ב-2010 על ידי האקדמיה הסינית למדע עבור טכנולוגיית LTE. זהו צופן זרם סינכרוני, מותאם לחומרה ותוכנה כאחד, פועל ברמת מילים באורך 32 סיביות, מקבל מפתח הצפנה באורך 128 סיביות, וקטור אתחול באורך 128 סיביות ומייצר מילים פסאודו-אקראיות באורך 32 סיביות המשמשות חלק מזרם מפתח להצפנה ופענוח של המידע מילה אחר מילה. ZUC שוכן בליבת תקן 3GPP להצפנה מאומתת של שיחה סלולרית באלגוריתמים EEA3 להצפנה ו-EIA3 לאימות. הצופן קרוי על שמו של המתמטיקאי הסיני זו צ'אנגזי שחי במאה החמישית לספירה.

תיאור הצופן

ZUC מחולק לשני מצבי הפעלה, מצב הכנה ומצב העבודה. בשלב הראשון מפתח ההצפנה ווקטור האתחול נטענים לתוך המצב הפנימי והצופן מופעל (clocked) ללא יצירת פלט. בשלב השני בכל פעימת שעון נוצרת מילה פסאודו אקראית באורך 32 סיביות.
בהמרות ממילים לבתים מתייחסים לכל הערכים כאל מספרים שלמים לפי סדר בתים קטן. לדוגמה אם  ו- אז . הסימן "" מייצג הזזה מעגלית לשמאל בגבולות מילה באורך  סיביות.הסימנים "" ו-"" מייצגים הזזה (shift) של סיביות לימין או לשמאל בהתאמה, במספר פוזיציות לפי הערך המופיע לאחר הסימן. הסימן  מייצג חיבור מודולו . הסימן  הוא XOR. ל-ZUC שלוש שכבות כמתואר בתרשים משמאל:

 שכבה עליונה - LFSR בעל 16 מצבים (Taps).
 שכבה אמצעית - סידור מחדש ברמה של סיביות.
 שכבה תחתונה - פונקציה אי-ליניארית.

LFSR
בשכבה העליונה הצופן מכיל אוגר זיזה ממושב ליניארי הכולל 16 כניסות באורך 31 סיביות כל אחת המסומנות  כאשר . בכל פעימה תכולת האוגר מוזזת צעד אחד לימין כלומר תכולת כל תא מועתקת לתא הבא שלימינו והתא הראשון () מתעדכן לפי הפונקציה להלן. בשלב האתחול האוגר מקבל מילה אחת  באורך 31 סיביות המתקבלת על ידי הסרת הסיבית הימנית (הכי פחות משמעותית) של הפלט  של הפונקציה האי-ליניארית, כלומר . בשלב האתחול בהינתן הקלט  מתבצעים המהלכים הבאים:
 ;
 ;
 ;
 .
במצב עבודה ה-LFSR אינו מקבל קלט ופועל כדלהלן:
 ;
 ;
 .
מהיבט פרקטי כפל האלמנט   בחזקות  של 2 מעל השדה  מתבצע על ידי הזזה מעגלית של  לשמאל  סיביות. לכן במהלך 1 לעיל כל שנדרש הוא חיבור מודולו  לאחר סדרה של כמה הזזות. ההזזה המעגלית בקוד נראית כך:
.

ובאופן כללי מהלך 1 המתואר לעיל ניתן לביצוע בתוכנה באופן הבא:
.

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

סידור מחדש (BitReorganization)
בשכבה האמצעית של האלגוריתם הנקראת בקיצור BR, מחלצים 128 סיביות משמונה תאים של ה-LFSR במיקומים המתוארים להלן ומהם מרכיבים ארבע מילים באורך 32 סיביות. שלוש המילים הראשונות ישמשו קלט לפונקציה האי-ליניארית להלן ואילו המילה הרביעית משתתפת ביצירת מילת פלט אחת של זרם המפתח. המיקומים ב-LFSR מהם נוטלים סיביות הם: . ארבע המילים האמורות מיוצגות על ידי  אותם מרכיבים על ידי  חצאי הקלט לפי הסדר הבא: 
 ;
 ;
 ;
 .
הסמלים  ו- מייצגים את החצי העליון והחצי התחתון של המילה בהתאמה. למשל  פירושו הסיביות  ולא  של  היות ש- מוגדר באורך 31 סיביות. לדוגמה בשורה 1 לעיל הערך של  הוא שרשור של 16 הסיביות המשמעותיות ביותר של  החל מהסיבית במיקום ה-15 ועד הסיבית ה-30 עם 16 הסיביות הפחות משמעותיות של  החל מהסיבית במיקום ה-0 ועד הסיבית ה-15.

פונקציה אי-ליניארית
השכבה התחתונה כוללת פונקציה  המכילה שני תאי זיכרון  ו- באורך 32 סיביות כל אחד. הקלט הוא  שהם פלט השכבה הקודמת והפלט הוא מילה  באורך 32 סיביות. ביתר פירוט:
 ;
 ;
 ;
 ;
 .
הפונקציה  היא תיבות החלפה S-box בגודל 32x32 סיביות והפונקציות  ו- הן פונקציות ליניאריות כמתואר להלן.

תיבות החלפה
 הוא תיבת החלפה s-box בגודל 32x32 המורכבת מארבע תיבות  שהן פונקציות אי-ליניאריות קבועות בצורת ארבע טבלאות בגודל 8x8 (המכילות 256 כניסות בגודל 8 סיביות). כאשר  וכן . והטבלאות  ו- מובאות להלן. הפונקציה  מקבלת את הקלט  בגודל בית אחד ומחזירה את הערך הנמצא בכניסה הנמצאת בשורה  ובעמודה  בטבלה וכן לגבי יתר הבתים של מילת הקלט (בסך הכול ארבעה בתים במילה), , ו- כאשר  ו- הם בתים. הפונקציה  אם כן מוגדרת כך:  כאשר .

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

הכנת מפתח
תהליך ההכנה מקבל את המפתח הראשוני המסופק על ידי המשתמש מחולק ל-16 בתים  (128 סיביות) וכן וקטור האתחול  (16 בתים), וטוען אותם לתוך 16 הכניסות של אוגר ה-LFSR בתוספת קבוע  באורך 240 סיביות המובא להלן, המחולק ל-16 מקטעים באורך 15 סיביות כל אחד . הערך ההתחלתי של כל כניסה באוגר הוא שרשור של שלושת הערכים: קטע אחד מהמפתח, חלק אחד מהקבוע  להלן וחלק מוקטור האתחול, כך: 
 עבור .

הקבוע  הוא:
,
.

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

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

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

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

ביטחון
ZUC הוא צופן חדש יחסית והוא בעצם שיפור של הצופן SNOW. חוקרים גילו שהצופן בגרסה המקורית (1.4) היה פגיע להתקפת מוצפן נבחר על וקטור האתחול. במקרים מסוימים הבדלים בוקטור האתחול הניבו מפתח הצפנה זהה מה שמצמצם את אורך המפתח האפקטיבי לכ-100 סיביות במקום 128. בצופן זרם שימוש במפתח הצפנה זהה להצפנת חלקים מהנתונים מהווה פגיעה הרסנית במיוחד בביטחון ההצפנה. כדי למנוע התקפה זו הם המליצו להחליף את ה-XOR בחיבור () מודולו  בביטוי () בשלב האתחול, גרסה זו של הצופן נקראת 1.6 והיא מעודכנת בתיאור הצופן לעיל. ZUC הוא צופן מהיר מאוד בהשוואה לצפנים כמו SNOW. הוא למעשה מהמהירים ביותר הקיימים כיום וכן בשל המפתח הארוך ווקטור האתחול הארוך (128 סיביות כל אחד) מספק הגנה מספיק טובה מפני כמה התקפות ידועות כמו: התקפת מפתח חלש, התקפות ניחוש, התקפה אלגברית, התקפות תיזמון, התקפה דיפנרציאלית והתקפת קירוב ליניארי. הצופן אינו מספק הגנה טובה מפני התקפת ערוץ צדדי המתמקדת בגרף צריכת האנרגיה שלו במהלך הצפנה או פענוח. חוקרים הראו שההתקפה הנקראת DPA קיצור של Differential Power Analysis אפשרית נגד הצופן במידה שלתוקף יכולת למדוד את צריכת האנרגיה במחשב בו מבוצעת ההצפנה.

וקטור בדיקה
לדוגמה אם המפתח הוא:

וקטור האתחול הוא:

המילה הראשונה של פלט הצופן צריכה להיות: .

קוד לדוגמה

typedef unsigned char byte;
typedef unsigned int uint;

uint LFSR[16];
uint F_R1;
uint F_R2;
uint BRC[4];

byte S0[256] = {
	0x3e,0x72,0x5b,0x47,0xca,0xe0,0x00,0x33,0x04,0xd1,0x54,0x98,0x09,0xb9,0x6d,0xcb,
	0x7b,0x1b,0xf9,0x32,0xaf,0x9d,0x6a,0xa5,0xb8,0x2d,0xfc,0x1d,0x08,0x53,0x03,0x90,
	0x4d,0x4e,0x84,0x99,0xe4,0xce,0xd9,0x91,0xdd,0xb6,0x85,0x48,0x8b,0x29,0x6e,0xac,
	0xcd,0xc1,0xf8,0x1e,0x73,0x43,0x69,0xc6,0xb5,0xbd,0xfd,0x39,0x63,0x20,0xd4,0x38,
	0x76,0x7d,0xb2,0xa7,0xcf,0xed,0x57,0xc5,0xf3,0x2c,0xbb,0x14,0x21,0x06,0x55,0x9b,
	0xe3,0xef,0x5e,0x31,0x4f,0x7f,0x5a,0xa4,0x0d,0x82,0x51,0x49,0x5f,0xba,0x58,0x1c,
	0x4a,0x16,0xd5,0x17,0xa8,0x92,0x24,0x1f,0x8c,0xff,0xd8,0xae,0x2e,0x01,0xd3,0xad,
	0x3b,0x4b,0xda,0x46,0xeb,0xc9,0xde,0x9a,0x8f,0x87,0xd7,0x3a,0x80,0x6f,0x2f,0xc8,
	0xb1,0xb4,0x37,0xf7,0x0a,0x22,0x13,0x28,0x7c,0xcc,0x3c,0x89,0xc7,0xc3,0x96,0x56,
	0x07,0xbf,0x7e,0xf0,0x0b,0x2b,0x97,0x52,0x35,0x41,0x79,0x61,0xa6,0x4c,0x10,0xfe,
	0xbc,0x26,0x95,0x88,0x8a,0xb0,0xa3,0xfb,0xc0,0x18,0x94,0xf2,0xe1,0xe5,0xe9,0x5d,
	0xd0,0xdc,0x11,0x66,0x64,0x5c,0xec,0x59,0x42,0x75,0x12,0xf5,0x74,0x9c,0xaa,0x23,
	0x0e,0x86,0xab,0xbe,0x2a,0x02,0xe7,0x67,0xe6,0x44,0xa2,0x6c,0xc2,0x93,0x9f,0xf1,
	0xf6,0xfa,0x36,0xd2,0x50,0x68,0x9e,0x62,0x71,0x15,0x3d,0xd6,0x40,0xc4,0xe2,0x0f,
	0x8e,0x83,0x77,0x6b,0x25,0x05,0x3f,0x0c,0x30,0xea,0x70,0xb7,0xa1,0xe8,0xa9,0x65,
	0x8d,0x27,0x1a,0xdb,0x81,0xb3,0xa0,0xf4,0x45,0x7a,0x19,0xdf,0xee,0x78,0x34,0x60
};

byte S1[256] = {
	0x55,0xc2,0x63,0x71,0x3b,0xc8,0x47,0x86,0x9f,0x3c,0xda,0x5b,0x29,0xaa,0xfd,0x77,
	0x8c,0xc5,0x94,0x0c,0xa6,0x1a,0x13,0x00,0xe3,0xa8,0x16,0x72,0x40,0xf9,0xf8,0x42,
	0x44,0x26,0x68,0x96,0x81,0xd9,0x45,0x3e,0x10,0x76,0xc6,0xa7,0x8b,0x39,0x43,0xe1,
	0x3a,0xb5,0x56,0x2a,0xc0,0x6d,0xb3,0x05,0x22,0x66,0xbf,0xdc,0x0b,0xfa,0x62,0x48,
	0xdd,0x20,0x11,0x06,0x36,0xc9,0xc1,0xcf,0xf6,0x27,0x52,0xbb,0x69,0xf5,0xd4,0x87,
	0x7f,0x84,0x4c,0xd2,0x9c,0x57,0xa4,0xbc,0x4f,0x9a,0xdf,0xfe,0xd6,0x8d,0x7a,0xeb,
	0x2b,0x53,0xd8,0x5c,0xa1,0x14,0x17,0xfb,0x23,0xd5,0x7d,0x30,0x67,0x73,0x08,0x09,
	0xee,0xb7,0x70,0x3f,0x61,0xb2,0x19,0x8e,0x4e,0xe5,0x4b,0x93,0x8f,0x5d,0xdb,0xa9,
	0xad,0xf1,0xae,0x2e,0xcb,0x0d,0xfc,0xf4,0x2d,0x46,0x6e,0x1d,0x97,0xe8,0xd1,0xe9,
	0x4d,0x37,0xa5,0x75,0x5e,0x83,0x9e,0xab,0x82,0x9d,0xb9,0x1c,0xe0,0xcd,0x49,0x89,
	0x01,0xb6,0xbd,0x58,0x24,0xa2,0x5f,0x38,0x78,0x99,0x15,0x90,0x50,0xb8,0x95,0xe4,
	0xd0,0x91,0xc7,0xce,0xed,0x0f,0xb4,0x6f,0xa0,0xcc,0xf0,0x02,0x4a,0x79,0xc3,0xde,
	0xa3,0xef,0xea,0x51,0xe6,0x6b,0x18,0xec,0x1b,0x2c,0x80,0xf7,0x74,0xe7,0xff,0x21,
	0x5a,0x6a,0x54,0x1e,0x41,0x31,0x92,0x35,0xc4,0x33,0x07,0x0a,0xba,0x7e,0x0e,0x34,
	0x88,0xb1,0x98,0x7c,0xf3,0x3d,0x60,0x6c,0x7b,0xca,0xd3,0x1f,0x32,0x65,0x04,0x28,
	0x64,0xbe,0x85,0x9b,0x2f,0x59,0x8a,0xd7,0xb0,0x25,0xac,0xaf,0x12,0x03,0xe2,0xf2
};

uint EK_d[16] = {
	0x44D7, 0x26BC, 0x626B, 0x135E, 0x5789, 0x35E2, 0x7135, 0x09AF,
	0x4D78, 0x2F13, 0x6BC4, 0x1AF1, 0x5E26, 0x3C4D, 0x789A, 0x47AC
};
// c = a + b mod (2^31 – 1)
uint AddM(uint a, uint b)
{
	uint c = a + b;
	return (c & 0x7FFFFFFF) + (c >> 31);
}

#define MulByPow2(x, k) ((((x) << k) | ((x) >> (31 - k))) & 0x7FFFFFFF)

void LFSRWithInitialisationMode(uint u)
{
	uint f = LFSR[0];
	uint v = MulByPow2(LFSR[0], 8);
	f = AddM(f, v);
	v = MulByPow2(LFSR[4], 20);
	f = AddM(f, v);
	v = MulByPow2(LFSR[10], 21);
	f = AddM(f, v);
	v = MulByPow2(LFSR[13], 17);
	f = AddM(f, v);
	v = MulByPow2(LFSR[15], 15);
	f = AddM(f, v);
	f = AddM(f, u);
	for (int i = 0; i < 15; i++)
		LFSR[i] = LFSR[i + 1];
	LFSR[15] = f;
}

void LFSRWithWorkMode()
{
	uint f = LFSR[0];
	uint v = MulByPow2(LFSR[0], 8);
	f = AddM(f, v);
	v = MulByPow2(LFSR[4], 20);
	f = AddM(f, v);
	v = MulByPow2(LFSR[10], 21);
	f = AddM(f, v);
	v = MulByPow2(LFSR[13], 17);
	f = AddM(f, v);
	v = MulByPow2(LFSR[15], 15);
	f = AddM(f, v);
	for (int i = 0; i < 15; i++)
		LFSR[i] = LFSR[i + 1];
	LFSR[15] = f;
}

void BitReorganization()
{
	BRC[0] = ((LFSR[15] & 0x7FFF8000) << 1) | (LFSR[14] & 0xFFFF);
	BRC[1] = ((LFSR[11] & 0xFFFF) << 16) | (LFSR[9] >> 15);
	BRC[2] = ((LFSR[7] & 0xFFFF) << 16) | (LFSR[5] >> 15);
	BRC[3] = ((LFSR[2] & 0xFFFF) << 16) | (LFSR[0] >> 15);
}

#define ROT(a, k) (((a) << k) | ((a) >> (32 - k)))

uint L1(uint X)
{
	return (X ^ ROT(X, 2) ^ ROT(X, 10) ^ ROT(X, 18) ^ ROT(X, 24));
}

uint L2(uint X)
{
	return (X ^ ROT(X, 8) ^ ROT(X, 14) ^ ROT(X, 22) ^ ROT(X, 30));
}

#define MAKEU32(a, b, c, d) (((uint)(a) << 24) | ((uint)(b) << 16) | ((uint)(c) << 8) | ((uint)(d)))

uint F()
{
	uint W = (BRC[0] ^ F_R1) + F_R2;
	uint W1 = F_R1 + BRC[1];
	uint W2 = F_R2 ^ BRC[2];
	uint u = L1((W1 << 16) | (W2 >> 16));
	uint v = L2((W2 << 16) | (W1 >> 16));
	F_R1 = MAKEU32(S0[u >> 24], S1[(u >> 16) & 0xFF], S0[(u >> 8) & 0xFF], S1[u & 0xFF]);
	F_R2 = MAKEU32(S0[v >> 24], S1[(v >> 16) & 0xFF], S0[(v >> 8) & 0xFF], S1[v & 0xFF]);
	return W;
}

#define MAKEU31(a, b, c) (((uint)(a) << 23) | ((uint)(b) << 8) | (uint)(c))

void Initialization(byte* k, byte* iv)
{
	LFSR[0] = MAKEU31(k[0], EK_d[0], iv[0]);
	LFSR[1] = MAKEU31(k[1], EK_d[1], iv[1]);
	LFSR[2] = MAKEU31(k[2], EK_d[2], iv[2]);
	LFSR[3] = MAKEU31(k[3], EK_d[3], iv[3]);
	LFSR[4] = MAKEU31(k[4], EK_d[4], iv[4]);
	LFSR[5] = MAKEU31(k[5], EK_d[5], iv[5]);
	LFSR[6] = MAKEU31(k[6], EK_d[6], iv[6]);
	LFSR[7] = MAKEU31(k[7], EK_d[7], iv[7]);
	LFSR[8] = MAKEU31(k[8], EK_d[8], iv[8]);
	LFSR[9] = MAKEU31(k[9], EK_d[9], iv[9]);
	LFSR[10] = MAKEU31(k[10], EK_d[10], iv[10]);
	LFSR[11] = MAKEU31(k[11], EK_d[11], iv[11]);
	LFSR[12] = MAKEU31(k[12], EK_d[12], iv[12]);
	LFSR[13] = MAKEU31(k[13], EK_d[13], iv[13]);
	LFSR[14] = MAKEU31(k[14], EK_d[14], iv[14]);
	LFSR[15] = MAKEU31(k[15], EK_d[15], iv[15]);
	F_R1 = 0;
	F_R2 = 0;
	uint nCount = 32, w;
	while (nCount > 0)
	{
		BitReorganization();
		w = F();
		LFSRWithInitialisationMode(w >> 1);
		nCount--;
	}
}
void GenerateKeystream(uint* pKeystream, int KeystreamLen)
{
	BitReorganization();
	F(); // discard the output of F
	LFSRWithWorkMode();

	for (int i = 0; i < KeystreamLen; i++)
	{
		BitReorganization();
		pKeystream[i] = F() ^ BRC[3];
		LFSRWithWorkMode();
	}
}

ראו גם
 צופן זרם
 GSM
 SNOW

הערות שוליים

צפני זרם