The SHA-1 (secure hash algorithm) authentication scheme that underpins digital signatures used in SSL browser security and PGP encryption is reported to have been “broken”.
The claim has been Made on the website of respected cryptographic expert Bruce Schneier, who refers to a Chinese team at The University of Shandong as having released a paper outlining how it could be successfully attacked.
The paper is not yet available outside of specialist circles, so the claim can’t yet be verified in detail, but having previously helped break another hashing algorithm, MD5, the researchers have a track record in this area. “It pretty much puts a bullet into SHA-1 as a hash function for digital signatures,” Schneier comments pessimistically in his weblog..
SHA-1 is a type of “hash function”, a mathematical algorithm used to guarantee that a digital signature accompanying an encrypted transmission is authentic and hasn’t somehow been tampered with. Typically, it is applied to a digital signature, creating an output called a “message digest”.
This digest is then sent along with the digital signature itself, in separate transmissions. The receiver uses the same SHA-1 algorithm to create a new message digest from the signature which is compared with the one received. To a mathematically high degree of probability, they should be the same.
In theoretical terms, what the team is said to have done in “breaking” SHA-1 is demonstrate a way in which the likelihood of two message digests being the same – known as a “collision” – could be reduced from 2 to the power of 80 to 2 to the power of 69.
Although this should not give cause for immediate concern – a conventional attacker would still need a massive amount of processor time to interfere with its working in the real world – the use of such technology is highly sensitive to theoretical breakthroughs.
Only a week ago, William Burr, a security technology group manager at the National Institute of Standards and Technology (NIST), a was reported as backing the continued use of the hashing scheme. “SHA-1 is not broken […] and there is not much reason to suspect that it will be soon." Ideally its use should be phased out by 2010, he said.
His confidence now looks rather misplaced.