The Research on Cryptographic Schemes

Zheng Shihui

（Information Security Center of State Key Laboratory of Networking and Switching

Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China）

Abstrac t:Cryptography is an important technology for information security.It mainly includes symmetric and asymmetric cryptographic algorithms and protocols.For the symmetric cryptographic algorithms,it is easy to deduce decryption keys from the encryption keys and vice versa.Because this algorithm encrypts and decrypts data very quickly,it is applicable in situations where large numbers of data have to be protected.However,for the asymmetric algorithm,extracting the secret key from the public key is computationally infeasible.Although the performance speed of the asymmetric algorithm is much slower than that of the symmetric algorithm,the asymmetric algorithm has key distribution and management advantages over the symmetric one.Moreover,it is a perfect digital signature scheme.

Cryptography is an interdisciplinary study fullof challenges with a long and colorful history.The Egyptian used simple encryption methods to pass secret messages more than 4 000 years ago.During the two world wars,cryptography played a significant role.

The research and application of cryptographic technologies in the early days were mainly for military,diplomatic and government activities.But things have changed since the 1960s.The rapid development of computer and communication systems forced people to think how to securely complete various transactions via computer and communication networks.As a result,the cryptographic technologies have been widely applied in civilactivities as well,which,in return,has promoted the development of cryptography.

Traditional cryptography is largely regarded as an art.Cryptographers usually design and analyze cryptographic schemes by their intuitions.It is not until 1949,when Claude E.Shannon［1］published Communication Theory of Secrecy Systems,where the security and design criteria of the secrecy systems were discussed from the view of information theory,that cryptography became a science.In the 1970s,International Business Machines（IBM）Corporation developed the Data Encryption Standard（DES）,which was specified as an official Federal Information Processing Standard（FIPS）by the USfederalgovernment in 1977.Almost at the same time,Whitfield Diffie and Martin Hellman［2］first presented the idea of“public key cryptography”.In their paper,New Direction in Cryptography,they gave a solution for the key distribution problem existing in symmetric-key cryptosystem and suggested the idea of digital signature.In 1978,Ron Rivest,Adi Shamir and Leonard Adleman［3］devised the first practical public-key encryption and signature scheme:RSA（named after the initial letters of the designers）,which marked the beginning of modern cryptography.

1 Symmetric-key Algorithm

The cryptographic schemes are mainly classified into two kinds:symmetric-key and asymmetric-key algorithms.In the symmetric-key algorithms,the encryption and decryption keys are identical,or one key can be easily deduced from the other one.As these algorithms'encryption/decryption processes are very quick,they are applicable for encrypting large numbers of data.The symmetric-key algorithms can be further divided into block ciphers and stream ciphers.

1.1 Block Cipher

Figure 1 is the encryption process of a block cipher.In a block cipher,generating and storing the key stream is not required;so,these algorithms are often applied in the situation where the storage space is limited.Currently,the cryptanalysis and design processes of block ciphers are relatively open,where open calls and evaluations are often involved.Therefore,these algorithms are quite transparent,avoiding potential Figure 1 is the encryption process of a block cipher.In a block cipher,generating and storing the key stream is not required;so,these algorithms are often applied in the situation where the storage space is limited.Currently,the cryptanalysis and design processes of block ciphers are relatively open,where open calls and evaluations are often involved.Therefore,these algorithms are quite transparent,avoiding potential nformation security involves many aspects.For example,in terms of the requirements for security,it involves confidentiality,integrity,availability,authentication and non-repudiation.But in any case,cryptography is an important technology for information security.

Cryptography is an interdisciplinary study fullof challenges with a long and colorful history.The Egyptian used simple encryption methods to pass secret messages more than 4 000 years ago.During the two world wars,cryptography played a significant role.

The research and application of cryptographic technologies in the early days were mainly for military,diplomatic and government activities.But things have changed since the 1960s.The rapid development of computer and communication systems forced people to think how to securely complete various transactions via computer and communication networks.As a result,the cryptographic technologies have been widely applied in civilactivities as well,which,in return,has promoted the development of cryptography.attacks from design traps and giving the user the confidence in the security strength.Moreover,the open evaluation process greatly promotes the development of the block cipher techniques.

◀Figure 1.Encryption process in block cipher.

On May 13,1973,the USfederal government launched an open call for protecting its computer data during transmission or in storage.This action stimulated the research in the DES.Among the public invited candidates,Lucifer,a scheme developed by IBM Corporation,was selected.On March 17,1975,the USNational Bureau of Standards（NBS）published the algorithm and asked for open evaluation.In January 1977,NBSannounced that this IBM algorithm was specified as the encryption standard for sensitive but non-classified information of US government.DESthus became a Federal Information Processing Standard（FIPS）of America,i.e.,FIPS-46,which took effect on July 15,1977.But a reevaluation is done every five years by the USNational Security Agency（NSA）to determine whether DESshould be reaffirmed as the federal encryption standard.

In 1997,the USNational Institute of Standards and Technology（NIST,formerly NBS）,after reevaluating DES,announced that DESwas no longer secure enough to protect the federal government's information,and suggested invalidating the related standards.As a result,DEShas been only a part of Triple Data Encryption Standard（TDES）since then.Meanwhile,NISTpublicly called for new encryption primitive as its data encryption standard,i.e.,the Advanced Encryption Standard（AES）［4］.According to the selection criteria,the new algorithm must be 128 bits in block length and support variable-length key（e.g.,128,192 or 256 bits）.In 1998,the NISTpublished the collected 15 block ciphers at the first call-for-primitives meeting,and invited cryptology research agencies around the world to evaluate those algorithms regarding security and other issues.In 1999,NISTselected five out of the 15 ciphers as the candidates of AES:MARS,RC6,Rijndael,Serpent and Twofish.Based on the final evaluation result,Rijndael was specified as the new data encryption standard,and was released as FIPS-197 in December 2001.

The European Commission launched the New European Schemes for Signatures,Integrity,and Encryption（NESSIE）project［5］in January 2000.The main objective of the project is to evaluate a portfolio of cryptographic primitives,including block ciphers and stream ciphers,in terms of security,efficiency and flexibility.Up to September 2000,17 block cipher schemes have been obtained.

Meanwhile,the NESSIEproject included TDESand AESin its evaluation range and used them as benchmarks for evaluating the block cipher schemes.After two phases'selection in three years,the NESSIEproject finally selected the following algorithms as recommended block ciphers:MISTY164,Camllia128,AES128 and SHACAL-2.

In 2000,the Japanese Government set up Cryptography Research and Evaluation Committees（CRYPTREC）［6］.This Committee,like the European NESSIEproject,aims to evaluate the security and efficiency of cryptographic techniques for government use.Its evaluation covers 4 parts:symmetric key algorithms,asymmetric key algorithms,Hash functions,and random number generators.In the early months of 2002,the Committee drafted a recommended ciphers list,and in March 2003,it finalized the list,in which the block ciphers include:

·64-bit ciphers:CIPHERUNICORN-E,MISTY1［Ma00］and 3-keyTDES.

·128-bit ciphers:Camellia,CIPHERUNICORN-A,Hierocrypt-3,SC2000 and Rijndael128.

Currently,the design and analysis of block ciphers are stillthe focus of cryptographic research.In terms of design,researchers are looking for better cryptographic techniques to make a breakthrough in security and efficiency.As for analysis,the theory for proving security,the security in application,and new attack methods need further and profound study.In addition,developing new stream ciphers and Hash functions using block cipher techniques is of a

great concern for researchers.

1.2 Stream Cipher

The theoretical basis of the stream cipher is one-time pad.Astream cipher works on the following principle:it first generates a random key stream,which is of the same length as the plaintext message,then it combines this key stream with the plaintext bit by bit to produce the ciphertext.The decryption process is exactly the inverse of the encryption process.According to the study of Claude E.Shannon,this encryption process can enable a complete secrecy.However,in reality,it is impossible to generate a completely random key stream;only a pseudorandom key stream can be generated.

There is a memory component（storage）in stream cipher to store the generated key stream.Depending on whether or not the key stream is independent of the data（plaintext and ciphertext）,the stream ciphers are further divided into synchronous stream ciphers（as shown in Figure 2）and self-synchronizing stream ciphers（Figure 3）.

The stream ciphers were originally applied in government organizations and in military.Therefore,unlike block ciphers,there are no recognized international standards for stream ciphers,and most designs and cryptanalysis are confidential.But with the increasing demand and wide application of stream ciphers,their designs and analysis have gradually been put out for open call and evaluation.

▲Figure 2. Synchronous stream cipher process.

The NESSIEproject was the first one to start the open call process.

The NESSIEproject selected 6 stream ciphers for second-phase evaluation:Leviathan,UIi-128,BMGL,SOBER-t32,SOBER-tl and SNOW.However,all of them were finally rejected because they did not meet the NESSIE selection criteria.

In March 2003,CRYPTREC recommended 3 stream ciphers:MUGI,MULTI-S01 and RC4-128.

The European Network of Excellence for Cryptology（ECRYPT）［7］is a 4-year project funded by the Information Societies Technology（IST）Programme of the European Commission's Sixth Framework Programme（FP6）.This project was launched in February 2004,and consists five virtual laboratories:Symmetric Techniques Virtual Lab（STVL）,Asymmetric Techniques Virtual Lab（AZTEC）,Protocols Virtual Lab（PROVILAB）,Secure and Efficient Implementations Virtual Lab（VAMPIRE）and Watermarking and Perceptual Hashing Virtual Lab（WAVILA）.STVL hosted an open call for stream cipher primitives as a result of the discussion in the State of the Art of Stream Ciphers（SASC）workshop held in Belgium on November 14-15,2004.This open call,which can be regarded as an addition to the NESSIEproject where no stream cipher was obtained,was published in November 2004 and ended on April 29,2005.Atotalof 34 stream ciphers were obtained during the open call,and their third-phase evaluation began in April 2007.Among these stream ciphers collected,the candidates for software design are CryptMT（Version3）,Dragon,HC（HC-128 and HC-256）,LEX（LEX-128,LEX-192 and LEX-256）,NLS（NLSv2 encryption）,Rabbit,Salsa20 and SOSEMANUK;and the candidates for hardware design include DECIM（DECIMv2 and DECIM-128）,Edon80,F-FCSR（F-FCSR-Hv2 and F-FCSR-16）,Grain（Grainv1 and Grain-128）,MICKEY（MICKEY2.0 and MICKEY-1282.0）,Moustique,Pomaranch（Version 3）and Trivium.

The current research on stream ciphers focuses on two aspects listed below:

（1）Criteria for evaluating the key stream

Usually,the key stream is evaluated with Golomb's three randomness standard.Besides,it is required to conduct randomness tests for specific items,including frequency,sequence,poker,autocorrelation and excursion,as well as the complexity test to examine the unpredictability of the key stream.However,it is still unknown what kind of key stream can be regarded as secure and reliable.

（2）Approaches to construct high-linear complexity and long-period key streams

Currently,the most popular key stream generators include Linear Feedback Shift Register（LFSR）-based feedforward generator,nonlinear combination generator,clocked generator and key generator based on block cipher techniques.

2 Hash Function

Hash function is a function that transforms a variable-size 0-1 input into a fixed-size 0-1 string.The output string is called the hash value of the input.A secure Hash function must meet the following conditions:

·The output string must be at least 128 bits to resist the birthday attack.

·For a given input,its hash value is easy to be computed（a Hash function is often very efficient）.

·For a given Hash function,it is computationally infeasible to find some input even if the hash value is known（image attack resistance）.

·For a given Hash function and a given message,it is computationally infeasible to find another message whose hash value is equal to that of the given message（preimage attack resistance）.

·For a given Hash function,it is computationally infeasible to find any two messages whose hash values are equal（collision attack resistance）.

Hash functions are mainly used in construction of message authentication algorithm,password protection,bit commitment protocol,random number generation and digital signature scheme.

Of all Hash algorithms,MD-series and SHA-series are the most popular.Before 2004,the cryptanalysis of these algorithms did not have any breakthrough,which gave people confidence in their security and had widely applied these algorithms in network communication protocols.But in 2004,a Chinese cryptographist,Professor Wang Xiaoyun,and her team,developed new techniques for manually computing the complexity of collision attacks on MD4.They also developed the techniques to reduce the computational complexity of searching collision for MD5 and for SHA-1 to 239 and 263 respectively［9-10］.Their excellent work overthrew people's confidence in these algorithms and has forced cryptographists to reevaluate the security strength of current Hash algorithms,as well as to work out new Hash functions.

Figure 3.▶Self-synchronous stream cipher process.

▼Table 1. Duration and key lengths of cryptographic schemes （recommended by ECRYPT）

The Hash algorithms recommended in the NESSIEproject include SHA-256/384/512 and Whirlpool while the Hash algorithms recommended by CRYPTREC are RIPEMD-160 and SHA-1/256/384/512.

As to ECRYPT,it hosted a series of workshops with regard to Hash algorithm research.NISTplans to launch an open call for the new Hash function standard in 2008.

3 Asymmetric-key Algorithms

In the asymmetric-key cryptosystem,which is also called public key cryptosystem,there are two keys:public and private.It is computationally infeasible to deduce the private key from the public key.The public-key algorithm is quite slower than the symmetric-key algorithm in performance speed,but it has key management advantages over the symmetric-key one,and it generates signatures for digital messages.Furthermore,the new and better asymmetric-key ideas and schemes are gradually introduced.

3.1 Certificate Authority （CA）-based Public Key

The most important thing in public key algorithm design is the based NP-hard problem.For example,the earliest and most popular public key and signature scheme,i.e.,the RSA algorithm,is based on the factoring large integer problem.

The Diffie-Hellman（DH）key exchange scheme（named after the authors）,the Digital Signature Standard（DSS）and the ElGamal encryption system are all based on the discrete logarithm problem.Among the cryptosystems based on the discrete logarithm problem,there is a special one called Elliptic Curve Cryptography（ECC）.The advantage of this cryptosystem is that it can achieve a high level security with a quite short parameter.Therefore,it is quite suitable for the device with limited storage space,like a smart card,for instance.

In the NESSIEproject,three digital signature schemes are recommended:ECDSA,RSA-PSSand SFLASH.In March 2003,CRYPTREC recommended two public-key encryption algorithms（i.e.,RAS-OAEPand RSAES-PKCS1-v1 5）and four digital signature algorithms（i.e.,DSA,ECDSA,RSASSA-PKCS1-v1 5 and RSA-PSS）.

For over 20 years of study,cryptographers still have not completely cracked the algorithms based on the integer factoring problem and the discrete logarithm problem.This,no doubt,enhances the public's confidence in these algorithms.However,it does not mean the research on the public-key cryptosystems may be suspended.Although the up-to-date,most effective solutions for the factoring and discrete logarithm problems require a subexponential time under the original computation model,these problems have not been proved to be NPproblems yet.

Even if these problems are proved to be NPproblems,the related algorithms cannot be said secure because the algorithms based on the knapsack problem,which is an NP-complete problem,have all been broken.Besides,the introduction of quantum computer makes it possible to solve the above two problems in polynomial time［11］.Therefore,cryptographers have been looking for new difficult problems for public key algorithms.At present,the algorithms that are widely and intensively studied include code-based public key cryptosystem（e.g.,Mc Eliece,1978）,lattice-based cryptosystem（e.g.,NTRU,1996）,multivariate public-key cryptosystem（1999）and infinite group based cryptography which is based on theory（e.g.,braid group-based PKC,2000）.

3.2 ID-based public key

The identity-based cryptosystem was first proposed by Adi Shamir in 1984［12］.The main idea of the cryptosystem is to use the user's identity,such as name,IP address or email address,as the public key while the private key is sent to the user by a trusted third party,called Private Key Generator（PKG）.When Shamir proposed the idea of an ID-based cryptosystem,he also presented an ID-based digital signature scheme.However,it is not until 2001 that Dan Boneh et al［13］developed a practical and effective Identity-Based Encryption（IBE）scheme based on the bilinear pairing over elliptic curves.Currently,the ID-based schemes,including ID-based encryption,signature and protocols,come out one after the other.Thus,the efficiency of pairing computation becomes an immediate problem to be solved and is a hot topic in current research.

3.3 Cryptographic Protocols

Aprotocol is a series of steps that two or more parties agree upon to complete a specific task.In a cryptographic protocol,the participant may be a trusted party,or even an attacker.The common network communication protocols can be classified into three categories:

（1）Key Exchange Protocol

In a key exchange protocol,the two or more participating entities set up a shared key,like a session key used in a conversation.This kind of protocols may be symmetric or asymmetric（e.g.,DH key exchange protocol）.Three key exchanged protocols have been recommended by Japanese CRYPTREC:DH,ECDH and PSEC-KEM.

（2）Authentication Protocol

Authentication protocols include protocols related to identity authentication,message authentication,data source authentication and target authentication.They are used to protect the cryptosystems against attacks such as counterfeit,tamper and denial of service.The NESSIEproject recommends an authentication scheme GPS,which was developed by Ecole Normal Superieure and France Telecom.

（3）Protocols for special purposes

This category of cryptographic protocols includes electronic voting protocol,electronic cash protocol and multiparty computation protocol.

The PROVILAB of the ECRYPT Network of Excellence in Cryptology coordinates research in cryptographic protocols,and it consists of three working groups briefly described below:

·PROVI1 models and definitions,which mainly studies authentication,key agreement protocols,zero-knowledge proofs and identification protocols;

·PROVI2 secure computation protocols,which focuses on the research of efficient multiparty computation（MPC）,provable security for practical protocols and unconditionally secure protocols;

·PROVI3 rational cryptographic protocols,which coordinates research in rational behavior,economic and game-theoretic models and MPC with rational participants.

In March and July 2007,ECRYPT hosted two respective workshops on cryptographic protocols.

The cryptographic protocols are the basis for security of many distributed systems.Therefore,the security analysis of the protocols is an important subject in cryptology.The two main reasons that may bring security vulnerabilities to the protocols are the following:one is that the protocol developer misunderstands the cryptographic techniques or uses improper techniques,and the other is that the developer has not made a comprehensive study on the security demand of the specific environment before their development.Currently,two kinds of methods are used to analyze the cryptographic protocols:test with attacks,and formal analysis.In the test with attacks approach,all effective attacks will be collected and used to analyze the tested protocol one after another to see if the protocol has the capability to resist these attacks.The effectiveness of this approach largely depends on the selection of attacks.In the formal analysis,a model will be set up by adopting various languages and logic,and be used to prove the security of the protocol based on the specific assumptions,analyses and verification methods.At present,the study on formal analysis is hot in the industry.However,no progress has been achieved in terms of its application.