密码学系列之:Argon2加密算法详解
发布网友
发布时间：2024-09-07 05:04
共1个回答
热心网友
时间：2024-09-14 13:32
Argon2是一个密钥推导函数，在2015年7月被选为密码哈希大赛的冠军，它由卢森堡大学的AlexBiryukov、DanielDinu和DmitryKhovratovich设计，Argon2的实现通常是以CreativeCommonsCC0许可（即公共领域）或ApacheLicense2.0发布，并提供了三个相关版本，分别是Argon2d，Argon2i和Argon2id。
本文将会讨论一下Argon2的原理和使用。
密钥推导函数keyderivationfunction在密码学中，密钥推导函数(KDF)是一种密码学哈希函数，它使用伪随机函数从一个秘密值(如主密钥、密码或口令)中推导出一个或多个密钥。KDF可用于将密钥拉伸成更长的密钥，或获得所需格式的密钥，例如将Diffie-Hellman密钥交换的结果转换为用于AES的对称密钥。
PasswordHashingCompetition密码学虽然是研究密码的，但是其加密算法是越公开越好，只有公开才能去检视该算法的好坏，只有经过大家的彻底研究，才能够让该算法得以在业界使用和传播。
最出名的密码算法大赛肯定是由NIST在2001年为了指定标准的AES算法举办的大赛，该大赛的目的寻找最新的加密算法来替代老的DES算法。在这次大赛中，涌现了许多优秀的算法，包括CAST-256,CRYPTON,DEAL,DFC,E2,FROG,HPC,LOKI97,MAGENTA,MARS,RC6,Rijndael,SAFER+,Serpent,和Twofish等。最终Rijndael算法被选为最终的AES算法实现。
同样的PHC也是一个这样的算法比赛，和NIST举办的算法比赛不同的是，这是一个非官方的，由密码学家们组织的比赛。它是在由Jean-PhilippeAumasson于2012年秋季发起。
2013年第一季度，发布了征集意见书的通知，到2014年3月31日截止日期，共收到24份意见书。2014年12月，确定了9个入围名单。2015年7月，宣布Argon2为优胜者。
Argon2算法Argon2的设计很简单，旨在实现最高的内存填充率和对多个计算单元的有效利用，同时还能提供对tradeoffattacks的防御（通过利用处理器的缓存和内存）。
Argon2有三个变种。Argon2i、Argon2d和Argon2id。Argon2d速度更快，并且使用数据依赖的内存访问方式，这使得它对GPU破解攻击有很强的抵抗力，适合没有side-channeltimingattacks威胁的应用（例如加密货币）。
Argon2i则使用数据无关的内存访问，这对于密码哈希和基于密码的密钥推导算法来说是首选，其特点是速度较慢，因为它在内存上运行了更多的处理逻辑，以防止tradeoffattacks。
Argon2id是Argon2i和Argon2d的混合体，采用数据依赖型和数据独立型内存访问相结合的方式，从而可以同时抵御side-channeltimingattacks和GPU破解攻击的能力。
Argon2的输入参数Argon2有两类输入参数，分别是primaryinputs和secondaryinputs。
primaryinputs包括要加密的消息P和nonceS，分别代表password和salt。
P的长度是0到232-1字节，S的长度是8到232-1字节（如果是做密码hash，推荐16字节）。
之所以叫做primaryinputs，是因为这两个参数是必须输入的。
剩下的参数叫做secondaryinputs，他们包括：
并行程度p，表示同时可以有多少独立的计算链同时运行，取值是1到224-1。
Tag长度τ，长度从4到232-1字节。‘
内存大小m,单位是兆，值取8p到232-1。
迭代器的个数t，提升运行速度。取值1到232-1。
版本号v，一个字节，取值0x13。
安全值K，长度是0到232-1字节。
附加数据X，长度是0到232-1字节。
Argon2的类型，0代表Argon2d，1代表Argon2i，2代表Argon2id。
这些输入可以用下面的代码来表示：
Inputs:password(P):Bytes(0..232-1)Password(ormessage)tobehashedsalt(S):Bytes(8..232-1)Salt(16bytesrecommendedforpasswordhashing)parallelism(p):Number(1..224-1)Degreeofparallelism(i.e.numberofthreads)tagLength(T):Number(4..232-1)DesirednumberofreturnedbytesmemorySizeKB(m):Number(8p..232-1)Amountofmemory(inkibibytes)touseiterations(t):Number(1..232-1)Numberofiterationstoperformversion(v):Number(0x13)Thecurrentversionis0x13(19decimal)key(K):Bytes(0..232-1)Optionalkey(Errata:PDFsays0..32bytes,RFCsays0..232bytes)associatedData(X):Bytes(0..232-1)OptionalarbitraryextradatahashType(y):Number(0=Argon2d,1=Argon2i,2=Argon2id)Output:tag:Bytes(tagLength)Theresultinggeneratedbytes,tagLengthbyteslong处理流程我们先来看一下非并行的Argon2的算法流程：
非并行的Argon2是最简单的。
上图中G表示的是一个压缩函数，接收两个1024byte的输入，输出一个1024byte。
i表示的是执行的步数，上面的φ(i)就是输入，取自内存空间。
作为一个memory-hard的算法，一个很重要的工作就是构建初始内存。接下来，我们看一下如何构建初始内存空间。
首先，我们需要构建H0，这是一个64-byte的block值，通过H0，可以去构建更多的block。计算H0的公式如下：
H0=H(p,τ,m,t,v,y,?P?,P,?S?,S,?K?,K,?X?,X)
它是前面我们提到的输入参数的H函数。H0的大小是64byte。
看下H0的代码生成：
Generateinitial64-byteblockH0.Alltheinputparametersareconcatenatedandinputasasourceofadditionalentropy.Errata:RFCsaysH0is64-bits;PDFsaysH0is64-bytes.Errata:RFCsaystheHashisH^,thePDFsaysit's?(butdoesn'tdocumentwhat?is).It'sactuallyBlake2b.Variablelengthitemsareprependedwiththeirlengthas32-bitlittle-endianintegers.buffer←parallelism∥tagLength∥memorySizeKB∥iterations∥version∥hashType∥Length(password)∥Password∥Length(salt)∥salt∥Length(key)∥key∥Length(associatedData)∥associatedDataH0←Blake2b(buffer,64)//defaulthashsizeofBlake2bis64-bytes对于输入参数并行程度p来说，需要将内存分成一个内存矩阵B[i][j],它是一个p行的矩阵。
计算矩阵B的值：
其中H′是一个基于H的变长hash算法。
我们给一下这个算法的实现：
FunctionHash(message,digestSize)Inputs:message:Bytes(0..232-1)MessagetobehasheddigestSize:Integer(1..232)DesirednumberofbytestobereturnedOutput:digest:Bytes(digestSize)Theresultinggeneratedbytes,digestSizebyteslongHashisavariable-lengthhashfunction,builtusingBlake2b,capableofgeneratingdigestsupto232bytes.IftherequesteddigestSizeis64-bytesorlower,thenweuseBlake2bdirectlyif(digestSize<=64)thenreturnBlake2b(digestSize∥message,digestSize)//concatenate32-bitlittleendiandigestSizewiththemessagebytesFordesiredhashesover64-bytes(e.g.1024bytesforArgon2blocks),weuseBlake2btogeneratetwicethenumberofneeded64-byteblocks,andthenonlyuse32-bytesfromeachblockCalculatethenumberofwholeblocks(knowingwe'reonlygoingtouse32-bytesfromeach)r←Ceil(digestSize/32)-1;Generaterwholeblocks.InitialblockisgeneratedfrommessageV1←Blake2b(digestSize∥message,64);Subsequentblocksaregeneratedfrompreviousblocksfori←2tordoVi←Blake2b(Vi-1,64)Generatethefinal(possiblypartial)blockpartialBytesNeeded←digestSize–32*r;Vr+1←Blake2b(Vr,partialBytesNeeded)Concatenatethefirst32-bytesofeachblockVi(exceptthepossiblypartiallastblock,whichwetakethewholething)LetAirepresentthelower32-bytesofblockVireturnA1∥A2∥...∥Ar∥Vr+1如果我们的迭代次数多于一次，也就是说t>1,我们这样计算下一次迭代的B：
Bt[i][0]=G(Bt?1[i][q?1],B[i′][j′])⊕Bt?1[i][0]B^{t}[i][0]=G\left(B^{t-1}[i][q-1],B\left[i^{\prime}\right]\left[j^{\prime}\right]\right)\oplusB^{t-1}[i][0]Bt[i][0]=G(Bt?1[i][q?1],B[i′][j′])⊕Bt?1[i][0]
Bt[i][j]=G(Bt[i][j?1],B[i′][j′])⊕Bt?1[i][j]B^{t}[i][j]=G\left(B^{t}[i][j-1],B\left[i^{\prime}\right]\left[j^{\prime}\right]\right)\oplusB^{t-1}[i][j]Bt[i][j]=G(Bt[i][j?1],B[i′][j′])⊕Bt?1[i][j]
最终遍历T次之后，我们得到最终的B：
Bfinal=BT[0][q?1]⊕BT[1][q?1]⊕?⊕BT[p?1][q?1]B_{\text{final}}=B^{T}[0][q-1]\oplusB^{T}[1][q-1]\oplus\cdots\oplusB^{T}[p-1][q-1]Bfinal=BT[0][q?1]⊕BT[1][q?1]⊕?⊕BT[p?1][q?1]
最后得到输出：
Tag←H′(Bfinal)\mathrm{Tag}\leftarrowH^{\prime}\left(B_{\text{final}}\right)Tag←H′(Bfinal)
这段逻辑也可以用代码来表示：
Calculatenumberof1KBblocksbyroundingdownmemorySizeKBtothenearestmultipleof4*parallelismkibibytesblockCount←Floor(memorySizeKB,4*parallelism)Allocatetwo-dimensionalarrayof1KiBblocks(parallelismrowsxcolumnCountcolumns)columnCount←blockCount/parallelism;//IntheRFC,columnCountisreferredtoasqComputethefirstandsecondblock(i.e.columnzeroandone)ofeachlane(i.e.row)fori←0toparallelism-1doforeachrowBi[0]←Hash(H0∥0∥i,1024)//Generatea1024-bytedigestBi[1]←Hash(H0∥1∥i,1024)//Generatea1024-bytedigestComputeremainingcolumnsofeachlanefori←0toparallelism-1do//foreachrowforj←2tocolumnCount-1do//foreachsubsequentcolumn//i'andj'indexesdependifit'sArgon2i,Argon2d,orArgon2id(Seesection3.4)i′,j′←GetBlockIndexes(i,j)//theGetBlockIndexesfunctionisnotdefinedBi[j]=G(Bi[j-1],Bi′[j′])//theGhashfunctionisnotdefinedFurtherpasseswheniterations>1fornIteration←2toiterationsdofori←0toparallelism-1doforeachrowforj←0tocolumnCount-1do//foreachsubsequentcolumn//i'andj'indexesdependifit'sArgon2i,Argon2d,orArgon2id(Seesection3.4)i′,j′←GetBlockIndexes(i,j)ifj==0thenBi[0]=Bi[0]xorG(Bi[columnCount-1],Bi′[j′])elseBi[j]=Bi[j]xorG(Bi[j-1],Bi′[j′])ComputefinalblockCastheXORofthelastcolumnofeachrowC←B0[columnCount-1]fori←1toparallelism-1doC←CxorBi[columnCount-1]ComputeoutputtagreturnHash(C,tagLength)最通俗的解读，最深刻的干货，最简洁的教程，众多你不知道的小技巧等你来发现！
欢迎关注我的公众号:「程序那些事」,懂技术，更懂你！
