سالسا۲۰

سالسا۲۰ و رمز دیگر نزدیک به آن، ChaCha، رمزهای جریانی هستند که توسط دنیل ج. برنشتاین ساخته شده‌اند. Salsa20، رمز اصلی، در سال ۲۰۰۵ طراحی شد و مدتی بعد توسط برنشتاین به eSTREAM ارائه داده شد. Chacha نسخه اصلاح شدهی Salsa20 است که در سال ۲۰۰۸ منتشر شده‌است. این رمز از یک تابع رندکننده جدید استفاده می‌کند که پراکنش را افزایش می‌دهد و کارایی (performance) را در برخی معماری‌ها بالا می‌برد.

هر دو رمز براساس یک تابع شبه تصادفی ساخته شده‌اند که مبتنی بر عملیات جمع-چرخش-xor
(ARX)می‌باشد؛ جمع ۳۲ بیتی، عملیات چرخش و جمع بیت به بیت (XOR). تابع اصلی، یک کلید ۲۵۶ بیتی، یک نانس ۶۴ بیتی و یک شمارنده ۶۴ بیتی را به یک بلوک ۵۱۲ بیتی از کلید جریانی (key stream) مپ می‌کند. (نسخهی Salsa با کلید ۱۲۸ بیتی نیز وجود دارد). این امر به Salsa20 و Chacha این مزیت غیرمعمول را می‌دهد که کاربر می‌تواند به هر نقطهای در جریان کلید در زمانی ثابت (O(1))دست یابد. Salsa20 در پردازنده‌های مدرن x86، سرعتی در حدود ۴–۱۴ سیکل بر بایت از نظر نرمافزاری و عملکردی معقول از نظر سخت‌افزاری ارائه می‌دهد. این اختراع ثبت نشده‌است و برنشتاین چندین نسخه از نوع مالکیت عمومی بهینه شده برای معماریهای متداول نوشته‌است.

ساختار 
از نظر ساختار داخلی، این رمز از جمع بیت به بیت یا همان ⊕ (یای انحصاری)، جمع ۳۲ بیتی به پیمانه ⊞و عملیات چرخش با فاصله ثابت(>>>) بر روی حالت داخلی شانزده کلمه ۳۲ بیتی استفاده می‌کند. تنها استفاده از عملیات add-rotate-xor از امکان حمله زمانی در پیاده‌سازی‌های نرم‌افزاری جلوگیری می‌کند. حالت داخلی از شانزده کلمه ۳۲ بیتی ساخته شده که به عنوان یک ماتریس ۴ × ۴ چیده می‌شود.

حالت اولیه از  ۸ کلمه از کلید،   ۲ کلمه از موقعیت جریان،   ۲ کلمه از نانس (در حقیقت بیتهای موقعیت جریان اضافی)،   و ۴ کلمه ثابت تشکیل شده‌است:

کلمه‌های ثابت در اسکی تشکیل عبارت ("expand 32-byte k") را می‌دهد. (برای مثال این چهار کلمه “expa”, “nd 3”,”2-by” , “te k” هستند). این نمونهای از یک عدد "بدون نیرنگ" است. عملیات اصلی در Salsa20، ربع دور، (QR(a, b, c, d است که یک ورودی چهار کلمه ای می‌گیرد و خروجی ای چهار کلمه ای تولید می‌کند.b ^= (a + d) <<< 7;
c ^= (b + a) <<< 9;
d ^= (c + b) <<< 13;
a ^= (d + c) <<< 18;دورهای فرد (QR(a, b, c, d  را روی هریک از ۴ ستون ماتریس ۴ × ۴ و دورهای زوج (QR(a,b, c, d  را روی هریک از ۴ سطر ماتریس ۴ × ۴ پیاده می‌کنند. دو دور متوالی (دور ستون و دور سطر) را باهم دور دوتایی (double-round) می‌نامند. // دور فرد
QR( 0,  4,  8, 12) // ستون 1
QR( 5,  9, 13,  1) // ستون 2
QR(10, 14,  2,  6) // ستون 3
QR(15,  3,  7, 11) // ستون 4
// دور زوج
QR( 0,  1,  2,  3) // سطر 1
QR( 5,  6,  7,  4) // سطر 2
QR(10, 11,  8,  9) // سطر 3
QR(15, 12, 13, 14) // سطر 4 یک پیاده‌سازی از این رمز در زبان C/C++ در کد ذیل موجود است #include <stdint.h>
#define ROTL(a,b) (((a) << (b)) | ((a) >> (32 - (b))))
#define QR(a, b, c, d)(  \
b ^= ROTL(a + d, 7), \
c ^= ROTL(b + a, 9), \
d ^= ROTL(c + b,13), \
a ^= ROTL(d + c,18))
#define ROUNDS 20

void salsa20_block(uint32_t out[16], uint32_t const in[16])
{
int i;
uint32_t x[16];

for (i = 0; i < 16; ++i)
x[i] = in[i];
// 10 loops × 2 rounds/loop = 20 rounds
for (i = 0; i < ROUNDS; i += 2) {
// Odd round
QR(x[0], x[4], x[8], x[12]); // column 1
QR(x[5], x[9], x[13], x[1]); // column 2
QR(x[10], x[14], x[2], x[6]); // column 3
QR(x[15], x[3], x[7], x[11]); // column 4
// Even round
QR(x[0], x[1], x[2], x[3]); // row 1
QR(x[5], x[6], x[7], x[4]); // row 2
QR(x[10], x[11], x[8], x[9]); // row 3
QR(x[15], x[12], x[13], x[14]); // row 4
}
for (i = 0; i < 16; ++i)
out[i] = x[i] + in[i];
}در خط آخر آرایهٔ میکس شده کلمه به کلمه با آرایهٔ اصلی جمع می-شود تا بلوک جریان کلید ۶۴ بایتی خود را بدست آورد. این کار (جمع کردن) مهم است زیرا دورهای میکس کردن (mixing rounds) به تنهایی معکوس پذیر و قابل بازگشت هستند. به عبارت دیگر، اعمال عملیات معکوس ماتریس ۴ × ۴ اصلی را تولید خواهد کرد، که شامل کلید می‌شود. جمع کردن آرایهٔ میکس شده با اصلی بازیابی ورودی را غیرممکن می‌کند (این تکنیک به‌طور گسترده در توابع هش (hash functions)از MD4 تا SHA-2 استفاده می‌شود)

Salsa20، بیست دور از میکس کردن را بر روی ورودی خود اجرا می‌کند. با این حال، انواع دیگر آن با دورهای کاسته شده به نام‌های Salsa20/8 و Salsa20/12 که به ترتیب از ۸ و ۱۲ دور استفاده می‌کنند هم معرفی شده‌اند. این گونه‌ها برای تکمیل Salsa20 اصلی معرفی شدند و نه برای جایگیزینی آن و برای آن که عملکرد حتی بهتری در معیارهای eSTREAM نسبت به Salsa20 داشته باشند، اگر چه حاشیه امنیتی متناظر پایین‌تر.

XSalsa20 با نانس ۱۹۲ بیتی 
برنشتاین در سال ۲۰۰۸ نوعی از Salsa20 با نانس ۱۹۲ بیتی با نام XSalsa20 را ارائه داد. اگر Salsa20 امن باشد، XSalsa20 بسیار قابل اطمینان است، اما برای برنامه‌هایی که در آن نانس‌های طولانی‌تر مطلوب باشد، مناسب تر است. XSalsa20 کلید و ۱۲۸ بیت اول نانس را در یک بلوک Salsa20 تغذیه می‌کند (بدون جمع نهایی، که ممکن است حذف شود یا پس از یک بلوک استاندارد Salsa20 کم شود) و از ۲۵۶ بیت خروجی به عنوان کلید برای Salsa20 استاندارد با استفاده از ۶۴ بیت آخر نانس و موقعیت جریان استفاده می‌کند. به‌طور خاص، ۲۵۶ بیت خروجی استفاده شده بیت‌های متناظر با قسمت‌های غیر مخفی ورودی است: اندیس‌های ۰، ۵، ۱۰، ۱۵، ۶، ۷، ۸ و ۹.

گزینش eSTREAM از Salsa20 
Salsa20 توسط پروژه eSTREAM به عنوان یک طرح فاز ۳ برای پروفایل ۱ (نرم‌افزار) انتخاب شده‌است و بالاترین امتیاز رای‌گیری وزندار در بین تمامی الگوریتم‌های پروفایل ۱ را در انتهای فاز ۲ دریافت کرده‌است. Salsa20 قبلاً به عنوان طراحی متمرکز فاز ۲ برای پروفایل ۱ (نرم‌افزار) و به عنوان طراحی فاز ۲ برای پروفایل ۲ (سخت‌افزار) توسط پروژه eSTREAM انتخاب شده بود اما به فاز ۳ برای پروفایل ۲ پیشرفت نکرد زیرا eSTREAM احساس کرد که احتمالاً نامزد مناسبی برای محیط‌های سخت‌افزاری با محدودیت منابع بسیار بالا نیست.

تحلیل رمز Salsa20 
از سال ۲۰۱۵، هیچ حملهٔ منتشر شده‌ای بر روی Salsa20/12 یا Salsa20/20 کامل وجود ندارد؛ بهترین حملهٔ شناخته شده ۸ تا از ۱۲ یا ۲۰ تا دور را می‌شکند.

در سال ۲۰۰۵، پاول کرولی(Paul Crowley) از حمله به Salsa20/5 با پیچیدگی زمانی تخمینی 2165 خبر داد، و برنده جایزه ۱۰۰۰ دلاری برنشتاین به عنوان "جالب‌ترین رمزنگاری Salsa20"شد این حمله و تمام حملات بعدی بر اساس رمزنگاری دیفرانسیلی کوتاه شده، است.. در سال ۲۰۰۶، فیشر(Fischer,)، مایر(Meier)، بربین(Berbain)، بیاز(Biasse) و رابشاو(Robshaw) حمله ای به Salsa20/6 با پیچیدگی زمانی تخمینی2177 و حمله ای از نوع کلید مرتبط برروی Salsa20/7 با پیچیدگی زمانی تقریبی2217 را گزارش دادند.

در سال ۲۰۰۷، Tsunoo و همکاران. یک رمزنگاری از Salsa20 را اعلام کردند که ۸ تا از ۲۰ دور را می‌شکند تا کلید مخفی ۲۵۶ بیتی را در 2255 عملیات، با استفاده از 211.37 جفت ihd جریان کلید بازیابی کند. با این حال، به نظر نمی‌رسد که این حمله بتواند با حملهٔ جستجوی فراگیر رقابتی کند.

در سال ۲۰۰۸، Aumasson، فیشر(Fischer,)، خزایی (Khazaei)، مایر(Meier) و Rechberger از حمله کریپتانالیستی علیه Salsa20/7 با پیچیدگی زمانی2153 و همچنین از اولین حمله علیه Salsa20/8 با پیچیدگی زمانی تقریبی 2251 گزارش دادند. این حمله مفهوم جدید بیت‌های کلید خنثی احتمالی برای تشخیص احتمالی دیفرانسیلی کوتاه شده را بکار می‌بندد. این حمله می‌تواند برای به گونه ای تطبیق داده شود تا Salsa20/7 را با کلید ۱۲۸ بیتی بشکند.

در سال ۲۰۱۲، حملهٔ انجام شده توسط Aumasson و همکاران، برروی Salsa20/7 (کلید ۱۲۸ بیتی) تا پیچیدگی زمانی 2109 و علیه Salsa20/8 (کلید ۲۵۶ بیتی) تا پیچیدگی زمانی 2250، به دست شی (Shi) و همکاران بهبود یافت.

در سال ۲۰۱۳، موها(Mouha) و پرنل (Preneel) اثباتی را منتشر کردند که نشان می‌داد ۱۵ دور از Salsa20، به اندازهٔ ۱۲۸ بیت در برابر رمزنگاری دیفرانسیلی ایمن است. (به‌طور خاص، هیچ ویژگی دیفرانسیلی با احتمال بالاتر ا−130۲ ندارد، بنابراین رمزنگاری دیفرانسیلی دشوارتر از فرسودگی کلیدی ۱۲۸ بیتی است)

گونهٔ ChaCha 
در سال 2008، برنشتاین خانواده رمزهای نزدیک "ChaCha" را منتشر کرد، که هدف آنها افزایش نسبت پراکنش بر هر دور در عین رسیدن به کارایی یکسان یا کمی بهتر است. مقالهٔ Aumasson و همکاران، همچنین به ChaCha حمله می‌کند و به یک دور کمتر می‌رسد: برای ChaCha6 با ۲۵۶ بیت با پیچیدگی2139 و ChaCha7 با پیچیدگی 2248. ChaCha6 با ۱۲۸ بیت در محدوده ی2107 اما ادعا می‌کند که این حمله نمی‌تواند ChaCha7 با ۱۲۸ بیت را بشکند.

مانند Salsa20، جالت اولیه ChaCha شامل یک ثابت ۱۲۸ بیتی، یک کلید ۲۵۶ بیتی، یک شمارنده ۶۴ بیتی و یک نانس ۶۴ بیتی می‌شود که به صورت یک ماتریس ۴ × ۴ از کلمه‌های ۳۲ بیتی تنظیم شده‌است اما ChaCha بعضی از کلمات را در حالت اولیه دوباره مرتب می‌کند:

ثابت همانند Salsa20است ("expand 32-byte k"). ChaCha ربع دور در Salsa20 یعنی QR(a, b, c, d) را با تابع زیر جایگزین می‌کند: a += b; d ^= a; d <<<= 16;
c += d; b ^= c; b <<<= 12;
a += b; d ^= a; d <<<= 8;
c += d; b ^= c; b <<<= 7;توجه کنید که این نسخه هر کلمه را دو بار به روز می‌کند، در حالی که ربع دور Salsa20 هر کلمه را فقط یک بار به روز می‌کند. علاوه بر این، ربع دور ChaCha تغییرات را با سرعت بیشتری پراکنده می‌کند. به‌طور متوسط، پس از تغییر ۱ بیت از ورودی، ربع دور Salsa20، تعداد ۸ بیت خروجی را تغییر خواهد داد در حالی که ChaCha تعداد ۱۲٫۵ بیت خروجی را تغییر می‌دهد.

تعداد جمع‌ها، xorها و چرخش‌های بیتی در ربع دور ChaCha با ربع دور Salsa20 یکسان است ولی این واقعیت که دوتا از چرخش‌ها از مضارب ۸ هستند، باعث می‌شود که بهینه‌سازی کوچکی در برخی از معماری‌ها از جمله x86 انجام شود. علاوه بر این، قالب بندی ورودی به گونه ای دوباره تنظیم شده‌است تا از یک بهینه‌سازی اجرای کارآمد از SSE که برای Salsa20 کشف شده، پشتیبانی کند. به جای اینکه دورها بین ستون‌ها و ردیف‌ها متناوب باشد، بین ستون‌ها و در امتداد قطرهای مورب اجرا می‌شوند. ChaCha همانند Salsa20 شانزده کلمه ۳۲ بیتی را در یک ماتریس ۴ × ۴ مرتب می‌کند. اگر به عناصر ماتریس اندیسهای از ۰ تا ۱۵ نسبت دهیم:

در ادامه ربع دور در ChaCha بصورت زیر خواهد بود:// دور فرد
QR(0, 4,  8, 12) // ستون اول
QR(1, 5,  9, 13) // ستون دوم
QR(2, 6, 10, 14) // ستون سوم
QR(3, 7, 11, 15) // ستون چهارم
// دور زوج
QR(0, 5, 10, 15) // قطر 1 (قطر اصلی)
QR(1, 6, 11, 12) // قطر 2
QR(2, 7,  8, 13) // قطر 3
QR(3, 4,  9, 14) // قطر 4ChaCha20 از ۱۰ تکرار دور دوتایی استفاده می‌کند. یک پیاده‌سازی از این رمز در زبان C/C++ در کد قابل مشاهده است. #define ROTL(a,b) (((a) << (b)) | ((a) >> (32 - (b))))
#define QR(a, b, c, d) (   \
a += b,  d ^= a,  d = ROTL(d,16), \
c += d,  b ^= c,  b = ROTL(b,12), \
a += b,  d ^= a,  d = ROTL(d, 8), \
c += d,  b ^= c,  b = ROTL(b, 7))
#define ROUNDS 20

void chacha_block(uint32_t out[16], uint32_t const in[16])
{
int i;
uint32_t x[16];

for (i = 0; i < 16; ++i)
x[i] = in[i];
// 10 loops × 2 rounds/loop = 20 rounds
for (i = 0; i < ROUNDS; i += 2) {
// Odd round
QR(x[0], x[4], x[8], x[12]); // column 0
QR(x[1], x[5], x[9], x[13]); // column 1
QR(x[2], x[6], x[10], x[14]); // column 2
QR(x[3], x[7], x[11], x[15]); // column 3
// Even round
QR(x[0], x[5], x[10], x[15]); // diagonal 1 (main diagonal)
QR(x[1], x[6], x[11], x[12]); // diagonal 2
QR(x[2], x[7], x[8], x[13]); // diagonal 3
QR(x[3], x[4], x[9], x[14]); // diagonal 4
}
for (i = 0; i < 16; ++i)
out[i] = x[i] + in[i];
}ChaCha اساس کار تابع هش بلیک است، یک فینالیست در رقابت تابع هش NIST و جانشین BLAKE2 که برای سرعت حتی بالاتر تنظیم شده‌است. این رمز همچنین با استفاده از شانزده کلمه ۶۴ بیتی (۱۰۲۴ بیت حالت)، گونه ای را با ثابت‌های چرخش تنظیم شدهی مطابق تعریف می‌کند.

XChaCha 
با وجود اینکه توسط برنشتاین اعلام نشده‌است، برهان امنیت XSalsa20 مستقیماً به رمز مشابه "XChaCha" گسترش می‌یابد. برای تشکیل یک بلوک ورودی ChaCha از کلید و ۱۲۸ بیت اول نانس (کلمه‌های ۱۲ تا ۱۵ ورودی) استفاده کنید (با حذف جمع نهایی). کلمه‌های ۰–۳ و ۱۲–۱۵ (کلمات مرتبط با کلمات غیرکلیدی ورودی) را تولید و استخراج کنید سپس کلید قابل استفاده برای ChaCha معمولی را تشکیل دهید (با استفاده از ۶۴ بیت آخر نانس و ۶۴ بیت بلوک شمارنده)

به کار گرفته شدن ChaCha20 
گوگل ChaCha20 را به همراه کد تصدیق پیام Poly1305 برنشتاین به عنوان جایگزینی برای RC4 در TLS، که برای امنیت اینترنت استفاده می‌شود ، انتخاب کرده‌است. پیاده‌سازی گوگل، امنیت ترافیک(https (TLS/SSL) را بین مرورگر کروم بر روی تلفن‌های اندروید و وب سایت‌های گوگل تضمین می‌کند.

اندکی پس از بکارگرفته شدن رمز توسط گوگل برای TLS، الگوریتم‌های ChaCha20 و Poly1305 هردو برای رمز جدیدpoly1305"@"openssh.com در OpenSSH مورد استفاده قرار گرفتند. متعاقباً، این امر باعث می‌شود تا OpenSSH از طریق یک گزینه زمان کامپایل، از هرگونه وابستگی به OpenSSL اجتناب کند.

ChaCha20 همین‌طور برای تولیدکنندهٔ عدد تصادفی arc4random در سیستمهای عامل FreeBSD ، OpenBSD و NetBSD, به جای RC4 شکسته شده و همچنین در دراگون‌فلای بی‌اس‌دی برای زیرروال CSPRNG هسته (kernel-رایانش) استفاده می‌شود. با شروع از نسخه ۴٫۸، هسته لینوکس از الگوریتم ChaCha20 برای تولید داده برای دستگاه nonblocking /dev/urandom استفاده می‌کند.

ChaCha20 مرجعی برای پیاده‌سازی  در  منتشر شده‌است. پیاده‌سازی IETF الگوریتم منتشر شده برنشتاین را با تغییر نانس ۶۴ بیتی و بلوک شمارنده ۶۴ بیتی به نانس ۹۶ بیتی و بلوک شمارنده ۳۲ بیتی اصلاح کرده‌است؛ هنگامی که الگوریتم اصلاح شد نام آن تغییر نکرد زیرا از نظر رمزنگاری بی‌اهمیت است (هر دو چیزی را تشکیل می‌دهند به عنوان نانس ۱۲۸ بیتی خواهد شناخت) اما تغییر رابط می‌تواند منبعی برای سردرگمی توسعه دهندگان باشد. به دلیل بلوک شمارنده کاسته شده، حداکثر طول پیامی که می‌تواند با امنیت توسط نوع IETF رمزگذاری شود 232 بلوک ۶۴ بایتی (۲۵۶ GiB) است. برای برنامه‌هایی که این کافی نیست، مانند رمزگذاری فایل یا دیسک،  استفاده از الگوریتم اصلی با نانس ۶۴ بیتی را پیشنهاد می‌کند.

استفاده از ChaCha20 در IKE و IPsec برای استانداردسازی در  پیشنهاد شده‌است. استانداردسازی پیشنهادی برای کاربرد آن در TLS با عنوان  منتشر شده‌است. اعتقاد بر این است که ChaCha20 عملکردی بهتر از AES در یک پردازنده low-end بدون AES-NI دارد.

در سال ۲۰۱۸، RFC 7539 توسط RFC 8439 منسوخ شد.

ChaCha20 الگوریتمی است که بطور انحصاری توسط سیستم وایرگارد VPN استفاده می‌شود، مانند پروتکل نسخه 1.

در سال ۲۰۲۰، مایکروسافت برای ChaCha20 در ویندوز ۱۰ پشتیبانی اضافه کرده‌است، نسخه بهار 2021 (Manganese) از تاریخ ساخت ۱۹۶۱۹.

جستارهای وابسته 
 Speck - یک رمز جمع-چرخش-xor که توسط NSA تولید شده‌است.

یادداشت

منابع

پیوند به بیرون 
 Snuffle 2005: the Salsa20 encryption function
 Salsa20 specification (PDF)
 Salsa20/8 and Salsa20/12 (PDF)
 The eSTREAM Project: Salsa20
 The ChaCha family of stream ciphers
 Salsa20 Usage & Deployment
رمز دنباله‌ای
استانداردهای اینترنت
نگهداری یادکرد:استفاده از پارامتر نویسندگان
مقاله‌ها با نحو منسوخ‌شده تصویر