Tsammanin Entropy: Sabon Ma'auni don Kimanta Ƙarfin Kalmar Sirri

1. Gabatarwa & Dalili

Wannan takarda ta gabatar da Tsammanin Entropy, sabon ma'auni da aka tsara don kimanta ƙarfin kalmomin sirri na bazuwar ko masu kama da bazuwar. Dalilin ya samo asali ne daga gibi mai amfani a cikin kayan aikin tantance ƙarfin kalmar sirri da suka wanzu. Tsarin lissafi na gargajiya na haɗa-haɗa (misali, $\log_2(\text{sararin haruffa}^{\text{tsawon}})$) yana fitar da sakamako a cikin ƴan rago na bit, yayin da daidaitaccen tsarin masana'antu na NIST Entropy Estimation Suite ke ba da maki mafi ƙarancin entropy mai daidaitawa tsakanin 0 da 1. Wannan bambance-bambancen yana sa kwatanta kai tsaye da fassara mai ma'ana ya zama ƙalubale. Tsammanin Entropy yana cike wannan gibi ta hanyar ba da ƙimar ƙarfi akan ma'auni ɗaya na 0-1 kamar kayan aikin NIST, inda ƙimar, misali, 0.4 ke nuna cewa maharin dole ne ya ƙwace aƙalla kashi 40% na jimillar zato masu yuwuwa don gano kalmar sirri.

Aikin yana cikin mahallin aikin "PHY2APP", yana mai da hankali kan samar da ƙaƙƙarfan kalmomin sirri masu daidaito don shirya na'urar Wi-Fi (yayin amfani da ka'idar ComPass) ta amfani da hanyoyin Tsaro na Layer na Jiki, yana nuna buƙatar ingantaccen ma'auni mai ƙarfi, mai iya faɗaɗawa.

2. Ma'anoni Daban-daban na Entropy

Entropy yana auna rashin tsari, bazuwar, ko rashin tabbas. Ma'anoni daban-daban suna amfani da su daban-daban ga ƙarfin kalmar sirri.

2.1 Mafi ƙarancin Entropy (Min-Entropy)

An ayyana shi azaman $H_{\infty} = -\log_2(\max(p_i))$, inda $p_i$ shine yuwuwar wani abu. Yana wakiltar mafi munin yanayi, yana auna wahalar zato mafi yuwuwar sakamako. Wannan shine tushen fitowar tsarin NIST.

2.2 Entropy na Shannon

An ayyana shi azaman $H_1 = -\sum_{i=1}^{N} p_i \log_2 p_i$. Yana ba da ma'auni na matsakaicin ƙimar bayanai amma ana sukar shi saboda rashin alaƙa da ainihin wahalar zato a cikin mahallin fashewar kalmar sirri, saboda yana yin watsi da tsawon kalmar sirri da dabarar da ta fi dacewa ga maharin.

2.3 Entropy na Hartley

An ayyana shi azaman $H_0 = \log_2 N$, yana auna girman rarraba kawai (girman haruffa), yana yin watsi da yuwuwar haruffa gaba ɗaya.

2.4 Entropy na Zato (Guessing Entropy)

An ayyana shi azaman $G = \sum_{i=1}^{N} p_i \cdot i$, inda ake jera zato bisa raguwar yuwuwar. Wannan yana auna adadin zato da ake tsammani da maharin da ya fi dacewa zai buƙata. Yana da alaƙa kai tsaye da lokacin fashewa na zahiri amma ba a daidaita shi ba.

3. Tsammanin Entropy

3.1 Ma'ana & Tsari

An gina Tsammanin Entropy akan ra'ayin Entropy na Zato amma an daidaita shi zuwa ma'auni [0, 1]. Babban ra'ayin shine a ƙididdige ƙarfin daga tsarin kalmar sirri ɗaya. Yana la'akari da rukunin haruffa masu rarrabuwa: ƙananan haruffa $L$ (|L|=26), manyan haruffa $U$ (26), lambobi $D$ (10), da alamomi $S$ (32), suna samar da jimillar sararin haruffa $K$ mai girman 94 don Turanci.

Duk da yake cikakken jadawalin lissafi don kalmar sirri ɗaya yana nufi amma ba a bayyana shi sarai ba a cikin ɓangaren da aka ba da shi, ma'aunin a zahiri yana daidaita ƙoƙarin da maharin da ya fi dacewa zai buƙata dangane da jimillar sararin bincike. Idan $G$ shine Entropy na Zato kuma $N$ shine jimillar kalmomin sirri masu yuwuwa (misali, $94^{\text{tsawon}}$ don cikakken sarari), za a iya danganta nau'i mai daidaitawa da ra'ayi zuwa $E \approx G / N_{eff}$, inda $N_{eff}$ shine girman sararin bincike mai tasiri yana la'akari da tsarin kalmar sirri.

3.2 Fassara & Ma'auni

Babban ƙirƙira shine ma'auninsa mai fassara. Ƙimar Tsammanin Entropy na $\alpha$ (inda $0 \le \alpha \le 1$) yana nufin maharin dole ne ya aiwatar da aƙalla ɓangaren $\alpha$ na jimillar zato da ake buƙata (a cikin tsari mafi kyau) don fashe kalmar sirri. Ƙimar 1 tana nuna bazuwar da ta dace inda maharin dole ne ya aiwatar da cikakken bincike na ƙarfi. Wannan yayi daidai da ma'auni mafi ƙarancin entropy na NIST, yana sauƙaƙe kwatantawa da yanke shawara ga masu tsara tsarin.

4. Cikakken Fahimta & Ra'ayi na Mai Bincike

Cikakken Fahimta: Reaz da Wunder ba kawai suna ba da shawarar wani ma'auni na entropy ba; suna ƙoƙarin magance wani muhimmin gibi na amfani da fassara a cikin injiniyan tsaro. Ainihin matsalar ba rashin ma'auni na rikitarwa ba ne, amma gogayya ta fahimta lokacin da kayan aikin haɗa-haɗa suka yi kururuwa "80 bit!" kuma NIST ta yi rada "0.7". Tsammanin Entropy mai aiki ne mai fassara, yana canza ƙarfin ɓoyayyen rubutu zuwa ƙimar haɗari mai yuwuwa mai aiki akan allon haɗin kai.

Tsarin Ma'ana: Hujjar tana da sauƙi mai kyau: 1) Ma'auni da suka wanzu suna rayuwa a duniyoyi daban-daban (bit vs. maki masu daidaitawa), suna haifar da rudani. 2) Entropy na Zato ($G$) yana kusa da gaskiyar maharin amma ba shi da iyaka. 3) Don haka, daidaita $G$ dangane da sararin bincike mai tasiri don ƙirƙirar maki 0-1 waɗanda ke daidaita kai tsaye da kashi na ƙoƙarin da ake buƙata na maharin. Wannan yana haɗa ka'idar (mafi ƙarancin entropy na NIST) da na aiki (aikin mai fashe kalmar sirri).

Ƙarfi & Kurakurai: Ƙarfinsa shine sauƙinsa mai kyau da fassara nan take—wani abin alheri ga masu tsara manufofi da masu gine-ginen tsarin. Duk da haka, shaidan yana cikin zato na rarraba. Daidaiton ma'aunin ya dogara sosai kan yin daidaiton samfurin yuwuwar rarraba $p_i$ na haruffa a cikin samfurin kalmar sirri ɗaya, wanda matsala ce ta ƙididdiga da aka sani da wahala. Ba kamar tsarin NIST wanda ke gwada dogon ragowar bit ba, amfani da wannan ga ɗan gajeren kalmar sirri mai haruffa 16 yana buƙatar ƙididdiga masu ƙarfi waɗanda zasu iya zama masu hankali ga son zuciya. Takardar, daga ɓangaren da aka ba da shi, ba ta cika bayyana wannan tsarin ƙididdiga don lamari ɗaya ba, wanda shine ƙafar Achilles.

Fahimta Mai Aiki: Ga ƙungiyoyin tsaro, ana iya haɗa wannan ma'auni a cikin API na ƙirƙirar kalmar sirri ko ƙarin kayan aikin Active Directory don ba da ra'ayi na ƙarfi na ainihi, mai fassara nan take ("Kalmar sirrinka tana buƙatar kashi 60% na zato don fashewa"). Ga masu bincike, mataki na gaba dole ne ya zama ingantaccen, ingantaccen tabbaci mai girma a kan kayan aikin fashewa na zahiri (kamar Hashcat ko John the Ripper) don daidaita samfurin. Shin Tsammanin Entropy na 0.8 da gaske yana nufin kashi 80% na sararin bincike? Wannan yana buƙatar hujja a kan samfuran AI na adawa, kama da yadda ake amfani da GAN don kai hari ga wasu fannonin tsaro. Ra'ayin yana da ban sha'awa, amma amfaninsa na aiki ya dogara ne akan ingantaccen tabbaci, bita da ƙwararru fiye da yanayin da aka sarrafa na kalmomin sirri da injina ke samarwa.

5. Cikakkun Bayanai na Fasaha & Tsarin Lissafi

Dangane da ra'ayoyin da aka zayyano, ana iya tsara Tsammanin Entropy $H_E$ don kalmar sirri da ra'ayi. Bari a zana kalmar sirri mai tsayi $l$ daga haruffa $\mathcal{A}$ tare da alaƙar rarraba yuwuwar kowane matsayi na haruffa (wanda za'a iya ƙididdige shi daga kalmar sirri kanta ko tarin bayanai).

Tsarin Yuwuwar Vector: Don jimillar sararin kalmar sirri mai girman $N = |\mathcal{A}|^l$, a ka'ida za'a iya jera duk kalmomin sirri masu yuwuwa bisa raguwar yuwuwar zaɓe (bisa ga samfurin samarwa).
Entropy na Zato: Adadin zato da ake tsammani don maharin da ya fi dacewa shine $G = \sum_{i=1}^{N} p_i \cdot i$, inda $p_i$ shine yuwuwar kalmar sirri ta $i$ mafi yuwuwa.
Daidaitawa: Matsakaicin yuwuwar $G$ don rarraba iri ɗaya shine $(N+1)/2$. Ana iya ayyana ma'auni mai daidaita ƙoƙari kamar haka: $$ H_E \approx \frac{2 \cdot G - 1}{N} $$ Wannan zai sanya rarraba iri ɗaya (cikakkiyar bazuwar) zuwa $H_E \to 1$ yayin da $N$ ya girma, da kuma kalmar sirri mai yiyuwa sosai (inda $G$ yake da ƙanƙanta) zuwa ƙima kusa da 0.
Ƙididdiga na Aiki: Don kalmar sirri ɗaya, dole ne a ƙididdige "matsayinta" ko jimillar yuwuwar duk kalmomin sirri da suka fi yuwuwa fiye da ita. Idan jimillar yuwuwar kalmar sirri har zuwa matsayinta shine $\alpha$, to $H_E \approx 1 - \alpha$. Wannan yayi daidai da bayanin takardar cewa ƙimar 0.4 tana nufin bincika kashi 40% na sarari.

Ingantaccen, ingantaccen algorithm don ƙididdige wannan daga samfurin ɗaya shine babban gudummawar fasaha da marubutan suka nuna.

6. Sakamakon Gwaji & Bayanin Ginshiƙi

Lura: Ba a ƙunshe da takamaiman sakamakon gwaji ko ginshiƙai a cikin ɓangaren PDF da aka ba da shi. Wannan shine bayanin da ya dogara da abin da binciken tabbaci na yau da kullun don irin wannan ma'auni zai haɗa.

Cikakken kimanta Tsammanin Entropy zai iya haɗa ginshiƙai masu zuwa:

Ginshiƙi 1: Taswira ta Kwatanta Ma'auni. Wannan ginshiƙi zai nuna kalmomin sirri akan gatura biyu: Gatura-X yana nuna ƙarfin bit na gargajiya (misali, $\log_2(94^l)$), kuma Gatura-Y yana nuna Tsammanin Entropy (0-1). Gajimare na maki zai bayyana alaƙa (ko rashinsa) tsakanin ma'auni biyu, yana nuna kalmomin sirri waɗanda suka daɗe (babban ƙarfin bit) amma masu yiyuwa (ƙananan Tsammanin Entropy).
Ginshiƙi 2: Lankwalin Juriya na Fashewa. Wannan zai nuna ainihin ɓangaren sararin binciken da maharin (ta amfani da kayan aiki kamar Hashcat tare da harin na ka'ida) dole ne ya bi don fashe kalmomin sirri da aka rarraba ta hanyar makin Tsammanin Entropy (misali, 0.0-0.1, 0.1-0.2...). Ma'auni mai kyau zai nuna layin diagonal cikakke inda ƙoƙarin da aka annabta (Entropy) ya yi daidai da ainihin ƙoƙari. Karkata daga diagonal yana nuna kuskuren ƙididdiga.
Ginshiƙi 3: Rarraba Makin. Tarihin tarihi yana nuna makin Tsammanin Entropy don nau'ikan kalmomin sirri daban-daban: waɗanda injina ke samarwa (misali, daga ka'idar ComPass), waɗanda mutum ya samar tare da ka'idoji, da waɗanda mutum ya samar ba tare da ka'idoji ba. Wannan zai nuna a zahiri ikon ma'aunin na rarrabe tsakanin hanyoyin samar da kalmar sirri.

Babban sakamakon da za'a tabbatar da shi shine da'awar: "Samun Tsammanin Entropy na wata ƙima, misali, 0.4 yana nufin cewa maharin dole ne ya ƙwace aƙalla kashi 40% na jimillar adadin zato." Wannan yana buƙatar simintin harin na zahiri.

7. Tsarin Bincike: Misalin Lamari

Yanayi: Kimanta kalmomin sirri biyu masu haruffa 12 don tsarin da ke amfani da sararin ASCII mai bugawa mai haruffa 94.

Kalmar Sirri A (Zaɓin Mutum): Summer2024!
Kalmar Sirri B (Samfurin Injina): k9$Lp@2W#r1Z

Ƙarfin Bit na Gargajiya: Dukansu suna da matsakaicin matsakaici ɗaya: $\log_2(94^{12}) \approx 78.7$ bit.

Binciken Tsammanin Entropy:

Kalmar Sirri A: Tsarin ya zama ruwan dare gama gari: kalmar ƙamus ("Summer"), shekara mai yiyuwa ("2024"), da alamar ƙarshe ta gama gari ("!"). Samfurin yuwuwa (kamar sarkar Markov da aka horar da ita akan kalmomin sirri da aka ɓoye) zai ba da babban yuwuwa ga wannan tsari. Matsayinsa a cikin jerin kalmomin sirri masu yuwuwa zai yi ƙasa sosai, ma'ana jimillar yuwuwar kalmomin sirri da suka fi yuwuwa ya yi yawa. Don haka, Tsammanin Entropynsa zai zama ƙasa (misali, 0.05-0.2), yana nuna maharin zai iya gano shi a cikin farkon kashi 5-20% na tsarin zato mai inganci.
Kalmar Sirri B: Ya bayyana bazuwar, ba tare da wani tsari bayyananne ba, yana haɗa rukunin haruffa a kowane matsayi. Samfurin yuwuwa zai ba da ƙima ƙasa sosai, kusan iri ɗaya ga wannan jeri na musamman. Matsayinsa zai yi yawa sosai (kusa da tsakiyar/ƙarshen jerin da aka jera). Don haka, Tsammanin Entropynsa zai zama babba (misali, 0.7-0.95), yana nuna maharin dole ne ya bincika mafi yawan sarari.

Wannan misalin yana nuna yadda Tsammanin Entropy ke ba da ƙarin ƙima da ƙima na haɗari na gaskiya fiye da ƙarfin bit iri ɗaya daga tsarin gargajiya.

8. Hangar Aikace-aikace & Hanyoyin Gaba

Aikace-aikace Nan Take:

Mitan Ƙarfin Kalmar Sirri na Ainihi: Haɗa Tsammanin Entropy cikin hanyoyin rajistar yanar gizo da aikace-aikace don ba masu amfani da alamar ƙarfi mai fassara, bisa kashi.
Ai da Ka'idojin Tsaro: Ƙungiyoyi za su iya saita ƙananan ƙofofin Tsammanin Entropy (misali, 0.6) maimakon ka'idojin rikitarwa kawai, suna ɗaure manufofi kai tsaye da ƙoƙarin fashewa da aka ƙididdige.
Binciken Tsarin Atomatik: Duba bayanan kalmar sirri da suka wanzu (waɗanda aka yi musu hash) don ƙididdige rarraba Tsammanin Entropy na gama gari da gano asusun da ke da raunin kalmar sirri mai mahimmanci.

Hanyoyin Bincike na Gaba:

Ƙididdiga Masu Ƙarfi na Samfurin Guda: Haɓakawa da kwatanta hanyoyin ƙididdiga (misali, ta amfani da samfuran harshe na jijiyoyi, samfuran n-gram, ko matatun Bloom) don daidai ƙididdige yuwuwar/matsayi na kalmar sirri ɗaya daga inda aka samo $H_E$.
Kimantawa na Adawa: Gwada ma'aunin a kan kayan aikin fashe kalmar sirri na zamani da samfuran AI (misali, PassGAN, daidaitawar tsarin Generative Adversarial Network don kalmomin sirri) don ganin ko ƙoƙarin da aka annabta ya yi daidai da ainihin lokutan fashewa.
Bayan Kalmomin Sirri: Amfani da ra'ayin "ɓangaren ƙoƙari" mai daidaitawa ga wasu sirri, kamar maɓallan ɓoyayyen rubutu (inda bit suke daidai) ko samfuran halittar mutum, don ƙirƙirar ma'auni mai ƙarfi guda ɗaya a cikin abubuwan tantancewa daban-daban.
Ƙoƙarin Daidaitawa: Ba da shawarar Tsammanin Entropy ko ka'idojinsa ga hukumomi kamar NIST don haɗawa a cikin sake dubawa na gaba na jagororin ainihin dijital (misali, SP 800-63B).

9. Nassoshi

Ma'aikatar Ilimi da Bincike ta Tarayyar Jamus (BMBF). Cikakkun bayanai game da tallafin aikin PHY2APP.
M. Dell'Amico, P. Michiardi, Y. Roudier, "Ƙarfin Kalmar Sirri: Bincike na Zahiri," a cikin Proceedings of IEEE INFOCOM, 2010. (Wakiltar bincike kan hanyoyin ƙarfin kalmar sirri).
Cibiyar Ƙididdiga da Fasaha ta Ƙasa (NIST). Tsarin Ƙididdiga na Entropy. [Kan layi]. Ana samuwa: https://github.com/usnistgov/entropy-estimation
NIST Special Publication 800-90B. Shawara don Tushen Entropy da ake amfani da su don Samar da Bit na Bazuwar.
J. Kelsey, K. A. McKay, M. Turan, "Samfuran Hasashe don Ƙididdiga Mafi ƙarancin Entropy," a cikin Proceedings of CHES, 2015.
K. Reaz, G. Wunder, "ComPass: Ka'ida don Tsaro da Amfani da Shirya Na'urar Wi-Fi," a cikin Proceedings of ACM WiSec, 2023. (An ɗauka daga mahallin).
C. E. Shannon, "Ka'idar Sadarwa ta Lissafi," The Bell System Technical Journal, vol. 27, pp. 379–423, 623–656, 1948.
R. V. L. Hartley, "Watsa Bayanai," The Bell System Technical Journal, vol. 7, no. 3, pp. 535–563, 1928.
J. Bonneau, "Kimiyyar Zato: Bincike kan Tarin Kalmomin Sirri Millyan 70 da aka ɓoye sunansu," a cikin Proceedings of IEEE Symposium on Security and Privacy, 2012.
J. L. Massey, "Zato da Entropy," a cikin Proceedings of IEEE International Symposium on Information Theory (ISIT), 1994.
C. Cachin, Ma'auni na Entropy da Tsaro mara Sharadi a cikin ɓoyayyen rubutu. Takardar PhD, ETH Zurich, 1997.
J. O. Pliam, "Bambanci tsakanin Aiki da Entropy a cikin ɓoyayyen rubutu," 1998. [Kan layi]. Ana samuwa: https://eprint.iacr.org/1998/024
B. Hitaj, P. Gasti, G. Ateniese, F. Perez-Cruz, "PassGAN: Hanyar Koyo mai zurfi don Zato Kalmar Sirri," a cikin Proceedings of ACNS, 2019. (Nassoshi na waje don kimantawar AI na adawa).