Further problems with SHA-1

on Friday, August 19, 2005
So what is SHA-1?

From wikipedia: The SHA (Secure Hash Algorithm) family is a set of related cryptographic hash functions. The most commonly used function in the family, SHA-1, is employed in a large variety of popular security applications and protocols, including TLS, SSL, PGP, SSH, S/MIME, and IPSec. SHA-1 is considered to be the successor to MD5, an earlier, widely-used hash function. The SHA algorithms were designed by the National Security Agency (NSA) and published as a US government standard.

The first member of the family, published in 1993, is officially called SHA; however, it is often called SHA-0 to avoid confusion with its successors. Two years later, SHA-1, the first successor to SHA, was published. Four more variants have since been issued with increased output ranges and a slightly different design: SHA-224, SHA-256, SHA-384, and SHA-512 — sometimes collectively referred to as SHA-2.

From w3c.org: The Secure Hash Algorithm takes a message of less than 264 bits in length and produces a 160-bit message digest which is designed so that it should be computationaly expensive to find a text which matches a given hash. ie if you have a hash for document A, H(A), it is difficult to find a document B which has the same hash, and even more difficult to arrange that document B says what you want it to say.

Some months ago a team of chinese researchers found an algorithm that could produce collisions in SHA-1, i.e., different messages could produce the same hash, which could be used, in theory, to forge certificates. SHA-1 is supposed to require at least 2^80 to produce a collision, which would be enough to keep it squarely out of supercomputer realm. The researchers initially managed to produce collisions in 2^69 operations, and now they were able to do it in 2^63. The lower it gets, the faster it is to break :D

For now, this is only a paper... until someone implements it, and then the fun begins. Although the US are recommending a move to SHA-2, there's this interesting quote by the NIST security technology group manager William Burr, in Federal Computer Week: "SHA-1 is not broken, and there is not much reason to suspect that it will be soon." Should become an interesting tagline in a bit of time... hehehe


on Tuesday, August 16, 2005
Nothing at all related to coding, this one, but leaving it here as a reminder for myself later - from September 23 to October 18, at Faleria António Prates, there will be a show of paintings done by robots created by a painter, Leonel Moura. Tak about conceptual art :p


Not directly related to coding, but a very interesting topic on it's own, is Computer Forensics and Incident Response. To relate this to coding, this field is so new that there's a huge need for good solid reliable smart tools to analyze and extract information from systems. I mean, even the most basic of informations, like knowing the memory map of a running windows system, is still an unkown!

If you dd (dd - a linux tool also available on windows to dump bytes... be it memory, a drive, whatever - to a file, used to image disks or analyze memory or (yep) do forensics analysys) a windows machine's memory, how do you extract meaningful information out of it? How is it organized, what is the kernel region or the applications region? Process memory is part RAM part swap, how do you deal with that? If you crash dump a windows, you can analyze the dump information on MS's tools, but dd's output is not read by the debuggers, so we need tools for this :p

Windows Incident Response Blog