Wrox Programmer Forums

Need to download code?

View our list of code downloads.

Go Back   Wrox Programmer Forums > Java > Other Java > BOOK: Beginning Cryptography with Java
Password Reminder
Register
Register | FAQ | Members List | Calendar | Search | Today's Posts | Mark Forums Read
BOOK: Beginning Cryptography with Java
This is the forum to discuss the Wrox book Beginning Cryptography with Java by David Hook; ISBN: 9780764596339
Welcome to the p2p.wrox.com Forums.

You are currently viewing the BOOK: Beginning Cryptography with Java section of the Wrox Programmer to Programmer discussions. This is a community of tens of thousands of software programmers and website developers including Wrox book authors and readers. As a guest, you can read any forum posting. By joining today you can post your own programming questions, respond to other developersí questions, and eliminate the ads that are displayed to guests. Registration is fast, simple and absolutely free .
DRM-free e-books 300x50
Reply
 
Thread Tools Display Modes
  #1 (permalink)  
Old August 15th, 2006, 03:28 PM
Registered User
 
Join Date: Aug 2006
Location: , , .
Posts: 5
Thanks: 0
Thanked 0 Times in 0 Posts
Default Chapter 3 - Exercise 3

I'm having trouble understanding the rationale for the answer to exercise 3 in chapter 3:
What is the primary limitation of the use of a MAC or message digest?

The primary limitation of a MAC or message digest is the amount of data that it is safe to feed into it. The data limitation exists because, beyond a certain size, the likelihood of different data computing to the same digest or MAC value becomes too high.

My understanding of cryptographic hashes is that it is not feasible to find two another message with the same hash. I don't see what feeding a large message into it has to do with increasing the likelihood of a collision.

Can you expand on this, or perhaps provide some reference?

Andy Neilson
Reply With Quote
  #2 (permalink)  
Old August 15th, 2006, 09:24 PM
dgh dgh is offline
Wrox Author
Points: 864, Level: 11
Points: 864, Level: 11 Points: 864, Level: 11 Points: 864, Level: 11
Activity: 0%
Activity: 0% Activity: 0% Activity: 0%
 
Join Date: Aug 2005
Location: , , .
Posts: 206
Thanks: 0
Thanked 20 Times in 20 Posts
Default

How feasible it is to find a collision with a hash depends on the current technology and current knowledge. Finding a collision which is useful in the sense that it can be used to fool someone is harder again. None of this makes it impossible though.

One way to think about hashes and MAC's is as one way compression functions. The main point being that if a MAC is 16 bits long and all your documents are 64k bytes long it should be clear that reducing the entire set of bit strings possible in 524288 bits to a set of bit strings that only has 65536 members will result in a number of collisions. One set is vastly larger than the other.

Regards,

David

Reply With Quote
  #3 (permalink)  
Old August 16th, 2006, 09:55 AM
Registered User
 
Join Date: Aug 2006
Location: , , .
Posts: 5
Thanks: 0
Thanked 0 Times in 0 Posts
Default

I understand that many large messages result in the same hash. I still don't think there is a reasonable justification for characterizing this as the primary limitation of the use of a MAC or message digest.

I have difficulty with the idea that compression of large space of message into a smaller space is really an issue. Given that in reality, that the hash size is 160-512 bits (and not 16), the "smaller" space is still 2^160 to 2^512, which is still very large.

Assuming that you are using brute force in an attempt to find a collision (and you can use messages of any length), on average, you still need to try something like 2^80 to 2^256 hashes before finding a collision. It seems to me that the likelihood of a collision is so low that the size of data is not really an issue.

More to the point, my complaint about this exercise question is that it doesn't really relate to anything that you say in chapter 3.

Andy
Reply With Quote
  #4 (permalink)  
Old August 16th, 2006, 03:09 PM
dgh dgh is offline
Wrox Author
Points: 864, Level: 11
Points: 864, Level: 11 Points: 864, Level: 11 Points: 864, Level: 11
Activity: 0%
Activity: 0% Activity: 0% Activity: 0%
 
Join Date: Aug 2005
Location: , , .
Posts: 206
Thanks: 0
Thanked 20 Times in 20 Posts
Default

Chapter 3 discusses digests, MACs, and HMACs.

As page 73 mentions MACs do not have to be the block size of the cipher to be useful, but the size of any MAC or HMAC, or a reduction in size for the sake of a protocol must be considered in terms of the size of the actual messages being passed through the system. This has nothing to do with the fact that a couple of message digest algorithms have a bit size of 160 bits or that there are ones with a block size of 512 bits. The question at the end of the chapter is to enforce the idea that choice of MAC, HMAC, or digest size needs to be thought about as it changes the collision profile for the underlying algorithm. It's one of the reasons digest like SHA-512 were invented.

This is done in practice - for example SHA-384 is a reduction on SHA-512. 16 and 32 bit MACs are often employed, even though the underlying cipher or digest may have an output size which is much larger.

All digests have a limit on the size of data that should be put into them. This isn't to say there are not other considerations, but the safe input size is the first one you encounter.

Regards,

David

Reply With Quote
Reply


Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off
Trackbacks are Off
Pingbacks are On
Refbacks are Off

Similar Threads
Thread Thread Starter Forum Replies Last Post
Chapter 5 Exercise 2 diango BOOK: Beginning Visual Basic 2005 Databases ISBN: 978-0-7645-8894-5 4 February 1st, 2011 02:24 PM
Chapter 5 - Exercise 1 scgtman BOOK: Beginning Visual Basic 2005 Databases ISBN: 978-0-7645-8894-5 3 May 16th, 2006 08:10 PM
Chapter 3 Exercise 3 Matt WAXON BOOK: Beginning PHP, Apache, MySQL Web Development ISBN: 978-0-7645-5744-6 3 July 4th, 2005 02:19 AM
Chapter 4, Exercise 3 DRAYKKO BOOK: Beginning Java 2 3 July 9th, 2004 02:34 PM
Chapter 8, Exercise 4 cjo BOOK: Beginning ASP.NET 1.0 0 November 3rd, 2003 01:26 PM



All times are GMT -4. The time now is 05:49 AM.


Powered by vBulletin®
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
© 2013 John Wiley & Sons, Inc.