輕量級(jí)密碼教材

WG2——輕量級(jí)密碼算法目錄1. 安全隱私 21.1 安全 21.2 隱私 32. 分組密碼 32.1 AES 42.2 CLEFIA 52.3 DES 62.4 DESXL 72.5 HIGHT 72.6 KASUMI 82.7 mCrypton 92.8 PRESENT 102.9 SEA 112.10 XTEA 133. 輕量級(jí)協(xié)議 163.1 HB及其變體 163.2 HB協(xié)議 163.3 HB協(xié)議 173.4 對(duì)HB+的多種改進(jìn) 183.5 隨機(jī)HB及其變體 193.6 基于Rabin函數(shù)的協(xié)議 204. 近期安全成果 204.1 KATAN和KTANTAN 204.2 PRESENT算法 264.3 XTEA 29安全隱私在本節(jié)中,我們給出一個(gè)大綱中遇到的安全隱私需求系統(tǒng)，涉及低成本普及設(shè)備的有限計(jì)算和通信資源,RFID標(biāo)簽比較典型,并且這些需求的方式可以使用一個(gè)輕量級(jí)密碼協(xié)議來解決。我們考慮系統(tǒng)由兩個(gè)主要組件:?低成本設(shè)備有限計(jì)算和通信能力包括至少一個(gè)集成電路,例如低成本RFID標(biāo)簽或智能卡。基礎(chǔ)設(shè)施,即一個(gè)設(shè)備管理系統(tǒng)能夠與重量輕通信設(shè)備。對(duì)于一個(gè)RFID系統(tǒng),基礎(chǔ)設(shè)施由后臺(tái)系統(tǒng)連接到無線閱讀。這種系統(tǒng)的應(yīng)用特別廣泛:（例如）供給鏈的自動(dòng)化管理,票務(wù),電話卡,小額支付和訪問控制、自動(dòng)收費(fèi)、公共運(yùn)輸,防止假冒,寵物跟蹤、航空行李跟蹤、圖書館管理。設(shè)備用于解決各種不同的需要，他們的內(nèi)存和電源等特點(diǎn)，他們的通信和計(jì)算能力，還有這些所帶來的成本。一個(gè)值得注意的標(biāo)準(zhǔn)化活動(dòng)在這些文獻(xiàn)內(nèi)可以查找[36,40]。這種系統(tǒng)的一個(gè)共同特點(diǎn)是設(shè)備和基礎(chǔ)設(shè)施之間的通信協(xié)議必須允許基礎(chǔ)設(shè)施來識(shí)別設(shè)備。后來我們專注于與此協(xié)議相關(guān)的安全和隱私問題。因此我們不認(rèn)為相關(guān)的安全和隱私問題的信息存儲(chǔ)、交換和處理在基礎(chǔ)設(shè)施之內(nèi)。毫不奇怪,如此廣泛的應(yīng)用程序和物理特性,對(duì)這些系統(tǒng)的安全隱私需要相當(dāng)多樣化。(1)在安全隱私并不重要的問題上，一些最初的供應(yīng)鏈管理應(yīng)用程序使用RFID標(biāo)簽的標(biāo)簽僅僅是一個(gè)條形碼替代品，而不是交付給最終消費(fèi)者或使用“殺死”命令，在可以禁用之前交付給最終消費(fèi)者,越來越多的應(yīng)用程序的出現(xiàn),低成本設(shè)備和無線電通信功能輸入終端用戶的生活(如圖書館管理、自動(dòng)收費(fèi))導(dǎo)致越來越多的關(guān)注涉及他們隱私的潛在危害。令人擔(dān)心的是,通過低成本設(shè)備附加到她所攜帶的對(duì)象,一個(gè)人可能會(huì)離開電子追蹤她的動(dòng)作和行為,成為可追蹤的惡意方配備無線電設(shè)備（的對(duì)象）。

(2)應(yīng)用如票務(wù)或訪問控制,擁有低成本設(shè)備伴侶具體化了一些權(quán)利需要防止偽造或模擬合法設(shè)備,例如通過克隆合法設(shè)備或數(shù)據(jù)的回放之前通過一個(gè)合法的標(biāo)簽。為了解決這些安全需求,身份驗(yàn)證機(jī)制,允許系統(tǒng)證實(shí)的身份標(biāo)記是必需的。雖然很難協(xié)調(diào),后者的安全需要與前者的隱私需要經(jīng)常是聯(lián)合的,例如在售票的情況下,公共交通等等。根據(jù)是否合并沒有安全和隱私保護(hù)功能,還是只有安全特性,或是只有隱私保護(hù)功能,或者兩者兼有,輕量級(jí)協(xié)議允許基礎(chǔ)設(shè)施來確定低成本設(shè)備，大致可以分成四類,如表所示。這個(gè)表中使用的術(shù)語將在后續(xù)中進(jìn)行詳細(xì)的解釋。系統(tǒng)中的安全與隱私涉及普及設(shè)備現(xiàn)在已經(jīng)成為密碼學(xué)中一個(gè)非?；钴S的研究課題,并且合適的本原和協(xié)議的設(shè)計(jì)是輕量級(jí)加密領(lǐng)域的一個(gè)重大挑戰(zhàn)。安全身份驗(yàn)證,解決上述安全威脅(即防止合法設(shè)備的克隆或模擬),可能代表了大多數(shù)輕量級(jí)加密。利用主題下面的區(qū)別可以身份識(shí)別和身份驗(yàn)證:當(dāng)一個(gè)協(xié)議允許一個(gè)系統(tǒng)識(shí)別設(shè)備,但不能證實(shí)這身份,因此抵制克隆或模擬攻擊將被命名為一個(gè)鑒定協(xié)議,此協(xié)議允許系統(tǒng)識(shí)別設(shè)備和確證身份，將被命名為一個(gè)認(rèn)證協(xié)議或相當(dāng)于一個(gè)身份驗(yàn)證方案。如果一個(gè)認(rèn)證協(xié)議另外又確認(rèn)了設(shè)備，該設(shè)備對(duì)應(yīng)的協(xié)議是合法的,我們將稱之為相互認(rèn)證協(xié)議。高效的身份認(rèn)證解決方案正逐漸出現(xiàn),即使是最受限系統(tǒng)。第一個(gè)可能的方法是使用一個(gè)分組密碼在傳統(tǒng)的質(zhì)詢-響應(yīng)協(xié)議。為了考慮計(jì)算資源在某些設(shè)備(3000通用電氣，甚至更少，通常被認(rèn)為是作為一種復(fù)雜性上限為典型的低成本設(shè)備)的嚴(yán)重限制，專用的輕量級(jí)分組密碼已經(jīng)開發(fā)出來，例如DESXL,PRESENT,和KATAN[81,18,25]。這種專用的分組密碼代表另一種可選的標(biāo)準(zhǔn)密碼的輕量級(jí)實(shí)現(xiàn)諸如AES密碼[136]。一些有著非常低的硬件腳本的流密碼,例如Grainv1或Trivium[53,26]也有可能導(dǎo)致非常有效的身份驗(yàn)證解決方案。另一方面,一些具體的基于身份驗(yàn)證方案的流密碼現(xiàn)今已被提出。輕量級(jí)的認(rèn)證協(xié)議不是基于對(duì)稱元素,例如SQUASH[119]和HB系列RFID方案[63,46]，而是描繪了另一個(gè)有前景的研究項(xiàng)目,即使它保持著一個(gè)復(fù)雜的任務(wù)，到目前為止還是從這些家庭抵制部分密碼分析結(jié)果來確定實(shí)際情況，[77,44,43,105]。最后,CryptoGPS[48],非對(duì)稱身份驗(yàn)證方案要求極低的計(jì)算資源提供預(yù)先估計(jì)，輸出存儲(chǔ)在設(shè)備中的樣本名都反常的被證明為比大多數(shù)對(duì)稱方案更適合廉價(jià)設(shè)備。雖然身份驗(yàn)證和相互認(rèn)證代表著系統(tǒng)在實(shí)際中所需考慮的主要安全功能,可能對(duì)一些應(yīng)用程序來說，還需要考慮額外的安全特性,比如消息一體化(使用消息身份驗(yàn)證代碼或簽名方案)或數(shù)據(jù)加密(使用一個(gè)加密算法)。隱私隱私保護(hù)輕量級(jí)識(shí)別或驗(yàn)證協(xié)議在近年來也有很多研究。但是公平地說,這些仍然是一個(gè)不太成熟的領(lǐng)域，不僅僅是身份驗(yàn)證協(xié)議和設(shè)計(jì)現(xiàn)實(shí)的輕量級(jí)協(xié)議,考慮到約束裝置和系統(tǒng)方面仍然是一個(gè)非常具有挑戰(zhàn)性的問題。以下的開創(chuàng)性工作[60,62,6,33,131]的定義和主要的各種隱私的觀念的提出和相互鏈接已被探索。到目前為止，并沒有引入未被詳細(xì)定義的各種隱私觀念(只是提出了一個(gè)相當(dāng)全面的類型在[131])。值得一提的是，一個(gè)基本的要求在任何私人身份或認(rèn)證協(xié)議是為了防止被動(dòng)或主動(dòng)的攻擊者，能夠訪問跟蹤設(shè)備的通信接口，即確保匿名性和不可鏈接性交往的一個(gè)合法的設(shè)備。這個(gè)屬性，被一些創(chuàng)始者叫做弱隱私[131],很容易提供對(duì)稱設(shè)置,例如，通過使用一個(gè)輕量級(jí)分組密碼，在質(zhì)詢-響應(yīng)協(xié)議和所有注冊(cè)的關(guān)鍵系統(tǒng)設(shè)備中，從而避免傳輸設(shè)備在身份認(rèn)證前交換。更需要的隱私是財(cái)產(chǎn)隱私，這是出于這樣一個(gè)事實(shí)：對(duì)于很多輕量級(jí)設(shè)備來說，成本意味著將禁止任何物理干預(yù)阻力。除了之前的弱隱私需求，私人財(cái)產(chǎn)協(xié)議必須確保敵人能夠篡改設(shè)備時(shí)，仍無法鏈接數(shù)據(jù)設(shè)備，訪問任何之前她可能記錄的交換。很容易看到，前者基于分組密碼的簡(jiǎn)單示例的協(xié)議并不是財(cái)產(chǎn)協(xié)議。提供一些隱私，并且典型體現(xiàn)識(shí)別關(guān)系的協(xié)議是OSK方案[102,103]。該協(xié)議依賴于使用標(biāo)記的兩個(gè)單向散列函數(shù)。一個(gè)哈希函數(shù)在當(dāng)前狀態(tài)更新每個(gè)識(shí)別標(biāo)記,而另一個(gè)標(biāo)識(shí)值來自當(dāng)前的內(nèi)部狀態(tài)。隨后搜索識(shí)別價(jià)值收到讀者在散列鏈端相關(guān)系統(tǒng)中每個(gè)標(biāo)記。很多OSK方案將其轉(zhuǎn)化為私人認(rèn)證協(xié)議在[7]中被提出,從而使它能夠抵抗重放攻擊。密碼本的權(quán)衡允許原始方案和一些變體加快處理讀者的一端以一定的預(yù)先估計(jì)也在[8]中提出。然而有人注意到OSK協(xié)議及其驗(yàn)證變異容易受到拒絕服務(wù)攻擊(DoS),使設(shè)備系統(tǒng)失調(diào)。此外,DoS攻擊妥協(xié)提出這樣的隱私,是否成功就在于對(duì)手是否可以了解識(shí)別或鑒定交流有一個(gè)合法的她可以訪問的系統(tǒng)。最近提出一些替代選擇的OSK家族身份驗(yàn)證方案，基于廣闊的加密成分低于OSK的單向散列函數(shù)和提供安全特性,例如PFP[9]——這是使用偽隨機(jī)的數(shù)量生成器和一個(gè)散列的普遍的家庭函數(shù),O-FRAP[130]——這是使用一個(gè)輸入偽隨機(jī)函數(shù)擴(kuò)張,和pep[13]——這是依賴于使用IV的流密碼。分組密碼已經(jīng)掌握了DES,DESXL,HIGHT和SEA的數(shù)據(jù)計(jì)算，或者說，擁有100千兆的計(jì)算速度。注意，計(jì)算能力在不同的密碼算法不能比較的。AES由Rijndaed設(shè)計(jì)的這個(gè)分組密碼在2000年被NIST標(biāo)準(zhǔn)化為AdvancedEncryptionStandard（AES）。在此期間，AES的許多低消耗的變體中，AES-128減小到了3100GE。這些運(yùn)行結(jié)果表示AES-128在某些環(huán)境當(dāng)中可以作為安全輕量級(jí)密碼運(yùn)用。AES-128介紹AES沿襲了wide-trail的設(shè)計(jì)特點(diǎn)，包含一個(gè)秘鑰生成和聲明了更新轉(zhuǎn)換。接下來，我們主要介紹AES的一個(gè)變體，AES-128。需要更多的信息，參考AES的詳細(xì)介紹[99]。矩陣更新AES-128長(zhǎng)為128比特，由一個(gè)4*4的矩陣實(shí)現(xiàn)。AES用4輪置換和10輪迭代。非線性層替換字節(jié)（SB）用8比特的AES的S-盒表示每一個(gè)獨(dú)立的字節(jié)。循環(huán)的行移位(SR),j行左移j位。線性散列層列混合（MC）用一個(gè)MDS矩陣實(shí)現(xiàn)矩陣的列相乘。在第i輪，秘鑰加(AK)添加一個(gè)128比特的輪秘鑰Ki到AES矩陣中，第一輪K0秘秘鑰生成AES-128的秘鑰生成是從前面的輪秘鑰生成新的秘鑰，第一輪秘鑰128比特，第一輪的循環(huán)遞歸用XRD作用包含一個(gè)線性部分和一個(gè)非線性函數(shù)Fi每次循環(huán)一個(gè)字節(jié)，4個(gè)S-盒作為輸出，循環(huán)4解密于AES的解密，相反的輪變換用相反的次序進(jìn)行，秘鑰加自反和輪秘鑰計(jì)算用相反的次序。逆行變換向右循環(huán)，由于AES的S-盒基于GF（28）的逆運(yùn)算，只有仿射變換需要改變它的逆過程對(duì)反字節(jié)替換解密。而且逆列混合輕量級(jí)硬件運(yùn)行能耗低成本的AES-128的運(yùn)行中只有3400GE被發(fā)表。到目前為止，這是最小的AES運(yùn)行環(huán)境，包括加密，解密和秘鑰建立。運(yùn)行加密有1032個(gè)分組循環(huán)的明文。使用的技術(shù)是一個(gè)0.35米從飛利浦半導(dǎo)體CMOS式過程。運(yùn)用這項(xiàng)技術(shù)，混合分組頻率80兆赫茲，能提供9.9兆比特每秒的數(shù)據(jù)產(chǎn)量。電路也設(shè)置為低能耗和達(dá)到3.0毫安，100千赫茲和1.5伏。實(shí)現(xiàn)用8比特?cái)?shù)據(jù)路徑和一個(gè)S-盒，其中S-盒用于比特替換，逆比特替換以及秘鑰生成。S-盒是在邏輯電路下利用Canright的S-盒運(yùn)行的，是基于GF（28最近，不同的低成本AES運(yùn)算已經(jīng)公布，但是只有加密過程。在[74]中一個(gè)AES-128加密過程運(yùn)用一個(gè)標(biāo)準(zhǔn)胞電路在0.25微米的半導(dǎo)體加工技術(shù)已經(jīng)提高到870個(gè)分組3900GE。功耗小于20微瓦2.5v和100千赫。一個(gè)更快的實(shí)現(xiàn)已經(jīng)發(fā)表在[66]，有534個(gè)分組循環(huán)，運(yùn)用4070GE。他們已經(jīng)使用了0.13微米互補(bǔ)金屬氧化物半導(dǎo)體工藝技術(shù)臺(tái)積電和能耗23.83微瓦1.2v,500千赫。最小的AES實(shí)現(xiàn)到目前為止已發(fā)表在[51]用3100GE只使用3100循環(huán)

0.13微米CMOS技術(shù)進(jìn)行加密。在這8比特實(shí)現(xiàn)中,不同的AES輪轉(zhuǎn)換為不同的8比特并行執(zhí)行的數(shù)據(jù)/秘鑰。由于高度流水線方式的能耗相當(dāng)高37w/MHz1.2v。給出的最大時(shí)鐘頻率152MHz。注意,功耗不同過程的技術(shù)是比較困難的。密碼分析在過去的10年里，對(duì)AES-128的攻擊并沒有取得顯著進(jìn)展，最好的攻擊手段也只分析到10輪中的7輪。最好的攻擊方法是在2000年公布的7輪方。另外一個(gè)7輪攻擊。一年之后一個(gè)不可能的差分針對(duì)6輪密碼分析被放棄了。最近，公布了成熟的AES分析，他是關(guān)于公開秘鑰已知秘鑰和選擇秘鑰在7輪AES上的分析。這些攻擊努力體現(xiàn)AES的性質(zhì)但是沒有一個(gè)能夠恢復(fù)隨機(jī)選擇秘鑰。注意，就算是最新的AES-192和AES-256攻擊在相關(guān)秘鑰和HASH函數(shù)方面也不能應(yīng)用到AES-128上，因?yàn)檫@些分析方法需要更自由的秘鑰生成。CLEFIACLEFIA是索尼和Nagoya大學(xué)聯(lián)合設(shè)計(jì)的。和AES類似，也是有128位的分組長(zhǎng)度和三種不同的秘鑰長(zhǎng)度，分別是128,192和256字節(jié)。C運(yùn)用一個(gè)4叉樹和一個(gè)8叉樹形式加2個(gè)Feistel網(wǎng)，運(yùn)用秘鑰對(duì)每個(gè)分組加密18（128字節(jié)），22（192字節(jié)）或者26（256字節(jié)）輪。最佳實(shí)現(xiàn)結(jié)果C的設(shè)計(jì)者在論文中針對(duì)不同的秘鑰長(zhǎng)度提供了硬件運(yùn)行的參數(shù)。其他發(fā)表在[126]的運(yùn)行已經(jīng)普遍優(yōu)化。盡管他們已經(jīng)普遍達(dá)到了在每個(gè)分組的比率達(dá)到最高的頻率，但是他們的還是比[120]中的執(zhí)行要大。因此，在固定頻率10萬赫茲的前提下，他們的效率還是不好，在2.1桌面也沒有包括這些運(yùn)行。最好的密碼分析攻擊C的設(shè)計(jì)者解釋了怎樣對(duì)抗差分分析，線性分析，不可能差分分析，saturation，代數(shù)分析和秘鑰相關(guān)分析。其中最好的（imporsibledifferential）能夠攻擊含有128位秘鑰的C的10輪加密和含有192位秘鑰的C的11輪加密以及含有256位秘鑰的C的12輪加密。所有的攻擊需要超過2100個(gè)選擇明文，這根本是不可能的。時(shí)間復(fù)雜度對(duì)于192字節(jié)和256字節(jié)秘鑰來說，非常接近暴力破解，而內(nèi)存需求則分別為2121和2153個(gè)分組長(zhǎng)度。對(duì)于128字節(jié)秘鑰攻擊，只有2102個(gè)分組需要存儲(chǔ)并且只需要2102個(gè)減少的輪的評(píng)估值.這些新技術(shù)的改進(jìn)方案發(fā)布在[128，127，139]，但是由于十分復(fù)雜其中沒有一個(gè)可行。這些分析方法并沒有能夠分析出C的所有輪，因此并沒有對(duì)C造成威脅。2.2桌面總結(jié)了這些C其他方面CLEFIA被建議包含在未來的ISO/IEC29192-2標(biāo)準(zhǔn)在輕量級(jí)密碼分析中。-第二部分，分組密碼。DESDES它包含了以64字節(jié)為分組長(zhǎng)度的Feistel結(jié)構(gòu)網(wǎng)，和一個(gè)56字節(jié)長(zhǎng)的可行秘鑰，加密16輪。最佳實(shí)現(xiàn)結(jié)果自從Biham和Shamir首次公布了差分攻擊，在[12]，DES就被認(rèn)為理論上可攻破的。他們的攻擊需要247.2個(gè)可選擇明文和237.2個(gè)DESevalutions和占用很小的內(nèi)存。Matsui’s的線性密碼分析能夠比暴力攻擊更快地攻破DES[94]。他的攻擊有85%的可能性成功，并且需要243個(gè)已知明文，和2其他方面DES從1977年被NIST用于加密標(biāo)準(zhǔn)直到在2001年被AES取代。DESXLDESXL被et.al的領(lǐng)導(dǎo)者提出[82]，并且是基于DESL，DESL是DES的一個(gè)修改后的變體。DESL和DES很相似，除了層間替換不同，其中DES的八個(gè)S盒被改成了一個(gè)S盒替換八次。更進(jìn)一步，初始置換和它的逆（IP,IP-1）被取消了。額外DESXL還運(yùn)用秘鑰白化技術(shù)技術(shù)增加秘鑰最佳實(shí)現(xiàn)結(jié)果Pochmannet.al介紹了DESXL的輕量級(jí)硬件運(yùn)行結(jié)果在[109]中。他們的結(jié)構(gòu)中運(yùn)用了連續(xù)的數(shù)據(jù)路徑，并且新需要用144個(gè)時(shí)鐘加密一個(gè)數(shù)據(jù)分組。在180納米的技術(shù)前提下，他們的運(yùn)行需要2168個(gè)GE。表2.5列出了運(yùn)行結(jié)果。最好的密碼分析攻擊DESXL的作者解釋了怎樣對(duì)抗線性分析和差分分析以及Davies-Murphy攻擊[82]。更進(jìn)一步，基于S盒的2次和三次方程，他們提出代數(shù)分析并不會(huì)對(duì)DESXL造成很大的威脅。其他方面DESXL包含了一個(gè)自由e學(xué)習(xí)應(yīng)用CrypTool[37]。HIGHTHIGHT在2006年被Honget.al提出[55]。他是集合了分組長(zhǎng)64字節(jié)的Feistel網(wǎng)路架構(gòu)和128字節(jié)長(zhǎng)的秘鑰加密32輪。最好的運(yùn)行結(jié)果HIGHT的設(shè)計(jì)者公布了ASIC碼的加密運(yùn)算，其需要3048個(gè)GE[55]。它運(yùn)用了以輪為基礎(chǔ)的結(jié)構(gòu)，因此需要34個(gè)clock循環(huán)加密一個(gè)數(shù)據(jù)。Limetal.描述了HIGHT的一個(gè)更加緊湊的ASIC碼運(yùn)行也能實(shí)現(xiàn)加密的功能[89]。它需要34個(gè)clock通過優(yōu)化秘鑰表和控制邏輯運(yùn)算，這個(gè)部分減少到2608個(gè)GE（屋里單位）。表2.6總結(jié)了HIGHT的運(yùn)行結(jié)果。最好的密碼分析攻擊HIGHT的設(shè)計(jì)者解釋了怎樣抵抗差分分析，線性分析，截?cái)嗖罘址治?，不可能差分分析，飽和分析，高階差分，代數(shù)分析和變體的秘鑰相關(guān)分析[55]。他們最好的攻擊（不可能差分分析）能夠分析到18輪，但是需要246.8個(gè)可選擇明文和2109.2個(gè)賦值Lu能夠計(jì)算在HIGHT的25輪上運(yùn)用260個(gè)選擇明文和2126.78個(gè)求值的不可能差分攻擊[91]。在同一篇論文當(dāng)中，一個(gè)相關(guān)秘鑰矩陣和相關(guān)秘鑰差分攻擊能夠計(jì)算到HIGHT的26和28輪。前者需要251.2個(gè)可選擇明文和2120.41個(gè)加密次數(shù)，而后者需要260最近Ozenetal.公布了改進(jìn)的不可能差分分析攻擊在HTGHT的16輪，它需要261個(gè)可選擇明文和2119.53個(gè)加密次數(shù)以及2109字節(jié)的內(nèi)存[106]。他們也公布了31輪的相關(guān)秘鑰不可能差分攻擊,其中運(yùn)用了完全的代碼本和2117張etal.開發(fā)了一個(gè)新的17輪飽和區(qū)分器，計(jì)算saturation攻擊HIGTH減少到了22輪。[138]這個(gè)攻擊需要262.04個(gè)可選擇明文和2118.71個(gè)22輪計(jì)算次數(shù)。并沒有提供內(nèi)存復(fù)雜度。表2.7總結(jié)了這些對(duì)其他方面在南朝鮮，HIGHT被用作一個(gè)標(biāo)準(zhǔn)的加密算法（TTAS.KO-12.0040）[122]。最近正在討論把它加入ISO/IEC18033-3標(biāo)準(zhǔn)加密算法里。——第三部分:分組密碼。KASUMIKASUMI是一個(gè)擁有64字節(jié)分組和128字節(jié)秘鑰長(zhǎng)度的分組密碼。它是Matsui的分組密碼MISTY1的一個(gè)變體，關(guān)于加強(qiáng)數(shù)據(jù)加密的部分和一些輕量級(jí)秘鑰生成的部分。KASUMI有一個(gè)嵌入的結(jié)構(gòu)。它的循環(huán)結(jié)構(gòu)的最高水平是一個(gè)人包含32比特到32比特的函數(shù)的Feistel體系，而兩個(gè)低水平的運(yùn)用Feistel的變體體系，即Mistey體系，去構(gòu)造一個(gè)32比特到32比特的函數(shù)FO和16比特到16比特的函數(shù)FI。KASUMMI和兩個(gè)實(shí)現(xiàn)模型關(guān)于源于流密碼和MAC——UEA1(UMTSEncryptionAlgorithm)和UIA1(UMTSIntegrityAlgorithm)——被SGPP標(biāo)準(zhǔn)化用于第三代手機(jī)系統(tǒng)UMTS。一個(gè)也源自KASUMI并且和UEA1相同的流密碼也被采用，在A5/3名下，作為第二代手機(jī)系統(tǒng)的第三個(gè)標(biāo)準(zhǔn)化的加密算法。一個(gè)KASUMI最初的安全分析伴隨著它的設(shè)計(jì)一起公布，在[117]中可以找到。兩個(gè)最好的可選擇明文攻擊KASUMI的輪減少的版本在這個(gè)文件中都用到了不可能差分分析的性質(zhì)。他們攻破了KASUMI的變體的6輪，用了255（253.3）可選擇明文和2119（復(fù)雜度相當(dāng)于2100次加密）次簡(jiǎn)單運(yùn)算。迄今為止，對(duì)于KASUMI的輪減少變體，和Kuhn的在KASUMI得6輪的不可能差分攻擊一起，他們始終代表著最好的可選擇明文攻擊。許多在對(duì)KASUMI的分析取得的巨大進(jìn)步都在相關(guān)秘鑰攻擊的模型里。在這個(gè)模型里，假設(shè)密碼破譯者不僅實(shí)現(xiàn)加密和解密可選擇明文（密文）中的信息，在未知秘鑰條件下，而且在源于K的一個(gè)或多個(gè)附加秘鑰的條件下還能運(yùn)用一個(gè)被對(duì)方控制變換，例如：一個(gè)獨(dú)家新聞或者一個(gè)常量。當(dāng)[17]的攻擊能夠運(yùn)用兩個(gè)相關(guān)秘鑰攻擊用破KASUMI8輪中的6輪，更多最近的相關(guān)秘鑰分析能夠利用4個(gè)相關(guān)秘鑰攻擊全部的8輪比秘鑰的徹底研究更快。由于它的低復(fù)雜度，在[35]中的攻擊方法中，最近的一個(gè)叫做Dunkelmanetal.的三明治攻擊的分析方法能夠在兩個(gè)小時(shí)內(nèi)在個(gè)人電腦上模擬KASUMI。所有這些攻擊都得益于線性秘鑰生成。雖然有缺陷存在表明KASUMI不能作為一個(gè)理想的密碼，但是相關(guān)秘鑰攻擊并沒有在3GPP和mCrypton2005年Lim和Korkishko設(shè)計(jì)了mCrypton[87]，mCrypton是基于Crypton的。它是加密64比特長(zhǎng)的分組，并且提供了三種不同的秘鑰長(zhǎng)度：64比特，96比特和128比特。其中每一輪都包含一個(gè)替換層，一個(gè)列替換層和一個(gè)行列互換層以及一個(gè)秘鑰添加層。最佳實(shí)現(xiàn)結(jié)果設(shè)計(jì)者提供了一些運(yùn)行數(shù)據(jù)，反映的是mCrypton的一輪的結(jié)構(gòu)[87]。他們的結(jié)構(gòu)需要13個(gè)分組循環(huán)，不同的秘鑰長(zhǎng)度需要2420GE到2949GE不等的區(qū)域和一個(gè)只加密核。如果加入的解密算法，對(duì)每個(gè)秘鑰對(duì)應(yīng)需要的區(qū)域要擴(kuò)充40%。最好的密碼分析攻擊作者聲稱mCrypton能夠抵抗線性分析和差分攻擊[87]。他們指出類似于代數(shù)攻擊和相關(guān)秘鑰攻擊這樣的分析方法對(duì)于mCrypton來說和Crypton不一樣。然而cryption早在1999年就被公布出來了，針對(duì)它的分析方法也越來越成熟了。2009年，Park公布了關(guān)于mCrypton的安全分析[107]。他發(fā)現(xiàn)一個(gè)7輪的相關(guān)秘鑰矩陣特點(diǎn)，并運(yùn)用它去攻擊mCrypton的第8輪。本攻擊需要246個(gè)可選擇明文的數(shù)據(jù)復(fù)雜246mCrypton的8輪運(yùn)算的時(shí)間復(fù)雜度，并且需要5*248字節(jié)的內(nèi)存。PRESENTPRESENT是一個(gè)應(yīng)用于驅(qū)動(dòng)環(huán)境下的SPN分組密碼，例如RFID標(biāo)簽和網(wǎng)絡(luò)傳感器。在硬件上他被設(shè)計(jì)的特別緊湊，特別有競(jìng)爭(zhēng)力。PRESENT運(yùn)行64比特的測(cè)試分組，進(jìn)行31輪迭代和80比特或者128比特的秘鑰。Bogdanov設(shè)計(jì)了PRESENT并在2007年發(fā)布在SHES上[18]。PRESENT的每一整輪都包含了3個(gè)層次，按順序?qū)⑺麄兎譃椋好恳粚佣加幸粋€(gè)子秘鑰，一個(gè)由四個(gè)4比特的S盒構(gòu)成的S盒進(jìn)行16次線性變換的到一個(gè)中間密文，一個(gè)叫做P層的線性變換包括一個(gè)固定的比特置換。只有擁有輪子秘鑰xor層才是involution。因此，解密過程需要反向分析S盒和P層。經(jīng)過31輪迭代后悔輸出一個(gè)包含復(fù)雜的最后輪子秘鑰的變換。最佳的實(shí)現(xiàn)結(jié)果PRESENT的設(shè)計(jì)者只公布了在ASIC上的加密[18]。一個(gè)基于輪區(qū)域優(yōu)化的PREESENT-80的運(yùn)算需要1570GE和32個(gè)分組循環(huán)去實(shí)現(xiàn)一個(gè)單加密。一個(gè)低能耗的具有相似結(jié)構(gòu)的運(yùn)算交換區(qū)域需要1623GE。PRESENT-80需要32個(gè)分組循環(huán)和1886GE。Rolfesetal.發(fā)布了幾個(gè)關(guān)于RESENT的硬件實(shí)現(xiàn)[115]。運(yùn)用一個(gè)連續(xù)體系結(jié)構(gòu)的PRESENT-80只需要1075GE和547個(gè)分組循環(huán)。關(guān)于基于輪和連續(xù)硬件實(shí)現(xiàn)的PRESENT-128和對(duì)更多不同PRESENT的實(shí)現(xiàn)能在[110]里面找到。表2.11總結(jié)了PRESENT的運(yùn)行結(jié)果。最好的密碼分析攻擊表2.12總結(jié)了現(xiàn)行的最好的攻擊方法，該表按照秘鑰長(zhǎng)度和漸增輪的順序排表。PRESENT的設(shè)計(jì)者聲稱它能夠抵抗差分和線性密碼分析。他還解釋為什么截?cái)嗖罘止簦罘志€性攻擊,積分攻擊，瓶頸攻擊，代數(shù)攻擊，相關(guān)秘鑰攻擊和滑動(dòng)攻擊都不太有希望能夠分析出PRESENT。PRESENT公布后不久，王小云就發(fā)表了她的關(guān)于PRE-SENT的差分性質(zhì)的發(fā)現(xiàn)[133]。她指出，一個(gè)PRESENT的16輪逆對(duì)差分攻擊來說是可行的。特別的，利用264個(gè)可選擇明文和關(guān)于265比特的時(shí)間復(fù)雜度能夠捕捉到32比特的秘鑰，然后再用窮舉攻擊獲得剩下的48比特秘鑰，這種可能性高達(dá)0.999999939.進(jìn)一步，232個(gè)6比特的計(jì)算和224個(gè)哈希包是內(nèi)存需要的。這個(gè)攻擊的缺點(diǎn)是它需要一個(gè)對(duì)應(yīng)密碼本，也就是所有264個(gè)已知的明文需要對(duì)應(yīng)的密文。但是，如果所有的明文以及對(duì)應(yīng)的密文都知道了，那么也就不再需要知道秘鑰了，因?yàn)楣粽咭呀?jīng)能夠根據(jù)密文查到明文了。再者，攻擊只能攻擊31輪的16輪，所以PRESENT依然有很大的前景。在一個(gè)基于代數(shù)分析的小的模式的攻擊，作者分運(yùn)用5,6和7輪分析了PRESENT的變體。這個(gè)作者強(qiáng)調(diào)一個(gè)5輪的攻擊只需要80個(gè)可選擇明文，但是7,輪的分析卻需要224.3個(gè)可選擇明文，并且需要一個(gè)2100.1的時(shí)間復(fù)雜度和一個(gè)277字節(jié)的數(shù)據(jù)復(fù)雜度。更進(jìn)一步，作者聲明代數(shù)分析不能擴(kuò)展超過某一個(gè)點(diǎn)，因?yàn)闀r(shí)間復(fù)雜度隨增加一個(gè)新一類的統(tǒng)計(jì)學(xué)飽和攻擊被Collard和Standaerd提出，PRESENT正在被這個(gè)攻擊測(cè)試。它開發(fā)置換層的性質(zhì)，特別是第5,6,9和10個(gè)S盒輸出的16比特中的8比特都指向另外一個(gè)S盒。有兩個(gè)攻擊被建議去分裂PRESENT的16輪。其中一個(gè)需要236個(gè)可選擇明文，228的內(nèi)存存取和需要存儲(chǔ)216的計(jì)算值，而另外一個(gè)則需要至少233個(gè)可選擇明文和257的內(nèi)存存取和需要存取233的計(jì)算值。注意，作者在復(fù)雜度估計(jì)中添加了一個(gè)常量C，因?yàn)樵O(shè)置假設(shè)是否成立還不清楚。作者還推測(cè)這個(gè)攻擊的擴(kuò)張可能能夠分解PRE-SENT的24輪,在[1]中，三個(gè)運(yùn)用代數(shù)和差分技術(shù)的攻擊方法被提出。作者演示了實(shí)驗(yàn)結(jié)果，包括其中兩種攻擊方法在PRESENT-80的變體的16輪和PRESENT-128的17,18和19輪的運(yùn)用。所以的攻擊需要263個(gè)可選擇明文對(duì)和1G字節(jié)的RAM。他們對(duì)PRESENT-80-16的攻擊需要246CPU分組循環(huán)，對(duì)PRESEN-T-128的變體需要298到2Ohkuma研究弱密鑰和PRESENT的變體的線性加密的關(guān)系[104]。他聲稱32%的可能秘鑰是若秘鑰，因?yàn)槎嗦窂阶饔?，且使用這些弱密鑰就能使線性擴(kuò)張4輪成為可能。他對(duì)PRESENT的攻擊減少到24輪能夠恢復(fù)40比特的概率為0.95.他需要完全的24個(gè)秘鑰本和至少240個(gè)估計(jì)減少到24輪為暴力攻擊剩下的40比特的主密鑰創(chuàng)造條件。沒有提供時(shí)間和內(nèi)存復(fù)雜度的相關(guān)數(shù)據(jù)。最近，Choo在他發(fā)現(xiàn)的基礎(chǔ)上提出一個(gè)多維的線性攻擊減少到26輪，其成功的概率為0.95[64]。這些估計(jì)值被看做是低范圍的，因?yàn)橹豢紤]了線性路徑的相關(guān)性。兩個(gè)攻擊都需要整個(gè)密碼本或者是不少于262.4對(duì)已知明文和160億字節(jié)的RAM。時(shí)間復(fù)雜度為265，PRESENT的272個(gè)實(shí)現(xiàn)結(jié)果減少到25Nakaharaetal.介紹了線性外殼攻擊分析PRESENT減少到26輪[59]。他們發(fā)現(xiàn)，計(jì)算偏差來自于估計(jì)偏差，并隨著輪數(shù)的增加而增加。這就能夠使線性分析能夠利用整個(gè)密碼本和240內(nèi)存以及298.6個(gè)運(yùn)行結(jié)果來攻擊PRESENT的到目前為止已經(jīng)有各種各樣的攻擊應(yīng)用在減少PRESENT變體的輪上。表2.12表明，沒有一個(gè)攻擊能夠?qū)RESENT的所有輪造成威脅，盡管一些攻擊在PRESENT公布后相繼出現(xiàn)。其他方面PRESENT正在被討論應(yīng)用到未來的ISO/IEC19192-2標(biāo)準(zhǔn)的輕量級(jí)密碼上。SEASEA被Standaertetal.提出[123]。SEA基于Feis-tel結(jié)構(gòu)并遵循大范圍參數(shù)選擇：n：明文大小，秘鑰長(zhǎng)度；b：處理器規(guī)模；nb=n2b：每一個(gè)nr明文大小的唯一限制就是一個(gè)單詞的大小是6比特的倍數(shù)，即n=x·6b。SEAn,b用n比特的單詞長(zhǎng)度和b比特單詞長(zhǎng)度的處理器使一個(gè)變體降級(jí)。作者并沒有詳細(xì)說明了SEA的輪數(shù)。基于他們的安全分析，他們發(fā)現(xiàn)至少需要3n4+2·（nb+[最優(yōu)實(shí)現(xiàn)結(jié)果梅斯等人已經(jīng)在[93]中實(shí)現(xiàn)了多種不同的SEA?？紤]到兩個(gè)不同的架構(gòu):一個(gè)大小為n位的循環(huán)數(shù)據(jù)通路和大小為b位的序列化數(shù)據(jù)路徑。此外,協(xié)處理器架構(gòu)的提出，需要一個(gè)外部RAM(256位)明文和密文的存儲(chǔ)鍵/圓鍵和一些工作寄存器。然而,因?yàn)榇鎯?chǔ)需求通常是典型輕量級(jí)部分硬件最昂貴的一個(gè)實(shí)現(xiàn),與僅計(jì)算邏輯所需的數(shù)據(jù)路徑——為一個(gè)完整的加密區(qū)電流的核心相比，將是很不公平的。因此,對(duì)于只為了一個(gè)公平的比較,表2.13列出了從循環(huán)和電流的序列化的實(shí)現(xiàn)。FPGA對(duì)SEA的實(shí)現(xiàn)結(jié)果記錄在[124]中,但是沒有包括在這里,因?yàn)樗麄儾辉诒疚牡姆秶Ｗ顑?yōu)密碼分析攻擊SEA的設(shè)計(jì)者提供了線性安全評(píng)估和不同的攻擊及其擴(kuò)展(疊層、微分線性、多線性,回飛棒和矩形攻擊)。同時(shí)也對(duì)truncateddi?erential，無偏差，Slide，位加密和代數(shù)攻擊進(jìn)行了討論。作者得出這樣的結(jié)論:除了代數(shù)攻擊，沒有攻擊能對(duì)他們的設(shè)計(jì)造成威脅。基于他們的發(fā)現(xiàn),作者推導(dǎo)出了最小秩的公式(見上圖)。XTEA由Needham和Wheeler設(shè)計(jì)的分組密碼，是在1997年作為技術(shù)報(bào)告發(fā)表的。這個(gè)密碼是TEA密碼（也是由Needham和Wheeler設(shè)計(jì)的）的一些弱點(diǎn)被改進(jìn)后的結(jié)果，TEA曾被用于微軟的Xbox游戲機(jī)。XTEA是64輪Feistel密碼，它的分組大小為64位和密鑰大小為128位。TEA和XTEA都是在Linux內(nèi)核中實(shí)現(xiàn)的。大事年表：分組密碼TEA族1994年。TEA密碼(小加密算法)是64輪Feistel密碼，它使用64位的分組和一個(gè)128位的密鑰。它是由Wheeler和Needham設(shè)計(jì)的，并被發(fā)表在[134]上。它因設(shè)計(jì)簡(jiǎn)單而著稱，隨后，該密碼被深入研究，而關(guān)于它的攻擊也隨之而來。1996年。Kelsey等人證實(shí)了TEA有效的密鑰長(zhǎng)度是126位[70]。這個(gè)結(jié)果引發(fā)了對(duì)微軟Xbox游戲機(jī)的攻擊，在這款游戲機(jī)中TEA被當(dāng)做一個(gè)哈希函數(shù)來使用[125]。1997年。Kelsey，Schneier和Wagner構(gòu)造了一種關(guān)于TEA的相關(guān)密鑰攻擊，其中選擇的明文是，時(shí)間復(fù)雜度為。在這之后，Wheeler和Needham重新設(shè)計(jì)了TEA，得到了yieldBlockTEA和XTEA（eXtendedTEA）[135]。XTEA的分組大小、密鑰大小以及輪數(shù)都與TEA相同，BlockTEA滿足了可變分組的大小，因?yàn)樗鼘?duì)幾次迭代應(yīng)用了XTEA輪函數(shù)。TEA和XTEA是在Linux內(nèi)核中實(shí)現(xiàn)的。1998年。為了糾正BlockTEA的缺陷，Needham和Wheeler設(shè)計(jì)了修正后的BlockTEA或XXTEA，并發(fā)表在一個(gè)技術(shù)報(bào)告[135]上。這個(gè)密碼使用不平衡Feistel網(wǎng)絡(luò)和可變長(zhǎng)的消息。輪數(shù)是由分組大小決定的，但它至少是六。對(duì)BlockTEA完整的攻擊在[116]提出，其中也詳盡的寫出了XXTEA的一些弱點(diǎn)。2002-2010。在這段時(shí)期，對(duì)TEA族密碼的分析結(jié)果被發(fā)表。表2.14列出了對(duì)XTEA的攻擊及其復(fù)雜度。在[65]中，它展示了一種XTEA的超低能耗的實(shí)現(xiàn)方法，這可能比AES更適合資源匱乏的環(huán)境。注意，如果一個(gè)應(yīng)用程序每次都要求給小于128位的數(shù)據(jù)進(jìn)行加密，XTEA的較小的分組大小也十分有利。表2.14：對(duì)XTEA的鍵恢復(fù)攻擊，時(shí)間復(fù)雜度是平均值,如果在最初的論文中被明確說明,則給出成功概率的平均數(shù)（KP:已知明文、CP:選擇明文,RK:相關(guān)密鑰設(shè)置）。對(duì)XTEA的密鑰恢復(fù)攻擊對(duì)XTEA的鍵恢復(fù)攻擊的概況在表2.14中給出。XTEA的描述分組密碼XTEA的分組大小是64位，密鑰大小是128位。它使用64輪Feistel網(wǎng)絡(luò)（見圖2.1）。Feistel網(wǎng)絡(luò)(見圖2.2)的F-函數(shù)使用32位的輸入值x，產(chǎn)生一個(gè)32位的輸出值為：XTEA的128位的密鑰K被分為4個(gè)32位的子密鑰{K0，…，K3}。在每一輪中，根據(jù)密鑰的計(jì)劃表選出4個(gè)子密鑰其中之一。確定一個(gè)常數(shù),它來源于黃金比例。的不同倍數(shù)的兩位被用為每輪子密鑰的索引。第t輪中使用的32位子密鑰，其中是按照下列規(guī)則中選出的：XTEA第t輪的64位輸入值，包含兩個(gè)32位的部分（見圖2.1).第一輪,明文p被用作輸入值。第t+1輪的輸入是由第t輪的輸入根據(jù)下列公式遞歸地計(jì)算出的：其中。是根據(jù)(2.2)選出的。作為參考，我們也在表2.15列出了每輪中使用的子密鑰。XTEA的密文c是由第64輪之后獲得的兩個(gè)部分連接起來得到的：。最后，我們要注意到，在上面的描述中的一輪我們是指Feistel輪。這是不與XTEA的原始提案[135]中周期（cycle）這一術(shù)語混淆。一個(gè)周期相當(dāng)于兩個(gè)Feistel輪。因此XTEA有64輪或32個(gè)周期。硬件實(shí)現(xiàn)近期XTEA的硬件實(shí)現(xiàn)在[65]中給出。實(shí)現(xiàn)過程的細(xì)節(jié)在表2.16列出。輕量級(jí)協(xié)議HB及其變體射頻識(shí)別(RFID)是一種可以使RFID閱讀器進(jìn)行全自動(dòng)無線識(shí)別帶有RFID標(biāo)簽的對(duì)象的技術(shù)。最初，這項(xiàng)技術(shù)主要是應(yīng)用于托盤、紙箱以及其他一些產(chǎn)品的電子標(biāo)簽來實(shí)現(xiàn)供應(yīng)鏈的無縫監(jiān)管。今天,RFID技術(shù)被廣泛運(yùn)用到許多其他應(yīng)用程序上，包括動(dòng)物身份識(shí)別[4]，圖書館管理[96]，訪問控制[4,3,101,49]，電子票證[101,3,49]，電子護(hù)照[58]，甚至植入人類內(nèi)[61]。典型的RFID系統(tǒng)包括許多標(biāo)簽以及至少一個(gè)用于與標(biāo)簽通信的閱讀器。標(biāo)簽是一個(gè)與天線相連的集成電路，而這兩者通常都集成在一些附著在對(duì)象上用以識(shí)別的塑料卡或貼紙上。RFID設(shè)備是由閱讀器驅(qū)動(dòng)的，因此不能發(fā)起通信，而且內(nèi)存有限，沒有防偽，僅限于基本的加密計(jì)算。很簡(jiǎn)單的標(biāo)簽也包括成千上萬的電路門，因此編碼電路不允許復(fù)雜的計(jì)算。更復(fù)雜的標(biāo)簽還可以進(jìn)行對(duì)稱密鑰計(jì)算，而且非常復(fù)雜的標(biāo)簽可以進(jìn)行公鑰計(jì)算。通常，閱讀器的目的是從未知的標(biāo)簽中區(qū)分出合法的標(biāo)簽。在實(shí)踐中，RFID閱讀器通?？梢园踩兀幢Ｃ懿⒄J(rèn)證過地）訪問后臺(tái)數(shù)據(jù)庫，而后臺(tái)數(shù)據(jù)庫中包含了所有合法的標(biāo)簽上的信息。今天，RFID應(yīng)用的目的主要是識(shí)別或驗(yàn)證，其中包括訪問控制[61]和[129]防偽系統(tǒng)。一個(gè)RFID系統(tǒng)的用戶擁有一個(gè)或多個(gè)不建立光學(xué)或身體接觸就能詢問的標(biāo)簽。在訪問控制系統(tǒng)中，這提供了很大方便，因?yàn)橛脩舨恍枰獙⑺麄兊陌踩钆撇迦腴喿x器，而只要把它放在錢包或口袋里即可。我們也必須考慮RFID在身份驗(yàn)證和識(shí)別系統(tǒng)上的常見威脅。事實(shí)上，RFID系統(tǒng)的潛在威脅就是，敵人試圖模仿或克隆一個(gè)合法的標(biāo)簽進(jìn)行攻擊。我們?cè)噲D用一個(gè)認(rèn)證標(biāo)簽發(fā)行者創(chuàng)建一個(gè)標(biāo)簽，這是合法的。因此，必須提出合適的對(duì)策。然而，無線交互是難以察覺的，因此就可能會(huì)允許未經(jīng)授權(quán)的實(shí)體獲取用戶的相關(guān)數(shù)據(jù)，包括個(gè)人信息和位置。因此，除了對(duì)傳統(tǒng)身份驗(yàn)證系統(tǒng)的威脅，RFID還必須考慮與射頻接口相關(guān)的隱私和安全問題。對(duì)RFID系統(tǒng)最明顯的攻擊出自于未經(jīng)授權(quán)的實(shí)體。敵人必須獲得或模擬一個(gè)標(biāo)簽，并被一個(gè)真正的閱讀器所接受。為了達(dá)到這個(gè)目標(biāo),對(duì)手可能會(huì)執(zhí)行各種攻擊，包括中間人攻擊或重放攻擊，來撞擊底層身份驗(yàn)證協(xié)議，或者他可能試圖創(chuàng)建偽造標(biāo)簽或復(fù)制真實(shí)用戶的標(biāo)簽。文獻(xiàn)提出了幾個(gè)對(duì)RFID具有不同的作用的協(xié)議，從概念和理論的可行性以及結(jié)果的不可能性，到基于對(duì)專用硬件和計(jì)算機(jī)的假設(shè)得到實(shí)際結(jié)果。我們將把重點(diǎn)放在極其廉價(jià)的RFID標(biāo)簽上，它具有非常有限的計(jì)算和存儲(chǔ)能力。在這種配置下工作,研究人員專心致志地研究HB協(xié)議(最初由Hopper和Blum在[57]人類識(shí)別中提出)和一些變化。本章提出了本研究的最先進(jìn)的方向發(fā)展。HB協(xié)議一個(gè)非常受歡迎的輕量級(jí)協(xié)議——RFID認(rèn)證協(xié)議，也就是所謂的HB協(xié)議，由Hopper和Blum在[57]中提出。實(shí)際上，這個(gè)協(xié)議的目標(biāo)是使用最基本的操作，如矩陣乘法和異或算法，來執(zhí)行安全的人工識(shí)別（也就是說，所需的計(jì)算必須是可行的，甚至對(duì)人類而言也是）同時(shí)，還要滿足合理的安全觀念。事實(shí)上，RFID認(rèn)證協(xié)議HB使用所需的計(jì)算非常簡(jiǎn)單，應(yīng)用的硬件也十分廉價(jià)。HB協(xié)議的描述。一般地，參與者Alice和Bob共享一個(gè)k位秘密x，其中k是安全參數(shù)。首先，Alice發(fā)送給Bob一個(gè)k位隨機(jī)字符串a(chǎn)。Bob計(jì)算二進(jìn)制內(nèi)積，并將其發(fā)送給Alice，然后Alice通過驗(yàn)證校驗(yàn)位檢查Bob的身份。上述二輪協(xié)議重復(fù)r次是為了減少被欺騙的可能性，就是防止一位假冒的參與者僅僅通過猜測(cè)c的值，就成功騙過Alice。上面的第一次嘗試實(shí)際上只是一次微不足道的攻擊，不過的確，O(k)次有效的“挑戰(zhàn)—響應(yīng)”對(duì)可以使其他人通過使用高斯消元法計(jì)算出x。這促使了一個(gè)想法的產(chǎn)生，那就是，以某種恒定的概率發(fā)送錯(cuò)誤的值來干擾響應(yīng)，并要求當(dāng)錯(cuò)誤響應(yīng)小于等于次時(shí)，Alice接受身份驗(yàn)證。協(xié)議只需要AND和XOR運(yùn)算以及隨機(jī)數(shù)生成操作，這使得Bob在傳輸過程中不用緩存字符串a(chǎn)就可以直接一輪一輪地計(jì)算的。HB協(xié)議的安全性。HB協(xié)議的安全性與噪聲環(huán)境下的學(xué)習(xí)校驗(yàn)（簡(jiǎn)稱LPN）問題有關(guān)。3.2.1定義（LPN問題）設(shè)A是一個(gè)隨機(jī)的q×k二進(jìn)制矩陣，x是一個(gè)隨機(jī)k位向量，連續(xù)的噪音參數(shù),v是一個(gè)隨機(jī)的q位向量,且。給定A,以及,找到一個(gè)k位向量使得成立。LPN問題是NP-Hard[10]問題（NP指非確定性多項(xiàng)式，NP-Hard即NP難題），但是，照例，隨機(jī)情況下LPN問題的困難性仍不清楚。目前，解決隨機(jī)情況下LPN問題的解決方案運(yùn)行時(shí)間為[16]。假設(shè)隨機(jī)情況下的LPN問題是困難的，并限制對(duì)手只能被動(dòng)竊聽攻擊，這時(shí)，HB協(xié)議被證明是安全的。這意味著在Alice和Bob運(yùn)行協(xié)議的過程中，對(duì)手不允許插入消息。但是，這僅僅只是允許研究真實(shí)的雙方之間對(duì)話的文字記錄。只要在第二個(gè)階段，對(duì)手就可以與Alice運(yùn)行認(rèn)證協(xié)議，并有希望通過她的檢查。HB協(xié)議在[63]中，Juels和Weis提出了HB協(xié)議的一個(gè)變體，命名為HB+。HB+對(duì)敵人的主動(dòng)攻擊提供了安全。更準(zhǔn)確地說，HB+默認(rèn)對(duì)手偽裝成參與者與鮑勃交互信息，并試圖計(jì)算出Bob的一部分秘密x，這樣，偽裝的對(duì)手就可以在之后與Alice通信的過程中毫無阻礙。協(xié)議稍微有些復(fù)雜，不適用于人類，但對(duì)輕量級(jí)設(shè)備，如RFID標(biāo)簽，仍然非常有效。HB+協(xié)議的描述。Alice和Bob分享兩個(gè)k位字符串x和y。協(xié)議運(yùn)行開始，首先Bob發(fā)送給Alice一個(gè)k位隨機(jī)字符串b，然后Alice回應(yīng)一個(gè)k位隨機(jī)字符串a(chǎn)。最后，Bob計(jì)算出，其中隨機(jī)數(shù)v滿足時(shí)概率為，。如果，則Alice接受一輪。重復(fù)進(jìn)行以上3輪分組r次，若拒絕的輪數(shù)少于次，那么Alice最后的輸出結(jié)果為接受。HB+協(xié)議的安全性。HB+的安全性也是基于隨機(jī)情況下LPN問題的難度。正如上面提到的，對(duì)HB協(xié)議具體的改善在于允許對(duì)手偽裝成參與者與Bob通信來進(jìn)行主動(dòng)攻擊。不過，敵人在試圖偽裝成Bob之前仍然是不允許與Alice通信的。換句話說，不允許敵人在被檢測(cè)到之前與閱讀器發(fā)起對(duì)話。這種形式的主動(dòng)攻擊被稱為“偵查模式”，并應(yīng)用在防偽上。另一個(gè)更強(qiáng)的主動(dòng)攻擊，即允許敵人在試圖偽裝成Bob之前接近Alice，被稱為“預(yù)防”模式。在[47]中，Gilbert、Robshaw和Sibert證明，HB+在“預(yù)防”模式對(duì)于主動(dòng)攻擊來說是不安全的。更具體地說，他們展示了一種中間人攻擊的方法，即敵人偽裝成參與者篡改Alice發(fā)送給Bob的挑戰(zhàn)請(qǐng)求，如果這個(gè)篡改引起了身份驗(yàn)證的錯(cuò)誤，則中止協(xié)議。參數(shù)分析。Juels和Weis[63]基于他們對(duì)Blum，Kalai和Wasserman[16]的LPN學(xué)習(xí)算法的研究，提出了密鑰大小的下界。根據(jù)他們的分析，當(dāng)k=224，時(shí)，敵人運(yùn)行LPN學(xué)習(xí)算法破壞身份驗(yàn)證協(xié)議的屬性至少需要時(shí)間。隨后，F(xiàn)ossorier，Mihaljevic，Imai，Cui和Matsuura展示了一種改進(jìn)的LPN解決算法，將其在k=224，的情況下攻破HB+協(xié)議所需的時(shí)間減少到。Levieil和Fouque在[85]中將上述攻擊的復(fù)雜度減少到。Carrijo，Tonicelli，Imai和Nascimento在[28]中，Goebiewski，Majcher，Zagorski和Zawada在[50]中，都考慮了對(duì)于HB和HB+協(xié)議的其他的那些被動(dòng)攻擊。這些攻擊是通過使用較少的文字記錄進(jìn)行的，而且實(shí)際的攻擊可以用參數(shù)來表示，但是這完全不符合Juels和Weis在[63]中的建議。并行和并發(fā)的HB和HB+協(xié)議的安全性。乙肝和乙肝+協(xié)議的一個(gè)主要限制就是輪數(shù)的復(fù)雜度取決于所需的安全性。這是由于基本協(xié)議的連續(xù)迭代以及一些不得不面對(duì)的棘手問題而產(chǎn)生的，而這些棘手問題是為了證明當(dāng)?shù)遣⑿袌?zhí)行時(shí)上述兩個(gè)協(xié)議的安全性的。HB和HB+協(xié)議實(shí)際應(yīng)用的一個(gè)重要結(jié)果是由Katz，Shin[67]給出的。他們表明HB和HB+的基本2輪和3輪分組在并發(fā)和并行模式下，實(shí)際上是安全的，他們?nèi)匀患僭O(shè)LPN問題在隨機(jī)的情況下是很難的。這意味著人們可以安全地實(shí)現(xiàn)并行模式下基本分組的r次順序執(zhí)行，從而分別使得2和3輪協(xié)議獲得了令人滿意的安全性。這個(gè)改進(jìn)的分析是基于Regev在[113]中給出的結(jié)果，他在其中表明，LPN問題的難度說明了某一分布的偽隨機(jī)性。這是利用獲得也更簡(jiǎn)潔易懂的證據(jù)。Katz和Shin工作的限制[67]就是他們的分析要求。Katz和Smith隨后的一篇論文[69]展示了一個(gè)更為嚴(yán)謹(jǐn)?shù)姆治觥试S使用任何滿足的。對(duì)于進(jìn)一步的細(xì)節(jié),請(qǐng)參閱[68]。對(duì)HB+的多種改進(jìn)HB+協(xié)議對(duì)于中間人攻擊的不安全性(即在“預(yù)防”模式下)開啟的挑戰(zhàn)會(huì)話獲得更安全的變化，也可以成功地使用在應(yīng)用程序，其中這樣的攻擊是適用的。PUF-HB。Hammouri和Sunar[52]提出了結(jié)合身體不可克隆的特征與HB協(xié)議來獲得協(xié)議，這種協(xié)議至少與HB+的安全性相同。此外,最終的協(xié)議也可以成功防止一些對(duì)HB+的中間人攻擊，但沒有提供證據(jù)說明該協(xié)議可以防止一般的中間人攻擊。此外，使用PUFs提高了對(duì)標(biāo)簽的硬件需求(從而增加了制造的成本)，不過，這也限制了可能的應(yīng)用。Trusted-HB+。Bringer和Chabanne在[23]中建議對(duì)HB+協(xié)議最終的身份驗(yàn)證信息增加使用*-balanced散列函數(shù)[78]，以證明溝通的完整性。由此產(chǎn)生的協(xié)議稱為Trusted-HB+。與[63]中的分析類似，這份協(xié)議被宣稱為，在使用參數(shù)的實(shí)踐中是安全的。然而，F(xiàn)rumkin和Shamir在[41]展示了Trusted-HB+的幾個(gè)弱點(diǎn)，以及結(jié)合不同攻擊方式，提出了可以在時(shí)間內(nèi)打破Trusted-HB+協(xié)議的主動(dòng)攻擊者和在時(shí)間內(nèi)打破Trusted-HB+協(xié)議的被動(dòng)攻擊者HB++，HB*和HB-MP。Bringer，Chabanne和Dottax提出HB++——HB+協(xié)議的一個(gè)變種，它需要普遍的散列函數(shù)，位旋轉(zhuǎn)操作和小序列置換，從而使得HB+向使用更先進(jìn)的硬件的方向發(fā)展，這與HB+的目標(biāo)截然相反。隨后跟進(jìn)的協(xié)議——Piramuthu[108]提出HB++的另一個(gè)變體——也同樣存在相同的限制。更多的HB+變體被提出，其中，Duc和Kim在[34]中提出了HB*，Munilla和Peinado提出了HB-MP。然而，Gilbert，Robshaw和Seurin在[45]中展示了所有的變體都是不安全的。HB-MP的一個(gè)變體——被稱為HB-MP+,在[84]中被Leng,Mayes和Markantonakis證明對(duì)中間人攻擊具有更好的安全性隨機(jī)HB及其變體在上述一系列試圖改進(jìn)HB+的論文之后，Gilbert、Robshaw和Seurin在[46]中提出了一種新的協(xié)議，稱為RANDOM-HB#。它展示了對(duì)HB+協(xié)議的一個(gè)清晰的改進(jìn)。首先，在檢測(cè)模型中被證明安全的，與HB+的安全性證明相同。然而，除此之外RANDOM-HB#的確具有能抵抗[47]中的中間人攻擊的安全特性。RANDOM-HB#包含HB+的m并行迭代，因此秘密可以被認(rèn)為是一對(duì)二進(jìn)制隨機(jī)矩陣。核實(shí)步驟主要是比較m比特的向量與，如果錯(cuò)位的數(shù)目少于，其中閥值，，那么就接受這個(gè)秘密。除了它在檢測(cè)模型中的安全性，RANDOM-HB#的直接改進(jìn)HB+的主要特征，是其在被稱為GRS-MIM-model的中間人模型中的安全性。在這個(gè)模型中，攻擊者可以觀察到所有的標(biāo)簽和閱讀器之間的通信，也可以修改閱讀器發(fā)送給標(biāo)簽的信息。在這第一階段后，攻擊者試圖模仿標(biāo)簽與閱讀器運(yùn)行協(xié)議。因?yàn)镠B+在這個(gè)模型中是不安全的，RANDOM-HB#顯然是在協(xié)議抵抗主動(dòng)攻擊的全面安全性方面邁進(jìn)了一步。有趣的是，RANDOM-HB#的分析并沒有顯示LPN問題的直接減少。對(duì)于檢測(cè)模型下安全性的證明，該計(jì)劃的安全性已經(jīng)減少到MHB難題，正如在[63]中提到的，MHB本質(zhì)上就是一個(gè)與LPN難題有關(guān)的HB元組難題。之后，Canetti、Halevi和Steiner[24]對(duì)非獨(dú)立問題的研究結(jié)果就被應(yīng)用到將MHB問題的安全性與HB難題，甚至是LPN問題聯(lián)系起來。在GRS-model中，通過將其減少到檢測(cè)模型的安全性的方法，RANDOM-HB#被證明是安全的。除了上述所有良好的特性外，RANDOM-HB#有一個(gè)缺點(diǎn)：矩陣的使用增加了標(biāo)簽存儲(chǔ)要求，也就是說，在需求方面，它明顯差于HB+。為了解決這個(gè)限制，Gilbert、Robshaw和Seurin[46]提出了另外一個(gè)協(xié)議，也被稱為HB#。這個(gè)協(xié)議使用了兩個(gè)隨機(jī)二進(jìn)制Toeplitz矩陣[78]，因?yàn)檫@樣的矩陣可以通過只使用位存儲(chǔ)，而不是位，這明顯改善了存儲(chǔ)的需求。然而，這樣的改進(jìn)也引入了一個(gè)缺點(diǎn)。事實(shí)上,為了證明安全檢測(cè)和GRS-mim模型下的額安全性，LPN問題是不夠的了。因此，提出了一個(gè)新的臨時(shí)的假設(shè)——這個(gè)猜想就是當(dāng)使用Toeplitz矩陣時(shí)，上面所討論的MHB難題是困難的。RANDOM-HB#和HB+抵抗更一般的中間人攻擊的可能的安全性在中[46]和[105]被提及，Ouafi、Overbeck和Vaudenay展示了一種普遍又實(shí)用的中間人攻擊方式，打破了RANDOM-HB#、HB+和所有之前的類HB協(xié)議的安全性。這種攻擊的主要思想在于混合了主動(dòng)攻擊和被動(dòng)攻擊。事實(shí)上，該攻擊通過竊聽另一個(gè)會(huì)話的信息獲得價(jià)值，來修改會(huì)話消息。最后，在[86]中，Li、Gong和Qin提出了一個(gè)新的名為HB-C—的類HB協(xié)議，它自稱是對(duì)HB+的存儲(chǔ)和安全方面進(jìn)行了改進(jìn)。然而，這個(gè)證明只是基于一個(gè)新的猜想。不僅如此，他們還提出了一種新的貌似可以防止[105]中攻擊的噪音模式。最終的協(xié)議被命名為HB-CM，也是基于另一個(gè)臨時(shí)的猜想。結(jié)論安全的輕量級(jí)協(xié)議的認(rèn)證是一項(xiàng)非常有挑戰(zhàn)性的工作，已經(jīng)成為了近期密碼學(xué)的中心研究課題。它在提出新的provably-secure協(xié)議方向和打破基于錯(cuò)誤猜想提出的協(xié)議方向都做出了一些貢獻(xiàn)。本章討論的最先進(jìn)的協(xié)議顯示了目前在不同現(xiàn)實(shí)環(huán)境下允許RFID使用極其廉價(jià)標(biāo)簽方面取得的一系列進(jìn)步。獲得有效的方案仍然存在困難，也就是說，對(duì)一般主動(dòng)攻擊的安全性仍然是一個(gè)有趣的、開放的問題。基于Rabin函數(shù)的協(xié)議在[118]中Shamir提出了SQUASH，平方哈希函數(shù)的簡(jiǎn)稱，該函數(shù)是針對(duì)在高度受限的設(shè)備中，比如RFID標(biāo)簽上的質(zhì)詢-響應(yīng)消息認(rèn)證碼應(yīng)用程序。SQUASH使用Rabin公鑰加密函數(shù)[112]，m為使用密鑰n加密的消息（其中公開的模數(shù)n為至少兩個(gè)未知素?cái)?shù)之積）。相比之下，現(xiàn)有的協(xié)議都是基于LPN問題的，比如方案中HB系列：Hopper和Blum在[57]中提出的變種，包括HB+[63]、HB++[22]和HB-MP[98]。在[77]中，Ouafi和Vaudenay提出了一種對(duì)SQUASH-0攻擊方式，并在[118]中提出了一個(gè)版本。它使用了混合功能，該功能擴(kuò)大了密鑰的異或位和使用線性反饋移位寄存器的挑戰(zhàn)信息位數(shù)。對(duì)SQUASH-0的攻擊使用作為模數(shù)，并且使用1024選擇挑戰(zhàn)信息進(jìn)行密鑰恢復(fù)攻擊。結(jié)論是提出的SQUASH-0被打破，并且如果因式分解很困難，那么SQUASH的安全性聲稱是錯(cuò)誤的。近期安全成果在這一章，我們將通過對(duì)2010年1月26-27日在魯汶的召開的SYMLAB輕量級(jí)算法研究會(huì)議所得出的成果,提供一些關(guān)于KTANTAN[25],PRESENT[18]和XTEA[135]的某些評(píng)價(jià)。這些結(jié)果關(guān)注工作進(jìn)展,一些文章在準(zhǔn)備中或者在審查中。這次在魯汶召開的會(huì)議的參與者是AndreyBogdanov,KotaIdeguchi,SebastiaanIndesteege,OzgulKu_cuk,ChristianRechberger,VincentRijmen,KyojiShibutani。KATAN和KTANTAN差分密碼分析。通過自動(dòng)搜索，工作[25]包含KATAN或者KTANTAN一個(gè)更全面的微分分析屬性。不過,搜索微分軌跡與迭代結(jié)構(gòu)(開始和結(jié)束相同的差異)可能是很有趣的。在一開始,我們研究它是否存在短迭代軌跡。更先進(jìn)的方法可以包括一個(gè)對(duì)更多可能的軌跡的搜索，它基于相鄰輪之間數(shù)據(jù)的強(qiáng)依賴性,因此,潛在地增加了存在這種通道的可能性。在[2]中,通過代數(shù)分析，KTANTAN32的最好的微分特性[25]由42輪已經(jīng)被延長(zhǎng)到71輪,因?yàn)槊艽a允許簡(jiǎn)單的代數(shù)表示相對(duì)小數(shù)量的輪。相關(guān)密鑰的差分密碼分析方法。

KATAN的密鑰表所描述的線性代碼是72和84之間的最小距離,這是我們已經(jīng)驗(yàn)證的一個(gè)屬性。然而,我們注意到降低版本(例如一半密碼)最低重量要低得多,這可能在聯(lián)合攻擊上是可利用的。工作[25]表明如果擴(kuò)展的子密鑰重量差異超過80,那就是保證任何位KATAN32加密的概率微分最多達(dá)到2-32.我們還發(fā)現(xiàn),本地碰撞概率達(dá)到0.5是可能的。未來的工作將嘗試方法[111]，探索是否可以建造位加密差異,這可能由許多本地碰撞組成。但是要注意,絕大多數(shù)潛在的關(guān)于KATAN/KTANTAN的應(yīng)用,以及任何其他輕量級(jí)密碼,在實(shí)踐中位加密攻擊不太可能是一個(gè)主要的想法。線性密碼分析——相鄰時(shí)鐘的相關(guān)性。在KATAN48中,每一輪包括兩個(gè)反饋函數(shù)——fa和fb的應(yīng)用程序。兩個(gè)應(yīng)用程序的函數(shù)使用相同的密鑰。因此,如果能使其他輸入fa和fb的兩個(gè)時(shí)鐘是相等的,所以輸出也將相等,無論密鑰如何。在KATAN64,同樣的密鑰每輪使用三次。然而,事實(shí)證明在相對(duì)簡(jiǎn)單的輪數(shù)里保持這樣的完全相等，這是不可能的。這種方法可以被視為線性密碼分析的一個(gè)特例。當(dāng)考慮線性近似,包含相同密鑰的兩個(gè)線性組合可以組合在一起這是消除相關(guān)性的關(guān)鍵。因?yàn)閼?yīng)用于KATAN的非線性函數(shù)都是AND函數(shù),這種函數(shù)是結(jié)果有偏的,所以它不可能在許多輪中成功地導(dǎo)出線性近似。設(shè)計(jì)師們規(guī)定了一些對(duì)抗線性密碼分析的KATAN的阻力的邊界狀態(tài)。然而,目前還不清楚怎樣獲得這些邊界。嘗試和否定這些邊界可能是值得的。尋找線性近似。使用自動(dòng)化技術(shù)尋找良好的線性近似是最好的成果。幾種方法可能是有用的,包括基于線性和差分密碼分析之間技術(shù),結(jié)合從編碼理論衍生出來的技術(shù)。另一種方法是將密碼劃分成一個(gè)個(gè)包含小輪數(shù)的詞塊,可以將一個(gè)完整的代數(shù)描述寫入這些詞塊中,方便建立良好的線性近似。然后,這樣的近似鏈接在一起,中間通過一個(gè)輕量級(jí)的線性模式選擇來覆蓋更大的輪的數(shù)量,即使是32位版本的密碼不允許一個(gè)詳盡的搜索。代數(shù)屬性。KATAN/KTANTAN中的安全分析設(shè)計(jì)論文[25]指出,對(duì)KATAN32經(jīng)過160輪計(jì)算之后，每一個(gè)內(nèi)部狀態(tài)的程度可以達(dá)到最大程度的明文位。但是,這在眾多單項(xiàng)的分布方面仍然存在問題。即使達(dá)到最大程度,單項(xiàng)分布仍有可能不隨機(jī)。Aumasson觀察[5],KATAN32僅在55輪之后才能達(dá)到程度20，只有在87輪之后才能達(dá)到最大程度。正如4.1節(jié)中解釋的,相同的密鑰使用兩倍的響應(yīng)時(shí)間。對(duì)KATAN48來說。KATAN64,允許取消可能出現(xiàn)導(dǎo)致“失蹤”單項(xiàng)曾幫工的表達(dá)式。這種結(jié)構(gòu)有助于洞察開發(fā)多維數(shù)據(jù)集攻擊減少了許許多多的的版本。結(jié)構(gòu)屬性：我們發(fā)現(xiàn)了一個(gè)一般的的結(jié)構(gòu)屬性：KATAN0(0)=KTANTAN0(0)=0。也就是說,零密鑰映射零明文為零密文。這是足夠的,以免推薦指定的應(yīng)用程序版本的密碼以及構(gòu)建基于分組密碼散列函數(shù)直接擴(kuò)展。此外,探索輕量級(jí)密鑰擴(kuò)散到輕量級(jí)明文的速度有多快以及結(jié)合其他攻擊是很有趣的。密鑰表把80位的密鑰分成16片，每片5位。在每輪中、ka和kb來自同一密鑰片。這兩個(gè)輪密鑰是由選擇密鑰片中其中之一個(gè)密鑰產(chǎn)生的。像MD5消息擴(kuò)展,但并不是所有的關(guān)鍵部分經(jīng)常被同樣的復(fù)制。由此可見密鑰表是線性的。在25%的輪中,ka和kb是相同的一個(gè)副本的片。除此之外,這一事實(shí)可以支持密鑰猜測(cè)為擴(kuò)展各種猜測(cè)攻擊看來,并不是所有的用戶提供的80位密鑰是第一批80位擴(kuò)展密鑰。短的分組長(zhǎng)度。KATAN/KTANTAN促進(jìn)密碼分析的屬性之一是有許多完全指定的有非常小的塊的版本,例如,32或48位的。這使得一個(gè)做計(jì)算的實(shí)驗(yàn)分析混合密鑰的置換結(jié)構(gòu)成為可能。例如,我們可以先應(yīng)用各種統(tǒng)計(jì)測(cè)試顯示排列的出軌行為。更復(fù)雜的技術(shù)可能包括置換的內(nèi)部結(jié)構(gòu)排列。有兩個(gè)不同大小的寄存器非線性相互傳輸。假設(shè)這種建結(jié)構(gòu)就像另一個(gè)設(shè)置復(fù)雜的兩個(gè)寄存器替換為一個(gè)大的寄存器的非線性更新。我們也可以研究L1,L2寄存器之間的結(jié)構(gòu)關(guān)系。KATAN位加密的密碼分析Reduced-Round的不同版本：這部分是基于deguchi和KyojiShibutani.一些注釋：一個(gè)函數(shù)來更新一個(gè)內(nèi)部狀態(tài)的LFSR兩個(gè)時(shí)鐘。KeyUpdate():一個(gè)函數(shù)通過兩個(gè)時(shí)鐘來更新一個(gè)LFSR的內(nèi)部狀態(tài)。KS(K)[r]:K密鑰的密鑰表中的第r個(gè)密鑰。R:減少的輪的數(shù)量:X：更新每輪內(nèi)部消息值的時(shí)鐘數(shù)量。當(dāng)KATAN-32,48,64時(shí)，x分別等于1;2;3.密碼分析的結(jié)果。我們?cè)谶@個(gè)報(bào)告中研究KATAN的安全位加密設(shè)置。我們的結(jié)果顯示在表4.1中。算法類型輪數(shù)數(shù)據(jù)時(shí)間mem.KATAN-32related-keydistinguisher58972222θ(1)θ(1)related-keykey-recoveryKATAN-48related-keydistinguisher46662222θ(1)θ(1)related-keykey-recoveryKATAN-64related-keydistinguisher46552222θ(1)θ(1)related-keykey-recoveryKATAN’-32related-keydistinguisher741052222θ(1)θ(1)related-keykey-recoveryKATAN’-48related-keydistinguisher60802222θ(1)θ(1)related-keykey-recoveryKATAN’-64related-keydistinguisher56672222θ(1)θ(1)related-keykey-recovery在表4.1中,KATAN’-ns是KATAN的變體，它跟原始的KATAN相比，使用其他計(jì)數(shù)器。這些都是在4.1節(jié)。觀察。KATAN的密鑰表是LFSR的一個(gè)輸出序列，它被一個(gè)80位長(zhǎng)度的密鑰初始化。給定一個(gè)密鑰K,我們可以準(zhǔn)備一個(gè)密鑰K’，它的密鑰表通過p輪變換：KS(K)[r+2p]=KS(K’)[r].特別地,K’可以被準(zhǔn)備為，K’=KeyUpdatep(K);(4.1)KeyUpdate(.):f0;{0,1——>{0,1;這是一個(gè)函數(shù)，用來由兩個(gè)時(shí)鐘更新LFSR的內(nèi)部狀態(tài)。(KATAN的密鑰表每一輪被兩次計(jì)時(shí))。相關(guān)密鑰分析。我們的分析是由相關(guān)密鑰設(shè)置來完成的。一個(gè)敵人可以訪問兩個(gè)加密神諭,一個(gè)是伴隨密鑰K，另一個(gè)是伴隨K’=KeyUpdatep(K)。他的目標(biāo)是建立一對(duì)消息(P;P’),P是用密鑰K加密的,P’是用密鑰K’加密的;P的一個(gè)內(nèi)部消息值在(r+P)輪前等于P’在第r輪前的值。（r=1,2,3…R-p）。我們用Sr(Sr’)表示第r輪前的內(nèi)部消息值P(P’)。如果和區(qū)別為零,下一輪的區(qū)別只來自常量值的差異。區(qū)分和密鑰恢復(fù)（Key-Recovering）算法。在這里,我們?yōu)镵ATAN的減少輪版本展示區(qū)分和密鑰恢復(fù)算法。在圖4.1中描述的算法的概述。步驟1從加密神諭中（用密鑰K），對(duì)手被給出個(gè)明密對(duì)。步驟2用密鑰K加密的前P輪中，對(duì)于每一對(duì)明密對(duì)()和子密鑰k，敵人在第p輪之后計(jì)算一個(gè)內(nèi)部消息值,用表示，并且用查詢加密神諭的值。他獲得一個(gè)密文，與是一致的。步驟3用密鑰加密的最后P輪中，對(duì)于每一和子密鑰,對(duì)手在第(R-p)輪之后計(jì)算一個(gè)內(nèi)部狀態(tài)信息值，用表示。如果他發(fā)現(xiàn)一個(gè)內(nèi)部狀態(tài)信息值=，他就認(rèn)為是一對(duì)正確的子密鑰對(duì)。步驟4的對(duì)手詳盡的搜索其余的密鑰，其余密鑰還有(80–4*p)比特的長(zhǎng)度。上述算法的成功概率來自于當(dāng)子密鑰正確時(shí)內(nèi)部消息值等于用和的加密過程的概率。后者概率取決于用密鑰和密鑰加密產(chǎn)生的恒量之間的漢明距離，后者是由p輪下滑。假設(shè)內(nèi)部消息值是隨機(jī)的，恒量的每1比特差異都有的概率相互抵銷。因此，兩個(gè)恒量之間的漢明距離為d時(shí)，上面的概率就達(dá)到了。在這個(gè)算法中，敵人獲得個(gè)內(nèi)部狀態(tài)信息值（為了獲取正確的子密鑰）。因?yàn)榈仁?成立是建立在概率的基礎(chǔ)上的，所以如果大于或等于，那么就存在一個(gè)，以更高的概率存在。在另一方面，敵人獲得個(gè)（為了正確的子密鑰）。對(duì)于正確的子密鑰，等式=應(yīng)該是以概率成立的。所以，如果<，它就被當(dāng)成一個(gè)密鑰流區(qū)分器使用。我們?cè)O(shè)置。復(fù)雜性對(duì)于步驟1，數(shù)據(jù)復(fù)雜性是個(gè)明密對(duì)，時(shí)間復(fù)雜性是加密計(jì)算次。對(duì)于步驟2，數(shù)據(jù)復(fù)雜性最多是，時(shí)間復(fù)雜性也至多是。對(duì)于步驟3，時(shí)間復(fù)雜性至多大約是。對(duì)于步驟4，時(shí)間復(fù)雜性是。因此，算法的數(shù)據(jù)復(fù)雜性大約是，時(shí)間復(fù)雜性大約是（，）。僅僅對(duì)于區(qū)分器來說，我們不必完成第四步。所以，數(shù)據(jù)復(fù)雜性大約是，時(shí)間復(fù)雜性是（，）。對(duì)于KATAN-32來說，能被安裝的算法的最長(zhǎng)輪數(shù)是R=57，這時(shí)候參數(shù)p和d的取值為p=1；d=27.因此，數(shù)據(jù)復(fù)雜性是，時(shí)間復(fù)雜性也是。對(duì)于KATAN-48和KATAN-64也是如此，我們計(jì)算出算法的參量并且在表4.1列出最優(yōu)參量值。密鑰恢復(fù)的擴(kuò)大對(duì)于密鑰恢復(fù)，上述算法是精確的。在這個(gè)修正本里，第三步和第四步是改變了的。第3’步：用密鑰加密的最后P輪中，對(duì)于每一和子密鑰,對(duì)手在第(R-p)輪之后計(jì)算一個(gè)內(nèi)部狀態(tài)信息值，用表示。如果他發(fā)現(xiàn)一個(gè)內(nèi)部狀態(tài)信息值=，他就用子密鑰添加一個(gè)代表正確候選的標(biāo)志。第4’步:對(duì)于每一個(gè)正確候選的子密鑰，敵人詳細(xì)地計(jì)算剩余密鑰，剩余密鑰長(zhǎng)度(80-4*p)比特長(zhǎng)度。如果這種修正是可以應(yīng)用的，那么為了使得算法成功的概率更高，漢明距離的約束變成了xd<b。原因如下。如果xd<b,那么在在步驟中，正確的子密鑰被作為一個(gè)正確的候選選中的概率比其他不正確的個(gè)子密鑰高。這意味著正確的子密鑰將被作為候選在步驟中選出來，不正確的子密鑰則不會(huì)。因此,窮舉搜索剩余密鑰比特這種算法比暴力搜索整個(gè)密鑰要更有效率。對(duì)于步驟來說,時(shí)間復(fù)雜度是。第步的時(shí)間復(fù)雜度是。因此,算法的數(shù)據(jù)復(fù)雜度大約是，時(shí)間復(fù)雜度大約是max（，，）。通過計(jì)算常量值之間的漢明距離,KATAN-32得出的最好的結(jié)果是,d=31,p=22和R=97。數(shù)據(jù)復(fù)雜度是，時(shí)間復(fù)雜度是。對(duì)于KATAN-48和KATAN–64也是如此,我們研究算法的參數(shù)并且在表4.1中列出了最好的參數(shù)。選擇明文還是已知明文?在步驟1中,沒有要求明文優(yōu)先，所以不必選擇。另一方面,在步驟2中,明文要求是那些步驟1中的明文被輪函數(shù)轉(zhuǎn)換之后所得到的明文所以必須要求選擇。從這個(gè)意義上講,該算法需要選擇明文設(shè)置。然而,如果步驟2明文要求的數(shù)量是,那么選擇明文還是已知明文就沒有區(qū)別了，可以說算法在已知明文設(shè)置下工作。區(qū)分和密鑰覆蓋算法:減少數(shù)據(jù)復(fù)雜度的版本我們按如下步驟計(jì)算前面算法的數(shù)據(jù)復(fù)雜度:步驟1對(duì)手從用密鑰K的加密神諭中獲得個(gè)明密對(duì)，明文的集合用表示，對(duì)前p輪的所有子密鑰都有：到是一個(gè)雙射映射，是在步驟2中使用的明文集合。步驟2對(duì)手在使用密鑰K的加密神諭中查詢，獲得一個(gè)一致的密文。因?yàn)榈谝徊街械囊粋€(gè)明文映射到中的一個(gè)元素，。他用表示這種一致。第三步對(duì)最后p輪用密鑰加密的最后p輪的每一個(gè)和子密鑰，對(duì)手在輪后計(jì)算一個(gè)內(nèi)部狀態(tài)信息值，用表示，這是通過對(duì)的部分解密得出的。如果他發(fā)現(xiàn)一個(gè)內(nèi)部狀態(tài)信息價(jià)值,使得成立,那么他用子密鑰添加一個(gè)標(biāo)志代表一個(gè)正確的候選。步驟4正確候選的每一個(gè)子密鑰,對(duì)手都窮舉計(jì)算剩余密鑰，剩余密鑰長(zhǎng)度為比特。下面步驟是精確的。在第2步,我們只要求獲得個(gè)明密對(duì)。如果d<b,正確的子密鑰被選中作為步驟3中一個(gè)正確的候選的概率比其他不正確的子密鑰被選中的概率高。這意味著正確的子密鑰被選中作為步驟3的候選，一些不正確的子密鑰則不能被選中。因此,窮舉搜索剩余密鑰比特這種算法比暴力搜索整個(gè)密鑰要更有效率。KATAN算法的變體的分析在本節(jié)中,我們運(yùn)用前面的論點(diǎn)研究KATAN算法的一些變體。這些變體使用其他m序列(8位LFSRs)計(jì)算常量的值。這改變兩個(gè)相關(guān)密鑰加密的漢明距離,所以我們的分析也是被影響的。結(jié)果如表4.1所示,最低完全性的變體被列出來。一個(gè)正在建設(shè)中[20]。PRESENT算法本節(jié)概述了對(duì)PRESENT可能的攻擊(或者改善現(xiàn)有的攻擊)。盡管很多關(guān)于收集實(shí)驗(yàn)數(shù)據(jù)的問題被提出來，這次會(huì)議的主要結(jié)果還是列出實(shí)驗(yàn)的工作。會(huì)議參與者:C_elineBlondeau,BaudoinCollard,Beno^_tG_erard,GregorLeander,WilliMeier,Mar__aNaya-Plasencia,SvetlaNikova,Fran_cois-Xavier，Standaert,ElmarTischhauser,DenizTozandKeremVarici.線性密碼分析和弱密鑰我們討論了SAC2009論文[104]統(tǒng)計(jì)方法識(shí)別密鑰空間的一小部分和多重路徑對(duì)線性殼的影響。雖然被認(rèn)為是一個(gè)創(chuàng)新的想法,但這種方法也不是建設(shè)性的,所以對(duì)于輪數(shù)比較少的情況來說（12到14輪對(duì)于實(shí)際確認(rèn)來說是可操作的），獲得實(shí)驗(yàn)證據(jù)這會(huì)是挺好的。更為普遍的是,問題是在PRESENT的密鑰表中是否有一些有用的東西去開發(fā)，來獲得那些弱密鑰的詳細(xì)特征。統(tǒng)計(jì)飽和攻擊大部分時(shí)間是花在討論攻擊[30]和證明理論適應(yīng)性的實(shí)驗(yàn)設(shè)計(jì)思路。為了有更少數(shù)量的變體應(yīng)用于窮舉搜索,基于80比特密鑰的小型版本被定義了出來。這些密碼仍然需要一個(gè)80比特的密鑰和比特的變量時(shí)鐘長(zhǎng)度。這個(gè)密碼是通過選擇n=16來獲得的，這和FULLPRESENT是一樣的。對(duì)于密鑰表來說，兩個(gè)附加的版本（所有的密鑰完全相同，所有的論密鑰uniform是隨機(jī)的而且是獨(dú)立的），獲得密鑰表的洞察力的影響。鏈接到多維線性密碼分析。在對(duì)這種攻擊的討論期間，一個(gè)主要問題被提出來，這就是如何關(guān)聯(lián)對(duì)多維線性密碼分析的統(tǒng)計(jì)飽和攻擊設(shè)置,多維線性密碼分析是由Hermelin,Cho和Nyberg在文獻(xiàn)【54】中提出來的。Gregor建議采取如下的觀點(diǎn)[80]。在多維線