ജന്മദിനാക്രമണം

ഒരു ഗൂഢശാസ്ത്ര ആക്രമണമാണ് ജന്മദിനാക്രമണം (Birthday attack), സംഭാവ്യത സിദ്ധാന്തത്തിലെ ജന്മദിനപ്രശ്നത്തിനു പിന്നിലെ ഗണിതത്തെ ഫലപ്രദമായി ഉപയോഗപ്പെടുത്തി നടത്തുന്നതിനാലാണ് ഈ പേര് ലഭിക്കുവാൻ കാരണം. $f$ എന്ന ഫലനം ഉണ്ടെങ്കിൽ ഈ ആക്രമണത്തിലെ ലക്ഷ്യം $f(x_{1})=f(x_{2})$ എന്നത് സാധ്യമാകുന്ന രണ്ട് വ്യത്യസ്ത $x_{1},x_{2}$ എന്ന ഇൻപുട്ടുകൾ കണ്ടുപിടിക്കലാണ്, അങ്ങനെയുള്ള $x_{1},x_{2}$ എന്ന ജോഡി ഇൻപുട്ടുകളെ കൊളീഷൻ (collision) എന്ന് പറയുന്നു. ഒരു കൊളീഷൻ കണ്ടുപിടിക്കുന്നതിന് വേണ്ടി യാദൃച്ഛികമായോ, യാദൃച്ഛികം എന്ന രൂപേണയോ തിരഞ്ഞെടുക്കുന്ന വ്യത്യസ്ത ഇൻപുട്ടുകളിൽ $f$ ഫലനത്തിന്റെ ഫലങ്ങൾ കണ്ടുപിടിക്കുകയാണ് ഈ ആക്രമണത്തിൽ ചെയ്യുന്നത്. പ്രതേകിച്ച് $f(x)$ എന്ന ഫലനത്തിന്റെ ഔട്ട്പുട്ടായി $H$ എന്ന വലിയ ഗണത്തിലെ വ്യത്യസ്ത അംഗങ്ങൾ ഒരേ സംഭാവ്യതയിലാണ് ലഭിമാകുന്നതെങ്കിൽ ജന്മദിനപ്രശ്നം അനുസരിച്ച് ഈ രീതി ഫലപ്രദമാണ്. ശരാശരി $1.25\cdot {\sqrt {H}}$ വ്യത്യസ്ത ശ്രമങ്ങൾക്ക് ശേഷം $f(x_{1})=f(x_{2})$ എന്നത് സാധ്യമാകുന്ന രണ്ട് വ്യത്യസ്ത $x_{1},x_{1}$ എന്ന ഇൻപുട്ടുകൾ ലഭിക്കുമെന്നാണ് ഇതുവഴി പ്രതീക്ഷിക്കുക.

ഗണിതം

പ്രധാന ലേഖനം: ജന്മദിനപ്രശ്നം

$H$ എന്ന ഗണത്തിൽ നിന്നും $n$ ഇൻപുട്ടുകൾ ഏകതാനമായും യാദൃച്ഛികമായും തിരഞ്ഞെടുക്കുന്നു എന്ന് കരുതുക, ഇതിൽ ആവർത്തനം അനുവദനീയവുമാണ്. $p(n;H)$ എന്നത് ഒരു വില തന്നെ ഒന്നിൽ കൂടുതൽ തവണ തിരഞ്ഞെടുക്കപ്പെടുന്നു എന്നതിന്റെ സംഭാവ്യതയാണെങ്കിൽ, അത് ഇങ്ങനെയെഴുതാം

$p(n;H)\approx 1-e^{-n(n-1)/(2H)}\approx 1-e^{-n^{2}/(2H)},$

ഇവിടെ തിരഞ്ഞെടുക്കേണ്ട കുറഞ്ഞ എണ്ണം വിലകൾ $n(p;H)$ ആണെങ്കിൽ, ഒരു കൊളീഷൻ കണ്ടെത്തുന്നതിനുള്ള ഏറ്റവും കുറഞ്ഞ സംഭാവ്യത $p$ ആണ്, മുകളിലെ വ്യജ്ഞകം വിപരീത രൂപത്തിലെഴുതുന്നതുവഴി ഇങ്ങനെ ലഭിക്കുന്നു.

$n(p;H)\approx {\sqrt {2H\ln {\frac {1}{1-p}}}},$

ഇവിടെ സംഭാവ്യത 0.5 ആയി നൽകുകയാണെങ്കിൽ നമുക്ക് ലഭിക്കുക

$n(0.5;H)\approx 1.1774{\sqrt {H}}$.

ആദ്യത്തെ കൊളീഷൻ കണ്ടുപിടിക്കുന്നതിനു മുൻപ് $Q(H)$ എണ്ണം വിലകൾ തിരഞ്ഞെടുക്കേണ്ടി വരും എങ്കിൽ, ഈ സംഖ്യ ഏതാണ്ട് ഇങ്ങനെ കണ്ടെത്താം

$Q(H)\approx {\sqrt {{\frac {\pi }{2}}H}}.$

ഉദാഹരണത്തിന്, ഇവിടെ 64 ബിറ്റ് ഹാഷാണ് ഉപയോഗിക്കപ്പെട്ടെതെങ്കിൽ മൊത്തം 1.8 × 10¹⁹ വ്യത്യസ്ത ഔട്ട്പുട്ടുകൾ ലഭ്യമാണ്. ഈ ഔട്ട്പുട്ടുകളെല്ലാം ഒരേ സംഭാവ്യതയിലാണ് നിലകൊള്ളുന്നതെങ്കിൽ ബ്രൂട്ട് ഫോഴ്സ് (brute force) രീതിയിൽ ഏകദേശം 5.1 × 10⁹ ശ്രമങ്ങൾക്കൊണ്ട് ഒരു കൊളീഷൻ കണ്ടെത്തുവാൻ സാധിക്കുന്നതാണ്. ഈ വിലയെ ജന്മദിന നിബദ്ധം (birthday bound) എന്നു വിളിക്കുന്നു. പൊതുവായി n-ബിറ്റ് കോഡുകൾക്ക് ഈ വില $2^{n/2}$ ഉപയോഗിച്ച് കണ്ടെത്താവുന്നതാണ്. കുറച്ച് ഉദാഹരണങ്ങൾ പട്ടികയിൽ നൽകിയിരിക്കുന്നു.

ബിറ്റുകൾ	സാധ്യമായ ഔട്ട്പുട്ടുകൾ (H)	യാദൃച്ഛിക കൊളിഷൻ കണ്ടെത്തുന്നതിനു വേണ്ട സംഭാവ്യത (p)
		10−18	10−15	10−12	10−9	10−6	0.1%	1%	25%	50%	75%
32	4.3 × 109	2	2	2	2.9	93	2.9 × 103	9.3 × 103	5.0 × 104	7.7 × 104	1.1 × 105
64	1.8 × 1019	6.1	1.9 × 102	6.1 × 103	1.9 × 105	6.1 × 106	1.9 × 108	6.1 × 108	3.3 × 109	5.1 × 109	7.2 × 109
128	3.4 × 1038	2.6 × 1010	8.2 × 1011	2.6 × 1013	8.2 × 1014	2.6 × 1016	8.3 × 1017	2.6 × 1018	1.4 × 1019	2.2 × 1019	3.1 × 1019
256	1.2 × 1077	4.8 × 1029	1.5 × 1031	4.8 × 1032	1.5 × 1034	4.8 × 1035	1.5 × 1037	4.8 × 1037	2.6 × 1038	4.0 × 1038	5.7 × 1038
384	3.9 × 10115	8.9 × 1048	2.8 × 1050	8.9 × 1051	2.8 × 1053	8.9 × 1054	2.8 × 1056	8.9 × 1056	4.8 × 1057	7.4 × 1057	1.0 × 1058
512	1.3 × 10154	1.6 × 1068	5.2 × 1069	1.6 × 1071	5.2 × 1072	1.6 × 1074	5.2 × 1075	1.6 × 1076	8.8 × 1076	1.4 × 1077	1.9 × 1077

Table shows number of hashes n(p) needed to achieve the given probability of success, assuming all hashes are equally likely. For comparison, 10⁻¹⁸ to 10⁻¹⁵ is the uncorrectable bit error rate of a typical hard disk [1]. In theory, MD5, 128 bits, should stay within that range until about 820 billion documents, even if its possible outputs are many more.