Salsa20

Salsa20 הוא צופן זרם שפותח ב-2005 על ידי דניאל ברנשטיין באוניברסיטת אילינוי בשיקגו והוצע עבור פרויקט eSTREAM האירופאי. ב-2008 נבחר על ידי eSTREAM בסיבוב השלישי (Phase 3), כאחד מארבעת האלגוריתמים המובילים במסגרת פרופיל 1 בקטגוריית צופן זרם בתוכנה. הגרעין של Salsa20 הוא פונקציה פסאודו-אקראית הפועלת על קלט ופלט בגודל 64 בתים ומיושמת כצופן זרם במצב מונה. הפונקציה מקבלת מפתח הצפנה סודי באורך 128 או 256 סיביות, ערך ייחודי חד-פעמי באורך 64 סיביות הנקרא Nonce ומשמש כוקטור אתחול, מונה המייצג את מספר הבלוק באורך 64 סיביות וקבועים נוספים. על ידי גיבוב הערכים הללו כשהם משולבים יחד, מייצרת פלט פסאודו-אקראי באורך 64 בתים, אותו מחברים בחיבור בינארי עם בלוק טקסט קריא לקבלת טקסט מוצפן. אפשר להצפין עם מפתח אחד עד  בתים של מידע. המבנה הזה מעניק לצופן יתרון ביכולת לשחזר כל בלוק ספציפי מהטקסט המוצפן בזמן קבוע. מימוש ממוטב של צופן Salsa יכול להגיע ליעילות בסדר גודל של כמעט 14 מחזורי שעון לבית או כ-643 מגה לשנייה (לעומת RC4 שמגיע לסדר גודל של 200 מגה לשנייה בקירוב). נכון לשנת 2014 נחשב Salsa לצופן בטוח ולא ידוע על התקפה יעילה נגדו.

תיאור האלגוריתם

Salsa20 הוא צופן זרם סינכרוני (שבו המפתח מופק ללא תלות בטקסט הקריא או המוצפן), הפועל על יחידת מידע בגודל 64 בתים. השלד העיקרי מורכב מפונקציית גיבוב הכוללת שילוב של שלוש פעולות אריתמטיות פשוטות; חיבור מודולו  המבוצע במילים בגודל 32 סיביות, חיבור מודולו 2 (המסומן XOR) והזזה מעגלית (rotation) על מילים (הזזה של כל סיביות המילה שמאלה או ימינה במספר פוזיציות לפי פרמטר, כאשר הסיביות הקיצוניות שנפלטות מצד אחד מוחזרות מהצד השני). ומפיקה פלט בגודל 64 בתים פסאודו-אקראיים שמרכיבים את 'המצב הפנימי' של הצופן. פונקציית הגיבוב הופכת לפונקציית הצפנה בשיטת ורנם, שבה תוצאת הגיבוב הופכת למפתח הצפנה מורחב בגודל 16 מילים. בלוק הטקסט הקריא בגודל 16 מילים מוצפן מילה אחר מילה, בדרך זו: . הפענוח זהה, כיוון ש-XOR הופכי של עצמו. סדר הפעולות בתוך הליבה של Salsa20 הוא "או-מוציא של חיבור לאחר הזזה מעגלית" בקיצור ARX (ראשי תיבות של שלוש הפעולות לפי הסדר האמור). שילוב זה הוכח כבטוח כנגד התקפה דיפרנציאלית (ראה להלן) וכן מבטיח עמידות כנגד התקפת תזמון (timing attack).

ביטחון ויעילות

ב-2005 דווח על סוג של ההתקפה דיפרנציאלית נגד גרסה מצומצמת של סלסה בחמשה סבבים, מסומן בקיצור Salsa20/5 בסיבוכיות זמן של  בקירוב. מפתח ההתקפה זכה באלף דולר מאת דניאל ברנשטיין שהבטיח את הפרס לכל מי שיצליח להציג "קריפטואנליזה הכי מעניינת של סלסה". ב-2006 הצליחו מספר חוקרים לפתח התקפה כנגד Salsa20/6 בסיבוכיות זמן של  וכן התקפת Related key על Salsa20/7 בזמן של . ב-2007 פותחה התקפה על Salsa20/8 בזמן של  עם  מפתחות. ב-2008 פותחה התקפה נגד Salsa20/7 בזמן של  וכן התקפה על Salsa20/8 בזמן של . ב-2012 התקפה של אמסון ושי כנגד Salsa20/8 הצליחה לשבור את הצופן בזמן של  או בזמן של  במקרה של מפתח 256 סיביות עם 8 סבבים. ב-2013 פורסמה הוכחה שצופן סלסה מעל 15 סבבים בטוח כנגד התקפה דיפרנציאלית, כלומר לא נמצאו מאפיינים דיפרנציאליים בהסתברות גבוהה מ- כך שהיא אינה יעילה מכוח גס.
Salsa20 מהיר יותר מ-AES ובמבחני ביצועים של eSTREAM נמצא שבעשרים סבבים הצופן מסוגל להצפין בקצב של 3.93 מחזורי שעון לבית על Xeon בעל ליבה כפולה 3 גיגה-הרץ. כמו כן קיימות שתי גרסאות של הצופן פחותות סבבים הנקראות Salsa20/8 ו-Salsa20/12 עם שמונה סבבים או 12 סבבים בהתאמה, המיועדים למשתמשים הרואים צורך בצופן יעיל ומוכנים להקריב מעט בביטחונו.

ChaCha

ב-2008 הציע דניאל ברנשטיין את משפחת ChaCha שהיא גרסה משופרת של צפני זרם החולקת אותם עקרונות תכנון עם Salsa20 אך בשינויים קלים שנועדו בעיקר להגברת רמת הפיזור (diffusion) של הצופן. הפיזור הנוסף אינו בא על חשבון ביצועים, כמו ב-Salsa20 בכל סבב מתבצעים 16 פעולות חיבור, XOR והזזה מעגלית בהיסטים קבועים וכן נשמרת אותה רמת מקביליות ואף יותר. ההערכה היא שגרסאות ChaCha מספקות עמידות גבוהה יותר נגד קריפטואנליזה ומשפרות במעט את הביצועים אם כי רק על פלטפורמות מסוימות. בגלל אחידות כמות העבודה בכל סבב, למספר הסבבים השפעה ישירה על ביצועי הצופן. מסיבה זו הוצעו גרסאות מופחתות סבבים לשיפור ביצועים על חשבון ביטחון. ChaCha8 מבוסס על Salsa20 עם שמונה סבבים, ChaCha12 על Salsa20 עם 12 סבבים בהתאמה. ההבדלים בין צופן Salsa וצופן ChaCha הם כדלהלן:

שימושים

ב-2014 אימצה גוגל את ChaCha יחד עם קוד אימות מסרים Poly1305 כתחליף ל-RC4 ב-OpenSSL. כמו כן המימוש של גוגל עבור TLS משמש להגנה על תעבורת הרשת (HTTPS) בין דפדפן כרום לאנדרואיד לבין אתרי גוגל. באופן דומה האלגוריתם שולב בפרוטוקול OpenSSH. הצופן ChaCha נכלל גם במערכות ההפעלה OpenBSD ו-NetBSD. וכן הוצע לפרוטוקול IPSec בטיוטה RFC 7539 וטיוטה RFC 7634. פונקציית הגיבוב BLAKE מבוססת על ליבת צופן ChaCha בשינויים מינוריים.

קוד לדוגמה

להלן קוד C++‎ שלם של צופן ChaCha20 המלא (20 סבבים). למען הבהירות הקוד אינו ממוטב והוא תואם את ההמלצה המופיעה באתר המפתח. ההנחה שהמהדר תומך בסדר בתים קטן. הפונקציה ‎_lrotl‎  היא  פונקציית הזזה מעגלית לשמאל הכלולה בספרייה הסטנדרטית של VS. אפשר לשנות את מספר הסבבים בפונקציה ChaCha_encrypt בקריאה לפונקציה Salsa20_Rounds בהתאם לצורך, למשל לגרסת שמונה סבבים יש לציין 8 בפרמטר האחרון, ערכים מומלצים הם 8,12 או 20.
typedef unsigned char byte;typedef unsigned int uint;#define BYTES_TO_INT(p) (((uint*)(p))[0])#define INT_TO_BYTES(p, v) (((uint*)(p))[0] = (v))#define ROTATE(v,c) (_lrotl(v, c))#define XOR(v,w) ((v) ^ (w))#define PLUS(v,w) ( (uint)(((v) + (w)) & 0xFFFFFFFF))#define PLUSONE(v) (PLUS((v),1))typedef struct{
   uint input[16];} ChaCha_Context;#define QUARTERROUND(a,b,c,d) \  x[a] = PLUS(x[a],x[b]); x[d] = ROTATE(XOR(x[d],x[a]),16); \  x[c] = PLUS(x[c],x[d]); x[b] = ROTATE(XOR(x[b],x[c]),12); \  x[a] = PLUS(x[a],x[b]); x[d] = ROTATE(XOR(x[d],x[a]), 8); \  x[c] = PLUS(x[c],x[d]); x[b] = ROTATE(XOR(x[b],x[c]), 7);static const char sigma[] = "expand 32-byte k";static const char tau[] = "expand 16-byte k";static void Salsa20_Rounds(byte output[64], const uint input[16], uint nrounds){
uint x[16];

for (uint i = 0; i < 16; ++i) 
x[i] = input[i];

for (uint i = nrounds; i > 0; i -= 2) {
QUARTERROUND( 0, 4,  8, 12)
QUARTERROUND( 1, 5,  9, 13)
QUARTERROUND( 2, 6, 10, 14)
QUARTERROUND( 3, 7, 11, 15)
QUARTERROUND( 0, 5, 10, 15)
QUARTERROUND( 1, 6, 11, 12)
QUARTERROUND( 2, 7,  8, 13)
QUARTERROUND( 3, 4,  9, 14)
}
for (uint i = 0; i < 16; ++i) 
x[i] = PLUS(x[i], input[i]);

for (uint i = 0; i < 16; ++i) 
INT_TO_BYTES(output + 4 * i, x[i]);}void ChaCha_keysetup(ChaCha_Context *ctx, const byte *k, uint kbits, uint ivbits){
const char *constants;

ctx->input[4] = BYTES_TO_INT(k + 0);
ctx->input[5] = BYTES_TO_INT(k + 4);
ctx->input[6] = BYTES_TO_INT(k + 8);
ctx->input[7] = BYTES_TO_INT(k + 12);

if (kbits == 256) { // recommended
k += 16;
constants = sigma;
}
else { // kbits == 128
constants = tau;
}
ctx->input[8] = BYTES_TO_INT(k + 0);
ctx->input[9] = BYTES_TO_INT(k + 4);
ctx->input[10] = BYTES_TO_INT(k + 8);
ctx->input[11] = BYTES_TO_INT(k + 12);
ctx->input[0] = BYTES_TO_INT(constants + 0);
ctx->input[1] = BYTES_TO_INT(constants + 4);
ctx->input[2] = BYTES_TO_INT(constants + 8);
ctx->input[3] = BYTES_TO_INT(constants + 12);}void ChaCha_ivsetup(ChaCha_Context *ctx, const byte *iv){
ctx->input[12] = 0;
ctx->input[13] = 0;
ctx->input[14] = BYTES_TO_INT(iv + 0);
ctx->input[15] = BYTES_TO_INT(iv + 4);}void ChaCha_encrypt(ChaCha_Context *ctx, const byte *m, byte *c, uint bytes){
byte output[64];

if (!bytes) return;
for (;;) {
Salsa20_Rounds(output, ctx->input, 20);
ctx->input[12] = PLUSONE(ctx->input[12]);
if (!ctx->input[12]) {
ctx->input[13] = PLUSONE(ctx->input[13]);
// stopping at 2^70 bytes per nonce is user's responsibility
}
if (bytes <= 64) {
for (uint i = 0; i < bytes; ++i) c[i] = m[i] ^ output[i];
return;
}
for (uint i = 0; i < 64; ++i) c[i] = m[i] ^ output[i];
bytes -= 64;
c += 64;
m += 64;
}}