Correlation attack
কোরিলেশন অ্যাটাক হল স্ট্রিম সাইফারগুলি ভাঙার জন্য ক্রিপ্টোগ্রাফিক পরিচিত-প্লেইনটেক্সট আক্রমণের একটি শ্রেণী যার কীস্ট্রিমগুলি বুলিয়ান ফাংশন ব্যবহার করে বেশ কয়েকটি লিনিয়ার-ফিডব্যাক শিফট রেজিস্টারের (এলএফএসআর) আউটপুটকে একত্রিত করে তৈরি করা হয়। পারস্পরিক সম্পর্ক আক্রমণগুলি একটি পরিসংখ্যানগত দুর্বলতাকে কাজে লাগায় যা মূলধারার জন্য নির্বাচিত নির্দিষ্ট বুলিয়ান ফাংশন থেকে উদ্ভূত হয়। যদিও কিছু বুলিয়ান ফাংশন পারস্পরিক সম্পর্ক আক্রমণের জন্য ঝুঁকিপূর্ণ, এই ধরনের ফাংশন ব্যবহার করে উত্পন্ন স্ট্রিম সাইফারগুলি সহজাতভাবে অনিরাপদ নয়। ব্যাখ্যা কোরিলেশন অ্যাটাক তখন সম্ভব হয় যখন কীস্ট্রিম জেনারেটরের একটি পৃথক এল. এফ. এস. আর-এর আউটপুট অবস্থা এবং সমস্ত এল. এফ. এস. আর-এর আউটপুট অবস্থার সংমিশ্রণকারী বুলিয়ান ফাংশনের আউটপুটের মধ্যে একটি উল্লেখযোগ্য সম্পর্ক বিদ্যমান থাকে। এই আক্রমণগুলি মূলধারার আংশিক জ্ঞানের সংমিশ্রণে নিযুক্ত করা হয়, যা সরল পাঠ্যের আংশিক জ্ঞান থেকে উদ্ভূত হয়। তারপর একটি এক্সওআর লজিক গেট ব্যবহার করে দুটিকে তুলনা করা হয়। এই দুর্বলতা একজন আক্রমণকারীকে পৃথক এল. এফ. এস. আর এবং বাকি সিস্টেমের জন্য আলাদাভাবে ব্রুট-ফোর্স করার অনুমতি দেয়। উদাহরণস্বরূপ, একটি কীস্ট্রিম জেনারেটরে যেখানে চারটি 8-বিট এল. এফ. এস. আর একত্রিত হয়ে কীস্ট্রিম তৈরি করা হয়, এবং যদি একটি রেজিস্টার বুলিয়ান ফাংশন আউটপুটের সাথে সম্পর্কযুক্ত হয়, তবে প্রথমে এটিকে ব্রুট ফোর্স করা সম্ভব হয়, তারপরে বাকি তিনটি এল. এফ. এস. আর। ফলস্বরূপ, মোট আক্রমণ জটিলতা 28 + 224 হয়ে যায়। সমগ্র সিস্টেমে একটি ব্রুট-ফোর্স আক্রমণ চালানোর ব্যয়ের তুলনায়, জটিলতা 232 সহ, এটি 256 এর নিচে একটি আক্রমণ প্রচেষ্টার সঞ্চয় ফ্যাক্টরকে উপস্থাপন করে। যদি একটি দ্বিতীয় রেজিস্টার ফাংশনের সাথে সম্পর্কযুক্ত হয়, তবে প্রক্রিয়াটি পুনরাবৃত্তি করা যেতে পারে এবং 65028 এর নিচে একটি প্রচেষ্টা সঞ্চয় ফ্যাক্টরের জন্য আক্রমণের জটিলতা 28 + 28 + 216-এ হ্রাস করা যেতে পারে। উদাহরণ গেফ জেনারেটর একটি উদাহরণ হল গেফ জেনারেটর, যা তিনটি এলএফএসআর নিয়ে গঠিতঃ এলএফএসআর-1, এলএফএসআর-2 এবং এলএফএসআর-3। এই রেজিস্টারগুলিকে যথাক্রমেঃ,, এবং হিসাবে চিহ্নিত করা যাক। তারপরে, জেনারেটর আউটপুট প্রদানের জন্য তিনটি রেজিস্টারের সংমিশ্রণে বুলিয়ান ফাংশনটি দেওয়া হয় (অর্থাৎ। (এবং) XOR (এবং নয়))। তিনটি রেজিস্টারের আউটপুটের জন্য 23 = 8 টি সম্ভাব্য মান রয়েছে এবং তাদের প্রত্যেকটির জন্য এই সংমিশ্রণ ফাংশনের মান নীচের সারণিতে দেখানো হয়েছেঃ তৃতীয় রেজিস্টারের আউটপুট বিবেচনা করুন। উপরের টেবিলটি দেখায় যে 8টি সম্ভাব্য আউটপুটের মধ্যে 6টি জেনারেটর আউটপুটের সংশ্লিষ্ট মানের সমান। সমস্ত সম্ভাব্য ক্ষেত্রে 75 শতাংশ ক্ষেত্রে, এইভাবে এল. এফ. এস. আর-3 জেনারেটরের সঙ্গে 'সম্পর্কযুক্ত'। এটি একটি দুর্বলতা যা নিম্নরূপ কাজে লাগানো যেতে পারেঃ একটি সরল পাঠ্যের সাইফার পাঠ্যে একটি বাধা তৈরি করা যেতে পারে যা একটি স্ট্রিম সাইফার দ্বারা তার কীস্ট্রিম জেনারেটর হিসাবে একটি গেফ জেনারেটর ব্যবহার করে এনক্রিপ্ট করা হয়েছে, অর্থাৎ। জন্য, সময়ে এল. এফ. এস. আর-1-এর আউটপুট কোথায়, ইত্যাদি। এটিও সম্ভব যে সাধারণ পাঠ্যের অংশ, যেমন। প্লেইনটেক্সটের প্রথম 32টি বিট (টেক্সটের 4টি এ. এস. সি. আই. আই অক্ষরের সাথে সম্পর্কিত)। প্লেইন টেক্সট একটি বৈধ এক্স. এম. এল ফাইল বিবেচনা করে এটি সম্পূর্ণ অসম্ভব নয়, উদাহরণস্বরূপ, প্রথম 4টি এ. এস. সি. আই. আই অক্ষর অবশ্যই "<এক্স. এম. এল" হতে হবে। একইভাবে, অনেক ফাইল ফরম্যাট বা নেটওয়ার্ক প্রোটোকলের খুব আদর্শ শিরোনাম বা পাদচরণ রয়েছে। আটকানো এবং আমাদের পরিচিত/অনুমানের পরিপ্রেক্ষিতে, আমরা সহজেই এক্সওআর-ইঙ্গ দ্বারা উভয়কে একসাথে খুঁজে পেতে পারি। এটি জেনারেটর আউটপুটের পরপর 32টি বিট নির্ধারণ করা সহজ করে তোলে। এটি এল. এফ. এস. আর-3-এর জন্য সম্ভাব্য কীগুলির (প্রাথমিক মান) স্থানের একটি ব্রুট-ফোর্স অনুসন্ধানকে সক্ষম করে (ধরে নিই যে আমরা এল. এফ. এস. আর-3-এর ট্যাপ করা বিটগুলি জানি, একটি অনুমান যা কের্কহফসের নীতির সাথে সামঞ্জস্যপূর্ণ)। মূল স্থানের যে কোনও প্রদত্ত কী-এর জন্য, আমরা দ্রুত এল. এফ. এস. আর-3-এর আউটপুটের প্রথম 32 বিট তৈরি করতে পারি এবং এগুলিকে পুরো জেনারেটরের আউটপুটের পুনরুদ্ধার করা 32 বিটের সাথে তুলনা করতে পারি। যেহেতু আমরা আগে প্রতিষ্ঠিত করেছি যে এল. এফ. এস. আর-3-এর আউটপুট এবং জেনারেটরের মধ্যে 75 শতাংশ সম্পর্ক রয়েছে, তাই আমরা জানি যে এল. এফ. এস. আর-3-এর জন্য আমরা সঠিকভাবে কী অনুমান করেছি যদি এল. এফ. এস. আর-3 আউটপুটের প্রথম 32টি বিটের মধ্যে প্রায় 24টি জেনারেটর আউটপুটের সংশ্লিষ্ট বিটের সাথে মিলে যায়। যদি আমরা ভুলভাবে অনুমান করে থাকি, তাহলে এই দুটি ক্রমের প্রথম 32টি বিটের প্রায় অর্ধেক বা 16টি মিলবে বলে আমাদের আশা করা উচিত। এইভাবে আমরা এল. এফ. এস. আর-1 এবং এল. এফ. এস. আর-2-এর চাবি থেকে স্বাধীনভাবে এল. এফ. এস. আর-3-এর চাবি পুনরুদ্ধার করতে পারি। এই পর্যায়ে আমরা 3টি এল. এফ. এস. আর-এর একটি ব্যবস্থাকে পাশবিক বল প্রয়োগ করার সমস্যাকে হ্রাস করে একটি একক এল. এফ. এস. আর-কে এবং তারপর 2টি এল. এফ. এস. আর-এর একটি ব্যবস্থাকে পাশবিক বল প্রয়োগের সমস্যায় পরিণত করেছি। এখানে সঞ্চিত প্রচেষ্টার পরিমাণ নির্ভর করে এল. এফ. এস. আর-এর দৈর্ঘ্যের উপর। বাস্তবসম্মত মূল্যবোধের জন্য, এটি একটি খুব উল্লেখযোগ্য সঞ্চয় এবং ব্রুট-ফোর্স আক্রমণকে খুব ব্যবহারিক করে তুলতে পারে। উপরের সারণিতে লক্ষ্য করুন যে এটি 8-এর মধ্যে 6 বার জেনারেটর আউটপুটের সাথে একমত, আবার জেনারেটর আউটপুটের মধ্যে 75 শতাংশ পারস্পরিক সম্পর্কের একটি সম্পর্ক। আমরা এল. এফ. এস. আর-1 এবং এল. এফ. এস. আর-3-এর চাবিকাঠি থেকে স্বাধীনভাবে এল. এফ. এস. আর-2-এর বিরুদ্ধে একটি ব্রুট ফোর্স আক্রমণ শুরু করতে পারি, শুধুমাত্র এল. এফ. এস. আর-1-কে অবিচ্ছিন্ন রেখে। এইভাবে, আমরা 3টি সম্পূর্ণ স্বাধীন এল. এফ. এস. আর-কে পাশবিকভাবে বাধ্য করার জন্য যতটা প্রয়োজন ততটা প্রচেষ্টার মাধ্যমে গেফ জেনারেটরটি ভাঙতে সক্ষম। এর অর্থ হল গেফ জেনারেটর একটি খুব দুর্বল জেনারেটর এবং স্ট্রিম সাইফার কীস্ট্রিম তৈরি করতে কখনই ব্যবহার করা উচিত নয়। উপরের টেবিল থেকে লক্ষ্য করুন যে জেনারেটর আউটপুট 8-এর মধ্যে 4 বার-একটি 50 শতাংশ পারস্পরিক সম্পর্ক। আমরা অন্যদের থেকে স্বাধীনভাবে এল. এফ. এস. আর-1-কে পাশবিকভাবে জোর করার জন্য এটি ব্যবহার করতে পারি নাঃ সঠিক কী আউটপুট দেবে যা 50 শতাংশ সময় জেনারেটর আউটপুটের সাথে একমত হবে, তবে গড়ে তাই একটি ভুল কী হবে। এটি একটি নিরাপত্তা দৃষ্টিকোণ থেকে আদর্শ পরিস্থিতির প্রতিনিধিত্ব করে-সংমিশ্রণ ফাংশনটি বেছে নেওয়া উচিত যাতে প্রতিটি পরিবর্তনশীল এবং সংমিশ্রণ ফাংশনের আউটপুটের মধ্যে পারস্পরিক সম্পর্ক যতটা সম্ভব 50 শতাংশের কাছাকাছি থাকে। বাস্তবে, এমন একটি ফাংশন খুঁজে পাওয়া কঠিন হতে পারে যা অন্যান্য নকশার মানদণ্ড ত্যাগ না করে এটি অর্জন করে, যেমন, সময়ের দৈর্ঘ্য, তাই একটি আপোষের প্রয়োজন হতে পারে। আক্রমণের পরিসংখ্যানগত প্রকৃতি স্পষ্ট করা যদিও উপরের উদাহরণটি পারস্পরিক সম্পর্কের আক্রমণের পিছনে তুলনামূলকভাবে সহজ ধারণাগুলি ভালভাবে চিত্রিত করে, তবে এটি সম্ভবত পৃথক এলএফএসআরগুলির ব্রুট ফোর্সিং কীভাবে এগিয়ে যায় তার ব্যাখ্যাকে সহজতর করে। ভুলভাবে অনুমান করা কীগুলি এল. এফ. এস. আর আউটপুট তৈরি করবে যা জেনারেটর আউটপুটের সাথে প্রায় 50 শতাংশ সময় একমত হয় কারণ, একটি নির্দিষ্ট দৈর্ঘ্যের দুটি র্যান্ডম বিট সিকোয়েন্স দেওয়া হলে, কোনও নির্দিষ্ট বিটের মধ্যে সিকোয়েন্সের মধ্যে চুক্তির সম্ভাবনা 0.5 হয়। যাইহোক, নির্দিষ্ট পৃথক ভুল কীগুলি ভালভাবে এলএফএসআর আউটপুট তৈরি করতে পারে যা জেনারেটর আউটপুটের সাথে প্রায়শই ঠিক 50 শতাংশের চেয়ে কম বা কম সম্মত হয়। এটি এল. এফ. এস. আর-এর ক্ষেত্রে বিশেষভাবে লক্ষণীয়, যার জেনারেটরের সাথে সম্পর্ক বিশেষভাবে শক্তিশালী নয়; যথেষ্ট ছোট পারস্পরিক সম্পর্কের ক্ষেত্রে, এটি অবশ্যই সম্ভাবনার ক্ষেত্রের বাইরে নয় যে একটি ভুলভাবে অনুমান করা কী এল. এফ. এস. আর আউটপুটের দিকে পরিচালিত করবে যা জেনারেটর আউটপুটের পছন্দসই সংখ্যক বিটের সাথে একমত। সুতরাং, সেই এল. এফ. এস. আর-এর অনন্য চাবি শনাক্ত করা সম্ভব নাও হতে পারে। তবে বেশ কয়েকটি সম্ভাব্য কী সনাক্ত করা সম্ভব হতে পারে, যা এখনও সাইফারের সুরক্ষার একটি উল্লেখযোগ্য লঙ্ঘন। উপরন্তু, পরিচিত সরল পাঠ্যের একটি মেগাবাইট দেওয়া হলে, পরিস্থিতি যথেষ্ট ভিন্ন হবে। একটি ভুল কী এল. এফ. এস. আর আউটপুট তৈরি করতে পারে যা 512 কিলোবাইটের বেশি জেনারেটর আউটপুটের সাথে একমত হয় তবে সঠিকভাবে অনুমান করা কী হিসাবে 768 কিলোবাইট জেনারেটর আউটপুটের সাথে একমত হওয়ার সম্ভাবনা নেই। একটি নিয়ম হিসাবে, একটি পৃথক রেজিস্টার এবং জেনারেটর আউটপুটের মধ্যে পারস্পরিক সম্পর্ক যত দুর্বল হবে, তত বেশি পরিচিত সরল পাঠ্যটি উচ্চ মাত্রার আত্মবিশ্বাসের সাথে সেই রেজিস্টারের কী খুঁজে বের করতে হবে। একটি প্রদত্ত পারস্পরিক সম্পর্কের জন্য প্রয়োজনীয় পরিচিত সরল পাঠ্যের দৈর্ঘ্যের অনুমান দ্বিপদী বণ্টন ব্যবহার করে গণনা করা যেতে পারে। উচ্চতর ক্রমের পারস্পরিক সম্পর্ক সংজ্ঞা জিওফ জেনারেটরের উপর উদাহরণ আক্রমণে যে পারস্পরিক সম্পর্কগুলি কাজে লাগানো হয়েছিল সেগুলি প্রথম ক্রমের পারস্পরিক সম্পর্কগুলির উদাহরণ যা বলা হয়ঃ সেগুলি জেনারেটর আউটপুটের মান এবং একটি পৃথক এলএফএসআর-এর মধ্যে পারস্পরিক সম্পর্ক। এগুলি ছাড়াও উচ্চ-ক্রমের পারস্পরিক সম্পর্কগুলি সংজ্ঞায়িত করা সম্ভব। উদাহরণস্বরূপ, এটি সম্ভব হতে পারে যে কোনও প্রদত্ত বুলিয়ান ফাংশনের কোনও পৃথক রেজিস্টারের সাথে কোনও দৃঢ় সম্পর্ক নেই, তবে দুটি রেজিস্টারের কিছু বুলিয়ান ফাংশনের মধ্যে একটি উল্লেখযোগ্য সম্পর্ক থাকতে পারে, উদাহরণস্বরূপ। এটি দ্বিতীয় ক্রমের পারস্পরিক সম্পর্কের একটি উদাহরণ হবে। তৃতীয় ক্রমের পারস্পরিক সম্পর্ক এবং উচ্চতর এইভাবে সংজ্ঞায়িত করা যেতে পারে। উচ্চ-ক্রমের পারস্পরিক সম্পর্ক আক্রমণগুলি একক-ক্রমের পারস্পরিক সম্পর্ক আক্রমণগুলির চেয়ে বেশি শক্তিশালী হতে পারে, তবে, এই প্রভাবটি "সীমিত রিটার্নের আইন" সাপেক্ষে। নীচের টেবিলটি একটি একক বুলিয়ান ফাংশন দ্বারা মিলিত আটটি 8-বিট এলএফএসআর সমন্বিত একটি কীস্ট্রিম জেনারেটরের উপর বিভিন্ন আক্রমণের জন্য গণনামূলক ব্যয়ের একটি পরিমাপ দেখায়। খরচের গণনা বোঝা তুলনামূলকভাবে সহজবোধ্যঃ যোগফলের বামতম পদটি পরস্পর সম্পর্কিত জেনারেটরগুলির জন্য মূল স্থানের আকারকে উপস্থাপন করে এবং ডানতম পদটি অবশিষ্ট জেনারেটরগুলির জন্য মূল স্থানের আকারকে উপস্থাপন করে। যদিও উচ্চ-ক্রমের পারস্পরিক সম্পর্কগুলি আরও শক্তিশালী আক্রমণের দিকে পরিচালিত করে, তবে সেগুলি খুঁজে পাওয়া আরও কঠিন, কারণ জেনারেটর আউটপুটের সাথে সম্পর্কিত হওয়ার জন্য উপলব্ধ বুলিয়ান ফাংশনের স্থান ফাংশনের সাথে যুক্তির সংখ্যা বাড়ার সাথে সাথে বৃদ্ধি পায়। পরিভাষা চলকের একটি বুলিয়ান ফাংশনকে বলা হয় "-তম ক্রম পারস্পরিক সম্পর্ক প্রতিরোধ ক্ষমতা", অথবা কিছু পূর্ণসংখ্যার জন্য "তম ক্রম পারস্পরিক সম্পর্ক প্রতিরোধ ক্ষমতা", যদি ফাংশনের আউটপুট এবং তার ইনপুটগুলির কোনও বুলিয়ান ফাংশনের মধ্যে কোনও উল্লেখযোগ্য সম্পর্ক বিদ্যমান না থাকে। উদাহরণস্বরূপ, একটি বুলিয়ান ফাংশন যার কোনও প্রথম-ক্রম বা দ্বিতীয়-ক্রমের পারস্পরিক সম্পর্ক নেই, কিন্তু যার তৃতীয়-ক্রমের পারস্পরিক সম্পর্ক রয়েছে, তা দ্বিতীয় ক্রমের পারস্পরিক সম্পর্ক প্রতিরোধ ক্ষমতা প্রদর্শন করে। স্পষ্টতই, উচ্চতর পারস্পরিক সম্পর্ক প্রতিরোধ ক্ষমতা একটি ফাংশনকে একটি কীস্ট্রিম জেনারেটরে ব্যবহারের জন্য আরও উপযুক্ত করে তোলে (যদিও এটি একমাত্র জিনিস নয় যা বিবেচনা করা দরকার)। সিজেন্থালার দেখিয়েছেন যে বীজগাণিতিক মাত্রার চলকের বুলিয়ান ফাংশনের পারস্পরিক সম্পর্ক প্রতিরোধ ক্ষমতা সন্তুষ্ট করে; প্রদত্ত ইনপুট চলকের জন্য, এর অর্থ হল যে একটি উচ্চ বীজগাণিতিক মাত্রা সর্বাধিক সম্ভাব্য পারস্পরিক সম্পর্ক প্রতিরোধ ক্ষমতাকে সীমাবদ্ধ করবে। উপরন্তু, যদি ফাংশনটি ভারসাম্যপূর্ণ হয়। এটি অনুসরণ করে যে ভেরিয়েবলের একটি ফাংশন th অর্ডার কোরিলেশন ইমিউন হওয়া অসম্ভব। এটি এই বিষয়টি থেকেও আসে যে, এই ধরনের যে কোনও ফাংশন ইনপুট ফাংশনের এক্সওআর-এর সংমিশ্রণ হিসাবে রিড-মুলার ভিত্তি ব্যবহার করে লেখা যেতে পারে। সাইফার ডিজাইনের প্রভাব একটি স্ট্রিম সাইফারের নিরাপত্তায় পারস্পরিক সম্পর্ক আক্রমণের প্রভাবের সম্ভাব্য চরম তীব্রতার পরিপ্রেক্ষিতে, স্ট্রিম সাইফারে এটি ব্যবহার করার সিদ্ধান্ত নেওয়ার আগে পারস্পরিক সম্পর্ক প্রতিরোধের জন্য একটি প্রার্থী বুলিয়ান সংমিশ্রণ ফাংশন পরীক্ষা করা অপরিহার্য। যাইহোক, এটি লক্ষ্য করা গুরুত্বপূর্ণ যে উচ্চ পারস্পরিক সম্পর্ক প্রতিরোধ ক্ষমতা একটি প্রয়োজনীয়, কিন্তু একটি কীস্ট্রিম জেনারেটরে ব্যবহারের জন্য উপযুক্ত বুলিয়ান ফাংশনের জন্য পর্যাপ্ত শর্ত নয়। বিবেচনা করার মতো অন্যান্য বিষয় রয়েছে, উদাহরণস্বরূপ, ফাংশনটি ভারসাম্যপূর্ণ কিনা-সমস্ত সম্ভাব্য ইনপুট বিবেচনা করার সময় এটি যতগুলি আউটপুট দেয় ততগুলি বা মোটামুটিভাবে যতগুলি আউটপুট দেয় ততগুলি 0 হয়। একটি নির্দিষ্ট আকারের বুলিয়ান ফাংশনগুলি সহজেই তৈরি করার পদ্ধতিগুলিতে গবেষণা পরিচালিত হয়েছে যা কমপক্ষে পারস্পরিক সম্পর্কের অনাক্রম্যতার কিছু নির্দিষ্ট ক্রমের নিশ্চয়তা দেয়। এই গবেষণায় ইমিউন বুলিয়ান ফাংশন এবং ত্রুটি সংশোধন কোডের মধ্যে পারস্পরিক সম্পর্ক উন্মোচিত হয়েছে। এছাড়াও ক্রিপ্টোগ্রাফি রেফারেন্সের বিষয়গুলি দেখুন ব্রুস স্নাইয়ার। ফলিত ক্রিপ্টোগ্রাফিঃ সি, দ্বিতীয় সংস্করণে প্রোটোকল, অ্যালগরিদম এবং সোর্স কোড। জন উইলি অ্যান্ড সন্স, ইনকর্পোরেটেড 1996। ধারা 16.4-এর পৃষ্ঠা 382: এল. এফ. এস. আর ব্যবহার করে স্ট্রিম সাইফার। বাহ্যিক লিঙ্ক বুলিয়ান ফাংশনগুলির অনলাইন ডাটাবেস দর্শকদের পারস্পরিক সম্পর্ক প্রতিরোধ ক্ষমতা সহ বিভিন্ন উপায়ে বুলিয়ান ফ্যাক্টরগুলির একটি ডাটাবেস অনুসন্ধান করার অনুমতি দেয়। ক্রিপ্টোগ্রাফিক আক্রমণ