MD5 Hash

In cryptography, MD5 (Message-Digest algorithm 5) is a widely used cryptographic hash function with a 128-bit hash value. As an Internet standard (RFC 1321), MD5 has been employed in a wide variety of security applications, and is also commonly used to check the integrity of files. An MD5 hash is typically expressed as a 32 digit hexadecimal number.

MD5 is a strengthened version of MD4. Like MD4, the MD5 hash was invented by Professor Ronald Rivest of MIT. Also, MD5 was obviously used as the model for SHA-1, since they share many common features. MD5 and SHA-1 are the two most widely used hash algorithms today, but use of MD5 will certainly decline over time, since it is now considered broken 

The Algorithm 

The MD5 hash is described in RFC 1321 along with a C implementation. MD5 is similar to the MD4 hash. The padding and initialisation is identical.

MD5 operates on 32-bit words. Let M be the message to be hashed. The message M is padded so that its length (in bits) is equal to 448 modulo 512, that is, the padded message is 64 bits less than a multiple of 512. The padding consists of a single 1 bit, followed by enough zeros to pad the message to the required length. Padding is always used, even if the length of M happens to equal 448 mod 512. As a result, there is at least one bit of padding, and at most 512 bits of padding. Then the length (in bits) of the message (before padding) is appended as a 64-bit block.

The padded message is a multiple of 512 bits and, therefore, it is also a multiple of 32 bits. Let M be the message and N the number of 32-bit words in the (padded) message. Due to the padding, N is a multiple of 16.

A four-word buffer (A,B,C,D) is used to compute the message digest. Here each of A, B, C, D is a 32-bit register. These registers are initialized to the following values in hexadecimal:

word A: 01 23 45 67
word B: 89 ab cd ef

word D: 76 54 32 10

word C: fe dc ba 98

We first define four auxiliary functions that each take as input three 32-bit words and produce as output one 32-bit word.

where  is logical and,  is logical or and  is logical xor. Do the following:

/* Process each 16-word block. */

For i = 0 to N/16-1 do

    /* Copy block i into X. */

    For j = 0 to 15 do

        Set X[j] to M[i*16+j].

    end /* of loop on j */

    /* Save A as AA, B as BB, C as CC, and D as DD. */

    AA = A
BB = B

    DD = D
CC = C


    /* Round 1. */

    /* Let [abcd k s i] denote the operation

        a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */

    /* Do the following 16 operations. */

    [ABCD  0  7  1]  [DABC  1 12  2]  [CDAB  2 17  3]  [BCDA  3 22  4]
[ABCD  4  7  5]  [DABC  5 12  6]  [CDAB  6 17  7]  [BCDA  7 22  8]

    [ABCD 12  7 13]  [DABC 13 12 14]  [CDAB 14 17 15]  [BCDA 15 22 16]
[ABCD  8  7  9]  [DABC  9 12 10]  [CDAB 10 17 11]  [BCDA 11 22 12]


    /* Round 2. */

    /* Let [abcd k s i] denote the operation

        a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). */

    /* Do the following 16 operations. */

    [ABCD  1  5 17]  [DABC  6  9 18]  [CDAB 11 14 19]  [BCDA  0 20 20]
[ABCD  5  5 21]  [DABC 10  9 22]  [CDAB 15 14 23]  [BCDA  4 20 24]

    [ABCD 13  5 29]  [DABC  2  9 30]  [CDAB  7 14 31]  [BCDA 12 20 32]
[ABCD  9  5 25]  [DABC 14  9 26]  [CDAB  3 14 27]  [BCDA  8 20 28]


    /* Round 3. */

    /* Let [abcd k s t] denote the operation

        a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). */

    /* Do the following 16 operations. */

    [ABCD  5  4 33]  [DABC  8 11 34]  [CDAB 11 16 35]  [BCDA 14 23 36]
[ABCD  1  4 37]  [DABC  4 11 38]  [CDAB  7 16 39]  [BCDA 10 23 40]

    [ABCD  9  4 45]  [DABC 12 11 46]  [CDAB 15 16 47]  [BCDA  2 23 48]
[ABCD 13  4 41]  [DABC  0 11 42]  [CDAB  3 16 43]  [BCDA  6 23 44]


    /* Round 4. */

    /* Let [abcd k s t] denote the operation

        a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */

    /* Do the following 16 operations. */

    [ABCD  0  6 49]  [DABC  7 10 50]  [CDAB 14 15 51]  [BCDA  5 21 52]
[ABCD 12  6 53]  [DABC  3 10 54]  [CDAB 10 15 55]  [BCDA  1 21 56]

    [ABCD  4  6 61]  [DABC 11 10 62]  [CDAB  2 15 63]  [BCDA  9 21 64]
[ABCD  8  6 57]  [DABC 15 10 58]  [CDAB  6 15 59]  [BCDA 13 21 60]


    /* Then perform the following additions. (That is increment each

        of the four registers by the value it had before this block

        was started.) */

    A = A + AA
B = B + BB

    D = D + DD
C = C + CC


end /* of loop on i */

The algorithm above uses a set o 64 constants T[i] for i = 1 to 64. Let T[i] denote the i-th element of the table, which is equal to the integer part of 4294967296 times abs(sin(i)), where i is in radians. The elements of the table are given in the appendix of RFC 1321.

SECURE HASH ALGORITHM - SHA 512

Hashing Algorithm — SHA-512

So, SHA-512 does its work in a few stages. These stages go as follows:

1. Input formatting
2. Hash buffer initialization
3. Message Processing
4. Output

Let’s look at these one-by-one.

1. Input Formatting:

SHA-512 can’t actually hash a message input of any size, i.e. it has an input size limit. This limit is imposed by its very structure as you may see further on. The entire formatted mesage has basically three parts: the original message, padding bits, size of original message. And this should all have a combined size of a whole multiple of 1024 bits. This is because the formatted message will be processed as blocks of 1024 bits each, so each bock should have 1024 bits to work with.

<pic: original message>

Original message

Padding bits

The input message is taken and some padding bits are appended to it in order to get it to the desired length. The bits that are used for padding are simply ‘0’ bits with a leading ‘1’ (100000…000). Also, according to the algorithm, padding needs to be done, even if it is by one bit. So a single padding bit would only be a ‘1’.

The total size should be equal to 128 bits short of a multiple of 1024 since the goal is to have the formatted message size as a multiple of 1024 bits (N x 1024).

<pic: msg + pad>

Message with padding

Padding size

After this, the size of the original message given to the algorithm is appended. This size value needs to be represented in 128 bits and is the only reason that the SHA-512 has a limitation for its input message.

Since the size of the original message needs to be represented in 128 bits, the message size can be at most (2¹²⁹-1) bits and also taking into consideration the necessary single padding bit, it maximum size would then be (2¹²⁹-2). Even though this limit exists, it doesn’t actually cause a problem since the actual limit is so high (2¹²⁹-2 = 680,564,733,841,876,926,926,749,214,863,536,422,910 bits).

<pic: msg + pad +size>

Message with padding and size

Now that the padding bits and the size of the message have been appended, we are left with the completely formatted input for the SHA-512 algorithm.

Formatted Message

2. Hash buffer initialization:

The algorithm works in a way where it processes each block of 1024 bits from the message using the result from the previous block. Now, this poses a problem for the first 1024 bit block which can’t use the result from any previous processing. This problem can be solved by using a default value to be used for the first block in order to start off the process. (Have a look at the second-last diagram).

Since each intermediate result needs to be used in processing the next block, it needs to be stored somewhere for later use. This would be done by the hash buffer, this would also then hold the final hash digest of the entire processing phase of SHA-512 as the last of these ‘intermediate’ results.

So, the default values used for starting off the chain processing of each 1024 bit block are also stored into the hash buffer at the start of processing. The actual value used is of little consequence, but for those interested, the values used are obtained by taking the first 64 bits of the fractional parts of the square roots of the first 8 prime numbers (2,3,5,7,11,13,17,19). These values are called the Initial Vectors (IV).

Why 8 prime numbers instead of 9? Because the hash buffer actually consists of 8 subparts (registers) for storing them.

<pic: IV>

Hash buffer and Initialization Vector values

MESSAGE AUTHENTICATION REQUIREMENTS

In the context of communications across a network, the following attacks can be identified.

1.                                       Disclosure: Release of message contents to any person or process not possess- ing the appropriate cryptographic key.

2.                                       Traffic analysis: Discovery of the pattern of traffic between parties. In a connection-oriented application, the frequency and duration of connections could be determined. In either a connection-oriented or connectionless environ- ment, the number and length of messages between parties could be determined.

3.                                       Masquerade: Insertion of messages into the network from a fraudulent source. This includes the creation of messages by an opponent that are purported to come from an authorized entity. Also included are fraudulent acknowledg- ments of message receipt or nonreceipt by someone other than the message recipient.

4.                                       Content modification: Changes to the contents of a message, including insertion, deletion, transposition, and modification.

5.                                       Sequence modification: Any modification to a sequence of messages between parties, including insertion, deletion, and reordering.

6.                                       Timing modification: Delay or replay of messages. In a connection-oriented application, an entire session or sequence of messages could be a replay of some previous valid session, or individual messages in the sequence could be delayed or replayed. In a connectionless application, an individual message (e.g., data- gram) could be delayed or replayed.

7.                                       Source repudiation: Denial of transmission of message by source.

8.                                       Destination repudiation: Denial of receipt of message by destination.

Measures to deal with the first two attacks are in the realm of message confi- dentiality and are dealt with in Part One. Measures to deal with items (3)  through

(2)                             in the foregoing list are generally regarded as message authentication. Mechanisms for dealing specifically with item (7) come under the heading of digital signatures. Generally, a digital signature technique will also counter some or all of the attacks listed under items (3) through (6). Dealing with item (8) may require a combination of the use of digital signatures and a protocol designed to counter this attack.

In summary, message authentication is a procedure to verify that received messages come from the alleged source and have not been altered. Message authentication may also verify sequencing and timeliness. A digital signature is an authentication technique that also includes measures to counter repudiation by the source.

Knapsack Encryption

RSA is just one way of doing public key encryption. Knapsack is a good alternative where we can create a public key and a private one. The knapsack problem defines a problem where we have a number of weights and then must pack our knapsack with the minimum number of weights that will make it a given weight. In general the problem is:

• Given a set of numbers A and a number b.
• Find a subset of A which sums to b (or gets nearest to it).

So imagine you have a set of weights of 1, 4, 6, 8 and 15, and we want to get a weight of 28, we could thus use 1, 4, 8 and 15 (1+4+8+15=28).

So our code would become 11011 (represented by '1', '4', no '6', '8' and '15'.

Then if our plain text is 10011, with a knapsack of 1, 4, 6, 8, 15, we have a cipher text of 1+4+8+15 which gives us 28.

A plain text of 00001 will give us a cipher text of 15.

With public key cryptography we have two knapsack problems. One of which is easy to solve (private key), and the other difficult (public key).

Creating a public and a private key

We can now create a super-increasing sequence with our weights where the cur-rent value is greater than the sum of the preceding ones, such as {1, 2, 4, 9, 20, 38}. Super-increasing sequences make it easy to solve the knapsack problem, where we take the total weight, and compare it with the largest weight, if it is greater than the weight, it is in it, otherwise it is not.

For example with weights of {1,2,4,9,20,38} with a value of 54, we get:

        

Check 54 for 38? Yes (smaller than 54). [1] We now have a balance of 16.
Check 16 for 20? No. [0].

Check 5 for 4? Yes. [1]. We now have a balance of 1.
Check 16 for 9? Yes. [1]. We now have a balance of 5.
Check 1 for 2? No. [0].

Check 1 for 1? Yes [1].

Our result is 101101.

If we have a non-super-increasing knapsack such as {1,3,4,6,10,12,41}, and have to make 54, it is much more difficult. So a non-super-increasing knapsack can be the public key, and the super-increasing one is the private key.

Making the Public Key

We first start with our super-increasing sequence, such as {1,2,4,10,20,40} and take the values and multiply by a number n, and take a modulus (m) of a value which is greater than the total (m - such as 120). For n we make sure that there are no common factors with any of the numbers. Let's select an n value of 53, so we get:

1×53 mod(120) = 53

2×53 mod(120) = 106
4×53 mod(120) = 92

20×53 mod(120) = 100
10×53 mod(120) = 50

40×53 mod(120) = 80

So the public key is: {53,106,92,50,100,80} and the private key is {1, 2, 4, 10, 20,40}. The public key will be difficult to factor while the private key will be easy. Let's try to send a message that is in binary code:

111010 101101 111001

We have six weights so we split into three groups of six weights:

111010 = 53 + 106 + 92 + 100 = 351
101101 = 53+ 92 + 50 + 80 = 275

111001 = 53 + 106 + 92 + 80 = 331

Our cipher text is thus 351 275 331.

The two numbers known by the receiver is thus 120 (m - modulus) and 53 (n multiplier).

We need n-1, which is a multiplicative inverse of n mod m, i.e. n(n−1) = 1 mod m. For this we find the inverse of n:

n-1 = 53-1 mod 120

(53 x _n) mod 120 = 1 

So we try values of n-1 in (53 x n-1 mod 120) in order to get a result of 1:

n-1  Result
1     53

3    39
2    106
...

77  1
75   15

76  68

The inverse of 53 mod 120 is 77

Working out (we are searching for a value of 1)

Val (val * n) mod m

1 53

2 106

3 39

4 92

5 25

6 78

7 11

8 64

9 117

10 50

11 103

12 36

13 89

14 22

15 75

16 8

17 61

18 114

19 47

20 100

21 33

22 86

23 19

24 72

25 5

26 58

27 111

28 44

29 97

30 30

31 83

32 16

33 69

34 2

35 55

36 108

37 41

38 94

39 27

40 80

41 13

42 66

43 119

44 52

45 105

46 38

47 91

48 24

49 77

50 10

51 63

52 116

53 49

54 102

55 35

56 88

57 21

58 74

59 7

60 60

61 113

62 46

63 99

64 32

65 85

66 18

67 71

68 4

69 57

70 110

71 43

72 96

73 29

74 82

75 15

76 68

77 1

Found it at 77