My favorite security topics revolve around espionage and attacks, likely because I fancy myself an internationally renowned spy – a female James Bond – who took a wrong turn and ended up doing investigations for a bank. Thus, I must lead my vicarious life of intrigue out on the web until the FBI sees fit to hire me on full time as a security goddess.
Today I’m going to begin this blog by discussing one of my favorite brute force attacks. A BIRTHDAY ATTACK is an attempt to recreate a digital signature in order to “prove” that a message is legitimate after we have nefariously altered it for our own evil purpose.
When we digitally sign an email message, we perform a one-way hash function on the message to validate that we are, in fact, the sender. When the message is received, the recipient runs the same one-way hash calculation and if the value matches the original, they know the message is legitimate and has been unaltered since its origin. The one-way hash value is a mathematical calculation that is simple to compute in one direction and computationally infeasible to run in reverse. For example, if I were to multiply 68,435,299 x 391,001,278, my computer can easily calculate the correct total. However, given only the total 26,758,289,369,312,122 how easy would it be to deduce the original two integers? Not impossible, but HIGHLY unlikely.
The birthday attack is based on the paradox that in a room of 23 people, there is a 50% probability that two people within the group share the same birthday (month/day). If you were to attempt to find someone with the same birthday as you, however, you’d need 253 people for the same likelihood. Finding two people with the same birthday is equivalent in this situation to finding two messages with the same message digest (the final outcome of the hashing algorithm.)
In a birthday attack, I want to alter a message after it has been sent. Why? Let’s assume that ACME Products has extended a job offer to Jenny and the message was only signed and not encrypted – leaving the plain text available to a typical packet sniffer. Jenny is excited about the work, but disappointed in the salary offered so she decides to take some less than ethical initiative. She obviously doesn’t have the private key with which the message was originally signed, so she decides to alter the message slightly – let’s say by increasing the salary offer from $60,000 to $80,000 per annum. She takes the altered messages and re-runs it through the hashing algorithm only to find that the message digest (the final result) has changed – as expected. The message digest is a fixed value depending on the strength of the hash, so Jenny understands that there is a finite number of digest values that will be used. She alters the message again – this time aiming for $85,000 per annum. She checks the new message digest against the original value and still finds no match. Next she tries $85,000 per YEAR instead of per annum and runs the message again – but no match. After multiple tries (usually through the use of a script or program written for these types of attacks), Jenny eventually finds an alteration that produces the SAME message digest as the original message. VOILA! She has a new offer letter from ACME that is digitally signed by the hiring director offering her a salary of $465,000 per month. Success!
Finding two messages that contain the same message digest (hashed value) is known as a collision. The stronger the hash value, the more difficult the attack becomes (a 160-bit hash value vs a 256-bit or 512-bit hash, for example).
So how do I protect against birthday attacks? Encrypting the body of the message provides additional security because it would require the attacker to first decrypt the message before they could begin alteration. Another suggestion would be to include a digital timestamp in the message – the process of finding a collision takes time, and a timestamp would be a clear indication that the message may have been altered. The issue here would be finding a reliable method of 3rd party time validation, as timestamps can also be altered or modified by attackers.
For myself, my biggest birthday attack concern of the day is whether or not someone is going to tip the waitress off so I’m forced to endure a half-baked version of “Restaurant Happy Birthday.” I’m off to party…
Your comments, thoughts, and experiences are always welcome on this blog – discussion and debate are welcome, provided you remain respectful of everyone’s viewpoint.
Very good analysis of the Birthday Attack.
Would it also be feasible and viable, to add white space in the original message?
In terms of encryption? Or are you looking specifically at the hashing function?
The best forms of encryption are going to throw additional bits of useless, random information into the message – if they didn’t, it would be easy for us to find commonly used words and phrases (like doing puzzles in the Sunday paper).
Adding this information is going to make it more difficult to crack the key (thereby keeping our information confidential), but keep in mind that it requires more overhead which can slow down the process of encryption and decryption and overwhelm resources.
We’ll talk more about initialization vectors and cryptography (my favorite subject), and we’ll even delve deeper into some of the specific hash functions (MD5) in future posts – but please feel free to expand on your question and/or share your experiences. One of the things I enjoy most about this blog is the exposure to new thoughts and perspectives!