The Introduction to Encryption II

Chia sẻ: Huy Hoang | Ngày: | Loại File: PDF | Số trang:29

Thêm vào BST

Báo xấu

126
lượt xem 20
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

This is the second of two of the most important classes we have the privilege to teach as part of the SANS Security Essentials course. In the first course, we went on a quick tour of some of the important issues and concepts in the field of cryptography. We saw that encryption is real, it is crucial, it is a foundation of so much that happens in the world around us today --and, most of it in a manner that is completely transparent to us.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: The Introduction to Encryption II

Introduction to Encryption II Security Essentials The SANS Institute Encryption and Exploits - SANS ©2001 1 This is the second of two of the most important classes we have the privilege to teach as part of the SANS Security Essentials course. In the first course, we went on a quick tour of some of the important issues and concepts in the field of cryptography. We saw that encryption is real, it is crucial, it is a foundation of so much that happens in the world around us today --and, most of it in a manner that is completely transparent to us. I guess you know that one of SANS’ mottos is, “Never teach anything in a class which the student can’t use at work the next day.” One of our goals in this course is to help you be aware of how cryptography operates under the covers in some of the major cryptosystems which are used on a 24x7 basis in our world. Along the way, we’ll share some hard-earned pragmatic lessons we’ve learned, and hope that our experience will be of help to you. Enjoy! 2-1
Why Do I Care About Crypto? U.S. Dept. of Commerce Public Key Infrastructure (PKI) no longer supports DES... Digital Certificates National Institute of Standards Digital Signatures E-Business and Technology (NIST) is E-Commerce leading the development of AES Distributed Denial of Service --the replacement for DES... Privacy attack daemon found to be protected by “blowfish” Mobile Code --a DES-like block cipher... Smart Cards “Adversary” The Internet Insecure Global Networks “Alice” “Bob” Communications in the presence of adversaries… Confidentiality Integrity Authentication Non-repudiation Encryption II - SANS ©2001 2 Without cryptography, there is no e-business, no viable e-commerce infrastructures, no military presence on the Internet and no privacy for the citizens of the world. There are numerous and continually increasing everyday instances in which we encounter cryptosystems at work and at play, often without even realizing it. The underlying cryptographic infrastructure actually works so well that we only take notice when it is absent, or implemented incorrectly! When you use a secure mobile telephone, all communications between you and the party on the other end are rapidly encrypted and decrypted on the fly, so that any eavesdropper will not be able to listen in on your conversation. Every once in awhile, we hear how the confidential communication of a public figure was intercepted and his or her privacy compromised. Yet another example of not using cryptographically enabled products. One of the more important emerging applications of cryptographically-enabled communications is at e-commerce-enabled web sites on the Internet and the World Wide Web. When supported with an enterprise-wide Public Key Infrastructure (PKI), a whole suite of new and innovative products and services is instantly enabled. Today, this is leading to new business opportunities, new capabilities being delivered to consumers, new functionality provided by organizations to their shareholders, fundamental changes in the way entire industries function, new legislation, tapping into global opportunities, etc. 2-2
Course Objectives • Concepts in Cryptography • Secret (Symmetric) Key Systems – Triple-DES – AES • Public (Asymmetric) Key Systems – RSA – ECC Encryption II - SANS ©2001 3 We begin this course by examining the conceptual underpinnings behind major cryptosystems that are in use today. In particular, we’ll look at Triple-DES which is a good alternative for the now obsolete DES algorithm, which is officially no longer considered to be secure. Next, we’ll stop by for a quick status update on the development activity that is currently underway throughout the global cryptographic community in connection with the new Advanced Encryption Standard (AES). Our next stop will be the RSA algorithm, which is a widely implemented public key cryptographic algorithm, and which came off-patent in September 2000. We’ll perform an exercise in which we’ll walk through a highly simplified version of the mathematical mechanism upon which the RSA algorithm is based. We’ll wrap up this course by considering the characteristics of emerging Elliptic Curve Cryptosystems (ECC), which are rapidly growing in popularity due to the proliferation of such devices as PDAs, mobile telephones, information appliances, ATMs, and smart cards. All right. Enough of the big picture. Let’s dive right into it… 2-3
Concepts in Cryptography 1 Confidentiality Integrity of Data Authentication Non-repudiation • What if… – we can find a mathematical “problem” that exhibits characteristics of one-way functions (with trapdoors)? • Probability Theory – or, as mathematicians would prefer to say, • Information Theory a problem that is “impossible” to solve in • Complexity Theory • Number Theory polynomial time? • Abstract Algebra • Finite Fields • Hmm… – we could use it to build a new cryptosystem! Encryption II - SANS ©2001 4 You’ll recognize the four important characteristics of cryptosystems that are at the top of this slide: Confidentiality, Integrity of Data, Authentication, and Non-repudiation. We covered this material in Encryption I. So we know that these are important characteristics that any good cryptosystem must have. But, how do we go about actually constructing such a cryptosystem? Where do we begin? Mathematics comes to our rescue. In general, there are many fields in mathematics that contain concepts that could prove to be useful as we seek to build a cryptosystem. Specifically, we find that the following branches of mathematics are particularly rich in ideas we could use: Probability Theory, Information Theory, Complexity Theory, Number Theory, Abstract Algebra, and Finite Fields. In Encryption I, we were introduced to one-way mathematical functions. We saw how such functions which have “trapdoors” have interesting properties that could prove to be useful in cryptography. We are using the term “trapdoor” to refer to a way to decrypt a message using a different key. So with public key cryptography, one would encrypt the message with a public key. The “trapdoor” would be the corresponding private key that would be used to decrypt or retrieve the message. If the one-way function deals with a “hard” mathematical problem – one that is impossible to solve in polynomial time – then it could be used to make things very difficult for any adversary who might be eavesdropping on our communications over an insecure public network like the global Internet. At the same time, the existence of a “trapdoor” could be used to provide an easy solution to the “intractable” problem for use by the sender and/or the recipient. Hmmm... 2-4
Concepts in Cryptography 2 Computational Complexity deals with time and space requirements for the execution of algorithms. This is exactly the Problems can be classified as class of problems we are looking for! tractable or intractable. Tractable Problems Intractable Problems “Easy” problems. Can be solved in polynomial “Hard” problems. Cannot be solved in polynomial time (i.e. “quickly”) for certain inputs time (i.e. “quickly”) Examples: Examples: • constant problems • exponential or super-polynomial problems • linear problems • factoring large integers into primes (RSA) • quadratic problems • solving the discrete logarithm problem (El Gamal) • cubic problems • computing elliptic curves in a finite field (ECC) Encryption II - SANS ©2001 5 Following this train of thought, let’s see what hard or intractable problems are already well-known in mathematics. These problems just might provide us with the building blocks upon which we could build our cryptosystem. Computational complexity is a branch of mathematics which studies time and space requirements for the execution of algorithms. It classifies problems as either tractable (easy to solve) or intractable (hard to solve). This is really neat, because its exactly what we’re looking for. It turns out that there are many well-known intractable problems – the class of problems we’re interested in. These exponential or super-polynomial problems are “hard” problems which cannot be solved in polynomial time (i.e., quickly). Actually, it is more accurate to say that these problems are believed to be intractable by the worldwide mathematical community that is active in researching issues in the field of computation complexity. Three well-known examples of intractable problems include: factoring large integers into their two prime factors (the basis for RSA); solving the discrete logarithm problem over finite fields (the basis for ElGamal); and computing elliptic curves over finite fields (the basis for Elliptic Curve Cryptosystems). Now, let’s examine each of these three important classes of intractable problems in greater detail, as each one of them forms the basis of important cryptosystems that are widely used all over the world today. 2-5
Concepts in Cryptography 3 An Example of an Intractable Problem... Difficulty of factoring a large integer into its two prime factors • A “hard” problem Example: RSA • Years of intense public scrutiny • based on difficulty of factoring a large integer suggest intractability into its prime factors • No mathematical proof so far • ~1000 times slower than DES • considered “secure” • de facto standard • patent expires in 2000 Encryption II - SANS ©2001 6 Every middle school student knows how to factor integers. So, given an integer 15, they can immediately respond that the integer factors are 1x15 and 3x5. Easy enough! So why is this a hard problem? Why is it on our list of intractable problems? It turns out that the key here – no pun intended – is the word “large.” Factoring a large integer into its prime factors is decidedly non-trivial. In fact, there is no easy solution to the problem. This is the general consensus of the global community that actively researches such mathematical topics. It is important to note, however, that there is no unequivocal mathematical “proof” that this problem cannot be solved easily. It’s the years of public scrutiny of the problem that leads us to conclude that it is a hard problem which cannot be solved in polynomial time. For our purposes, this is good enough to build a cryptosystem upon. Actually...that’s already been done! The most widely used example is the RSA algorithm, which takes advantage of the intractability of the integer factorization problem to build the public key (asymmetric) cryptosystem which is widely used throughout the world. How about some of the other intractable problems we found from our brief survey of the field of mathematics? Can they also be used to construct cryptosystems? Great question! Glad you asked. 2-6
Concepts in Cryptography 4 Another Intractable Problem... Difficulty of solving the discrete logarithm problem --for finite fields • A “hard” problem Examples • Years of intense public scrutiny • El Gamal encryption and signature schemes suggest intractability • Diffie-Hellman key • No mathematical proof so far agreement scheme • Schnorr signature • The discrete logarithm problem scheme is as difficult as the problem of • NIST’s Digital Signature Algorithm (DSA) factoring a large integer into its prime factors Encryption II - SANS ©2001 7 Another intractable problem that appears to have useful properties that we can use to build a cryptosystem upon is the difficulty of solving what is known as the discrete logarithm problem for finite fields. The mathematics behind this type of problem are complex and we will not attempt an explanation of the working mechanism in this brief course. It turns out that there is no easy solution to this problem either. Again, this is the general consensus of the global community that actively researches such mathematical topics. It is important to note, however, that there is no unequivocal mathematical “proof” that this problem cannot be solved easily. It’s the years of public scrutiny of the problem that leads us to conclude that it is a hard problem which cannot be solved in polynomial time. But, how does it compare with the previous intractable problem we looked at – the factorization of large integers into their two prime factors? There is evidence that the discrete logarithm problem is just as difficult. So, we should be able to use this problem in building a cryptosystem? Right? Absolutely! Again...that’s already been done! The following cryptosystems are all built upon the intractability of the discrete logarithm problem over finite fields: the ElGamal encryption and signature schemes, the Diffie-Hellman key agreement scheme, the Schnorr signature scheme, and the Digital Signature Algorithm (DSA) by the U.S. Department of Commerce’s National Institute of Standards and Technology (NIST). 2-7
Concepts in Cryptography 5 Yet Another Intractable Problem... Difficulty of solving the discrete logarithm problem --as applied to elliptic curves Examples • Elliptic curve El Gamal • A “hard” problem encryption and signature • Years of intense public scrutiny schemes • Elliptic curve Diffie-Hellman suggest intractability key agreement scheme • No mathematical proof so far • Elliptic curve Schnorr signature scheme • In general, elliptic curve • Elliptic Curve Digital cryptosystems (ECC) offer Signature Algorithm (ECDSA) higher speed, lower power consumption, and tighter code Encryption II - SANS ©2001 8 Now, let’s take a quick look at yet another class of intractable problems. This one involves the difficulty of solving the discrete logarithm problem (we just discussed it in the previous slide) as applied to elliptic curves. So, how does this class of intractable problem compare with the previous intractable problem we’ve looked at – the factorization of large integers into their two prime factors, and solving the discrete logarithm problem over finite fields? Very well, thank you! And…it has a number of very attractive features to boot. Features that include high security levels even at low key lengths, high speed processing, and low power and storage requirements. These characteristics are very useful in crypto-enabling the many new devices that are rapidly appearing in the marketplace, e.g. mobile telephones, information appliances, smart cards, and even the venerable ATMs. Of course it has been broken a few times so they are still working on this one. 2-8
Voila! We Can Now Build... Communications in the presence of adversaries… Confidentiality Integrity Authentication Non-repudiation Confidentiality! Original Document “Alice” first creates a Hash of the Original ---------- Digital Hash Document. Next, she encrypts the Hash Ciphertext Hash Alice encrypts Signature with her Private Key to generate a Digital or Algorithm with her Signature. Finally, she transmits the plaintext Private Key Original Document and the Digital Signature to “Bob.” Authentication! Non-repudiation! Original Document ---------- Integrity of Data! “Bob” first creates a Hash of the Original Hash Ciphertext Same Hash Document. Next, he decrypts the Digital or Bob compares Algorithm Signature with Alice’s Public Key to plaintext the two hashes regenerate the Hash that Alice originally created. Finally, he compares the two Digital Hash Hashes. A match indicates the Original Signature Bob decrypts Document was not tampered with. with Alice’s Public Key Encryption II - SANS ©2001 9 We started out by noting that communicating in the presence of adversaries meant constructing a cryptosystem that was capable of providing support for important requirements such as Confidentiality, Integrity of Data, Authentication, and Non-repudiation. We briefly examined some of the well-known intractable mathematical problems which could be used as building blocks upon which to construct our cryptosystem. But how do we make the connection between complex and abstract mathematical concepts, to crypto-enabled products we use routinely every day of our lives? While each type of cryptosystem addresses the specific details in its own unique way, the fundamental concepts behind the working crypto-mechanism that actually delivers the functionality that makes it possible to support Confidentiality, Integrity of Data, Authentication, and Non- repudiation are fundamentally quite similar. This “big picture” slide puts it all together from the perspective of a message being sent by Alice over an insecure public network (like the global Internet) to Bob. Please study this slide carefully for a few moments, and trace the working mechanism that is at the foundation of many cryptosystems. See for yourself exactly how the users of the cryptosystem are able to tap into the Confidentiality, Integrity of Data, Authentication, and Non-repudiation services that are supported by the cryptosystem. 2-9
Milestones in Cryptography Origins of Cryptography RSA AES: Advanced Encryption Standard (traced as far back as 4000 years! (Rivest, Shamir, Adleman, 1978) (sponsored by NIST, finalist selected.) Index of Coincidence Public-Key Encryption (Friedman, 1918) (Rabin, 1979) Vernam Cipher Public-Key Encryption & Signature (Vernam, 1926) (ElGamal, 1985) Secure Communications Elliptic Curve Cryptography …built upon (Shannon, 1949) (Miller, 1986 & Koblitz, 1987) Lucifer Cryptosystem ECA: Elliptic Curve Algorithm the work of (Feistel, 1974) (Lenstra, 1987) giants! Public-Key Cryptography Differential Cryptanalysis (Diffie and Hellman, 1976) (Biham and Shamir, 1993) Key-Exchange Method X.509 v3 Digital Certificates (Diffie and Hellman, 1976) (ITU-T, 1993) DES: Data Encryption Standard Linear Cryptanalysis (U.S. FIPS-46, 1977) (Matsui, 1994) Public-Key Cryptography ... (Merkle, 1978) Encryption II - SANS ©2001 10 We noted earlier in our discussion that a number of mathematicians and researchers had made important contributions, over the years, to the advanced mathematical ideas that serve as the foundation of many widely used cryptosystems in use today. We also noted that each of the three classes of intractable problems we discussed had been successfully employed as building blocks for constructing cryptosystems. There is a long, rich history behind modern cryptosystems. This slide lists a few (by no means, all!) of the leading cryptographers whose work and ideas have been successfully incorporated into everyday products that we use on a routine basis. Modern day cryptosystems are truly built upon the work of giants! The mathematics behind cryptosystems is invariably abstract and can be highly complex. The process of developing new cryptographic algorithms works best when the attention of the entire global cryptographic community can be focused on the development activity. It is generally acknowledged that openness to intense scrutiny by the global cryptographic community in the development process of new cryptographic algorithms is the most effective way to achieving algorithms that can be trusted to serve as the foundation of our growing ecommerce infrastructure. The U.S. Department of Commerce’s NIST has done just that as it selected the finalist for the Advanced Encryption Standard (AES). 2 - 10
DES: Data Encryption Standard • Released March 17, 1975 • Rather fast encryption algorithm • Widely used; a de facto standard • Symmetric-key, 64-bit block cipher • 56-bit key size Small 256 key space • Today, DES is not considered secure Encryption II - SANS ©2001 11 DES is the most commonly used encryption algorithm in the world. On March 17, 1975, the United States government proposed the adoption of the Data Encryption Standard (DES) cryptosystem as a national standard for use with “unclassified computer data.” It was based upon IBM’s Lucifer cryptosystem. DES is specified in FIPS-42. The Data Encryption Algorithm (DEA) is essentially the same cipher based on the ANSI X.3.92 standard. Due to the internal bit-oriented operations in the design of DES, software implementations of DES are slow, while hardware implementations are faster. Four different modes of operation for DES were standardized for use in the USA by the National Institute of Standards and Technology (NIST): Electronic Code Book (ECB) mode, Cipher Block Chaining (CBC) mode, Output Feedback (OFB) mode, and Cipher Feedback (CFB) mode. From the very beginning, concerns were raised about the vulnerability of DES due to the rather small key length of 56 bits, resulting in a keyspace containing only 256 possible different keys. The effectiveness of attacks based on brute force searches depends upon the size of the keyspace involved. Because DES is limited to an effective key size of only 56-bits (= 64-bit block - 8 parity bits), it is vulnerable to brute force attacks. DES was first [publicly] cracked in in theRSA Challenge, which was a five month effort, and subsequent attempts are taking less and less time. At the present time, there is a general consensus that DES is not secure. 2 - 11
DES • In 1992 it was proven that DES is not a group. This means that multiple DES encryptions are not equivalent to a single encryption. THIS IS A GOOD THING. • If something is a group than – E(E(K,M)K2) = E(K3,M) • Since DES is not a group, multiple encryptions will increase the security. Encryption II - SANS ©2001 12 As we know, DES is no longer supported because of the key length. With current technology and computers, this key length is considered non-secure. For additional information, see the book Cracking DES. It gives you all of the code you would need to build your own DES cracking engine. Just think, you would be the envy of the entire neighborhood! Since DES is weak, someone proposed whether you could perform multiple encipherments to increase the key length. In order to do this, you would have to prove whether DES is a group or not. It was proven that DES is not a group; this means that multiple DES encryptions are not equivalent to a single encryption. This is a very good thing. If DES was a group, then triple DES would provide the same key length as single DES. Since DES is not a group, multiple encryptions will increase the security. If something is a group, then E(E(K,M)K2) = E(K3,M), which means multiple encipherments are equivalent to a single encipherment. 2 - 12
DES Weaknesses • DES is considered non-secure for very sensitive encryption. It is crackable in a short period of time. • See the “Cracking DES” book by O’Reilly. • Multiple encryptions and key size will increase the security. • Double DES is vulnerable to the meet-in-the- middle attack and only has an effective key length of 57 bits. • Triple DES is preferred. Encryption II - SANS ©2001 13 Now that we know that multiple enchipherments of DES will help the key length, why “triple” DES? What happened to double DES, and why isn’t it used? Funny thing you should ask. It turns out that double DES is vulnerable to the meet-in-the-middle attack, which gives an effective key length of 57 bits, which is only one more bit more than DES. So because of this weakness, triple DES is used. We will look at the meet-in-the-middle attack on the next slide. 2 - 13
Meet-in-the-middle Attack K1 K2 M E C’ C E E C C’ M D D E(M,K1) = C’ , 2 56 possibilities D(C,K2) = C’ , 2 56 possibilities K2 2 56 + 2 56 = 2 57 K1 so double DES only gives effective key length of 57 bits which is 1 more than DES Encryption II - SANS ©2001 14 With the meet-in-the-middle attack, you start with both the message and the ciphertext. In this case M and C. For each choice of K1 compute C’=E(K1,M) – this is a table of 2 56 For each choice of K2 compute C”=D(K2, C) – this is a table of 2 56 Therefore the amount of keys tried is 256 + 256 = 257, which gives an effective key length of 57 bits. Now when you play Geek Trivial Pursuit and someone asks, “Why isn’t double DES used?”, you will know the answer! 2 - 14
Triple-DES 3 One round 64-bit plaintext Li-1 Ri-1 of DES Initial Permutation f Ki 16 rounds (iterations) of function f ⊕ 2 Li Ri Final Permutation In Triple-DES, the DES algorithm, shown 64-bit ciphertext on the left, is applied three times, and two different crypto-variables are used. Encryption II - SANS ©2001 15 Earlier in this discussion and also in Encryption I, we noted that the Data Encryption Standard (DES) is no longer -- officially -- considered to be secure. We also noted that the Advanced Encryption Standard (AES) is currently under development as we implement the chosen standard. In the meantime, the global e-commerce infrastructure build-out is proceeding at a furious pace, due to all the new e-business initiatives that are sprouting up all over the world. The need for a fast symmetric key block cipher is extremely urgent. If DES can no longer be considered to be secure, what can we do in the interim? Well, there are a number of alternative and fast symmetric key block ciphers that are available today, and which can be used instead of DES. However, it turns out that while DES is definitely not to be considered as a secure algorithm, there are derived algorithms that use DES at their core which can still be considered to be secure and can be used. Specifically, the Triple-DES algorithm is an example of one such derived algorithm, and it is a viable option which can be used in place of DES -- at least until AES is officially selected and becomes available. This slide shows the mechanism of the Triple-DES algorithm. Note, that it looks (not surprisingly!) a lot like the DES algorithm. It is the unique way in which the DES algorithm is applied three times, with two different crypto-variables, that makes Triple-DES secure enough to use in the interim between DES and AES. 2 - 15
Triple-DES USAGE VULNERABILITIES Supported in latest releases Cracking Triple-DES means of Web clients, such as examining all possible pairs Microsoft Internet Explorer of crypto-variables (a task & Netscape Communicator considered to be beyond today’s technology) Prefer Triple-DES over DES (which is --officially -- no So far, there have been no longer considered to be public reports claiming to secure) have cracked Triple-DES... Encryption II - SANS ©2001 16 Triple-DES is a well-known and widely implemented algorithm which has been intensely scrutinized by the global cryptographic community. See the ANSI X9.52 standard for additional information on Triple-DES encryption. Support for Triple-DES is built right into popular web clients, such as the Microsoft Internet Explorer and the Netscape Communicator. Using Triple-DES from the end user perspective is often as simple as simply reconfiguring the SSL v3.0 service in the web client to prefer Triple-DES over DES. As an aside – when was the last time you configured the SSL v3.0 service in your Web client? Have you disabled SSL v2.0, which is vulnerable to man-in-the-middle attacks? If not, then whenever you browse your way to an incorrectly configured SSL-enabled web site on the global Internet, you might end up using SSL v2.0 with DES in your communications with that web site. This may or may not be a problem for you, depending on the sensitivity of your communications. But, it might be worth taking some time to verify that your web client is configured as you’d like it to be. 2 - 16
AES • Advanced Encryption Standard • AES is a new encryption algorithm(s) that is being designed to be effective well into the 21st century THE FIVE “AES” FINALISTS ! • MARS IBM Countdown • RC6™ RSA Laboratories to AES ! • Rijndael Joan Daemen, Vincent Rijmen • 1/2/1997, the quest for • Serpent Ross Anderson, Eli Biham, Lars Knudsen AES begins... • Twofish Bruce Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall, Niels Ferguson • 8/9/1999, five finalist algorithms announced Significance • Announced winner - Developing “good” cryptographic algorithms that can be trusted is Rijndeal hard. The only practical way to develop such algorithms is to perform the development process in an open manner, and under intense public scrutiny of the global cryptographic community. Can you think of a recent example in which this was not followed? Encryption II - SANS ©2001 17 On January 2, 1997, NIST announced the initiation of an effort to develop the Advanced Encryption Standard (AES). A formal call for algorithms was made on September 12, 1997. The call stipulated that the AES must specify an unclassified, publicly disclosed encryption algorithm(s), available royalty-free, worldwide. In addition, the algorithm(s) would implement symmetric key cryptography as a block cipher and (at a minimum) support a block size of 128-bits and key sizes of 128, 192, and 256-bits. The evaluation criteria were divided into three major categories: Security, Cost, and Algorithm and Implementation Characteristics. In October, 2000, NIST selected a finalist for the Advanced Encyption Standard (AES). The two researchers who developed Rijndael (pronounced “Rain Doll” or “Rhine Dahl”) for the AES are from Belgium: Dr. Joan Daemen (Yo'-ahn Dah'-mun) of Proton World International and Dr. Vincent Rijmen (Rye'-mun) of Katholieke Universiteit Leuven. The AES will supplant the inadequate 56-bit key Data Encryption Standard (DES), which is to be used only in legacy systems. AES has three key sizes: 128-bit, 192-bit, and 256-bit. Testing of the algorithm was performed by NIST and the Canadian Commiunications Security Establishment (CSE). 2 - 17
AES Algorithm Cipher (byte in[4*Nb], byte out[4*Nb], word w[Nb*(Nr+1)]) begin byte state[4,Nb] state = in AddRoundKey(state, w) for round = 1 step 1 to Nr-1 SubBytes(state) ShiftRows(state) MixColumns(state) AddRoundKey(state, w+round*Nb) end for SubBytes(state) ShiftRows(state) AddRoundKey(state, w+Nr*Nb) out = state end Encryption II - SANS ©2001 18 After all this build-up, here's the AES algorithm in pseudo-code. There are three parameters passed to this program: • in[] is an array containing the block of plaintext. In general, in[] is 4*Nb bytes in size, meaning 16 bytes in the current AES specification. • out[] is an array containing the ciphertext and is also 4*Nb bytes in size. • w[] is the array containing the Expanded Key and is Nb*(Nr+1) words in size. The code also shows one additional data structure, namely state[], a two-dimensional array containing the current value of the transformed ciphertext. The transformations themselves are defined by four function calls, namely AddRoundKey(), SubBytes(), ShiftRows(), and MixColumns(); the specifics of these transformations are described on the next page. The code is then pretty straightforward: • The plaintext is moved into the state[] array • The first Round Key is applied • There are then Nr-1 rounds that apply all four transformations • The final round applies all but the MixColumns() transformation • The state[] array is moved into the ciphertext data structure 2 - 18
AES Basic Functions • AES algorithm employs four basic transformations: – AddRoundKey: XOR Round Key with State – SubBytes: Substitute bytes in State s to form State s' on a byte-for-byte basis using S-box – ShiftRows: Left circular shift of rows 1-3 in State s by 1, 2, and 3 bytes, respectively – MixColumns: Apply mathematical transformation to each column in State s to form State s' Encryption II - SANS ©2001 19 The four AES transformations act as follows: • AddRoundKey: Takes the appropriate Round Key and performs a bit-by-bit XOR with the current State • SubBytes: Using a Substitution box (S-box) defined in the specification, substitutes each 8-bit quantity in the State array to a different 8-bit value. • ShiftRows: Left circularly shift the contents of State array rows 1, 2, and 3 by 1, 2, and 3 bytes, respectively. A "left circular shift of one byte," for example, means that the bytes in columns 1, 2, and 3 move to position 0, 1, and 2, respectively, the value in byte position 0 moves to position 3. • MixColumns: Another byte value substitution, but in this case performed on a column (32 bit) basis; i.e., rather than perform an S-box substitution on a per byte basis, this transformation applies a polynomial transformation on four bytes at a time. 2 - 19
AES VULNERABILITIES USAGE Too early to tell… The AES algorithm is being developed to replace DES, At the moment, the which is no longer officially algorithm(s) has been considered to be secure. selected. Lets see how it stands the test of time. DES/Triple-DES is very widely used throughout the So far so good…. world today, and AES is expected to be just as The NIST is spearheading popular... the selection process. Encryption II - SANS ©2001 20 The Advanced Encryption Standard (AES) development process is a splendid opportunity to see first-hand what it takes to develop a cryptographic algorithm. The development process is inherently complex, and the only realistic way to reduce the risk is to open up the development activity to all interested parties, and also to intense scrutiny by the global cryptographic community. Visit the AES web site at NIST at http://www.nist.gov/aes/ to learn more about the effort, which is still ongoing. You see, now that the algorithm is agreed on, it is important to test the implementations of the algorithm. Can you think of another recent cryptographic algorithm development effort which was not performed in an open manner with intense scrutiny by the global cryptographic community? The cryptographic algorithm was developed in relative secrecy. When it finally shipped as part of a product to end users, it was quickly cracked shortly after it was released causing significant embarrassment for the sponsors. Sure, that was the DVD encryption we discussed in the last lesson. 2 - 20