04-07-2012, 11:07 AM
Message Authentication
Message Authentication.docx (Size: 106.43 KB / Downloads: 27)
• message authentication is concerned with:
o protecting the integrity of a message
o validating identity of originator
o non-repudiation of origin (dispute resolution)
• electronic equivalent of a signature on a message
• an authenticator, signature, or message authentication code (MAC) is sent along with the message
• the MAC is generated via some algorithm which depends on both the message and some (public or private) key known only to the sender and receiver
• the message may be of any length
• the MAC may be of any length, but more often is some fixed size, requiring the use of some hash function to condense the message to the required size if this is not acheived by the authentication scheme
• need to consider replay problems with message and MAC
o require a message sequence number, timestamp or negotiated random values
Authentication using Private-key Ciphers
• if a message is being encrypted using a session key known only to the sender and receiver, then the message may also be authenticated
o since only sender or receiver could have created it
o any interference will corrupt the message (provided it includes sufficient redundancy to detect change)
o but this does not provide non-repudiation since it is impossible to prove who created the message
• message authentication may also be done using the standard modes of use of a block cipher
o sometimes do not want to send encrypted messages
o can use either CBC or CFB modes and send final block, since this will depend on all previous bits of the message
o no hash function is required, since this method accepts arbitrary length input and produces a fixed output
o usually use a fixed known IV
o this is the approached used in Australian EFT standards AS8205
o major disadvantage is small size of resulting MAC since 64-bits is probably too small
Hashing Functions
• hashing functions are used to condense an arbitrary length message to a fixed size, usually for subsequent signature by a digital signature algorithm
• good cryptographic hash function h should have the following properties:
o h should destroy all homomorphic structures in the underlying public key cryptosystem (be unable to compute hash value of 2 messages combined given their individual hash values)
o h should be computed on the entire message
o h should be a one-way function so that messages are not disclosed by their signatures
o it should be computationally infeasible given a message and its hash value to compute another message with the same hash value
o should resist birthday attacks (finding any 2 messages with the same hash value, perhaps by iterating through minor permutations of 2 messages [1])
• it is usually assumed that the hash function is public and not keyed
• traditional CRCs do not satisfy the above requirements
• length should be large enough to resist birthday attacks (64-bits is now regarded as too small, 128-512 proposed)
Snefru
• a one-way hash function designed by Ralph Merkle
• creates 128 or 256 bit long hash values (let m be length)
• uses an algorithm H which hashes 512-bits to m-bits, taking the first m output bits of H as the hash value
o H is based on a reversible block cipher E operating on 512-bit blocks
o H is the last m-bits of the output of E XOR'd with the first m-bits of the input of E
o E is composed of several passes, each pass has 64 rounds of an S-box lookup and XOR
o E can use 2 to 8 passes
• overview of algorithm
o break message into 512-m bit chunks
o each chunk has the previous hash value appended (assuming an IV of 0)
o H is computed on this value, giving a new hash value
o after the last block (0 padded to size as needed) the hash value is appended to a message length value and H computed on this, the resulting value being the MAC
• Snefru has been broken by a birthday attack by Biham and Shamir for 128-bit hashes, and possibly for 256-bit when 2 to 4 passes are used in E
• Merkle recommends 8 passes, but this is slow
MD2, MD4 and MD5
• family of one-way hash functions by Ronald Rivest
• MD2 is the oldest, produces a 128-bit hash value, and is regarded as slower and less secure than MD4 and MD5
• MD4 produces a 128-bit hash of the message, using bit operations on 32-bit operands for fast implementation
R L Rivest, "The MD4 Message Digest Algorithm", Advances in Cryptology - Crypto'90, Lecture Notes in Computer Science No 537, Springer-Verlag 1991, pp303-311
• MD4 overview
o pad message so its length is 448 mod 512
o append a 64-bit message length value to message
o initialise the 4-word (128-bit) buffer (A,B,C,D)
o process the message in 16-word (512-bit) chunks, using 3 rounds of 16 bit operations each on the chunk & buffer
o output hash value is the final buffer value
• some progress at cryptanalysing MD4 has been made, with a small number of collisions having been found
• MD5 was designed as a strengthened version, using four rounds, a little more complex than in MD4 [2]
• a little progress at cryptanalysing MD5 has been made with a small number of collisions having been found
• both MD4 and MD5 are still in use and considered secure in most practical applications
• both are specified as Internet standards (MD4 in RFC1320, MD5 in RFC1321)
SHA (Secure Hash Algorithm)
• SHA was designed by NIST & NSA and is the US federal standard for use with the DSA signature scheme (nb the algorithm is SHA, the standard is SHS)
• it produces 160-bit hash values
• SHA overview[3]
o pad message so its length is a multiple of 512 bits
o initialise the 5-word (160-bit) buffer (A,B,C,D,E) to
o (67452301,efcdab89,98badcfe,10325476,c3d2e1f0)
o process the message in 16-word (512-bit) chunks, using 4 rounds of 20 bit operations each on the chunk & buffer
o output hash value is the final buffer value
• SHA is a close relative of MD5, sharing much common design, but each having differences
• SHA has very recently been subject to modification following NIST identification of some concerns, the exact nature of which is not public
• current version is regarded as secure