An excuse to mention cryptography
Posted by Jacques Chester on Saturday, June 20, 2009
I needn’t tell Troppo readers that a few days of heady excitement are afoot in Canberra. Personally I doubt that the PM will go, but Swan might be in serious trouble.
A lot of argy-bargy has gone on about whether a “smoking gun” email, allegedly in the Coalition’s possession, is genuine. A lot of people have pointed out that it’s pretty easy to forge an email — after all, it’s just a bunch of text.
Enter the noble and mysterious art of cryptography. In particular, enter the mature but rarely-used technology of digital signatures.
Some Technical Talk
Digital signature schemes combine the two great pillars of modern cryptography: one-way hash functions and dual-key encryption.
A hash function turns any document into a fixed-length string. The clever part about hash functions is that they aren’t reversible. You can’t take the generated hash and run it backwards to get the original document. Hashes are widely used to store passwords or to check the integrity of downloads.
Dual-key encryption means that every person gets a private key, and they distribute a public key. If you possess the private key you can read items encrypted with the public key, which ensures that only the intended reader will see it. Alternatively, if you encrypt an item with your private key, people can ensure that it was you who did it by applying your public key.
In a digital signature scheme, these two things are combined. First, the system generates a hash for the document being signed. Then, it encrypts that hash with the sender’s private key.
At the other end, the receiver decrypts the signature with the public key, then computes the document hash themselves. If the received hash is the same as their own calculation, they know that the document was sent by the person claimed.
Some Practical Consequences
Digital signatures (and a related technology, HMACs, which I won’t discuss here) can quickly settle the question of who said what and when. If the sender’s private key is secure, the digital signature cannot be forged, cannot be reneged and cannot be refuted. It is, in actual fact, more reliable than a paper signature.
If the Federal government used digital signatures, it would be trivial to establish whether the Opposition possessed the genuine article. HMACs would further make it possible to determine, given a collection of correspondence, whether any items are missing from that collection.
Support for digital signatures is built into every modern email client and server. I reckon that the government could do worse than to roll out digital signature infrastructure throughout government. For centuries we’ve been relied on the integrity of the paper trail; it would be nice if the e-trail was as trustworthy.
This entry was posted on Saturday, June 20th, 2009 at 12:07 PM and filed under IT and Internet, Politics - national.
Follow comments here with the RSS 2.0 feed.
Apologies. Comments and trackbacks are both currently closed.
If the senders private key is secure,…
That’s the problem. We are assuming that the private key is secure – by that, no black hats have access to the computer on which the key resides. But laptops get stolen, and ministers’ computers get bugged. Private keys make it harder for baddies to get on public service computers. But if they access the machine anyway to commit a crime, then private keys make it harder to prove the innocence of the relevant public servant or politician.
They’re no silver bullet.
Posted on 20-Jun-09 at 1:41 pm | PermalinkThe usual solution is to use symmetric encryption on the private key. You need both the key and the passphrase that goes with it.
Notice that this is already more secure than a password alone and more secure than a signature, which can be easily photocopied.
Posted on 20-Jun-09 at 1:48 pm | PermalinkAnd even if keys do get stolen, you can verifiably revoke them. Again, something that can’t be done with ordinary emails or signatures.
Posted on 20-Jun-09 at 1:49 pm | PermalinkInteresting, but not critically relevant in this case. I’d say the only possibilities are
(a) The email was sent from the PMs office; or
(b) The email published by the Telegraph was neither sent by the PMs office nor received by the Treasury
Of these (a) is looking increasingly unlikely. If (b) is true, then digital signatures are irrelevant, I think – the Tele would not have the private key and would be unable to check it.
The idea that someone spoofed a message to the Treasury would seem to fit with Grech’s Senate testimony, but it makes no sense. Grech would surely have replied to the supposed sender at which point the spoof would have been revealed.
Coming to the politics, it seems increasingly likely that Turnbull has made a disastrously bad call. Most aspects of the issue are too complex for the average punter (eg me), but anyone can understand a fake email. Of course, if the email turns out to be real, it will be Rudd who has made the disastrous call.
Posted on 21-Jun-09 at 10:34 am | PermalinkTurnbull will indeed have over-reached if no email turns up, particularly given the easier mark that Swan’s documented involvement offered. But that’s now been subsumed in the “fake email” brouhaha.
Posted on 21-Jun-09 at 11:19 am | PermalinkJohn;
The Telegraph would not use the private key to check the signature. They would use the public key. That’s the beauty of the scheme.
Otherwise, yes, one of the two men has overreached. Talk about your high stakes poker.
Posted on 21-Jun-09 at 11:52 am | PermalinkThe analogy to high stakes poker seems quite apt. To me i can’t avoid the mental image of Turnbull, then Rudd, in a rush of blood, both going ‘all in’ in a game of Texas hold’em (or whatever the game played on TV is) with both hanging on the cards the dealer will turn over. The on-screen graphic has Rudd at 90% chance of winning or more with Turnbull looking like he needs a miracle on (IIRC) the turn or the river card or else he’ll be down to only a couple of chips with Rudd ending up with a giant stack.
Oh, and Swan has been left playing the pokies, Rudd telling him ‘I’ll pick you up when it’s time to go home Wayne.’
Posted on 21-Jun-09 at 1:12 pm | PermalinkOK, Jacques, I should have read the post better.
But as you say, one of the two has overreached. As Geoff says, Swan was an easy target, though his breach was trivial compared to what was routine under Howard (eg Manildra). But now it all turns on the existence of a genuine email, which appears increasingly unlikely.
Posted on 21-Jun-09 at 2:04 pm | PermalinkWith digitally signed emails, Grech would have instantly known that the spoof email was a fraud and never considered replying to it. The government email system could go one step further and strip out all unsigned and incorrectly signed emails to ensure that Grech only sees bona fide messages.
However, let’s consider the other side of the coin which is legitimate emails that conveniently vanish when curious stickybeaks go searching for them (see also Karl Rove and the “accidentally” deleted emails). Cryptography won’t help you there. Possibly a series chain of hash values (as per http://git-scm.com/) might show the evidence of a missing item in the chain, but once you find there’s a hole, then what?
How about a USB device that contains the private key inside the device AND a fingerprint scanner on top of the device? If the email signature is constructed inside the USB device, then the host computer never gets access to the cryptographic information at all (yes admittedly, a compromised host could sneak in and sign a few extra emails at the same moment the legitimate user has his/her thumb on the device, but the device could also keep a list of what it signed for later check).
Posted on 21-Jun-09 at 3:30 pm | PermalinkSure. Better yet, forward them to the DSD or AFP.
The blank tapes problem. But it can be useful to know absolutely when something is missing. The other thing about HMACs (which is what Git is using) is that you can continuously check them. Nothing stops a system check from running every hour. And again, it’s better than an ordinary paper trail where there’s no such assurances.
Key management is a whole subfield in itself. Generally private keys are symmetrically encrypted with a single key. The passphrase used to encrypt also decrypts. That way, if even somebody gets the keyfile, they still need to know the pass phrase.
A biometric system can’t provide that, because it’s probablistic. You don’t get exactly the same input for each thumb press, just a probability that it matches some example. So it’s useless as a pass phrase for encrypting the private key.
The actual design of secure crypto schemes is best left to the experts, which is why I didn’t go into too much detail. I was trying to point out what it can give you.
Posted on 21-Jun-09 at 4:03 pm | PermalinkJacques, Tel
There are several problems with the USB/signature idea
1. The USB devices Tel refers to have existed for about 10 years BUT are not
the memory sticks we all know and use.
A memory stick is readable but just about anything and the only security it
offers is a little extra physical security because it’s on my keychain and
a little harder for someone to get access to.
But they can sniff if I use my memory stick to transfer an unrelated file
to their laptop.
So memory sticks are out.
2. The alternative is a much more expensive device (about $50 in quantities
of 100 from memory) that actually does the hash calculation on the stick
itself – ie. it has a little processor chip on board.
These are better, but not by much because if you know what you are dealing
with you can spoof them.
These things have been around in the market for over 10 years but are very
rarely used and haven’t taken off in real life. (About the only use that
I’m aware of is by banks to secure payment processing hardware, but there
two keys held by two different people are used within a short space of time
much like the old Minuteman nuclear missile firing system. This is to get
around the next problem.)
But the major problem is that all these hashes and codes are not signatures.
A signature is something that I make personally, fully cognisant of what I am doing. A “digital signature” is a mark that is placed on a document that is
difficult, but not impossible, for someone else to duplicate.
In other words, a digital signature is like an old fashioned seal. I may be
the only person who normally carries the seal, but its mark doesn’t mean 100%
that I signed the document (or even knew that I was doing it, which is an
issue with computer viruses that can do things behind my back)
The “security” Jacques refers to, is only the difficulty of replicating the
mark much like a very complex seal that is difficult to copy. But the mark
does not create a signature of the same strength as a legal one in my own hand.
And bionic systems are rubbish. When I’ve used them they’ve been quite
unreliable and only recognize my fingerprint about 8 times out of 10, have quite
a high false positive rate (ie. you can get lucky and find your print will
sometimes open my safe), and can be spoofed easily.
Spoofing can be done from a fingerprint on a glass lifted off and transferred to
Posted on 21-Jun-09 at 8:35 pm | Permalinka bit of silicon.
I disagree. It is basically impossible if you’ve done it properly. With a sufficiently large key (2 kilobytes) it won’t be decrypted before the universe ends.
If you want pure signature-like semantics, you require the user to enter the passphrase every time they send an email.
And remember, this is better than what we have now.
Posted on 21-Jun-09 at 9:24 pm | PermalinkThat’s what you would like it to be, but a handwritten signature can be copied (using a digital photograph, a bit of touchup and a FAX machine) or forged (someone skilled enough to just write the signature). We use it because it is good enough for most situations, having two people (signature of a witness) it is better, but potentially still beatable. Credit cards have a signature on the back and any merchant is within their rights to request that you sign to prove you are the real holder of the card — but CC fraud happens all the time. The biggest advantage of a handwritten signature is that it’s reasonably well tested and well understood by most of the population — doesn’t mean it is good, merely a known level of badness.
I’m aware that fingerprints can be copied, so can pretty much anything (including DNA even). There’s no such thing as perfect security. With cryptography you never know whether someone has found a convenient shortcut (like prime factorisation algorithms, which do exist).
For what it’s worth, the AFP seem to believe that Turnbull is the loser, and the email in question is in fact a fake (so say the ABC). Might be a double dissolution moment, no doubt both sides will be furiously polling
Posted on 22-Jun-09 at 5:12 pm | PermalinkJacques: ” [duplicating a digital signature] is basically impossible if youve done it properly. ”
Actually, it’s relatively simple. SHA1 which is the basis of digital signatures was broken back in 2005 (http://en.wikipedia.org/wiki/Sha1) and the attacks on it have improved – ie. gotten faster – since. The putatitve replacements SHA2 and SHA3 suffer from the same mathematical flaw.
There’s also a fairly practical attack that doesn’t require breaking the key – roughly speaking (I’m doing violence to the details) you prepare a dangerous document and block hash it, then prepare an innoccouss one and iteratively fiddle with it hashing all the while until it yields the same hash. This is a search that takes a lot less time than breaking the code will. Now join the two together in the same document. Because SHA1 is a block cypher the resulting document (which can be an email or webpage) will have the same hash.
Your “signed” document can now be decoded to two different versions. Now send it.
With a little tweaking (ie. Javascript) you can foist this on the unsuspecting who will only see the innocuous version, and then reveal the dangerous version at the most embarrassing moment.
As to whether all of this comprises a signature Bruce Schneier had this to say back in 2000:
http://www.schneier.com/crypto-gram-0011.html
Tel_’s objection I would answer this way. You know the new chip based CC’s? I have one but I always sign and never use a PIN.
The reason why is that if I use a PIN the risk of fraudulent use lies with me not the bank. I can never repudiate a transaction – even if my card is replicated and the thief has used a scanner to capture my PIN (a not uncommon ruse) – because the bank simply says “the card was used with the correct PIN, so either it was you or you didn’t keep your PIN safe”.
By signing on the other hand I can repudiate fraudulent use by other means “but I wasn’t in Nigeria last Monday, check my passport”.*
If you were not aware of this, go and re-read the conditions on your CC.
* And this is not funny, a few years ago, in another country, I had 3 large fraudulent transactions go through in the space of about 4 hours and the bank was willing to accept my word that I was at work instead of about 10km away at the relevant times. With a PIN I don’t think they would have bothered to listen to me.
Posted on 26-Jun-09 at 9:24 pm | PermalinkNothing actually requires you to use SHA1, that’s just been the recommended default now. As I understand it SHA1 has been weakened but not comprehensively broken. You can try to create a collision (the two documents scenario), but it’s still out of the reach of anyone in this lifetime.
Most crypto experts say that the way to deal with the weakness is to expand it. So now the recommended approach is to use SHA-256. Even with the side-band attacks the potential hash space is so much larger that you’re back into heat-death-of-the-universe territory.
SHA3 hasn’t been declared yet. Bruce Schneier and some friends of his have an algorithm in the SHA3 competition called Skein. A very interesting design. They reckon that making an individual round more complex does not strengthen the final hash enough compared to adding more rounds. They draw a direct analogy with the attacks on SHA1, MD5 et al.
I suppose all of this shows that good crypto systems are best left to the experts, but I still think that the claims for them are pretty good over the alternative. Of course it’s no longer clear who, if anyone, saw the forged email apart from the copy Godwin Grech allegedly created so what digital signatures would have bought in an identical case is unclear.
Posted on 27-Jun-09 at 2:12 am | PermalinkI’d go along with the HMAC system if the hash values for public-servant emails are put on public display. Such that anyone can download and copy the latest list of email-hash values and keep a copy for later reference. Although some of these hash functions are “broken”, I’ve yet to see anyone demonstrate that they can reconstruct an original document from just the hash digest. Thus, the privacy of the original document would be quite safe.
Armed with hash lists for all public service email boxes, we would have a pretty good idea where the email went
If the “unsuspecting” keeps a copy of the innocuous version, then he/she merely pops that up and notes an observable case of hash collision. I’m sure it would not take much study to identify that the hash collision was deliberate (generally deliberate hash collision documents have patches of random garbage where someone did a bit of brute-force bit fitting, generally near the end, a cryptographic expert would spot it a mile off).
This puts the sender of the email into even greater danger because now there is clear evidence of fraud, and NO plausible deniability of an innocent accidental hash collision.
Your reasoning is based on the established common-law regarding signatures vs the lack of any established precedent for cryptography. This filters into T&C because of course, with every step into a new technology the banks are going to picket that territory in their favour. You prefer the old territory not because it is more fertile, but because you happen to possess a map. When JM makes decisions based on the narrow criteria of what’s good for JM, that is indeed rational but not of any benefit to someone attempting to design systemic improvements that might make fraud more difficult across the board.
I’d be a bit curious if people would reveal their intuition on who they think knew the email in question was a fake. Naturally I’m guessing that Malcolm Turnbull didn’t know, else he would not have stuck his neck out so far. Rumor has it that someone laid the tripwire for him, but that’s just rumor.
Posted on 27-Jun-09 at 11:53 am | PermalinkJust for the record, as far as I know the mag-stripe cards actually have the PIN encoded on the stripe. The logic is that ATMs can still verify a PIN when comms links are down, and those banks that allow you to change your PIN demand you do it on a special machine which actually puts your card through a rewrite phase (why bother rewriting the card if the PIN was only stored on central database). If you ask the bank about this they will obviously not tell the truth and pretend that the PIN is not encoded on the card, probably some people are fooled into thinking the system is slightly more secure than it really is. I personally regard such deception as fraudulent but I’m told that it is perfectly legal under the all purpose umbrella of “security by obscurity”.
In order to protect the PIN on a mag-stripe, cryptography is all you have. I don’t have any particular information about the algorithm design or how secure it might be (presumably yet another one-way hash like SHA-1, but with a secret step in the process), but putting a chip into the card means you can have both cryptographic mechanisms in the chip plus also other protections (e.g. a brute-force detector and self-destruct triggers). Chips are also intrinsically more difficult to copy because there is a hardware component, plus a software component. Extracting software out of a chip can be done by micro-milling and electron microscopy to measure charge in the floating gates — several orders of magnitude more difficult than copying a mag-stripe.
I’m fully in favour of the move toward chips in these cards.
Posted on 27-Jun-09 at 12:16 pm | PermalinkTel_
To put my objection to chip-n-pin and other forms of digital signatures in a nutshell: “real signatures have witness’s, digital ones don’t”.
I doubt that technology will ever be able to change that. Every attempt at foolproof substitutes has failed; fingerprints, iris, facial recognition. All of them.
Bottom line is that Schneier’s principle of “security is a process not a technnology” applies. All the fancy mathematics in the world won’t make a hash code a signature.
Lastly, I question how strong the processes actually are. Two examples:-
1. Over the last few years the NSA in the US has been required to report to congress the number of times (but not the circumstances) they have had to decrypt keys by brute force or use the various backdoors available to them. In the first 4 (?) years of this requirement they reported only a handful of incidents (less than 10 I believe)
2. In 2002 the CIA seized an encrypted Al Quaida laptop in Afghanistan and broke into it. The agent in charge was asked how they decrypted the files and responded “We didn’t have to this time, and we never have before. The keys are never kept safe enough.”
It’s worth remembering that the banks believe the NSA has been reading their encrypted payments traffic for years and this was confirmed a while back when it was publicly revealed that the NSA had been monitoring all SWIFT traffic almost since its inception.
Posted on 27-Jun-09 at 9:06 pm | Permalink