Realization of the round 2 aes candidates using altera fpga

( ＳＣ１６Ｅ０３６) 阶段性研究成果
[作者简介] 张 叉(１９６５—) ꎬ男ꎬ四川盐亭人ꎬ四川师范大学外国语学院教授ꎬ四川省比较文学研究基地兼职研究员ꎬ国际期刊« 美中
外语» ( ＵＳ￣Ｃｈｉｎａ Ｆｏｒｅｉｇｎ Ｌａｎｇｕａｇｅ) 与« 中美英语教学» ( Ｓｉｎｏ￣ＵＳ Ｅｎｇｌｉｓｈ Ｔｅａｃｈｉｎｇ) 审稿专家ꎬ国内集刊« 外国语文论丛» 主编ꎬ主要从事英美
得以创建之前ꎬ在印度文学中就已经出现了一些
关注比较层面的文本ꎮ 您能就此给我们作一个阐
释吗?
达斯古普塔:我在早先的一篇文章中提出这
个问题的时候ꎬ主要指的是经常在梵文或孟加拉
文学与欧洲文学之间运用比较的 １９ 世纪孟加拉
大学( Ｊａｄａｖｐｕｒ Ｕｎｉｖｅｒｓｉｔｙ) 设立比较文学系之际的
１９５６ 年ꎬ当时布达德瓦 博斯应邀担任系主任ꎮ
近早期戏剧ꎬ 对亚里士多德 ( Ａｒｉｓｔｏｔｌｅ) 的 « 诗学»
( Ｐｏｅｔｉｃｓ) 和婆罗多( Ｂｈａｒａｔａ) 的« 舞论» ( Ｎａｔｙａｓａｓ￣
ｔｒａ) 进行研究就更加必要ꎬ比如ꎬ研究索福克勒斯
( Ｓｏｐｈｏｃｌｅｓ) 的« 俄狄浦斯王» ( Ｏｅｄｉｐｕｓ Ｒｅｘ) 和迦梨
陀娑的« 莎恭达罗» ( Ａｂｈｉｊｎａｎａｓａｋｕｎｔａｌａｍ) ꎮ 但是ꎬ
此文是四川师范大学外国语学院教授张叉对
Ｓｔｕｄｉｅｓ ｉｎ Ｉｎｄｉａ:Ｇｅｎｏｌｏｇｙ) ꎮ 请同我们分享一下您
拉沃蒂达斯古普塔所作的比较文学专题访谈录
苏芭查克拉沃蒂达斯古普塔( 以下简称
印度贾达夫普尔大学比较文学系教授苏芭查克
的主要内容ꎮ 张叉教授对苏芭查克拉沃蒂达
斯古普塔教授所作的专题 访 谈 录 由 八 个 部 分 组

Numerical atomic orbitals for linear-scaling calculationsJavier Junquera,1O´scar Paz,1Daniel Sa´nchez-Portal,2,3and Emilio Artacho41Departamento de Fı´sica de la Materia Condensada,C-III,Universidad Auto´noma,28049Madrid,Spain2Department of Physics and Materials Research Laboratory,University of Illinois,Urbana Illinois618013Departamento de Fı´sica de Materiales and DIPC,Facultad de Quı´mica,UPV/EHU,Apdo.1072E-20080San Sebastia´n,Spain 4Department of Earth Sciences,University of Cambridge,Downing Street,Cambridge CB23EQ,United Kingdom͑Received6April2001;published28November2001͒The performance of basis sets made of numerical atomic orbitals is explored in density-functional calcula-tions of solids and molecules.With the aim of optimizing basis quality while maintaining strict localization ofthe orbitals,as needed for linear-scaling calculations,several schemes have been tried.The best performanceis obtained for the basis sets generated according to a new scheme presented here,aflexibilization of previousproposals.Strict localization is maintained while ensuring the continuity of the basis-function derivative at thecutoff radius.The basis sets are tested versus converged plane-wave calculations on a significant variety ofsystems,including covalent,ionic,and metallic.Satisfactory convergence is obtained for reasonably smallbasis sizes,with a clear improvement over previous schemes.The transferability of the obtained basis sets istested in several cases and it is found to be satisfactory as well.DOI:10.1103/PhysRevB.64.235111PACS number͑s͒:71.15.Ap,71.15.MbI.INTRODUCTIONIn order to make intelligent use of the increasing power of computers for thefirst-principles simulation of ever larger and more complex systems,it is important to develop and tune linear-scaling methods,where the computational load scales only linearly with the number of atoms in the simula-tion cell.The present status of these methods and their ap-plications can be found in several reviews.1–3Essential for linear scaling is locality,and basis sets made of localized wave functions represent a very sensible basis choice.It is not only the scaling that matters,however,the prefactor be-ing also important for practical calculations.The prefactor depends significantly on two aspects of the basis:͑i͒the number of basis functions per atom,and͑ii͒the size of the localization regions of these functions.Atomic orbitals offer efficient basis sets since,even though their localization ranges are larger than those of some other methods,4the number of basis functions needed is usu-ally quite small.The price to pay for this efficiency is the lack of systematics for convergence.Unlike with plane-wave5or real-space-grid6related methods,there is no unique way of increasing the size of the basis,and the rate of convergence depends on the way the basis is enlarged.This fact poses no fundamental difficulties,it just means that some effort is needed in the preparation of unbiased basis sets,in analogy to the extra work required to prepare pseudo-potentials to describe the effect of core electrons.Maximum efficiency is achieved by choosing atomic or-bitals that allow convergence with small localization ranges and few orbitals.It is a challenge again comparable to the one faced by the pseudopotential community,where transfer-ability and softness are sought.7For atomic wave functions the optimization freedom is in the radial shape.Gaussian-type orbitals have been proposed for linear scaling,8–10con-necting with the tradition of quantum chemistry.11,12These bases are,however,quite rigid for the mentioned optimiza-tion,imposing either many Gaussians or large localization ranges.Numerical atomic orbitals͑NAO’s͒are moreflexible in this respect.Different ideas have been proposed in the litera-ture,originally within tight-binding contexts concentrating on minimal͑single␨)bases.They are obtained byfinding the eigenfunctions of the isolated atoms confined within spherical potential wells of different shapes,13–15or directly modifying the eigenfunctions of the atoms.16These schemes give strictly localized orbitals,i.e.,orbitals that are strictly zero beyond given cutoff radii r c.Afirst extension towards more complete basis sets was proposed using the excited states of the confined atoms,17but the quite delocalized char-acter of many excited states made this approach inefficient unless very stringent confinement potentials were used.18 For multiple␨,a better scheme was proposed based on the split-valence idea of quantum chemistry,11,12but adapted to strictly localized NAO’s.19In the same work,a systematic way was proposed to generate polarization orbitals suited for these basis sets.The scheme of Ref.19has proven to be quite efficient,systematic,and reasonable for a large variety of systems͑for short reviews,see Refs.19and20͒.In this work we go beyond previous methodologies be-cause of two main reasons:͑i͒It is always desirable to obtain the highest possible accuracy given the computational re-sources available,and͑ii͒it is important to know and show what is the degree of convergence attainable by NAO basis sets of reasonable sizes.We explore these issues by variationally optimizing basis sets for a variety of condensed systems.The parameters de-fining the orbitals are allowed to vary freely to minimize the total energy of these systems.This energy is then compared with that of converged plane-wave calculations for exactly the same systems,including same density functional and pseudopotentials.The optimal basis sets are then tested monitoring structural,and elastic properties of the systems.The transferability of the basis sets optimized for particu-lar systems is then checked by transferring them to other systems and testing the same energetical,structural,and elas-tic parameters.Finally,the effect of localizing the orbitalsPHYSICAL REVIEW B,VOLUME64,235111tighter than what they variationally choose is explored on a demanding system.II.METHODThe calculations presented below were all done using density-functional theory21,22͑DFT͒in its local-density23ap-proximation͑LDA͒.Core electrons were replaced by norm-conserving pseudopotentials7in their fully separable form.24 The nonlocal partial-core exchange-correlation correction25 was included for Cu to improve the description of the core-valence interactions.Periodic boundary conditions were used for all systems. Molecules were treated in a supercell scheme allowing enough empty space between molecules to make intermo-lecular interactions negligible.For solid systems,integra-tions over the Brillouin zone were replaced by converged sums over selected kជsets.26Thus far the approximations are exactly the same for the two different sets of calculations performed in this work: based on NAO’s and on plane-waves͑PW’s͒.The calcula-tions using NAO’s were performed with the SIESTA method, described elsewhere.18,27Besides the basis itself,the only additional approximation with respect to PW’s is the replace-ment of some integrals in real space by sums in afinite three-dimensional͑3D͒real-space grid,controlled by one single parameter,the energy cutoff for the grid.27This cutoff, which refers to thefineness of the grid,was converged for all systems studied here͑200Ry for all except for Si and H2,for which80and100Ry respectively,were used͒.Similarly,the PW calculations were done for converged PW cutoffs.28 Cohesive curves for the solids were obtained byfitting calculated energy values for different unit-cell volumes to cubic,quartic,and Murnaghan-like29curves,a procedure giving values to the lattice parameter,the bulk modulus and the cohesive energy of each system.The bulk moduli given by the Murnaghan and quarticfits deviate from each other by around3%,the Murnaghan values being the lowest and the ones shown in the tables.The deviations between Mur-naghan and cubicfits are of the order of7%.The other cohesive parameters do not change appreciably with thefits.The atomic-energy reference for the cohesive energy was taken from the atomic calculations within the same DFT and pseudopotentials,always converged in the basis set.They are hence the same reference for NAO’s and for PW’s,the dif-ference in cohesive energies between the two accounting for the difference in the total energy of the solid.The isolated-atom calculations included spin polarization.III.BASIS OF NUMERICAL ATOMIC ORBITALSThe starting point of the atomic orbitals that conform the basis sets used here is the solution of Kohn-Sham’s Hamil-tonian for the isolated pseudoatoms,solved in a radial grid, with the same approximations as for the solid or molecule ͑the same exchange-correlation functional and pseudopoten-tial͒.A strict localization of the basis functions is ensured either by imposing a boundary condition,by adding a con-fining͑divergent͒potential,or by multiplying the free-atom orbital by a cutting function.We describe in the following three main features of a basis set of atomic orbitals:size, range,and radial shape.A.Size:Number of orbitals per atomFollowing the nomenclature of quantum chemistry,we es-tablish a hierarchy of basis sets,from single␨to multiple␨with polarization and diffuse orbitals,covering from quick calculations of low quality to highly converged ones,as con-verged as thefinest calculations in quantum chemistry.A single␨͑also called minimal͒basis set͑SZ in the following͒has one single radial function per angular momentum chan-nel,and only for those angular momenta with substantial electronic population in the valence of the free atom.Radialflexibilization is obtained by adding a second func-tion per channel:double␨͑DZ͒.Several schemes have been proposed to generate this second function.In quantum chem-istry,the split valence11,30scheme is widely used:starting from the expansion in Gaussians of one atomic orbital,the most contracted Gaussians are used to define thefirst orbital of the double␨and the most extended ones for the second. Another proposal defines the second␨as the derivative of thefirst one with respect to occupation.31For strictly local-ized functions there was afirst proposal17of using the ex-cited states of the confined atoms,but it would work only for tight confinement.An extension of the split valence idea of quantum chemistry to strictly localized NAO’s was proposed in Ref.19and has been used quite successfully in a variety of systems.It consists of suplementing each basis orbital with a new basis function that reproduces exactly the tail of the original orbital from a given matching radius r m out-wards.The inner part goes smoothly towards the origin as r l(aϪbr2),where a and b are chosen to ensure continuity of the function and its derivative at r m.We follow this scheme in this work,which generalizes to multiple␨trivially by adding more functions generated with the same procedure.Angularflexibility is obtained by adding shells of higher angular momentum.Ways to generate these so-called polar-ization orbitals have been described in the literature,both for Gaussians11,12and for NAO’s.19In this work,however,they will be obtained variationally,as the rest,within theflexibili-ties described below.B.Range:Cutoff radii of orbitalsStrictly localized orbitals͑zero beyond a cutoff radius͒are used in order to obtain sparse Hamiltonian and overlap ma-trices for linear scaling.The traditional alternative to this is based on neglecting interactions when they fall below a tol-erance or when the atoms are beyond some scope of neigh-bors.For long ranges or low tolerances both schemes are essentially equivalent.They differ in their behavior at shorter ranges,where the strict-localization approach has the advan-tage of remaining in the Hilbert space spanned by the basis, remaining variational,and avoiding numerical instabilities no matter how short the range becomes.For the bases made of strictly localized orbitals,the prob-lem isfinding a balanced and systematic way of defining all the different cutoff radii,since both the accuracy and theJUNQUERA,PAZ,SA´NCHEZ-PORTAL,AND ARTACHO PHYSICAL REVIEW B64235111computational efficiency in the calculations depend on them.A scheme was proposed19in which all radii were defined by one single parameter,the energy shift,i.e.,the energy raise suffered by the orbital when confined.In this work,however, we step back from that systematic approach and allow the cutoff radii to vary freely in the optimization procedure͑up to a maximum value of8a.u.͒.C.ShapeWithin the pseudopotential framework it is important to keep the consistency between the pseudopotential and the form of the pseudoatomic orbitals in the core region.This is done by using as basis orbitals the solutions of the same pseudopotential in the free atom.The shape of the orbitals at larger radii depends on the cutoff radius͑see above͒and on the way the localization is enforced.Thefirst proposal13used an infinite square-well potential͑see Fig.1͒.It has been widely and successfully used for minimal bases within the ab initio tight-binding scheme of Sankey and collaborators13us-ing the FIREBALL program,but also for moreflexible bases using the methodology of SIESTA.This scheme has the disadvantage,however,of generating orbitals with a discontinuous derivative at r c as seen in Fig.1.This discontinuity is more pronounced for smaller r c’s and tends to disappear for long enough values of this cutoff.It does remain,however,appreciable for sensible values of r c for those orbitals that would be very wide in the free atom.It is surprising how small an effect such a kink produces in the total energy of condensed systems͑see below͒.It is,never-theless,a problem for forces and stresses,especially if they are calculated using a͑coarse͒finite three-dimensional grid.Another problem of this scheme is related to its defining the basis considering the free atoms.Free atoms can present extremely extended orbitals,their extension being,besides problematic,of no practical use for the calculation in con-densed systems:the electrons far away from the atom can be described by the basis functions of other atoms.Both problems can be addressed simultaneously by add-ing a soft confinement potential to the atomic Hamiltonian used to generate the basis orbitals:it smooths the kink and contracts the orbital as variationally suited.Two soft confine-ment potentials have been proposed in the literature͑Fig.1͒, both of the form V(r)ϭV o r n,one for nϭ2͑Ref.14͒and the other for nϭ6.15They present their own inconveniences,however.First,there is no radius at which the orbitals be-come strictly zero,they have to be neglected at some point. Second,these confinement potentials affect the core region spoiling its adaptation to the pseudopotential.This last problem affects a more traditional scheme as well,namely,the one based on the radial scaling of the or-bitals by suitable scale factors.In addition to very basic bonding arguments,32it is soundly based on restoring virial’s theorem forfinite bases,in the case of Coulombic potentials ͑all-electron calculations͒.33The pseudopotentials limit its applicability,allowing only for extremely small deviationsfrom unity(ϳ1%)in the scale factors obtained variationally ͑with the exception of hydrogen that can contract up to 25%͒.34An alternative scheme to avoid the kink has also beenproposed:16Instead of modifying the potential,it directlymodifies the orbitals of the atom.Following ideas of previ-ous mixed-basis schemes37the atomic orbital is multiplied by1Ϫexp͓Ϫ␣(rϪr c)2͔for rϽr c and zero otherwise.16In Ref.16it is the hard confined wave function which is thenmodified,while in Ref.37it is the free atom wave function.We follow Ref.37.This method is tested in the next section. This scheme does provide strict localization beyond r c,but introduces a different problem:for large␣and small r c a bump appears in the orbital close to r c,which becomes a discontinuity in the wave function in the limit of infinite␣͑Ref.37͒͑this is not the case in Ref.16͒.FIG.1.Shape of the3s orbital of Mg in MgO for the different confinement schemes͑a͒and corresponding potentials͑b͒.NUMERICAL ATOMIC ORBITALS FOR LINEAR-...PHYSICAL REVIEW B64235111In this work we propose a new soft confinement potential avoiding the mentioned deficiencies.It is shown in Fig.1.It isflat͑zero͒in the core region,starts off at some internal radius r i with all derivatives continuous,and diverges at r c ensuring the strict localization there.It isV͑r͒ϭV o eϪ(r cϪr i)/(rϪr i)r cϪr.͑1͒In the following the different schemes are compared,theirdefining parameters being allowed to change variationally.Finally,the shape of an orbital is also changed by theionic character of the atom.Orbitals in cations tend to shrink, and they swell in anions.Introducing a␦Q in the basis-generating free-atom calculations gives orbitals betteradapted to ionic situations in the condensed systems.IV.OPTIMIZATION PROCEDUREGiven a system and a basis size,the range and shape ofthe orbitals are defined by a set of parameters as describedabove.The parameters are described in the following.Per atomic species there is a global␦Q,an extra charge͑positive or negative͒added to the atom at the time of solving theatomic DFT problem for obtaining the basis orbitals͑see below͒.Confinement is imposed separately for each angular mo-mentum shell,with its corresponding parameters that depend on the scheme used.Hard confinement implies one param-eter per shell(r c),and our soft confinement implies three (r c,r i,and V o).One parameter(V o)is needed only in the r n-confinement schemes,14,15and two parameters in the scheme of Elsaesser et al.37(r c and the width of the cutting function͒.Finally,for each␨beyond thefirst,there is a matching radius as mentioned above.19The values of these parameters are defined variationally, according to the following procedure:͑i͒Given a set of parameters,the Kohn-Sham Hamil-tonian͑including the pseudopotential͒is solved for the iso-lated atom,in the presence of the confining potential and the extra charge␦Q.͑In the case of the scheme of Elsaesser et al.,37there is no confining potential,but an a posteriori modification of the solution wave functions.͒This is done for all the relevant l shells of all the different atomic species. The multiple zetas are built from the former using the match-ing procedure described above,19according to the r m’s within the set of parameters.This procedure gives a basis set for each set of parameter values.͑ii͒Given the basis set,a full DFT calculation is per-formed of the system for which the basis is to be optimized, normally a condensed system,solid or molecule.The Kohn-Sham total energy of this system becomes then a function of that set of parameters.Note that neither the extra charge nor the confinement potentials are added to the Kohn-Sham Hamiltonian of the system,they were just used to define the basis.The total-energy calculations are performed for given structural parameters of the studied system.We have chosen to work with experimental structures.This choice is,how-ever,of no great importance since the basis sets are supposed to be transferable enough to render any bias negligible.This is certainly the case at the DZP level,not so much for mini-mal bases.See the section on transferability below.͑iii͒The previous two steps are built in as a function into a minimization algorithm.As a robust and simple minimiza-tion method not requiring the evaluation of derivatives,we have chosen the downhill simplex method.38We have not dedicated special efforts to maximizing the efficiency of the minimization procedure since the systems used for basis op-timization typically involve a small number of atoms and the total-energy calculations are quick.The possible improve-ment in the minimization efficiency is therefore of no rel-evance to the present study.We have no argument to discard the existence of several local minima in the energy function.For the systems studied here there may be sets of parameters giving better bases than the ones we obtain.We systematically tested their robustness by restarting new simplex optimizations from the already optimized sets.More systematic searches for absolute minima,however,would require much more expensive tech-niques,which would not be justified at this point.We have thus satisfied ourselves with the ones obtained,that show good and consistent convergence characteristics.The values obtained for the parameters in the optimizations described below can be obtained from the authors.39V.RESULTSparison of different confinement schemesTable I shows the performance for MgO of the different schemes described above for constructing localized atomic orbitals.The basis sets of both magnesium and oxygen were variationally optimized for all the schemes.Mg was chosen because the3s orbital is very extended in the atom and both the kink and the confinement effects due to other orbitals are very pronounced.Results are shown for a SZ͑single s and p TABLE parison of different confinement schemes on the cohesive properties of MgO,for SZ and DZP basis sets.The gen-eralization of the different schemes to DZP is done as explained in the text.Unconfined refers to using the unconfined pseudoatomic orbitals as basis.a,B,and E c stand for lattice parameter,bulk modulus,and cohesive energy,respectively.The PW calculations were performed with identical approximations as the NAO ones except for the basis.Experimental values were taken from Ref.40.SZ DZPBasis a B E c a B E c scheme͑Å͒͑GPa͒͑eV͒͑Å͒͑GPa͒͑eV͒Unconfined 4.25119 6.49Sankey 4.1722210.89 4.1216511.82 Elsaesser 4.1622811.12 4.1216311.84 Porezag 4.1819611.17 4.0918311.83 Horsfield 4.1522111.26 4.1116811.86 This work 4.1522611.32 4.1016711.87PW 4.1016811.90 Expt. 4.2115210.3JUNQUERA,PAZ,SA´NCHEZ-PORTAL,AND ARTACHO PHYSICAL REVIEW B64235111channels for both species͒and a DZP basis͑double s and p channels plus a single d channel͒.Figure1shows the shape of the optimal3s orbital for the different schemes,and the shape of the confining potentials.The following conclusions can be drawn from the results:͑i͒Within the variational freedom offered here,the3s orbital of Mg wants to be confined to a radius of around6.5bohr, irrespective of scheme,which is extremely short for the free atom.This confinement produces a pronounced kink in the hard scheme.͑ii͒The total energy is relatively insensitive to the scheme used to generate the basis orbitals,as long as there is effective confinement.͑iii͒The basis made of uncon-fined atomic orbitals is substantially worse than any of the others.͑iv͒The pronounced kink obtained in Sankey’s hard confinement scheme is not substantially affecting the total energy as compared with the other schemes.It does perturb, however,by introducing inconvenient noise in the energy variation with volume and other external parameters,and especially in the derivatives of the energy.͑v͒The scheme proposed in this work is variationally slightly better than the other ones,but not significantly.Its main advantage is the avoidance of known problems.In the remainder of the paper, the confinement proposed in this work will be used unless otherwise specified.B.Basis convergenceTable II shows how NAO bases converge for bulk silicon.This is done by comparing different basis sizes,each of them optimized.The results are compared to converged͑50Ry͒PW results͑converged basis limit͒keeping the rest of the calculation identical.Figure2͑a͒shows the cohesion curves for this system.Even though the main point of this work is testing the convergence of NAO basis sets independently of other is-sues,we consider it interesting to gauge the relevance of the errors introduced by the basis by comparing them with other typical errors that appear in these calculations.The NAO and PW results are thus compared to all-electron LDA results49to compare basis errors with the ones produced by the pseudo-potentials.Experiment gives then reference to the error co-mitted by the underlying LDA.The comparisons above are made with respect to the converged-basis limit,for which we used PW’s up to very high cutoffs.It is important to distinguish this limit from the PW calculations at lower cutoffs,as used in many computa-tions.To illustrate this point,Fig.2͑b͒compares the energy convergence for PW’s and for NAO’s.Even though the con-vergence of NAO results is a priori not systematic with the way the basis is enlarged,the sequence of bases presented in thefigure shows a nice convergence of total energy with respect to basis size͑the number of basis functions per atom are shown in parentheses in thefigure͒:the convergence rate is similar to the one of PW’s͑DZP has three times more orbitals than SZ,and a similar factor is found for their equivalents in PW’s͒.For the particular case of Si,Fig.2 shows that the polarization orbitals(3d shell͒are very im-portant for convergence,more than the doubling of the basis. This fact is observed from the stabilization of SZP with re-spect to SZ,which is much larger than for DZ.Figure2shows that an atomic basis at the DZP level requires ten times less functions than its͑energetically͒equivalent PW basis,being Si the easiest system forPW’s.FIG.2.Convergence of NAO basis sets for bulk Si.͑a͒Cohe-sive curve for different basis sets.The lowest curve shows the PW results,filled symbols the NAO bases of this work(opt),and open symbols the NAO bases following Ref.19.Basis labels are like in Table II.͑b͒Comparison of NAO convergence with PW conver-gence.In parentheses is the number of basis functions per atom.TABLE II.Basis comparisons for bulk Si.a,B,and E c stand forlattice parameter͑inÅ͒,bulk modulus͑in GPa͒,and cohesive en-ergy͑in eV͒,respectively.SZ,DZ,and TZ stand for single␨,double␨,and triple␨.P stands for polarized,DP for doubly polar-PW results were taken from Ref.41,and the experimentalvalues from Ref.42.SZ DZ TZ SZP DZP TZP TZDP PW LAPW Expt.a 5.52 5.49 5.48 5.43 5.40 5.39 5.39 5.38 5.41 5.43B85878597979797969698.8E c 4.70 4.83 4.85 5.21 5.31 5.32 5.34 5.37 5.28 4.63NUMERICAL ATOMIC ORBITALS FOR LINEAR-...PHYSICAL REVIEW B64235111For other systems the ratio is much larger,as shown in Table III.It is important to stress that deviations smaller than the ones due to the pseudopotential or the DFT used are obtained with a relatively modest basis size as DZP.This fact is clearin Table II for Si,and in Table IV for other systems.Table IV summarizes the cohesion results for a variety of solids of different chemical kind.They are obtained with optimal DZP basis sets.It can be observed that DZP offers results in good agreement with converged-basis numbers,showing the con-vergence of properties other than the total energy.The devia-tions are similar or smaller than those introduced by LDA or by the pseudopotential.47VI.TRANSFERABILITYTo what extent do optimal bases keep their performance when transferred to different systems than the ones they were optimized for?This is an important question,since if the performance does not suffer significantly,one can hope to tabulate basis sets per species,to be used for whatever sys-tem.If the transferability is not satisfactory,a new basis set should then be obtained variationally for each system to be studied.Of course the transferability increases with basis size,since the basis has more flexibility to adapt to different environments.In this work we limit ourselves to try it on DZP bases for a few representative systems.Satisfactory transferability has been obtained when check-ing in MgO the basis set optimized for Mg bulk and O in a water molecule.Similarly,the basis for O has been tested in H 2O and O 2,and the basis for C in graphite and diamond.TABLE III.Equivalent PW cutoff (E cut )to optimal DZP basesfor different parison of number of basis functions per atom for both bases.For the molecules,a cubic unit cell of 10Åof side was used.System No.funct.DZPNo.funct.PWE cut ͑Ry ͒H 251129634O 2134544286Si1322722Diamond 1328459␣-quartz1392376TABLE IV .Basis comparisons for different solids.a ,B ,and E c stand for lattice parameter ͑in Å͒,bulk modulus ͑in GPa ͒,and co-hesive energy ͑in eV ͒,respectively.ExpLAPW Other PW PW DZP Aua 4.08a 4.05b 4.07c 4.05 4.07B 173a 198b 190c 191188E c 3.81a -- 4.19 4.03MgOa 4.21d 4.26e - 4.10 4.11B 152d 147e -168167E c 10.30d 10.40e -11.9011.87Ca 3.57a3.54f 3.54g 3.53 3.54B 442a 470f 436g 466453E c 7.37a 10.13f 8.96g 8.908.81Sia 5.43a 5.41h 5.38g 5.38 5.40B 99a 96h 94g 9697E c 4.63a 5.28h 5.34g 5.37 5.31Naa 4.23a 4.05i 3.98g 3.95 3.98B 6.9a 9.2i 8.7g 8.89.2E c 1.11a 1.44j 1.28g 1.22 1.22Cua 3.60a 3.52b 3.56g - 3.57B 138a 192b 172g -165Ec 3.50a 4.29k 4.24g - 4.37Pba 4.95a - 4.88- 4.88B 43a -54-64E c2.04a- 3.77- 3.51aC.Kittel,Ref.42.bA.Khein,D.J.Singh,and C.J.Umrigar,Ref.43.cB.D.Yu and M.Scheffler,Ref.44.dF.Finocchi,J.Goniakowski,and C.Noguera,Ref.40.eJ.Goniakowski and C.Noguera,Ref.45.fN.A.W.Holzwarth et al.,Ref.46.gM.Fuchs,M.Bockstedte,E.Pehlke,and M.Scheffler,Ref.47.hC.Filippi,D.J.Singh,and C.J.Umrigar,Ref.41.iJ.P.Perdew et al.,Ref.48.jM.Sigalas et al.,Ref.49.kP.H.T.Philipsen and E.J.Baerends,Ref.50.TABLE V .Transferability of basis sets.‘‘Transf.’’stands for the DZP basis transferred from other systems,while ‘‘Opt.’’refers to the DZP basis optimized for the particular system.For MgO the basis was transferred from bulk Mg and an H 2O molecule,for graphite the basis was transferred from diamond,and for H 2O it was taken from H 2and O 2.a ,B ,and E c stand for lattice parameter,bulk modulus,and cohesive energy,respectively.⌬E stands for the energy difference per atom between graphite and a graphene plane.E b is the binding energy of the molecule.System BasisProperties MgOa ͑Å͒B ͑GPa ͒E c ͑eV ͒Transf. 4.1315711.81Opt. 4.1016711.87PW 4.1016811.90Expt.4.2115210.30Graphitea ͑Å͒c ͑Å͒⌬E ͑meV ͒Transf. 2.456 6.5038PW a 2.457 6.7224Expt.b2.456 6.67423c H 2Od O-H ͑Å͒␪H-O-H ͑deg ͒E b ͑eV ͒Transf.0.975105.012.73Opt.0.972104.512.94PW 0.967105.113.10LAPW d 0.968103.911.05Expt.e0.958104.510.08a M.C.Schabel and J.L.Martins,Ref.51.bY .Baskin and L.Mayer,Ref.52.cL.A.Girifalco and dd,Ref.53.dP.Serena,A.Baratoff,and J.M.Soler,Ref.54.eG.Herzberg,Ref.55.JUNQUERA,PAZ,SA´NCHEZ-PORTAL,AND ARTACHO PHYSICAL REVIEW B 64235111。

Infiltrate the Vault:Security Analysis and Decryption of Lion Full DiskEncryptionOmar Choudary University of Cambridge omar.choudary@Felix Gr¨o bert∗felix@Joachim Metz∗joachim.metz@AbstractWith the launch of Mac OS X10.7(Lion),Apple has introduced a volume encryption mechanism known as FileVault2.Apple only disclosed marketing aspects of the closed-source software,e.g.its use of the AES-XTS tweakable encryption,but a publicly available security evaluation and detailed description was unavailable until now.We have performed an extensive analysis of FileVault2and we have been able tofind all the algorithms and parameters needed to successfully read an encrypted volume.This allows us to perform forensic investigations on encrypted volumes using our own tools.In this paper we present the architecture of FileVault2, giving details of the key derivation,encryption process and metadata structures needed to perform the volume decryption.Besides the analysis of the system,we have also built a library that can mount a volume encrypted with FileVault2.As a contribution to the research and forensic communities we have made this library open source.Additionally,we present an informal security evalua-tion of the system and comment on some of the design and implementation features.Among others we analyze the random number generator used to create the recovery password.We have also analyzed the entropy of each 512-byte block in the encrypted volume and discovered that part of the user data was left unencrypted1.∗The opinions expressed in this paper are mine alone and do not reflect the opinions of my employer or affiliates of my employer unless otherwise explicitly stated.1This was reported to Apple in2011and FileVault Disk Encryption has been altered accordingly.See Apple CVE-2011-3212.1IntroductionSince the launch of Mac OS X10.7,also known as Lion, Apple includes a volume encryption software named FileVault2[8]in their operating system.While the pre-vious version of FileVault(introduced with Mac OS X 10.3)only encrypted the home folder,FileVault2can en-crypt the entire volume containing the operating system (this is commonly referred to as full disk encryption). This has two major implications:first,there is now a new functional layer between the encrypted volume and the originalfile system(typically a version of HFS Plus). This new functional layer is actually a full volume man-ager which Apple called CoreStorage[10]Although this full volume manager could be used for more than volume encryption(e.g.mirroring,snapshots or online storage migration)we don’t currently know of any other appli-cations.Therefore in the rest of this paper we will use the term CoreStorage for the combination of the encrypted volume and the functional layer that links this volume to the actual HFS Plusfilesystem.The second implication is that the boot process is slightly modified since the user password or other token must be retrieved before being able to decrypt the data. Apple’s volume encryption is equivalent to solu-tions such as PGP Whole Disk Encryption[12],True-Crypt[13],Sophos SafeGuard[20],Credant[21],Win-Magic SecureDoc[22],or Check Point FDE[23].All these solutions can be used on corporate laptops,which generally contain sensitive data that must be protected at all times(even when the computer is turned off).To the best of our knowledge,Apple has not released any documentation or source code on FileVault2,which obstructs security experts and consumers to assess the security of the system.Also,the missing documentation and interfaces effectively limit the development of any third-party tools that can help in data recovery or forensic investigations.In this paper we present the results of our analysisof FileVault2:we were able tofind most of its algo-rithms and parameters to the extent that we are able to read and mount a CoreStorage volume on a Linux ma-chine.In the following sections we describe in detail the key derivation mechanisms and the encryption pro-cess.There remains unknown information in the volume header and metadata,that we believe is used for verifica-tion routines or other functionality of CoreStorage which does not seem to affect the read of the contents of the en-crypted volume.Based on thesefindings,we have developed a cross-platform library that reads and mounts CoreStorage vol-umes.Such a library can be used to analyse the contents of a particularfile(or block)from an encrypted volume, without having to use Mac OS or even without having physical access to the Apple computer in question(e.g. by booting from a Linux live CD and connecting to the machine via the network).Our work provides the security and forensic commu-nity with an open source library that can be used to anal-yse CoreStorage volumes,having the user password or recovery password.It is also possible to recover the data from a CoreStorage volume using a private key but our library does not support this yet.However,this merely involves updating the key derivation process,which we fully describe in this paper.As part of our analysis we have also done an(informal) assessment of the security of the encryption mechanisms, including the random number generator mechanism used to create the recovery password.We found that some data is unnecessary protected(however weakly)while some other basic mechanisms such as code mangling are not used at all.We have also performed an entropy test on each512-byte block of the encrypted volume and we found that part of the user data was left unencrypted. 1.1Goals and motivationsOur primary goal has been to determine how FileVault2 operates.As we will detail in the next section,this task involvesfinding how and where the encrypted volume master key is stored,how this key can be obtained from the user password or another token,what other data(the metadata)is available and how is used,andfinally how the disk encryption and decryption are performed.As part of this process we created an open source tool that can read and decrypt a CoreStorage volume.Our motivation is twofold.First of all we needed a tool for digital forensic investigations.When a computer is suspected of malware or some malicious access we need to obtain certainfiles from the disk.If the computer is at a distant location it might not be feasible or conve-nient to send the computer or disk(for a Mac Book Air is not even trivial to remove the disk)in order to anal-yse it at the forensic laboratory.Even if we had physical access to a computer,we would not trust the operating system to extract the necessaryfiles since malware could tamper with the OS.With FileVault2enabled,we cannot read the disk contents unless the Mac OS is running.Al-though it is possible to access the disk of a Mac computer with another Mac computer using a FireWire connection, many times we use forensic tools on another operating system than Mac OS and we cannot rely on remote lo-cations having spare Mac computers for this task.Hav-ing cross-platform software to read encrypted volumes solves these problems.We can simply boot the Mac com-puter from a Linux live CD and use the software either locally or remotely to access the necessaryfiles.The second part of the motivation has been our de-sire to have a security assessment of the system.Since FileVault2can be used on corporate machines we needed to make sure that using this system instead of other known encryption solutions will not introduce vul-nerabilities.The next paragraphs provide a brief background on full disk encryption after which the details of FileVault2 are discussed.2BackgroundCommonly a hard disk is logically organised in multi-ple sections,often referred to as either partitions or vol-umes.These volumes can be used for various purposes, and they are often structured according to afile system format(e.g.NTFS,FAT,HFS,etc.).It is possible to have a single disk with3volumes,where thefirst volume is formatted with NTFS and contains a Windows operat-ing system,the second volume is formatted with EXT3 and contains an installation of a Linux distribution,while the third volume is formatted with FAT and only contains data(no operating system).The reader is encouraged to check the excellent book by Brian Carrier[28]for more details on the topic.V olume encryption is a mechanism used to encrypt the contents of an entire volume.This is sometimes referred to as full disk encryption,which is mis-leading,since a physical disk can actually contain mul-tiple volumes,each encrypted independently.The term full disk encryption is incorrectly used in the case of FileVault2and other systems such as BitLocker,that in fact perform volume encryption.Nonetheless,due to its popularity,we will continue to use the term full disk encryption in the remaining of this paper. Now,here is one the main problems:since we are en-crypting the entire volume,and this volume might be the volume containing the operating system,there is no un-encrypted code left to actually boot the system.There-fore the minimum code required to decrypt the operatingmetric cryptography would impact the read/write perfor-mance too much).Therefore,there must be a key that can unlock this encrypted volume.A typical AES key is128or256bits,too long for users to remember or type every time they boot the ma-chine:128bits can be represented with a minimum of22 characters using base64although base32or hexadecimal are more user-friendly,each requiring26or32charac-ters respectively.As a result,most full disk encryption schemes actually store this key(known as the volume master key)in an encrypted blob(usually by encrypt-ing or hashing the key along with some additional infor-mation several times).This blob can only be decrypted using an intermediary key that is derived from the user password or another user-trusted input,e.g.a private key stored on a USB stick,a smart card,or a trusted platform module(TPM)linked to the encrypted volume(see Fer-guson’s paper[1]for a detailed discussion on how to use these methods).This process is depicted infigure1.As you can observe fromfigure1,the blob containing key,as the IV.Although this approach can work(and is actually used in several full disk encryption implemen-tations such as Linux Unified Key Setup[2]),it has the disadvantage thatflipping one bit in the encrypted block will result in one bitflipped in the unencrypted version of the block,along with16corrupted bytes.For more details on these problems the reader in encouraged to see the work of Clemens[2]and Ferguson[1]. Bitlocker,the full disk encryption mechanism imple-mented in Windows since the version of Vista,deals with theflipping problem by adding a mechanism called Elephant Diffuser.FileVault2instead uses a tweak-able encryption scheme known as AES-XTS.We detail this method in the next sections but for the moment we mention that it has several advantages over AES in CBC mode with a block-derived IV,and solves most of the problems discussed earlier.The last important problem we should mention refers to the storage of the volume master key during system operation and sleep modes.As we mentioned earlier,Figure2:the recovery password shown by Mac OS when FileVault2is enabled.during the boot process the volume master key is derived from the user password or another token.Once this key is derived,the OS stores it in memory in order to read and write blocks efficiently without having to derive this key on every disk access.Halderman et al.[3]explain how an attacker with temporary access to a running sys-tem can scan the memory in order to retrieve the volume master key and therefore decrypt the contents of the disk. As far as we know this problem is still largely unsolved although computer manufacturers may use proprietary methods(such as on-board tamper resistant memories) to mitigate such attacks.Having discussed the basic concepts used in full disk encryption,we move to the core of this paper,presenting the details of FileVault2.A summary of the system is given in section3.6.3FileVault2architecture3.1Enabling FileVault2In Mac OS X Lion,after FileVault2is enabled,a series of events take place.First of all the user is presented with a24character recovery password(seefigure2).This password can be used to access the encrypted volume even if the user password is lost.We comment later on the security of this recovery method.Next,thefile system in the main volume is con-verted from the native HFSPlus type to CoreStorage(en-crypted).During this operation,the user can still use the system at will and the ConversionStatusfield in the EncryptedRoot.plistfile(details below)contains the string Converting.After the encryption process is com-plete the string changes to Complete.At the moment we do not know how the Mac OS keeps track of the encrypted blocks during the conver-sion process,so our tool cannot correctly mount vol-umes that are in a Converting state.This information could exist only somewhere in the last blocks of the vol-ume,since all the data before the encrypted volume is zeroed(details in section4).Comparing data from a par-tially encrypted volume with one fully encrypted wesee Figure3:output of diskutil list run on a Mac Book Air with FileVault2enabled.that the encrypted metadata(see details later)is identi-cal,while the Disk Label metadata only differs in some bytes.While these bytes might be related to the encryp-tion status,we believe the information,if available,is actually found near the encrypted metadata,in one of the encrypted chunks that follow the encrypted volume(see figure9).In addition to the encryption itself,a new volume gen-erally called Recovery HD appears alongside the main Macintosh HD existing volume.This new partition con-tains the encrypted volume master key,as described be-low.3.2The new volume,boot process andEncryptedRoot.plistfileRunning the command diskutil list on a Mac OS installation with FileVault2enabled will show an output similar tofigure3.Infigure3you can see the encrypted volume (disk0s2),the new volume(disk0s3),the original un-modified EFI volume(disk0s1),and also the unlocked (unencrypted)version of the main volume(disk1).There is also an additional partition(disk0s4)which we created just for testing purposes.The new Recovery HD volume contains a series of newfiles,including new EFI boot code to deal with the encrypted volume.The EFI(Extensible Firmware Inter-face),now known as UEFI(Unified EFI)[24],is a recent standard meant to replace the traditional BIOS system to boot a computer.It contains all the necessary POST routines to check the hardware and the necessary code to locate the volume that has an operating system and start booting from there.Around2006Apple switched to the Intel architecture and decided to use EFI instead of the traditional BIOS[25].When FileVault2is enabled,the existing EFI code(generally divided between a separate non-volatile memory location on the main board and a volume containing a FATfile system named EFI)is sup-plemented with code available in the new Recovery HD volume.This new code allows the system to display a UI where the user can type its password in order to unlock the encrypted volume key and load the actual OS. Among all thefiles available in the new volumethe most important for FileVault2operation is the EncryptedRoot.plist.wipekeyfile2,which con-tains all the information needed to extract the volume master key from the user’s password or a recovery to-ken.The EncryptedRoot.plist.wipekeyfile is en-crypted using AES-XTS(details later)with an all-zeros tweak key,but the encryption key is easily available in the header(first block)of the CoreStorage volume(see table2in Appendix).Among other data,the header block contains also the size of the entire volume(in-cluding metadata),another UUID which is used as a key to decrypt part of the metadata(see details later),and a CRC32checksum.The actual polynomial that is used for the CRC32calculation is currently unknown to us. However the open source code contains the precomputed computed CRC table found during the analysis.The CRC32checksum is used to validate the values in the FileVault2metadata structures.Once decrypted,thefile EncryptedRoot.plist has an XML structure with the following important entries:•PassphraseWrappedKEKStruct(1)–284byte structure for recovery password.•PassphraseWrappedKEKStruct(2)–284byte structure for user password.•KEKWrappedV olumeKeyStruct(1)–unused.•KEKWrappedV olumeKeyStruct(2)–contains wrapped volume master key.We mention that if multiple users are registered on the same machine then the EncryptedRoot.plistfile will have a separate PassphraseWrappedKEK structure for each user.In the following we present the key derivation mecha-nisms.3.3Key derivationThe volume master key is derived from the user pass-word,a private key token or the recovery password. Since the volume master key is the same but the ini-tial input is different,FileVault2uses an intermediary key that is decrypted under different inputs:password or recovery token.This intermediary key,which decrypts the volume master key,is called the volume key Key-Encryption-Key(KEK).The overall key derivation pro-cess is depicted infigure4.2found in com.apple.boot.X/System/Library/Caches/com.apple.corestorage/ (where X changes randomly between R,S and P)In this section we describe the key derivation process in the case of a volume master key derived from the user password.Thefirst step is to derive the intermediary vol-ume key KEK from the given password;this in turn is ac-complished in two stages.Wefirst need to use PBKDF2 to derive a key from the user password and then we need to decrypt the AES-wrapped version of the volume key KEK with this key.PBKDF2[15]is an algorithm used to derive a standard cryptographic key(of any length)from a user password (i.e.a written language text).The main objective of this algorithm is to make it difficult for an attacker to brute-force all possible values of the user password(which could be short or easy to guess).This is done by the use of two counter-measures:a salt and a large number of iterations.A random salt is required to avoid rainbow tables;such tables can be used to create precomputed re-sults of a cryptographic operation on various inputs such as dictionary keywords.The number of iterations speci-fies how many times to apply a pseudo-random function such as HMAC-SHA1[14]on the user password(and derived results)before creating thefinal key;this step ef-fectively slows down any attacker trying to brute-force the user password(see section4for a discussion on this matter).The salt value for PBKDF2is found in the PassphraseWrappedKEK structure(see table3in Ap-pendix)related to the user.However the number of PBKDF2iterations is not defined there.In our analy-sis we initially found that FileVault2derived the num-ber of iterations based on the amount of time required to compute a multiple of1000PBKDF2computations. We have later seen there is a default of41000iterations if the precomputed value is lower,and this appears to be always the case on current hardware.Probably the static value will be used most of the time,since a variable value might lead to incompatibility between devices(now you can access the encrypted volume of an Apple computer from another device via FireWire)and even blocked ac-cess to your machine if it performs slower or faster in time.For completeness we mention that the pseudo-random function used by FileVault2with PBKDF2is HMAC-SHA256.Once we have derived the PBKDF2key we can use this key to unwrap the intermediary KEK using the AES Wrap algorithm[16].This algorithm is used to wrap (encrypt)a cryptographic key under another key.In the case of FileVault2,the PBKDF2key is used to decrypt the intermediary volume key KEK,which in turn is used to decrypt the volume master key(also encrypted using the AES Wrap algorithm).The volume master key is wrapped under the intermediary KEK to support its main goal:only authorised users should be able to decrypt the disk contents(hence to access this key),while the in-Wrap algorithm(applying the unwrap operation),we can use this key to unwrap the volume master key from the KEKWrappedV olumeKey structure(see table4in Ap-pendix).In both unwrapping operations(to obtain the interme-diary KEK and the volume master key),the wrapped data has24bytes but the unwrapped key has only16bytes. That is because thefirst8bytes of the unwrapped data ac-tually contain the initial value of0xA6(a different value indicates a wrong decryption key),leaving only16bytes for the actual unwrapped key.Figure5:Example of an EncryptedRoot.plist when private key is used.The key derivation process can be summarised as:/Library/Keychains/FileVaultMaster.cer. Next we describe the encryption algorithm,AES-XTS, and present the last missing piece:the tweak key.3.4AES-XTSAES-XTS[18]is the encryption mechanism used by FileVault2to encrypt a volume.The overall architecture of AES-XTS is shown infigure6.AES-XTS is a type of tweakable encryption,using AES[19]as the block ci-pher.The XTS construction for tweakable encryption is based on Rogaway’s XEX[7].It allows each block onby j bits(this is the group multiplication shown in the di-agram)with a possible addition of a carry and a special value of135on thefirst byte.The shifted result T(the encrypted tweak)is xor-ed into the corresponding input data unit P and the output is then encrypted under key1 using AES-ECB.The result is then xor-ed with the same encrypted tweak yielding thefinal encrypted data unit. The complete encrypted data block is simply the con-catenation of all the encrypted data units.Decryption is done similarly,replacing the second AES encryption by decryption.AES-XTS has several advantages over alternatives such as AES in CBC:there is no requirement for an ini-tialization vector(the tweak key can be derived from the block number);each block is encrypted differently(since the tweak value will be different);and unlike AES-CBC, AES-XTS prevents an attacker from changing one spe-cific bit in a data unit by xor-ing each AES input with a different shifted version of the encrypted tweak. FileVault2uses AES-XTS in several places,always figure8.There are two essential metadata structures needed to decrypt the main volume:the Disk Label metadata and the encrypted metadata.The Disk Label metadata block offset can be found from the CoreStorage volume header(64-bit little endian value at byte offset104,see table2in Appendix).This offset can be multiplied with the32-bit block size value at byte offset96in the vol-ume header to obtain the byte offset within the volume. The block size is generally4096(0x1000),which is also the standard block size for the HFSPlusfile system.The size of the Disk Label metadata is given in the volume header,but in our experiments all the data of interest was available within thefirst8704bytes(i.e.seventeen512-byte blocks).We show the most importantfields of the Disk Label metadata in table5in Appendix.The Disk Label meta-data provides the offset of the encrypted metadata using the formula:o f f set=disk label[disk label[220]+32]Figure7:Example of data in thefirst xml metadata struc-ture.The encrypted metadata,as our given name im-plies,is encrypted.We found that we can decrypt its contents using AES-XTS with key1and key2from the CoreStorage volume header(see table2in Appendix), starting with a tweak value of0and using an8192-byte block size.The contents of the encrypted metadata structure are shown in table6in Appendix.The essential details are: the encrypted volume size(which equals the size of the decrypted volume–this is smaller than the size of the entire CoreStorage volume),the encrypted volume off-set,and the offset of thefirst xml metadata which con-tains the Logical Volume Family UUID(under the xml key com.apple.corestorage.lv.familyUUID). Thefirst,second and third xml metadata structures contain various UUIDs and other information related to the encrypted volume.However for decryption purposes we only need the lv.familyUUID(i.e.the Logical Volume Family UUID)which is available in both the first and third xml metadata structures.An example of thefirst xml metadata is shown infigure7.Using the Logical V olume Family UUID we can de-rive the full disk encryption tweak key by applying SHA-256on the concatenation between the volume master key and this UUID,and then retaining only thefirst16bytes: key2=MSB16(SHA256(volume master key|lv.f amilyUUID))Now that we have presented the building blocks of FileVault2we can describe the entire volume decryp-tion process,as depicted infigure8.Firstly we need to decrypt the EncryptedRoot.plistfile using the key from the volume header.Then,using the user’s pass-word or a recovery token we can extract the volume mas-ter key.We can now derive the full disk encryption tweak key from the encrypted metadata and the volume master key.At this point we can use the volume master key as key1and the full disk encryption tweak key as key2 with AES-XTS to decrypt the main volume,with a tweak value starting from0and a block size of512bytes.4Security analysis:problems and solutionsIn this section we present the results of our informal se-curity analysis of FileVault2.4.1Random number generator andrecovery passwordNaturally,the security of the complete FileVault2system relies on the quality of the encryption keys.While some keys are derived from the user provided password,as ex-plained earlier,other keys are randomly generated,for example the recovery password,key encryption keys and volume ing the recovery password,it is possible to mount and decrypt the complete CoreStorage volume. FileVault2features two recovery tokens:an RSA key and a recovery password.The asymmetric key recovery for corporate deployments is done using the same mech-anism as in thefirst FileVault implementation:a File-VaultMaster certificate is installed in the system’s key-chain and the public key of the certificate is used to en-crypt the intermediary KEK key,which is then added to the EncryptedRoot.plistfile.In this section we will take a closer look at the sec-ond recovery mechanism,the recovery password,tar-geted at consumers.When activating FileVault2,the System Preferences application displays a randomly gen-erated120bit password,encoded with base32,to the end user and advises them to securely store the password for recovery(seefigure2).The recovery password is read from/dev/random(through libcsfde and SecCreateRe-coveryPassword()in Security.framework). Therefore,the security of the FileVault2system can be reduced to the security of the pseudo random num-ber generator(PRNG)used in Mac OS X Lion for /dev/random.Mac OS relies on Counterpane’s imple-mentation of the Yarrow PRNG[6]with modifications by Apple available as open source[9].The Yarrow PRNG design has been obsoleted by Fortuna[11],written by the original authors.To evaluate the strength of Apple’s implementation of Yarrow,we evaluated the seeding of the PRNG.Be-cause the state of the PRNG is kept between reboots, we assume a scenario in which the end user activates FileVault2right after thefirst boot after operating sys-tem installation.This is a worst-case scenario,in which the PRNG has only been seeded with the least amount of entropy.During boot-time the PRNG is seeded with 8,20and332bytes.After boot-time,the PRNG is peri-odically seeded with332bytes every10minutes.If an attacker could guess the content of the seed,he would be able to recreate the PRNG’s state and predict its output, and hence determine the recovery password.The sources for the seeding are as follows:•8bytes boot seed:this seed is deterministic because it is the value of the current microtime()during boot.•20bytes boot seed:this is read from the SystemEntropyCachefile which contains the pre-vious state of the PRNG before reboot.Thefile is written by EntropyManager every6hours and during shutdown.It contains20byte output from /dev/random.This seed is deterministic in ourabove scenario because the system has booted the first time.•328byte boot and periodic seed:this seed is triggered by securityd and the seed’s contents are collected in the kernel’s kdbg getentropy() function.It is the core seed for the PRNG.The data contains41samples of mach absolute time(), which returns an8byte nano-precision time offset for different kernel threads.During1000reboots, we sampled the entropy seed of the PRNG.Our es-timate is that the total seeding entropy is40sam-ples of8bits of mach absolute time.This would result in320bits of total entropy because the nano-precision timestamps are only unpredictable in the lower bits and higher byte values have clearly re-occurring patterns.Thus,this represents a search space which is suboptimal,i.e.not every input to the seed is unpredictable and the amount of en-tropy input is less than what other operating sys-tems seed[4,5].However,the search space is large enough that it is not brute-force-able.For highly security-critical scenarios,the PRNG should be reseeded by manually writing entropy to /dev/random before activation of FileVault2.4.2Plaintext bits in encrypted volume Once we found most of the details about FileVault2op-eration we computed the entropy of each512-byte block of the CoreStorage volume to verify our assumptions and also to make sure we were not missing any data.A bitmap of the volume is shown infigure9,where blue corresponds to plain text,red to encrypted data and white to data with zero entropy(i.e.all bytes have the same value,such as all bytes0x00or0xFF).As you can see from the bitmap infigure9,there is a large block of zero data(with the exception of thefirst header block)at the beginning of the disk,then a large portion of encrypted data corresponding to the encrypted volume,and at the end there is a mix of plain text,en-crypted and zero data corresponding to the metadata,en-crypted metadata and related structures,and the backup header(last block).When wefirst looked at this data using the previous version of OS X(10.7.1),we discovered two interest-ing facts:firstly,there was a mix of plain text,zero and encrypted data at the beginning of the disk.Part of this data looked like unencrypted HFSPlusfile sys-tem structures.We could observe what seemed to be valid HFSPlus headers,allocation and extentsfiles.This led us to think for a moment that FileVault2might be afile based encryption mechanism rather than volume based.We could observe an allocationfile unencrypted,。

Symmetric-key Cryptography of AESLixinShanghai University of Electric Power School of computer science and technology, Shanghai Pudong New Area1543101883@Symmetric-key algorithms are a class of algorithms for cryptography that use the same cryptographic keys for both encryption of plaintext and decryption of ciphertext. The keys may be identical or there may be a simple transformation to go between the two keys. The keys, in practice, represent a shared secret between two or more parties that can be used to maintain a private information link. This requirement that both parties have access to the secret key is one of the main drawbacks of symmetric key encryption, in comparison to public-key encryption.2, the advanced encryption algorithm AES[2]Advanced Encryption Standard (Advanced Encryption Standard, AES), in cryptography is also called Rijndael encryption method, is the United States federal government adopted a block encryption standard. This standard is used to replace the original DES, have been various analysis and widely used all over the world. After five years of the selection process, the advanced encryption standard by the United States National Institute of standards and Technology (NIST) released in November 26, 2001 in FIPS PUB 197, and in May 26, 2002 of become effective standard. On 2006, the advanced encryption standard has become the most popular symmetric key encryption algorithm. The algorithm for the Belgian cryptographer Joan Daemen and Vincent Rijmen designed, combining the two author's name, the name to Rijndael, contributors to the advanced encryption standard selection process.(Rijndael "Rhine Doll" pronunciation.).2.1 introduction to AlgorithmsAlthough AES still has different view, but on the whole, AES as a new generation of data encryption standard convergence of strong security, high performance, high efficiency, ease of use and flexibility. AES is designed with three key length: 128192256 bits, in relative terms, 128 of AES than DES key 56 key 1021 times.2.2 algorithm principle and process[3]Clear data packet length for 128 or 16 bytes, key length can be 16,24, or 32 bytes (128192 or 256).According to the length of the key, the algorithm referred to as AES-128, AES-192, AES-256.The password by N wheel, wherein the wheel based on the key length: 16 bytes 24 bytes 10 round key is a key corresponding to the 12 round, 14 round, 32 byte keys.The last round only contains three transform, in the first round in front of an initial single transform (add round key), can be seen as 0 wheel.Clear data packet length for 128 or 16 bytes, key length can be 16,24, or 32 bytes(128192 or 256).According to the length of the key, the algorithm referred to as AES-128, AES-192, AES-256.The password by N wheel, wherein the wheel based on the key length: 16 bytes 24 bytes 10 round key is a key corresponding to the 12 round, 14 round, 32 byte keys.The last round only contains three transform, in the first round in front of an initial single transform (add round key), can be seen as 0 wheel.(1) it is not a Feistel structure.The structure of Feistel is a block cipher, generally divided into one of 64 groups, one group of left and right part, general for the 16 iterations, each iteration after the exchange of left and right position, can conduct their own design: packet size key length round number sub key generation wheel function(2) the input key is extended by 44 32 bit words consisting of an array of w[i].(3) consists of 4 distinct phases, including a replacement and three place:Bytes instead of (SubBytes): S box with a completion packet bytes into bytes instead of.Line shift (ShiftRows): a simple replacement.Column (MixColumns): confusion with domain GF (28) of the arithmetical properties of a place.Add round key (AddRoundKey): current packet and extended key part is the bitwise XOR.(4) the algorithm structure is simple.On encryption and decryption operations, the algorithm consists of add round key start, followed by 9 rounds of iterations, each round contains all 4 phases instead, followed by a tenth round of three stages.(5) only add round key stages using a secret key.(6) add round key is XOR, the other three stages to provide diffusion and confusion, nonlinear function, this method is very effective and very safe.(7) for each phase are inverse.(8) the decryption algorithm in the reverse mode using the extended key.But the AES decryption and encryption algorithms are not the same.(9) when all four phase inversion, it is easy to prove that the decryption function can recover the original plaintext.(10) the process of encryption and decryption of the last round only contains three stages.1, bytes instead of transformationSimple table lookup operation.AES defines a S box, which is a 16X16 byte matrix, contains 8 bits can represent the number 256 a replacement. Bytes: S box mapping: the 4 bytes of high as row value, low 4 bits for the column value, to these ranks value as index from S box position corresponding to the removed elements as output. For example, sixteen hexadecimal number {95} corresponding to the S box of 9 rows and 5 columns in the S box, the value of {2A}, so {95} is substituted for the {2A}.Inverse S box with a similar, backstepping .2, the row shift transform4X4 state first row of matrix unchanged, second rows of circular shift left one byte,third left circular shift of two bytes, fourth rows of three byte circular shift to left.3, the column obfuscationEach column of each byte is mapped to a new value, this value is 4 bytes in the column by function transformation.4, add round key transformationIn the add round key transformation, 128 state matrix according to a 128 position with the round key XOR. Reverse round key with transform and positive add round key transform, because the XOR operation is its own inverse.5, the key expansionInput key directly copied to the array of the first extended key words. Then, each with four characters to fill the remainder of the extended key array. In the extended key array, each new word w[i] relies on the w[i-1] and w[i-4].In four cases, three using the xor. On the w array subscript is multiple of 4 element uses a more complex functions to calculate the.The G function:1, word cycle function is to make one word in 4 byte shift left one byte, the input word is [B0, B1, B2, B3] transform into [B1, B2, B3, B0].2, word instead of the S box to the input word in each byte instead.3, the results with round or different constant Rcon[j].Wheel constant:Wheel constant is a word, the word to the right of three bytes for a total of 0.Thus the words and Rcon dissimilarity or, only with the word the left byte or different. Each round of the round constants are different, the definition for the Rcon[j]= (RC[j], 0,0,0), whereRC[1]=1, RC[j]=2, RC[j-1].The value of RC[j] to sixteen hexadecimal representation for:Equivalent inverse cipherAES encryption algorithm and encryption algorithm is different. In spite of encryption and decryption key expansion of the form is the same, but in the decryption transform in different order.Two improvements to enable decryption algorithm structure and algorithm structure of the same. In the encryption process, the wheel structure for bytes instead, shift rows, columns of confusion, add round key. In the standard in the decryption process, the wheel structure for retrograde transposition, Inverse Substitute Bytes, add round key column, reverse confusion. Therefore, in deciphering round in the first two stages should be exchanged, after the two stages also need to exchange.Reverse line shift effect in state byte order, but not change the byte content, also do not depend on the byte content to its transformation. Reverse bytes instead of state byte content, but do not change the byte order also do not depend on the byte sequence to its transformation. Therefore, the two operation can exchange. For a given state S: Reverse migration [reverse bytes instead of (S)] = reverse bytes instead of [reversemigration (S)]Add round key and reverse column confusion does not change the state byte order. If we take the key as a word sequence, then add round key and reverse column confused every time on the state column operation. The two operation on the column input is linear. For a given state of S and given wheel key W:Reverse column (S W confusion) =[reverse column confusion (S)] [column reverse confusion (W)]Note:(1) for calculating the round key is used in the reverse column obfuscating transformations, can use the corresponding reverse column transform algorithm instead of the four array, which can save the space of 4K.And, due to the reverse column transform in the AES implementation in the round key generation using, for the algorithm not to add / solution performance impact.(2) wheel constant cycle of 51 (from before 52 generation wheel constant known), and the AES algorithm with a maximum before the 14 round constants.2.4 Algorithm and ApplicationRijndael algorithm is flexible, simple, against multiple cipher analysis advantages, its goal is to develop into can be safely used for commercial, political and military encryption algorithm. In addition, the AES algorithm for hardware implementation of speed is about 3 times the software implementation, it is to realize with hardware encryption provides a very good opportunity. With the rapid development of network technology, network data encryption requirements increasing, the application of AES in a first embodiment of network information safety in the field.The application of the wireless networkAs wireless communication channel than the wired network is more open, the security requirements of higher. In order to guarantee the security of the data transfer, some wireless networks using AES. For example, ZigBee technology, to ensure that the MAC frame integrality, confidentiality, authenticity and consistency, the MAC layer is encrypted using the AES algorithm, and generates a series of security mechanism.Application of electronic commerceIn respect of electronic business affairs , mainly AES in e-commerce platform of cryptographic protocols and transaction security protocol. For example, the application of AES in SSL (Secure Sockets Layer secure socket layer) protocol. Through the AES encrypted data and transmits to each other. The receiver can use the AES key to get specific real-time data. The typical research include: AES and RSA hybrid encryption system using the NTRU public key cipher system; distribution of AES key; AES and ECC (elliptic curve cryptography) combination of encryption system.Application of AES softwareIn AES software, the application field of contains voice, video information encryption, data encryption. Nowadays multimedia information encryption problems highlighted. Because the multimedia information data is very big, directly to its encryption efficiency is low. So, we should consider not only the data encryption algorithm using AES method, and corresponding design on multimedia information encryption process. About AES in the application database, mainly in how data input, output in generation, distribution andmanagement of the key data encryption and security strategy.AES Hardware ApplicationIn AES hardware implementation, the main direction of RF IC card data security, smart card and hard disk data encryption etc. The RF IC card application scope is very broad, such as bus IC card, campus card.Reference[1] Internet Baidu Encyclopedia /view/7591.htm.2012/12/5.[2] John Savard's description of the AES algorithm/crypto/co040401.htm.2012/12/5.[3] [the]William Stallins; King Zhang Yi Yang Min Du Ruiying Deng, cryptography and network security P105-127.[4]E．Biham，A．Shamir．Differential cryptanalysis of DES-like cryptosystems[J]．Journal of Cryptology,1 991，4(1)：3—72．[5] E．Biham，A．Shamir．Defferential fault analysis of secret key cryptosytems[A]．In：Advances in Cryptology·CRYPTO’97[C]．Lecture Notes in ComputerScience 1294，Berlin：Springer-Verlag，1 997：5 1 3-525．[6] M．Mitsuru．Linear cryptanalysis method for DES cipher[A]．In：Advances inCryptology—EUROCRYPT’93[C]．Lecture Notes in Computer Science 765，Berlin：Springer-Verlag，1 994：386-397．[7] J．-S．Coron，P Kocher，D．Naccache．Statistics and secret leakage[A]．YFrankel(Ed)．In：Financial Cryptography-FC 2000，LNCS[C]．LNCS 1 962，Berlin：Springer-Verlag，200 1：1 57～1 73．[8] Wen Congjian computer science and technology AES differential - algebraic attack on 2009:16 ~ 22.。