ARTICLE 27: trusciencetrutechnology@blogspot.com 70th B’Day Voume.2009-2010
CRYPTOGRAPHY
By
Shri P. V. P. Deekshit M.Sc (Computer Science)
s/o Shri P. V. S. Sharma, 17-11-10,Official Colony,Maharanipeta.P.O,
Visakhapatnam-530002.
ABSTRACT:
This project surveys the theory and applicationms of cryptographic has functions, such as MDS and SHA-I, HMAC and Whirlpool especially their resistence to collision-finding attacks. We review definitions, design principles, trace genealogy of standard hash functions, discuss generic attacks, attacks on iterative hash functions, and recent attacks on specific functions.The main contribution of this article lies in the study of practical constructions for hash functions. A general model for hash functions is proposed and a taxonomy for attacks is presented. Then all schemes in the literature are divided into three classes: hash functions based on block ciphers, hash functions based on modular arithematic and dedicated hash functions. An overview is that to compare the hash functions with the size of message digest and time complexity of hash functions:SHA-I,HMAC,WHIRLPOOL and MD5.
Keywords: Cryptography,SHA-1, HMAC,WHIRLPOOL, MD5, Sample Code, examples, implementation.
1.About Cryptography
Cryptography is the art and science of keeping messages secure. When a message is transferred from one place to another, it contents are readily available to an evesdropper.
In cryptography world the message that needs to be secured is called plaintext or clear text. The scranmbled form of the message is called cipher text. The process Cryptography is the science of writing in secret code and is an ancient art; the first documented use of cryptography in writing dates back to circa 1900 B.C. when an Egyptian scribe used non-standard hieroglyphs in an inscription. Some experts argue that cryptography appeared spontaneously sometime after writing was invented, with applications ranging from diplomatic missives to war-time battle plans. It is no surprise, then, that new forms of cryptography came soon after the widespread development of computer communications. In data and telecommunications, cryptography is necessary when communicating over any untrusted medium, which includes just about any network, particularly the Internet.
Within the context of any application-to-application communication, there are some specific security requirements, including:
Authentication: The process of proving one's identity. (The primary forms of host-to-host authentication on the Internet today are name-based or address-based, both of which are notoriously weak.)
Privacy/confidentiality: Ensuring that no one can read the message except the intended receiver.
· Integrity: Assuring the receiver that the received message has not been altered in any way from the original.
· Non-repudiation: A mechanism to prove that the sender really sent this message.
Cryptography, then, not only protects data from theft or alteration, but can also be used for user authentication. There are, in general, three types of cryptographic schemes typically used to accomplish these goals: secret key (or symmetric) cryptography, public-key (or asymmetric) cryptography, and hash functions, each of which is described below. In all cases, the initial unencrypted data is referred to as plaintext. It is encrypted into cipher text, which will in turn (usually) be decrypted into usable plaintext.
In many of the descriptions below, two communicating parties will be referred to as Alice and Bob; this is the common nomenclature in the crypto field and literature to make it easier to identify the communicating parties. If there is a third or fourth party to the communication, they will be referred to as Carol and Dave. Mallory is a malicious party, Eve is an eavesdropper, and Trent is a trusted third party.
TYPES OF CRYPTOGRAPHIC ALGORITHMS:
There are several ways of classifying cryptographic algorithms. For purposes of this they will be categorized based on the number of keys that are employed for encryption and decryption, and further defined by their application and use. The three types of algorithms that will be discussed are :
· Secret Key Cryptography (SKC): Uses a single key for both encryption and decryption
· Public Key Cryptography (PKC): Uses one key for encryption and another for decryption
· Hash Functions: Uses a mathematical transformation to irreversibly "encrypt" information.
Secret Key Cryptography
With secret key cryptography, a single key is used for both encryption and decryption. As shown in Figure 1A, the sender uses the key (or some set of rules) to encrypt the plaintext and sends the cipher text to the receiver. The receiver applies the same key (or rule set) to decrypt the message and recover the plaintext. Because a single key is used for both functions, secret key cryptography is also called symmetric encryption.
With this form of cryptography, it is obvious that the key must be known to both the sender and the receiver; that, in fact, is the secret. The biggest difficulty with this approach, of course, is the distribution of the key.
Secret key cryptography schemes are generally categorized as being either stream ciphers or block ciphers. Stream ciphers operate on a single bit (byte or computer word) at a time and implement some form of feedback mechanism so that the key is constantly changing. A block cipher is so-called because the scheme encrypts one block of data at a time using the same key on each block. In general, the same plaintext block will always encrypt to the same cipher text when using the same key in a block cipher whereas the same plaintext will encrypt to different cipher text in a stream cipher.
Stream ciphers come in several flavors but two are worth mentioning here. Self-synchronizing stream ciphers calculate each bit in the keystream as a function of the previous n bits in the keystream. It is termed "self-synchronizing" because the decryption process can stay synchronized with the encryption process merely by knowing how far into the n-bit keystream it is. One problem is error propagation; a garbled bit in transmission will result in n garbled bits at the receiving side. Synchronous stream ciphers generate the keystream in a fashion independent of the message stream but by using the same keystream generation function at sender and receiver. While stream ciphers do not propagate transmission errors, they are, by their nature, periodic so that the keystream will eventually repeat.
Block ciphers can operate in one of several modes; the following four are the most important:
· Electronic Codebook (ECB) mode is the simplest, most obvious application: the secret key is used to encrypt the plaintext block to form a cipher text block. Two identical plaintext blocks, then, will always generate the same cipher text block. Although this is the most common mode of block ciphers, it is susceptible to a variety of brute-force attacks.
· Cipher Block Chaining (CBC) mode adds a feedback mechanism to the encryption scheme. In CBC, the plaintext is exclusively-ORed (XORed) with the previous cipher text block prior to encryption. In this mode, two identical blocks of plaintext never encrypt to the same cipher text.
· Cipher Feedback (CFB) mode is a block cipher implementation as a self-synchronizing stream cipher. CFB mode allows data to be encrypted in units smaller than the block size, which might be useful in some applications such as encrypting interactive terminal input. If we were using 1-byte CFB mode, for example, each incoming character is placed into a shift register the same size as the block, encrypted, and the block transmitted. At the receiving side, the cipher text is decrypted and the extra bits in the block (i.e., everything above and beyond the one byte) are discarded.
· Output Feedback (OFB) mode is a block cipher implementation conceptually similar to a synchronous stream cipher. OFB prevents the same plaintext block from generating the same cipher text block by using an internal feedback mechanism that is independent of both the plaintext and cipher text bit streams.
· Data Encryption Standard (DES):
The most common SKC scheme used today, DES was designed by IBM in the 1970s and adopted by the National Bureau of Standards (NBS) [now the National Institute for Standards and Technology (NIST)] in 1977 for commercial and unclassified government applications. DES is a block-cipher employing a 56-bit key that operates on 64-bit blocks. DES has a complex set of rules and transformations that were designed specifically to yield fast hardware implementations and slow software implementations, although this latter point is becoming less significant today since the speed of computer processors is several orders of magnitude faster today than twenty years ago. IBM also proposed a 112-bit key for DES, which was rejected at the time by the government; the use of 112-bit keys was considered in the 1990s, however, conversion was never seriously considered.
2. About Hash functions: Data integrity assurance and data origin authentication are essential security services in financial transactions, software distribution and data storage and so on. Message digest algorithms are extensively used in IP security and in Digital signature applications. The Digital signatures are used in electronic commerce, where the recipient of a message desires to verify the origin of the message and its integrity. A digital signature is computed using a set of rules and set of parameters such that the identity of the signatory and integrity of the data can be verified. The algorithm makes use of a private key to generate a digital signature. Signature verification makes use of a public key which corresponds to, but is not the same as, the private key. A hash function is used in the signature generation process to obtain a condensed version of data, called a message digest.
Hash algorithms, also known as message digest algorithms; generate a unique message digest for a message of arbitrary length. These algorithms are designed to have the following properties of easily computing the hash value; being very hard to compute the message from the digest and being hard to find another message, which has the same message, digest as the first message.
Hash functions are also used in producing a message authentication code that is referred to as HMAC. HMAC has been chosen as the mandatory to implements MAC for IP security and is used in SSL. HMAC is designed to use the available hash functions such as message digest5, secure hash algorithms etc
In this paper the popular hash algorithms SHA1, HMAC, WHIRLPOOL and MD5 are considered for implementing in software and programmable hardware. The performance of these algorithms is analyzed with respect to time complexity depending on the size of the data.
Hash functions, also called message digests and one-way encryption, are algorithms that, in some sense, use no key (Figure 1C). Instead, a fixed-length hash value is computed based upon the plaintext that makes it impossible for either the contents or length of the plaintext to be recovered. Hash algorithms are typically used to provide a digital fingerprint of a file's contents, often used to ensure that the file has not been altered by an intruder or virus. Hash functions are also commonly employed by many operating systems to encrypt passwords. Hash functions, then, provide a measure of the integrity of a file.
Hash algorithms that are in common use today include:
Message Digest (MD) algorithms: A series of byte-oriented algorithms that produce a 128-bit hash value from an arbitrary-length message.
MD2 (
RFC 1319): Designed for systems with limited memory, such as smart cards. MD4 (
RFC 1320): Developed by Rivest, similar to MD2 but designed specifically for fast processing in software.
MD5 (
RFC 1321): Also developed by Rivest after potential weaknesses were reported in MD4; this scheme is similar to MD4 but is slower because more manipulation is made to the original data. MD5 has been implemented in a large number of products although several weaknesses in the algorithm were demonstrated by German cryptographer Hans Dobbertin in 1996.
Secure Hash Algorithm (SHA):Algorithm for NIST's Secure Hash Standard (SHS). SHA-1 produces a 160-bit hash value and was originally published as FIPS 180-1 and RFC 3174. FIPS 180-2 describes five algorithms in the SHS: SHA-1 plus SHA-224, SHA-256, SHA-384, and SHA-512 which can produce hash values that are 224, 256, 384, or 512 bits in length, respectively. SHA-224, -256, -384, and -512 are also described in RFC 4634.
RIPEMD: A series of message digests that initially came from the RIPE (RACE Integrity Primitives Evaluation) project. RIPEMD-160 was designed by Hans Dobbertin, Antoon Bosselaers, and Bart Preneel, and optimized for 32-bit processors to replace the then-current 128-bit hash functions. Other versions include RIPEMD-256, RIPEMD-320, and RIPEMD-128.
HAVAL (HAsh of VAriable Length): Designed by Y. Zheng, J. Pieprzyk and J. Seberry, a hash algorithm with many levels of security. HAVAL can create hash values that are 128, 160, 192, 224, or 256 bits in length.
Whirlpool:
A relatively new hash function, designed by V. Rijmen and P.S.L.M. Barreto. Whirlpool operates on messages less than 2256 bits in length, and produces a message digest of 512 bits. The design of this has function is very different than that of MD5 and SHA-1, making it immune to the same attacks as on those hashes (see below).
· Tiger: Designed by Ross Anderson and Eli Biham, Tiger is designed to be secure, run efficiently on 64-bit processors, and easily replace MD4, MD5, SHA and SHA-1 in other applications. Tiger/192 produces a 192-bit output and is compatible with 64-bit architectures; Tiger/128 and Tiger/160 produce the first 128 and 160 bits, respectively, to provide compatibility with the other hash functions mentioned above.
Hash functions are sometimes misunderstood and some sources claim that no two files can have the same hash value. This is, in fact, not correct. Consider a hash function that provides a 128-bit hash value. There are, obviously, 2128 possible hash values. But there are a lot more than 2128 possible files. Therefore, there have to be multiple files — in fact, there have to be an infinite number of files! — that can have the same 128-bit hash value.
..+--./*797
AssociationsAssociations are relationships between classes and represent groups of links. Each end of an association can be labeled by a set of integers indicating the number of links that can legitimately originate form an instance of the class connected to the association end. Associations are used to represent a wide range of connections among a set of objects
User
Selection of algorithms
USER 1 ----------------> * Selection of Algorithm
One user can select more than one algorithm
Algorithms used in the project:
.HMAC :
H= embedded hash function(e.g., SHA-1)
M=message input to HMAC(including the padding specified in the embedded hash function)
Y= ith block of M,0<=i<=(L-1) L=number of blocks in M B=number of bits in a block N=length of hash code produced by embedded hash function K=secret Key; if key length is greater than b, the key is input to the hash function to produce an n-bit key; recommended length is>=n
K+=K Padded with zeros on the left so that the result is b in length
I pad=00110110 (36 in hexadecimal)
O pad=01011100(5C in hexadecimal)
Implementation of HMAC Algorithm • Step1: Append zeros to the left end of K to create a b-bit string K+.
• Step2: XOR (bit wise exclusive-OR)K+ with ipad to produce the b-bit block Si
• Step3: Append M to Si
• Step4: Apply H to the stream generated in Step3.
• Step5: XOR K+ with Opad to produce the b bit block S0.
• Step6: Append the hash result from step 4 to S0.
• Step7: Apply H to the stream generated in step6 and output the result.
Implementation of SHA-1 Algorithm
The Algorithm takes as input a message with a maximum length of less than of 264 bits and produce as output as 160 bit message digest.
• Step1- Appending Bits:
The Message is padded like a single 1 bit is added into the end of message, after which 0-bits are added until the length of ‘M ‘ is congruent to 448 modulo 512 (length=448mod512).
• Step2: Appending Length:
A block of 64=bit representation of b is appended to the result of above step. Thus resulted message is a multiple of 512 bits.
• Step3- Buffer Initialization:
A 160 bit buffer is used to hold intermediate and final results of the hash function.
This buffer can be represented as five 32 bit registers as A,B,C,D,E.
• After all L-512 bit blocks have been processed, the out put from the Lth stage is the 160-bit message digest.
Implementation of MD5 Algorithm :
The algorithm takes as input a message of arbitrary length and produces as output a 128-bit message digest of the input.
The processing involves the following steps.
• Step1: PaddingThe message is padded to ensure that its length in bits. 64 is divisible by 512. That is, its length is congruent to 448 modulo 512.
•
Step2: Appending lengthA 64-bit binary representation of the original length of the message is concatenated to the result of step (1).
Let the expanded message be represented as a sequence of L 512-bit blocks Y0, Y1,..,Yq,..,YL-1.
• Step:3 Initialize the MD bufferThe variables IV and CV are represented by a four–word buffer (ABCD) used to compute the message digest. Here each A, B, C, D is a 32-bit register and they are initialized as IV to the following values in hexadecimal. Low-order bytes are put first.
Word A: 01 23 45 67
Word B: 89 AB CD EF
Word C: FE DC BA 98
Word D: 76 54 32 10
4. Compression function MD5 :
The output of the fourth round is added to the input of the first round (CVq) to produce CVq+1
Step5: Output
After all L 512-bit blocks have been processed, the
output from Lth stage is the 128-bit message digest.
Implementation of WHIRLPOOL Algorithm:
The message digest is produced in four steps
Step 1: Padding
Message is padded to multiple of 256 bits. In the case where the unpadded message is already of that length it is padded with 512 bits (2x256), which is the maximum padding length.
Step 2: Message length
The length of the unpadded message is appended to the message. The length is expressed as a 256 bit unsigned integer, with the most significant byte being the leftmost.
After this step the message length is n x 512 bits (n=1, 2, …).
Step 3: Hash matrix initialization
The results of the hash function (both intermediate and final) and stored in an 8x8 matrix. Each element of the matrix is 8 bits (a byte) of the message, thus the hash matrix holds 512 bits in total and the first matrix H0 is initialized with zeros (each byte is 0000 0000)
Step 4: Block cipher
The block cipher processes the message in 512-bit blocks.
Structure of Whirlpool :
Algorithms Used in Project:
Source Code:
Imports System.Data
Imports System.Data.OleDb
Public Class Form2
Public message, hashmsg As String
Dim str As String
Dim ch As Char
Dim a1, b1, c1, d1, e1, f1 As Char
Dim r, n, l, j, msglen As Integer
Dim l1, t, y, j2 As Integer
Dim bin0, bin, bin1, bin2, bin3, bin4, bin5 As String
Dim bin10, bin11, bin21, bin31, bin41 As String
Dim h(4), k(3), hash(4), w(15) As String
Dim hdec(4), kdec(3), w1(79) As UInt64
Dim hd(4) As UInt32
Dim a, b, c, d, x, f, p1, temp As UInt64
Dim key, key0 As String
Dim r1, r2, r3 As String
Dim bs, k0 As Integer
Dim ipad, opad, ipad0, opad0, ch1, ch2 As String
Dim len As Integer = 0
Dim txt, wbin0, wbin1, wbin2, wbin3, wstr As String
Dim wch As Char
Dim wr, wl, wtxtlen, wn, wc As Integer
Dim cstate(7, 7), kstate(7, 7), kstate1(7, 7), dsbox(15, 15) As Integer
Dim ak(7, 7), sc(7, 7), mr(7, 7), drc(9, 7, 7), dkeys(9, 7, 7), dmds(7, 7) As Integer
Function generatesha(ByVal msg As String) As String
bin10 = msg
bin11 = ""
ch1 = ""
l = (bin10.Length)
For i As Integer = 0 To l - 1
ch = bin10.Substring(i, 1)
n = Convert.ToInt16(ch, 16)
ch1 = Convert.ToString(n, 2)
r = ch1.Length()
If r < r =" 4" integer =" 0" ch1 =" 0" bin11 =" bin11" l =" bin11.Length()" msglen =" l" bin11 =" bin11" l =" 448" l =" 960" l =" 1472" l =" 1984" integer =" 0" bin11 =" bin11" bin21 = "" bin21 =" (Convert.ToString(msglen," n =" 64" integer =" 0" bin21 =" 0" bin31 = "" bin31 =" bin11.ToString()" l =" bin31.Length()" n =" (l" l =" l" integer =" 0" j =" 0" bin41 = "" integer =" 0" a =" q(j).ToString()" a1 = "A" bin41 =" bin41" b =" q(j).ToString()" b1 = "B" bin41 =" bin41" c =" q(j).ToString()" c1 = "C" bin41 =" bin41" d =" q(j).ToString()" d1 = "D" bin41 =" bin41" x =" q(j).ToString()" e1 = "E" bin41 =" bin41" f =" q(j).ToString()" f1 = "F" bin41 =" bin41" bin41 =" bin41" j =" j" j =" j" integer =" 0" integer =" 0" l =" bin41.Length()" l1 =" l" l1 =" l1" y =" 0" j2 =" 0" p1 =" Math.Pow(2," integer =" 0" j2 =" j2" integer =" 0" y =" y" integer =" 16">> 31)
Next i
a = hdec(0)
b = hdec(1)
c = hdec(2)
d = hdec(3)
x = hdec(4)
For i As Integer = 0 To 79
If i >= 0 And i <= 19 Then f = (b And c) Or ((Not b) And d) t = 0 ElseIf i >= 20 And i <= 39 Then f = b Xor c Xor d t = 1 ElseIf i >= 40 And i <= 59 Then f = (b And c) Or (b And d) Or (c And d) t = 2 ElseIf i >= 6 And i <= 79 Then f = b Xor c Xor d t = 3 End If temp = (((a <<>> 27)) + f + x + kdec(t) + w1(i)) Mod p1
x = d
d = c
c = ((b <<>> 2)) Mod p1
b = a
a = temp
Next i
hdec(0) = (hdec(0) + a) Mod p1
hdec(1) = (hdec(1) + b) Mod p1
hdec(2) = (hdec(2) + c) Mod p1
hdec(3) = (hdec(3) + d) Mod p1
hdec(4) = (hdec(4) + x) Mod p1
Next k1
bin5 = ""
For i As Integer = 0 To 4
hd(i) = Convert.ToUInt32(hdec(i))
hash(i) = Convert.ToString(hd(i), 16)
'TextBox2.Text = TextBox2.Text & hash(i).ToString() & " "
bin5 = bin5 & hash(i).ToString() & " "
Next i
Return bin5
End Function
Private Sub Form2_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
GroupBox1.Enabled = False
GroupBox2.Enabled = False
End Sub
Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
Dim con As New OleDbConnection(MyKit.getconstr())
Dim cmd As New OleDbCommand()
cmd.Connection = con
Dim size As Integer = message.Length
If CheckBox1.Checked Then
GroupBox1.Enabled = True
Dim dt As Long = Date.Now.Ticks
MsgBox("Start Time : " + Date.Now.Ticks.ToString, MsgBoxStyle.Information, "SHA1")
'message = Form1.TextBox1.Text
If message = "" Then
MsgBox("Start Time : " + Date.Now.Ticks.ToString, MsgBoxStyle.Information, "SHA1")
TextBox2.Text = " "
Else
For i As Integer = 0 To (Form1.TextBox1.Text.Length - 1)
ch = message(i)
r = CInt(Asc(ch))
bin = (Convert.ToString(r, 16))
str = str & bin.ToString()
Next i
End If
hashmsg = generatesha(str)
TextBox2.Text = hashmsg.ToString()
MsgBox("End Time : " + Date.Now.Ticks.ToString, MsgBoxStyle.Information, "SHA1")
dt = Date.Now.Ticks - dt
MsgBox("Execution Time : " + dt.ToString, MsgBoxStyle.Information, "SHA1")
con.Open()
cmd.CommandText = "delete from sha1 "
cmd.ExecuteNonQuery()
con.Close()
con.Open()
cmd.CommandText = "insert into sha1 values(" & size & "," & dt & ")"
cmd.ExecuteNonQuery()
con.Close()
End If
CONCLUSIONS
This project implements the four hash algorithms which are most sophisticated algorithms in hashing messages. This project gives the algorithm which is most best in time complexity and messaged digest size.Finally it concludes the best algorithm according to their size and time complexity.
11. Bibliography/References
Books:
Federal Information Processing Standards (FIPS) Publication 180-1, Secure Hash Standard (SHS), U.S. DoC/NIST, April 17, 1995.
[HAC] A. Menezes, P. van Oorschot, and S. Vanstone. Handbook of Applied
Cryptography, CRC Press, Inc., October 1997.
References:
1. Barreto, Paulo S.L.M. and Rijmen, Vincent (2003) (PDF). The WHIRLPOOL Hashing Function
2. http://planeta.terra.com.br/informatica/paulobarreto/whirlpool.zip. Retrieved on 2007-11-21.
3. Kyoji, Shibutani and Shirai, Taizo (2003) (PDF). On the diffusion matrix employed in the whirlpool hashing function
4. http://www.cosic.esat.kuleuven.be/nessie/reports/phase2/whirlpool-20030311.pdf. Retrieved on 2007-11-21.
5. American Bankers Association, Keyed Hash Message Authentication Code, ANSI
6. H. Krawczyk, M. Bellare, and R. Canetti, HMAC: Keyed-Hashing for Message Authentication, Internet Engineering Task Force, Request for Comments (RFC)
7. National Institute of Standards and Technology, Secure Hash Standard (SHS), Federal Information processing Standards Publication 180-1, 17
12th April 2010
The Iceland's volcano:
(UKPA) – 7 hours ago of 19th April 2010 Seven die as quake hits Afghanistan:
