سكريبت

أداة تشفير scrypt
المطور(ون)	كولن بيرسيفال
إصدار مستقر	1.3.2 / 2 أكتوبر 2023 ؛ منذ 13 شهرًا
مستودع	github.com/Tarsnap/scrypt
موقع إلكتروني	www.tarsnap.com/scrypt.html

سكريبت
عام
المصممين	كولن بيرسيفال
نُشرت لأول مرة	2009
تفاصيل الشفرة
أحجام الملخص	عامل
أحجام الكتل	عامل
جولات	عامل

في التشفير ، scrypt (تُلفظ "ess crypt" ^{[1] ) هي}دالة اشتقاق مفتاح تعتمد على كلمة مرور أنشأها كولين بيرسيفال في مارس 2009، في الأصل لخدمة النسخ الاحتياطي عبر الإنترنت Tarsnap . ^[2]^[3] تم تصميم الخوارزمية خصيصًا لجعل تنفيذ هجمات الأجهزة المخصصة واسعة النطاق أمرًا مكلفًا من خلال طلب كميات كبيرة من الذاكرة. في عام 2016، نشرت IETF خوارزمية scrypt باسم RFC 7914. ^[4] يتم استخدام نسخة مبسطة من scrypt كمخطط لإثبات العمل من قبل عدد من العملات المشفرة ، تم تنفيذها أولاً بواسطة مبرمج مجهول يُدعى ArtForz في Tenebrix وتبعها Fairbrix و Litecoin بعد فترة وجيزة. ^[5]

مقدمة

إن وظيفة اشتقاق المفتاح المستندة إلى كلمة المرور مصممة بشكل عام لتكون مكثفة حسابيًا، بحيث تستغرق وقتًا طويلاً نسبيًا للحوسبة (على سبيل المثال في حدود عدة مئات من المللي ثانية). يحتاج المستخدمون الشرعيون فقط إلى أداء الوظيفة مرة واحدة لكل عملية (على سبيل المثال، المصادقة)، وبالتالي فإن الوقت المطلوب لا يُذكَر. ومع ذلك، من المرجح أن يحتاج هجوم القوة الغاشمة إلى أداء العملية مليارات المرات، وعند هذه النقطة تصبح متطلبات الوقت كبيرة، وفي الحالة المثالية، محظورة.

تتطلب أدوات تشفير المفاتيح السابقة المستندة إلى كلمة المرور (مثل PBKDF2 الشهيرة من RSA Laboratories ) موارد منخفضة نسبيًا، مما يعني أنها لا تتطلب أجهزة معقدة أو ذاكرة كبيرة جدًا لأدائها. وبالتالي، يتم تنفيذها بسهولة وبتكلفة زهيدة في الأجهزة (على سبيل المثال على ASIC أو حتى FPGA ). يسمح هذا للمهاجم الذي لديه موارد كافية بشن هجوم موازٍ واسع النطاق من خلال بناء مئات أو حتى آلاف من تطبيقات الخوارزمية في الأجهزة وجعل كل منها يبحث عن مجموعة فرعية مختلفة من مساحة المفتاح. يقسم هذا مقدار الوقت اللازم لإكمال هجوم القوة الغاشمة على عدد التطبيقات المتاحة، مما قد يؤدي إلى تقليصه إلى إطار زمني معقول.

تم تصميم وظيفة scrypt لمنع مثل هذه المحاولات من خلال زيادة متطلبات الموارد للخوارزمية. على وجه التحديد، تم تصميم الخوارزمية لاستخدام كمية كبيرة من الذاكرة مقارنة بـ KDFs الأخرى القائمة على كلمة المرور، ^[6] مما يجعل حجم وتكلفة التنفيذ المادي أكثر تكلفة بكثير، وبالتالي الحد من مقدار التوازي الذي يمكن للمهاجم استخدامه، لكمية معينة من الموارد المالية.

ملخص

إن متطلبات الذاكرة الكبيرة لـ scrypt تأتي من متجه كبير من سلاسل البتات شبه العشوائية التي يتم إنشاؤها كجزء من الخوارزمية. بمجرد إنشاء المتجه، يتم الوصول إلى عناصره بترتيب شبه عشوائي ودمجها لإنتاج المفتاح المشتق. سيحتاج التنفيذ البسيط إلى الاحتفاظ بالمتجه بالكامل في ذاكرة الوصول العشوائي حتى يمكن الوصول إليه حسب الحاجة.

نظرًا لأن عناصر المتجه يتم إنشاؤها خوارزميًا، يمكن إنشاء كل عنصر على الفور حسب الحاجة، وتخزين عنصر واحد فقط في الذاكرة في كل مرة، وبالتالي تقليص متطلبات الذاكرة بشكل كبير. ومع ذلك، فإن إنشاء كل عنصر من المفترض أن يكون مكلفًا من الناحية الحسابية، ومن المتوقع الوصول إلى العناصر عدة مرات طوال تنفيذ الوظيفة. وبالتالي، هناك مقايضة كبيرة في السرعة للتخلص من متطلبات الذاكرة الكبيرة.

غالبًا ما يوجد هذا النوع من التنازل بين الوقت والذاكرة في خوارزميات الكمبيوتر: يمكن زيادة السرعة على حساب استخدام المزيد من الذاكرة، أو تقليل متطلبات الذاكرة على حساب إجراء المزيد من العمليات واستغراق وقت أطول. الفكرة وراء scrypt هي جعل هذه التنازلات مكلفة عمدًا في أي اتجاه. وبالتالي يمكن للمهاجم استخدام تنفيذ لا يتطلب الكثير من الموارد (وبالتالي يمكن تشغيله بالتوازي بشكل كبير بتكلفة محدودة) ولكنه يعمل ببطء شديد، أو استخدام تنفيذ يعمل بسرعة أكبر ولكنه يتطلب ذاكرة كبيرة جدًا وبالتالي يكون تشغيله بالتوازي أكثر تكلفة.

خوارزمية

دالة scrypt
    المدخلات:  تتضمن هذه الخوارزمية المعلمات التالية: 
      عبارة المرور:     سلسلة بايتات من الأحرف المراد تجزئتها 
      Salt :     سلسلة بايتات من الأحرف العشوائية التي تعدل التجزئة للحماية من هجمات جدول Rainbow 
      CostFactor (N): عدد صحيح   معلمة تكلفة وحدة المعالجة المركزية/الذاكرة - يجب أن تكون قوة 2 (مثل 1024) 
      BlockSizeFactor (r):   معلمة حجم الكتلة الصحيحة، والتي تعمل على ضبط حجم القراءة المتسلسلة للذاكرة والأداء. (يتم استخدام 8 بشكل شائع) 
      ParallelizationFactor (p): عدد صحيح   معلمة التوازي . (1 .. 2 ³² -1 * hLen/MFlen) 
      DesiredKeyLen (dkLen): عدد صحيح   طول المفتاح المطلوب بالبايتات (طول الإخراج المقصود بالثمانيات للمفتاح المشتق؛ عدد صحيح موجب يفي بـ dkLen ≤ (2 ³² − 1) * hLen.) 
      hLen: عدد صحيح   طول دالة التجزئة بالثمانيات (32 لـ SHA256). 
      MFlen: عدد صحيح   طول إخراج دالة الخلط بالثمانيات ( SMix أدناه). محدد على أنه r * 128 في RFC7914. 
   الإخراج: 
      DerivedKey:     مجموعة بايتات من البايتات، DesiredKeyLen طويلة

   
   الخطوة 1. إنشاء كتلة   ملح باهظة الثمن ← 128*BlockSizeFactor // الطول (بالبايت) لإخراج دالة الخلط SMix (على سبيل المثال 128*8 = 1024 بايت)

   استخدم PBKDF2 لتوليد 128*BlockSizeFactor*p بايت أولي من البيانات (على سبيل المثال 128*8*3 = 3072 بايت) 
   تعامل مع النتيجة كمجموعة من عناصر p ، حيث يكون كل عنصر عبارة عن بايتات بحجم الكتلة (على سبيل المثال 3 عناصر، كل منها 1024 بايت) 
   [B ₀ ...B _p−1 ] ← PBKDF2 _HMAC-SHA256 ( Passphrase ، Salt ، 1، blockSize*ParallelizationFactor)

   امزج كل كتلة في B CostFactor مرات باستخدام دالة ROMix (يمكن خلط كل كتلة بالتوازي) 
   لـ i ← 0 إلى p-1 do 
      B _i ← ROMix(B _i , CostFactor)

   جميع عناصر B هي ملحنا "الغالي الثمن" الجديد 
   expensiveSalt ← B ₀ ∥B ₁ ∥B ₂ ∥ ... ∥B _p-1  // حيث ∥ هو الترابط
 
   الخطوة 2. استخدم PBKDF2 لتوليد العدد المطلوب من البايتات، ولكن باستخدام salt الباهظ الثمن الذي أنشأناه للتو، 
   قم بإرجاع PBKDF2_HMAC-SHA256 (Passphrase، expensiveSalt، 1، DesiredKeyLen)؛

حيث تم تعريف تدوين PBKDF2(P, S, c, dkLen) في RFC 2898، حيث c هو عدد التكرارات.

يتم استخدام هذا الترميز بواسطة RFC 7914 لتحديد استخدام PBKDF2 مع c = 1.

دالة ROMix(كتلة، تكرارات)

   إنشاء نسخ تكرارية من X
   X ← كتلة
   بالنسبة إلى i ← 0 إلى تكرارات −1 من 
      V _i ← X
      X ← BlockMix(X)

   بالنسبة إلى i ← 0 إلى التكرارات −1
      j ← Integerify(X) mod تكرارات
      X ← BlockMix(X xor V _j )

   العودة X

حيث يحدد RFC 7914 Integerify(X)نتيجة تفسير آخر 64 بايت من X كعدد صحيح صغير A ₁ .

نظرًا لأن التكرارات تساوي 2 إلى قوة N، فإن أول بايتات Ceiling(N / 8) فقط من بين آخر 64 بايت من X، والتي يتم تفسيرها على أنها عدد صحيح صغير A ₂ ، هي المطلوبة فعليًا لحساب . Integerify(X) mod Iterations = A₁ mod Iterations = A₂ mod Iterations

دالة BlockMix(B):

    الكتلة B عبارة عن r قطعة مكونة من 128 بايت (وهو ما يعادل 2r قطعة مكونة من 64 بايت)
    ر ← الطول(ب) / 128؛

    تعامل مع B كمجموعة من 2r قطعًا مكونة من 64 بايتًا 
    [B₀ ...B_2r-1 ] ← B

    X ← B _2r−1
    لـ i ← 0 إلى 2r−1 do 
        X ← Salsa20/8(X xor B _i )   // تجزئات Salsa20/8 من 64 بايت إلى 64 بايت 
        Y _i ← X

    العودة ← Y ₀ ∥Y ₂ ∥...∥Y _2r−2_∥ Y ₁ ∥Y 3 ∥...∥Y _2r−1

حيث أن Salsa20/8 هي النسخة المكونة من 8 جولات من Salsa20 .

استخدامات العملات المشفرة

تُستخدم Scrypt في العديد من العملات المشفرة كخوارزمية لإثبات العمل (بشكل أكثر دقة، كدالة تجزئة في خوارزمية إثبات العمل Hashcash ). تم تنفيذها لأول مرة في Tenebrix (تم إصدارها في سبتمبر 2011) وكانت بمثابة الأساس لـ Litecoin و Dogecoin ، والتي اعتمدت أيضًا خوارزمية scrypt الخاصة بها. ^[7]^[8] غالبًا ما يتم إجراء تعدين العملات المشفرة التي تستخدم scrypt على وحدات معالجة الرسومات ( GPUs ) نظرًا لأن وحدات معالجة الرسومات تميل إلى امتلاك قوة معالجة أكبر بكثير (لبعض الخوارزميات) مقارنة بوحدة المعالجة المركزية. ^[9] أدى هذا إلى نقص في وحدات معالجة الرسومات المتطورة بسبب ارتفاع سعر هذه العملات في شهري نوفمبر وديسمبر 2013. ^[10]

جدوى

تم كتابة أداة scrypt في مايو 2009 بواسطة Colin Percival كعرض توضيحي لوظيفة اشتقاق مفتاح scrypt. ^[2]^[3] وهي متوفرة في معظم توزيعات Linux و BSD .

انظر أيضا

Argon2 – الفائز بمسابقة Password Hashing لعام 2015
bcrypt – دالة التجزئة لكلمة المرور المستندة إلى blowfish
bcrypt – أداة تشفير ملفات متعددة الأنظمة تعتمد على blowfish تم تطويرها في عام 2002 ^[12]^[13]^[14]^[15]
crypt – دالة مكتبة Unix C
crypt – أداة مساعدة لنظام يونكس
ccrypt – أداة مساعدة
وظيفة اشتقاق المفتاح
تمديد المفتاح
mcrypt – أداة مساعدة
PBKDF2 – دالة اشتقاق مفتاح قائمة على كلمة المرور قياسية واسعة الاستخدام 2
PufferFish – وظيفة تجزئة كلمات المرور المخزنة مؤقتًا والتي تعتمد على تصميم bcrypt المحسن
المقايضة بين المكان والزمان

مراجع

^ "كولين بيرسيفال". تويتر . مؤرشف من الأصل في 17 فبراير 2019.
^ "دالة اشتقاق مفتاح سكريبت". Tarsnap . مؤرشف من الأصل في 28 مايو 2019 . تم الاسترجاع في 21 يناير 2014 .
^ "دليل الأوامر العامة لبرنامج SCRYPT(1)". صفحات دليل Debian . مؤرشف من الأصل في 2 مارس 2022. تم الاسترجاع في 2 مارس 2022 .
^ بيرسيفال، كولين؛ جوزيفسون، سيمون (أغسطس 2016). "وظيفة اشتقاق المفتاح المستندة إلى كلمة المرور في سكريبت". محرر RFC. مؤرشف من الأصل في 13 ديسمبر 2021. تم الاسترجاع في 13 ديسمبر 2021 .
^ أليك ليو (29 نوفمبر 2013). "ما وراء البيتكوين: دليل إلى العملات المشفرة الأكثر واعدة". مؤرشف من الأصل في 13 يونيو 2018. تم الاسترجاع في 8 يوليو 2017 .
^ بيرسيفال، كولين. "اشتقاق مفتاح أقوى عبر وظائف الذاكرة المتسلسلة الصعبة" (PDF) . مؤرشف (PDF) من الأصل في 14 أبريل 2019. تم الاسترجاع في 11 نوفمبر 2022 .
^ أندرياس م. أنطونوبولوس (3 ديسمبر 2014). إتقان البيتكوين: فتح العملات الرقمية المشفرة. أوريلي ميديا. ص 221، 223. رقم ISBN 9781491902646.
^ "تاريخ العملات المشفرة". litecoin.info wiki . 7 فبراير 2014. مؤرشف من الأصل في 11 يونيو 2016. استرجاع 27 يونيو 2014 .
^ Roman Guelfi-Gibbs. Litecoin Scrypt Mining Configurations for Radeon 7950. Amazon Digital Services. مؤرشف من الأصل في 24 أكتوبر 2016. تم الاسترجاع في 11 سبتمبر 2017 .
^ جويل هروسكا (10 ديسمبر 2013). "الارتفاع الهائل في تعدين لايتكوين يؤدي إلى نقص في بطاقات الرسوميات". ExtremeTech. مؤرشف من الأصل في 12 ديسمبر 2017. تم الاسترجاع في 1 يناير 2014 .
^ "الإصدار 1.3.2". 2 أكتوبر 2023. تم الاسترجاع 20 أكتوبر 2023 .
^ Shelley, Johnny; Stolarczyk, Philip. "Bcrypt – Blowfish File Encryption (homepage)". Sourceforge . مؤرشف من الأصل في 29 أغسطس 2015 . تم الاسترجاع في 8 أبريل 2024 .
^ "bcrypt APK for Android – free download on Droid Informer". droidinformer.org . مؤرشف من الأصل في 15 فبراير 2020 . تم الاسترجاع 2 مارس 2022 .
^ "حزمة T2 – trunk – bcrypt – أداة لتشفير الملفات". t2sde.org . مؤرشف من الأصل في 28 أكتوبر 2017 . تم استرجاعه في 2 مارس 2022 .
^ "معلومات ترخيص Oracle® GoldenGate". مركز مساعدة Oracle . مؤرشف من الأصل في 6 مارس 2024. تم الاسترجاع في 8 أبريل 2024 .