اسکریپت (رمزنگاری)

یک تابع مشتق کلید (KDF) مبتنی بر رمز عبور به‌طور کلی برای محاسبات فشرده طراحی شده‌است، به طوری که محاسبه برای مدت زمان نسبتاً طولانی به طول می‌انجامد (تقریباً چند صد میلی ثانیه). کاربران مجاز فقط باید یک بار در هر عملیات، تابع را اجرا کنند (به عنوان مثال، احراز هویت)، و بنابراین زمان مورد نیاز ناچیز است. با این حال، یک حمله جستجوی فراگیر (Brute-force attack) احتمالاً نیاز به میلیاردها بار انجام عملیات دارد، در این صورت زمان مهم و قابل توجه می‌شود.

KDFهای مبتنی بر رمز عبور قدیمی (مانند PBKDF2 متعلق به RSA Laboratories) منابع نسبتاً کمی نیاز دارند، به این معنی که آنها سخت‌افزار دقیق یا حافظه بسیار زیادی برای انجام کار نیاز ندارند؛ بنابراین، آنها به راحتی می‌توانند در سخت‌افزار (به عنوان مثال در یک ASIC یا حتی یک FPGA) اجرا شوند. این به مهاجم اجازه می‌دهد تا با منابع کافی و در مقیاس بزرگ، یک حمله موازی بزرگ را با پیاده‌سازی صدها یا حتی هزاران الگوریتم در سخت‌افزار و جستجو در زیر مجموعه‌های مختلف از فضای کلیدی راه اندازی کند. این، زمان لازم برای تکمیل حمله جستجوی فراگیر را بر اساس تعدادی از پیاده‌سازی‌های موجود تقسیم می‌کند و احتمالاً آن را به یک فریم زمان معقول تبدیل می‌کند.

تابع اسکریپت طراحی شده‌است تا از چنین تلاش‌هایی با افزایش درخواست منابع از الگوریتم جلوگیری کند. به‌طور خاص، این الگوریتم طراحی شده‌است که از مقدار زیادی حافظه در مقایسه با KDFهای مبتنی بر رمز عبور دیگر استفاده کند، که اندازه و هزینه اجرای سخت‌افزاری را بسیار گران‌تر می‌کند و بنابراین مقدار موازی را که مهاجم می‌تواند برای یک داده استفاده کند محدود می‌کند.

الزامات حافظه بزرگ scrypt از یک بردار بزرگ رشته‌های باینری شبه تصادفی حاصل می‌شود که به عنوان بخشی از الگوریتم تولید می‌شوند. هنگامی که بردار تولید می‌شود، عناصر آن در یک دستور شبه تصادفی دیده می‌شوند و برای تولید کلید مشتق شده ترکیب می‌شوند. یک پیاده‌سازی ساده نیاز به نگه داشتن کل بردار در حافظه را دارد تا بتوان آن را در صورت نیاز مشاهده کرد.

از آنجا که عناصر بردار به صورت الگوریتمی تولید می‌شوند، هر عنصر می‌تواند حین اجرا در صورت نیاز تولید شود، فقط یک عنصر در یک زمان در حافظه ذخیره می‌شود و در نتیجه نیازهای حافظه به‌طور قابل توجهی قطع می‌شود. با این حال به نظر می‌آید تولید هر عنصر به صورت محاسباتی گران باشد، و انتظار می‌رود که عناصر بارها در طول اجرای تابع قابل دسترسی شوند. به این ترتیب برای خلاص شدن از نیاز زیاد به حافظه، سرعت به میزان قابل توجهی کاهش می‌یابد.

این نوع تقارن زمان حافظه اغلب در الگوریتم‌های کامپیوتری وجود دارد: سرعت می‌تواند در ازای استفاده از حافظه بیشتر افزایش یابد، یا نیازهای حافظه در ازای اجرای عملیات‌های بیشتر و طولانی‌تر شدن انجام عملیات کاهش یابد. ایده پشت اسکریپت این است که عمداً این هزینه را در هر دو جهت کاهش می‌دهد؛ بنابراین مهاجم می‌تواند از یک پیاده‌سازی استفاده کند که به منابع زیادی نیاز ندارد (و بنابراین می‌تواند با هزینه محدود، به‌طور گسترده‌ای موازی باشد) اما بسیار آهسته اجرا شود یا از یک پیاده‌سازی سریع تر که به حافظه بسیار زیادی نیاز دارد استفاده کند و بنابراین موازی سازی با هزینه بیشتری انجام می‌شود.

الگوریتم شامل پارامترهای زیر است:

• Passphrase - رشته‌ای از کاراکترها که هش می‌شوند.
• Salt - یک رشته از کاراکترهایی که هش را تغییر می‌دهند تا در مقابل حملات جدول رنگین‌کمانی (Rainbow table) محافظت کنند.
• N - پارامتر هزینه پردازنده / حافظه.
• p - پارامتر موازی سازی؛ یک عدد صحیح مثبت رضایت بخش p ≤ (۲۳۲–۱) * hLen / MFLen.
• dkLen - طول خروجی پیشنهادی در کلید مشتق شده؛ یک عدد صحیح مثبت رضایت بخش dkLen ≤ (۲۳۲–۱) * hLen.
• r - پارامتر اندازه بلوک، که اندازه حافظه متوالی و عملکرد را بهبود می‌بخشد. برای این پارامتر معمولاً عدد ۸ استفاده می‌شود.
• hLen - طول در تابع هش (۳۲ برای SHA256).
• MFlen - طول در خروجی تابع اختلاط (SMix در زیر). به عنوان R * ۱۲۸ در RFC7914 تعریف شده‌است.

 Function scrypt
 Inputs:
 Passphrase: Bytes string of characters to be hashed
 Salt: Bytes random salt
 CostFactor (N): Integer CPU/memory cost parameter
 BlockSizeFactor (r): Integer blocksize parameter (8 is commonly used)
 ParallelizationFactor (p): Integer Parallelization parameter. (1..2-1 * hLen/MFlen)
 DesiredKeyLen: Integer Desired key length in bytes
 Output:
 DerivedKey: Bytes array of bytes, DesiredKeyLen long

 Step 1. Generate expensive salt
 blockSize ← 128*BlockSizeFactor //Length (in bytes) of the SMix mixing function output (e.g. 128*8 = 1024 bytes)

 Use PBKDF2 to generate initial 128*BlockSizeFactor*p bytes of data (e.g. 128*8*3 = 3072 bytes)
 Treat the result as an array of p elements, each entry being blocksize bytes (e.g. 3 elements, each 1024 bytes)
   [B0...Bp−1] ← PBKDF2HMAC-SHA256(Passphrase, Salt, 1, blockSize*ParallelizationFactor)

 Mix each block in B 2 times using ROMix function (each block can be mixed in parallel)
 for i ← 0 to p-1 do
 Bi ← ROMix(Bi, 2)

 All the elements of B is our new "expensive" salt
 expensiveSalt ← B0∥B1∥B2∥ … ∥Bp-1 //where ∥ is concatenation

 Step 2. Use PBKDF2 to generate the desired number of bytes, but using the expensive salt we just generated
 return PBKDF2HMAC-SHA256(Passphrase, expensiveSalt, 1, DesiredKeyLen);

علامت (PBKDF2 (P, S، c, dkLen در RFC 2898 تعریف شده‌است، c تعداد تکرار است.

این نماد توسط RFC 7914 برای تعیین استفاده از PBKDF2 با c = ۱ استفاده می‌شود.

 Function ROMix(Block, Iterations)

 Create Iterations copies of X
 X ← Block
 for i ← 0 to Iterations−1 do
 Vi ← X
 X ← BlockMix(X)

 for i ← 0 to Iterations−1 do
 j ← Integerify(X) mod Iterations
 X ← BlockMix(X xor Vj)

 return X

RFC 7914 که (Integerify (X را در نتیجه تفسیر ۶۴ بایت آخر X به عنوان یک عدد صحیح A1 تعریف می‌کند.

 Function BlockMix(B):
 The block B is r 128-byte chunks (which is equivalent of 2r 64-byte chunks)
 r ← Length(B) / 128;

 Treat B as an array of 2r 64-byte chuncks
    [B0...B2r-1] ← B

 X ← B2r−1
 for i ← 0 to 2r−1 do
 X ← Salsa20/8(X xor Bi) //Salsa20/8 hashes from 64-bytes to 64-bytes
 Yi ← X

 return ← Y0∥Y2∥... ∥Y2r−2 ∥ Y1∥Y3∥... ∥Y2r−1

Scrypt در بسیاری از رمزگشایی‌ها به عنوان یک الگوریتم اثبات کار استفاده می‌شود. این اولین بار برای Tenebrix پیاده‌سازی شد (منتشر شده در سپتامبر ۲۰۱۱) و به عنوان پایه برای لایت‌کوین (Litecoin) و دوژکوین (Dogecoin) به خدمت گرفته شد، که همچنین از الگوریتم اسکریپتش اقتباس شد. استخراج رمزارزهایی که از اسکریپت استفاده می‌کنند اغلب بر روی واحد پردازش گرافیکی (GPU) انجام می‌شود، زیرا واحدهای پردازش گرافیکی نسبت به پردازنده (CPU) توانایی پردازش قابل توجهی دارند (برای برخی از الگوریتم‌ها). افزایش قیمت این ارزها در ماه‌های نوامبر و دسامبر ۲۰۱۳ منجر به کمبود GPUهای قدرتمند شد. از ماه مه سال ۲۰۱۴، سخت‌افزار ماینینگ تخصصی مدارهای مجتمع با کاربرد خاص (ASIC) برای رمزارزهای مبتنی بر اسکریپت موجود شد. از سال ۲۰۱۶، InnoSilicon ادعا کرد که فناوری ۱۴ نانومتری با کارایی ۱٫۵ میکروژول بر هش (µJ/hash) دارد.

• تابع مشتق کلید
• PBKDF2
• Bcrypt

صفحه اسکریپت در سایت Tarsnap