SHA256 - Hashing Algorithm
SHA256 - Hashing Algorithm
The Hashing algorithm we have used up to now is known as SHA256. (Secure Hashing Algorithm). For access and knowledge, go here. There are a number of alternatives. Most produce hashes of less than 20 characters and the risk of collision (two different documents or VRs producing the same hash) is significantly higher.
There is at least one other public domain algorithm which produces a hash of 20 characters, known as RIPEMD. Our choice between the two was more or less arbitrary in that when we went looking for the code, it became clear that SHA1 is much more widespread than RIPEMD.
More recently, however, the SHA algorithms have been expanded to include 256, 512 and 768 bit options. The benefits of the additional keyspace and reduced collision risk may be sufficient to outweigh the additional storage space required, particularly as storage is already cheap and getting cheaper. We may, therefore, "upgrade" to longer hashes as the system is developed.
Recently (Feb 2005) the world of cryptography experienced what, for it, was almost the equivalent of a Tsunami - when Chinese cryptographers announced a potential break to SHA1. For an enlightening discussion on the full implications of this breakthrough, you should read this page on Bruce Schneier's website.
Its relevance to the Codel project, however, is minimal. We use hashes for three purposes, none of which is seriously affected by the break. Two of our purposes relate to integrity and one to security;
- Counterfeit Prevention - A manufacturer creates a VR. We don't know the VR, we store only its hash value. When an end user wishes to validate their product they will input the VR (which is printed somewhere on the product) and it will hash to a value we hold on the database. No problem. IF the break permitted a counterfeiter to create their own VRs which happened to have matching hashes on our database, then - and only then - would it be a problem. As you will see if you read the linked page, this is emphatically NOT what has been achieved.
- Database Security - The object of using the Hashes on our database is to ensure that we do not know the sensitive information represented by the hashes. In order to obtain that sensitive information, the attacker has to obtain the hash and "reverse engineer" it to obtain the initial VR (or document if its on the Copyright database, rather than the product tracking database). Again, if you read the discussion, this is emphatically NOT what has been achieved. Brute force attacks on a hash, with a view to recreating the original message, will still require 2160 attempts and remain, to all intents and purposes, computationally infeasible (for the time being)
- Copyright - An author creates a document. Submits the hash to Codel to register their copyright date. An attacker wants to challenge the copyright - not to present an alternative document. End of problem! If its the same document, it must produce the same hash and the issue is about dates, not documents.
What is all the fuss about then?
What the break means is that if an attacker gets to choose BOTH messages (in our context this would mean that they create both the manufacturer's VR AND the counterfeiter's!) then what the Chinese have (almost) demonstrated is that it is technically feasible to find 2 VRs which produced the same hash values. They have not cracked the much more difficult problem of finding a second message to produce any arbitrary hash.
It should also be clear, if you read how our VRs are constructed that this construction places a further enormous hurdle in the way of the attacker. Not only do they have to create two VRs with matching hashes, but they also have to meet our construction rules.
As Schneier points out, in practical terms, this break does not immediately undermine all the security based on SHA1 but it sounds an alarm bell because "attacks always get better" and, as he's been warning since September 2004, there are potential problems with SHA which mean its time we created entirely new hashing algorithms. But again, as he points out, its "time to walk, not run, to the fire exits".
The important point about Schneier's analysis is that SHA itself is now in question. The attack that works for SHA1 should in principle work for all other SHA variants - although the reduction from 2128 to 2117 attempts still leaves a lot more breathing space than the reduction from 280 to 269. Nevertheless, ALL the SHA algorithms are now under suspicion so although we can climb to a higher part of the ship, it is still sinking - but very very slowly. So slowly, in fact, that it is clearly going to be capable of several more years of round the world cruising before it disappears beneath the waves.
With all that in mind, we will probably use SHA256 in place of SHA1 whenever that is an option. But we won't be too concerned about continued use of SHA1 for those uses where security is not the issue (such as copyright protection).