Correlation attack
સહસંબંધ હુમલાઓ એ પ્રવાહ સંકેતલિપીઓને તોડવા માટે ક્રિપ્ટોગ્રાફિક જાણીતા-પ્લેઇનટેક્સ્ટ હુમલાઓનો એક વર્ગ છે, જેમના મુખ્ય પ્રવાહો બુલિયન કાર્યનો ઉપયોગ કરીને કેટલાક રેખીય-પ્રતિસાદ શિફ્ટ રજિસ્ટર (એલ. એફ. એસ. આર.) ના આઉટપુટને જોડીને પેદા થાય છે. સહસંબંધ હુમલાઓ આંકડાકીય નબળાઈનો ઉપયોગ કરે છે જે કીસ્ટ્રીમ માટે પસંદ કરેલા ચોક્કસ બુલિયન કાર્યમાંથી ઉદ્ભવે છે. જ્યારે કેટલાક બુલિયન કાર્યો સહસંબંધ હુમલાઓ માટે સંવેદનશીલ હોય છે, ત્યારે આવા કાર્યોનો ઉપયોગ કરીને પેદા થતા પ્રવાહ સંકેતો સ્વાભાવિક રીતે અસુરક્ષિત નથી. સ્પષ્ટીકરણ સહસંબંધ હુમલાઓ ત્યારે શક્ય બને છે જ્યારે કીસ્ટ્રીમ જનરેટરમાં વ્યક્તિગત એલ. એફ. એસ. આર. ની આઉટપુટ સ્થિતિ અને તમામ એલ. એફ. એસ. આર. ની આઉટપુટ સ્થિતિઓને જોડતા બુલિયન કાર્યના આઉટપુટ વચ્ચે નોંધપાત્ર સહસંબંધ અસ્તિત્વમાં હોય. આ હુમલાઓનો ઉપયોગ મુખ્યપ્રવાહના આંશિક જ્ઞાન સાથે કરવામાં આવે છે, જે સાદા લખાણના આંશિક જ્ઞાનમાંથી મેળવવામાં આવે છે. ત્યારબાદ XOR લોજિક ગેટનો ઉપયોગ કરીને બંનેની સરખામણી કરવામાં આવે છે. આ નબળાઈ હુમલાખોરને વ્યક્તિગત એલ. એફ. એસ. આર. અને બાકીની સિસ્ટમ માટે અલગથી કીને બ્રુટ-ફોર્સ કરવાની મંજૂરી આપે છે. દાખલા તરીકે, કીસ્ટ્રીમ જનરેટરમાં જ્યાં ચાર 8-બીટ એલ. એફ. એસ. આર. ને કીસ્ટ્રીમ બનાવવા માટે જોડવામાં આવે છે, અને જો રજિસ્ટરમાંથી એક બુલિયન ફંક્શન આઉટપુટ સાથે સહસંબંધિત હોય, તો તેને પહેલા બ્રુટ ફોર્સ કરવું શક્ય બને છે, ત્યારબાદ બાકીના ત્રણ એલ. એફ. એસ. આર. આવે છે. પરિણામે, હુમલાની કુલ જટિલતા 28 + 224 બને છે. સમગ્ર સિસ્ટમ પર બ્રુટ-ફોર્સ એટેક શરૂ કરવાના ખર્ચની તુલનામાં, જટિલતા 232 સાથે, આ માત્ર 256 થી ઓછા હુમલાના પ્રયાસ બચત પરિબળને રજૂ કરે છે. જો બીજું રજિસ્ટર કાર્ય સાથે સહસંબંધિત હોય, તો પ્રક્રિયાને પુનરાવર્તિત કરી શકાય છે અને 65028 થી ઓછા પ્રયાસ બચત પરિબળ માટે હુમલાની જટિલતાને 28 + 28 + 216 સુધી ઘટાડી શકાય છે. ઉદાહરણ ગેફ જનરેટર એક ઉદાહરણ ગેફ જનરેટર છે, જેમાં ત્રણ એલએફએસઆરનો સમાવેશ થાય છેઃ એલએફએસઆર-1, એલએફએસઆર-2 અને એલએફએસઆર-3. ચાલો આ રજિસ્ટરને અનુક્રમેઃ,, અને તરીકે દર્શાવવામાં આવે. પછી, જનરેટર આઉટપુટ પ્રદાન કરવા માટે ત્રણ રજિસ્ટરને જોડીને બુલિયન કાર્ય (એટલે કે. (અને) XOR (અને નહીં)). ત્રણ રજિસ્ટરના આઉટપુટ માટે 23 = 8 સંભવિત મૂલ્યો છે, અને તેમાંના દરેક માટે આ સંયોજન કાર્યનું મૂલ્ય નીચે કોષ્ટકમાં દર્શાવવામાં આવ્યું છેઃ ત્રીજા રજિસ્ટરના આઉટપુટને ધ્યાનમાં લો. ઉપરનું કોષ્ટક દર્શાવે છે કે 8 સંભવિત આઉટપુટમાંથી, 6 જનરેટર આઉટપુટના અનુરૂપ મૂલ્યની બરાબર છે. તમામ સંભવિત કેસોમાંથી 75 ટકા કિસ્સાઓમાં, આમ એલ. એફ. એસ. આર.-3 જનરેટર સાથે 'સહસંબંધિત' છે. આ એક નબળાઈ છે જેનો નીચે પ્રમાણે ઉપયોગ કરી શકાય છેઃ સાદા લખાણના સાઇફર લખાણ પર અવરોધન કરી શકાય છે, જેને સ્ટ્રીમ સાઇફર દ્વારા તેના કીસ્ટ્રીમ જનરેટર તરીકે ગેફ જનરેટરનો ઉપયોગ કરીને એન્ક્રિપ્ટ કરવામાં આવ્યું છે, એટલે કે. માટે, સમયે LFSR-1 નું આઉટપુટ ક્યાં છે, વગેરે. તે પણ શક્ય છે કે સાદા લખાણનો ભાગ, દા. ત. સાદા લખાણના પ્રથમ 32 બિટ્સ (લખાણના 4 ASCII અક્ષરોને અનુરૂપ). સાદા લખાણને માન્ય XML ફાઇલ તરીકે ધ્યાનમાં લેતા આ સંપૂર્ણપણે અસંભવિત નથી, ઉદાહરણ તરીકે, પ્રથમ 4 ASCII અક્ષરો "<XML" હોવા જોઈએ. તેવી જ રીતે, ઘણા ફાઇલ ફોર્મેટ અથવા નેટવર્ક પ્રોટોકોલમાં ખૂબ જ પ્રમાણભૂત હેડર અથવા ફૂટર્સ હોય છે. અવરોધિત અને આપણા જાણીતા/અનુમાનિતને જોતાં, આપણે સરળતાથી XOR દ્વારા બંનેને એકસાથે શોધી શકીએ છીએ. આનાથી જનરેટર આઉટપુટના સતત 32 બિટ્સ નક્કી કરવાનું સરળ બને છે. આ એલ. એફ. એસ. આર.-3 માટે સંભવિત કીઓ (પ્રારંભિક મૂલ્યો) ની જગ્યાની બ્રુટ-ફોર્સ શોધને સક્ષમ કરે છે (એમ ધારીને કે આપણે એલ. એફ. એસ. આર.-3 ના ટેપ કરેલા બિટ્સને જાણતા હોઈએ છીએ, જે ધારણા કેર્કહોફ્સના સિદ્ધાંતને અનુરૂપ છે). કી સ્પેસમાં આપેલ કોઈપણ કી માટે, આપણે ઝડપથી એલ. એફ. એસ. આર.-3 ના આઉટપુટના પ્રથમ 32 બિટ્સ પેદા કરી શકીએ છીએ અને તેની તુલના આપણા સમગ્ર જનરેટરના આઉટપુટના પુનઃપ્રાપ્ત 32 બિટ્સ સાથે કરી શકીએ છીએ. કારણ કે આપણે અગાઉ સ્થાપિત કર્યું છે કે એલ. એફ. એસ. આર.-3ના ઉત્પાદન અને જનરેટર વચ્ચે 75 ટકા સહસંબંધ છે, આપણે જાણીએ છીએ કે જો એલ. એફ. એસ. આર.-3ના ઉત્પાદનના પ્રથમ 32 બિટ્સમાંથી આશરે 24 બિટ્સ જનરેટરના ઉત્પાદનના અનુરૂપ બિટ્સ સાથે મેળ ખાય તો આપણે એલ. એફ. એસ. આર.-3 માટે કીનો સાચો અંદાજ લગાવી દીધો છે. જો આપણે ખોટો અંદાજ લગાવ્યો હોય, તો આપણે આ બે સિક્વન્સના પ્રથમ 32 બિટ્સમાંથી લગભગ અડધા અથવા 16 સાથે મેળ ખાવાની અપેક્ષા રાખવી જોઈએ. આમ આપણે એલ. એફ. એસ. આર.-1 અને એલ. એફ. એસ. આર.-2ની ચાવીઓથી સ્વતંત્ર રીતે એલ. એફ. એસ. આર.-3 માટેની ચાવી પુનઃપ્રાપ્ત કરી શકીએ છીએ. આ તબક્કે આપણે 3 એલ. એફ. એસ. આર. ની પ્રણાલીને બળજબરીથી બળજબરીથી બળજબરીથી બળજબરીથી બળજબરીથી બળજબરીથી બળજબરીથી બળજબરીથી બળજબરીથી બળજબરીથી બળજબરીથી બળજબરીથી બળજબરીથી બળજબરીથી બળજબરીથી બળજબરીથી બળજબરીથી બળજબરીથી બળજબરીથી બળજબરીથી બળજબરીથી બળજબરીથી બળજબરીથી બળજબરીથી બળજબરીથી બળજબરીથી બળજબરીથી બળજબરીથી બળજબરીથી બળજબરીથી બળજબરીથી બળજબરીથી બળજબરીથી બળજબરીથી બળજબરીથી બળજબરીથી બળજબરીથી બળજબરીથી બળજબરીથી બળજબરીથી બળજબરીથી બળજબરીથી બળજબરીથી બળજબરીથી બળજબરીથી બળજબરીથી અહીં બચાવેલા પ્રયાસની રકમ એલ. એફ. એસ. આર. ની લંબાઈ પર આધારિત છે. વાસ્તવિક મૂલ્યો માટે, તે ખૂબ જ નોંધપાત્ર બચત છે અને બ્રુટ-ફોર્સ હુમલાઓને ખૂબ જ વ્યવહારુ બનાવી શકે છે. ઉપરના કોષ્ટકમાં અવલોકન કરો કે જે 8 માંથી 6 વખત જનરેટર આઉટપુટ સાથે પણ સંમત થાય છે, ફરીથી જનરેટર આઉટપુટ અને વચ્ચે 75 ટકા સહસંબંધનો સહસંબંધ છે. આપણે એલ. એફ. એસ. આર.-1 અને એલ. એફ. એસ. આર.-3ની ચાવીઓથી સ્વતંત્ર રીતે એલ. એફ. એસ. આર.-2 સામે બ્રુટ ફોર્સ એટેક શરૂ કરી શકીએ છીએ, જેનાથી માત્ર એલ. એફ. એસ. આર.-1 અખંડ રહે છે. આમ, આપણે 3 સંપૂર્ણપણે સ્વતંત્ર એલ. એફ. એસ. આર. ને બળજબરીથી ચલાવવા માટે જરૂરી તેટલા પ્રયત્નો સાથે ગેફ જનરેટરને તોડી શકીએ છીએ. આનો અર્થ એ છે કે ગેફ જનરેટર ખૂબ જ નબળું જનરેટર છે અને તેનો ઉપયોગ ક્યારેય સ્ટ્રીમ સાઇફર કીસ્ટ્રીમ્સ બનાવવા માટે થવો જોઈએ નહીં. ઉપરના કોષ્ટકમાંથી નોંધ કરો કે જે જનરેટર આઉટપુટ સાથે 8 માંથી 4 વખત સંમત થાય છે-50 ટકા સહસંબંધ. આપણે આનો ઉપયોગ અન્ય લોકોથી સ્વતંત્ર રીતે એલ. એફ. એસ. આર.-1 ને બ્રુટ ફોર્સ કરવા માટે કરી શકતા નથીઃ સાચી કી આઉટપુટ આપશે જે 50 ટકા સમય જનરેટર આઉટપુટ સાથે સંમત થાય છે, પરંતુ સરેરાશ તે ખોટી કી હશે. આ સુરક્ષાના દ્રષ્ટિકોણથી આદર્શ પરિસ્થિતિનું પ્રતિનિધિત્વ કરે છે-સંયોજન કાર્ય પસંદ કરવું જોઈએ જેથી દરેક ચલ અને સંયોજન કાર્યના ઉત્પાદન વચ્ચેનો સહસંબંધ શક્ય તેટલો 50 ટકાની નજીક હોય. વ્યવહારમાં, અન્ય ડિઝાઇન માપદંડ, દા. ત., સમયગાળાનો ત્યાગ કર્યા વિના આ હાંસલ કરે તેવું કાર્ય શોધવું મુશ્કેલ હોઈ શકે છે, તેથી સમાધાન જરૂરી હોઈ શકે છે. હુમલાની આંકડાકીય પ્રકૃતિને સ્પષ્ટ કરવી જ્યારે ઉપરોક્ત ઉદાહરણ સહસંબંધ હુમલાઓ પાછળના પ્રમાણમાં સરળ ખ્યાલોને સારી રીતે સમજાવે છે, તે કદાચ વ્યક્તિગત એલ. એફ. એસ. આર. ની ક્રૂર બળજબરી કેવી રીતે આગળ વધે છે તેની ચોક્કસ સમજૂતીને સરળ બનાવે છે. ખોટી રીતે અનુમાનિત કીઓ એલ. એફ. એસ. આર. આઉટપુટ પેદા કરશે જે જનરેટર આઉટપુટ સાથે આશરે 50 ટકા સમય સંમત થાય છે કારણ કે, આપેલ લંબાઈના બે રેન્ડમ બીટ સિક્વન્સ આપવામાં આવે તો, કોઈપણ ચોક્કસ બીટ પર સિક્વન્સ વચ્ચેના કરારની સંભાવના 0.5 છે. જો કે, ચોક્કસ વ્યક્તિગત ખોટી કીઓ સારી રીતે એલ. એફ. એસ. આર. આઉટપુટ પેદા કરી શકે છે જે જનરેટર આઉટપુટ સાથે બરાબર 50 ટકાથી વધુ વખત સંમત થાય છે. આ ખાસ કરીને એલ. એફ. એસ. આર. ના કિસ્સામાં મુખ્ય છે, જેનો જનરેટર સાથેનો સહસંબંધ ખાસ કરીને મજબૂત નથી; નાના પર્યાપ્ત સહસંબંધો માટે, તે ચોક્કસપણે શક્યતાના ક્ષેત્રની બહાર નથી કે ખોટી રીતે અનુમાનિત કી પણ એલ. એફ. એસ. આર. આઉટપુટ તરફ દોરી જશે જે જનરેટર આઉટપુટના બિટ્સની ઇચ્છિત સંખ્યા સાથે સંમત થાય છે. આમ, તે એલ. એફ. એસ. આર. ની અનન્ય ચાવી ઓળખવી શક્ય ન પણ હોઈ શકે. જો કે, સંખ્યાબંધ સંભવિત કીઓને ઓળખવી શક્ય છે, જે હજુ પણ સાઇફરની સુરક્ષાનો નોંધપાત્ર ભંગ છે. વધુમાં, જાણીતા સાદા લખાણના મેગાબાઇટને જોતાં, પરિસ્થિતિ નોંધપાત્ર રીતે અલગ હશે. ખોટી કી એલ. એફ. એસ. આર. આઉટપુટ પેદા કરી શકે છે જે જનરેટર આઉટપુટના 512 કિલોબાઇટ્સથી વધુ સાથે સંમત થાય છે પરંતુ તે આઉટપુટ ઉત્પન્ન કરે તેવી શક્યતા નથી જે જનરેટર આઉટપુટના 768 કિલોબાઇટ્સ જેટલું યોગ્ય રીતે અનુમાનિત કી સાથે સંમત થાય છે. એક નિયમ તરીકે, વ્યક્તિગત રજિસ્ટર અને જનરેટર આઉટપુટ વચ્ચેનો સહસંબંધ જેટલો નબળો હોય છે, તેટલો જ વધુ જાણીતો સાદા લખાણ તે રજિસ્ટરની ચાવીને ઉચ્ચ સ્તરના આત્મવિશ્વાસ સાથે શોધવા માટે જરૂરી છે. આપેલ સહસંબંધ માટે જરૂરી જાણીતા સાદા લખાણની લંબાઈના અંદાજોની ગણતરી દ્વિપદી વિતરણનો ઉપયોગ કરીને કરી શકાય છે. ઉચ્ચ ક્રમના સહસંબંધોની વ્યાખ્યા જ્યોફ જનરેટર પરના ઉદાહરણ હુમલામાં જે સહસંબંધોનો ઉપયોગ કરવામાં આવ્યો હતો તે પ્રથમ ક્રમના સહસંબંધોના ઉદાહરણો છેઃ તે જનરેટર આઉટપુટના મૂલ્ય અને વ્યક્તિગત એલ. એફ. એસ. આર. વચ્ચેના સહસંબંધ છે. આ ઉપરાંત ઉચ્ચ ક્રમના સહસંબંધોને વ્યાખ્યાયિત કરવું શક્ય છે. દાખલા તરીકે, તે શક્ય છે કે જ્યારે આપેલ બુલિયન કાર્યને તે જોડતા કોઈપણ વ્યક્તિગત રજિસ્ટર સાથે કોઈ મજબૂત સહસંબંધ નથી, ત્યારે બે રજિસ્ટરના કેટલાક બુલિયન કાર્ય વચ્ચે નોંધપાત્ર સહસંબંધ અસ્તિત્વમાં હોઈ શકે છે, દા. ત., આ બીજા ક્રમના સહસંબંધનું ઉદાહરણ હશે. ત્રીજા ક્રમના સહસંબંધો અને ઉચ્ચને આ રીતે વ્યાખ્યાયિત કરી શકાય છે. ઉચ્ચ-ક્રમના સહસંબંધ હુમલાઓ સિંગલ-ક્રમના સહસંબંધ હુમલાઓ કરતાં વધુ શક્તિશાળી હોઈ શકે છે, જો કે, આ અસર "મર્યાદિત વળતરના કાયદાને" આધિન છે. નીચેનું કોષ્ટક એક જ બુલિયન કાર્ય દ્વારા સંયુક્ત આઠ 8-બીટ એલ. એફ. એસ. આર. ધરાવતા કીસ્ટ્રીમ જનરેટર પરના વિવિધ હુમલાઓ માટે ગણતરીત્મક ખર્ચનું માપ દર્શાવે છે. ખર્ચની ગણતરીને સમજવી પ્રમાણમાં સીધી છેઃ સરવાળાની ડાબી બાજુની મુદત સહસંબંધિત જનરેટર માટે મુખ્ય જગ્યાના કદને રજૂ કરે છે, અને જમણી બાજુની મુદત બાકીના જનરેટર માટે મુખ્ય જગ્યાના કદને રજૂ કરે છે. જ્યારે ઉચ્ચ ક્રમના સહસંબંધો વધુ શક્તિશાળી હુમલાઓ તરફ દોરી જાય છે, ત્યારે તેમને શોધવાનું પણ વધુ મુશ્કેલ છે, કારણ કે કાર્યમાં દલીલોની સંખ્યા વધવાની સાથે જનરેટર આઉટપુટ સામે સહસંબંધ સ્થાપિત કરવા માટે ઉપલબ્ધ બુલિયન કાર્યોની જગ્યા વધે છે. પરિભાષા ચલોનું બુલિયન કાર્ય "-th ક્રમ સહસંબંધ રોગપ્રતિકારક" કહેવાય છે, અથવા કેટલાક પૂર્ણાંક માટે "th ક્રમ સહસંબંધ પ્રતિરક્ષા" હોય છે, જો કાર્યના આઉટપુટ અને તેના ઇનપુટ્સના કોઈપણ બુલિયન કાર્ય વચ્ચે કોઈ નોંધપાત્ર સહસંબંધ અસ્તિત્વમાં નથી. ઉદાહરણ તરીકે, બુલિયન કાર્ય કે જેમાં કોઈ પ્રથમ ક્રમ અથવા બીજા ક્રમના સહસંબંધ નથી, પરંતુ જે ત્રીજા ક્રમના સહસંબંધ ધરાવે છે તે બીજા ક્રમના સહસંબંધની પ્રતિરક્ષા દર્શાવે છે. દેખીતી રીતે, ઉચ્ચ સહસંબંધ પ્રતિરક્ષા કીસ્ટ્રીમ જનરેટરમાં ઉપયોગ માટે કાર્યને વધુ યોગ્ય બનાવે છે (જોકે આ એકમાત્ર વસ્તુ નથી જેને ધ્યાનમાં લેવાની જરૂર છે). સિજેન્થેલરે દર્શાવ્યું હતું કે ચલની બીજગણિત ડિગ્રીના બુલિયન કાર્યની સહસંબંધ પ્રતિરક્ષા સંતોષ આપે છે; ઇનપુટ ચલોના આપેલ સમૂહ માટે, આનો અર્થ એ છે કે ઉચ્ચ બીજગણિત ડિગ્રી મહત્તમ સંભવિત સહસંબંધ પ્રતિરક્ષાને પ્રતિબંધિત કરશે. વધુમાં, જો કાર્ય સંતુલિત હોય તો. તે અનુસરે છે કે ચલોનું કાર્ય th ક્રમ સહસંબંધ રોગપ્રતિકારક હોવું અશક્ય છે. આ એ હકીકત પરથી પણ અનુસરે છે કે આવા કોઈપણ કાર્યને ઇનપુટ કાર્યોના XOR ના સંયોજન તરીકે રીડ-મુલર આધારનો ઉપયોગ કરીને લખી શકાય છે. સાઇફર ડિઝાઇનની અસરોને સ્ટ્રીમ સાઇફરની સુરક્ષા પર સહસંબંધ હુમલાની અસરની સંભવિત આત્યંતિક તીવ્રતાને ધ્યાનમાં રાખીને, સ્ટ્રીમ સાઇફરમાં તેનો ઉપયોગ કરવાનો નિર્ણય લેતા પહેલા સહસંબંધ પ્રતિરક્ષા માટે ઉમેદવાર બુલિયન સંયોજન કાર્યનું પરીક્ષણ કરવું જરૂરી હોવું જોઈએ. જો કે, એ નોંધવું અગત્યનું છે કે ઉચ્ચ સહસંબંધ પ્રતિરક્ષા એ જરૂરી છે, પરંતુ કીસ્ટ્રીમ જનરેટરમાં ઉપયોગ માટે યોગ્ય બુલિયન કાર્ય માટે પૂરતી સ્થિતિ નથી. ધ્યાનમાં લેવા માટે અન્ય મુદ્દાઓ છે, ઉદાહરણ તરીકે, કાર્ય સંતુલિત છે કે નહીં-પછી ભલે તે બધા સંભવિત ઇનપુટ્સને ધ્યાનમાં લેવામાં આવે ત્યારે તે 0 જેટલું કરે છે તેટલું અથવા લગભગ 1 જેટલું આઉટપુટ આપે છે. આપેલ કદના સરળતાથી બુલિયન કાર્યો પેદા કરવા માટેની પદ્ધતિઓમાં સંશોધન હાથ ધરવામાં આવ્યું છે જે ઓછામાં ઓછા સહસંબંધ પ્રતિરક્ષાના અમુક ચોક્કસ ક્રમની બાંયધરી આપે છે. આ સંશોધનમાં સહસંબંધ રોગપ્રતિકારક બુલિયન કાર્યો અને ભૂલ સુધારણા સંકેતો વચ્ચેની કડીઓ મળી આવી છે. સંકેતલિપી સંદર્ભોમાં વિષયો બ્રુસ શ્નેયર પણ જુઓ. એપ્લાઇડ ક્રિપ્ટોગ્રાફીઃ સી, બીજી આવૃત્તિમાં પ્રોટોકોલ, અલ્ગોરિધમ્સ અને સોર્સ કોડ. જ્હોન વિલી એન્ડ સન્સ, ઇન્ક. 1996. વિભાગ 16.4 નું પાનું 382: એલ. એફ. એસ. આર. નો ઉપયોગ કરીને પ્રવાહ સંકેતો. બાહ્ય કડીઓ બુલિયન કાર્યોનો ઓનલાઇન ડેટાબેઝ મુલાકાતીઓને સહસંબંધ પ્રતિરક્ષા સહિત અનેક રીતે બુલિયન પરિબળોના ડેટાબેઝને શોધવાની મંજૂરી આપે છે. ક્રિપ્ટોગ્રાફિક હુમલાઓ