Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 4712.1Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.Chapter 12Cryptographic Hash Functions12.2Objectives To introduce general ideas behind cryptographic hash functions To discuss the Merkle-Damgard scheme as the basis for iterated hash functions To distinguish between two categories of hash functions: To discuss the structure of SHA-512.Chapter 12 To discuss the structure of Whirlpool.12.312-1 INTRODUCTION12-1 INTRODUCTIONA cryptographic hash function takes a message of A cryptographic hash function takes a message of arbitrary length and creates a message digest of fixed arbitrary length and creates a message digest of fixed length. The ultimate goal of this chapter is to discuss length. The ultimate goal of this chapter is to discuss the details of the two most promising cryptographic the details of the two most promising cryptographic hash algorithmshash algorithms SHA-512 and Whirlpool. SHA-512 and Whirlpool. 12.1.1 Iterated Hash Function12.1.2 Two Groups of Compression FunctionsTopics discussed in this section:Topics discussed in this section:12.412.1.1 Iterated Hash FunctionMerkle-Damgard SchemeFigure 12.1 Merkle-Damgard scheme12.51. The compression function is made from scratch.12.1.2 Two Groups of Compression Functions2. A symmetric-key block cipher serves as a compression function.Message Digest (MD)Whirlpool12.612.1.2 Continued12.7Rabin Scheme12.1.2 ContinuedFigure 12.2 Rabin scheme12.8Davies-Meyer Scheme12.1.2 ContinuedFigure 12.3 Davies-Meyer scheme12.9Matyas-Meyer-Oseas Scheme12.1.2 ContinuedFigure 12.4 Matyas-Meyer-Oseas scheme12.10Miyaguchi-Preneel Scheme12.1.2 ContinuedFigure 12.5 Miyaguchi-Preneel scheme12.1112-2 SHA-51212-2 SHA-512SHA-512 is the version of SHA with a 512-bit message SHA-512 is the version of SHA with a 512-bit message digest. This version, like the others in the SHA family digest. This version, like the others in the SHA family of algorithms, is based on the Merkle-Damgard of algorithms, is based on the Merkle-Damgard scheme. scheme. 12.2.1 Introduction12.2.2 Compression Function12.2.3 AnalysisTopics discussed in this section:Topics discussed in this section:12.1212.2.1 IntroductionFigure 12.6 Message digest creation SHA-51212.13Message PreparationSHA-512 insists that the length of the original message be less than 2128 bits. 12.2.1 ContinuedSHA-512 creates a 512-bit message digest out of a message less than 2128.Note12.1412.2.1 ContinuedThis example shows that the message length limitation of SHA-512 is not a serious problem. Suppose we need to send a message that is 2128 bits in length. How long does it take for a communications network with a data rate of 264 bits per second to send this message?Example 12.1SolutionA communications network that can send 264 bits per second is not yet available. Even if it were, it would take many years to send this message. This tells us that we do not need to worry about the SHA-512 message length restriction.12.1512.2.1 ContinuedThis example also concerns the message length in SHA-512. How many pages are occupied by a message of 2128 bits?Example 12.2SolutionSuppose that a character is 32, or 26, bits. Each page is less than 2048, or approximately 212, characters. So 2128 bits need at least 2128 / 218, or 2110, pages. This again shows that we need not worry about the message length restriction.12.1612.2.1 ContinuedFigure 12.7 Padding and length field in SHA-51212.1712.2.1 ContinuedWhat is the number of padding bits if the length of the original message is 2590 bits?Example 12.3SolutionWe can calculate the number of padding bits as follows:The padding consists of one 1 followed by 353 0’s.12.1812.2.1 ContinuedDo we need padding if the length of the original message is already a multiple of 1024 bits?Example 12.4SolutionYes we do, because we need to add the length field. So padding is needed to make the new block a multiple of 1024 bits.12.1912.2.1 ContinuedWhat is the minimum and maximum number of padding bits that can be added to a message?Example 12.5Solutiona. The minimum length of padding is 0 and it happens when (−M − 128) mod 1024 is 0. This means that |M| = −128 mod 1024 = 896 mod 1024 bits. In other words, the last block in the original message is 896 bits. We add a 128-bit length field to make the block complete.12.2012.2.1 ContinuedExample 12.5b) The maximum length of padding is 1023 and it happens when (−|M| −128) = 1023 mod 1024. This means that the length of the original message is |M| = (−128 −1023) mod 1024 or the length is |M| = 897 mod 1024. In this case, we cannot just add the length field because the length of the last block exceeds one bit more than 1024. So we need to add 897 bits to complete this block and create a second block of 896 bits. Now the length can be added to make this block complete.Continued12.21Words12.2.1 ContinuedFigure 12.8 A message block and the digest as words12.22Word Expansion12.2.1 ContinuedFigure 12.9 Word expansion in SHA-51212.2312.2.1 ContinuedShow how W60 is made.Example 12.6SolutionEach word in the range W16 to W79 is made from four previously-made words. W60 is made as12.24Message Digest Initialization12.2.1 Continued12.2512.2.2 Compression FunctionFigure 12.10 Compression function in SHA-51212.2612.2.2 ContinuedFigure 12.11 Structure of each round in SHA-51212.27Majority Function12.2.2 ContinuedConditional FunctionRotate Functions12.2812.2.2 Continued12.29There are 80 constants, K0 to K79, each of 64 bits. Similar These values are calculated from the first 80 prime numbers (2, 3,…, 409). For example, the 80th prime is 409, with the cubic root (409)1/3 = 7.42291412044. Converting this number to binary with only 64 bits in the fraction part, we get12.2.2 ContinuedThe fraction part: (6C44198C4A475817)1612.3012.2.2 ContinuedWe apply the Majority function on buffers A, B,